Karen Godary-Dejean

Alain Redlinger

Antony Guillaume

Martin Laurie

Keywords: logique épistémique, multi-agent, raisonnement temporel, planification epistemic logic, multi-agent, temporal reasoning, planning Je tiens tout d

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.

Introduction

This first chapter describes the definitions used in the thesis. The first section is about some generic definitions that are not fully spelled out. The following sections describe some instantiations. These sections are about some variants of automated planning problems. The first one is classical planning, the simplest form of planning. The second adds some reasoning over the agents knowledge. The third is about planning with temporally extended actions. The last one combines all of this in epistemic temporal planning.

The last section of this chapter explains the contribution of this thesis.

1 Introduction

Résumé du chapitre en français

Ce chapitre présente les définitions utilisées dans le reste de la thèse. On suppose donnés un ensemble d'états, un ensemble d'actions et un ensemble de formules construites sur un ensemble de fluents. Une tâche de planification est composée d'un état initial, une fonction modélisant les actions et une formule de but. On distingue deux types de plans, les plans séquentiels et les plans parallèles. Dans un plan séquentiel, une action est appliquée à un état pour créer l'état suivant tandis que dans un plan parallèle il s'agit d'un ensemble d'actions qui sont appliquées. Un plan séquentiel est donc un ensemble ordonné d'actions et un plan parallèle est un ensemble ordonné d'ensembles d'actions.

La forme la plus simple de planification est appelée planification classique. En planification classique les fluents sont des variables propositionnelles. Un état est un ensemble de fluents, ceux ci sont les fluents vrais dans cet état, les autres étant faux. Le but est une formule propositionnelle. Les actions sont composées d'une précondition qui doit être vraie pour que l'action puisse être exécutée et d'un ensemble d'effets. Dans leur forme la plus simple les effets sont séparés en effets positifs (ensemble de fluents ajoutés à l'état) et effets négatifs (ensemble de fluents supprimés de l'état). Cette définition étant limitée, différentes extensions ont été proposées, notamment les effets conditionnels. Un effet conditionnel est composé d'une condition et d'ensembles d'effets positifs et négatifs. Si une action est exécutée, tous les effets dont la condition est vraie verront leurs effets appliqués, les autres effets ne seront pas appliqués. En planification classique, un plan est dit plan solution si son execution depuis l'état initial amène à un état où le but est vrai.

La planification épistémique est la forme de planification incluant un raisonnement sur la connaissance des agents. Selon le langage utilisé, la connaissance peut être ajoutée aux fluents ou aux formules en utilisant des opérateurs de connaissance. La logique dynamique épistémique la plus courante (DEL) utilise la deuxième solution. DEL est intéressante par sa grande expressivité mais cela implique une complexité élevée. La planification DEL a été prouvée indécidable. Pour pouvoir étudier des problèmes de planification épistémiques solvables en un temps raisonnable, différentes approches ont été étudiées. Ces approches ajoutent des restrictions soit sur l'aspect épistémique soit sur l'aspect dynamique. Pour le premier il s'agit généralement de contraindre l'utilisation de l'opérateur de connaissance sur les fluents. Les contraintes dynamiques modifient la connaissance des agents sur les actions, celles ci peuvent par exemple être toutes publiques. Dans la suite de cette thèse nous utilisons EL-O pour la partie épistémique. Il s'agit d'une logique épistémique allégée basée sur des opérateurs de visibilité. Le fonctionnement de ces opérateursun agent voit si plutôt que de savoir que -permet de contourner certaines contraintes ajoutées par le choix d'avoir un opérateur appliqué seulement aux fluents tout en conservant les gains en complexité liés à ce choix.

L'objectif de cette thèse était de créer des outils d'aide à la planification pour les problèmes de la vie réelle. J'oppose ici les problèmes de la vie réelle aux problèmes jouets qui ont un intérêt philosophique mais qui ne se trouveront jamais dans la vie réelle. Je me suis concentré sur la réunion de trois aspects différents que l'on trouve couramment dans les problèmes de la vie réelle : multi-agents, les actions étendues dans le temps et le raisonnement sur la connaissance des agents. Les problèmes de planification temporelle et épistémique multi-agents peuvent être utiles de nombreuses façons. Nous pouvons les utiliser pour aider les gens à décider de la manière d'accomplir une tâche, par exemple pour les lignes de production d'une usine. Ils peuvent être utilisés dans les jeux vidéo pour l'IA de personnages non jouables ou pour générer la dynamique d'une histoire. Ou encore pour des robots plus intelligents, afin de déterminer les actions qu'ils doivent effectuer et quand ils doivent les faire. Comme nous voulons aider à planifier des problèmes de la vie réelle, nous voulons disposer d'outils qui peuvent trouver une solution dans un délai raisonnable. Comme la planification temporelle temporelle et épistémique est au moins aussi difficile que la planification classique, nous avons choisi leur complexité PSPACE-complète comme limite inférieure. Dans cette classe de complexité les problèmes avec un faible nombre d'actions et d'étapes peuvent être résolus mais les problèmes plus importants peuvent nécessiter une quantité énorme de temps qui pourrait ne pas être pratique. Nous voulions donc que les problèmes de planification soient dans PSPACE. Comme cela représentait déjà beaucoup de travail, nous avons choisi de ne considérer que les problèmes déterministes. Cela implique que l'aspect multiagents est présent dans la description et l'exécution du problème mais pas dans la recherche de la solution. Nous voyons la résolution comme étant effectuée de manière centralisée. Cela implique que cette localisation peut communiquer la partie pertinente du plan à chaque agent avant son exécution. Cela fonctionne bien pour les problèmes de coopération entre les agents. Pour les problèmes avec compétition entre les agents, le vainqueur de la compétition est choisi lorsque le problème est modélisé.

Introduction

Dans le chapitre 2, je présente les problèmes de bavardage épistémique temporel (TEGP). Ils sont une généralisation du problème du bavardage épistémique avec des contraintes temporelles sur les appels. Nous avons ajouté une durée pour toutes les actions d'appel et des contraintes sur les moments auxquels un appel entre deux agents est autorisé. Ce chapitre montre que les TEGP sont des problèmes NP-complets même avec des buts négatifs. Un exemple de but négatif est que l'on ne veut pas que l'agent i connaisse le secret de l'agent j. Ces problèmes montrent l'intérêt d'ajouter un aspect temporel aux problèmes épistémiques pour les rendre plus réalistes. Lorsque nous voulons communiquer avec d'autres personnes, il se peut que nous ne soyons pas en mesure de les appeler quand nous le voulons et que le plan le plus court ne soit pas le meilleur lorsque ces contraintes sont prises en compte. Nous avons alors voulu ajouter plus de flexibilité aux contraintes temporelles. Cela a conduit aux deux chapitres suivants. Le chapitre 3 présente une extension de DL-PA pour ajouter du parallélisme dans la logique. Ce chapitre montre que DL-PPA conserve la complexité PSPACE-complète de DL-PA. Ce résultat est ensuite utilisé pour une tâche de planification classique à horizon borné. Deux programmes qui sont équivalents au problème de l'existence d'un plan de k étapes ou moins sont décrits. Une autre approche de la planification épistémique parallèle est décrite au chapitre 4. Cette fois ci, nous utilisons des actions EL-O et nous avons donc des actions épistémiques au lieu des actions classiques du chapitre précédent. Nous montrons que les actions EL-O peuvent être traduites en planification classique parallèle. Avec cette traduction, nous pouvons montrer que la planification parallèle EL-O est PSPACE-complète. Nous utilisons également la traduction vers la planification classique pour traduire certains problèmes épistémiques en PDDL. Cette dernière traduction nous a permis de tester certains de ces problèmes avec des planificateurs IPC et de comparer le temps d'obtention d'un plan.

Generic definitions

Generic definitions

We suppose given a set S of states and a set Act of action names, and a set of formulas Fml formed on a set F of fluents. I will use both action or action name with the same meaning. The set of boolean formulas Fml is defined by the following grammar:

ϕ f | ⊥ | ¬ϕ | ϕ 1 ∧ ϕ 2
where f ranges over the set of fluents F. We will use the abbreviations = ¬⊥ and ϕ 1 ∨ ϕ 2 = ¬(¬ϕ 1 ∧ ¬ϕ 2 ).

The precise nature of these sets will depend on the kind of planning under concern and will be detailed in the sequel. A planning task is a triple (s 0 , τ, Goal) with • s 0 ∈ S is the initial state • τ : Act × S → S is a partial function modeling the actions in Act1

• Goal ∈ Fml is the goal We say that an action a can be executed at a given state s if τ(a, s) is defined. In the following we use τ a as an abbreviation of τ(a, •). Then the result of the execution is a state s = τ a (s).

The solution of a planning task is an ordered set of actions called a plan. We call plans made of single actions sequential plans and plans made of sets of actions (steps) parallel plans. The execution of a plan consists of the ordered execution of the actions starting from a given state.

In order to define the execution of parallel plans several notions of interference have been proposed [START_REF] Knoblock | Generating Parallel Execution Plans with a Partial-order Planner[END_REF][START_REF] Dimopoulos | Encoding Planning Problems in Nonmonotonic Logic Programs[END_REF]. We choose the ∀-Step plan semantic of [START_REF] Rintanen | Planning as satisfiability: parallel plans and algorithms for plan search[END_REF] to build the interference rules. In such plans, actions of a step can be executed in any order with the same outcome. This rather restrictive definition is used in most approaches to parallel classical planning. For this, we extend the function τ to set of actions, with some restrictions. The execution of an empty set of actions τ ∅ is always defined and does not 1 Introduction change the state: τ ∅ (s) = s. We require τ A to be defined at a state s if and only if, for every action a ∈ A τ {a} is defined and in that case we require that τ A (s) = τ a (τ A\a (s)) = τ A\a (τ a (s)). This way, if τ A (s) is defined for a set A = {a 1 , . . . , a n }, then τ A (s) = τ a 1 (. . . (τ {an} (s)) . . .) for any ordering of the set.

Formally, the execution of a sequential plan a 0 , . . . , a n at a state s 0 is the sequence of states (s 0 , . . . , s n+1 ) where:

s i+1 = τ a i (s i )
and the execution of a parallel plan A 1 , . . . , A n at a state s 0 is defined as the sequence of states (s 0 , . . . , s n+1 ) where:

s i+1 = τ A i (s i )
To illustrate the different kinds of planning described here, I will use different variations of the gossip problem. The simplest one [START_REF] Akkoyunlu | Some Constraints and Tradeoffs in the Design of Network Communications[END_REF][START_REF] Hurkens | Spreading gossip efficiently[END_REF] has six agents. Each agent has a secret, something known by them and only them at the beginning, and the goal is for all the agents to know all the secrets. In order to achieve this goal, the agents can call each other to share all their knowledge.

Classical planning

The simplest form of automated planning [START_REF] Ghallab | Automated Planning: Theory & Practice[END_REF]) is called classical planning. Such planning tasks are modeled with propositional variables as fluents.

In the generalized gossip problem [START_REF] Maffre | Ignorance is bliss : observability-based dynamic epistemic logics and their applications[END_REF] there are n agents (noted i, j, etc.) who each have a secret, something known by them (ksec i,i ) but no one else (¬ksec j,i for j = i). The goal of the planning task is for all the agents to know all the secrets. In order to achieve this goal the agents can call each other.

During a one-way call (such as a letter or email) information only passes in one direction, whereas during a two-way call (such as a telephone conversation) information passes in both directions. In the case of parallel communication, several calls between distinct pairs of agents may take place simultaneously, but an agent can only participate in one call (either by or to another agent) 1.2 Classical planning at the same instant. Parallel communications can model usual multi agent communication problems. The sequential version, in which only one call can take place at the same time, is of interest when the aim is to minimise the total number of calls or when the communication channel is shared by the agents.

State description

The states of a classical planning task are sets of fluents. All the fluents in the set are true in this state and the other fluents are false. In the generalized gossip problem, the initial state is s 0 = {ksec i,i : i ∈ {1..n}}.

Action description

In classical planning, an action a is described with a precondition pre(a) which must be true for the action to be executed, and a set of effects eff (a), describing the consequences of the action. The effects are fluents that are added or deleted from the current state. These effects may have conditions of their own, in that case they are called conditional effects. We require that the actions descriptions are consistent, that is when executed in a given state s, for any fluent f , an action cannot delete and add f .

Without conditional effects

The simplest form of action description is that of STRIPS [START_REF] Fikes | STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving[END_REF] (Stanford Research Institute Problem Solver). In this language, preconditions are limited to a conjunction of fluents that must be true and fluents that must be false in order for the action to be executable. The same limitation applies to the goal formula.

The effects are divided in two sets: eff + (a) is the set of fluents that are added to the state after the execution of a and eff -(a) is the set of fluents that are deleted from the state. The partial function τ a is as follows:

τ a (s) = (s \ eff -(a)) ∪ eff + (a) if s |= pre(a)
undef otherwise As a's description is consistent it does not matter in which order we apply negative and positive effects.

Introduction

For the gossip problem it is:

τ Call i,j (s) = s ∪ {ksec i,k : k ∈ {1..n}, ksec j,k ∈ s} ∪ {ksec j,k : k ∈ {1..n}, ksec i,k ∈ s}
In the case of parallel plans, we require that the set of actions A executed on a given step has no contradictory effects. This means that for any pair of actions a 1 , a 2 ∈ A, eff + (a 1 ) ∩ eff -(a 2 ) = ∅. For example, opening and closing a door have contradictory effects. We also want to avoid cross-interaction.

Here, this means that for two distinct actions a 1 , a 2 ∈ A, a 1 cannot add a fluent that must be false for pre(a 2 ) nor delete a fluent that must be true for pre(a 2 ). For example, closing a door will interact with crossing it. We say that a set of actions without contradictory effects and cross-interaction in a state s is consistent in s. Those constraints are more restrictive than accepting all ∀-Step plans but are simpler to test within our logics and give only ∀-Step plans. Under these restrictions testing whether a ∀-step plan is valid is polytime while it is CoNP-complete for any generic ∀-step plan [START_REF] Rintanen | Planning as satisfiability: parallel plans and algorithms for plan search[END_REF].

With conditional effects

STRIPS being limited, some other languages were proposed to extend the description of actions. The most widespread one, and the only one I will write about, is PDDL [START_REF] Mcdermott | PDDL -The Planning Domain Definition Language[END_REF]) (Planning Domain Definition Language).

In PDDL, the preconditions of actions and the goal can be any boolean formula and the actions can have conditional effects. Here we will only consider non recursive conditional effects, which is usually called conditional STRIPS. In this case, a conditional effect ce has a condition cnd(ce) and positive eff + (ce) and negative eff -(ce) effects. As we can express unconditional effects as conditional effects that have as a condition, we can reduce the description of an action to a tuple a = (pre(a), eff (a)). When the action a is executed in a state s, all the conditional effects ce ∈ eff (a) of a are executed. When a conditional effect is executed, if its condition is true in the state s, all the fluents in eff + (ce) are added to the state and all the fluents in eff -(ce) are deleted.

Classical planning

Formally:

τ a (s) =        (s \ ce∈eff (a) s|=cnd(ce) eff -(ce)) ∪ ce∈eff (a) s|=cnd(ce) eff + (ce) if s |= pre(a) undef otherwise
As in STRIPS planning, for parallel plans we require consistent actions sets. A set of actions A is said to be free of contradictory effects in a state s if and only if for any pair of actions a 1 , a 2 ∈ A and for every ce 1 ∈ eff (a 1 )

and ce 2 ∈ eff (a 2 ), if s |= ce 1 ∧ ce 2 then eff + (ce 1 ) ∩ eff -(ce 2 ) = ∅.
For the cross-interaction, we generalise the definition used for STRIPS planning. We say that two states s and s agree on a formula ϕ if and only if either s |= ϕ and s |= ϕ or s |= ϕ and s |= ϕ. Then we say that two different actions a 1 and a 2 have no cross-interaction at s if the following hold:

1. s and τ a 1 (s) agree on pre(a 2 ) and on the condition cnd(ce 2 ) of every conditional effect ce 2 ∈ eff (a 2 );

2. s and τ a 2 (s) agree on pre(a 1 ) and on the condition cnd(ce 1 ) of every conditional effect ce 1 ∈ eff (a 1 ).

Goal and preconditions description

In classical planning the goal and the preconditions are both boolean formulas over the set of fluents. However, depending on the language used, there can be some restrictions on these formulas. They are usually the same for both the goal and the preconditions.

In STRIPS the formulas can only be conjunctions of fluents and negations of fluents. In PDDL the formulas can use the full set of boolean formulas described above.

For the generalised gossip problem, the goal is Goal = i,j∈{1..n} ksec i,j .

Solution description

For a plan to be a solution of a classical planning task, the goal formula must be true in the state reached after the execution of the plan on the initial state.

When describing a planning task with the definitions above this cannot be 1 Introduction verified in classical propositional logic. In the use cases of STRIPS or PDDL the verification is done in some meta-language. Therefore, the dynamic aspect of planning is implicit when describing a planning task in these languages. However, we may want to have an explicit definition of both the planning task and the validity of a solution for this task in a formal logic. To do this, one can use two dynamic logics, one for sequential planning only and one for both sequential and parallel plans.

Sequential

For sequential plans, we will use DL-PA [START_REF] Herzig | A Dynamic Logic of Normative Systems[END_REF]) (Dynamic Logic of Propositional Assignments). With DL-PA, we can describe a planning task with any boolean formulas for the goal and preconditions and conditions of conditional effects. We can also describe τ A but only for single actions (i.e. A is a singleton). DL-PA is interesting for classical planning [START_REF] Herzig | On the revision of planning tasks[END_REF], in particular because of the complexity of satisfiability checking is in PSPACE. This matches with the complexity of determining plan existence [START_REF] Bylander | The Computational Complexity of Propositional STRIPS Planning[END_REF] which is PSPACE-complete.

Parallel

Many authors have investigated how planning problems and their solutions can be represented in Propositional Dynamic Logic PDL, including work on conformant and contingent planning and planning with epistemic actions [START_REF] Spalazzi | A dynamic logic for acting, sensing, and planning[END_REF][START_REF] Andersen | Conditional Epistemic Planning[END_REF][START_REF] Li | More for free: a dynamic epistemic framework for conformant planning over transition systems[END_REF][START_REF] Bolander | Better Eager Than Lazy? How Agent Types Impact the Successfulness of Implicit Coordination[END_REF][START_REF] Cong | Small Undecidable Problems in Epistemic Planning[END_REF]. However and to the best of our knowledge, it has not been investigated yet how planning with concurrent actions can be captured in dynamic logic. Probably the reason for that is that there is no consensus on the semantics of parallel actions in the PDL community: there are proposals interpreting parallel composition as interleaving [START_REF] Mayer | The Complexity of PDL with Interleaving[END_REF][START_REF] Benevides | Propositional dynamic logics for communicating concurrent programs with CCS's parallel operator[END_REF], as intersection [START_REF] Balbiani | PDL with Intersection of Programs: A Complete Axiomatization[END_REF], and as relations between states and sets of states [START_REF] Peleg | Concurrent dynamic logic[END_REF][START_REF] Goldblatt | Parallel Action: Concurrent Dynamic Logic with Independent Modalities[END_REF]. There are also extensions with modalities from resource separation logics [START_REF] Balbiani | Iteration-free PDL with storing, recovering and parallel composition: a complete axiomatization[END_REF][START_REF] Benevides | Propositional Dynamic Logic with Storing, Recovering and Parallel Composition[END_REF] Viana 2011; P. A. S. Veloso, S. R. M. Veloso, and Benevides 2014).

Epistemic planning

Tools to find a solution to a planning task

Theorem provers for logics such as DL-PA allow us to decide whether there exists a plan and to verify a given plan. However using these may not be the most efficient way to find a solution plan for a given planning task. To find a plan for a specific planning task we can use planners. There are many different kinds of planners that gives different kinds of solutions. Some will return an optimal plan, a plan with the minimum number of steps to achieve the goal. Some will return a suboptimal plan but will focus on the time and memory needed to find this plan. The plans can also be constrained with a different cost for each action. Such a plan will be optimal if it minimises the total cost.

The easiest way to find a state-of-the-art planner is to look at the International Planning Competition (IPC) results. All of the planners here use PDDL as input language and represent top state-of-the-art performances. We can also use SATPLAN [START_REF] Mali | On the utility of Plan-space (Causal) Encodings[END_REF][START_REF] Vidal | Recherche dans les graphes de planification, satisfiabilité et stratégies de moindre engagement[END_REF] which is based on the translation from a planning problem to a SAT problem. Many SAT solvers give a solution when there exists one. This solution can then be translated to a solution plan for the planning problem. As SAT solvers are more widely used than planners, they may have better performances. However, SAT is a NP-complete problem when classical planning is a PSPACE-complete problem. To reduce a planning problem to NP, we search for horizon bounded plans. To find an optimal plan we have to search for a plan for different lengths then take the shorter one. The search can be done in different ways. We can search incrementally and stop when the SAT problem has a solution. We can also search by dichotomy. When the SAT problem has a solution, the problem is either longer than the optimal solution or it is an optimal solution. And when the SAT problem has no solution, it is shorter than the optimal solution.

Epistemic planning

