Reasoning about concurrent actions and its applications to epistemic and temporal planning

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.Planning is a problem of the domain of artificial intelligence that can be applied to many areas. In this thesis we are interested in extending the possibilities of planning to model realistic problems. We oppose toy problems such as muddy children with problems that can be encountered in the real world. Real world problems have features that need to be taken into account in their resolution. They are often multi-agent and require the ability to reason on the knowledge of the agents, we call this epistemic reasoning. The actions of the agents may require a certain amount of time to be fully executed and the agents may perform actions in parallel. Finally, actions may have unpredictable consequences or independent events may occur. Different areas of planning have been studied to add these aspects to classical planning. Although the multi-agent aspect has been studied in combination with the other three, the other combinations have been studied little or not at all. The aim of this thesis is to provide elements to allow planning of multi-agent, temporal and epistemic problems. These three aspects (multi-agent, temporal and epistemic, abbreviated to MaTEp) seem to us the most important to associate. Uncertainty is a much more significant addition since it can be present at multiple levels in problems and can be managed in many different ways. We begin by presenting a family of MaTEp planning problems, the temporal and epistemic gossip problems. The epistemic gossip problem is a problem where there are several agents, each with information known only to them. They can call each other to share the entirety of the knowledge they have, about each other's information but also about the agents' knowledge about this information. The goal is then to have a knowledge shared by all the agents up to a certain depth. With a depth of 1, we want all agents to know all the secrets. With a depth of 2 we also want everyone to know that everyone knows all the secrets. Here we generalise this problem by adding time constraints on communications. Agents can only call each, other or are forced to call each other, at some given instants. We show that this family of problems is NP-complete, even if we add negative goals such as having agent i ignore the secret of agent j. We then present a dynamic logic called dynamic logic of parallel propositional assignments (DL-PPA) with parallel programs. We show that the problems of satisfiability and model-checking are both PSPACE-complete. This proof is made through a polynomial reduction to the dynamic logic of propositional assignments (DL-PA) logic on which DL-PPA is based