Ce mémoire présente une comparaison de deux algorithmes de reconnaissance de plan, soit YAPPR (Yet Another Probabilistic Plan Recognizer) et PR-Plan (Plan Recognizer as Planning). Afin de comparer les algorithmes, nous avons voulu utiliser un domaine plus complexe et réaliste que ceux utilisés jusqu’à présent. Pour ce faire, nous avons établi un protocole de comparaison en utilisant le concept d’observation in situ. Nous avons utilisé le jeu de stratégie en temps réel StarCraft comme environnement de simulation. Puis, nous avons créé un agent jouant à StarCraft qui utilise la reconnaissance de plan comme élément central pour le système de prise de décision. Pour valider que notre principe d’observation in situ fonctionne, nous avons créé des agents témoins et exécuté de nombreuses simulations.

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.

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.

L’intelligence artificielle est un domaine de l’informatique étudiant la conception d’agents intelligents. Un agent est une entité acquérant de l’information sur son environnement par ses capteurs et agissant sur son environnement à travers ses actionneurs. Certains agents existent seulement dans le domaine logiciel, comme par exemple un agent intelligent pour un jeu vidéo, alors que d’autres existent dans le monde physique, tels les robots mobiles. Les domaines des jeux vidéo et de la robotique partagent certaines caractéristiques, dont la nécessité de prendre des décisions en temps réel dans un environnement dynamique ainsi qu’une vue incomplète sur cet environnement. Ce mémoire est divisé en deux chapitres. Le premier chapitre traite d’une approche de planification de trajectoires exploitant la géométrie d’une classe particulière de robots omnidirectionnels non-holonomes afin de calculer des chemins adéquats leur permettant d’atteindre une destination désirée. Les résultats obtenus avec cette approche tendent à démontrer qu’elle est plus efficace que les algorithmes traditionnels de planification de trajectoires grâce à l’information additionnelle prise en compte lors du calcul. Le second chapitre décrit l’architecture décisionnelle de l’agent intelligent SPAR qui est en mesure de jouer de façon autonome des parties de StarCraft : Brood War, un jeu de stratégie en temps réel. L’architecture de SPAR inclut entre autres des algorithmes de planification de trajectoires similaires à ceux du premier chapitre. Elle permet de faire face plus facilement et de façon plus rigoureuse, en comparaison avec les architectures existantes, aux nombreuses difficultés propres à ce type de jeu. Ces difficultés incluent un degré élevé de concurrence dans les actions et une multitude d’unités à contrôler dans un contexte temps réel. L’agent SPAR a participé aux volets 2011 et 2012 de la compétition AIIDE de StarCraft et à l’édition 2012 de la compétition SSCAI où il a obtenu à chaque fois des résultats honorables.

Pour respecter les droits d’auteur, la version électronique de ce mémoire a été dépouillée de ses documents visuels et audio‐visuels. La version intégrale du mémoire a été déposée au Service de la gestion des documents et des archives de l'Université de Montréal. / Cette recherche propose une analyse du jeu de stratégie en temps réel StarCraft (Blizzard Entertainment, 1998). Il s’agit de questionner le concept de stratégie dans le jeu sans s’en tenir à ce qu’on peut voir et entendre. Ce mémoire débute sur une description du jeu en détails afin de faire ressortir comment la stratégie joue un rôle dans l’ensemble des compétences qui y sont mobilisées. Ensuite, le cercle heuristique du processus stratégique offre une modélisation du fonctionnement de la stratégie en tant que processus cognitif, basé sur les états du jeu inférés chez le joueur et sur ses plans stratégiques. Ce modèle et les concepts qui en découlent sont consolidés par des analyses de parties spécifiques de StarCraft. / This thesis offers an analysis of the Real-Time Strategy game StarCraft (Blizzard Entertainment, 1998). Its goal is to explore beyond the visible and audible part of the game to elucidate the concept of strategy into play. Following a description of the game and its constraints, it demonstrates how strategy plays a major role within the skills needed to play. Then, our “heuristic circle of the strategic process” describes how strategy works as a cognitive process, and how it interacts with both the game states inferred by the player and his or her strategic plans. Finally, this model and its underlying concepts are supported by close analyses of StarCraft game sequences.

Cette recherche propose une analyse du jeu de stratégie en temps réel StarCraft (Blizzard Entertainment, 1998). Il s’agit de questionner le concept de stratégie dans le jeu sans s’en tenir à ce qu’on peut voir et entendre. Ce mémoire débute sur une description du jeu en détails afin de faire ressortir comment la stratégie joue un rôle dans l’ensemble des compétences qui y sont mobilisées. Ensuite, le cercle heuristique du processus stratégique offre une modélisation du fonctionnement de la stratégie en tant que processus cognitif, basé sur les états du jeu inférés chez le joueur et sur ses plans stratégiques. Ce modèle et les concepts qui en découlent sont consolidés par des analyses de parties spécifiques de StarCraft. / This thesis offers an analysis of the Real-Time Strategy game StarCraft (Blizzard Entertainment, 1998). Its goal is to explore beyond the visible and audible part of the game to elucidate the concept of strategy into play. Following a description of the game and its constraints, it demonstrates how strategy plays a major role within the skills needed to play. Then, our “heuristic circle of the strategic process” describes how strategy works as a cognitive process, and how it interacts with both the game states inferred by the player and his or her strategic plans. Finally, this model and its underlying concepts are supported by close analyses of StarCraft game sequences. / Pour respecter les droits d’auteur, la version électronique de ce mémoire a été dépouillée de ses documents visuels et audio‐visuels. La version intégrale du mémoire a été déposée au Service de la gestion des documents et des archives de l'Université de Montréal.