Epistemic planning is the form of planning that involves reasoning about the agents' knowledge. Depending on the logic used, knowledge will be modeled either via special fluents, using knowledge based variables, or via the formulas by adding some knowledge operators.

For instance the gossip problem was generalised in (Cooper, Herzig, Maffre, 1 Introduction Maris, and Régnier 2016b;Cooper, Herzig, Maffre, Maris, and Régnier 2016c) to the epistemic gossip problem. In the epistemic gossip problem, we are not only interested in the knowledge of the secrets for each agent but also the knowledge they have of the other agents' knowledge. The goal of an epistemic gossip problem planning task can be shared knowledge of order 3: that all the agents know that all of them know that all of them know every secret. It can also be that a specific agent knows that the other agents know all the secrets.

We use two different formats for the propositional variables in the epistemic gossip problem. We can keep the same variables as in classical planning (ksec i,j ) that means that agent i knows the secret of agent j. Alternatively, we consider than the secrets are booleans and we keep the knowledge out of the propositions. To do this, we use sec j instead, which means that the secret of agent j is true. In such a case, the secret may be, for instance, about the truth of a gossip that everyone heard about agent j.

DEL

This subsection is based on [START_REF] Bolander | A Gentle Introduction to Epistemic Planning: The DEL Approach[END_REF] and (Cooper, Herzig, Maffre, Maris, Perrotin, et al. 2019).

Epistemic planning is the general setting of planning in Dynamic Epistemic Logic DEL [START_REF] Bolander | Epistemic planning for single and multi-agent systems[END_REF][START_REF] Löwe | DEL Planning and Some Tractable Cases[END_REF]. DEL combines standard epistemic logic (the static component) with event models describing actions and their perception by the agents (the dynamic component). As DEL-based planning is undecidable [START_REF] Bolander | Epistemic planning for single and multi-agent systems[END_REF], restrictions of either the static or the dynamic component were explored. Most approaches focused on the latter. It turned out that undecidability is already the case under severe restrictions: basically, DEL planning tasks are only decidable when all actions are public [START_REF] Aucher | Undecidability in epistemic planning[END_REF][START_REF] Bolander | Complexity Results in Epistemic Planning[END_REF][START_REF] Cong | Small Undecidable Problems in Epistemic Planning[END_REF], which is not the case in many real world multiagent applications.

Given a set of propositions p ∈ P, the set of DEL formulas Fml DEL is defined by the following grammar:

ϕ p | ⊥ | ¬ϕ | ϕ 1 ∨ ϕ 2 | K i ϕ | CK iϕ 1.
3 Epistemic planning

State description

To represent the states in a DEL planning task we need a Kripke structure.

A Kripke structure is a triple M(W, R, h) where:

• W is a set of possible words

• R is a set of symmetric binary relations R i , the indistinguishably relation for agent i, on W

• h : P → 2 W is a function that, for each propositional variable, gives the set of worlds where that variable is true This way, we can have a model of all the worlds that are possible for our agents. If an agent i does not have enough knowledge to distinguish a world w 1 from a world w 2 , then there is a relation in R i between these worlds. Then, the epistemic state is the tuple (w 0 , M) where w 0 ∈ W .

Action description

The actions of DEL are described with action models. An action model is a tuple (E, R, pre, eff ) where:

• E is a set of events • R is the set of indistinguishably relations

• pre : E → Fml DEL assigns a precondition to each event

• eff : E → Fml DEL assigns an effect to each event, for all e ∈ E, eff (e) is a conjunction of literals over P For instance, the action model corresponding to the truthful public announcement of p has a single event e, total relations, p as precondition and an empty effect: (e, Agt, p, skip). Another example may be a truthful semiprivate announcement whether p to agent i. Agent i learns whether p and other agents only learn that i learns whether p without learning whether p. This is modeled by an action model with two events, e + and e -. The preconditions are pre(e + ) = p and pre(e -) = ¬p and the effects are undefined. The set of indistinguishably relations is R j = {e + , e -} × {e + , e -} for every j = i and R i = {(e + , e + ), (e -, e -)}. The designated event is e + if we want i to learn that p or e -if we want i to learn that ¬p.

1 Introduction

Other decidable approaches

We overview existing work on decidable epistemic planning in the DEL paradigm. We only present sequential plans: as far as we know parallel plans have not been investigated yet.

The approach of [START_REF] Muise | Planning Over Multi-Agent Epistemic States: A Classical Planning Approach[END_REF]) is based on a lightweight epistemic logic where the scope of the epistemic operator K i is restricted to literals, or literals that are preceded by a sequence of epistemic operators [START_REF] Demolombe | A Simple and Tractable Extension of Situation Calculus to Epistemic Logic[END_REF][START_REF] Steedman | Planning dialog actions[END_REF][START_REF] Lakemeyer | Efficient Reasoning in Multiagent Epistemic Logics[END_REF], and negations [START_REF] Muise | Planning Over Multi-Agent Epistemic States: A Classical Planning Approach[END_REF]; in other words, no conjunctions or disjunctions can occur in the scope of K i . Such restrictions however exclude formulas such as K i (K j p ∨ K j ¬p) expressing that agent i knows that agent j knows whether the propositional variable p is true. This is a major drawback because such formulas are fundamental in communication and more generally in any forms of interaction: a situation where agent i does not know whether or not p is the case (¬K i p∧¬K i ¬p) but knows that j knows (K i (K j p∨K j ¬p)) may lead agent i to ask j about p. Such 'knowing-whether' information also conveniently describes the initial situation of the gossip problem:

i ((K i sec i ∨ K i ¬sec i ) ∧ j =i (¬K i sec j ∧ ¬K i ¬sec j ))
where sec i is the secret of agent i, as well as the goal i,j (K i sec j ∨ K i ¬sec j ). In our EL-O-based approach all these formulas can be expressed. [START_REF] Kominis | Beliefs In Multiagent Planning: From One Agent to Many[END_REF] keep the language of standard epistemic logic (so their language is not restricted to epistemic literals) and restrict the dynamic component. It requires that the initial state is common knowledge and that all action occurrences are either public or semi-public. This makes it impossible to account for many natural everyday situations such as gossiping.

A series of papers by Liu et col. investigates epistemic planning with common knowledge based on the situation calculus paradigm (Q. Liu and Y. Liu 2018;[START_REF] Huang | A General Multi-agent Epistemic Planner Based on Higher-order Belief Change[END_REF]. They represent KD45 knowledge in a particular normal form that generalises Moss's characteristic formulas. Their actions have very general effects, such as a disjunction becoming common knowledge, which requires the integration of belief update and revision operations.

Le et al. study DEL-based planning with common knowledge under compact representations of the initial epistemic state and of event models [START_REF] Le | EFP and PG-EFP: Epistemic Forward Search Planners in Multi-Agent Domains[END_REF]. For the former they use what they call S5-theories (although their epistemic logic is K, not S5); for the latter they use the action language mA, which has statements of the kind "agent i observes action a". This differs from 1.3 Epistemic planning our modelling where agents observe propositional variables, which makes it difficult to compare the two approaches. We can however also model their 'coin in the box' example which they claim no approach can deal with. A limitation of mA is that only literals can be announced. Agents therefore cannot communicate higher-order knowledge, as required in the generalised gossip problem. We note that they mention the issue of interfering actions but do not develop this further because it is not clear how to compute effects under mA.

We here simplify the static component: we replace standard epistemic logic by a lightweight version, Epistemic Logic of Observation (EL-O), which is based on the notion of observability of a propositional variable by an agent. In EL-O it is supposed that agent i knows that p is true when p is true and i observes p. Symmetrically, i knows that p is false when p is false and i observes p. Thus when i observes p then i knows either that p is true or that p is false. The other way round, when i does not observe p then i does not know whether p: both p and ¬p are possible for i. This extends to higher-order observability: i may observe whether j observes p, and so on. (Cooper, Herzig, Maffre, Maris, and Régnier 2016a) showed that EL-O is suitable for sequential epistemic planning.

State description

We recall Epistemic Logic of Observation, abbreviated EL-O. Its language is a fragment of that of the dynamic epistemic logic DEL-PAO [START_REF] Herzig | A Poor Man's Epistemic Logic Based on Propositional Assignment and Higher-order Observation[END_REF] where models were always infinite: we now simulate them by finite models, via a modification of the interpretation. This makes the semantics immediately suitable for model checking, which had required some more work in the original presentation.

The epistemic aspect is captured by observability operators. The set of observability operators is:

OBS = {S i : i ∈ Agt} ∪ {JS},
where S i stands for individual visibility of agent i and JS stands for joint visibility of all agents. The set of all sequences of visibility operators of length at most k is noted OBS ≤k ; and the set of all sequences of visibility operators of length k is noted OBS =k . Then the set of all finite sequences of 1 Introduction visibility operators is OBS * = k≥0 OBS =k and the set of all finite non-empty sequences is OBS + = k≥1 OBS =k . Elements of OBS * are noted σ, σ , etc. The depth of a sequence of operators σ, noted depth(σ), is the number of operators composing it.

Visibility atoms, or atoms for short, are finite sequences of visibility operators followed by a propositional variable. The set of all atoms is:

ATM = {σ p : σ ∈ OBS * , p ∈ P}.
For example, S 1 p reads "1 sees the value of p"; it means that 1 knows whether p is true or false. JS S 2 q reads "all agents jointly see whether agent 2 sees the value of q": there is joint attention in the group of all agents concerning 2's observation of q; agent 2 may or may not see the value of q, and in both cases this is jointly observed. S 1 S 2 S 3 p reads "1 sees whether 2 sees whether 3 sees p". Atoms with an empty sequence of observability operators are nothing but propositional variables.

Principles of introspection play an important role in epistemic logic: when agent i knows that p then i also knows that she knows that p; and when agent i does not know that p then i also knows that she does not know that p. In our visibility-based epistemic logic, introspection can be expressed as S i S i α. Likewise, joint introspection is expressed as JS JS α. The latter implies σJS α for every non-empty σ because joint visibility implies any nesting of individual visibility. We therefore call an atom introspective if it contains two consecutive S i , or a JS that is preceded by a non-empty sequence of observability operators. In other words, an atom is introspective if it is of the form σ S i S i α for some σ ∈ OBS * , or of the form σ JS α for some σ ∈ OBS + . The set of all introspective atoms is

I -Atm = {σ S i S i α : σ ∈ OBS * and α ∈ ATM } ∪ {σ JS α : σ ∈ OBS + and α ∈ ATM }.
The complement of I -Atm is the set of relevant atoms: R-Atm = ATM \I -Atm.

Action description

The actions descriptions of an EL-O planning task is made in the same way as for classical planning. The fluents are EL-O atoms, without JS operators, 1.3 Epistemic planning instead of propositions. One of the contributions of chapter 4 is the ability to use JS in EL-O planning tasks.

We will usually use actions with conditional effects. The precondition pre(a) of the action a is an EL-O formula, as are the conditions cnd(ce) of a conditional effect ce ∈ eff (a). The effects of ce, eff + (ce) and eff -(ce) are sets of EL-O atoms.

The second example of section 1.3.1.2 is modeled in EL-O with an action with p as a precondition and an unconditional effect with S i p and S j S i p for every j = i.

Goal and precondition description

The language of EL-O is defined by the same grammar as defined above with visiblity atoms (noted α, α , β, . . .) as fluents:

ϕ ::= α | ⊥ | ¬ϕ | (ϕ 1 ∧ ϕ 2 ) The set of EL-O formulas is noted Fml EL-O . The set of relevant formulas is R-Fml EL-O = {ϕ ∈ Fml EL-O : ATM (ϕ) ⊆ R-Atm}. The set ATM (ϕ)
is the set of atoms occurring in ϕ. It is defined inductively by:

ATM (α) = {α} ATM (¬ϕ) = ATM (ϕ) ATM (ϕ ∧ ϕ ) = ATM (ϕ) ∪ ATM (ϕ )
For example, ATM (JS q∧S 2 p) = {JS q, S 2 p} and ATM (S 1 JS p) = {S 1 JS p}. Note that neither p nor JS p are atoms of S 1 JS p.

As for the formulas, the whole definition of planning tasks and actions are like in classical planning. We only need to use atoms as fluents instead of propositional variables.

The epistemic gossip problem

In the case of the gossip problem, the set of propositional variables P = {ksec i,j | i, j ∈ Agt} where ksec i,j reads "i knows j's secret". So S k ksec i,j means that agent k sees if i knows j's secret. The goal is to achieve some knowledge over those secrets. For any planning task, the goal is a formula 1 Introduction over the atoms of the problem (Goal), we say that max({depth(α) : α ∈ ATM (Goal)}) is the depth d of the problem.

The actions in the gossip problem are calls between two agents leading to an update of the two agents' knowledge. In one-way calls, after a call from agent i to agent j, agent j sees everything that agent i knew before the call and they jointly see that. As there is no need for atoms of depth over d2 , we can simplify the jointly seeing by saying that they both see that they see that they see these atoms, and so up to the depth d;

Formally, for the epistemic gossip problem of depth 2, the execution of an action Call i,j is modeled by the function:

τ Call i,j (s) = s ∪ {S j α, S j S i α, S i S j α, . . . : α ∈ ATM and S i α ∈ s} 1.3.2.

Solution description

Like in classical planning to describe both the planning task and the validity of a solution for this task in a formal logic, we need a dynamic logic. For this we use DEL-PAO which has the same dynamic aspect as DL-PA and the same atoms as EL-O. This implies the same restrictions as both logics, mainly that it cannot represent parallel plans. However, DEL-PAO satisfiability checking complexity is the same as DL-PA. This way, we have epistemic planning problems with the same complexity as classical planning problems.

Tools to find a solution

Unlike classical planning, there is no standardised way of writing an epistemic planning task for a solver. That's why there are different approaches for epistemic planners. [START_REF] Le | EFP and PG-EFP: Epistemic Forward Search Planners in Multi-Agent Domains[END_REF]) describes an epistemic forward search planner called Efp to search for solutions for problems such as their 'coin in the box' example. They are also approaches to use STRIPS or classical planning, with external functions to handle the planning task and the epistemic reasoning separately [START_REF] Hu | What you get is what you see: Decomposing Epistemic Planning using Functional STRIPS[END_REF], or simply by translating the problem into classical planning (Cooper, Herzig, Maffre, Maris, and Régnier 2016b).

Temporal planning

As in classical planning, there are SAT-based approaches for epistemic planning. [START_REF] Lagniez | A SAT-Based Approach For PSPACE Modal Logics[END_REF]) presents some experimental results comparing state of the art solvers for modal logics with the MoSaiC solver using a RECAR approach.

Temporal planning

In classical planning actions have no explicit duration. We can usually consider that the actions have no duration and are instantaneous. This assumption may not work for all problems. For instance, in the gossip problem all the calls are instantaneous but we may have to give them a duration. Calls with a duration allows problems with agents that takes longer to exchange the informations. Or we could add restrictions on when the agents can call each other.

Temporal planning is an extension of classical planning with actions with durations. It allows one to model such problems.

State description

If there is a duration for each action, there has to be a link between the states and time. There are two different approaches to reason about the time. Either with a logic of instants [START_REF] Mcdermott | A Temporal Logic for Reasoning About Processes and Plans[END_REF] or with a logic of intervals [START_REF] Allen | Towards a General Theory of Action and Time[END_REF]. Then, the states are bounded either with the instants or with the end-points of the intervals.

Action description

An extension of PDDL, PDDL 2.1 [START_REF] Fox | PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains[END_REF] proposes actions with a duration. With this extension, actions can have effects either at the beginning or at the end of the action and preconditions are split in three parts. The preconditions can be needed at the beginning, the end or over the entire duration of the action. This is shown in Figure 1. 1. This means that during the execution of an action, multiple state transitions may occur. The top line represents the preconditions, the middle one the action a and the bottom one the effects. The horizontal axis represents the time. The letters are s for "at-start", e for "at-end" and o for "over-all" (over the entire duration).

Solution description

As in classical planning, a temporal planning task may have a sequential solution. However, there are some temporal planning tasks which have only parallel solutions. For instance to hammer a nail, one has to hold the nail on the wall while hammering it. If both actions are not executed concurrently, the nail will fall on the ground. Those planning tasks are called temporally expressive [START_REF] Cushing | When is Temporal Planning Really Temporal?[END_REF].

While asking for a sequential or a parallel solution does not change the complexity in classical planning, the distinction between temporally expressive and temporally simple planning tasks involves a difference of complexity. A temporally simple planning task can be linearly reduced to a classical planning task. However the problem of the existence of a solution for a temporally expressive planning is EXPSPACE-complete [START_REF] Rintanen | Complexity of Concurrent Temporal Planning[END_REF]).

Tools to find a solution

As for classical planners that use the standard language PDDL, temporal planners have been developed for the language PDDL 2.1 involving temporal aspects. Most of these temporal planners are usually working separately for planning and scheduling. While the selection of actions in a solution plan can be done by a planning module, scheduling such actions can be done in parallel via a TMM (Time Map Manager) to handle temporal constraints [START_REF] Dean | Temporal Data Base Management[END_REF]. These temporal constraints can be modeled for example as a STP (Simple Temporal Problem) [START_REF] Dechter | Temporal Constraint Networks[END_REF] or as a DTP (Disjunctive Temporal problem) (Stergiou and Koubarakis 1.5 Aim and contribution of the thesis 2000). We do not detail such techniques here as it would add a lot of details not relevant for this thesis.

In the same way as SAT-based approaches for classical or epistemic planning, SAT modulo theory (SMT) can be used to find a solution for temporal planning. This approach was studied in several works [START_REF] Maris | TLP-GP: New Results on Temporally-Expressive Planning Benchmarks[END_REF]Rintanen 2015;[START_REF] Shin | Processes and continuous change in a SAT-based planner[END_REF].

Aim and contribution of the thesis

The aim of this thesis was to make tools to help planning for real life problems. I here oppose real life problems to toy problems which have a philosophical interest but may never be found in real life. I focussed on bringing together three different aspects commonly found in real life problems: multi-agent, temporally extended actions and reasoning about the knowledge of the agents.

Multi-agent temporal and epistemic planning problems can be useful in many ways. We can use them for helping people decide how to accomplish a task, for instance to optimise the production lines in a factory. They can also be used in video games for the AI of non playable characters or to dynamically generate a story. Or for smarter robots, to find which actions they have to do and when they have to do them.

As we want to help planning for real life problems, we want to have tools that can find a solution in a reasonable amount of time. As both temporal and epistemic planning is at least as difficult as classical planning we choose their PSPACE-complete complexity as a lower bound. Within this complexity problems with a low number of actions and steps can be solved but bigger problems may need a huge amount of time that might not be practical. Therefore we wanted to have all planning problems in PSPACE.

As this was already a lot of work, we choose to consider only deterministic problems. This implies that the multi-agents aspect is present in the problem description and execution but not in the search of the solution. We think of the solving being done centrally. This implies that this location can communicate the relevant part of the plan to each agent before its execution. This works well for problems with cooperation between the agents. For problems with competition between the agents, the winner of the competition is chosen when the problem is modeled.

1 Introduction

Outline of the thesis

In Chapter 2, I present the temporal epistemic gossip problems (TEGP for short). They are a generalisation of the epistemic gossip problem with temporal constraints on the calls. We added a duration for all call actions and constraints on the times allowed for a call between two agents. This chapter shows that TEGP are NP-complete problems even with negative goals. An example of negative goal is that we do not want agent i to know the secret of agent j. These problems show the interest of adding a temporal aspect to epistemic problems to make them more realistic. When we want to communicate with other people, we may not be able to call them whenever we want and the shortest plan may not be the fastest when those constraints are taken into account.

We then wanted to add more flexibility to the temporal constraints. This led to the two following chapters. Chapter 3 shows an extension to DL-PA to add parallelism in the logic. This chapter shows that DL-PPA maintains the PSPACE-complete complexity of DL-PA. This result is then used for bounded horizon classical planning task. Two programs that are equivalent to the problem of the existence of a plan of k steps or less are described.

Another approach to parallel epistemic planning is described in chapter 4. This time we use EL-O actions so we have epistemic actions instead of the classical actions of the previous chapter. We show that EL-O actions can be translated to parallel classical planning. With this translation we can show that EL-O parallel planning is PSPACE-complete. We also use the translation to classical planning to translate some epistemic problems to PDDL. With this last translation we tested some of these problems with some IPC planners and compared the time to get a plan.

Temporal Epistemic Gossip Problem

Here, we enrich the epistemic gossip problem by allowing to limit any communication to a set of instants (such as an interval during which the two agents involved in the call are both available). For an example, one can think of satellites on different orbits which can only communicate when they 'see' each other. In a more down-to-earth example, the interval during which a mobile communication is available is often limited by the charge capacity of the battery. Another variant we study is when certain calls must occur at given instants (for example for maintenance or security reasons).

We show that the temporal epistemic gossip problem is in NP even for a complex goal given in the form of a CNF and in the presence of constraints on the instants when calls can or must take place. This positive result, when compared to classical planning follows from the reasonable assumption that knowledge is never destroyed. Moreover, we show that in the absence of temporal constraints and negative goals, temporal epistemic gossiping is in P. We then show maximality of this tractable subproblem in the sense that the problem becomes NP-complete in the following cases: in the presence of temporal constraints (even as weak as a simple upper bound on the execution time of a plan) and in the presence of negative goals (such as agent i should not learn the secret of agent j).

