La capacité à reconnaître les intentions d’un agent est un élément important de l’analyse de la situation. Connaître ces intentions est souvent un facteur clé de la prise de décision dans plusieurs domaines tels que la robotique, les jeux vidéo, la sécurité informatique et l’analyse du renseignement. Une des approches algorithmiques souvent utilisées pour reconnaître les intentions d’un agent suppose une connaissance préalable de tous les plans exécutables par l’agent observé. À partir de ces plans et des données d’observation, on peut alors prédire les comportements et les intentions de l’agent observé simplement en générant les modèles d’exécution de plans cohérents avec les données d’observation. Ces modèles d’exécution constituent en quelque sorte les hypothèses sur le plan et le but poursuivi par l’agent observé. Ainsi, la probabilité que l’agent observé poursuive un but particulier est établie comme étant la proportion des modèles cohérents avec ce but. Cette approche existe depuis une dizaine d’années et fait partie des approches les plus étudiées en ce moment. Cependant, elle comporte des lacunes fondamentales, notamment une explosion combinatoire de la taille de l’espace d’hypothèses. Ce mémoire de maîtrise propose un algorithme permettant d’aborder ce dernier problème en contrôlant l’exploration de l’espace d’hypothèse. Avec ce nouvel algorithme, on peut approximer la probabilité du but, de sorte que la précision de l’approximation s’améliore graduellement avec le temps de calcul. Cette approche a été publiée dans l’une des deux plus prestigieuses conférences scientifiques sur l’intelligence artificielle : International Joint Conference on Artificial Intelligence (IJCAI), en 2013.

La capacité de reconnaître les intentions des autres est une composante essentielle non seulement de l'intelligence humaine mais aussi de l'intelligence artificielle dans plusieurs domaines d'application. Pour les algorithmes d'intelligence artificielle, reconnaître l'intention d'un agent à partir d'une observation partielle de ses actions demeure un défi de taille. Par exemple dans les jeux de stratégie en temps réel, on aimerait reconnaître les intentions de son adversaire afin de mieux contrer ses actions futures. En domotique, on voudrait une maison capable de comprendre et d'anticiper les intentions de ses habitants pour maximiser leur confort et les assister dans leurs activités quotidiennes. Dans le domaine de la sécurité informatique, un outil de détection des intrus doit pouvoir observer les actions des usagers du réseau et déceler ceux qui ont des intentions malveillantes. Ce mémoire de maîtrise propose d'aborder ce problème sous observabilité partielle par adaptation des méthodes utilisées dans l'analyse grammaticale probabiliste. L'approche probabiliste considérée utilise une grammaire hors contexte de multi-ensemble partiellement ordonnée et considère la poursuite de plusieurs buts simultanément, ordonnés ou non. Cela revient donc à faire de l'analyse grammaticale probabiliste avec plusieurs symboles de départ.

Ce mémoire propose une approche pour la reconnaissance de plan qui a été conçue pour les environnements avec des adversaires, c'est-à-dire des agents qui veulent empêcher que leurs plans soient reconnus. Bien qu'il existe d'autres algorithmes de reconnaissance de plan dans la littérature, peu sont adaptés pour de tels environnements. L'algorithme que nous avons conçu et implémenté (PROBE, Provocation for the Recognition of Opponent BEhaviours ) est aussi capable de choisir comment provoquer l'adversaire, en espérant que la réaction de ce dernier à la provocation permette de donner des indices quant à sa véritable intention. De plus, PROBE utilise des machines à états finis comme représentation des plans, un formalisme différent de celui utilisé par les autres approches et qui est selon nous mieux adapté pour nos domaines d'intérêt. Les résultats obtenus suite à différentes expérimentations indiquent que notre algorithme réussit généralement à obtenir une bonne estimation des intentions de l'adversaire dès le départ et que cette estimation s'améliore lorsque de nouvelles actions sont observées. Une comparaison avec un autre algorithme de reconnaissance de plan démontre aussi que PROBE est plus efficace en temps de calcul et en utilisation de la mémoire, sans pourtant sacrifier la qualité de la reconnaissance. Enfin, les résultats montrent que notre algorithme de provocation permet de réduire l'ambiguïté sur les intentions de l'adversaire et ainsi améliorer la justesse du processus de reconnaissance de plan en sélectionnant une provocation qui force l'adversaire, d'une certaine façon, à révéler son intention.

