LogoLogo

Vianey, Julien. Raisonnement avec des actions concurrentes et ses applications à la planification épistémique et temporelle

Vianey, Julien (2020). Raisonnement avec des actions concurrentes et ses applications à la planification épistémique et temporelle.

[img]PDF - nécessite un logiciel de visualisation PDF comme GSview, Xpdf or Adobe Acrobat Reader
1148Kb

Résumé en francais

La planification est un problème d'intelligence artificielle pouvant être appliquée à de nombreux domaines. Dans cette thèse nous nous intéressons à étendre les possibilités de la planification pour représenter des problèmes réalistes. Nous opposons les problèmes jouets comme les enfants sales ("muddy children") aux problèmes que l'on peut rencontrer dans le monde réel. Les problèmes du monde réel vont présenter différentes caractéristiques qu'il faudra pouvoir prendre en compte dans leur résolution. Ils sont bien souvent multi-agent et demandent de pouvoir raisonner sur la connaissance des agents, ce que l'on appelle raisonnement épistémique. Les actions des agents peuvent nécessiter une certaine durée pour se réaliser et les agents peuvent les réaliser en parallèle. Enfin, les actions peuvent avoir des conséquences imprévisibles ou des événements indépendants peuvent se produire. Différents domaines de planification ont été étudiés pour ajouter ces différents aspects à la planification classique. Bien que l'aspect multi-agent ait été étudié en combinaison avec les trois autres, les autres combinaisons ne l'ont pas ou peu été. Le but de cette thèse est d'apporter des éléments pour permettre de résoudre des tâches de planification multi-agent, temporelles et épistémiques. Ces trois aspects (multi-agent, temporel et épistémique, abrégé en MaTEp) nous semblent les plus importants à associer. L'incertain représente un ajout bien plus conséquent puisqu'il peut être présent à de multiples niveaux dans les problèmes et il peut être géré de très nombreuses manières. Nous commençons par présenter une famille de problèmes de planification MaTEp, les problèmes de bavardage temporels et épistémiques. Le problème du bavardage épistémique est un problème où plusieurs agents ont chacun une information connue d'eux seuls. Ils peuvent s'appeler pour partager l'intégralité des connaissances qu'ils ont, sur les informations de chacun mais aussi sur la connaissance des agents sur ces informations. Le but est alors d'avoir une connaissance partagée par tous les agents jusqu'à une certaine profondeur. Avec une profondeur de 1 on voudra que tous les agents connaissent tous les secrets. Avec une profondeur de 2 on voudra également que tous sachent que tous connaissent tous les secrets. Nous généralisons ici ce problème en ajoutant des contraintes temporelles sur les communications. Les agents ne peuvent s'appeler ou sont forcés de s'appeler à certains moments. Nous montrons que cette famille de problèmes est NP-complète, et ce même si on ajoute des buts négatifs comme avoir l'agent i qui ignore le secret de l'agent j. Nous présentons ensuite une logique dynamique que l'on appelle logique dynamique d'affectations propositionnelles parallèles (DL-PPA) avec des programmes parallèles. Nous montrons que les problèmes de satisfiabilité et de model-checking sont tous les deux PSPACE-complets. Cette preuve est faite via une réduction polynomiale vers la logique dynamique d'affectations propositionnelles (DL-PA) sur laquelle DL-PPA est basée. Cette logique est ensuite appliquée à la planification classique. Le problème de recherche de l'existence d'une solution à un problème de planification peut être traduit en une formule DL-PPA. Nous présentons des traductions pour des solutions permettant l'exécution d'actions en parallèle ainsi que pour des solutions n'autorisant qu'une exécution séquentielle. Ces même programmes peuvent être modifiés pour modéliser la recherche de solution à horizon borné, c'est à dire des plans de longueur restreinte. La dernière partie présente une traduction d'un problème de planification épistémique vers un problème de planification classique. Le problème de planification épistémique est décrit dans une logique statique, EL-O, avec une description des transitions d'états via une fonction partielle. Nous montrons que ce problème peut être traduit polynomialement de la planification épistémique avec EL-O vers de la planification classique. Cette traduction implique que la planification épistémique présentée est dans PSPACE. Dans le même esprit, en nous basant sur notre modèle de planification épistémique nous avons créé des domaines et problèmes PDDL. Ces problèmes ont été testés avec des planificateurs de la compétition internationale de planification (IPC) de 2018. Nous avons comparé les temps d'exécution nécessaires aux planificateurs pour donner une solution. Ces résultats sont similaires pour les différents planificateurs testés et montrent que ces types de problèmes ne sont pas évidents pour des planificateurs au top de l'état de l'art.

Sous la direction du :
Directeur de thèse
Herzig, Andreas
Maris, Frédéric
Ecole doctorale:Mathématiques, informatique, télécommunications de Toulouse (MITT)
laboratoire/Unité de recherche :Institut de Recherche en Informatique de Toulouse (IRIT), UMR 5505
Mots-clés libres :Logique épistémique - Multi-agent - Raisonnement temporel - Planification
Sujets :Informatique
Déposé le :03 Dec 2021 16:11