The content of this chapter corresponds to an article published at the European Conference on Multi-Agent Systems (EUMAS 2018) (Cooper, Herzig, Maris, and Vianey 2018).

Content of the chapter

Résumé du chapitre en français

Ici, nous enrichissons le problème du bavardage épistémique en autorisant de limiter toute communication à un ensemble d'instants (comme un intervalle pendant lequel les deux agents impliqués dans la communication sont tous deux disponibles). Par exemple, on peut penser à des satellites sur des orbites différentes qui ne peuvent communiquer que lorsqu'ils se "voient" mutuellement. Dans un exemple plus terre à terre l'intervalle de temps pendant lequel une communication mobile est disponible est souvent limité par la capacité de charge de la batterie. Une autre variante que nous étudions est celle où certains appels doivent avoir lieu à des instants donnés (par exemple, pour des raisons de maintenance ou de sécurité).

Nous montrons que les problèmes de bavardage épistémique temporel (TEGP) est en NP même pour un but complexe donné sous la forme d'une CNF et avec des contraintes sur les instants où les communications peuvent ou doivent avoir lieu. Ce résultat positif, par rapport à la planification classique découle de l'hypothèse raisonnable que la connaissance n'est jamais détruite. De plus, nous montrons qu'en l'absence de contraintes temporelles et de buts négatifs, le bavardage épistémique temporel est dans P. Nous montrons ensuite que le problème devient NP-complet dans les cas suivants : en présence de contraintes temporelles (même aussi faibles qu'une simple borne supérieure sur le temps d'exécution d'un plan) et en présence de buts négatifs (comme l'agent i ne doit pas apprendre le secret de l'agent i).

Pour prouver l'appartenance à NP, nous cherchons la longueur d'un plan sans boucle pour un problème ayant une solution, dans le pire des cas. Dans ce cas, pour qu'un agent apprenne la valeur d'un atome il faut que cette information transite par tous les agents. Si l'on a n agents, il faut donc n -1 appels. Pour avoir une connaissance de profondeur d d'une proposition, il faut répéter cette opération d fois. Et si la CNF contient m clauses, pour qu'elles soient toutes vraies il faut répéter cela m fois. On a donc un plan solution de longueur polynomiale par rapport à la taille du problème dès lors qu'il existe une solution. Ceci est suffisant pour dire que les TEGP appartiennent à NP.

Le sous problème n'utilisant ni contraintes temporelles ni fluents négatifs est équivalent au problème du bavardage épistémique. Ce problème est prouvé comme étant dans P. Pour les autres sous problèmes, nous en avons choisis quelques uns pour chercher une meilleure borne inférieure à la complexité des TEGP.

En effet, le simple ajout de contraintes temporelles simples (ici on n'ajoute qu'une limite aux appels, après un certain temps tous les appels sont interdits) suffit pour avoir une borne inférieure NP-difficile. On peut facilement construire un graphe de communications traduisant un problème SAT dès lors que le nombre d'appels est limité. Pour le cas où l'on autoriserait les appels en parallèle, il suffit d'utiliser les contraintes temporelles pour forcer des appels séquentiels.

Un autre apport des TEGP par rapport au problème du bavardage épistémique est l'ajout de buts négatif (qu'un agent ne connaisse pas un secret par exemple). Même en l'absence de contraintes temporelles, cet ajout impose une borne inférieure de complexité NP-difficile. Avec ces résultats, nous prouvons que les TEGP sont NP-complets.

Definitions

The set of all atoms of depth at most d is noted ATM . Observe that if the depth of atom α ∈ ATM is strictly less than d then S i α also belongs to ATM .

An instance of the depth-d temporal epistemic gossip problem (TEGP) is given by a tuple Π = (s 0 , Goal, Agt, I p , I n ):

s 0 ⊆ ATM such that s 0 contains every ksec i,i , for i ∈ Agt Goal ∈ Fml is a conjunction of clauses I p ⊆ N × (N ∪ {∞}) × Agt × Agt I n ⊆ N × Agt × Agt
where s 0 is the initial state; Goal is the goal we want to achieve in the form of a CNF formula (that we identify with a set of clauses); I p is the set of intervals during which two agents can call each other and I n is the set of instants when two agents must call each other. All the number used in this chapter are encoded in binary.

The set I n of necessary calls may correspond to calls that have been programmed in the network for some other purpose. We suppose that I n is included in I p , in the sense that for every (t, i, j) ∈ I n there is a (t 1 , t 2 , i, j) ∈ I p such that t 1 ≤ t ≤ t 2 . In this thesis we always consider the initial state s 0 = {ksec i,i | i ∈ Agt} in which all agents know their own secrets.

A set of calls A between agents induces a partial function between states, i.e. from 2 ATM to 2 ATM . For a state s ∈ 2 ATM :

τ A (s) =                      undef if ∃a ∈ A : s pre(a), or ∃a 1 , a 2 ∈ A : a 1 = Call i 1 ,j 1 and a 2 = Call i 2 ,j 2 with {i 1 , j 1 } ∩ {i 2 , j 2 } = ∅ s ∪ a∈A, ce∈eff (a), and s|=cnd(ce) eff + (ce) otherwise A plan is a relation P ⊆ N × Agt × Agt.
Given a plan P and a natural number t, the set of calls happening at instant t is P (t) = {(i, j) : (t, i, j) ∈ P }. We use |P | to denote the number of distinct instants t for which P (t) = ∅. We use T P (k) to denote the k-th instant (in strictly increasing order of time) at which a call happens in P : i.e. T P (1) < . . . < T P (|P |) and ∀t, P (t) = ∅ ⇔ ∃k ∈ {1, . . . , |P |}, T (k) = t. Our modelling of time by the natural numbers implicitly imposes a fixed duration of one time unit for each call.

Given a TEGP Π = (s 0 , Goal, Agt, I p , I n ), a plan P satisfies the temporal constraints of Π if and only if all the necessary calls are in P and every call in P is possible; formally: I n ⊆ P and for every (t, i, j) ∈ P there is a (t 1 , t 2 , i, j) ∈ I p such that t 1 ≤ t ≤ t 2 . Moreover, P solves the TEGP if and only if it satisfies the temporal constraints and there is a sequence of states

(s 0 , • • • , s |P | ) such that • s 0 = Init • s |P | |= Goal • s k+1 = P (T P (k + 1))(s k ) for every k with 0 ≤ k < |P |
where P (T p (k+1)) is the set of actions at instant T p (k+1) and P (T p (k+1))(s k ) is the result of executing these actions in state s k . By the definition above of A(s), the set of actions P (T p (k + 1)) at instant T p (k + 1) cannot contain two calls involving the same agent. In the sequential version of the TEGP, a solution plan P must also satisfy ∀t, card(P (t)) ≤ 1.

A TEGP defines in a natural way a call digraph G in which the vertices are the agents and the directed edges the possible calls. In the two-way version, G is a graph. a, b, c, d ande) where each server can only communicate with a subset of the others. Note that all calls are assumed to be one-way in this example. As part of the maintenance program, a, b, c and d send a backup of their data to e every night and these backups can be sent to any server during the day (between 8:00 and 18:00). The others servers can communicate with each other at any moment if there is a communication link between them. The communication graph is depicted in Figure 2.1.

Example 1. Consider a network of five servers (which we call

On the same network, another question that we can ask is whether c can know a's data without a being aware of this. In this case, the goal is ksec c,a ∧ ¬S a ksec c,a . The answer is 'yes' since the following plan establishes the goal: the necessary Call a,e at instant 2, followed by Call e,c at an instant t ∈ [8, 18] (together with the other necessary calls Call b,e at instant 4, Call c,e at instant 20 and Call d,e at instant 22). double-ended arrow represents two directed edges (i.e., the possibility of one-way calls in both directions). The tuples on the arcs represents the subsets of I p and I n for the calls from agent i (at the beginning of the arc) to j (at the end of the arc). If there is no arc from i to j, then no call is possible from i to j. The number of calls needed for a disjunction of formulas to be true is at most the maximum of the number of calls needed for each formula. In a CNF, there are only disjunctions over atoms, so the number of calls needed for a disjunction is d(n -1).

2 Temporal Epistemic Gossip Problem a b ({(0, ∞)}, ∅) c ({(0, ∞)}, ∅) d ({(0, ∞)}, ∅) ({(0, ∞)}, ∅) e ({(2, 2)}, {2}) ({(8, 18)}, ∅) ({(4, 4)}, {4}) ({(8, 18)}, ∅) ({(20, 20)}, {20}) ({(8, 18)}, ∅) ({(22, 22)}, {22}) ({(8, 18)}, ∅)
The number of calls needed for a conjunction of formulas is the sum of the number of calls needed for every formula, which here is at most d(n -1). So, with m being the number of conjunctions in the CNF of the goal, at most md(n -1) calls are needed for a problem with only possible calls. Thus, if a solution plan P exists, then P contains a subset Q of at most md(n -1) calls which are sufficient to establish all positive atoms in the goal.

For a problem with necessary calls, it can happen that the plan Q does not contain all the necessary calls I n . However, as P is a solution plan, it must contain every necessary calls. Thus, there exists a subset of P , Q that is also a solution plan with at most md(n -1) + |I n | calls.

A subproblem of the temporal gossip problem in P

We say that a TEGP instance is positive if its goal is a CNF containing only positive atoms. A special case of TEGP is the class of positive non temporally constrained epistemic gossip problems Π = (s 0 , Goal, Agt, I p , I n ) where I p = {(0, ∞, i, j) : (i, j) ∈ E}, for some E, and Goal is a positive CNF. In this case, E is the set of edges in the call digraph: if a call is possible (as specified by E), it is possible at any instant. On the other hand, there is no restriction on the set of necessary calls I n .

Proposition 2. The class of positive non temporally constrained epistemic gossip problems can be solved in polynomial time.

Proof. There is a simple polynomial-time algorithm for positive non temporally constrained epistemic gossip problems: make all possible calls in some fixed order and repeat this operation md(n -1) + |I n | times. Call this sequential plan Q. By the proof of Proposition 1, if a solution plan exists, there is a sequential solution plan P of length at most md(n -1) + |I n |. The actions of P necessarily appear as a subsequence of Q. Since the goal and preconditions of actions contain only positive atoms, the extra actions of Q cannot destroy any goals or preconditions. It follows that if a solution plan exists, then Q is also a solution plan. Thus this simple algorithm solves the class of positive non temporally constrained epistemic gossip problems in polynomial time.

Given an arbitrary instance of TEGP, we can construct a positive non temporally constrained instance by ignoring negative goals and temporal constraints (specified by I p ). This is a polynomial-time solvable relaxation of the original TEGP instance. This provides a relaxation which is inspired by the well-known delete-free relaxation of classical planning problems and is orthogonal to the relaxation of temporal planning problems based on establisher-uniqueness and monotonic fluents [START_REF] Cooper | Monotone Temporal Planning: Tractability, Extensions and Applications[END_REF]. Consider that this relaxation of an instance of TEGP has no solution, then the instance of TEGP does not have a solution. This can be used to find TEGP's instances without solution in polynomial-time.

NP-completeness when execution time is bounded

The simplest temporal constraint is just a time limit on the execution of a plan. In the case of sequential plans this simply corresponds to placing a bound on plan length (which is equal to the number of calls) whereas in the parallel case execution time corresponds to the number of steps. We show in this section that this single constraint (a time limit on plan execution) is sufficient to render the epistemic gossip problem NP-complete. It is worth noting that the PSPACE complexity of classical planning is not affected by the possibility of placing an arbitrary limit on plan length, but the special case of delete-free planning passes from P to NP-hard when a bound is placed on plan length [START_REF] Bylander | The Computational Complexity of Propositional STRIPS Planning[END_REF]. We show that this remains true for the specific case of gossiping problems.

NP-completeness when execution time is bounded

We begin by studying the sequential case of TEGP.

Proposition 3. The epistemic gossip problem with no temporal constraints but with a bound on the number of calls is NP-complete, even when the goal is a conjunction of positive atoms.

Proof. We will exhibit a polynomial-time reduction from the well-known NPcomplete problem SAT to the version of the epistemic gossip problem whose question is whether there is a sequential solution plan of length at most L. To do so, for a given set of clauses {C 1 , . . . , C m } we need the following agents:

• an agent S (the source),

• literal agents, i.e., agents for every variable and every negation of a variable (which we name, respectively, x + and x -) for each variable x of the SAT instance,

• clause agents, i.e., agents for every clause (which we name C i for the ith clause of the SAT instance).

Before performing this construction, we first add a dummy clause (x ∨ ¬x) for each SAT variable x. This clearly does not change the semantics of the instance but it does force us to specify the truth value of each variable in a solution of the SAT instance.

The source agent S and clause agents can only communicate with literal agents. The source agent S can communicate with every literal agent. A literal agent can only communicate with S and those clauses it is a member of. The graph G of communications is shown in Figure 2.2 for a particular SAT instance. In this example, C 1 = (¬x ∨ y ∨ z), C 2 = (¬y ∨ z) and the clauses C 3 , C 4 , C 5 are the dummy clauses (x ∨ ¬x), (y ∨ ¬y), (z ∨ ¬z).

A variable x is considered to be true (false) if S's secret passes through x + (respectively, x -) in the solution plan on its way to the agent representing the dummy clause (x ∨ ¬x). The bound on the number of actions will prevent the possibility of S's secret passing through both x + and x -. So the choice of whether S's secret passes through x + or x -determines an assignment to the variable x in the SAT problem.

The goal of this instance of TEGP is that every clause agent knows the secret of S (Goal = C i ksec C i ,S ). Now set the bound on plan length to be L = 2n + m, where n is the number of variables in the SAT instance and m

2 Temporal Epistemic Gossip Problem C 1 C 2 C 3 C 4 C 5 x + x - y + y - z + z - S Figure 2
.2: Representation of the formula (¬x ∨ y ∨ z) ∧ (¬y ∨ z) as a temporal epistemic gossip problem in which the question is whether there is a plan using no more than 8 calls.

the number of clauses in the original instance. With the new dummy clauses, the total number of clauses is n + m.

In a solution plan P we require at least n calls, one to either x + or x -, for the n SAT variables x, in order for S's secret to be able to reach the agent corresponding to the dummy clause x ∨ ¬x. P must also contain at least n + m calls to the clause agents C i (including the dummy clauses) to establish the goals ksec C i ,S . A solution plan of length precisely 2n + m corresponds to a solution of the corresponding SAT instance since such a plan defines a unique assignment to all variables that satisfies all clauses. For example, the solution x = f alse, y = f alse, z = true to the SAT instance of Figure 2.2 corresponds to the following solution plan of length 8: S calls x -; S calls y -; S calls z + ; x -calls C 1 ; z + calls C 2 ; x -calls C 3 ; y -calls C 4 ; z + calls C 5 . This reduction from SAT is clearly polynomial.

Proposition 1 proves the existence of a polynomial-length certificate for positive instances of the decision version of TEGP. Such certificates (solutions) can be verified in polynomial time. Thus TEGP ∈ NP. Since the epistemic gossip problem with no temporal constraints but with a bound on the number of calls is clearly still in NP, this completes the proof of NP-completeness.

The proof of Proposition 3 was given for the case of two-way communications. It is trivial to adapt it to the case of one-way communications (for example, by only allowing calls from S to literal agents and from literal agents to clause 2.4 NP-completeness when execution time is bounded agents). One can note that any two-way temporal epistemic gossip problem can be polynomially translated to a problem with one-way calls. A two-way call between agents i and j is translated to two one-way calls, one from i to j and one from j to i.

We now consider the parallel version of the TEGP. Recall that in the parallel version of the TEGP, several calls may take place at each step, provided no agent is concerned by more than one call at each step.

Proposition 4. The parallel version of the epistemic gossip problem with no temporal constraints except for a bound on the number of steps is NP-complete even when the goal is a conjunction of positive atoms.

Proof. By the same argument as in the proof of Proposition 1, the problem is in NP. We complete the proof by exhibiting a polynomial reduction from 3SAT which is well known to be NP-complete. Given an instance I 3SAT of 3SAT, by introducing sufficiently many new variables x which are copies of old variables x (together with the clauses x ∨ ¬x , ¬x ∨ x to impose equality of x and x ) we can transform I 3SAT into an equivalent instance in which each literal does not occur in more than three clauses. This is a polynomial reduction since we need to introduce at most one copy of each variable x per clause in which it occurs in I 3SAT . Therefore, from now on, we suppose that each literal occurs in at most two clauses in I 3SAT .

We construct an instance I of the epistemic gossip problem which has a parallel solution plan of length 2p if and only if I 3SAT is satisfiable. We choose the value of p to be strictly greater than n + 3, where n is the number of variables in I 3SAT . To be concrete, we can choose p = n + 4. We add to I 3SAT p -n new dummy variables x n+1 , . . . , x p none of which occur in the clauses of I 3SAT . In I there is an agent S (the source), literal agents x + i , x - i for each variable x i (i = 1, . . . , p), and a clause agent C j for each of the clauses C j (j = 1, . . . , m) of I 3SAT . For each variable x i (i = 1, . . . , p), we also add a dummy-clause agent D i which we can consider as representing the dummy clause x i ∨ ¬x i . Instead of linking these basic agents directly, we place paths of new agents between these basic agents. Between agent S and agent x + i we add a path of length p + 1 -i. Similarly, we add a new path of the same length between S and agent x - i . For i = 1, . . . , p, we add two new paths both of length p between the literal agents x + i and x - i and the dummy-clause agent D i . For each clause C j of I 3SAT , we also add three new paths of length q from the agents corresponding to the literals of C j to the agent C j , where 33

2 Temporal Epistemic Gossip Problem C 1 C 2 D 1 D 2 D 3 D 4 D 5 D 6 D 7 x + 1 7 x - 1 4 7 x + 2 4 7
x - In order to establish the goal ksec D i ,S , the secret of S has to follow a path from S to D i . The shortest paths from S to D 1 are of length 2p and pass through either x + 1 or x - 1 . Recall that our aim is to find a plan whose execution requires at most 2p steps. Thus, to establish ksec D 1 ,S in 2p steps, during the first step, S must call the first agent on the path to x + 1 or the first agent on the path to x - 1 . The shortest path from S to D 2 is of length 2p -1, so during the second step, S must call the first agent either on the path to x + 2 or the first agent on the path to x - 2 . By a simple inductive argument, we can see that during step i (i = 1, . . . , p), S must call the first agent on the path to x + i or x - i . We can consider that the choice of whether S's secret passes through x + i or x - i determines an assignment to the variables x i . Due to the diminishing lengths of these paths as i increases, S's secret arrives simultaneously at the literal agents, either x + i or x - i , for i = 1, . . . , p. Another p steps are then required to send in parallel this secret to the dummy-clause agents D j , for a total number of steps of 2p. Almost simultaneously (within two time units), S' secret arrives at the clause agents C j , provided it has passed through one of the agents corresponding to the literals of C j . The length of paths from literal agents (x + i or x - i ) to clause agents C j is q = p -3 which is slightly less than p to allow for the fact that a literal agent, say x + i , may have to send S's secret along at most four paths: first towards D i , then towards the (at most) three clauses in which x i occurs.

It is important to note that S is necessarily occupied during the first p steps, as described above, so if S were to try to send its secret both to x + i and x - i for some i ≤ n the secret could not arrive via the second of these paths at a clause agent C j in less than 2p + 1 -n + q = 3p -n -2 steps which is greater than the upper bound of 2p steps (since p = n + 4). By our construction, the goal ksec C j ,S is established only if the assignment to the variables x i determined by the solution plan satisfies the clause C j . Hence, parallel solution plans of length 2p steps correspond precisely to solutions of I 3SAT . We have therefore demonstrated a polynomial reduction from 3SAT to the parallel version of the epistemic gossip problem with a bound on the number of steps.

The following corollary follows from the fact that we can place an upper bound L on the number of steps in a plan by simply imposing via I p an interval of possible instants [1, L] for all calls.

Corollary 5. TEGP is NP-complete.

NP-completeness of gossiping with negative goals

We show in this section that even without temporal constraints or a bound on plan length, when we allow negative goals the problem of deciding the existence of a solution plan is NP-complete. Proposition 6. The epistemic gossip problem with possibly negative goals is NP-complete even in the absence of any temporal constraints or bound on plan length.

Proof. The same argument as in the proof of Proposition 1 shows that the problem belongs to NP since it is a subproblem of TEGP.

To complete the proof, it suffices to give a polynomial reduction from SAT. Let I SAT be an instance of SAT. We will construct a call graph G and a set of goals such that the corresponding instance I Gossip of the epistemic gossip problem is equivalent to I SAT . Recall that the nodes of the call graph G are the agents and the edges of G the communication links between agents.

For each propositional variable x in I SAT , we add four nodes x + , x -, b x , d x to G joined by the edges shown in Figure 2.4(b). There is a source node S in G and edges (S, x + ), (S, x -) for each variable x in I SAT . For each clause C j in I SAT , we add a node C j joined to the nodes corresponding to the literals of C j . This is illustrated in Figure 2.4(a) for the clause C j = ¬x ∨ y ∨ z. The solution plan to I Gossip will make S's secret transit through x + (on its way from S to some clause node C j ) if and only if x = true in the corresponding solution to I SAT .

For each clause C j in I SAT , G contains a clause gadget as illustrated in Figure 2.4(a) for the clause ¬x ∨ y ∨ z. We also add ksec C j ,S to the set of 2.5 NP-completeness of gossiping with negative goals goals. Clearly, S's secret must transit through one of the nodes corresponding to the literals of C j (x -, y + or z + in the example of Figure 2.4) to achieve the goal ksec C j ,S .

C j d x x - y + z + x + x - b x S (a) (b)
To complete the reduction, it only remains to impose the constraint that a's secret transits through at most one of the nodes x + , x -, for each variable x of I SAT . This is achieved by the negation gadget shown in Figure 2.4(b) for each variable x. We add the goals ksec dx,bx and ¬ksec dx,S for each variable x, and the goal ¬ksec C j ,bx for each variable x and each clause C j (containing the literal x or ¬x). The goal ksec dx,bx ensures that b x 's secret transits through x or ¬x. Now, recall that we assume that during a call, agents communicate all their knowledge. Suppose that b x 's secret transits through x + : then S's secret cannot transit through x + before b x 's secret (because of the negative goal ¬ksec dx,S ) and cannot transit through x + after b x 's secret (because of the negative goal ¬ksec C j ,bx ). By a similar argument, if b x 's secret transits through x -, then S's secret cannot transit through x + . Thus, this gadget imposes that S's secret transits through exactly one of the nodes x + , x -.

We have shown that I SAT has a solution if and only if I Gossip has a solution. Since the reduction is clearly polynomial, this completes the proof.

The NP-completeness shown in the proof of Proposition 6 holds for both the sequential and parallel versions of the gossip problem.

2 Temporal Epistemic Gossip Problem

Discussion and conclusion

We have defined temporal epistemic gossip problems and have investigated their complexity. Our results are in line with previous results concerning epistemic planning: it is possible to add an epistemic dimension to planning, thus increasing expressibility, without increasing complexity (Cooper, Herzig, Maffre, Maris, and Régnier 2016a).

In our approach agents are not introspective: ksec i,j does not imply S i ksec i,j , and S k ksec i,j does not imply S k S k ksec i,j . This only concerns positive introspection: negative introspection cannot be expressed. Positive introspection can however be enforced by adding axioms ksec i,j → S i ksec i,j , and S k ksec i,j → S k S k ksec i,j . We however did not do so in order to simplify presentation.

We have assumed a centralized approach in which a centralized planner decides the actions of all agents. Several other researchers have recently studied distributed versions of the classical gossip problem where the agents have to decide themselves whom to call, based on the knowledge (and ignorance) they have [START_REF] Apt | Epistemic Protocols for Distributed Gossiping[END_REF]Apt, Grossi, and Hoek 2018;[START_REF] Apt | On the Computational Complexity of Gossip Protocols[END_REF]Apt and Wojtczak 2017b;Apt and Wojtczak 2017a;[START_REF] Van Ditmarsch | Epistemic protocols for dynamic gossip[END_REF][START_REF] Van Ditmarsch | Parameters for Epistemic Gossip Problems[END_REF]). An interesting avenue of future research would be to consider the epistemic gossip problem in this framework.