Les intersections sont les zones les plus dangereuses du réseau routier. Les statistiques montrent que la plupart des accidents aux intersections sont causés par des erreurs des conducteurs, et que la plupart pourraient être évités à l'aide de systèmes d'aide à la conduite. En particulier, les communications inter-véhiculaires ouvrent de nouvelles opportunités pour les applications sécuritaires aux intersections. Le partage d'informations entre les véhicules via des liens sans fil permet aux véhicules de percevoir leur environnement au-delà des limites du champ de vision des capteurs embarqués. Grâce à cette représentation élargie de l'environnement dans l'espace et dans le temps, la compréhension de situation est améliorée et les situations dangereuses peuvent être détectées plus tôt. Cette thèse aborde le problème de l'estimation du risque aux intersections d'un nouveau point de vue : une structure de raisonnement est proposée pour analyser les situations routières et le risque de collision à un niveau sémantique plutôt qu'au niveau des trajectoires. Le risque est déterminé en estimant les intentions des conducteurs et en identifiant les potentiels conflits, sans avoir à prédire les futures trajectoires des véhicules. L'approche proposée a été validée par des expérimentations en environnement réel à l'aide de véhicules équipés de modems de communication véhicule-véhicule, ainsi qu'en simulation. Les résultats montrent que l'algorithme permet de détecter les situations dangereuses à l'avance et qu'il respecte les contraintes temps-réel des applications sécuritaires. Il y a deux différences principales entre l'approche proposée et les travaux existants. Premièrement, l'étape de prédiction de trajectoire est évitée. Les situations dangereuses sont identifiées en comparant ce que les conducteurs ont l'intention de faire avec ce qui est attendu d'eux d'après les règles de la circulation et le contexte. Le raisonnement sur les intentions et les attentes est réalisé de manière probabiliste afin de prendre en compte les incertitudes des mesures capteur et les ambiguïtés sur l'interprétation. Deuxièmement, le modèle proposé prend en compte les informations sur le contexte situationnel, c'est-à-dire que l'influence de la géométrie de l'intersection et des actions des autres véhicules est prise en compte lors de l'analyse du comportement d'un véhicule. / Intersections are the most complex and dangerous areas of the road network. Statistics show that most road intersection accidents are caused by driver error and that many of them could be avoided through the use of Advanced Driver Assistance Systems. In particular, vehicular communications open new opportunities for safety applications at road intersections. The sharing of information between vehicles over wireless links allows vehicles to perceive their environment beyond the field-of-view of their on-board sensors. Thanks to this enlarged representation of the environment in time and space, situation assessment is improved and dangerous situations can be detected earlier. This thesis tackles the problem of risk estimation at road intersections from a new perspective: a framework is proposed for reasoning about traffic situations and collision risk at a semantic level instead of at a trajectory level. Risk is assessed by estimating the intentions of drivers and looking for conflicts in them, rather than by predicting the future trajectories of the vehicles and looking for intersections between them. The proposed approach was validated in field trials using passenger vehicles equipped with vehicle-to-vehicle wireless communication modems, and in simulation. The results demonstrate that this algorithm allows the early detection of dangerous situations in a reliable manner and complies with real-time constraints. The proposed approach differs from previous works in two key aspects. Firstly, it does not rely on trajectory prediction to assess the risk of a situation. Dangerous situations are identified by comparing what drivers intend to do with what they are expected to do according to the traffic rules and the current context. The reasoning about intentions and expectations is performed in a probabilistic manner to take into account sensor uncertainties and interpretation ambiguities. Secondly, the proposed motion model includes information about the situational context. Both the layout of the intersection and the actions of other vehicles are taken into account as factors influencing the behavior of a vehicle.

Durant ces travaux de thèse, une comparaison empirique de différentes<br />techniques d'apprentissage de structure de réseaux bayésiens a été<br />effectuée, car même s'il peut en exister très ponctuellement, il<br />n'existe pas de comparaisons plus globales de ces algorithmes.<br />De multiples phases de tests nous ont permis d'identifier quelles<br />méthodes souffraient de difficultés d'initialisation et nous avons<br />proposé une technique pour les résoudre.<br />Nous avons ensuite adapté différentes méthodes d'apprentissage de<br />structure aux bases de données incomplètes et avons notamment<br />introduit une technique pour apprendre efficacement une structure arborescente.<br />Cette méthode est ensuite adaptée à la problématique plus spécifique<br />de la classification et permet d'apprendre efficacement et en toute<br />généralité un classifieur de Bayes Naïf augmenté.<br />Un formalisme original permettant de générer des bases de données<br />incomplètes ayant des données manquantes vérifiant les hypothèses MCAR<br />ou MAR est également introduit.<br />De nombreuses bases synthétiques ou réelles ont alors été utilisées<br />pour tester ces méthodes d'apprentissage de structure à partir de<br />bases incomplètes.

Les intersections sont les zones les plus dangereuses du réseau routier. Les statistiques montrent que la plupart des accidents aux intersections sont causés par des erreurs des conducteurs, et que la plupart pourraient être évités à l'aide de systèmes d'aide à la conduite. En particulier, les communications inter-véhiculaires ouvrent de nouvelles opportunités pour les applications sécuritaires aux intersections. Le partage d'informations entre les véhicules via des liens sans fil permet aux véhicules de percevoir leur environnement au-delà des limites du champ de vision des capteurs embarqués. Grâce à cette représentation élargie de l'environnement dans l'espace et dans le temps, la compréhension de situation est améliorée et les situations dangereuses peuvent être détectées plus tôt. Cette thèse aborde le problème de l'estimation du risque aux intersections d'un nouveau point de vue : une structure de raisonnement est proposée pour analyser les situations routières et le risque de collision à un niveau sémantique plutôt qu'au niveau des trajectoires. Le risque est déterminé en estimant les intentions des conducteurs et en identifiant les potentiels conflits, sans avoir à prédire les futures trajectoires des véhicules. L'approche proposée a été validée par des expérimentations en environnement réel à l'aide de véhicules équipés de modems de communication véhicule-véhicule, ainsi qu'en simulation. Les résultats montrent que l'algorithme permet de détecter les situations dangereuses à l'avance et qu'il respecte les contraintes temps-réel des applications sécuritaires. Il y a deux différences principales entre l'approche proposée et les travaux existants. Premièrement, l'étape de prédiction de trajectoire est évitée. Les situations dangereuses sont identifiées en comparant ce que les conducteurs ont l'intention de faire avec ce qui est attendu d'eux d'après les règles de la circulation et le contexte. Le raisonnement sur les intentions et les attentes est réalisé de manière probabiliste afin de prendre en compte les incertitudes des mesures capteur et les ambiguïtés sur l'interprétation. Deuxièmement, le modèle proposé prend en compte les informations sur le contexte situationnel, c'est-à-dire que l'influence de la géométrie de l'intersection et des actions des autres véhicules est prise en compte lors de l'analyse du comportement d'un véhicule.

Dans cette thèse, nous proposons une méthode pour construire un outil d'aide à la décision pour le diagnostic de maladie rare. Nous cherchons à minimiser le nombre de tests médicaux nécessaires pour atteindre un état où l'incertitude concernant la maladie du patient est inférieure à un seuil prédéterminé. Ce faisant, nous tenons compte de la nécessité dans de nombreuses applications médicales, d'éviter autant que possible, tout diagnostic erroné. Pour résoudre cette tâche d'optimisation, nous étudions plusieurs algorithmes d'apprentissage par renforcement et les rendons opérationnels pour notre problème de très grande dimension. Pour cela nous décomposons le problème initial sous la forme de plusieurs sous-problèmes et montrons qu'il est possible de tirer partie des intersections entre ces sous-tâches pour accélérer l'apprentissage. Les stratégies apprises se révèlent bien plus performantes que des stratégies gloutonnes classiques. Nous présentons également une façon de combiner les connaissances d'experts, exprimées sous forme de probabilités conditionnelles, avec des données cliniques. Il s'agit d'un aspect crucial car la rareté des données pour les maladies rares empêche toute approche basée uniquement sur des données cliniques. Nous montrons, tant théoriquement qu'empiriquement, que l'estimateur que nous proposons est toujours plus performant que le meilleur des deux modèles (expert ou données) à une constante près. Enfin nous montrons qu'il est possible d'intégrer efficacement des raisonnements tenant compte du niveau de granularité des symptômes renseignés tout en restant dans le cadre probabiliste développé tout au long de ce travail. / In this thesis, we propose a method to build a decision support tool for the diagnosis of rare diseases. We aim to minimize the number of medical tests necessary to achieve a state where the uncertainty regarding the patient's disease is less than a predetermined threshold. In doing so, we take into account the need in many medical applications, to avoid as much as possible, any misdiagnosis. To solve this optimization task, we investigate several reinforcement learning algorithm and make them operable in our high-dimensional. To do this, we break down the initial problem into several sub-problems and show that it is possible to take advantage of the intersections between these sub-tasks to accelerate the learning phase. The strategies learned are much more effective than classic greedy strategies. We also present a way to combine expert knowledge, expressed as conditional probabilities, with clinical data. This is crucial because the scarcity of data in the field of rare diseases prevents any approach based solely on clinical data. We show, both empirically and theoretically, that our proposed estimator is always more efficient than the best of the two models (expert or data) within a constant. Finally, we show that it is possible to effectively integrate reasoning taking into account the level of granularity of the symptoms reported while remaining within the probabilistic framework developed throughout this work.