Several other variants of our centralized model could also be investigated, including the precondition that i has to know the telephone number of j in order to call j and telephone numbers are communicated in the same way as secrets. In another variant, the secrets can be passwords which are no longer constants since each agent i can change their own password (Cooper, Herzig, Maffre, Maris, and Régnier 2016c).

Dynamic Logic of Parallel Propositional Assignments

In chapter 1 we presented some semantics of parallel actions in PDL. We here take a different route and build on a simple version of dynamic logic where atomic programs are assignments of formulas to propositional variables. Dynamic Logic of Propositional Assignments DL-PA has numerous applications in knowledge representation [START_REF] Herzig | Belief Change Operations: A Short History of Nearly Everything, Told in Dynamic Logic of Propositional Assignments[END_REF] in particular classical planning [START_REF] Herzig | On the revision of planning tasks[END_REF], and is considerably simpler than PDL. In particular, complexity is much lower: satisfiability checking is in PSPACE. We add an operator of parallel composition to DL-PA, as well as an operator of inclusive nondeterministic composition (as opposed to PDL's exclusive nondeterministic composition).

The chapter is organised as follows. We extend DL-PA to DL-PPA in Section 3.1 and show in Section 3.2 that complexity stays in PSPACE. In Section 3.3 we show how sequential and parallel planning as well as their bounded versions can be polynomially translated to DL-PPA. Section 3.4 concludes.

The content of this chapter corresponds to an article published at the International Joint Conference on Artificial Intelligence (IJCAI 2019) [START_REF] Herzig | Dynamic logic of parallel propositional assignments and its applications to planning[END_REF].

Content of the chapter

Résumé du chapitre en français

Dans le chapitre 1, nous avons présenté une sémantique des actions parallèles en PDL. Nous prenons ici un chemin différent et nous nous basons sur une version simple de la logique dynamique où les programmes atomiques sont des affectations de formules à des variables propositionnelles. La logique dynamique d'affectations propositionnelles DL-PA a de nombreuses applications dans la représentation des connaissances [START_REF] Herzig | Belief Change Operations: A Short History of Nearly Everything, Told in Dynamic Logic of Propositional Assignments[END_REF]) en particulier la planification classique [START_REF] Herzig | On the revision of planning tasks[END_REF], et est considérablement plus simple que PDL. En particulier, la complexité est beaucoup plus faible : la vérification de la satisfiabilité est dans PSPACE. Nous ajoutons un opérateur de composition parallèle à DL-PA, ainsi qu'un opérateur de composition nondéterministe inclusive (par opposition à la composition nondéterministe exclusive de PDL).

Ce chapitre est organisé comme suit. Nous étendons DL-PA en DL-PPA (logique dynamique d'affectations propositionnelles parallèles) dans la section 3.1 et montrons dans la section 3.2 que la complexité reste dans PSPACE. Dans la section 3.3, nous montrons comment la planification séquentielle et parallèle ainsi que leurs versions bornées peuvent être traduites de manière polynomiale en DL-PPA. La section 3.4 conclut.

Nous étendons le langage de DL-PA avec deux nouveaux opérateurs π 1 π 2 et π 1 π 2 . Le premier permet d'indiquer que les deux programmes π 1 et π 2 sont exécutés en simultané, et le second est l'opérateur de composition nondéterministe inclusive. De la même manière que l'opérateur de composition nondéterministe exclusive, il permet l'exécution d'un des deux programmes, mais il permet également l'exécution des deux en parallèle. Le résultat de π 1 π 2 sera alors soit l'exécution de π 1 , soit l'exécution de π 2 , soit l'exécution de π 1 π 2 . Nous avons ensuite créé des programmes en DL-PA permettant de traduire ces deux opérateurs en un temps polynomial, ce qui montre que DL-PPA est dans PSPACE, comme DL-PA.

L'appartenance à cette classe de complexité rend DL-PPA intéressante pour traduire des problèmes de planification classique. Ceci ayant déjà été réalisé pour la recherche de l'existence de plan séquentiel en utilisant DL-PA, nous avons complété ces résultats en ajoutant la recherche de plans parallèles. Pour cela nous avons choisi d'utiliser la sémantique ∀-Step qui est généralement utilisée en planification. Pour respecter cette sémantique, nous avons fixé deux règles. La première est que deux actions effectuées en parallèle ne doivent pas avoir d'effets contradictoires. Une action qui ajoute un fluent ne peut pas être exécutée en parallèle d'une action qui le détruit. Par exemple l'action « porter l'objet » ne peut pas s'exécuter en même temps que l'action « poser l'objet ». L'une rend faux que l'objet est au sol alors que l'autre le rend vrai. La seconde est que les conditions ne peuvent pas être altérées par une autre action, ce que l'on appelle interaction croisée. La précondition d'une action ne peut pas être rendue fausse par une autre action. Par exemple, l'action de porter un objet pour l'agent i et l'action de porter le même objet pour l'agent j ne peuvent pas se produire en parallèle. Les deux ont pour précondition la présence de l'objet au sol et comme effet l'absence de cet objet au sol. De même pour les conditions des effets conditionnels qui ne peuvent pas devenir fausses (ou vraies si elles étaient fausses) suite aux effets d'une autre action exécutée en parallèle. Nous avons également utilisé l'opérateur de k ou moins répétitions d'un programme pour modéliser la recherche d'un plan en k étapes ou moins. En effet, bien qu'il soit prouvé qu'en planification classique à horizon non borné l'existence d'un plan séquentiel implique l'existence d'un plan parallèle et vice versa ce n'est pas forcément le cas pour la recherche à horizon borné, un plan parallèle en k étapes ou moins peut exister sans qu'un plan séquentiel soit possible avec le même horizon. and the standard operator of nondeterministic composition ∪ is similar to that between inclusive and exclusive disjunction: the interpretation of π 1 ∪ π 2 is "do either π 1 or π 2 ", while that of π 1 π 2 is "do either π 1 , or π 2 , or both". We call the former exclusive nondeterministic choice and the latter inclusive nondeterministic choice. The interpretation of parallel composition π 1 π 2 is that both programs are executed on local copies of the variables, and then the resulting state is obtained by merging these local states: π 1 π 2 fails if two assigned variables get assigned different truth values by π 1 and π 2 ; otherwise new truth values override old ones.

Language

The language of DL-PPA is built from a given countably infinite set of propositional variables P. Programs π and formulas ϕ are defined by the grammar

ϕ p | ⊥ | ¬ϕ | ϕ ∧ ϕ | π ϕ π p←ϕ | ϕ? | π; π | π ∪ π | π π | π π | π *
where p ranges over P. The formula π ϕ reads "there is a possible execution of π such that ϕ is true afterwards". The program p←ϕ assigns the truth value of ϕ to p and is called atomic program. For example, p←¬p swaps the truth value of p: when p is true then it becomes false and vice versa. ϕ? tests that ϕ is true (which fails when ϕ is false). π 1 ; π 2 executes π 1 and π 2 in sequence. π 1 ∪ π 2 nondeterministically chooses between executing either π 1 or π 2 ; and π 1 π 2 nondeterministically chooses between executing either π 1 , or π 2 , or both. π 1 π 2 is the parallel composition of π 1 or π 2 . The set of all formulas is Fml. In the following, we will use the standard abbreviations for ∨, → and ↔.

The language of DL-PA is the fragment of DL-PPA without and .

The set of propositional variables occurring in a formula ϕ is noted P ϕ ; similarly, the set of variables occurring in a program π is noted P π . For example, P p←q∨r = {p, q, r}.

DL-PA and DL-PPA

The length of DL-PPA formulas and of DL-PPA programs is the number of symbols required to write them down, excluding parentheses and considering that the length of propositional variables is 1. We note them (ϕ) and (π).

We use standard formula connectives such as and ϕ → ψ. We use the program connectives of n-times iteration of programs, recursively defined by π ≤0 = ? π ≤n+1 = ? ∪(π; π ≤n ) Furthermore, ; p i ∈P p i ←ϕ i is a shorthand for p 1 ←ϕ 1 ; • • • ; p n ←ϕ n , for P = {p 1 , . . . , p n }. When P = ∅ we identify the sequence with ?. We have to be careful here because sequential composition ';' is not commutative; e.g., the interpretation of p←q; q←p will differ from that of q←p; p←q. Each time we use the abbreviation we will make sure that the order does not matter.

Semantics of DL-PPA

Semantics is in terms of valuations, alias states, which are subsets of P. So the set of all valuations is 2 P . We use V , V , U , W , . . . to denote valuations.

p DL-PA = {V : p ∈ V } π ϕ DL-PA = V : there is U such that (V , U ) ∈ π DL-PA and U ∈ ϕ DL-PA p←ϕ DL-PA = {(V , V ∪{p}) : V ∈ ϕ DL-PA } ∪ {(V , V \{p}) : V ∈ ϕ DL-PA } ϕ? DL-PA = {(V , V ) : V ∈ ϕ DL-PA } π 1 ; π 2 DL-PA = π 1 DL-PA • π 2 DL-PA π 1 ∪ π 2 DL-PA = π 1 DL-PA ∪ π 2 DL-PA π * DL-PA = ( π DL-PA ) * = k∈N 0 ( π DL-PA ) k
Table 3.1: Interpretation of DL-PA formulas and programs Formulas and programs are interpreted by mutual recursion. In DL-PA, the interpretation of a formula ϕ was a set of valuations ϕ DL-PA ⊆ 2 P and the interpretation of a program π is a binary relation on valuations π DL-PA ⊆ 2 P × 2 P ; the main clauses are recalled in Table 3.1. In contrast, in DL-PPA the interpretation of a program π is a ternary relation on the set of valuations π ⊆ 2 P × 2 P × 2 P . When (V , U , W ) ∈ π then there is an execution of π from state V to state U assigning the variables in W . The definition is again by mutual recursion and the main clauses are given in Table 3.2; the others are standard.

Let us comment on the clauses that are new w.r.t. DL-PA.

The semantics of the assignment p←ϕ is: p is made true if ϕ is true and is made false if ϕ is false, and in both cases the set of assigned variables is the singleton {p}.

The semantics of parallel composition is that each subprogram π k is executed locally; then it is checked whether the modifications (in terms of assigned variables) are compatible: this is the case when all variables that are assigned by both subprograms (namely the variables in W 1 ∩ W 2 ) get assigned the same truth value. If this is not the case then the parallel composition fails; otherwise the resulting valuation U is computed by putting together (1) the unchanged part of V (i.e., V \ W ), ( 2) the updates of π 1 (i.e., U 1 ∩ W 1 ), (3) the updates of π 2 (i.e., U 2 ∩W 2 ). Moreover, the set of variables W assigned by the parallel composition is the union of those assigned by the subprograms.

The semantics of inclusive nondeterministic composition π 1 π 2 is, as announced, the exclusive nondeterministic composition of the three programs π 1 , π 2 and π 1 π 2 .

Here are some examples of interpretations of programs:

p←⊥ = {(V , V \ {p}, {p}) : V ⊆ P} ? p←⊥ = p←⊥ p← p←⊥ = ∅ p← q←⊥ = {(V , (V \ {q}) ∪ {p}, {p, q}) : V ⊆ P} p←p p←⊥ = {(V , V , {p}) : V ⊆ P and p / ∈ V } Proposition 7.
Let π be a DL-PPA program and let (V , U , W ) ∈ π . Then:

• W ⊆ P π ; • V \ U ⊆ W and U \ V ⊆ W ;
3.1 DL-PA and DL-PPA

p = {V : p ∈ V } π ϕ = {V : there are U , W such that (V , U , W ) ∈ π and U ∈ ϕ } p←ϕ = {(V , V ∪{p}, {p}) : V ∈ ϕ } ∪ {(V , V \{p}, {p}) : V / ∈ ϕ } ϕ? = {(V , V , ∅) : V ∈ ϕ } π 1 ; π 2 =    (V , U , W ) : there are U 1 , W 1 , W 2 s.th. (V , U 1 , W 1 ) ∈ π 1 , (U 1 , U , W 2 ) ∈ π 2 and W = W 1 ∪ W 2    π 1 ∪ π 2 = π 1 ∪ π 2 π 1 π 2 = π 1 ∪ π 2 ∪ π 1 π 2 π 1 π 2 =            (V , U , W ) : there are U 1 , W 1 , U 2 , W 2 such that (V , U 1 , W 1 ) ∈ π 1 , (V , U 2 , W 2 ) ∈ π 2 , W 1 ∩ W 2 ∩ U 1 = W 1 ∩ W 2 ∩ U 2 , U = (V \W ) ∪ (U 1 ∩W 1 ) ∪ (U 2 ∩W 2 ), and W = W 1 ∪ W 2            π * = k∈N0 π k Table 3.2: Interpretation of DL-PPA programs • If P π ⊆ P then V ⊆ P implies U ⊆ P .
The first item can be restricted a bit further: W is a subset of the variables occurring on the left-hand side of assignments of π.

The next result says that the variables not occurring in a formula or a program do not matter in their interpretation. Proposition 8. Let ϕ be a DL-PPA formula and π a DL-PPA program. Let P be a set of variables none of which occurs in ϕ or π, i.e., P is such that

P ∩ P ϕ = P ∩ P π = ∅. Then • V ∪P ∈ ϕ iff V \P ∈ ϕ ; • (V ∪P, U ∪P, W ) ∈ π iff (V \P, U \P, W ) ∈ π .
A formula ϕ is satisfiable if and only if ϕ = ∅. Thanks to Propositions 7 and 8, when checking validity or satisfiability of a formula ϕ it suffices to check triples (V , U , W ) whose elements are all subsets of P ϕ .

Reduction from DL-PPA to DL-PA

We suppose that variables used in a counter do not occur elsewhere, so that they do not interfere with other programs.

Counters allow us to formulate in a more compact way our abbreviation π ≤k whose expansion has length exponential in k: using a log k -bit counter we can identify π ≤k with the program ct←0; (¬ct=k ? ; π; ct++) * whose length is linear in (π) + log k. Indeed, although these two programs do not have the same interpretation, they behave the same as far as the variables of π are concerned.

Proposition 11. For valuations V , U , W ⊆ P π , we have (V , U , W ) ∈ π ≤k if and only if

(V , U ∪U , W ∪W ) ∈ ct←0; (¬ct=k ? ; π; ct++) *
for some subsets U and W of the set of counter variables.

Reduction from DL-PPA to DL-PA

We are now going to give a polynomial-time reduction of formulas and programs of DL-PPA to DL-PA. Our translation eliminates and thanks to the introduction of (several kinds of) copies of propositional variables.

Auxiliary variables

First, the variable δ p stores that p has been assigned; it will allow us to simulate the third component W of the interpretation of programs that keeps trace of assigned variables.

Second, when translating parallel composition we sequentialise the parallel execution of two programs π 1 and π 2 , and in order to safely do so we let each of them work on local copies of variables p, respectively noted (p) 1 and (p) 2 .

The translation of inclusive nondeterministic composition π 1 π 2 also requires some care: the naive f (π 1 π 2 ) = π 1 ∪ π 2 ∪ (π 1 π 2 ) would come with an exponential growth. Our translation re-uses the above copying technique.

Dynamic Logic of Parallel Propositional Assignments

We extend copying from variables to sets of variables and to programs. We associate to each set of variables P ⊆ P the copies (P ) 1 = {(p) 1 : p ∈ P } and (P ) 2 = {(p) 2 : p ∈ P }; and we map programs π to programs (π) 1 by replacing all variables p of π by (p) 1 ; similarly, we map π to (π) 2 . For example, (p←q ∧ r) 2 = (p) 2 ←(q) 2 ∧ (r) 2 .

Proposition 12. Let V , U , W ⊆ P π and let k be either 1 or 2. Then:

• (V , U , W ) ∈ π iff ((V ) k , (U ) k , (W ) k ) ∈ (π) k ; • V ∈ ϕ iff (V ) k ∈ (ϕ) k .
The proof is by simultaneous induction on the structure of π and ϕ.

Programs and formulas used in the translation

The translation uses some programs and formulas that are defined in this subsection.

The first program creates two copies of the variables in a finite set P ⊆ P and stores that these copies have not been assigned yet:

copy(P ) = ; p∈P (p) 1 ←p; (p) 2 ←p; δ (p) 1 ←⊥; δ (p) 2 ←⊥
Proposition 13. For every finite P ⊆ P, (V , U ) ∈ copy(P ) DL-PA if and only if

U = ((V \ ((P ) 1 ∪(P ) 2 )) ∪ ((V ) 1 ∩(P ) 1 ) ∪ ((V ) 2 ∩(P ) 2 )) \ (δ ((P ) 1 ) ∪ δ ((P ) 2 ) ).
The next program copies back the values of the i-copies of the elements of P and records whether they were modified, for i ∈ {1, 2}: get(P, i) = ; p∈P p←(p) i ; δ p ←δ p ∨ δ (p) i Proposition 14. For every finite P ⊆ P, (V , U ) ∈ get(P, i) DL-PA if and only if

U = ((V \ P ) ∪ {p : (p) i ∈ V } ∪ {δ p : δ (p) i ∈ V ∩ δ (P ) i }.

Reduction from DL-PPA to DL-PA

The last program merges two parallel subprograms: it copies back the values of the variables in P , depending on where it got modified:

merge(P ) = ; p∈P p←(p ∧ ¬δ (p) 1 ∧ ¬δ (p) 2 ) ∨ ((p) 1 ∧ δ (p) 1 ) ∨ ((p) 2 ∧ δ (p) 2 ); δ p ←δ p ∨ δ (p) 1 ∨ δ (p) 2
Proposition 15. For every finite P ⊆ P, (V , U ) ∈ merge(P ) DL-PA if and only if

U = (V \ (P ∪ δ P )) ∪        p ∈ P : (p ∈ V and δ (p) 1 , δ (p) 2 / ∈ V ) or (δ (p) 1 , (p) 1 ∈ V ) or (δ (p) 2 , (p) 2 ∈ V )        ∪ {δ p ∈ δ P : δ p ∈ V or δ (p) 1 ∈ V or δ (p) 2 ∈ V )}.
Finally, the following formula conditions the merging of two parallel subprograms:

Mergeable(P ) = p∈P δ (p) 1 ∧ δ (p) 2 → (p) 1 ↔ (p) 2

The translation

We are going to show that and can be polynomially eliminated from DL-PPA formulas. The resulting formula is in the language of DL-PA, which will allow us to transfer complexity results. The recursive definition of the translation of formulas and programs is given in Table 3.3. It is homomorphic for all the program operators and logical operators of PDL, so we only comment the non-trivial cases: assignments, parallel composition and inclusive nondeterministic composition.

• Each assignment p←ϕ is translated by additionally storing that p has been assigned (via a fresh variable δ p ).

• The translation of parallel composition π 1 π 2 relies on the introduction of two fresh copies (p) 1 and (p) 2 of each propositional variable p occurring in π 1 π 2 . Then for each program π, the program (π) 1 is obtained by substituting each p in π by its copy (p) 1 ; similarly for (π) 2 . The translation of π 1 π 2 starts by making local copies for each subprogram, then executes π 1 and π 2 on these copies. Then the translation checks whether the two results can be merged. If so then the values of the relevant copies are copied back to each p (doing nothing when none of the copies has been assigned). Finally the auxiliary variables (p) 1 and (p) 2 are set to false.

• In the translation of inclusive nondeterministic composition π 1 π 2 , the check of compatibility followed by copying back is replaced by an exhaustive nondeterministic composition of either checking compatibility and copying back the values computed by π 1 π 2 , or copying back the values computed by π 1 , or copying back the values computed by π 2 .

f (p) = p f (p←ϕ) = p←f (ϕ); δ p ← f (⊥) = ⊥ f (ϕ? ) = f (ϕ)? f (¬ϕ) = ¬f (ϕ) f (π 1 ; π 2 ) = f (π 1 ); f (π 2 ) f (ϕ 1 ∨ ϕ 2 ) = f (ϕ 1 ) ∨ f (ϕ 2 ) f (π 1 ∪ π 2 ) = f (π 1 ) ∪ f (π 2 ) f ( π ϕ) = f (π) f (ϕ) f (π * ) = (f (π)) * f (π 1 π 2 ) = copy(P π 1 ∪ P π 2 ); f (π 1 ) 1 ; f (π 1 ) 2 ;
Mergeable(P π 1 ∪ P π 2 )? ; merge(P π 1 ∪ P π 2 );

f (π 1 π 2 ) = copy(P π 1 ∪ P π 2 ); f (π 1 ) 1 ; f (π 1 ) 2 ;
((Mergeable(P π 1 ∪ P π 2 )? ; merge(P π 1 ∪ P π 2 ))

∪ get(P π 1 , 1) ∪ get(P π 2 , 2));

(p) 1 ← ; δ (p) 1 ← ; (p) 2 ←⊥; δ (p) 2 ← ; (δ (p) 1 ∧ δ (p) 2 ) → ((p) 1 ↔ (p) 2 )? ; p←(p ∧ ¬δ (p) 1 ∧ ¬δ (p) 2 ) ∨ ((p) 1 ∧ δ (p) 1 ) ∨ ((p) 2 ∧ δ (p) 2 ); δ p ←δ p ∨ δ (p) 1 ∨ δ (p) 2 .
Just as the original program, the translated program has an empty interpretation because after setting δ (p) 2 and δ (p) 1 to true and (p) 1 to true and (p)

2
to false, the test

δ (p) 1 ∧ δ (p) 2 → (p) 1 ↔ (p) 2 ?
is going to fail.

Correctness of the translation

We define the copied variables for the translation of programs and formulas as:

CP(ϕ) = P f (ϕ) \ (P ϕ ∪ δ Pϕ ) CP(π) = P f (π) \ (P π ∪ δ Pπ )
For example, the copied variables of the above program are CP(p← p←⊥) = {(p) 1 , (p) 2 , δ (p) 1 , δ (p) 2 }. Observe that P f (π) is a subset of P π ∪ δ Pπ ∪ CP(π) and that P π , δ Pπ , and CP(π) are disjoint. We call P ϕ ∪ δ Pϕ the surface variables of f (ϕ); similarly, P π ∪ δ Pπ are the surface variables of f (π).

We say that two valuations V and V agree on a set of propositional variables X ⊆ P if V ∩ X = V ∩ X. It follows from Proposition 8 that if V and V agree on P ϕ then V ∈ ϕ if and only if V ∈ ϕ . This means that only the variables of ϕ matter when interpreting ϕ.

Lemma 16. Let δ p / ∈ P π and (V , U ) ∈ f (π) DL-PA . If δ p ∈ V thenδ p ∈ U .
Proof. The only modification of the change-recording variables occurs in the translation of parallel compositions and inclusive nondeterministic compositions, via assignments of the form δ p ←δ p ∨ δ (p) 1 ∨ δ (p) 2 . Therefore the δ p variables are never made false.

The next lemma relies on the fact that when translating π 1 π 2 and π 1 π 2 , the variables δ (p) i are set to false before the programs (π i ) i are executed: more fastidious. Basically, their proof uses that in the translation of parallel composition the initial values of all the copy variables (p) 1 and (p) 2 in CP(P π ) are irrelevant because they get assigned the value of p. Similarly, the initial values of change-recording variables that are not surface variables (such as δ (p) 1 and δ (p) 2 ) are irrelevant because they get assigned to false.

This ends the proof.

The second item of the above lemma implies that when V and V agree on

P π ∪ δ Pπ and (V , U ) ∈ f (π) then there is a U agreeing with U on P π ∪ δ Pπ such that (V , U ) ∈ f (π) .
The next lemma says that the change-recording variables can be added to the interpretation of translated formulas and programs.

Lemma 19. For all formulas ϕ, programs π and finite sets of variables X such that δ X ∩ P π = δ X ∩ P ϕ = ∅:

1. If V ∈ f (ϕ) DL-PA then V ∪δ X ∈ f (ϕ) DL-PA and V \δ X ∈ f (ϕ) DL-PA ; 2. If (V , U ) ∈ f (π) DL-PA then (V ∪ δ X , U ∪ δ X ) ∈ f (π) DL-PA and (V \ δ X , (U \ (δ X ∩ V ))) ∈ f (π) DL-PA .
Proof. We prove by simultaneous induction on the form of ϕ and π that for every p ∈ P:

1. If V ∈ f (ϕ) DL-PA then V ∪ {δ p } ∈ f (ϕ) DL-PA (IH1); 2. If V ∈ f (ϕ) DL-PA then V \ {δ p } ∈ f (ϕ) DL-PA (IH2); 3. If (V , U ) ∈ f (π) DL-PA then (V ∪ {δ p }, U ∪ {δ p }) ∈ f (π) DL-PA (IH3); 4. If (V , U ) ∈ f (π) DL-PA and δ p ∈ V then (V \ {δ p }, U \ {δ p }) ∈ f (π) DL-PA (IH4).
For formulas we only give the case of the dynamic operator. Suppose

V ∈ f ( π ϕ) DL-PA , which means that there is a U such that (V , U ) ∈ f (π) DL-PA and U ∈ f (ϕ) DL-PA . In order to prove that V ∪ {δ p } ∈ f ( π ϕ) DL-PA we use IH3 and IH1, which give us that (V ∪ {δ p }, U ∪ {δ p }) ∈ f (π) DL-PA and U ∪ {δ p } ∈ f (ϕ) DL-PA . In order to prove that V \ {δ p } ∈ f ( π ϕ) DL-PA we distinguish two cases. 3. If (V , U ) ∈ f (π) DL-PA then (V ∩P π , U ∩P π , W ) ∈ π for some W ⊆ P (IH3).
We analyse the different cases of formulas and programs.

• For formulas of the form π ϕ we prove the two directions of IH1 separately.

For the left-to-right direction, suppose V ∈ π ϕ . Then there are U , W such that (V , U , W ) ∈ π and U ∈ ϕ

. By IH2 and IH1:

(V ∩P π , (U ∩P π ) ∪ δ W ∪ X) ∈ f (π) DL-PA and U ∈ f (ϕ) DL-PA
for some X ⊆ CP(π). As to the interpretation of the program f (π), by Proposition 8 we can add the irrelevant variables V ∩(P ϕ \ P π ) to both elements of the tuple:

((V ∩P π ) ∪ (V ∩(P ϕ \ P π )), (U ∩P π ) ∪ (V ∩(P ϕ \ P π )) ∪ δ W ∪ X) ∈ f (π) DL-PA
. (The proposition applies because the sets V ∩(P ϕ \ P π ) and P f (π) are disjoint.) Again by Proposition 8 we have V ∩(P ϕ \ P π ) = U ∩(P ϕ \ P π ), and therefore get:

((V ∩(P ϕ ∪P π )), (U ∩(P ϕ ∪P π )) ∪ δ W ∪ X) ∈ f (π) DL-PA ,
that is

((V ∩P π ϕ , (U ∩P π ϕ ) ∪ δ W ∪ X) ∈ f (π) DL-PA . (3.1)
As to the interpretation of the formula f (ϕ), we modify U as follows:

intersect U with P f (ϕ) and then add the irrelevant variables U ∩(P π \ P ϕ ) thanks to Proposition 8 (similarly to what we did for programs);

subtract all change-recording variables of U and then add the change-recording variables δ W thanks to Lemma 19.

Reduction from DL-PPA to DL-PA

By these set-theoretic operations we obtain that

(U ∩P π ϕ ) ∪ δ W ∪ (U ∩CP(ϕ)) ∈ f (ϕ) DL-PA . (3.2)
Observe that the second element of the tuple in (3.1) and the valuation in (3.2) agree on the surface variables of π ϕ, and a fortiori on those of ϕ, i.e., on P ϕ ∪δ Pϕ . We can therefore apply the first item of Lemma 18: we have

(U ∩P π ϕ ) ∪ δ W ∪ X ∈ f (ϕ) DL-PA . (3.3)
Then 3.1 and 3.3 together tell us that

V ∩P π ϕ ∈ f (π) f (ϕ) DL-PA .
Applying again Lemma 19 we then get

(V ∩P π ϕ ) ∪ (V ∩δ P π ϕ ) ∈ f (π) f (ϕ) DL-PA .
As this valuation agrees with V on the surface variables of π ϕ, we can apply Lemma 18 again and conclude that

V ∈ f ( π ϕ) DL-PA .
For the right-to-left direction of IH1, suppose V ∈ f ( π ϕ) . Then there is a U such that

(V , U ) ∈ f (π) DL-PA and U ∈ f (ϕ) DL-PA
. Applying IH1 and IH3 we get that there is a W such that

(V ∩P π , U ∩P π , W ) ∈ π and U ∈ ϕ
. As above we can add the irrelevant variables V ∩(P ϕ \ P π ) thanks to Proposition 8:

(V ∩P π ϕ , U ∩P π ϕ , W ) ∈ π and U ∩P π ϕ ∈ ϕ
, from which it directly follows that V ∩P π ϕ ∈ π ϕ . The latter is equivalent to V ∈ π ϕ by Proposition 8.

DL-PPA applied to automated planning

Proof. The lower bound is due to PSPACE hardness of DL-PA satisfiability checking [START_REF] Herzig | A Dynamic Logic of Normative Systems[END_REF]. The upper bound follows from PSPACE membership of DL-PPA model checking via the preceding Proposition 24.

DL-PPA applied to automated planning

Lets recall the conditions for a set of actions to be consistent. A consistent set of actions has no contradictory effects and no cross-interaction between its actions. A set of actions A is say to be free of contradictory effects in a state V if and only if for any pair of actions a 1 , a 2 ∈ A and for every ce 1 ∈ eff (a 1 )

and ce 2 ∈ eff (a 2 ) if V ∈ ce 1 ∧ ce 2 then eff + (ce 1 ) ∩ eff -(ce 2 ) = ∅.
We say that two states V and V agree on a formula ϕ if and only if either V ∈ ϕ and V ∈ ϕ or V ∈ ϕ and V ∈ ϕ . Then we say that two different actions a 1 and a 2 have no cross-interaction at V if the following hold:

1. s and τ a 1 (s) agree on pre(a 2 ) and on the condition cnd(ce 2 ) of every conditional effect ce 2 ∈ eff (a 2 );

2. s and τ a 2 (s) agree on pre(a 1 ) and on the condition cnd(ce 1 ) of every conditional effect ce 1 ∈ eff (a 1 ).

In this section, we formally define actions and sequential and parallel planning tasks within our framework DL-PPA. Then we show that a DL-PPA model checking can be used to test the solvability of such tasks.

Sequential planning with conditional effects

We suppose given a set of action names Act. A planning task is a triple (V 0 , τ, Goal) where:

• V 0 ⊆ P is a valuation (the initial state)

• τ : Act × P → P is a partial function modeling the actions in Act

• Goal ∈ Fml is the goal Each action a ∈ Act is described with a tuple (pre(a), eff (a)) where:

• pre(a) ∈ Fml is the precondition of a;

• eff (a) ∈ Fml × 2 P × 2 P is a set of triples ce of the form

(cnd(ce), eff + (ce), eff -(ce)),
the conditional effects of a, where cnd(ce) is a DL-PPA formula (the condition) and eff + (ce) and eff -(ce) are sets of variables that are respectively added and deleted by a if condition ce is true.

The function τ can be defined from such action descriptions : :

τ a (V ) is defined (a is executable in state V ) if and only if V ∈ pre(a) and for all ce 1 , ce 2 ∈ eff (a) such that V ∈ cnd(ce 1 )∧cnd(ce 2 ) : eff + (ce 1 )∩eff -(ce 2 ) = ∅. When τ a is defined in V then: τ a (V ) = V \ ce∈eff (a) V ∈ cnd(ce) eff -(ce) ∪ ce∈eff (a) V ∈ cnd(ce) eff + (ce)
We associate to action a the DL-PPA program exeAct(a):

exeAct(a) = pre(a)? ce∈eff (a)   ¬cnd(ce)? ∪    cnd(ce)? p∈eff + (ce) p← q∈eff -(ce) q←⊥      
The program exeAct(a) behaves like a: Lemma 26. For every action a ∈ Act:

1. τ a is defined in V iff there are U , W such that (V , U , W ) ∈ exeAct(a) ; 2. If τ a is defined in V then τ a (V ) = U iff (V , U , W ) ∈ exeAct(a) for some W .
Proof. Let us take an arbitrary state V . τ a (V ) is not defined iff: (1) V / ∈ pre(a) , or (2) there are ce 1 , ce 2 ∈ eff (a) and p ∈ P such that V ∈ cnd(ce 1 )∧ cnd(ce 2 ) and eff + (ce 1 ) ∩ eff -(ce 2 ) contains some p. In case (1), the program fails because pre(a)? = ∅, in case ( 2), the program fails because p←⊥ p← = ∅. When τ a (V ) is defined then V ∈ pre(a) , so (V , V , ∅) ∈ pre(a)? . Moreover, for each ce ∈ eff (a) such that V ∈ cnd(ce) the programs ( p∈eff + (ce) p← ) and ( q∈eff -(ce) q←⊥) are executed in parallel and all the assignments are consistent (no p←⊥ and p← is executed in parallel). Then the parallel composition of all these programs leads, by definition, to the state 3.3 DL-PPA applied to automated planning

τ a (V ) = U , with (V , U , W ) ∈ exeAct(a)
, where W is the set of all assigned variables in the program exeAct(a).

We say that a state V is reachable by a sequential plan from a state V 0 via a set of conditional actions Act if there is a sequential plan, that is, a sequence of actions a 1 , . . . , a m from Act, and a sequence of states V 0 , . . . ,

V m with m ≥ 0 such that V = V m and τ a k (V k-1 ) = V k for every k such that 1 ≤ k ≤ m.
A planning task is solvable by a sequential plan if there is at least one state V ∈ Goal such that V is reachable by a sequential plan from V 0 via Act; otherwise it is unsolvable by a sequential plan.

Parallel planning with conditional effects

A set of actions A = {a 1 , . . . , a m } determines a partial function τ A from 2 P to 2 P : τ A (V ) is defined (a 1 , . . . , a m are executable in parallel in state V ) if and only if:

1. for all a i ∈ A, τ a i is defined in V , and

the set of actions

A is consistent in V . When τ A is defined in V then: τ A (V ) =      V \ a∈A,ce∈eff (a), V ∈ cnd(ce) eff -(ce)      ∪ a∈A,ce∈eff (a), V ∈ cnd(ce) eff + (ce)
To every set of conditional actions we can associate a DL-PPA program that behaves exactly like the parallel execution of its elements. Given A = {a 1 , . . . , a m }, let exeAct(A) be the DL-PPA program

exeAct(A) = a∈A    exeAct(a) a ∈A a =a exeAct(a ) pre(a)? ce∈eff (a) (cnd(ce) ↔ exeAct(a ) cnd(ce)) ?    Lemma 27. For every finite set of actions A = {a 1 , . . . , a m }, 1. τ A is defined in V iff there are U , W such that (V , U , W ) ∈ exeAct(A) ; 2. If τ A is defined in V then τ A (V ) = U iff (V , U , W ) ∈ exeAct(A) for some W .
Proof. Let us take an arbitrary state V and two actions a, a ∈ A. By Lemma 26, for all i ∈ {1, . . . , m} we know that exeAct(a i ) behaves like a i , and then is executable if

τ a i (V ) is defined. τ A (V ) is not defined if and only if; (1) τ a (V ) is not defined; (2) There are ce ∈ eff (a) and ce ∈ eff (a ) and p ∈ P such that V ∈ cnd(ce) ∧ cnd(ce ) and p ∈ eff + (ce) ∩ eff -(ce ); (3) τ a (V ) /
∈ pre(a) ; ( 4) there is a conditional effect ce = cnd(a) such that V and τ a (V ) do not agree on ce.

Case ( 2) happens if and only if exeAct(a) exeAct(a ) fails because of the execution of the parallel composition of p←⊥ and p← ; case (3) happens if and only if then the execution of exeAct(a ) pre(a)? fails; case (4) happens if and only if the execution of (cnd(ce) ↔ exeAct(a ) cnd(ce))? fails.

When τ A is defined,

a ∈A a =a exeAct(a ) pre(a)? ce∈eff (a) (cnd(ce) ↔ exeAct(a ) cnd(ce))?
is defined. Then, the parallel composition of exeAct(a)(V ) for every action a ∈ A leads, by definition, to the state τ A (V ) = U , with (V , U , W ) = exeAct(A) , where W is the set of all assigned variables in the program exeAct(A).

We say that a state V is reachable by a parallel plan from a state V 0 via a set of actions Act if there is a parallel plan, that is, a sequence A 1 , . . . , A m of sets of actions A i ⊆ Act and a sequence of states V 0 , . . . , V m with m ≥ 0 such that V = V m and τ A k (V k-1 ) = V k for every k such that 1 ≤ k ≤ m. A planning task (Act, V 0 , Goal) is solvable by a parallel plan if there is at least one state V ∈ Goal such that V is reachable by a parallel plan from V 0 via Act; otherwise it is unsolvable by a parallel plan.

Solvability of bounded horizon planning tasks

Now that we have defined a parallel encoding of actions and the solvability of a planning task, we can capture the solvability of a planning task in DL-PPA 3.3 DL-PPA applied to automated planning with a bounded horizon k. This problem is known to be PSPACE-complete [START_REF] Bylander | The Computational Complexity of Propositional STRIPS Planning[END_REF]).

Theorem 28. A planning task (Act, V 0 , Goal) is solvable by a sequential plan with no more than k actions if and only if:

V 0 ∈   a∈Act exeAct(a)   ≤k

Goal

Proof. Our formula reads "there exists an execution of ( a∈Act exeAct(a)) ≤k after which Goal is true." We know by Lemma 26 that exeAct(a) behaves correctly and produces the same effects as action a. The program ( a∈Act exeAct(a)) ≤k non-deterministically chooses an action a from Act and executes the corresponding program exeAct(a), then repeats this a number of times less or equal than k. This produces a sequence of at most k actions, i.e., a sequential plan bounded by k. Therefore the formula is satisfied in the initial state if and only if there exists a sequential plan of length bounded by k after which the goal is satisfied, i.e., if and only if the planning task is solvable with a sequence of at most k actions.

Theorem 29. A planning task (Act, V 0 , Goal) is solvable by a parallel plan with no more than k steps if and only if:

V 0 ∈   a∈Act exe a ←⊥; a∈Act exe a ← ; π exe   ≤k

Goal

where exe a / ∈ P exeAct(a) for all a ∈ Act, and

π exe = a∈Act        ¬exe a ? ∪      exe a ? exeAct(a) a ∈Act a =a    ¬exe a ? ∪ exe a ? exeAct(a ) pre(a)? ce∈eff (a) (cnd(ce) ↔ exeAct(a ) cnd(ce)) ?               
Proof. The program a∈Act exe a ←⊥ initialises a special fresh variable exe a / ∈ P exeAct(a) to ⊥, for each action a ∈ Act. Then the inclusive nondeterministic composition a∈Act exe a ← chooses some non empty subset of actions A ⊆ Act and executes the program a∈A exe a ← . At this point, exe a = iff a ∈ A, and the program π exe is executed. It is easily seen that, for a given choosen set of actions A, π exe behaves like the program exeAct(A). We know by Lemma 27 that this latter program behaves correctly and produces the same effect as the parallel execution of all actions in A. The sequence a∈Act exe a ←⊥; a∈Act exe a ← ; π exe is then repeated a number of times less or equal than k. This produces a sequence of at most k parallel executions of action sets, i.e., a parallel plan bounded by k. Therefore the formula is satisfied in the initial state if and only if there exists a parallel plan of length bounded by k after which the goal is satisfied, i.e., if and only if the planning task is solvable with a sequence of at most k parallel steps.

The nondeterministic choice of a subset of the set of actions to be executed at a step could be expressed by the program A⊆Act exeAct(A). However, this would have length exponential in the number of actions.

Both in Theorem 28 and in Theorem 29, the size of the model checking problems is polynomial in the size of the planning task plus log k. This relies on our compact representation of bounded programs π ≤k , cf. Proposition 11.

Conclusion

We have shown how to capture parallel classical planning in an extension of DL-PA by parallel and inclusive nondeterministic composition whose model checking and satisfiability checking problems are still in PSPACE. This allows in particular to decide, within the complexity boundaries, the existence of a plan given a finite horizon.

A straightforward continuation of our work is towards parallel epistemic planning: We can take over the epistemic extension of DL-PA in terms of observational variables that was applied to sequential epistemic planning in (Cooper, Herzig, Maffre, Maris, and Régnier 2016a).

Making Parallel Classical Planning Epistemic

Epistemic planning is important in multiagent systems. None of these approaches investigated up to now studied the construction of parallel epistemic plans. Such plans are however particularly interesting when there is more than one agent. In this chapter we investigate how multiple agents can act in parallel in order to achieve a common goal.

In the previous chapter we used this framework in order to solve classical planning tasks with parallel plans. In that work we supposed that agents always have perfect knowledge of the current state and of the occurrence of actions. We here relax this hypothesis: an agent may fail to observe the truth value of a given propositional variable and may fail to observe some actions. Moreover, they may not know other agents' observational capabilities. The object of these capabilities can be a propositional variables, but also the other agents' visibility; in other words, we consider higher-order visibility information.

We here apply EL-O to parallel epistemic planning: we provide a reduction of EL-O-based parallel planning to classical planning, which allows us to translate planning tasks into PDDL and use classical planners. We illustrate our approach with a parallel version of the epistemic gossip problem (Cooper, Herzig, Maffre, Maris, and Régnier 2019) where n agents initially each know their secret but not the others'; agents can exchange all secrets they know during a phone call to another agent; and the goal is to achieve shared knowledge of all secrets, i.e., everybody knows every secret. A parallel solution to the epistemic gossip problem is a sequence of sets of calls.

The content of this chapter corresponds to an article published at the International Conference on Principles of Knowledge Representation and Reasoning (KR 2020) (Cooper, Herzig, Maris, Perrotin, et al. 2020).

Content of the chapter

Résumé du chapitre en français

La planification épistémique est importante dans les systèmes multi-agents. Aucune de ces approches étudiées jusqu'à présent n'a étudié la construction de plans épistémiques parallèles. De tels plans sont pourtant particulièrement intéressants lorsqu'il y a plus d'un agent. Dans ce chapitre, nous étudions comment plusieurs agents peuvent agir en parallèle afin d'atteindre un objectif commun.

Dans le chapitre précédent, nous avons utilisé ce cadre pour résoudre des tâches de planification classiques avec des plans parallèles. Dans ce travail, nous avons supposé que les agents ont toujours une connaissance parfaite de l'état actuel et de l'occurrence des actions. Nous relaxons ici cette hypothèse : un agent peut ne pas observer la valeur de vérité d'une variable propositionnelle donnée et peut ne pas observer certaines actions. De plus, il peut ne pas connaître les capacités d'observation des autres agents. L'objet de ces capacités peut être une variable propositionnelle, mais aussi la visibilité des autres agents ; en d'autres termes, nous considérons une information de visibilité d'ordre supérieur.

Nous appliquons ici EL-O à la planification épistémique parallèle : nous fournissons une réduction de la planification parallèle basée sur EL-O à la planification classique, ce qui nous permet de traduire les tâches de planification en PDDL et d'utiliser des planificateurs classiques. Nous illustrons notre approche avec une version parallèle du problème de bavardage épistémique (Cooper, Herzig, Maffre, Maris et Régnier 2019) où n agents connaissent initialement chacun leur secret mais pas celui des autres ; les agents peuvent échanger tous les secrets qu'ils connaissent lors d'un appel téléphonique à un autre agent ; et l'objectif est de parvenir à une connaissance partagée de tous les secrets, c'est-à-dire que tout le monde connaît tous les secrets. Une solution parallèle au problème du bavardage épistémique est une séquence d'ensembles d'appels.

De la même manière que pour la planification classique parallèle du chapitre précédent il nous faut respecter l'absence d'effets contradictoires et d'interaction croisée. L'ajout de raisonnement sur les connaissances, et plus particulièrement de l'opérateur de visibilité jointe JS , impose de revoir ces règles. Nous faisons cela avec une expansion des descriptions d'actions et des tâches de planification. Cette expansion se fait en ajoutant les causes et les conséquences des fluents de la tâche de planification. La relation de conséquence est définie comme suit. α intérêtest la cause de β -et β la conséquence de α -si α = β ou si α = JS α et que β est une suite d'opérateurs de visiblité se terminant par α . En incluant aux ensembles (effets et état initial) les conséquences de leurs atomes et aux formules (préconditions, conditions et but) les causes de leurs atomes, nous pouvons appliquer les mêmes règles qu'en planification classique pour les contraintes liées à l'exécution en parallèle des actions. En restreignant l'expansion des conséquences aux fluents pertinents pour la tâche de planification que l'on souhaite résoudre -ceux présents dans la description de la tâche avant l'expansion -la complexité du problème d'existence d'un plan parallèle à un problème de planification épistémique est PSPACE-complète.

Ce résultat nous permet de considérer l'utilisation de planificateurs pour la planification classique pour résoudre des problèmes épistémiques. Nous avons réalisé un test de performance (benchmark) pour évaluer l'intérêt pratique d'une telle approche. Les résultats obtenus sont difficilement exploitables, la plupart des problèmes testés deviennent rapidement trop complexes lorsque l'on augmente leur taille. Cependant nous pensons que de futurs travaux utilisant cette approche pourraient permettre une résolution de problèmes de planification épistémique avec une efficacité proche de celle de la planification classique.

when α starts by JS) or the singleton {α} (namely when α is a propositional variable or starts by some S i ). Our formulation uses a generalisation of atomic consequence to sets of atoms s ⊆ ATM : s ⇒ = α∈s α ⇒ . Proposition 30. The following hold for every A, B ⊆ ATM :

1. (A ∪ I -Atm) ⇒ = A ⇒ ∪ I -Atm; 2. A ⇒ ∩ B ⇐ = ∅ iff A ⇒ ∩ B = ∅ iff A ∩ B ⇐ = ∅.

Language of EL-O

The language of EL-O is defined by the following grammar:

ϕ ::= α | ⊥ | ¬ϕ | (ϕ ∧ ϕ)
where α ranges over ATM .

The length of a formula is defined recursively by:

(⊥) = 1 (p) = 1 (σ p) = (σ) + 1 (¬ϕ) = (ϕ) + 1 (ϕ ∧ ϕ ) = (ϕ) + (ϕ ) + 1
where (σ) is the length of the finite sequence σ. For example, (S 1 S 2 p) = 3 and (S 2 p ∧ ¬p ∧ JS q) = 8. If β ⇒ α then the length of β is less than or equal to the length of α. Moreover, the set of causes of α has at most (α) elements: |α ⇐ | ≤ (α). It follows that the sum of the lengths of all causes of α is at most quadratic in the length of α:

Proposition 31. For every α, β : β⇒α (β) ≤ ( (α)) 2 .

Example 2. In the generalised gossip problem, for Agt = {1, . . . , n} the set of secrets is P = {sec i : i ∈ Agt}. The goal is to obtain shared knowledge of depth k:

Goal G k = i∈Agt σ ∈OBS + , (σ)≤k σ sec i . 4.1 EL-O: Epistemic Logic of Observation s |= α if α ∈ s ⇒ ∪ I -Atm s |= ¬ϕ if s |= ϕ s |= ϕ ∧ ψ if s |= ϕ and s |= ψ Table 4.1: Interpretation of formulas Hence Goal G 1 = i∈Agt j∈Agt S j sec i .

Semantics of EL-O

A state is a subset of the set of atoms ATM . We denote states by s, s , etc.

The set of all states is STATES = 2 ATM . The set of relevant states is R-STATES = 2 R-Atm . A way of guaranteeing introspection was proposed in [START_REF] Herzig | A Poor Man's Epistemic Logic Based on Propositional Assignment and Higher-order Observation[END_REF] where formulas are interpreted exclusively in introspectively closed states: states that contain all introspective atoms and are closed under ⇒, i.e., sets of atoms that equal s ∪ I -Atm ⇒ for some state s ⊆ ATM . Such introspective states being always infinite, it is not clear how to define model checking, which requires finite states. Here we work with finite models and interpret formulas in such a way that introspection is simulated.

The truth conditions for EL-O formulas are in Table 4.1. The condition for atoms is the only non-standard one: α is true in state s if α is introspective or β ⇒ α for some β ∈ s.

Example 3. In the initial gossiping state (in which secrets may or may not be true) every agent only knows her own secret. Therefore s

G 1 0 = {S i sec i : i ∈ Agt} ∪ A 1 where A 1 is some subset of {sec i : i ∈ Agt}. Then s G 1 0 |= S i sec i and s G 1 0 |= j =i ¬S i sec j for every i ∈ Agt. Although s G 1 0 does not contain S i S i sec j we have s G 1 0 |= S i S i sec j .
Given a set of states St ⊆ STATES, we say that a formula ϕ is valid in St if s |= ϕ for every s ∈ St; when s |= ϕ for some s ∈ St then we say that ϕ is satisfiable in St. Clearly, an atom α is valid in the set of all states STATES if and only if it is introspective. Moreover, atomic consequences are valid in

STATES: if α ⇒ β then α → β is valid in STATES. Remark 1.
When Agt is a singleton then S i p ∧ ¬JS p is satisfiable. While this anomaly could be taken care of by a modification of the semantics, we do not do so for the sake of readability and content ourselves with the observation that the JS operator is superfluous when there is only one agent.

Proposition 32. For every ϕ ∈ Fml EL-O there is a ϕ ∈ R-Fml EL-O such that ϕ ↔ ϕ is valid in STATES. Moreover, for every s ∈ STATES, there is a s ∈ R-STATES such that s |= ϕ iff s |= ϕ for every ϕ ∈ Fml EL-O .

Classical semantics for Fml EL-O is recovered by changing the truth condition for atoms:

s |= CPC α if α ∈ s. Proposition 33. For ϕ ∈ R-Fml EL-O and s ∈ R-STATES, s |= ϕ iff s ⇒ ∩ ATM (ϕ) |= ϕ iff s ⇒ ∩ ATM (ϕ) |= CPC ϕ.

Action Descriptions and Simple Epistemic Planning tasks

We assume that actions are deterministic and have conditional effects that are described by add-and delete-lists. Such effects are crucial in epistemic planning: when an agent performs an action then the effects on another agent's epistemic state typically depend on whether that agent sees the variables that are modified by the action.

Action Descriptions

An action description is a pair a = (pre(a), eff (a)) where pre(a) is a relevant formula from R-Fml EL-O (the precondition of a) and

eff (a) ⊆ R-Fml EL-O × 2 R-Atm × 2 R-Atm
is the set of conditional effects of a, describing which atoms the action may add or remove from the current state under additional conditions. For a triple ce = (cnd(ce), ceff + (ce), ceff -(ce))

in eff (a), cnd(ce) is the condition of ce, ceff + (ce) are the added atoms, and ceff -(ce) are the deleted atoms. We require effects to be consistent: we suppose that for every ce

1 , ce 2 ∈ eff (a), if ceff + (ce 1 ) ∩ (ceff -(ce 2 )) ⇐ = ∅ then pre(a) ∧ cnd(ce 1 ) ∧ cnd(ce 2 ) is unsatisfiable in EL-O.
That is, we exclude actions with conditional effects ce 1 , ce 2 ∈ eff (a) and α 1 ∈ ceff + (ce 1 ) and α 2 ∈ ceff -(ce 2 ) such that α 1 ⇒ α 2 . In other words, when pre(a) and their 4.2 Action Descriptions and Simple Epistemic Planning tasks triggering conditions cnd(ce 1 ) and cnd(ce 2 ) are jointly satisfiable then two conditional effects of a cannot conflict. This in particular forbids conditional effects ce ∈ eff (a) with ceff + (ce)∩ceff -(ce) = ∅ and pre(a)∧cnd(ce) satisfiable.

We disregard introspective atoms in the definition of actions because they are true at every state: adding or deleting them from a state does not change what is true in that state.

Example 4. In the original gossip problem G 1 where the goal is to obtain shared knowledge of depth 1, Call i,j = (pre(Call i,j ), eff (Call i,j )) with pre(Call i,j ) = and eff (Call i,j ) = {(S i sec 1 , {S j sec 1 }, ∅), (S j sec 1 , {S i sec 1 }, ∅), . . . ,

(S i sec n , {S j sec n }, ∅), (S j sec n , {S i sec n }, ∅)}.
That is, a call has two conditional effects per secret: if i sees a secret then that secret becomes visible to j, and vice versa.

Example 5. In the generalised gossip problem G k the precondition is pre(Call i,j ) = as before, and for every 0 ≤ m < k, σ m ∈ OBS ≤m and r ∈ Agt there is a conditional effect ce ∈ eff (Call i,j ) of the form:

cnd(ce) = S i σ m sec r ∨ S j σ m sec r , ceff + (ce) = {σ S i σ m sec r : σ ∈ {S i , S j } ≤k-m-1 } ∪ {σ S j σ m sec r : σ ∈ {S i , S j } ≤k-m-1 } = {σ σ m sec r : σ ∈ {S i , S j } ≤k-m }, ceff -(ce) = ∅,
where {S i , S j } ≤k-m denotes the set all sequences of observability operators S i and S j of length at most k-m. Hence a call achieves common knowledge of i and j up to level k of all secrets one of them knows. The set of all actions is Act G k = {Call i,j : i, j ∈ Agt, i = j}. All Call i,j satisfy our consistency condition because they have no negative effects, which makes conflicts impossible.

The length of an action description is

+ α∈ceff + (ce) (α) + α∈ceff -(ce) (α)     .

Simple Epistemic Planning Tasks

A simple epistemic planning task is a triple

P = (s 0 , τ, Goal)
where (We again disregard introspective atoms as they have no effect on the truth of a formula.)

• s 0 ∈ R-STATES = 2 R-Atm
Example 6. The planning task that corresponds to the original gossip problem is

G 1 = (s G 1 0 , Act G 1 , Goal G 1 ) with • Act G 1 = {Call i,j : i, j ∈ Agt and i = j} (cf. Example 4), • s G 1 0 = {S i sec i : i ∈ Agt} ∪ A 1 for some A 1 ⊆ {sec i : i ∈ Agt}, • Goal G 1 = i∈Agt j∈Agt S j sec i .
The set of atoms of a simple epistemic planning task is

ATM (P) =   a∈Act ATM (a)   ∪ s 0 ∪ ATM (Goal)
and its length is (P) = (s 0 ) + (Goal) + a∈Act (a).

Solutions to simple epistemic planning tasks can be either sequential plans or parallel plans. We focus on the latter in the rest of the chapter.

Parallel Epistemic Planning with EL-O

Parallel Epistemic Planning with EL-O

A parallel plan is a sequence of steps each of which is a set of actions that are executed simultaneously. Actions in a step should not conflict: we start by determining the conditions of parallel executability of a set of actions in a state, following the ∀-step semantics and the notion of interference in a state of [START_REF] Rintanen | Planning as satisfiability: parallel plans and algorithms for plan search[END_REF].

Semantics of a Single Action

We define the semantics of an action a in terms of a partial function τ a on relevant states. The function τ a is defined at s if s |= pre(a). In that case we say that a is executable at s and stipulate:

τa(s) =     s \ ce∈eff (a), s|=cnd(ce) (ceff -(ce)) ⇐     ∪ ce∈eff (a), s|=cnd(ce) (ceff + (ce)) ⇒ .
That is, if the precondition of a is satisfied then a removes negative effects of all those conditional effects ce that 'fire', i.e., whose triggering conditions are satisfied, plus their causes; and it adds the positive effects of ce plus their consequences.

Semantics of a Consistent Set of Actions

We use the same definition of a consistent set of action as before. A set of actions A is say to be consistent in a state s if there is no pair of actions in A with contradictory effects or cross-interaction.

Example 7. Some set of gossiping calls Call i,j can be consistent in any state. Therefore conference calls {Call i,j , Call i,r } where i calls j and r at the same time can be consistent, making the parallel gossiping task solvable in fewer steps.

One way to exclude conference calls is to replace Call i,j by Startcall i j plus a single Endcalls action as follows:

pre(Startcall i j ) = free i ∧ free j , eff (Startcall i j ) = eff (Call i,j ) ∪ {( , ∅, {free i , free j })}, pre(Endcalls) = , eff (Endcalls) = {( , {free i : i ∈ Agt}, ∅)},
and to add all free i to the initial state. Then there is no state where a set of actions with conference calls is consistent: Startcall i j and Startcall i r have cross interaction at any state satisfying free i ∧ free j ∧ free r .

While this solution is natural (agents cannot call two agents at a time because they are no longer available once they have begun a call), splitting calls into two separate actions artificially doubles the number of steps in an optimal solution. Another possibility that avoids the Endcalls action is to replace all Call i,j by Tcall i j , with:

pre(Tcall i j ) = , eff (Tcall i j ) = eff (Call i,j ) ∪ {(tg i , ∅, {tg i })} ∪ {(¬tg i , {tg i }, ∅)} ∪ {(tg j , ∅, {tg j })} ∪ {(¬tg j , {tg j }, ∅)}.
Here any two calls involving i each toggles the value of tg i , which makes that these calls have cross interaction at any state satisfying their preconditions.

A set of actions A = {a 1 , . . . , a m } determines a partial function τ A from R-STATES ⇒ to R-STATES ⇒ , where R-STATES ⇒ = {s ⇒ : s ∈ R-STATES}. The function τ A is defined at s if every a i ∈ A is executable at s and A is consistent in s. When τ A is defined at s then:

τ A (s) =   s \   a∈A,ce∈eff (a),s|=cnd(ce) (ceff -(ce)) ⇐     ∪   a∈A,ce∈eff (a),s|=cnd(ce) (ceff + (ce)) ⇒   .

Translation into Classical Planning and Complexity

When a 1 and a 2 are consistent in s then they can be interleaved arbitrarily: we have τ {a 1 ,a 2 } (s) = τ a 2 (τ a 1 (s)) = τ a 1 (τ a 2 (s)). More generally: Proposition 34. If a ∈ A is consistent in s with any other action in A then τ A (s) = τ a (τ A\a (s)) = τ A\a (τ a (s)).

Solvability by Parallel Plans

A state s is reachable by a parallel plan from a state s 0 ∈ R-STATES ⇒ via a set of actions Act if there is a sequence A 1 , . . . , A m of steps and a sequence of states s 0 , . . . , s m with m ≥ 0 such that s = s m and τ A k (s k-1 ) = s k for every k such that 1 ≤ k ≤ m.

A simple epistemic planning task (Act, s 0 , Goal) is solvable by a parallel plan if there is at least one state s that is reachable by a parallel plan from s ⇒ 0 via Act such that s |= Goal; otherwise it is unsolvable by a parallel plan. Solvability by a sequential plan is the special case where the parallel plan is required to be a sequence of singletons.

Example 8. Let G 1 be modification of G 1 that is obtained by replacing the actions Call i,j by Tcall i j of Example 7. Then G 1 can be solved in log 2 n steps of parallel calls if the number of agents n is even, and in log 2 n + 1 steps if n is odd [START_REF] Bavelas | Communication patterns in task-oriented groups[END_REF][START_REF] Landau | The distribution of completion times for random communication in a task-oriented group[END_REF][START_REF] Knödel | New gossips and telephones[END_REF]Cooper, Herzig, Maffre, Maris, and Régnier 2019). For instance, for n = 4 the parallel plan ({Tcall 1 2 , Tcall 3 4 }, {Tcall 1 3 , Tcall 2 4 }) is a solution of G 1 with 2 steps.

Translation into Classical Planning and Complexity

We now translate simple epistemic planning into classical planning. There, solvability by a parallel plan and by a sequential plan are equivalent under ∀-Step semantics, and both are PSPACE-complete [START_REF] Bylander | The Computational Complexity of Propositional STRIPS Planning[END_REF]. Our translation is polynomial, so the solvability of simple epistemic planning tasks is in PSPACE. It also gives us an encoding into PDDL, which allows us to use classical planners in sections 4.5 and 4.6. For a bounded horizon planning task we can translate into DL-PPA model checking and use the PSPACE membership result of chapter 3.

Two Versions of Classical Planning

There are two possibilities to define classical planning in our context. Version 1 amounts to epistemic planning restricted to the fragment of the language of EL-O without S i and JS: none of them can occur in classical action descriptions and planning tasks. It immediately follows that EL-O-based planning is PSPACE hard because classical planning is so.

Version 2 of classical planning keeps the language of EL-O but changes the semantics by weakening the consistency condition for action descriptions: a version 2 classical planning task is a triple P = (Act, s 0 , Goal) such that for every ce

1 , ce 2 ∈ eff (a), if ceff + (ce 1 ) ∩ ceff -(ce 2 ) = ∅ then pre(a) ∧ cnd(ce 1 ) ∧ cnd(ce 2 ) is unsatisfiable in Classical Propositional Calculus CPC.
We then define the partial functions τ CPC a as follows. First, τ CPC a is defined if s |= CPC pre(a); second, the resulting state is obtained without closing under atomic causes and consequences:

τ CPC a (s) =   s \    ce∈eff (a),s|= CPC cnd(ce) ceff -(ce)       ∪    ce∈eff (a),s|= CPC cnd(ce) ceff + (ce)    .
From there we modify the definitions of consistency of a set of actions and of τ CPC A in a similar manner, removing all atomic causes and consequences of sets and requiring conditions to be satisfied classically. A classical planning task is classically solvable if a goal state is reachable from the initial state via a set of actions Act, with the difference that reachability is now defined in terms of the function τ CPC A .

Expansion of Planning Tasks

Let P = (Act, s 0 , Goal) be a simple epistemic planning task. Its expansion is obtained by closing the initial state and the action descriptions under the

s ⇒ 0 ∩ ATM (P), Goal),
where the expansion of a conditional effect is defined as:

Exp P (eff (a)) = {(cnd(ce), (ceff + (ce)) ⇒ ∩ ATM (P), (ceff -(ce)) ⇐ ∩ ATM (P)) : ce ∈ eff (a)}.
Proposition 35. Let P = (Act, s 0 , Goal) be a simple epistemic planning task. Then P is solvable if and only if its expansion Exp(P) is classically solvable.

Proof. Let

R-STATES|

P = {s ∩ ATM (P) : s ∈ R-STATES ⇒ }.
We define a semantics of actions relative to P in the following manner: if s ∈ R-STATES| P and A = {a 1 , . . . , a m } ⊆ Act is a consistent set of actions then τ P A (s) is defined iff for all a ∈ A we have s |= pre(a), and in that case

τ P A (s) =      s \      a∈A,ce∈eff (a), s|=cnd(ce) (ceff -(ce)) ⇐ ∩ ATM (P)           ∪      a∈A,ce∈eff (a), s|=cnd(ce) (ceff + (ce)) ⇒ ∩ ATM (P)      .
It is easily shown that if s ∈ R-STATES| P and A is consistent in s then τ P A (s) ∈ R-STATES| P . By Proposition 33, for any state s ∈ R-STATES ⇒ and set of actions A ⊆ Act, τ A (s) is defined iff τ P A (s∩ATM (P)) is defined, and in that case τ P A (s∩ATM (P)) = τ A (s) ∩ ATM (P). We can then extend this result to any sequence of steps, i.e., to every parallel plan: for any state s ∈ R-STATES ⇒ , there exists a state s reachable from s via A 1 , . . . , A m iff there exists a state s that is P-reachable from s ∩ ATM (P) via this same sequence of sets of actions, where P-reachability is defined in the natural way following the semantics of actions relative to P, and in that case s = s ∩ ATM (P). In particular s and s agree on Goal, and therefore P is solvable iff the planning task (Act, s ⇒ 0 ∩ ATM (P), Goal) is P-solvable on R-STATES| P , where Psolvability is once again defined in the natural manner following the semantics of actions relative to P.

The expansion of P then 'spells out' the definition of the functions τ P A for A ⊆ Act. Moreover, Proposition 33 tells us that for any ϕ ∈ ATM (P), if s ∈ R-STATES| P then s |= ϕ iff s |= CPC ϕ. This gives us equivalence with classical planning.

Complexity

By Proposition 31, the length of the expansion of epistemic planning tasks P is polynomial in the length of P: (Exp(P)) ≤ ( (P)) 2 . Then PSPACE membership follows from Proposition 35. Hardness is the case because classical planning (version 1) is a particular case of simple epistemic planning, as we have observed in Section 4.4.1.

Proposition 36. The problem of deciding solvability of a simple epistemic planning task and its bounded horizon version are both PSPACE-complete.

Encoding into PDDL

In order to be able to use classical planners we encode simple epistemic planning tasks into the Planning Domain Definition Language PDDL McDermott et al. 1998. Fortunately, almost all planners from the 2018 International Planning Competition (IPC 2018)1 handle conditional effects and negative preconditions, and most of them handle disjunctive preconditions.

Encoding of Formulas

When encoding a planning task into PDDL, some PDDL requirement flags have to be set depending on the form of conditions cnd(ce) of conditional effects ce of actions as well as on the form of the formula Goal:

Encoding into PDDL

• the default flag :strips for conjunctions;

• the flag :negative-preconditions for negations;

• the flag :disjunctive-preconditions for disjunctions (if used to simplify writing) and negations of conjunctions.

For a formula ϕ without introspective atoms, we define a recursive function f (ϕ) which returns the encoding of ϕ into PDDL:

f (S i1 . . . S im p) = (p) if m = 0 (S-m i1 … im p) otherwise f (JS S i1 . . . S im p) = (JS p) if m = 0 (JS-m i1 … im p) otherwise f (¬ϕ) = (not f (ϕ)) f (ϕ 1 ∧ ϕ 2 ) = (and f (ϕ 1 ) f (ϕ 2 ))
with p ∈ P, m ≥ 0, and i 1 , . . . , i m ∈ Agt. In words, a visibility atom α = S The formula Goal and the preconditions of every action are EL-O formulas and are encoded as f (Goal) etc. The initial state s 0 is encoded as a set of fluents, encoding each α ∈ s ⇒ 0 as f (α).

Encoding of Actions

For every action a and every conditional effect ce ∈ eff (a) with (ceff + (ce)) ⇒ ∩ ATM (P) = {α 1 , . . . , α m } and (ceff -(ce)) ⇐ ∩ ATM (P) = {β 1 , . . . , β } we add the conditional effect:

(when f (cnd(ce))

(and f (α 1 ) . . . f (α m ) (not f (β 1 )) . . . (not f (β ))))
Example 9 (Example 4, ctd.). The action Call 1,2 is encoded as:

(:action call-1-2

:effect (and (when (or (S-1 1 s1) (S-1 2 s1)) (and (S-1 1 s1) (S-1 2 s1))) … (when (or (S-1 1 sn) (S-1 2 sn))

(and (S-1 1 sn) (S-1 2 sn)))))

This is the direct encoding of a call into PDDL. It can be generalised to any i and j by:

(:action call :parameters (?i ?j) :effect (and (forall (?s) (and (when (or (S-1 ?i ?s) (S-1 ?j ?s)) (and (S-1 ?i ?s) (S-1 ?j ?s)))))))

Experimental Results

To experiment with simple epistemic planning tasks we considered some benchmark tasks using planners from the international planning competition IPC 2018. The experiments were done using three classical planners of the optimal track of IPC 2018: Planning-PDBs, Complementary1 and Complementary2. We are in a multi-agent setting where agents execute actions simultaneously in steps. We designed our problems so that it is beneficial (in terms of minimising the number of steps) that agents cooperate and perform tasks in parallel. We want to find the shortest plan in which the agents cooperate in this way. For this, we used cost-optimal planners from the classical tracks of the competition. Given a cost function defined for all actions of the planning task, these planners return sequential plans minimizing total cost. To simulate parallel steps and ensure independence of actions in one step, we use in each experiment an EndStep action. That is, we adapt the action descriptions such as to ensure that all actions executed between two EndStep actions are applicable in parallel, and an EndStep action must occur in order to simulate the following parallel step. Moreover, we give zero cost to all actions but EndStep, therefore effectively counting the number of steps and guaranteeing that our experiments return optimal parallel plans.

The experiments all gave similar results for the problems described below, so we choose to show the results for Planning-PDBs. The results were obtained

Experimental Results

on a GNU/Linux machine running on a 3.6 to 4.4 GHz CPU with 32 GB of RAM and a 30 minutes time limit (wall clock time). All the execution times given below are CPU times.

Parallel Gossip Task

We use the gossip modelling of Example 7 with the actions Startcall i j and Endcalls, which here becomes our EndStep.

Figure 4.1 shows the difference between parallel and sequential gossiping. We can see that with only two agents (blue and longest curve) the execution times are very similar but when, for a fixed depth, the number of agents increases then the execution time increases, too. Thus, we have fewer results for parallel gossiping than for sequential gossiping.

The largest parallel gossiping task solved under 1800s was for 5 agents and an epistemic depth of 2. This task has 125 atoms, 26 actions and 1920 conditional effects. For sequential gossiping the largest solved planning task was for 8 agents and an epistemic depth of 1. This task has 56 atoms, 64 actions and 1512 conditional effects.

Management Task

For the next benchmark planning task, we consider that a set of tasks has to be performed by the set of agents and that the execution of any task by an agent requires the agent to have a corresponding skill. In the beginning, the skills are split between the agents so that a particular agent may lack some of the skills required to perform particular tasks. This can limit the ability of the agents to perform tasks in parallel. However, there are also actions which allow agents to teach some of their skills to other agents.

Initially all agents are free and the state is

s 0 = {free i : i ∈ Agt}∪S for some subset S of {S i skill k : i ∈ Agt, k ∈ Skills}∪{needs t,k : t ∈ Tasks, k ∈ Skills}.
The goal is to perform all tasks: Goal = t∈Tasks done t .

The action descriptions are listed in the upper half of Table 4.2. For each pair of agents i,j and skill skill k , the action Teach i,j,k can be executed when i knows the skill she is teaching and is either free or is teaching the same skill to another agent. Its effects are that j knows the skill, that i and j are both no longer free, and that i is still available to teach skill k to other agents. The action DoTask i,t,k requires that i is free and knows skill skill k and that skill k 4.6 Experimental Results is a necessary and sufficient condition to accomplish t. Its effect is that the agent is not free and that the task is done. Finally, the EndStep action frees all agents (regardless of whether they were teaching, learning or performing a task).

Suppose there are n agents, n tasks and one skill skill k that is only known by agent i. Then an optimal parallel plan has two steps: first i teaches skill k to the other agents and then each agent j executes task t j in parallel. In contrast, the optimal sequential plan is that i executes all the tasks herself, which is an n-step plan that cannot be parallelized. Figure 4.2 shows the time needed by Planning-PDBs to find a plan, in seconds. It compares the effect of the number of tasks, the number of agents and the number of skills. The first plot shows the effect of the number of tasks with different fixed values of the number of agents and skills. We can see that this variable has almost no effect on the difficulty to find a plan. The second plot does the same with the number of agents with different fixed values for the number of tasks and skills, while in the third plot the number of skills is the only variable which varies. These latter two plots show that the number of agents and the number of skills have an effect on the complexity. However, we do not have enough values to say more about this relationship.

The number of results were limited by the increasing complexity of the planning task. The most complex planning task for which we found an optimal parallel plan involved 7 tasks, 7 agents and 6 skills: this instance has 92 atoms and 638 actions. The most complex planning task tested and which timed out, had 7 tasks, 7 agents and 7 skills: this instance has 105 atoms and 736 actions.

Remark 2. One may replace Teach i,j,k by the action ReqSkill j,i,k of j asking i to teach her skill skill k . Then we have to add to the precondition that j does not have the skill but knows that i does:

pre(ReqSkill j,i,k ) = pre(Teach i,j,k ) ∧ ¬S j skill k ∧ S j S i skill k .
We note that such a precondition cannot be expressed with epistemic literals of the approach of [START_REF] Muise | Planning Over Multi-Agent Epistemic States: A Classical Planning Approach[END_REF]. effect is that all agents jointly see that the meeting has been held and that the agents are no longer free. Finally, the action EndStep frees the agents and ends the step. For example, with 2 agents and 3 meetings (2 stages), the following is a solution plan: .3 shows the time needed by Planning-PDBs to find a plan, in seconds, relative to the number of meetings, where each plotted curve is for a fixed number of tasks and agents. We can see that the other two parameters (number of tasks and number of agents) have little to no effect on the difficulty of finding an optimal plan. In contrast, the number of meetings seems to have an exponential effect when it is greater than 10.

The largest planning task which was solved within the time limit of 1800s 90

Conclusion

involved 18 tasks, 17 meetings and two agents: this instance has 46 atoms and 16400 actions. The most complex planning tasks that we tested and that timed out had 18 tasks, 18 meetings and one agent: the planners were not able to ground this problem.

Conclusion

We have defined simple epistemic planning tasks and their solvability by a parallel plan and characterised its complexity via a polynomial translation into classical planning. This allows us to solve epistemic bounded horizon planning tasks by translating them to classical bounded horizon planning, which is known to be PSPACE-complete.

Our 'knowing whether'-based language can express more than the 'knowingthat'-based language of [START_REF] Muise | Planning Over Multi-Agent Epistemic States: A Classical Planning Approach[END_REF] (see Remark 2). Contrarily to [START_REF] Kominis | Beliefs In Multiagent Planning: From One Agent to Many[END_REF], we are not restricted to common knowledge of the initial state and public or semi-public actions, as illustrated by the gossiping task where actions are private. Moreover, none of the latter two approaches deals with common knowledge or concurrent actions. Experiments demonstrated the possibility of solving some interesting practical problems.

In future work we plan to use SAT-based planners such as Rintanen et al.'s [START_REF] Rintanen | Planning as satisfiability: parallel plans and algorithms for plan search[END_REF], which output parallel plans and therefore do not require the EndStep action.

Conclusion

This thesis showed, via a running example with several variations, the gossip problem, the interest of adding both temporal and epistemic aspects to a planning problem. These temporal epistemic gossip problems can still be extended. They are one of the simplest temporal epistemic planning problems so they can be used in many different ways. We can have different durations for different calls or make calls non-deterministic: the person we want to call may not be fully available even in allowed time frames; or there might be noise in the transmission altering the communication.

The first step to temporal planning is planning with parallel plans. With that in mind, we added parallelism to a dynamic logic without increasing its complexity. DL-PPA is an interesting basis for a parallel dynamic epistemic logic in PSPACE. The logic it is based on was already extended to an epistemic logic (DEL-PAO) and such work can be used to extend DL-PPA too. There is also some work done with DL-PPA for contingent planning in [START_REF] Scheck | Knowledge Compilation for Action Languages[END_REF].

We also showed how to translate epistemic planning problems from EL-O to PDDL to search for a parallel plan. The work done in Chapter 4 transforms a simple form of epistemic planning to classical planning. This can be combined with approaches such as SATPLAN to translate epistemic planning problems into SAT. The benchmarks in this chapter show that more work can be done to improve the planners for epistemic planning. This approach can also be extended to temporal epistemic planning using existing temporal planners and PDDL 2.1.

All those results can be used to make tools for temporal and epistemic planning. One interesting future work could be to extend EL-O with some temporal aspects to be able to reason about the knowledge of the agents and its variation over time. This could allow one to model loss of knowledge some time after the execution of an action that added it.

An application of planning that I find interesting is about generating stories, for instance, video game scenarios. The actions of the planning tasks could be atomic plot elements. The initial state represents the world at the beginning 5 Conclusion of the game. And the goal of the planning task is chosen so the player has fun playing the game and that some key elements of the scenario happens. However, a player does not act deterministically and could act differently from what the planner expected. On the other and, by modeling wisely the planning task and using replanning whenever the player diverges from the chosen path we may be able to have a scenario that adapts to the actions of the player. With the combination of temporal and epistemic planning, we could generate meaningful and complex stories. The knowledge of the characters can be taken into account as well as the time needed for the player to act and the world to change.

Conclusion en français

Cette thèse a montré, à travers la déclinaison d'un example, le problème du bavardage, l'intérêt d'ajouter des aspects temporels et épistémiques à un problème de planification. Ces problèmes de bavardage temporels et épistémiques peuvent encore être étendus. Puisque ils constituent l'un des problèmes de planification épistémique temporelle les plus simples, ils peuvent être utilisés de différentes manières. Nous pouvons avoir différentes durées pour différents appels ou rendre les appels non déterministes : la personne que nous voulons appeler peut ne pas être totalement disponible, même dans les intervales de temps spécifiés, ou bien il peut y avoir du bruit dans le système de communication.

La première étape vers la planification temporelle est la planification avec des plans parallèles. Dans cette optique, nous avons ajouté le parallélisme à une logique dynamique sans en augmenter la complexité. DL-PPA est une base intéressante pour une logique épistémique dynamique parallèle dans PSPACE. La logique sur laquelle elle est basée a déjà été étendue vers une logique épistémique (DEL-PAO) et un tel travail peut être utilisé pour étendre DL-PPA également. Il existe également des travaux réalisés avec DL-PPA pour la planification contingente dans [START_REF] Scheck | Knowledge Compilation for Action Languages[END_REF].

Nous avons aussi montré comment traduire les problèmes de planification épistémique de EL-O vers PDDL pour rechercher un plan solution parallèle. Le travail effectué dans le chapitre 4 transforme une forme simple de planification épistémique en planification classique. Ceci peut être combiné avec des approches telles que SATPLAN pour traduire les problèmes de planification épistémique en SAT. Les tests de performance de ce chapitre montrent qu'il est possible d'améliorer les planificateurs pour la planification épistémique. Cette approche peut également être étendue à la planification épistémique temporelle en utilisant les planificateurs temporels existants et PDDL 2.1.

Tous ces résultats peuvent être utilisés pour créer des outils de planification temporelle et épistémique. Un travail futur intéressant pourrait être d'étendre EL-O avec certains aspects temporels pour pouvoir raisonner sur la connaissance des agents et sa variation dans le temps. Cela pourrait permettre de modéliser la perte de connaissances un certain temps après l'exécution d'une action qui l'a ajoutée.

Une application de la planification que je trouve intéressante concerne la génération d'histoires, par exemple, des scénarios de jeux vidéo. Les actions des tâches de planification pourraient être des éléments atomiques de l'intrigue. L'état initial représente le monde au début du jeu. Et l'objectif de la tâche de planification est choisi pour que le joueur s'amuse en jouant le jeu et que certains éléments clés du scénario se produisent. Cependant, le joueur n'agit pas de façon déterministe et peut agir différemment de ce que le planificateur a prévu. D'un autre côté, en modélisant judicieusement la planification et en utilisant la replanification chaque fois que le joueur s'écarte du chemin chemin choisi, nous pouvons avoir un scénario qui s'adapte aux actions du joueur. Avec la combinaison de la planification temporelle et épistémique, nous pourrions générer des histoires intéressantes et complexes. Les connaissances des personnages peuvent être prises en compte, ainsi que le temps nécessaire pour que le joueur agisse et le monde change.

Les problèmes de planification multi-agents avec un raisonnement sur la connaissance des agents, appelé raisonnement épistémique, on déjà été bien étudiés. Il en est de même pour les problèmes avec des actions temporellement étendues. Cependant, les problèmes incluant à la fois raisonnement épistémique et temporel n'ont pas bénéficié d'autant d'attention. Nous considérons que la combinaison de ces aspects est nécessaire pour pouvoir pleinement représenter des problèmes que l'on rencontre dans le monde réel. C'est pourquoi nous avons cherché à les associer pour étendre les possibilités de planification.

Cette thèse présente plusieurs contributions à la planification multi-agent, temporelle et épistémique. Pour en montrer l'intérêt, nous avons créé et étudié une variante du problème du bavardage incluant des contraintes temporelles. Nous avons appelé cette famille de problèmes « temporal epistemic gossip problems » (problèmes de bavardage temporels et épistémiques). Nous montrons que le problème de l'existence d'un plan pour cette famille est NP-complet.

Étendre une logique épistémique pour lui permettre de représenter également des problèmes temporels pourrait vite mener à une complexité importante. Nous avons choisi de commencer en ajoutant du parallélisme à la logique dynamique d'assignations propositionnelles (dynamic logic of propositional assigments, DL-PA) pour créer la logique dynamique d'assignations propositionnelles parallèles (dynamic logic of parallel propositional assignments, DL-PPA), tout en conservant la complexité PSPACE-complète des problèmes de satisfiabilité et de vérification de modèle.

Nous avons ensuite tenté une autre approche, traduire un problème de planification épistémique en problème de planification classique. Le problème de planification est décrit dans une logique statique, EL-O, en définissant le problème d'existence de plan dans le méta-langage. Nous montrons que ces problèmes sont dans PSPACE via une traduction polynomiale de la planification épistémique avec EL-O vers de la planification classique. Dans le même esprit, en se basant sur notre modèle de planification épistémique nous avons créé des domaines et problèmes PDDL. Nous avons testé ces problèmes avec des planificateurs de la compétition internationale de planification (IPC) de 2018 afin de connaitre le temps nécessaire pour obtenir une solution. La comparaison des problèmes de chaque domaine nous a montré que les planificateurs actuels ne sont pas assez performants pour traiter des problèmes épistémiques avec cette approche.

Multi-agent planning problems involving reasoning over the agents' knowledge are well studied. The same is the case for problems with temporally extended actions. However, problems with both epistemic and temporal reasoning drew less attention. We consider that the combination of these two aspects is essential to fully model real world problems. That is why we wanted to combine them to extend the possibilities of planning.

This thesis contains several contributions to multi-agent, temporal and epistemic planning. To motivate such an enterprise, we designed and studied a variation of the gossip problem with temporal constraints. We called this family of problems "temporal epistemic gossip problems". We show that the solvability problem for this family is NP-complete.

Extending an epistemic logic in order to enable the modeling of temporal problems into classical planning problems may lead to a high complexity. We choose to start by adding parallelism to dynamic logic of propositional assignments (DL-PA), resulting in dynamic logic of parallel propositional assignments (DL-PPA), while keeping the PSPACE-complexity of the satisfiability and model-checking problems.

We then tried another approach, namely to translate epistemic planning problems into classical planning problems. The planning problem is first modeled in a static logic, EL-O, defining solvability in the metalangage. We show that these problem are in PSPACE via a polynomial translation from EL-O epistemic planning to classical planning. By means of this translation we created some domains and problems in PDDL. These problems were tested with planners from the international planning competition (IPC 2018) to retrieve the amount of time for a solution. The comparison between the problems of each domain showed that more research on epistemic planning is needed.

  Figure 1.1: PDDL 2.1 actionThe top line represents the preconditions, the middle one the action a and the bottom one the effects. The horizontal axis represents the time. The letters are s for "at-start", e for "at-end" and o for "over-all" (over the entire duration).

2. 1

 1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.2 Membership in NP . . . . . . . . . . . . . . . . . . . . . . . . 29 2.3 A subproblem of the temporal gossip problem in P . . . . . . 29 2.4 NP-completeness when execution time is bounded . . . . . . 30 2.5 NP-completeness of gossiping with negative goals . . . . . . . 36 2.6 Discussion and conclusion . . . . . . . . . . . . . . . . . . . . 38

Figure 2 . 1 :

 21 Figure 2.1: Call graph for Example 1 involving necessary calls with e. Adouble-ended arrow represents two directed edges (i.e., the possibility of one-way calls in both directions). The tuples on the arcs represents the subsets of I p and I n for the calls from agent i (at the beginning of the arc) to j (at the end of the arc). If there is no arc from i to j, then no call is possible from i to j.

Figure 2 . 3 :

 23 Figure 2.3: Representation of the formula (¬x ∨ y ∨ z) ∧ (¬y ∨ z) as a temporalepistemic gossip problem in which the question is whether there is a parallel plan using no more than 14 steps.

Figure 2 . 4 :

 24 Figure 2.4: (a) gadget imposing the clause C j = ¬x ∨ y ∨ z; (b) gadget imposing the choice between x and ¬x.

3. 1

 1 DL-PA and DL-PPA . . . . . . . . . . . . . . . . . . . . . . . . 42 3.1.1 Language . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.1.2 Semantics of DL-PPA . . . . . . . . . . . . . . . . . . . 43 3.1.3 Counters . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.2 Reduction from DL-PPA to DL-PA . . . . . . . . . . . . . . . 47 3.2.1 Auxiliary variables . . . . . . . . . . . . . . . . . . . . 47 3.2.2 Programs and formulas used in the translation . . . . 48 3.2.3 The translation . . . . . . . . . . . . . . . . . . . . . . 49 3.2.4 Correctness of the translation . . . . . . . . . . . . . . 51 3.2.5 Complexity results . . . . . . . . . . . . . . . . . . . . 60 3 Dynamic Logic of Parallel Propositional Assignments 3.3 DL-PPA applied to automated planning . . . . . . . . . . . . 61 3.3.1 Sequential planning with conditional effects . . . . . . 61 3.3.2 Parallel planning with conditional effects . . . . . . . 63 3.3.3 Solvability of bounded horizon planning tasks . . . . . 64 3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

3. 1

 1 DL-PA and DL-PPA Our Dynamic Logic of Parallel Propositional Assignments DL-PPA extends Dynamic Logic of Propositional Assignments DL-PA by two program operators: an operator of parallel composition and a new operator of nondeterministic composition . The distinction between

4. 1

 1 EL-O: Epistemic Logic of Observation . . . . . . . . . . . . . 71 4.1.1 Atoms and Introspective Atoms . . . . . . . . . . . . . 71 67

  is a finite state (the initial state) and• τ : Act × R-STATES → R-STATES is a partial function modeling theactions in Act which is a finite set of consistent actions, and• Goal ∈ R-Fml EL-O is an EL-O formula without introspective atoms.

4. 4

 4 Translation into Classical Planning and Complexity atomic causes and consequences that are relevant for P: Exp(P) = ({(pre(a), Exp P (eff (a))) : (pre(a), eff (a)) ∈ Act},

  i 1 . . . S im p is encoded by a special fluent with m+1 parameters. If m = 0, then the propositional variable p is encoded as a fluent without parameters. A visibility atom α = JS S i 1 . . . S im p is encoded by a special fluent with m+1 parameters. If m = 0 then a special fluent is encoded with the propositional variable p as unique parameter.

Figure 4 . 2 :

 42 Figure 4.2: Management: time to find an optimal parallel plan vs. number of tasks, agents or skills (for different fixed values of the two other parameters)

Figure 4 .

 4 Figure 4.3: Meetings: time to find an optimal parallel plan vs. number of meetings (for different fixed numbers of tasks and agents)

{DoMeeting 1 }

 1 , {EndStep}, {DoTask 1,1,1 , DoTask 2,2,1 }, {EndStep}, {DoMeeting 2 }, {EndStep}, {DoTask 1,3,2 , DoTask 2,4,2 }, {EndStep}, {DoMeeting 3 } .

Figure 4

 4 Figure 4.3 shows the time needed by Planning-PDBs to find a plan, in seconds, relative to the number of meetings, where each plotted curve is for a fixed number of tasks and agents. We can see that the other two parameters (number of tasks and number of agents) have little to no effect on the difficulty of finding an optimal plan. In contrast, the number of meetings seems to have an exponential effect when it is greater than 10.The largest planning task which was solved within the time limit of 1800s

  Let m be the number of clauses in the CNF of the goal. Let d be the the depth of atoms for the problem. If a plan for an instance of a TEGP exists, then there is a plan with md(n -1) + |I n | calls or less Proof. Let α ∈ ATM be an atom. S i α can only be true if there is a path in the graph G between i and some agent who knows α. Without loss of generality, we can assume that this path is cycle-free. The length of this path is at most n -1. Then, for any atom with an epistemic depth d, at most

	2.2 Membership in NP
	2.2 Membership in NP
	Proposition 1.

d(n -1

) calls are needed for this atom to be true, by the concatenation of d paths of length n -1.

Table 3 .

 3 3: Translation from DL-PPA to DL-PA 3.2 Reduction from DL-PPA to DL-PA

	For example, f (p←	p←⊥) is
	(p) 1 ←p; (p) 2 ←p; δ (p) 1 ←⊥; δ (p) 2 ←⊥;

τ can be generalized to τ : Act ×

S → 2 S to have incomplete knowledge about the initial state and non deterministic actions.

The calls are actions without preconditions, so the goal is the only formula that has to be true in these problems.

https://ipc2018-classical.bitbucket.io/

Remerciements

Bibliography

Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden. Ed. by J. Lang. ijcai.org, pp. 4780-4786. isbn: 978-0-9992411-2-7. doi: 10.24963/ijcai.2018/664. url: https://doi.org/10.24963/ijcai.2018/664. Cooper, Martin C., Andreas Herzig, Faustine Maffre, Frédéric Maris, Elise Perrotin, and Pierre Régnier (2019). "A Lightweight Epistemic Logic and its Application to Planning." In: AI Journal. submitted. Cooper, Martin C., Andreas Herzig, Faustine Maffre, Frédéric Maris, and Pierre Régnier (2016a). "A Simple Account of Multi-Agent Epistemic Planning." In: ECAI 2016 -22nd European Conference on Artificial Intelligence, 29 August-2 September 2016, The Hague, The Netherlands -Including Prestigious Applications of Artificial Intelligence (PAIS 2016). Ed. by Gal A. Kaminka, Maria Fox, Paolo Bouquet, Eyke Hüllermeier, Virginia Dignum, Frank Dignum, and Frank van Harmelen. Vol. 285. Frontiers in Artificial Intelligence and Applications. IOS Press, pp. 193-201. isbn: 978-1-61499-671-2. doi: 10.3233/978-1-61499-672-9-193. url: https://doi.org/10.3233/978-1-61499-672-9-193. -(2016b). "Simple Epistemic Planning: Generalised Gossiping." In: ECAI 2016 -22nd European Conference on Artificial Intelligence, 29 August-2 September 2016, The Hague, The Netherlands -Including Prestigious Applications of Artificial Intelligence (PAIS 2016). Ed. by Gal A. Kaminka, Maria Fox, Paolo Bouquet, Eyke Hüllermeier, Virginia Dignum, Frank Dignum, and Frank van Harmelen. Vol. 285. Frontiers in Artificial Intelligence and Applications. IOS Press, pp. 1563-1564. doi: 10.3233/978-1-61499-672-9-1563. arXiv: 1606.03244. -(2016c). "Simple epistemic planning: generalised gossiping." In: CoRR abs/1606.03244. url: http://arxiv.org/abs/1606.03244. -(2019). "The epistemic gossip problem." In: Discrete Mathematics 342.3, pp. 654-663. doi: 10.1016/j.disc.2018.10.041. url: https://doi. org/10.1016/j.disc.2018.10.041. Cooper, Martin C., Andreas Herzig, Frédéric Maris, Elise Perrotin, and Julien Vianey (Sept. 2020). "Lightweight Parallel Multi-Agent Epistemic Planning." In: Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, pp. 274-283. doi: 10.24963/ kr.2020/28. url: https://doi.org/10.24963/kr.2020/28. Cooper, Martin C., Andreas Herzig, Frédéric Maris, and Julien Vianey (2018).

"Temporal Epistemic Gossip Problems." In: Multi-Agent Systems -16th

When the variables of π 1 and π 2 are disjoint then they can be sequentialised: Proposition 9. Let π 1 and π 2 be two programs such that P π 1 ∩ P π 2 = ∅. Then π 1 π 2 = π 1 ; π 2 = π 2 ; π 1 .

Observe that Proposition 9 cannot be strengthened by only requiring that the variables that are assigned by π 1 and π 2 are disjoint. For example, the sets of valuations p← q←p and p← ; q←p are different. Just as in DL-PA [START_REF] Balbiani | DL-PA and DCL-PC: model checking and satisfiability problem are indeed in PSPACE[END_REF], the Kleene star can be eliminated in DL-PPA: intuitively, when there exists a run of π * going from x to y then it is possible to go from x to y in no more than 2 |Pπ| iterations of π. (Indeed, if there is a longer run, it necessarily goes through the same valuation twice and can be shortened.) Proposition 10. For all DL-PPA programs π, π * = π ≤2 |Pπ | .

The above result can be strengthened: one might replace |P π | with the number of atomic programs appearing in π; even better, one might replace it with the number of distinct variables appearing on the left-hand side of assignments of π. For instance, p←q∨r * can then be reduced to p←q∨r ≤2 instead of p←q∨r ≤8 .

Counters

In DL-PA one can implement k-bit counters (see e.g. [START_REF] Balbiani | Dynamic Logic of Propositional Assignments: A Well-Behaved Variant of PDL[END_REF], Section II.C)), and this transfers to DL-PPA. The encoding of a binary number of length k requires a vector of log k propositional variables. We represent the state of the counter by a formula ct, which stands for the conjunction of these log k variables or negations thereof. Furthermore we use the following abbreviations:

• ct←0 is a program that resets ct: all variables of the counter are set to false;

• For every integer i, ct=i is a formula that is true if and only if the value encoded by ct is i;

• ct++ increments the value of ct.

3 Dynamic Logic of Parallel Propositional Assignments this guarantees that their truth was caused by an assignment of (p) i that was performed during the execution of (π i ) i . Without such an initialisation for example the translation of f ( p← ? ) would be sensitive to the original truth value of δ (p) 2 : it would be true in the empty valuation and false in the valuation {δ (p) 2 }.

Let U and U agree on P π ∪δ Pπ . If V and V agree on P ⊆ P and P ∩ CP(π) = ∅ then U and U agree on P .

Proof. The only variables that f (π) can modify are in P π ∪δ Pπ ∪CP(π). Suppose both (V , U ) and (V , U ) are in f (π) DL-PA and P and CP(π) are disjoint. Then f (π) cannot modify the variables in P \ (P π ∪δ Pπ ), and U and V must agree on P \ (P π ∪δ Pπ ). For the same reason, U and V must agree on P \ (P π ∪δ Pπ ). As V and V agree on P , they trivially also agree on P \ (P π ∪δ Pπ ), and we get by transitivity of equality that U and U agree on P \ (P π ∪δ Pπ ). As by hypothesis U and U agree on P π ∪δ Pπ , they agree on the entire set P .

The next lemma says that only the surface variables matter when interpreting translated formulas and programs.

Lemma 18. For all formulas ϕ and programs π:

1. If V and V agree on P ϕ ∪δ Pϕ and V ∈ f (ϕ) DL-PA then V ∈ f (ϕ) DL-PA ; 2. If V and V agree on P π ∪δ Pπ and (V , U ) ∈ f (π) DL-PA then there is a U agreeing with U on P π ∪δ Pπ such that (V , U ) ∈ f (π) DL-PA .

Proof. The proof is by simultaneous induction on the form of ϕ and π and uses Lemma 17. Instead of the second item we use as induction hypothesis that if V and V agree on P π ∪δ Pπ and (V ,

). We abbreviate that induction hypothesis by IH2, while IH1 denotes the first item in the statement of the lemma.

• For the case of formulas of the form π ϕ, to prove IH1 suppose V and V agree on P π ϕ ∪δ P π ϕ and V ∈ f ( π ϕ) DL-PA . By the truth condition there is a

. By construction U agrees with U on P f (π) and therefore also on P π ∪δ Pπ . Lemma 17 applies for P = P ϕ ∪ δ Pϕ because the auxiliary variables in CP(π) are fresh: U and U agree on P = P ϕ ∪δ Pϕ . This allows us to apply IH1, giving us U ∈ f (ϕ) DL-PA . By the truth condition for the dynamic operator it follows that V ∈ f ( π ϕ) DL-PA .

• The other cases of formulas are straightforward.

• For the case of assignments, to prove IH2 suppose V and V agree on

• For the case of sequential composition, suppose V and V agree on

). Clearly, U 1 and U 1 agree on P π 1 ∪δ Pπ 1 . By Lemma 17 (which applies because the auxiliary variables in CP(π 1 ) are fresh) they also agree on P π 2 ∪δ Pπ 2 . This allows us to apply IH1, giving us

• The cases of exclusive nondeterministic composition and of finite iteration are straightforward.

• The cases of parallel composition and of inclusive nondeterministic composition are similar to that of sequential composition but a bit 3.2 Reduction from DL-PPA to DL-PA

For programs, the cases of parallel compositions and inclusive nondeterministic compositions rely on Lemma 16: in their translation, the only modifications of change-recording variables δ p are by assignments of the form δ p ←δ p ∨ δ (p) 1 ∨ δ (p) 2 which never make any δ p variable false.

The last two lemmas entail that only the variables in P ϕ are relevant for the interpretation of f (ϕ).

Lemma 20. For every formula ϕ,

Proof. We prove that if V and V agree on P ϕ and V ∈ f (ϕ) DL-PA then V ∈ f (ϕ) DL-PA . Suppose V and V agree on P ϕ and V ∈ f (ϕ) DL-PA . We split V up into three disjoint sets and get:

Then Lemma 19 (first item) tells us that the change-recording variables don't matter when interpreting formulas, therefore:

Finally, as this valuation agrees with V on the surface variables P ϕ ∪ δ Pϕ , by Lemma 18 (first item) we get that V ∈ f (ϕ) DL-PA .

The above lemmas are used in the grande finale: Theorem 21. For every formula ϕ, ϕ = f (ϕ) DL-PA .

Proof. We prove by simultaneous induction on the form of formulas and programs:

• The other cases of formulas are straightforward.

• For the case of assignments, to prove IH2 suppose (V , U , W ) ∈ p←ϕ . We distinguish two subcases.

we have X = ∅. The subcase where V / ∈ ϕ DL-PA is similar.

To prove IH3 suppose (V , U ) ∈ f (p←ϕ) DL-PA . We again distinguish two subcases.

Then by IH1 we get V ∩P ϕ ∈ ϕ DL-PA . Hence V ∩P p←ϕ ∈ ϕ DL-PA , too, as well as

The subcase where V / ∈ f (ϕ) DL-PA is similar.

• For the case of tests, to prove IH2 suppose (V , U , W ) ∈ ϕ? . Then V ∈ ϕ , U = V , and W = ∅. By Proposition 8 we have V ∩P ϕ ∈ ϕ , and by IH1 we have

• For the case of sequential compositions, to prove IH2 suppose (V , U , W ) ∈ π 1 ; π 2 . Then there are

Applying IH2 twice we get

for some X 1 ⊆ CP(π 1 ) and X 2 ⊆ CP(π 2 ). Adding irrelevant variables as we did for the previous cases we get

By Lemma 19 we can add the change-recording variables δ W 1 to the interpretation of f (π 2 ) and get

As the valuations

on the surface variables of f (π 2 ) we can apply Lemma 18 and get

for some U agreeing with

for some X ⊆ P; more precisely, X ⊆ X 1 ∪ X 2 . Finally, together with the above

we obtain

To prove IH3 suppose (V , U ) ∈ f (π 1 ; π 2 ) DL-PA . Then there is a U 1 such that (V , U 1 ) ∈ f (π 1 ) DL-PA and (U 1 , U ) ∈ f (π 2 ) DL-PA . Applying IH3 twice we get

for some W 1 and W 2 . Adding irrelevant variables as we did for the previous cases we get

Putting this together we obtain

• The case of exclusive nondeterministic composition is straightforward.

• The case of finite iteration derives from the cases of exclusive nondeterministic composition and of sequential composition.

• The case of parallel composition relies on sequential composition and uses Proposition 12.

This ends the proof.

Complexity results

We use the translation in order to establish complexity upper bounds. Lower bounds are imported from the fragment DL-PA.

The translation from DL-PPA to DL-PA is a polynomial transformation:

Proposition 22. The length (f (ϕ)) of the translation of a DL-PPA formula ϕ is polynomial in the length (ϕ) of ϕ.

Theorem 23. The DL-PPA model checking problem of deciding, given V and ϕ, whether V ∈ ϕ is PSPACE-complete.

Proof. The lower bound is due to PSPACE hardness of DL-PA model checking [START_REF] Herzig | A Dynamic Logic of Normative Systems[END_REF]. The upper bound is obtained by Theorem 21 and Proposition 22 thanks to PSPACE membership of DL-PA [START_REF] Balbiani | DL-PA and DCL-PC: model checking and satisfiability problem are indeed in PSPACE[END_REF].

To establish the complexity of satisfiability checking we reduce it polynomially to model checking.

Theorem 25. The DL-PPA satisfiability checking problem is PSPACEcomplete.

EL-O: Epistemic Logic of Observation

We recall the Epistemic Logic of Observation, abbreviated EL-O.

Atoms and Introspective Atoms

Let P be a countable set of propositional variables and let Agt be a finite set of agents. The set of observability operators is

where S i stands for individual visibility of agent i and JS stands for joint visibility of all agents. The set of all sequences of visibility operators of length at most k is noted OBS ≤k . Then OBS * = k≥0 OBS ≤k and OBS + = k≥1 OBS ≤k . Atoms are finite sequences of visibility operators followed by a propositional variable. The set of all atoms is

We use α, α , β,…to denote atoms.

The set of all introspective atoms is

The complement of I -Atm is the set of relevant atoms: R-Atm = ATM \I -Atm.

Atomic Consequence

We define a relation of atomic consequence between visibility atoms as follows: α ⇒ β if either α = β, or α = JS α and β = σ α for some σ ∈ OBS + . For example, JS p ⇒ S i p and JS p ⇒ JS S i p. The relation ⇒ is reflexive and transitive. When α ⇒ β, we say that α is a cause of β and that β is a consequence of α. We will ensure that atomic consequences are valid implications. We note α ⇐ the set of causes of α, and α ⇒ the set of its consequences. Clearly, (p) ⇒ = (p) ⇐ = {p} for p ∈ P. Moreover, (S i p) ⇒ = {S i p}, (S i p) ⇐ = {S i p, JS p}, (JS p) ⇒ = {σ p : σ ∈ OBS + }, and (JS p) ⇐ = {JS p}. Observe that α ⇐ is always finite while α ⇒ is either infinite (namely 4 Making Parallel Classical Planning Epistemic

Experimental Results

DoTask

Meetings Task

As an example of the use of common knowledge, consider a planning task which involves cooperation between different agents and which can be divided into m different stages with tasks to be performed at each step by each agent. Agents are only authorized to start stage +1 if all tasks of stage have been completed and all agents have common knowledge of this. The only way this can be achieved is by having a plenary meeting at the end of each stage during which each agent announces that their stage-task has been completed (action DoMeeting ). Initially all agents are free and no meeting or task has been completed: s 0 = {free i : i ∈ Agt}. The goal is for all tasks and meetings to be completed: Goal = t∈Tasks tdone t ∧ ∈Meetings mdone .

The action descriptions are listed in the lower half of Table 4.2. Each stage-task requires that the agent executing it knows that meeting has taken place. To avoid having stage-tasks done at stage-for > , the task also requires the meeting +1 not to have taken place yet. The action DoMeeting of holding a meeting is executable if all the agents are free. Its