RESUMÉ

La planification de chemin consiste à concevoir une séquence d'étapes à suivre pour une entité mobile. Cette tâche est au coeur de nombreux problèmes du monde réel. La planification est utilisée dans les problèmes d'optimisation pour les trains, dans l'aviation et même pour analyser/concevoir les intersections routières. En outre, l'utilisation récente de véhicules autonomes a accru le besoin de planification, notamment pour les robots d'entrepôt, les véhicules de remorquage d'avions, les robots de bureau, les véhicules portuaires autonomes, ou même pour les entités virtuelles de jeux vidéo. De plus, la planification peut garantir de nombreuses propriétés comme l'optimalité, l'absence de collisions, la connectivité périodique/continue ou la préservation d'une formation. L'étude de la planification autonome peut permettre de réduire la congestion, la pollution, les accidents, les coûts et plus encore.

Dans certaines applications, il est important de considérer la connectivité des agents. Bien que certaines configurations garantissent une connectivité permanente entre les entités (ex : entrepôts), ce n'est pas toujours le cas dans les applications avec des environnements ouverts. Prenons l'exemple des missions de collecte d'informations, au cours desquelles les agents doivent visiter un ensemble de lieux et recueillir des informations à l'aide de capteurs (e.g. des caméras, des capteurs de fumée, des hygromètres, etc.) Une exigence commune de ces missions est d'obtenir un flux vidéo en direct, ce qui ne peut être assuré que par une connectivité permanente. Cette exigence peut être critique dans des contextes spécifiques tels que les missions de recherche et de sauvetage, où la communication entre les agents dépend de la topologie de la zone (e.g. les bâtiments, les arbres) et où elle est nécessaire pour assurer une visite appropriée de la zone, ou pour transférer les informations recueillies à une station de base.

Un autre aspect que l'on retrouve dans de nombreuses applications est le manque de la connaissance complète de la zone dans laquelle les entités se déplacent. Par exemple, dans les missions d'exploration, les agents ne reçoivent aucune information sur l'environnement et doivent le découvrir par eux-mêmes. Dans ce contexte, les agents peuvent être amenés à assurer une connectivité à tout moment pour échanger leurs résultats et, en cas de déconnexion, ils devront se rechercher pour se reconnecter.

Les travaux récents sur la planification des entités se sont concentrés sur la planification d'exécutions sans collision. Ce problème, appelé Multi-Agent Path Finding (MAPF), consiste à trouver une séquence d'étapes pour qu'un groupe d'agents atteigne des cibles spécifiées tout en évitant les collisions. Cette thèse étudie deux aspects de la planification de chemins multi-agents afin de modéliser et de résoudre des applications plus réalistes : (1) la connectivité généralisée des agents ; (2) la connaissance incomplète de l'environnement.

De nombreux travaux sur la planification des chemins et la planification de couvertures supposent un modèle de graphe discret donné obtenu par décomposition cellulaire ou graphe de visibilité, ou utilisent une méthode d'échantillonnage pour construire un graphe sur lequel des algorithmes combinatoires sont appliqués. Les algorithmes basés sur les graphes, tels que ceux que nous étudions, et les travaux antérieurs tels que A* pour MAPF sont donc pertinents dans ce contexte.

Il est important de comprendre la complexité computationnelle de ces problèmes de graphes pour connaître les limites des solutions algorithmiques ainsi que les heuristiques qui peuvent être appliquées au problème en question. La contribution de ce travail est double. Tout d'abord, nous présentons un cadre pour étudier et modéliser les problèmes de planification de chemins multi-agents basés sur la connectivité. Nous fournissons un travail initial détaillé sur la complexité de ce cadre et un algorithme optimal pour le résoudre. Deuxièmement, nous étendons notre cadre de connectivité au cadre de connaissance incomplète et montrons la complexité du calcul connecté et décentralisé des plans dans des environnements partiellement connus.

Tout d'abord, nous abordons le problème de la connectivité, appelé Connected Multi-Agent Path Finding (MAPF). Bien que des travaux initiaux aient été effectués pour formaliser un cadre de communication basé sur l'environnement, nous avons étudié ce problème en détail sous deux objectifs différents, l'accessibilité et la couverture. Le premier problème consiste à rechercher une séquence d'étapes pour qu'un groupe d'agents navigue dans un environnement pour atteindre un emplacement spécifique. Le second problème consiste à trouver une exécution pour une flotte afin de couvrir tous les emplacements d'une zone. Un aspect important de ces problèmes est de savoir si on nous donne une limite sur le nombre d'étapes dans lesquelles les agents doivent atteindre leurs objectifs. Il est intéressant de noter que ces problèmes se comportent différemment selon la classe d'instance. En particulier, nous montrons la difficulté de ces problèmes en général et les restrictions possibles qui les rendent traitables. En outre, nous présentons la complexité de certaines variantes simples qui peuvent être déduites des preuves. Nos résultats montrent que les problèmes de recherche de chemin ou de couverture sont intraitables que l'exécution soit bornée ou non, NP-complet et PSPACE-complet respectivement. Cependant, décider de l'existence d'un plan peut devenir plus facile sous certaines hypothèses, surtout si l'on se restreint aux graphes sight-moveable. En effet, avec cette classe, qui restreint la communication aux emplacements assurant un chemin connecté, les problèmes sont LOG-SPACE ou NLOGSPACE. Cependant, nous avons montré que l'optimisation d'une exécution est un problème difficile à moins de se restreindre à des classes irréalistes.

Ensuite, nous illustrons et analysons un algorithme optimal pour résoudre CMAPF. Certains algorithmes ont été proposés précédemment : un algorithme en ligne et deux algorithmes d'approximation. Contrairement aux approches précédentes, la structure de notre algorithme est basée sur CBS, et nous prouvons son optimalité et sa correction. L'approche est découplée, un algorithme de bas niveau recherche un chemin pour chaque agent, tandis qu'un algorithme de haut niveau contraint les agents pour assurer la connectivité. Nous discutons de certaines optimisations, et nous fournissons une étude expérimentale de son passage à l'échelle.

Nous présentons un cadre pour la connaissance incomplète prenant en compte la connectivité. Nous utilisons le cadre de communication de la première contribution, et limitons notre étude au problème de l'accessibilité. La connaissance incomplète de l'environnement fait référence au fait que certains mouvements ou communications ne sont pas assurés. Ainsi, même si l'environnement est statique, les agents vont observer de nouvelles informations lors de leur exploration. Dans ce cas, il est important de distinguer deux problèmes. Premièrement, le cas connecté qui impose aux agents de rester connectés à toutes les étapes. Dans ce cas, les agents doivent s'assurer qu'une communication incertaine ne perturbera pas l'exécution. Cependant, les agents partagent la même connaissance à tout moment puisqu'ils s'informent mutuellement de leurs résultats. Le deuxième problème, le cas décentralisé, laisse les agents se déconnecter pendant la mission. Comme les agents ne peuvent pas partager leurs connaissances à tout moment, ils doivent raisonner sur les observations possibles des autres et leurs choix.

Cette différence est un indice de l'explication du "saut" conséquent en complexité entre le cas connecté et le cas décentralisé. Nos résultats montrent que la distinction intuitive entre le cas décentralisé et le cas connecté a un impact majeur sur la complexité du problème. En effet, le cas connecté est PSPACE-complet et le cas décentralisé est NEXPTIME-complet. Dans le cadre général des graphes dirigés, l'ajout d'une borne sur l'exécution n'a aucun impact sur la complexité. Cependant, sur les graphes non orientés, il est trivial de trouver une exécution non bornée, car les agents peuvent explorer toutes les configurations jusqu'à ce qu'ils atteignent le but ou découvrent qu'il est impossible de le faire.

INTRODUCTION

Path planning is the task of designing a sequence of steps for a mobile entity to follow. This task is required at the center of numerous real-world problems. Planning is used in optimization problems for trains [START_REF] Ghoseiri | A multiobjective train scheduling model and solution[END_REF], in aviation [START_REF] Pallottino | Decentralized Cooperative Policy for Conflict Resolution in Multivehicle Systems[END_REF] and even in the analysis/design of road intersections [START_REF] Dresner | A Multiagent Approach to Autonomous Intersection Management[END_REF]. In addition, the recent use of autonomous vehicles has increased the need for planning, namely for warehouse robots [START_REF] Peter | Coordinating Hundreds of Cooperative, Autonomous Vehicles in Warehouses[END_REF], aircraft-towing vehicles [START_REF] Morris | Planning, Scheduling and Monitoring for Airport Surface Operations[END_REF], office robots [START_REF] Veloso | CoBots: Robust Symbiotic Autonomous Mobile Service Robots[END_REF], autonomous port vehicles [START_REF] Thurston | Distributed agent architecture for port automation[END_REF], or even for virtual entities as in video-games [START_REF] Ma | Feasibility Study: Moving Non-Homogeneous Teams in Congested Video Game Environments[END_REF]. Additionally, planning of agents can guarantee many properties as optimality and lack of collisions [START_REF] Sharon | Conflict-based search for optimal multi-agent pathfinding[END_REF], periodic/continuous connectivity [START_REF] Hollinger | Multirobot Coordination With Periodic Connectivity: Theory and Experiments[END_REF] or preservation of a formation [START_REF] Li | Moving agents in formation in congested environments[END_REF]. The study of autonomous planning can allow one to reduce congestion, pollution, accidents, costs and more.

In some applications, it is important to consider the connectivity of the agents. Although some settings guarantee a permanent connectivity among entities (e.g. warehouses [START_REF] Peter | Coordinating Hundreds of Cooperative, Autonomous Vehicles in Warehouses[END_REF]), this is not always true in applications with open environments. As an example, consider information gathering missions, where agents are required to visit a set of locations and gather information using sensors (e.g. cameras, smoke sensors, hygrometers etc.). A common requirement of these missions is to obtain a live feed of video which can be ensured only through permanent connectivity [73]. This requirement can be critical in specific setting like search and rescue missions, where the communication between the agents depends on the topology of the area (e.g. buildings, trees) and it is required to ensure proper visit of the area, or to transfer information gathered to a base station [3,[START_REF] Tateo | Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It[END_REF].

Another aspect that can be found in many applications is the lack of complete knowledge of the area in which the entities move. For instance, in exploration missions, the agents are not provided any information of the environment and must discover it by themselves [START_REF] Rao | Robot navigation in unknown terrains: Introductory survey of non-heuristic algorithms[END_REF][START_REF] Thrun | Robotic Mapping: A Survey[END_REF]. In this context, the agents may have to ensure connectivity at all times to exchange their findings and in case of disconnection they will have to search for each other to reconnect.

Recent works on the planning of entities have been focused on the planning of collisionfree executions. This problem, called Multi-Agent Path Finding (MAPF), is to find a sequence of steps for a group of agents to reach specified targets while avoiding collisions. This dissertation studies two aspects of multi-agent path planning in order to model and solve more realistic applications: (1) generalized connectivity of the agents; (2) incomplete knowledge of the environment.

Many works on path planning and coverage path planning either assume a given discrete graph model obtained by cell decomposition or visibility graph [START_REF] Steven | Planning Algorithms[END_REF], or use a sampling method to construct a graph on which combinatorial algorithms are applied [START_REF] Kavraki | Analysis of probabilistic roadmaps for path planning[END_REF][START_REF] Kuffner | RRT-connect: An efficient approach to single-query path planning[END_REF]. Graph-based algorithms such as those we study, and previous work such as A * for MAPF [START_REF] Malcolm | Exploiting Subgraph Structure in MultiRobot Path Planning[END_REF][START_REF] Standley | Finding Optimal Solutions to Cooperative Pathfinding Problems[END_REF] and Conflict-Based Search (CBS) [START_REF] Sharon | Conflict-Based Search for Optimal Multi-agent Path Finding[END_REF] are thus relevant in this setting. It is important to under- stand the computational complexity of these graph problems to understand the limits of the algorithmic solutions and as well as heuristics that can be applied to the problem at hand.

In Figure 1.1, we depicted a 2D environment and an execution of two agents. The environment is represented by black and white tiles. The former represents obstacles and the latter represents free areas. An agent can move to either of the white tiles surrounding his current position (i.e. North, South, East, West). In this example the two agents are in collision after 4 steps in the cell D3. This execution is, thus, not collision-free and would not be valid for the MAPF problem. A solution would be to delay one of the agent by 1 step. An example of a partially-known environment is depicted in Figure 1.3. We consider that the agent can see at 2 cells away from them (only 1 cell in diagonal). In order to reach their goals, the agents must avoid the obstacles that they will encounter during the mission. It is worth noting that it may be beneficial for the agents to take a detour to observe the environment as it could shorten the paths of others. Indeed, it may be the case that an agent by, extending slightly its path and, observing the presence of an obstacle, can warn in advance another agent, shortening the overall execution.

Contribution

The contribution of this work is twofold. First, we present a framework to study and model connectivity-based multi-agent path planning problems. We provide a detailed initial work on the complexity of this framework and an optimal algorithm to solve it. Second, we extend our connectivity framework to the incomplete knowledge setting and show the complexity of the connected and decentralized computation of plans under partially known environments. Let us give a more detailed summary of our contributions.

Connectivity

Firstly, we address the problem of connectivity. While some initial work has been done to formalize an environment-based communication framework [START_REF] Hollinger | Multirobot Coordination With Periodic Connectivity: Theory and Experiments[END_REF][START_REF] Tateo | Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It[END_REF], we studied this problem in detail under two different goals, reachability and coverage. The summary of the contributions is depicted in Table 1.1.

The reachability problem is denoted CMAPF, for Connected Multi-Agent Path Finding, and the coverage problem is denoted CMACP, for Connected Multi-Agent Coverage Planning. The first problem consists in searching a sequence of steps for a group of agents to navigate in an environment to reach a specific location. The CMACP problem asks to find an execution for a fleet to cover every location of an area.

An important aspect of those problems is whether we are given a bound on the number of steps in which the agents are to achieve their goals. We will denote the bounded version of a problem with the prefix 'b'. For instance, bCMACP is the problem of finding a connected bounded covering execution.

It is worth noting that these problems behave differently depending on the class of instance. In particular, we show how hard these problems are in general and possible restrictions which render them tractable. In addition, we present the complexity of some simple variants that can be inferred from the proofs.

Our results show that path finding or coverage problems are intractable whether the execution is bounded or not, NP-complete and PSPACE-complete respectively. However, deciding the existence of a plan can become easier under some assumptions, especially if restricted to Sight-Moveable graphs. Indeed, with this class, which restrict the communication to locations ensuring a connected path, the problems are LOGSPACE or NLOGSPACE. However, we showed that the optimization of an execution is a hard problem unless restricted to unrealistic classes.

Then, we illustrate and analyze an optimal algorithm to solve Connected Multi-Agent Path Finding (CMAPF). Some algorithms have been previously proposed: an online algorithm [START_REF] Hollinger | Multirobot Coordination With Periodic Connectivity: Theory and Experiments[END_REF] and two approximation algorithms [START_REF] Tateo | Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It[END_REF]. Contrarily to the previous approaches, the structure of our algorithm is based on CBS, and we prove its optimality and soundness. The approach is decoupled, a low-level algorithm searches for a path for each agent, while a high-level algorithm constrains the agents to ensure connectivity. We discuss some optimizations, and we provide an experimental study of its scalability.

Incomplete Knowledge

We present a setting for incomplete knowledge taking connectivity into account. We use the communication framework of the first contribution, and restrict our study to the reachability problem. A problem with a suffix 'I'denotes the incomplete knowledge variant. For instance, bCMAPFI denotes the bounded reachability problem with incomplete knowledge. The summary of the contributions is depicted in Table 1.2.

The incomplete knowledge of the environment refers to the fact that some movement or communication are not ensured. Thus, even though the environment is static the agents will observe new information as they explore. In this case, it is important to distinguish two problems. First, the connected case which enforces the agents to stay connected at all steps. In this case, the agents have to ensure that an uncertain communication will not disrupt the execution. However, the agents share the same knowledge at all times as they inform each other of their findings. The second problem, the decentralized case, lets the agents disconnect during the mission. As the agents may not share their knowledge at all times, they have to reason about the possible observations of the others and their choices.

This difference is a hint at the explanation to the consequent "jump" in complexity between the connected case, CMAPFI, and the decentralized case, DMAPFI. Our results show that the intuitive distinction between the decentralized case and the connected case has a major impact on the complexity of the problem. Indeed, the connected case is PSPACE-complete and the decentralized case is NEXPTIME-complete. In the general setting of directed graphs, the addition of a bound on the execution has no impact on the complexity. However, on undirected graphs it is trivial to find an unbounded execution as the agents can explore all configurations until they reach the goal or discover that it cannot be done.

Outline

The rest of this dissertation is structured in 6 Chapters as follows:

In Chapter 2, we present the preliminaries. In particular, the Section 2.1 introduces the necessary notions of complexity theory and Section 2.2 formalizes MAPF. The Chapter 3 summarizes the state of the art. More precisely, in Section 3.1 we give a background of MAPF, Section 3.2 is dedicated to present previous works on coverage planning, in Section 3.3 we introduce some work on connectivity and Section 3.4 presents the work which inspired our incomplete knowledge framework. Then, the contributions of this dissertation are arranged in two parts, with Part I dedicated to the study of CMAPF, and Part II focused on the study of an incomplete knowledge setting for the coordination of agents.

In Chapter 4, we introduce and study the connectivity framework. Section 4.1 establishes the setting of our work. In Section 4.2, we introduce the required notions for the rest of the chapter. In Section 4.3, we describe the upper bounds of our problems on directed topological graphs and, in Section 4.4, we prove the lower bounds on undirected topological graphs to obtain completeness results. In Section 4.5, we study sight-moveable topological graphs. Section 4.6 contains the complexity analysis of the complete-communication topological graphs. We introduce relevant extensions of our problems in Section 4.7. We present a conclusion and future works in Section 4.8.

Chapter 5 introduces an algorithm to solve CMAPF. Section 5.1 gives an overview of the setting and previous works. Section 5.2 presents our algorithm, and Section 5.3 contains the correctness and optimality proofs. Then, Section 5.4 presents experiments.

In Chapter 6, we study the problem of connected coordination in a partially-known environment. Section 6.1 presents the study of incomplete knowledge. In Section 6.2, we formalize our imperfect information setting. We recall the TQBF and TDQBF problems in Section 6.3. Our results for the connected and decentralized cases are given in Sections 6.4 and 6.5 respectively. Section 6.6 contains additional results that can be obtained from our work, discussion on related work, and perspectives.

Finally, in Chapter 7, we conclude on the work achieved in this dissertation. We summarize the different results of each contribution in Section 7.1. In Section 7.2, we provide the list of articles that have been published during the writing of this study. Then, we state possible future works that would extend our results and remove limitations in Section 7.

PRELIMINARIES

This chapter is dedicated to the introduction of the concepts that require a proper definition for the results presented in this dissertation. We first introduce notions from complexity theory. This theory will be used throughout this work as we will classify the difficulty of several studied problems. This classification work has for primary purpose to evaluate how efficiently a problem can be solved. In addition, the complexity proofs provide an insight on the difficulties of a problem.

Then, we present the MAPF problem formally. This problem is at the root of this work and the definition will be extended to account for new aspects such as connectivity and incomplete knowledge.

Complexity Theory

Complexity theory is the study of algorithmic problems and how hard they are to solve. Let us begin with the notion of decision problem, complexity class and completeness. The following section is inspired from Garey and Johnson [START_REF] Michael | Computers and intractability[END_REF]. See the books of Garey and Johnson [START_REF] Michael | Computers and intractability[END_REF], Lewis and Papadimitriou [START_REF] Harry | Elements of the Theory of Computation[END_REF], Arora and Barak [START_REF] Arora | Computational complexity: a modern approach[END_REF], and Homer and Selman [START_REF] Homer | Computability and complexity theory[END_REF] for a detailed presentation of the complexity theory.

Problem

In this work, we consider a decision problem to be a task to accomplish. A task takes place in a specific domain and can either be completed or not. As an example, let us suppose that we want to deliver a package. For this delivery, we are given the instance: a map of the city, our starting location, and the delivery location. First and foremost, we must make sure that we can reach the delivery location. In other words, we must decide whether our task can be completed, if the current instance is positive or not. More formally, we define a decision problem as follows. From now on, when defining a problem, the input -describing the generic information provided -and the output -stating a question over the input -represent the domain and the positive instances, respectively. Let us define the Undirected Connectivity problem to illustrate the previous definition.

Problem (Undirected Connectivity).

-Input:

A graph G = V, E , with V a finite set of vertices and E a finite set of undirected edges, and two vertices s, t ∈ V .

-Output: Does there exist a path from s to t?

One can wish to ask a maximization or minimization question over the output. For instance, we can assume that our previous delivery problem is requiring to be done as fast as possible. This new task is an optimization problem which asks to minimize our path from s to t. It is worth noting that, a decision problem can be derived from an optimization problem. Indeed, by the introduction of a bound k, one can reformulate the yes-no question.

Problem (Undirected Shortest Path).

-Input:

A graph G = V, E , with V a finite set of vertices and E a finite set of undirected edges, two vertices s, t ∈ V , and a bound k.

-Output: Does there exist a path from s to t of cost no more than k?

Under the assumption that the cost is "easy" to compute, this decision problem is not harder than the associated optimization problem. Indeed, one can solve the optimization problem and compare the cost of the obtained solution with the given bound. Thus, the associated optimization problem is at least as hard.

Encoding

While the presentation of the formal encoding of a decision problem is beyond of the scope of this dissertation, a detail is worth bringing to the attention of the reader. When deriving a decision problem from an optimization problem, the exact encoding of the bound may be important to specify. Indeed, the complexity of a problem may increase significantly with the use of a more succinct encoding.

In this work, we will often demonstrate the complexity of a problem using a binary encoding of the bound, as one might call it more "reasonable". However, when relevant, we show whether the complexity holds or changes using a unary encoding for completeness.

Deterministic Turing Machine

To define the notion of algorithm, we must first present the model of computation. For simplicity, we model an algorithm by the two-tapes Deterministic Turing Machine (DTM), which consists of two infinite tapes (input, work), a finite control with two heads. A read-only head is attached to the input tape and a read/write head is attached to the work tape.

The tapes of the machine are composed of linearly ordered cells, each holding a symbol. The control is composed of a finite set of states, including the distinguished start, yes and no states. A depiction of a DTM is provided in Figure 2 and change state. The machine starts with the control in its start state and the heads on the cells numbered 1 of their respective tape. From there, the steps taken by the control is determined by its internal state and the content of the cell being read. When the control reaches the yes or no state, it halts and "answers" accordingly. Now, let us assume that given a problem Π, we have a DTM which, for all instances d ∈ D in the domain, answers "yes" if d ∈ Y and "no" if d / ∈ Y . Then we say that this DTM is a deterministic algorithm that solves the problem Π.

Complexity Classes

Time

In order to solve a problem, an algorithm must go through a number of steps during its computation. This idea can be related to the time used by the algorithm to halt. More formally, we define the time function as follows.

Definition 2.2 (Time Function).

T A,Π (n) = max d∈D,|d|=n {m | A solves d in m steps }
is the most amount of time which the algorithm A uses to solve an instance of size n of a problem Π.

We can say that A is a polynomial-time algorithm if there exists a polynomial p such that, for all n ∈ Z + , T A,Π (n) p(n). Equivalently, we can say that A is an exponential-time algorithm if there exists an exponential e such that, for all n ∈ Z + , T A,Π (n) e(n). We can now derive time-classes of problems: Definition 2.3 (PTIME). The class PTIME, or P for short, is the class of problems for which there exists a polynomial-time algorithm which solves it. Definition 2.4 (EXPTIME). The class EXPTIME is the class of problems for which there exists an exponential-time algorithm which solves it.

Space

During computation, an algorithm not only takes steps but uses space on the work tape of the DTM to store information. This can be called the "memory" of the algorithm. More formally, we define the space function as follows. We say that A is a polynomial-space algorithm if there exists a polynomial p such that, for all n ∈ Z + , S A,Π (n) p(n). Equivalently, we can say that A is an exponential-space or logarithmic-space algorithm.

Similarly to the time property previously defined, we can define space-classes of problems:

Definition 2.6 (PSPACE). The class PSPACE is the class of problems for which there exists a polynomial-space algorithm which solves it.

Definition 2.7 (EXPSPACE). The class EXPSPACE is the class of problems for which there exists an exponential-space algorithm which solves it.

Definition 2.8 (LOGSPACE). The class LOGSPACE, or L for short, is the class of problems for which there exists a logarithmic-space algorithm which solves it.

Note that regarding a logarithmic-space algorithm, only the space used on the work tape is considered.

Nondeterminism

Before providing a detailed description of a Nondeterministic Turing Machine (NDTM), it may be useful to present informally the concept of nondeterministic algorithm. For this purpose, let us define the following problem.

Problem (Traveling Salesman Problem).

-Input:

A graph G = V, E , with V a finite set of vertices and E a finite set of undirected edges, a vertex s ∈ V .

-Output: Does there exist a tour starting at s to visit all vertices exactly once ?

Intuitively, it seems quite hard to create a tour without having to come back on some previous choices as we might only later realize an early mistake. In fact, this problem does not admit a polynomial-time algorithm (unless P = NP). However, if we are given a tour, we can in polynomial-time verify whether this tour is valid. Thus, if we were lucky enough at guessing a tour, we might find a solution easily. This is the concept at the core of a nondeterministic algorithm.

More formally, a NDTM is structured as an DTM, except for the addition of a guessing module attached to a write-only head. This module starts on the cell numbered -1 of the work tape. From there, it can either write a symbol in the current cell, move to the left or stop. The choice of steps done by the guessing module are totally arbitrary. When the guessing module becomes inactive, the control starts its computation as in a DTM. Now, let us assume that given a problem Π, we have a NDTM which, for all instances d ∈ D in the domain, if d ∈ Y then there exists a guess that leads the control to answers "yes", and if d / ∈ Y then there is no such guess. Then we say that this NDTM is a nondeterministic algorithm that solves the problem Π.

We can now describe the nondeterministic equivalent of the previously introduced complexity classes. Definition 2.9 (NPTIME). The class NPTIME, or NP for short, is the class of problems for which there exists a nondeterministic polynomial-time algorithm which solves it. Definition 2.10 (NEXPTIME). The class NEXPTIME is the class of problems for which there exists a nondeterministic exponential-time algorithm which solves it. Definition 2.11 (NLOGSPACE). The class NLOGSPACE, or NL for short, is the class of problems for which there exists a nondeterministic logarithmic-space algorithm which solves it.

A generalized notation of complexity classes describes the type of Turing machine (deterministic (D), nondeterministic (N)) used along with the bound over the time or space function. For instance, we can equivalently denote NEXPTIME as NTIME(exp(n)), or LOGSPACE as DSPACE(log(n)).

An important theorem of the complexity theory is the following:

Theorem 2.1 (Savitch's Theorem [START_REF] Walter | Relationships Between Nondeterministic and Deterministic Tape Complexities[END_REF]). For all function f (n

) ≥ log(n), NSPACE(f (n)) ⊆ DSPACE(f 2 (n)).
In other words, all problems that can be solved by a NDTM in space f (n), can also be solved by a DTM in space f 2 (n).

Corollary. PSPACE = NPSPACE and EXPSPACE = NEXPSPACE.

Many more complexity classes have been introduced and studied in the literature. However, the problem studied throughout this dissertation will fit inside the presently introduced classes. In Figure 2.2, we depicted the inclusion of the complexity classes. Note that, if a problem can be solved in, let say, polynomial-time then it can be solved by an algorithm in any more powerful complexity class, for instance a nondeterministic exponential-time algorithm.

Completeness

Up until now, we described the complexity classes and the membership relation of a problem. A crucial notion for the study of problems is one of completeness. In particular, it gives a tool for studying how "hard" a problem is compared to others. Additionally, if a problem, complete for a specific class, happen to admit an efficient algorithm then any problem of this class can use this algorithm as a subroutine.

The key idea used to show that a problem is complete for a specific class is that of a transformation, also called reduction. Note that for the sake of conciseness, we will only present polynomial transformation that apply to proof of NP-completeness and above. However, an interested reader might want to refer to Sipser [START_REF] Sipser | Introduction to the theory of computation[END_REF] and Arora and Barak [START_REF] Arora | Computational complexity: a modern approach[END_REF] for details on transformation of P-completeness and below. Definition 2.12 (Polynomial Transformation). A polynomial transformation from a problem Π to Π is a function f : D → D that satisfies the following two conditions:

1. There exists a DTM that computes f in PTIME;

For all instances

d ∈ D, d ∈ Y if and only if f (d) ∈ Y .
Whenever a problem Π has a polynomial transformation to a Π , we say that Π can be polynomially reduced to Π . Intuitively, it also means that Π is "at least as hard" as Π. We can now define the concept of completeness. Definition 2.13 (Completeness). Given a class C, a problem Π is C-complete if Π ∈ C and, for all other problem Π ∈ C, Π can be polynomially reduced to Π .

Intuitively, the C-complete problems are the hardest problems in C. From our previous definitions, we can observe that given two problems Π, Π ∈ C, if Π is C-complete and Π reduces to Π then Π is C-complete. Thus, throughout this work we will rely on this observation to show that a problem is C-complete. Indeed, we will introduce a problem previously proven Ccomplete, show that our problem is in C and show that we have a polynomial transformation from the introduced problem to ours.

Note that the use of a polynomial reduction is not valid to show the completeness of a problem to the class P and below. Indeed, as a polynomial reduction would, by default, require a polynomial amount of time, one must use a logarithmic-space reduction or lower.

Asymptotic notation

We introduced complexity classes which let us prove how hard a problem is. However, when analyzing algorithms it may be important to obtain a more fine-grained classification of the computation time or space. Let us introduce the notion of asymptotic notation for computation time. Nevertheless, the following can be applied to describe spacial behavior of algorithms.

As stated previously, in order to solve a problem, an algorithm will go through a number of steps which may change depending on the instance. Intuitively, consider the problem of sorting a list, in general the algorithm will have to execute more steps to sort a longer list. It is important when analyzing an algorithm to describe how much the number of steps taken grows with the size of the instance.

Let us define multiple notations used to describe the behavior of an algorithm A on a problem Π. Definition 2.14 (Big-O Notation). A grows in O(f (n)) if there exists a positive constant c such that for all n, the number of steps of A for all instances d ∈ D of size n is at most c × f (n). Definition 2.15 (Big-Omega Notation). A grows in Ω(f (n)) if there exists a positive constant c such that for all n, the number of steps of A for all instances d ∈ D of size n is at least c × f (n).

Note that f ∈ Ω(g) if and only if g ∈ O(f ).

Multi-Agent Path Finding

Let us present the problem at the origin of this work. In this section, we formally introduce a general definition of the MAPF problem. We present the theoretical setting of the problem and a bounded variant.

Problem Statement

The MAPF is the problem of moving a group of agents in an environment. For theoretical convenience, the environment is modeled as a graph. Definition 2.16 (Graph). A graph is a couple G = V, E , with V a set of vertices and E ∈ V × V a set of edges.

Each agent starts at a specific location of the graph and move along the edges to reach their respective targets. In other words, the agents start at a configuration and must reach a provided goal configuration. Definition 2.17 (Configuration). A configuration c of n agents in a graph G is a vector of elements of V of size n, denoted c = c 1 , . . . , c n .

During their travel in the graph, all the agents synchronize when arriving at a node. This sequence of steps is called an execution.

Definition 2.18 (Execution).

An execution e of length with n agents in a graph G is a sequence of configuration e = c 1 , . . . , c such that (c j , c j+1 ) ∈ E for all 1 ≤ i < .

For simplicity, we can note c j → G c j+1 as a shortcut to (c j , c j+1 ) ∈ E. Two types of collisions must be avoided in an execution. Recall that c t k denotes the position of agent k at time t. = c t a . An execution without vertex-collision and edge-collision is said to be collision-free. Formally, MAPF can be defined as follows.

Problem 2.1 (MAPF). -Input:

A graph G and two configurations c s , c g of same size. -Output: Does there exist a collision-free execution e = c s , . . . , c g ? MAPF is a planning problem, thus it is often assumed that a solution always exists. However, it is important to minimize the number of steps in the execution. While multiple definitions of the minimization problem exist, we will restrict our definition to the minimization of the sum of paths length. In other words, we consider that an agent increases the cost of the execution if and only if it moves between two configurations or idles on a vertex different from its goal. A bounded version of MAPF can be defined as follows.

STATE OF THE ART

This chapter is dedicated to a summary of the literature surrounding the study of CMAPF and related works. First, we will present MAPF, the complexity of deciding the existence of an unbounded and bounded solution, special cases, variants and algorithms. Then, we introduce the previous contributions on CMAPF and the known results. In addition, we provide a presentation of the studies of the exploration of unknown environments. Finally, we present works which go beyond the initial problem and the possible extensions that our work can undergo.

Multi-Agent Path Finding

MAPF is a problem which has obtained growing interest in the recent years. Multiple lines of work brought MAPF to its current state. First, Reif [START_REF] John H Reif | Complexity of the mover's problem and generalizations[END_REF], in parallel with Hopcroft et al. [START_REF] Hopcroft | On the Complexity of Motion Planning for Multiple Independent Objects; PSPACE-Hardness of the "Warehouseman's Problem[END_REF], studied the complexity of the Coordinated Motion Problem which asks for the motion of multiple three-dimensional objects in an environment with obstacles. This problem was shown to be PSPACE-hard, even in the two-dimensional case. An example of such a problem is the case of two disc-shaped robots moving in the presence of polygonal obstacles [START_REF] Schwartz | On the Piano Movers' Problem: III. Coordinating the Motion of Several Independent Bodies: The Special Case of Circular Bodies Moving Amidst Polygonal Barriers[END_REF]. The planning problem for multiple agents is PSPACE-hard even when robot shapes are restricted to simple tiles [START_REF] Hearn | PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation[END_REF]. PSPACE-hardness was shown in case of unit-square robots with polygonal obstacles as well when agents are unlabelled/homogeneous, or in our terminology, anonymous [START_REF] Solovey | On the hardness of unlabeled multi-robot motion planning[END_REF]. A line of algorithms that avoid this high complexity are those based on sampling methods such as Kavraki et al. [START_REF] Kavraki | Analysis of probabilistic roadmaps for path planning[END_REF] and Kuffner and LaValle [START_REF] Kuffner | RRT-connect: An efficient approach to single-query path planning[END_REF]. They randomly sample points and check whether these points can be connected respecting the constraints of the system. This allows one to quickly generate a tree or a graph between sampled points, and continue sampling points until the desired plan is found.

In another line of work, Ratner and Warmuth [START_REF] Ratner | Finding a Shortest Solution for the N × N Extension of the 15-PUZZLE Is Intractable[END_REF] studied the generalized version of the 15-Puzzle. They showed that finding the shortest solution to this problem is NP-hard. In order to deal with the high complexity of the problem, multiple approaches were investigated.

First, with the introduction of A* [START_REF] Hart | Correction to "A Formal Basis for the Heuristic Determination of Minimum Cost Paths[END_REF], the centralized approach was investigated [START_REF] Latombe | [END_REF]. In this algorithmic approach, the group of agent is considered to be a single entity. Many variants of A* were studied and introduced to solve the MAPF efficiently and/or optimally. A standard of the game industry was Local Repair A* (LRA*) [START_REF] Stout | Smart Move: Intelligent Path-Finding[END_REF]. However, many more improvements and variants were studied [START_REF] Standley | Finding Optimal Solutions to Cooperative Pathfinding Problems[END_REF][START_REF] Goldenberg | A* variants for optimal multi-agent pathfinding[END_REF].

Another approach called the decoupled approach, recently gave birth to the most efficient algorithm to solve MAPF. The strategy of such approach is to consider each agent as independent, and plan their paths separately. A good example of such a technique is Windowed Hierarchical Cooperative A* (WHCA*) [START_REF] Silver | Cooperative Pathfinding[END_REF]. Agents are considered in turns; each one is assigned a path avoiding collisions with previously assigned agents. Similar approaches were studied by Dresner and Stone [START_REF] Dresner | A Multiagent Approach to Autonomous Intersection Management[END_REF], Wang, Botea, et al. [START_REF] Ko-Hsin | Fast and Memory-Efficient Multi-Agent Pathfinding[END_REF], and Jansen and Sturtevant [START_REF] Jansen | Direction Maps for Cooperative Pathfinding[END_REF]. However, contrarily to the centralized approaches, these are not optimal. In order to solve this last issue, Sharon et al. [START_REF] Sharon | Conflict-based search for optimal multi-agent pathfinding[END_REF] introduced CBS which was improved with many powerful optimizations [START_REF] Sharon | Meta-Agent Conflict-Based Search For Optimal Multi-Agent Path Finding[END_REF][START_REF] Boyarski | Don't Split, Try To Work It Out: Bypassing Conflicts in Multi-Agent Pathfinding[END_REF][START_REF] Felner | Adding Heuristics to Conflict-Based Search for Multi-Agent Path Finding[END_REF][START_REF] Li | Disjoint Splitting for Conflict-Based Search for Multi-Agent Path Finding[END_REF][START_REF] Li | Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search[END_REF].

Complexity

The complexity of MAPF has been intensively studied in order to find practical classes in which the problem is easier or that can be used to simplify the computation of the general problems through heuristics. Indeed, MAPF was studied on planar graphs [START_REF] Yu | Intractability of Optimal Multirobot Path Planning on Planar Graphs[END_REF], on grid graphs [START_REF] Yu | Structure and Intractability of Optimal Multi-Robot Path Planning on Graphs[END_REF]. While no practical classes of graphs seem to yield a tractable variant of the decision problem associated to the optimization of MAPF, deciding the existence of an execution was shown to be in PTIME [START_REF] Yu | Multi-agent Path Planning and Network Flow[END_REF].

Slideable

An interesting restriction of MAPF on grid maps is the one of slideable instances. This class of instances, introduced by Wang and Botea [START_REF] Ko-Hsin | Tractable Multi-Agent Path Planning on Grid Maps[END_REF], admits a polynomial-time algorithm. For an instance to be Slideable, there must exist a path for all agents to their goals which at all time admits alternative moves. The core idea is that the algorithm does not require replanning. While this algorithm is not complete for general MAPF, it runs in O(|V | 2 n 2 ) or even linearly on some instances.

Variants

Here we present multiple variants of MAPF that have been studied to capture additional important concepts.

Target Assignment

Introduced by Ma and Koenig [START_REF] Ma | Optimal Target Assignment and Path Finding for Teams of Agents[END_REF], the Target-Assignment and Path Finding (TAPF) problem is the problem of assigning targets to the agents in teams along planning collision-free paths. This problem generalizes both the anonymous and non-anonymous MAPF. Indeed, the anonymous MAPF would be TAPF with a single team of agents, and the non-anonymous MAPF would be TAPF with single agent teams. Multiple algorithmic solutions were introduced to solve TAPF [START_REF] Ma | Optimal Target Assignment and Path Finding for Teams of Agents[END_REF][START_REF] Van Nguyen | Generalized target assignment and path finding using answer set programming[END_REF][START_REF] Ma | Target Assignment and Path Planning for Navigation Tasks with Teams of Agents[END_REF].

Robustness

The theoretical formulation of MAPF does not take into account the various mishaps that can happen during the execution of the plan in the real world. Multiple concepts of robustness have been studied to create plans which can react or avoid problems during the execution. The concept of k-robustness [START_REF] Atzmon | Robust multi-agent path finding[END_REF], allows the agents to survive to a bounded number of mishaps. A parallel line of work studied a probabilistic robustness [START_REF] Atzmon | Probabilistic Robust Multi-Agent Path Finding[END_REF], which can provide a solution which succeeds with probability at least p.

Lifelong

While MAPF solves the problem of efficiently moving a group of agents in an arbitrary complex environment, it does not handle an important characteristic of the warehouse problems. In such a setting, the system continuously receives new requests of targets for the agents to reach. The Lifelong MAPF, introduced as Multi-Agent Pickup and Delivery (MAPD) [START_REF] Ma | Lifelong multi-agent path finding for online pickup and delivery tasks[END_REF], solves this online version of MAPF. More works on this particular variant was done by Ma et al. [START_REF] Ma | Lifelong path planning with kinematic constraints for multi-agent pickup and delivery[END_REF] and Li et al. [START_REF] Li | Lifelong Multi-Agent Path Finding in Large-Scale Warehouses[END_REF].

Coverage Planning

The coverage path planning problem has been studied in different settings; see the surveys of Choset [START_REF] Choset | Coverage for robotics -A survey of recent results[END_REF], Galceran and Carreras [START_REF] Galceran | A survey on coverage path planning for robotics[END_REF], and Cabreira et al. [START_REF] Tauã | Survey on Coverage Path Planning with Unmanned Aerial Vehicles[END_REF]. This problem can be used to solve inspection (where a given set of points of interests must be observed), surveillance (points of interest must be continuously visited), and can be used in applications such as lawn mowing and floor cleaning. One can prove probabilistic completeness results in some cases, which means that if a solution exists, then the algorithm will eventually find it with probability 1; although it may not be able to detect that no solution exists [START_REF] Englot | Sampling-Based Coverage Path Planning for Inspection of Complex Structures[END_REF]. Some of these algorithms work in two phases: the first phase consists in sampling points and checking the feasibility of the edges between them, and the second phase consists in solving a graph problem on this structure, and repeating the first phase if no solution is found. Some works use approximations of metric Traveling Salesman Problem (TSP) to find solutions in the constructed graph [START_REF] Danner | Randomized planning for short inspection paths[END_REF][START_REF] Englot | Planning Complex Inspection Tasks Using Redundant Roadmaps[END_REF]. Other works use A * search algorithms with suitable heuristics to compute approximate solutions [START_REF] Fu | Toward Asymptotically-Optimal Inspection Planning Via Efficient Near-Optimal Graph Search[END_REF].

Several works consider the coverage path planning problem for multiple agents [START_REF] Chen | The coverage problem in UAV network: A survey[END_REF][START_REF] Galceran | A survey on coverage path planning for robotics[END_REF][START_REF] Tauã | Survey on Coverage Path Planning with Unmanned Aerial Vehicles[END_REF]. Kusnur et al. [START_REF] Kusnur | A Planning Framework for Persistent, Multi-UAV Coverage with Global Deconfliction[END_REF] introduced a centralized framework to compute plans for the persistent coverage problem without communication constraints. In Rekleitis et al. [START_REF] Rekleitis | Efficient Boustrophedon Multi-Robot Coverage: an algorithmic approach[END_REF] gave algorithms for the repeated coverage problem in unknown environments for a team of robots, including the case of the line-of-sight communication restriction. This uses the cell decomposition given by Choset and Pignon [START_REF] Choset | Coverage Path Planning: The Boustrophedon Cellular Decomposition[END_REF] for the coverage path planning. Hazon and Kaminka [START_REF] Hazon | Redundancy, Efficiency and Robustness in Multi-Robot Coverage[END_REF] and Xiaoming Zheng et al. [START_REF] Zheng | Multi-robot forest coverage[END_REF] obtain a graph structure thanks to a cell decomposition, and variants of spanning trees are computed on this graph to ensure coverage with multiple robots. Graph problems related to this problem are studied by Xu [START_REF] Xu | Graph Planning for Environmental Coverage[END_REF]. The generalization of TSP was studied by Anbuudayasankar et al. [5] which is a relevant problem for coverage path planning in the multi-agent setting. Some works also consider maneuverability and camera angle constraints [1].

Connectivity

The continuous communication restriction appears in several works which provide experiments to demonstrate the feasibility of the proposed algorithms [START_REF] Pandey | Multi-robot exploration with communication requirement to a moving base station[END_REF][START_REF] Nestmeyer | Decentralized Simultaneous Multi-Target Exploration Using a Connected Network of Multiple Robots[END_REF][START_REF] Yanmaz | Connectivity versus area coverage in unmanned aerial vehicle networks[END_REF][START_REF] Wt Luke Teacy | Maintaining connectivity in UAV swarm sensing[END_REF]. Some works consider the use of dynamic teams of robots which exchange their information on current solutions [START_REF] Otte | Any-Com Multi-robot Path-Planning with Dynamic Teams: Multi-robot Coordination under Communication Constraints[END_REF]. Communication and battery restrictions are considered together by Cesare et al. [START_REF] Cesare | Multi-UAV exploration with limited communication and battery[END_REF] which gave an algorithm in which robots can adopt the roles for exploring, meeting, sacrificing themselves (continuing the mission in case of low battery), and serving as communication relay for other robots. Different communication restrictions have been considered as well such as event-based communication where the discovery of new information triggers communication (see e.g [3,[START_REF] Banfi | Asynchronous multirobot exploration under recurrent connectivity constraints[END_REF]).

Connected MAPF

The CMAPF problem was initially introduced by Hollinger and Singh [START_REF] Hollinger | Multirobot Coordination With Periodic Connectivity: Theory and Experiments[END_REF] along with an online algorithm. The algorithm would run on each agent separately and guarantee a periodic reconnection of the agents. The NP-hardness of bounded CMAPF was also proven in this work. Later, Tateo et. al. [START_REF] Tateo | Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It[END_REF] provided a complexity analysis of the unbounded problem and different variants. The problem is shown PSPACE-complete without a bound, regardless of the collisionfree requirement, or the addition of a base station. Here, we remind the reader the previous results of CMAPF.

Theorem 3.1 ([69]

). Deciding the existence of a bounded connected execution on undirected topological graphs is NP-hard.

Theorem 3.2 ([151]

). Deciding the existence of a connected execution on undirected topological graphs is PSPACE-complete.

Partially-Known Environment

The exploration and navigation in a partially-known/unknown environment has been intensively studied. Many parallel lines of works studied different approaches and model of this problem. Let us present a few from which our framework is inspired.

SLAM

The Simultaneous Localization and Mapping (SLAM) problem asks to integrate the information collected during navigation into the most accurate map possible. A good overview of the many methods developed for unknown environment mapping can be found in the work of Rao et al. [START_REF] Rao | Robot navigation in unknown terrains: Introductory survey of non-heuristic algorithms[END_REF]. However, SLAM does not address the navigation task. Two different problems emerged to address the planning of the navigation in parallel to the mapping task. The Simultaneous Planning Localization and Mapping (SPLAM) asks for a motion plan through the unknown environment, which is quite intractable [START_REF] Kuipers | A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations[END_REF][START_REF] Levitt | Qualitative navigation for mobile robots[END_REF][START_REF] Burgard | Collaborative multi-robot exploration[END_REF]. On the other hand, the Next-Best

Partially-Known Environment

View (NBV) problem [START_REF] González | Navigation Strategies for Exploring Indoor Environments[END_REF][START_REF] Nüchter | Planning Robot Motion for 3D Digitalization of Indoor Environments[END_REF]4] asks to guide a robot through the environment to optimize the amount of new information gathered per step.

Canadian Traveler Problem

An interesting variant of the Shortest Path problem is the Canadian Traveler Problem (CTP) initially formulated by Papadimitriou and Yannakakis [START_REF] Papadimitriou | Shortest paths without a map[END_REF]. A traveler wishes to travel to a city during winter. However, it might happen that some roads have not been cleared of snow. Thus, it is assumed that when arriving at an intersection, the traveler is able to observe which roads are clear. The problem has recently received additional interest [START_REF] Bar | The Canadian Traveller Problem[END_REF][START_REF] Nikolova | Route Planning under Uncertainty: The Canadian Traveller Problem[END_REF][START_REF] Xu | The canadian traveller problem and its competitive analysis[END_REF][START_REF] Eyerich | High-Quality Policies for the Canadian Traveler's Problem[END_REF]. CHAPTER 4

CONNECTED MULTI-AGENT PATH PLANNING

Introduction

The MAPF problem asks for a plan to move a group of agents to a target configuration in a graph while avoiding collisions. It is an important problem in the design of groups of autonomous vehicles, and has been used in several applications such as Kiva (Amazon Robotics) warehouse systems [START_REF] Peter | Coordinating Hundreds of Cooperative, Autonomous Vehicles in Warehouses[END_REF], autonomous aircraft towing vehicles [START_REF] Morris | Planning, Scheduling and Monitoring for Airport Surface Operations[END_REF], office robots [START_REF] Veloso | CoBots: Robust Symbiotic Autonomous Mobile Service Robots[END_REF] and characters in video games [START_REF] Silver | Cooperative Pathfinding[END_REF].

A closely related problem is that of coverage path planning which consists in computing a plan that visits a set of given locations in a graph. A comprehensive survey is provided by Galceran and Carreras [START_REF] Galceran | A survey on coverage path planning for robotics[END_REF]. Applications include underwater ship hull inspection [START_REF] Englot | Sampling-Based Coverage Path Planning for Inspection of Complex Structures[END_REF], wildfire tracking with drones [START_REF] Pham | A Distributed Control Framework of Multiple Unmanned Aerial Vehicles for Dynamic Wildfire Tracking[END_REF], to name a few.

An important application area is that of information gathering missions in which agents must visit a set of locations in an area and gather information using sensors (e.g. camera, smoke sensor, hygrometer etc.). Some applications, such as search and rescue missions, might require continuous connection between all agents and a base station, for instance, in order to stream video and allow human operators to make decisions [3]. In this case, the path planning and coverage path planning algorithms must take additional connectivity constraints into account in order to compute suitable plans. Several works have explored planning algorithms in this setting e.g. [START_REF] Martijn | Multi-robot exploration under the constraints of wireless networking[END_REF][START_REF] Pandey | Multi-robot exploration with communication requirement to a moving base station[END_REF].

The variant of MAPF with connectivity constraints and related computational complexity results were studied by Hollinger and Singh [START_REF] Hollinger | Multirobot Coordination With Periodic Connectivity: Theory and Experiments[END_REF] and Tateo et al. [START_REF] Tateo | Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It[END_REF]. The latter present complexity results for connectivity constraints with and without collision constraints and that the existence of a plan of arbitrary length in both cases is PSPACE-complete in undirected graphs. Interestingly, it means that it has the same complexity as classical planning [START_REF] Bylander | The Computational Complexity of Propositional STRIPS Planning[END_REF]. The work of Bodin et al. [START_REF] Bodin | Generating Plans for Cooperative Connected UAVs[END_REF] considers the coverage path planning and provides experiments in which instances are described in Planning Domain Definition Language (PDDL) and solved with the planner Functional STRIPS [START_REF] Francès | Purely Declarative Action Descriptions are Overrated: Classical Planning with Simulators[END_REF]. In other words, MAPF with connectivity constraints is more difficult than MAPF with collision constraints: deciding the existence of a collision-free plan of arbitrary length is in PTIME, as stated by Yu and Rus [START_REF] Yu | Pebble Motion on Graphs with Rotations: Efficient Feasibility Tests and Planning Algorithms[END_REF]. Now, concerning the optimization problems, there is a subtlety about the encoding (unary vs binary) of the length of plans. For MAPF with collision constraints, as the existence of a plan is equivalent to the existence of a plan of length O(|V | 3 ) where |V | is the number of nodes [START_REF] Yu | Pebble Motion on Graphs with Rotations: Efficient Feasibility Tests and Planning Algorithms[END_REF], the encoding of the length is not relevant. Thus, several papers on the topic do not specify the encoding [START_REF] Banfi | Intractability of Time-Optimal Multirobot Path Planning on 2D Grid Graphs with Holes[END_REF][START_REF] Ma | Multi-Agent Path Finding with Payload Transfers and the Package-Exchange Robot-Routing Problem[END_REF][START_REF] Ratner | Finding a Shortest Solution for the N × N Extension of the 15-PUZZLE Is Intractable[END_REF][START_REF] Yu | Intractability of Optimal Multirobot Path Planning on Planar Graphs[END_REF][START_REF] Yu | Planning Optimal Paths for Multiple Robots on Graphs[END_REF][START_REF] Yu | Multi-agent Path Planning and Network Flow[END_REF]. However, for MAPF with connectivity constraints, there is no such bound on the length of a plan. We show that the existence of a bounded plan when the bound is given in binary is PSPACE-complete; while when the bound is given in unary, the problem is NP-complete, even on undirected graphs, as claimed by Hollinger and Singh [START_REF] Hollinger | Multirobot Coordination With Periodic Connectivity: Theory and Experiments[END_REF], although they do not explicitly specify the membership proof and are ambiguous about the encoding 1 .

We mainly consider a setting where collisions are ignored. In fact, we are interested in the computational complexity of maintaining connectivity in plans. As done by Hollinger and Singh [START_REF] Hollinger | Multirobot Coordination With Periodic Connectivity: Theory and Experiments[END_REF], agents are be assumed to be equipped with a low-level collision avoidance system in some cases. Additionally, in drone applications with few agents, different altitudes can be used to avoid collisions. Nevertheless, we do discuss the impact of taking collision constraints into account in our results as well.

In this chapter, we are interested in the computational complexity of two problems: CMAPF is the variant of MAPF with connectivity constraints, without collision constraints; and CMACP is the variant of coverage path planning for multiple agents with connectivity constraints. As in the work of Hollinger and Singh [START_REF] Hollinger | Multirobot Coordination With Periodic Connectivity: Theory and Experiments[END_REF] and Tateo et al. [START_REF] Tateo | Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It[END_REF], a problem instance is a topological graph, which is a set of nodes given with movement edges along which agents can move, and communication edges which determine pairs of vertices at which communication is possible. Our results are as follows. We establish the computational complexity of determining the existence of plans, showing that CMAPF is PSPACE-complete on directed graphs as well, and proving that CMACP is PSPACE-complete on both types of graphs. We study bounded versions of these problems where a bound on the length of the plan is given as part of the input; these are denoted by bCMAPF and bCMACP. As done by Turner [START_REF] Turner | Polynomial-Length Planning Spans the Polynomial Hierarchy[END_REF], we advocate for lengths of plans written in unary, although we also study the complexity of our problems when the encoding is binary. We show that both bCMAPF and bCMACP are NP-complete when the bound is given in unary, and we clearly state their PSPACE-completeness when the bound is given in binary.

Given the prohibitively high complexity reported above, we are interested in searching for 'easier'classes of topological graphs which are realistic for the purpose of information gathering missions. One of our main contributions is the identification of a natural class of topological graphs, called sight-moveable, for which we give efficient algorithms. This class requires that whenever an agent can communicate with another node, then it can also move to that node while maintaining direct communication. This can be seen as a restriction on allowed topological graphs; however, if the graph at hand does not have this property, it may be possible to enforce it by removing some communication edges (not allowing the planning algorithm to rely on those edges). Subsection 4.5.3 describes a way to obtain sight-moveable graphs from a given topological graph. Thus, any plan found in the obtained sight-moveable graph can be applied on the original one.

The class of sight-moveable graphs offers good computational properties: both CMAPF and CMACP belong to NLOGSPACE, meaning that they can be solved by a non-deterministic algorithm that only uses a logarithmic amount of memory. Practically, it means that algorithms for generating plans can be parallelized, because NLOGSPACE is included in the Nick's class (NC), [START_REF] Cook | A Taxonomy of Problems with Fast Parallel Algorithms[END_REF], known to represent decision problems for which there is a parallel algorithm. However, the bounded versions remain NP-complete. We complete the investigation with the complexity analysis of the problem with complete communication graphs, where all pairs of nodes can communicate. In addition, we give complexity results on several variants of our problems.

Note that the PSPACE lower bound given by Tateo et al. [START_REF] Tateo | Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It[END_REF] concerned the reachability problem where agents start from arbitrary locations, whereas we prove that the PSPACE lower bound still holds for agents starting all from the base. Furthermore, this chapter extends the work of Charrier et al. [START_REF] Charrier | Reachability and Coverage Planning for Connected Agents[END_REF] and Charrier et al. [START_REF] Charrier | Reachability and Coverage Planning for Connected Agents[END_REF], in which the complexity of CMAPF (when agents start from the base) and CMACP on undirected topological graphs was left open. In this contribution, we solved them (Theorem 4.3 and 4.4). We also include detailed proofs and discuss relevant extensions that were not considered in previous work.

Overview In Section 4.2, we introduce the required notions for the rest of the chapter. In Section 4.3, we describe the upper bounds of our problems on directed topological graphs and, in Section 4.4, we prove the lower bounds on undirected topological graphs to obtain completeness results. In Section 4.5, we study sight-moveable topological graphs. Section 4.6 contains the complexity analysis of the complete-communication topological graphs. We introduce relevant extensions of our problems, in Section 4.7. We present a conclusion and future works in Section 4.8.

Preliminaries

In some path finding applications, one considers a discretization of the space which yields a graph of movements on which algorithms are run. For instance, regular grids which decompose the space in square, triangular or hexagonal cells, irregular grids with techniques such as quadtrees [START_REF] Finkel | Quad Trees: A Data Structure for Retrieval on Composite Keys[END_REF][START_REF] Knoll | A survey of octree volume rendering methods[END_REF] or Voronoï diagrams comprehensively discussed in the survey of Aurenhammer [START_REF] Aurenhammer | Voronoi Diagrams -A Survey of a Fundamental Geometric Data Structure[END_REF].

Our work is independent of the particular method used to obtain the discretization. We only work under the hypothesis that a feasible plan on the graph generated by the discretization is also feasible in the continuous space.

We will, now, introduce the notions used throughout this work. We define formally the general topological graphs and some subclasses, the notion of execution and the properties considered, the decision problems we investigate and some known results on these problems.

Topological Graphs

Our problems require graphs with two types of edges: movement edges along which agents can move, and communication edges which specify whether agents at two different locations can communicate. We call graphs with this additional information topological graphs. The formal definition is the following and examples are depicted in

4.1 (Topological Graph). A topological graph is a tuple G = V, E m , E c , with V a finite set of nodes containing a distinguished node B called the base, E m ⊆ V × V a set of movement edges and E c ⊆ V × V a set of undirected communication edges.
The node B is the supervision base station from which the agents start the mission and with which they are required to keep communication.

In some applications movement edges are reversible, that is, if an agent can travel from a node to another, it can also go back to the former through the same edge. Undirected graphs thus naturally arise in some applications. See Figure 4.1b for an example. Definition 4.2 (Undirected Topological Graph). A topological graph is said to be undirected if V, E m is an undirected graph.

Let us now introduce our new class, called sight-moveable topological graphs, which is one of our main contributions. This class requires the movement edges to be reflexive. In addition, whenever an agent can communicate with another node, then it can also move to that node while maintaining the communication with the node it started from. An example of a sight-moveable graph is given in Figure 4.1c.

Definition 4.3 (Sight-Moveable Topological Graph). A sight-moveable topological graph G = V, E m , E c is a directed topological graph such that 1. E m ⊆ E c , 2. for all v ∈ V , (v, v) ∈ E m , 3. and whenever (v, v ) ∈ E c , there exists a sequence ρ = ρ 1 , . . . , ρ n of nodes such that v = ρ 1 , v = ρ n , for all i ∈ {1, . . . , n -1} (v, ρ i ) ∈ E c and (ρ i , ρ i+1 ) ∈ E m .
Last, we define the complete-communication topological graphs which are simply sightmoveable topological graphs with undirected movement and complete communication topology. An example of such a graph is depicted in Figure 4.1d, and the formal definition is the following. Definition 4.4 (Complete-Communication Topological Graph). A topological graph is said to be a complete-communication if it is a sight-moveable topological graph such that V, E m is an undirected graph and

E c = V × V .
Observe that a complete-communication graphs are reflexive, undirected, connected graphs with communication edges between each pair of nodes.

We say that a topological graph has a planar (grid) movement graph iff the graph V, E m is a planar (resp. grid) graph.

Execution

An execution is a finite sequence of configurations describing the positions of the agents during the mission. We require that all agents should be connected to the base in all configurations. We will use multi-sets to denote nodes occupied by agents in configurations, since agents are anonymous. In other terms, if the goal is to reach a target configuration, it does not matter which agent occupies which node, as long as there is the right number of agents at each node. Other works use the term unlabelled or homogeneous (see e.g. [START_REF] Solovey | On the hardness of unlabeled multi-robot motion planning[END_REF]); but we use the terminology of Multi-Agent Path Finding (MAPF).

The formal definition of a configuration is the following. A configuration is said to be connected iff the graph

V c , E c ∩ (V c × V c ) is connected with V c = {B, c 1 , . . . , c n }.
Given a topological graph G = V, E m , E c , we write c → G c to say that agents in c perform one-step movements to occupy nodes in c . Formally, we have c → G c if c (resp. c ) can be written as c 1 , . . . , c n (resp. c 1 , . . . , c n ), and

(c i , c i ) ∈ E m for all 1 ≤ i ≤ n. Definition 4.6 (Execution).
An execution e of length with n agents in a topological graph G is a sequence of connected configuration e = c 1 , . . . , c such that c j → G c j+1 for all 1 ≤ j < .

In our setting, the makespan of an execution is equal to its length. A covering execution e = c 1 , . . . , c of length with n agents in a graph G is an execution such that c 1 = c = B, . . . , B and for all v ∈ V , there exists j ∈ {1, . . . , } such that v appears in c j . An example of such an execution is depicted in Figure 4.2 (from left to right).

Decision Problems

We formally define the problems CMAPF and CMACP and their bounded versions bCMAPF and bCMACP. We also consider variants CMAPF-init and CMACP-init denote the problems in which the agents start at a given configuration rather than at the base. In other words, the initial configuration is part of the input. In addition, CMACP-init requires the agents to return to the initial configuration rather than to the base.

In the above problems, the encoding of the integer n (unary or binary) does not matter. Indeed, in CMAPF, CMAPF-init and CMACP-init, the input already contains some configuration which is of size n; in CMACP, it is useless to have n greater than the number of nodes.

The Bounded Case

The bounded versions are inspired from the so-called polynomial-length planning problem [START_REF] Turner | Polynomial-Length Planning Spans the Polynomial Hierarchy[END_REF] in which we ask for the existence of a plan of length bounded by a polynomial in the size of the planning task. This can be seen as the decision problem for the optimization problem that seeks to minimize the length of an execution, except that we assume that the bound is given in unary. In fact, the goal of planning algorithms is to compute plans, so given a bound on the length of the desired plan, the algorithm always allocates memory space of size Ω( ) to store the plan.

That is why we use unary encoding in the following definitions. Binary encoding of the length is discussed as well in Subsection 4.7.1. Definition 4.9 (bCMAPF). Given a topological graph G, an integer n and a configuration c of size n and an integer written in unary, decide if there is an execution c 1 , . . . , c in G s.t.

≤ , c 1 = B, . . . , B and c = c. Definition 4.10 (bCMACP). Given a topological graph G, an integer n, an integer written in unary, decide if there exists a covering execution of length such ≤ .

Restriction to Subclasses of Graphs

We consider the restriction of the above problems to the following subclasses of graphs: directed graphs (denoted by DIR), undirected graphs (denoted by UND), sight-moveable graphs (denoted by SM) and complete-communication graphs (denoted by CC). The variants of these problems to a given graph class will be denoted using a subscript, that is, CMAPF , CMACP , bCMAPF , bCMACP , CMAPF-init , and CMACP-init denote the restriction of these problems to graphs of type ∈ {DIR, UND, SM, CC}.

Known Results

The connected version of MAPF was introduced by Hollinger and Singh [START_REF] Hollinger | Multirobot Coordination With Periodic Connectivity: Theory and Experiments[END_REF], in which a topological graph discretizes the space and it is proved that the existence of a plan for the reachability of a configuration of non-anonymous agents in a bounded number of steps with collisions allowed is NP-hard:

Theorem 4.1 ([69]). bCMAPF-init UND is NP-hard.
As stated before, the above paper actually states the NP-hardness of this problem but without specifying the encoding of the bound.

Tateo et al. [START_REF] Tateo | Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It[END_REF] establish the complexity of CMAPF-init UND :

Theorem 4.2 ([151]). CMAPF-init UND is PSPACE-complete.
We relate both problems showing PSPACE-hardness when agents all start at the base.

Overview of Results

In the rest of the work, we study upper and lower complexity bounds for the defined decision problems on different topological graphs. The following sections present our results, respectively, for the general case, the undirected graphs, sight-moveable graphs, and completecommunication graphs. An overview of these results is given in Figure 4

Directed Topological Graphs

In this section, we will consider the previous problems restricted to the class of directed topological graphs. These problems are thus denoted by CMAPF DIR and bCMAPF DIR (resp. CMACP DIR and bCMACP DIR ), with DIR denoting the class of directed topological graphs.

In this section, we show upper bounds for all our problems in the general case, that is, for directed topological graphs. Observe that this also provides upper bounds for other classes such as undirected graphs.

For the unbounded problems, we can design a straightforward non-deterministic algorithm running in polynomial space, that guesses an execution by keeping in memory the last configuration, and, for CMACP, the set of visited regions. In fact, the number of configurations is exponential, and a single configuration can be stored in polynomial space. Moreover, one can easily bound the length of executions by an exponential as well. We conclude with Savitch's Theorem (NPSPACE=PSPACE) [START_REF] Walter | Relationships Between Nondeterministic and Deterministic Tape Complexities[END_REF]: Proposition 4.1. CMACP and CMAPF are in PSPACE.

For the bounded versions of the problems, since the bound is encoded in unary, one can guess and check a path of bounded length in polynomial time. The result follows. Proposition 4.2. bCMACP and bCMAPF are in NP.

Undirected Topological Graphs

In this section we prove the PSPACE lower bound of the problems CMAPF and CMACP on undirected topological graphs.

We consider the result of Theorem 4.2 in the setting where all agents start at the base. , from v i to v i+1 , for all 1 ≤ i < n, from v n+1 to v 1 and from v n to v n+2 . We repeat this last procedure for the second layer as well.

Theorem 4.3. CMAPF UND is PSPACE-complete. G B B B v 1 v 2 v n v 1 v 2 v n v n+1 v n+2 v n+1 v n+2 s 1 s 2 s n t
We now give the formal definition of our reduction. In the sequel, we use the symbol to emphasize that the union is of disjoint sets. Formally, given (G, B, n, s, t) with G = V, E m , E c with base B, we define (G , B , n + 2, t ) where G = V , E m , E c with base B where:

-V := V B , v 1 , . . . , v n , v 1 , . . . , v n , v n+1 , v n+2 , v n+1 , v n+2 , t n+1 , t n+2 -E m is the symmetric closure of E m ∪ {(B , v 1 ), . . . , (B , v n ), (B , v n+1 ), (B , v n+2 )} ∪ {(v 1 , v 1 ), . . . , (v n , v n )} ∪ {(v 1 , s 1 ), . . . , (v n , s n )} ∪ (v n+1 , v n+1 ), (v n+2 , v n+2 ), (v n+1 , t n+1 ), (v n+2 , t n+2 ) ∪ {(t n+1 , t n+1 ), (t n+2 , t n+2 )}; -E c is the symmetric closure of E c ∪ (v 1 , v 2 ), . . . , (v n-1 , v n ) ∪ {(v 1 , v 2 ), . . . , (v n-1 , v n )} ∪ (B , v n+1 ), (B , v n+1 ), (B , t n+1 ) ∪ (v 1 , v n+1 ), (v n , v n+2 ), (t n+2 , B) ∪ {(t n+2 , v) | (B, v) ∈ E c } ∪ {(v 1 , v n+1 ), (v n , v n+2 ), (t n+1 , t n+2 )}.
It is worth noting that all connected configurations in G are now connected via B , t n+1 and t n+2 . We now show the instance (G, B, n, s, t) of CMAPF-init UND is feasible if, and only if in the constructed instance (G , B , n + 2, t ) of CMAPF UND is feasible.

(⇒) Suppose that t is reachable from s in the instance (G, B, n, s, t). We construct an execution for (G , B , n + 2, t ) as follows. All agents start from B . The n + 2 agents first reach v 1 , . . . , v n+2 , then v 1 , . . . , v n+2 , then s 1 , . . . , s n , t n+1 , t n+2 . After that, the agents at positions s 1 , . . . , s n reach positions t 1 , . . . , t n (following the same plan as in for (G, B, s, t)), while the two others remain in t n+1 and t n+2 .

(⇐) Let us consider an execution e from B , . . . , B to t for (G , B , n + 2, t ). Let us extract an execution from s to t for (G, B, n, s, t). In order to do so, we prove the Facts 1 and 2.

Fact 1. The configuration s 1 , . . . , s n , t n+1 , t n+2 , up to a permutation, appears in the execution e.

Proof. The configuration t is reached at the end of the execution e and the n + 2 agents started at B . Thus, n agents must enter into G and be at one of the s i at some point. Let us consider the moment of the execution e when an agent, denoted a, occupies a node s i . For that, it must be at v i before going to s i . Furthermore, for agent a to be connected at v i the nodes v n+1 and v 1 , . . . , v i-1 must be occupied. At the next step, at least the nodes t n+1 and t n+2 must be occupied for agent a to be connected at s i .

Consider the last instant before t n+2 is first occupied (some instant where t n+2 is occupied has to exist since otherwise no visit of G coud be connected to B ). At this last instant some agent is necessarily at v n+2 , hence v 1 , . . . , v n+1 are also occupied.

G B G G t 1 t 2 t n v 1 1 v 1 2 v 1 n v 2 1 v 2 2 v 2 n v 3 1 v 3 2 v 3 n v 4 1 v 4 2 v 4 n Figure 4.4 -Reduction of CMAPF UND to CMACP-init UND .
Towards contradiction, assume the agent at v i next moves to v i . Then for the connection to be maintained from B to this agent, also (in particular) v n+1 has to be occupied; this is necessarily by the (necessarily unique) agent which was at v n+1 , hence t n+1 is not occupied and so, the agent at t n+2 is not connected, contradiction. Hence the next configuration must be s 1 , . . . , s n , t n+1 , t n+2 . Now, by Fact 1, we can consider the last time at which the agents are in the configuration s 1 , . . . , s n , t n+1 , t n+2 . We prove the Fact 2.

Fact 2. Between that last time and the end of the execution, there are always the same n agents in G, one agent on t n+1 and one on t n+2 .

Proof. A similar reasoning to the last one can be used to show that if an agent is located at s i before moving to v i then nodes from s 1 to s n as well as t n+1 and t n+2 are occupied. Thus, since this is the last time the agents are in the configuration s 1 , . . . , s n , t n+1 , t n+2 , none of the n first agents can move out of G. Furthermore, t n+1 and t n+2 must stay occupied in order for the n agents in G to be connected to B .

From Facts 1 and 2, the positions of the first n agents in the portion of the execution between the last time in s 1 , . . . , s n , t n+1 , t n+2 and t are fully in G and gives an execution starting at s and finishing at t for (G, B, n, s, t).

We now turn our attention to CMACP UND . To do so, we start by establishing the PSPACEcompleteness of CMACP-init UND , and then show how to reduce this problem to CMACP UND .

Lemma 4.1. CMACP-init UND is PSPACE-complete.
Proof. The membership of CMACP-init UND to PSPACE can be shown by using the same arguments as for the proof of Proposition 4.1. The proof of PSPACE-hardness is obtained by polynomial reduction from CMAPF UND . We map a CMAPF UND -instance (G, B, n, t) to the CMACP-init UND -instance (G , B, 2n, s) where G is depicted in Figure 4.4 and starting at the configuration s = B, . . . , B, v 1 1 , . . . , v 1 n . The definition of s means that n agents start at the base B and n agents start in positions v 1 1 , . . . , v 1 n , that are in the reduction gadget. Let us describe the construction of G .

-Nodes We make four layers of vertices from v 1 1 , . . . , v 1 n to v 4 1 , . . . , v 4 n . -Movement We create movement edges between v j i and v j+1 i , with 1 ≤ i ≤ n and 1 ≤ j ≤ 3. Each node of the first and last layers have self-loops. The node v 4 1 has a movement edge to all nodes of G.

-Communication The node v 4 n has a communication edge to all nodes of G and all nodes of the fourth layer. We create a communication edge between v 2 i to t i , for all 1 ≤ i ≤ n. We create a communication edge between v 3 i and v 3 i+1 , for all 1 ≤ i < n. Finally, we connect in communication the nodes of the first layer and the node v 3 1 to the base B. 1 1 , . . . , v 1 n . We now show that the instance (G, B, n, t) of CMAPF UND is feasible if and only if the instance (G , B, 2n, s) of CMACP-init UND is feasible.

Formally, given (G, B, n, t) with G = V, E m , E c with base B, we define (G , B, 2n, s) where G = V , E m , E c with base B where: -V := V {v 1 1 , . . . , v 1 n , v 2 1 , . . . , v 2 n , v 3 1 , . . . , v 3 n , v 4 1 , . . . v 4 n } -E m is the symmetric closure of ∪E m ∪ {(v, v 4 1 ) | v ∈ V } ∪ {(v 1 i , v 1 i ), (v 1 i , v 2 i ), (v 2 i , v 3 i ), (v 3 i , v 4 i ), (v 4 i , v 4 i ) | i ∈ {1, . . . , n}} -E c is the symmetric closure of E c ∪ {(B, v 1 1 ) . . . (B, v 1 n )} ∪ {(t 1 , v 2 1 ), . . . , (t n , v 2 n )} ∪ (B, v 3 1 ), (v 3 1 , v 3 2 ), . . . , (v 3 n-1 , v 3 n ) ∪ (v 4 1 , v 4 n ) . . . (v 4 n-1 , v 4 n ) ∪ {(v 4 n , v) | v ∈ V } ; and s = B, . . . , B, v
(⇒) Suppose the configuration t is reachable in G. Let us construct an execution starting at s in G that cover all nodes in G . First, the first n agents reach configuration t, while the other n agents stay at layer v 1 i using the self-loops. After that, the first n agents stay at t while the others progress to the fourth layer v 4 i . Finally, while the agents at v 4 2 to v 4 n don't move using the self loops, the agent at v 4 1 covers the whole graph since the presence of an agent at v 4 n makes sure that all nodes of G are connected to other agents and to the base. Once finished, this agent can go back to v 4 1 and the n agents can return back to the layer 1 as initially. Finally, the n agents occupying configuration t can go back to B by following the same path in reverse. This constitutes a covering execution for CMACP-init UND .

(⇐) Assume that G can be covered, and let T denote the first time v 4 n is visited. The agent at v 4 n can only be at v 3 n at time T -1. Thus, the nodes v 3 1 , . . . , v 3 n-1 must also be occupied due to connectivity constraint. Then, at time T -2, all n agents were on the second layer v 2 i . In fact, the layer 4 must be empty at this point by the choice of T and due to connectivity edges (and note also that there are no self-loops on the third layer). But since each node v 2 i is only connected to t i , at time T -2 the other n agent must be at configuration t. This concludes the proof.

CMAPF-init UND CMAPF-init UND CMAPF UND CMACP-init UND
Theorem 4.4. CMACP UND is PSPACE-complete.

Proof. The upper bound comes from Proposition 4.1. We present the lower bound, which is by reduction from CMACP-init UND . We map a CMACP-init UND -instance (G, n, s) to the CMACP UND -instance (G , n + 2) of where G is defined as in Figure 4.3 (ignoring vertices t 1 , . . . , t n ). The formal description is given in the proof of Theorem 4.3.

We show that instance (G, n, s) of CMACP-init UND is feasible iff instance (G , n + 2) of CMACP UND is feasible. The proof is very similar to the proof of Theorem 4.3. The first n agents are used for the execution in G while the two others operate in the gadget.

(⇒) If G can be covered starting from s then in G , the agents can first reach s as described in proof of Theorem 4.3, then follow the same plan to cover the graph, and execute the plan in reverse to come back to s and then back to B . Meanwhile, the two others reach t n+1 and t n+2 loops there and come back to B .

(⇐) Assume there is a covering execution in G from base B . We already proved in Theorem 4.3 (Fact 1) that from configuration B , . . . , B the agents necessarily go through configuration s 1 , . . . , s n , t n+1 , t n+2 to go in G. In the proof of Fact 1, observe that before t n+2 is first occupied no s i can ever have been occupied, since these nodes are connected to B only through t n+2 . Hence the next configuration where all s i are occupied is the first visit of any agent to any s i . Said otherwise, and generalizing to other instants when t n+2 starts being occupied, agents always enter G at s 1 , . . . , s n together. With a dual reasoning, one can see that always leave G together. Hence, the execution in G , minus the steps in the gadget, can be reproduced in G.

We conclude this section by depicting, in Figure 4.5, the reductions used and the proof scheme. The dotted arrows represent the unmentioned corollaries.

B = c i 0 c i 1 c i 2 c i 3 c i 4 c i 5 c i 6

Sight-Moveable Topological Graphs

The main challenge in deciding whether there exists a connected plan is to verify that the given number of agents can visit a node of the graph while staying connected. Indeed, to visit a location connected to, say, the base, an agent might have to rely on multiple other agents. Hence, if we can guarantee that whenever two locations are connected we can move an agent from one to the other without the need of an extra relay, the problem becomes "easy". This assumption underlies the definition of sight-moveable topological graphs. Interestingly, the unbounded decision problems CMAPF SM and CMACP SM are in LOGSPACE and NLOGSPACE, respectively. Unfortunately, the bounded version bCMAPF SM is NP-complete. At the end of the section, we discuss a relaxation method based on this class of graphs.

Upper Bounds

Let us call USTCONN (resp. STCONN) the problem of determining whether two nodes of a given undirected (resp. directed) graph are connected. The algorithms presented in this section rely on the following complexity result: Proof. Let us define the problem UCONN as that of checking whether a given undirected graph is connected. By Theorem 4.5, this problem is in LOGSPACE since it suffices to check the connectivity between all pairs of nodes in LOGSPACE.

We are going to reduce CMAPF SM to UCONN in logarithmic space.

Let G = V, E m , E c a sight-moveable topological graph and c a configuration. Let V = {c 1 , . . . , c n , B}. We show that the configuration c is reachable iff the restriction of G := (V, E c ) to the nodes in V is a connected graph. It is clear that this condition is necessary since if G is not connected then the agents cannot occupy configuration c.

Conversely, assume that G is connected. Then, let us order the nodes B, c 1 , . . . , c n into c i 0 , c i 1 , c i 2 , . . . , c in with c i 0 = B, such that for all 1 ≤ j ≤ n, c i j is connected to some c i k with 0 ≤ k < j; such an order exists, and can be obtained by breadth-first search in a E c -spanning tree of V at root B, see Figure 4.6 for an example.

We then construct an execution for reaching the configuration c as follows. The construction is by induction on 0 ≤ j ≤ n: at step j, the first j agents occupy nodes c i 1 , . . . , c i j . The base case j = 0 is the empty execution. For j ≥ 1, let k < j such that (c i k , c i j ) ∈ E c . We send the j-th agent to c i k following the path that has been constructed earlier, by induction. We then move that agent to c i j following a path that stays connected with c i j , which exists by the sight-moveable property, the other agents either stay at c i 0 or at their respective c i j by using the self-loops.

Thus, (G, n, c) is a positive CMAPF SM -instance iff G is a positive UCONN-instance. The reduction is in logarithmic space: we compute G by enumerating all E c -edges (u, v) in G, and we output (u, v) when u, v ∈ V . We recall that we only take into account the working memory for computing G ; the output -G itself -is not taken into account in the used space (see e.g. [START_REF] Sipser | Introduction to the theory of computation[END_REF], Ch. 8, Def. 8.21).

Before giving the complexity of CMACP SM , we need the following intermediary result. Let us call Bounded-USTCONN the following problem: given an undirected graph G, two nodes s, t, an integer n, decide whether there is a path of length at most n from s to t in G. Note that, whatever the encoding of n is, the problem Bounded-USTCONN can be decided in logarithmic space.

Lemma 4.2. Bounded-USTCONN is in NLOGSPACE.

Proof. We reduce Bounded-USTCONN to STCONN in logarithmic space as follows. From a Bounded-USTCONN instance (G, s, t, n) we construct in logarithmic space a STCONN instance (G , s , t ):

1. The nodes of G are pairs (v, j) where v is a node of G and j ∈ {0, 1, . . . , m} where m is the minimum of n and the number of nodes of G.

2. The graph G contains an edge between (v, j) and (v , j + 1) when there is an edge between v and v in G or when v = v ;

3. s = (s, 0) and t = (t, n).

The STCONN instance (G , s , t ) can be computed in log-space.

Step 1 requires to store the current node v of G to be processed and an integer j written in binary, that is of size log m. Importantly, as m is smaller than the number of nodes in G , the representation of m is logarithmic in the size of the input. For this reason, note that the overall spatial complexity does not change even if the encoding of n is in binary.

Proposition 4.4. CMACP SM is in NLOGSPACE.

Proof. Let G = V, E m , E c be a sight-moveable topological graph and n an integer written in unary. We prove that for all vertices v, there is a path of length at most n from v to the base c in the communication graph iff (G, n) is a positive instance of CMACP SM . One direction is obvious: if (G, n) is a positive instance, then all vertices must within a distance of at most n from the base in the communication graph; otherwise no connected configuration can visit that vertex. Assume that all vertices are within a distance of n from the base. For any vertex v, consider path v 1 , . . . , v k in the communication graph, with v 1 = c, v k = c, and such that

(v i , v i+1 ) ∈ E c .
We apply the construction of Proposition 4.3 to build an execution from configuration c n to some configuration where k agents occupy {v 1 , . . . , v k }, and others stay at c. We now extend this execution to "roll back" so that all agents return to the base. We first let the agent at v k , go to v k-1 : this is possible by the sight-moveable property and since (v k , v k-1 ) ∈ E c . Then the two agents together move to v k-2 , and so on, until all come back to c. We can now combine these executions to cover all vertices, and let agents end in the base. Thus, the algorithm consists in checking sequentially, for all v, that ((V, E c ), v, c, n) is a positive instance of Bounded-USTCONN. Hence, we obtain a non-deterministic algorithm in logarithmic space to decide CMACP SM .

Lower Bounds

We now focus on the NP lower bound of bCMAPF SM .

Theorem 4.6. bCMAPF SM is NP-complete even for a fixed execution length ≥ 3. B Proof. The upper bound comes from Proposition 4.2. The lower bound proof is by polynomial time reduction from 3-SAT problem (see [START_REF] Karp | Reducibility Among Combinatorial Problems[END_REF]). Given a 3-SAT instance, set of clauses c 1 , . . . , c m with variables x 1 , . . . , x n , we describe the construction of an instance (G, k, c) of bCMAPF SM with k = n + m agents.

B v c i c i g c i (a) Clause gadget B v x i v ¬x i x ¬x g x (b) Variable gadget
v x 1 v ¬x 1 x 1 ¬x 1 g x 1 v xn v ¬xn x n ¬x n g xn v c 1 c 1 g c 1 v cm c m g cm
The topological graph G = V, E m , E c is constructed as follows. We start by placing the base B from which the agents start their mission.

Please recall that in a sight-moveable graph all movements edges have a respective communication edges, thus in the construction below we do not explicit them.

For each variable x, we construct a gadget composed of 5 nodes connected to the base depicted in Figure 4.7b: nodes x i , ¬x i , staging nodes v x i , v ¬x i and a goal node g x i . We add movement edges from B to v x i , from v x i to x and from x to g x i (resp. from B to v ¬x i , from v ¬x i to ¬x i and from ¬x i to g x i ). As for the communication, the node x i (res. ¬x i ) communicates with the base.

For each clause c j , we construct a gadget composed of 3 nodes depicted in Figure 4.7a. We create a node c j , a staging node v c j and a goal node g c j . We add movement edges from B to v c , from v c j to c j and from c j to g c j . The communication between a clause c j and a literal x i or ¬x i is dictated by the existence of the literal in the clause. We do not use direct communication edges because the obtained topological graph should be sight-moveable. Instead, we use fully connected paths of length 4. Such a path between -let say -x i and c j consists three intermediate nodes p 1 ij , p 2 ij , p 3 ij , such that there is a path made up of movement edges from x i to c j , passing throw p 1 ij , p 2 ij , p 3 ij . Furthermore, we suppose that the nodes x i , p 1 ij , p 2 ij , p 3 ij and c j form a clique w.r.t. to the communication edges. Now, there is a fully connected path of length 4 between x i and c j if and only if x i ∈ c j ; and there is a fully connected path of length 4 between ¬x i and c j if and only if ¬x i ∈ c j .

We add movement edges from g x i to g x i+1 , and from g c j to g c i+1 for all 1 ≤ i < n, as well as from g xn to g c 1 . Last, we add a fully connected path of length 4 from g x 1 to the base such that (g x 1 , B) ∈ E c , in the sense that all nodes of this path have communication edges between them. This translation is polynomial in the number of clauses and variables. The construction is depicted in Figure 4.8. The snake-like path from g x 1 to B is a fully connected path of length 4.

From a 3-SAT instance, one can construct the graph G and ask for an execution of length 3 to reach the configuration g x 1 , . . . , g xn , g c 1 , . . . , g cm . Formally, the topological graph G = V, E m , E c is defined by: agent in one of its literals. This is the case since val satisfies the formula. In the third step of the execution, agents go to states g x i and g c i . Here, the connection with the base is ensured since g x 1 is connected to it, and g x 2 is connected to g x 1 , g x 3 is connected to g x 2 and so on.

This execution is thus a solution of bCMAPF SM with bound = 3.

(⇐) We show that if in the graph G there exists an execution of at most 3 steps constructed from a 3-SAT instance, then the instance is satisfiable. Let us assume that we have an execution e of at most 3 steps with the last configuration being g x 1 , . . . , g xn , g c 1 , . . . , g cm .

The only shortest path from B to g c i is of length 3 and goes through v c i . For states g x i , the only shortest paths are also of length 3 and go through either v x i or v ¬x i . Thus, in order to reach the given target configuration, at the initial step, agents must cover the states v c i and either v x i or v ¬x i for all i, j. At the second step, following the above mentioned shortest paths, agents will be at states c i and either x i or ¬x i depending on the staging nodes they were occupying. The last step is the target configuration. Since the agents are connected at the second, it follows that for each clause c j , the state corresponding to some literal of c j is occupied by an agent. Thus, the valuation on variables encoded by the choices of the agents satisfies the 3-SAT instance.

Relaxation

For unbounded reachability and coverage, it seems tempting to take advantage of efficient algorithms on sight-moveable topological graphs (Proposition 4.3 and 4.4). In this subsection, we propose a transformation of a topological graph into a sight-moveable sub-graph. This transformation leads to a relaxation method: a solution found in the obtained sight-moveable topological graph still holds in the original graph.

This transformation requires the original graph to already satisfy properties 1 and 2 of Definition 4.3. If not, (1) we remove movement edges (v, v ) ∈ E m that are not in E c , (2) we remove all nodes without a self-loop.

Algorithm 1 Transformation into a sight-moveable topological graph

Require: A topological graph G = V, E m , E c satisfying properties 1 and 2 of Definition 4. v := Q.pop()

6: for all v | (v , v ) ∈ E m do 7: if (v, v ) ∈ E c then 8: C := C ∪ {(v, v )} 9: Q := Q ∪ {v } 10: E c := {(v, v ) | (v, v ) ∈ C and (v , v) ∈ C or v = v} 11: return V, E m , E c
The simple transformation, given in Algorithm 1, prunes the communication edges which do not respect the property 3 of sight-moveable topological graphs, described in Definition 4.3. We now show this transformation outputs a sight-moveable topological graph.

Theorem 4.7. Algorithm 1 constructs a sight-moveable topological graph.

For simplicity, we say that a node v is sight-moveable to a node v iff there exists a sequence ρ = ρ 1 , . . . , ρ n of nodes such that v = ρ 1 , v = ρ n , (v, ρ i ) ∈ E c and (ρ i , ρ i+1 ) ∈ E m for all i ∈ {1, . . . , n -1}. Algorithm 1 consists in running a breadth-first search from each vertex, and marking all reachable vertices v to which v is sight-moveable. The communication edges are kept if the sight-moveable property was shown to hold in both directions.

Proof. First, given a node v, we show that the queue Q contains only nodes that v is sightmoveable to.

Invariant Given v, let

I v : for all v ∈ Q, v is sight-moveable to v .
Proof. Before entering the while loop, at Line 3, the queue Q contains only v. Hence, the Invariant I v is initially satisfied. Let us suppose that Invariant I v holds after an arbitrary number of loop iterations. If Q is empty, Invariant I v holds. Otherwise, a node v is popped out of Q. If a successor of v communicates with v then we add the successors of v to Q. Invariant I v holds since v is sight-moveable to v , by induction, and

(v, v ) ∈ C.
We add a pair

(v, v ) to C iff v was in Q and (v, v ) ∈ E c . Hence, given Invariant I v , (v, v ) ∈ C iff v is sight-moveable to v . Finally, E c is the set of pairs (v, v ) such that (v, v ) ∈ C and (v , v) ∈ C, that is v is sight-moveable to v
and v is sight-moveable to v. Therefore, the graph returned by Algorithm 1 is sight-moveable. This relaxation offers the opportunity to verify efficiently if a topological graph contains a solution. It is worth noting that the original topological graph might admit a solution, while no solution is found by the relaxation.

We illustrate the usage of the relaxation on the following maps, depicted in Figure 4.9, previously used by Tateo et al. [START_REF] Tateo | Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It[END_REF], for the study of their algorithms. We use a similar discretization of the maps, i.e. the nodes of the graph are obtained by cells of 11×11 pixels for Office and 13×13 for Open, and we assume the communication range to be of 100 pixels. In addition, we use the same discretization with cells of 15×15 pixels for Coast, a map from the Benchmarks for Grid-Based Path-Finding [START_REF] Sturtevant | Benchmarks for Grid-Based Pathfinding[END_REF], with an identical communication range.

We show, in Figure 4.10, the size of each component of the graphs obtained after discretization and the impact of the relaxation. The relaxation of Office removes up to 18% of the communication edges. We can observe that most of the communication through the walls, allowed by the communication range, will be removed in the relaxation since the sight-moveable property cannot be ensured. In particular the large room in the center loses a lot of communication edges with its surrounding. However, the relaxation of Open removes only 0.2% of the communication due to its small number of obstacles. Finally, the relaxation does not remove any communication edges from the discretization made of Coast.

Intuitively, the relaxation removes communication links between two vertices which cannot be connected by maintaining communication. In fact, if a node communicates through an obstacle, then the sight-moveable property requires it to have a bypass path that remains connected. This is why, in the Office map, in particular at the borders of the central room, most communication links through walls are removed by the algorithm. But if the size of the obstacles is larger than the communication range, then there will be mostly no communication through obstacles, and it is unlikely that the relaxation will remove any communication edges: this can be observed on the Coast map where no edge is removed by the algorithm.

Thus, in open maps such as cities, forests etc., we expect that our relaxation removes a few edges and preserves the feasibility of our problems. It might however remove more communication edges, rendering the problems infeasible in indoor applications (inside of buildings, mazes, etc.). We leave the empirical evaluation of this relaxation for future work.

Complete-Communication Topological Graphs

The following result relies on the fact that the communication is complete.

Proposition 4.5. bCMAPF CC is in NLOGSPACE.

Proof. We refer to Lemma 4.2. Indeed, given a configuration c and ∈ N, the straightforward iteration on the locations c i followed by the verification of a path of at most (given in unary) steps from B to c i yields a sound and complete algorithm for bCMAPF CC .

Our NP lower bound proof of the bCMACP CC problem is by reduction from the grid Hamiltonian cycle (G-HC) problem which is the Hamiltonian cycle problem restricted to grid graphs and is NP-complete [START_REF] Itai | Hamilton Paths in Grid Graphs[END_REF]. We use this particular version of the Hamiltonian cycle problem for simplicity of the proof. Furthermore, we obtain a lower bound on the bCMACP CC problem with a grid movement graph. Theorem 4.8. Even restricted to grid graphs, bCMACP CC is NP-complete for a fixed number of agents n ≥ 1.

Proof. The upper bound follows from Proposition 4.2.

We give a polynomial-time reduction from the G-HC problem. Consider an instance of G-HC denoted G = V, E .

Consider the sight-moveable topological graph G = V, E m , E c with undirected movement E m = E and E c = V × V and associate a single agent and the bound |V | to the bCMACP CC instance. We call a simple cycle containing all vertices a tour. We prove that there exists a tour t in G iff there exists a covering execution of length |V | in G .

(⇒) Any tour of G is a valid execution satisfying bCMACP CC since the communication edges form a complete graph, and the bound is |V |.

(⇐) Let us suppose that we have an execution of length |V | which covers the graph G . The execution starts and ends at B and visits all nodes in |V | steps. Hence, the execution visits all nodes only once and is a cycle in the graph.

In Figure 4.11, we depicted the results obtained in this section and in Section 4.6.

Variants

Variants

In this section, we introduce several variants and study their impact on the complexity.

Bounded Reachability and Coverage with Binary Bounds

Our membership NP proofs for the bounded versions of the reachability and coverage problems rely on the unary encoding of the bound given in input. It is relevant to investigate the impact of providing that bound in binary on the complexity of the problems.

We show that both problems bCMAPF DIR and bCMAPF UND with the bound written in binary are both PSPACE-complete. The membership to PSPACE can be shown as in Proposition 4.1: since a binary counter can be added to count up to . For bCMAPF UND , the PSPACEhardness follows from a reduction from CMAPF UND , whose PSPACE-hardness is established in Theorem 4.3. Indeed, any instance of CMAPF UND can be reduced to bounded reachability with bound = |V | n . In fact, if CMAPF UND has a solution, then there is a plan of length at most |V | n . Indeed, in the worst case, the agents must go through all configurations possible in the graph. This number can be computed in polynomial time and represented in binary. The same argument is used to show the PSPACE-hardness of bCMAPF DIR by reduction from CMAPF DIR whose PSPACE-hardness was proved by Tateo et al. [START_REF] Tateo | Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It[END_REF] (see Theorem 4.2).

Theorem 4.9. The variants of bCMAPF DIR and bCMAPF UND with written in binary are PSPACE-complete.

A similar argument can be used to show the PSPACE-hardness of the problems bCMACP UND and bCMACP DIR . In fact, if there is a covering execution, then there must be one of length at most |V | n × (|V | + 1). Indeed, the agents must traverse at most the |V | n possible configurations to reach each node of the graph and go back to the base, which means an upper bound of |V | n × (|V | + 1) for the whole execution. This bound can be written in binary in polynomial space, so PSPACE-completeness also holds for these problems.

Theorem 4.10. The variants of bCMACP DIR and bCMACP UND with written in binary are PSPACE-complete.

Weighted Movement Graph

An interesting extension is obtained by assigning costs to edges of the movement graph, and considering the bounded reachability problem with respect to the total cost of the execution.

Consider a weighted topological graph G = V, E m , E c , cost , where for each edge cost(e) is the cost of e, a positive integer.

One could consider several ways of aggregating the weights along executions. We consider the case where the weights correspond to travel times between vertices, and the goal is to minimize total travel time, which also implies minimizing battery usage in drone applications. We consider a synchronous setting where all agents synchronize at each configuration in the plan; therefore, the travel time between two configurations is the maximum of the weights of the edges along which agents travel. In other terms, we assume that agents wait for each other at each step of the execution.

Formally, for an execution c 0 , c 1 , . . . , c k , the total cost is defined as follows:

k-1 i=0 max j∈{1,2,...,n} cost(c i j , c i+1 j ), (4.1)
where c i j denotes the vertex occupied by agent j at configuration c i . Assuming binary encoding of all weights, we are interested in checking the existence of an execution of bounded cost, and that of a covering execution of bounded cost.

When weights are encoded in unary, both reachability and coverage problems are NP-hard since when all costs are equal to 1, then the problems are identical to bCMAPF and bCMACP, respectively. Since all weights are natural numbers, the length of the execution is not more than the cost bound given in input. Thus, similarly to Proposition 4.2, one can guess an execution and bound its length with a polynomial number of guesses. When the weights are encoded in binary, then the problems are PSPACE-hard as shown in Section 4.7.1; and the PSPACE algorithms can be extended to establish PSPACE-completeness.

Theorem 4.12. The weighted variants of bCMAPF, bCMACP on directed and undirected topological graphs with binary encoding are PSPACE-complete.

Bounded Disconnection

Another extension consists in allowing the agents to be disconnected for a bounded number of steps along the execution. Such a feature can be desirable in order to allow the agents to reach difficult locations where communication cannot be guaranteed. By bounding the disconnection time, the connection with the base is only disturbed temporarily.

This extension is also PSPACE-complete. In fact, our membership results can easily be extended both for reachability and coverage problems. For PSPACE-hardness, observe that when the allowed bound is 0, the problems become identical to our setting, so all hardness proofs carry over.

Collisions

Collision constraints consist in disallowing several agents to share the same location at a given time, and provide an interesting extension of our setting. In our case, we allow several agents to be at the base but not at other nodes.

The PSPACE-completeness results hold by using the same reductions used for the proof of Theorems 4.3 and 4.4 from the collision-free variant problem of Tateo et al. [START_REF] Tateo | Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It[END_REF]. Indeed, the reductions gadgets used are collision-free, and thus we obtain: Theorem 4.13. The variants with collision constraints of the problems CMAPF UND , CMAPF DIR , CMACP UND and CMACP DIR are PSPACE-complete.

We can show that when the topological graph is sight-moveable, then the complexity of deciding the reachability and coverage without allowing collisions is unchanged. We use the same membership proof of Proposition 4.3 and 4.4. Indeed, a positive instance of CMAPF SM (resp. CMACP SM ) is a positive instance of CMAPF SM (resp. CMACP SM ) with collision constraints. In order to obtain a collision-free execution, it suffices to modify as follows: we consider an ordering, as depicted in Figure 4.6, and consider each branch one by one. For each branch, we dispatch first the agent with the furthest target from the base, followed by the second furthest agent and so on. This yields a collision-free execution for CMAPF SM . CMACP SM can be solved by a repeated application of CMAPF SM . Observe that CMAPF CC and CMACP CC can use the same algorithms. Regarding the bounded versions, the membership of Proposition 4.2 hold without allowing collisions. Indeed, checking if the path contains a collision can be done in polynomial-time. The lower bound can be showed by reduction from the MAPF problem to bCMAPF CC . Additionally, the proof of Theorem 4.8 holds without allowing collisions given that the proof holds for a single agent.

Theorem 4.15. The variants of bCMAPF and bCMACP without collisions are NP-complete for all ∈ {UND, DIR, SM, CC}.

Planar Movement Graphs

One could wonder whether the complexity of these problems change when restricted to topological graphs whose movement graphs are planar. This is an interesting question since in targeted applications the graphs are indeed planar; and some problems are known to become easier on planar graphs (e.g. the shortest path computation [START_REF] Philip | Shortest Paths in Directed Planar Graphs with Negative Lengths: A Linear-space O(N Log2 N)-time Algorithm[END_REF]). In this section, we show that our reductions proving the PSPACE-hardness of CMAPF UND , CMACP-init UND , CMACP UND and CMAPF SM use planar graphs, which means that these hardness results hold even when the input is restricted to planar graphs.

Actually, the proof of CMAPF-init UND , by Tateo et al. [START_REF] Tateo | Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It[END_REF], uses a planar movement graph. They even prove a stronger result: the reachability problem is PSPACE-hard even for graphs that are disjoint unions of paths 2 .

Let us consider an instance (G Reach init , B, s, t) of CMAPF-init UND where G Reach init is a topological graph that is a disjoint union of paths (depicted in the middle of Figure 4.12), B is 2. Their reduction is from a problem called the reconfiguration problem on constraint graphs. The topological graph computed from a constraint graph contains single nodes ( ), paths of length 3 (which we denote by

) and a single path graph of length |E| (denoted by . . . ), with E the set of edges in the constraint graph. its base, s = (s 1 , . . . , s n ) is initial configuration for n agents, depicted at the bottom of G Reach init in Figure 4.12 and t = (t 1 , . . . , t n ) is the target configuration (the target nodes t 1 , . . . , t n are in G Reach init as defined by Tateo et al. [START_REF] Tateo | Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It[END_REF] but are not displayed in the figure). Then as shown in Figure 4.12, the gadgets we proposed in this contribution can all be arranged to obtain planar graphs as well.

G Reach init G Reach G Cover init G Cover B B v 1 v 2 v n v 1 v 2 v n v n+1 v n+2 v n+1 v n+2 s 1 s 2 s n t n+1 t n+2 v 1 1 v 1 2 v 1 n+2 v 4 1 B v 1 . . . v n+2 v n+2+1 . . . v n+2+n+2 v n+2+n+3 v n+2+n+4 v 1 . . . v n+2 v n+2+1 . . . v n+2+n+2 v n+2+n+3 v n+2+n+4 t n+2+n+3 t n+2+n+4
1. The gadget given in Figure 4.3, used in the proof of Theorem 4.3 is a planar graph; in fact, it can be arranged, to obtain G Reach (in Fig. 4.12) whose base is B and is designed for n + 2 agents. This proves that CMAPF UND is PSPACE-hard on planar graphs.

2. We consider now the reduction of Figure 4.4 used in proof of Lemma 4.1, which contains G Reach . This reduction, named G Cover init in Figure 4.12 is also planar. The base of this graph is still B , and it is designed for n + 2 + n + 2 = 2n + 4 agents. In this reduction, the first n + 2 agents start in B while the others start in v 1 1 , . . . , v 1 n+2 . Indeed, the latter gadget is disconnected from the rest of the graph, except that the node v 4 1 has a movement edge to all nodes in the graph. One can observe that a movement edge can be created from v 4 1 to all nodes in the graph G Reach , while keeping the construction planar, thanks to the particular structure of G Reach . This shows that CMACP-init UND is PSPACE-hard on planar graphs.

Finally, we can add the gadget of

Conclusion

We have studied numerous variants of the defined problems in the hope to give a complete overview of this new extension of the MAPF problem. We provided a thorough study of coordination problems under connectivity constraints for reachability and coverage. This study carves an initial map of the complexity and the difficulties that can rise while solving such problems.

We still lack results for some of these variants. Furthermore, it is also unclear whether the combination of these variants can yield higher complexity. Additionally, there are still many variants of MAPF that have not been extended to these problems.

An important result of this chapter is the introduction of sight-moveable topological graphs. Indeed, being able to decide in NLOGSPACE whether the reachability or the coverage can be done is an important improvement over the previous results. However, the optimization of the execution cannot be solved in a easier manner in this class.

In realistic situation, the topological graph may not be fully known in advance. Indeed, the discretization may not represent faithfully the area in which the agents evolve. Thus, we attend to extend this work to incomplete knowledge in which the agents only have an overapproximation of the actual topological graph. While the agents move around the area they can observe the graph and update their knowledge.

Finally, not only can the area be partially known by the agents, but some mishaps can happen during the mission. Indeed, an external actor might disable an agent and, in this setting, the group of agent should have to find the agent or finish the mission without it. In the weighted graph extension (Subsection 4.7.2), mishaps can also be due to strong wind which modifies the cost of the movement. CHAPTER 5

CONNECTED-CONFLICT-BASED SEARCH

Introduction

In this chapter, we study an optimal decoupled algorithm for CMAPF that can be extended to the collision-avoidance requirement. Our algorithm is an adaptation of CBS [START_REF] Sharon | Conflict-Based Search for Optimal Multi-agent Path Finding[END_REF][START_REF] Sharon | Conflict-based search for optimal multi-agent pathfinding[END_REF] to handle connectivity constraints. We thus present the first optimal algorithm that handles connectivity in this setting.

Both MAPF and CMAPF could be solved offline as a single-agent search with A* [START_REF] Peter E Hart | A formal basis for the heuristic determination of minimum cost paths[END_REF]. However, this would be exponential in the number of agents and available moves. This coupled approach is computationally intensive and less effective, in general, than a decoupled approach in which paths of the agents are computed separately. This is the approach taken by CBS to solve MAPF. CBS computes optimal paths for each agent separately; and when a collision between two agents is detected at a location at a given time step, it enforces one of the agents away from that location at that time. Numerous improvements have been introduced to CBS [START_REF] Boyarski | ICBS: Improved Conflict-Based Search Algorithm for Multi-Agent Pathfinding[END_REF][START_REF] Felner | Adding Heuristics to Conflict-Based Search for Multi-Agent Path Finding[END_REF][START_REF] Li | Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search[END_REF][START_REF] Li | Disjoint Splitting for Conflict-Based Search for Multi-Agent Path Finding[END_REF][START_REF] Li | Symmetry-Breaking Constraints for Grid-Based Multi-Agent Path Finding[END_REF].

Our contribution is an optimal algorithm called Connectivity-Conflict-Based Search (CCBS) to solve CMAPF. The main structure of the algorithm is based on CBS with new enhancements to deal with the particular challenges of CMAPF. Observe that CBS deals with collision conflicts between two agents by enforcing one of the agents to move away from the location of the collision. In CCBS, connectivity conflicts correspond to disconnected configurations, that is, configurations where the agents do not form a connected subgraph. Resolving such a conflict is more tricky: a connectivity conflict can involve several agents (i.e. one may need to relocate several agents to obtain a connected configuration) and a single disconnected agent may not be the source of the conflict. Thus, unlike CBS, our algorithm may need several steps to resolve a connectivity conflict.

Outline Section 5.2 presents our algorithm. Section 5.3 contains the correctness and optimality proofs. Section 5.4 presents experiments, and we conclude and discuss the many possible extensions of this work in Section 5.5.

Connected-Conflict-Based Search

In this section we describe our algorithm called Connectivity-Conflict-Based Search (CCBS) for CMAPF. Let us first introduce an example used to illustrate some notions during the presentation of our algorithm.

v 1 v 2 v 3 v 4 v 5 v 6
Movement edges Communication edges The execution

([v 1 , v 2 , v 3 ], [v 4 , v 5 , v 6 ]
) is not connected. Indeed, at the second step the configuration is v 2 , v 5 : no communication edge exists between v 2 and v 5 . However, the execution

([v 1 , v 2 , v 3 , v 3 ], [v 4 , v 4 , v 5 , v 6 ]) is connected since the configurations v 1 , v 4 , v 2 , v 4 , v 3 , v 5
and v 3 , v 6 are connected. This execution is actually an optimal solution of this CMAPF instance and is of cost 4.

Our algorithm is inspired by the general concept of CBS [START_REF] Sharon | Conflict-based search for optimal multi-agent pathfinding[END_REF] which solves MAPF by finding an optimal collision-free execution (without any connectivity constraints). CBS solves the MAPF problem in a decoupled manner by computing separately the path of each agent and progressively repairing the resulting execution by constraining agents away from collision locations. CBS is correct and optimal, that is, it finds a collision-free execution with minimum cost whenever there is at least a solution, and, as shown by Sharon et al. [START_REF] Sharon | Conflict-based search for optimal multi-agent pathfinding[END_REF], it can be made complete by the addition of a polynomial procedure [START_REF] Yu | Pebble Motion on Graphs with Rotations: Efficient Feasibility Tests and Planning Algorithms[END_REF], that is, it can also detect the absence of solution.

Similarly to CBS, CCBS is composed of two levels, the high-level constructs a constraint tree which searches for the right set of constraints to add; and the low-level computes singleagent paths satisfying given constraints.

Definition 5.1 (Constraint).

A positive constraint is a tuple denoted by a, v, t where a is an agent, v a vertex, and t a time step.

Intuitively, a positive constraint a, v, t means that agent a must be at vertex v at time step t. Formally, given an execution exec, the path exec a for agent a is consistent with such a constraint if exec a [t] = v. An execution exec is consistent with a set of constraints if all paths exec a are consistent with all constraints in the set.

Notice the difference with CBS [START_REF] Sharon | Conflict-based search for optimal multi-agent pathfinding[END_REF] which only uses negative constraints, while we use positive ones. Positive constraints were already also used by Li et al. [START_REF] Li | Disjoint Splitting for Conflict-Based Search for Multi-Agent Path Finding[END_REF] for collision constraints only.

We will say that an execution exec has a connectivity conflict at time t, if there exists t such that exec[t] is a disconnected configuration.

The High-Level: The Constraint Tree

Given an instance of CMAPF G, k, s, g , the high-level of CCBS builds a constraint tree containing constraint nodes.

Definition 5.2 (Constraint Node).

A constraint node n is composed of the following attributes:

1. n.cons -a finite set of constraints; 2. n.exec -an execution; 3. n.cost -the cost of the execution.

Initially, the tree contains a single root node n with an empty set of constraints, an execution composed of a shortest path from s a to g a for each agent a.

If the execution is connected, we return it. Otherwise, we say that the execution contains connectivity conflicts, that is, disconnected configurations. In this case, we split this constraint node as follows: we select (1) a disconnected configuration at a timestep t, (2) and an agent a, and (3) for each vertex v ∈ V , we create a successor constraint node n with constraints n.cons ∪ { a, v, t }; we assign a shortest path for a satisfying these constraints, keep other agents' paths unchanged, and compute the cost of this new solution.

These generated constraint nodes are stored in a priority queue, called OPEN, ordered by the cost of their executions, and we break ties by choosing nodes with the least number of connectivity conflicts. Note that a child node added for a connectivity conflict at time step t may still contain a connectivity conflict at time step t; in fact, one may need to add several constraints (that is, to move several agents) in order to render the configuration connected. When generating children nodes for a connectivity conflict at time t, we thus do not consider agents for which there is already a constraint at time t since this would be either redundant or make the node unsatisfiable.

Note that for each connectivity conflict at time t and an agent a, one of the generated child node constrains agent a to his current location (this is because a child node is created for all v ∈ V ). This allows us to guarantee the optimality of the algorithm; in fact, if the optimal solution requires the agent to remain at his current position, we do keep a branch in the constraint tree consistent with an optimal solution.

We describe the 3 main steps of the high-level algorithm:

(1) Choice of the connectivity conflict Once a constraint node is selected for splitting from the priority queue, we need to select a connectivity conflict, that is, a disconnected configuration in the execution. An execution contains multiple conflicts in general, and the order in which these are addressed can have an impact on the performance of the search. Notice that one may need to modify several paths, that is, add several constraints, in order to render a configuration connected. Each such constraint corresponds to a level in the constraint tree, so several levels may be required to transform a single configuration into a connected one. Intuitively, we would like the search to avoid exploring too deep in the constraint tree too quickly, so we prefer conflicts that require a small number of constraints. We thus select a conflict with the least number of connected components in the communication graph of the configuration. The constraints added to solve such a conflict of course impact other time steps as well. Although these might create new conflicts, they can also solve other conflicts; intuitively, the hope is that the constraints often force the agents to remain close to each other rather than drift apart thus often guide us towards a solution. We empirically observed that this choice improved the performance.

(2) Choice of the agent In the worst case, one might need to relocate almost all agents in order to render a configuration connected. However, this is often not the case. In order to solve a connectivity conflict with a small number of constraints (thus, a small number of levels in the constraint tree), we select an agent in one of the smallest connected components of the communication graph of the configuration. For instance, an agent which seems to be alone and disconnected from the rest of a big group is selected and relocated first.

(3) Reducing the branching factor When splitting a constraint node, we generate a new constraint node for each available position of the selected agent, generating a total of |V | children nodes. Such a branching factor is not practical for an efficient search. Fortunately, most of the positions are often not reachable by the agent at the considered time step given the set of constraints of the node. Hence, the high-level algorithm creates a large number of nodes which are not satisfiable. In order to limit the generation of such nodes, we consider the following two optimizations.

Partial Splitting: The idea of this optimization is that when splitting a node n, we give priority to child nodes that have a better chance of not extending the execution. In fact, given a conflict at time t and agent a, we first only generate successor nodes for each v reachable by a in exactly t steps; and put the parent node n back to OPEN with its cost increased by 1. The next time the node n is selected for splitting, we continue generating nodes for vertices v reachable by a in exactly t-1 steps etc. Notice that the second set of nodes will necessarily increase the cost since they constrain the agent, at time t, to a vertex that they could reach in t-1 steps (while this might be necessary to ensure connectivity). Observe also that a constraint with v only reachable with more than t steps would be unsatisfiable so these are not generated. This optimization is inspired by Enhanced Partial Expansion A* (EPEA*) [START_REF] Felner | Partial-expansion A* with Selective Node Generation[END_REF].

Future constraint: When an agent a is constrained to be at location v at time t, this constrains the first portion of the path to be of length exactly t, and to end in v. Thanks to this simple observation, when addressing a connectivity conflict at time t < t, we can consider only those constraining at locations v at time t such that there exists a path of length t from s a to v , and a path of length t -t from v to v.

Both optimizations can be implemented using multi-value decision diagrams (MDDs) [START_REF] Boyarski | ICBS: Improved Conflict-Based Search Algorithm for Multi-Agent Pathfinding[END_REF]. Indeed, given agent a and cost , MDDs allow one to build a compact representation of all paths of cost for agent a. An MDD has a level for each time step, and level t contains all locations at which the agent a can be at time t along paths that reach the goal location with cost exactly . In particular, if agent a can reach their goal with cost , then level 0 only contains the start location and level only contains the goal location. We denote by MDD a [t] the set of all locations reachable by agent a with cost t along paths of cost that end in the goal. Figure 5.2a (resp. 5.2b) is the MMD of cost 2 (resp. 3) of agent 1 in Example 5.1. Note that MDD 3 1 does not contain the path [v 1 , v 2 , v 3 , v 3 ], as idling on the goal has cost 0, so this path has cost 2.

The overall algorithm is given in Algorithm 2, which shows how the constraint tree is created. It maintains a priority queue OPEN which stores the set of leaf nodes that have not been expanded yet. It runs as long as a solution has not been found and OPEN is non-empty. At each iteration, the best node is picked (Line 3). If this node has no connectivity conflict, it means that a solution is found (Line 4). If the node has connectivity conflicts, then such a conflict

v 1 v 2 v 3 (a) MDD 2 1 v 1 v 1 v 2 v 2 v 3 (b) MDD 3 1

Algorithm 2 High-Level of CCBS

Require: and an agent are chosen and child nodes are created (Lines 6 and 7). The last part of the algorithm shows the bypass optimization from Boyarski et al. [START_REF] Boyarski | Don't Split, Try To Work It Out: Bypassing Conflicts in Multi-Agent Pathfinding[END_REF] which is the following. If a child node n of n has the same cost as n, but has fewer conflicts, then we replace the execution of n by that of n , discard all children, and put n back in OPEN. This allows us to bound the size of the constraint tree.

Topological graph G = V, E m , E c ,

The Low-Level: Constrained Shortest Paths

We use an algorithm similar to the one described by Li et al. [START_REF] Li | Disjoint Splitting for Conflict-Based Search for Multi-Agent Path Finding[END_REF] to compute the constrained shortest paths for individual agents. Given a set of positive constraints, a start and a goal vertex, we use the positive constraints as timely ordered landmarks. We compute a shortest path from the start location to the first landmark using the original low-level of CBS [START_REF] Sharon | Conflict-Based Search for Optimal Multi-agent Path Finding[END_REF] (time-space A*). Then from the first landmark to the second and so on until the goal vertex. No time bound is put on the path to the goal, while one is used on landmarks, which correspond to the times given in the constraints. Remark that if a landmark cannot be reached in the given time then there is no path satisfying the constraints.

Algorithm 3 shows the sub-procedures used in CCBS. CSP is a call to the low-level, that is, CSP(s a , g a , c) returns a shortest path from s a to g a respecting the constraint set c.

Theoretical Analysis

In this section, we discuss the theoretical analysis of CCBS. Both following theorems are similar to the proofs of CBS [START_REF] Sharon | Conflict-based search for optimal multi-agent pathfinding[END_REF].

Lemma 5.1. At any moment during the execution of the algorithm, for all connected executions exec from s to g, there is a node n in OPEN that is consistent with exec.

Proof. Consider such an execution exec. We prove the lemma by induction on the expansion of the search tree in OPEN. At the beginning, the root does not contain any constraints, thus exec is consistent with the root node.

Let us assume that the property is true at step i-1, and let us denote the content of OPEN by n 1 , . . . , n k . At the i-th step of expansion, we choose a node, let it be n 1 . If one of the n 2 , . . . , n k is consistent with exec, then we are done. Otherwise, by induction, n 1 is consistent with exec. Moreover, if n 1 does not have conflicts, we are also done.

Otherwise, assume first that n 1 contains a connectivity conflict. The algorithm creates a child node for each possible position of an agent a at a time t. Hence, a child node is created with the additional constraint a, exec[t], t and added to OPEN. This node is thus consistent with exec. Last, notice that if the bypass optimization is applied, then the node n 1 is put back in OPEN.

Lemma 5.2. At any moment during the execution of the algorithm, for all constraint nodes n, n.cost ≤ cost(exec * (n)) with exec * (n) an optimal execution consistent with n. Proof. The cost n.cost is the sum of the cost of the shortest paths of each agent consistent with their respective constraints in n.cons. Since the path of each agent in the execution exec * (n) also satisfies all constraints n.cons, the inequality follows.

s 1 v 1 g 1 s 2 v 2 g 2
We are now ready to prove the soundness and completeness theorems.

Theorem 5.1 (Soundness). Any solution returned by CCBS is optimal.

Proof. Let exec be an optimal solution. The algorithm returns a solution if it pops a node n from OPEN which contains an execution without conflicts. By Lemma 5.2, we know that n.cost ≤ cost(exec * (n)), and since n.exec has no conflicts, we have n.cost = cost(exec * (n)). Furthermore, Lemma 5.1 shows that exec is consistent with some node n in OPEN at this moment, which means that n .cost ≤ cost(exec). But since the algorithm picks the node with the least cost, we also have n.cost ≤ n .cost. It follows that n.cost ≤ cost(exec), so the returned solution n.exec is optimal.

Theorem 5.2 (Completeness). If there is a solution, CCBS returns a solution.

Proof. Notice first that OPEN never becomes empty until a solution is found by Lemma 5.1. Assume that there is a non-terminating execution, thus generating an infinite constraint tree. We claim that the cost of any leaf at a depth m is at least m k|V | where k is the number of agents. In fact, by construction, there can be at most one constraint per agent and time step, so if t max denotes the maximal time step that appears in all the constraints along the branch up to depth m, then we have m ≤ k|V |t max , that is t max ≥ m k|V | . So the path of some agent has length at least t max . Now consider the node n at which a constraint at t max appears. Since goal configuration g is assumed to be connected, n.exec[t max ] must be different from g. Thus, the path of some agent a has length more than t max . Since this path is a shortest path satisfying the constraints n.cons, the path of agent a at any leaf node below n cannot be shorter. Thus cost at all such leafs is at least m k|V | . In other terms, the cost of each branch diverges to infinity as the branch is extended. This implies that each leaf node is eventually split since it will eventually become the top node in the priority queue. So, at some point, the queue only contains nodes of costs strictly greater than the cost of exec * . By Lemma 5.1, one node n of these nodes is consistent with exec * . We thus have n.cost > cost(exec * ). By definition, we have cost(exec * ) ≥ cost(exec * (n)). Contradiction with Lemma 5.2.

If there is a solution, CCBS returns an optimal solution. However, if there is no solution, CCBS runs forever, as does CBS. For example, consider the instance with two agents given in Figure 5.3. One can observe that there is no connected execution for the two agents. The constraint tree will grow infinitely enforcing the agents to stay at their starting locations.

As done by Sharon et al. [START_REF] Sharon | Conflict-based search for optimal multi-agent pathfinding[END_REF], we may use an algorithm to check the existence of a solution before running CCBS. While this check is in polynomial time in the collision-only case [START_REF] Yu | Pebble Motion on Graphs with Rotations: Efficient Feasibility Tests and Planning Algorithms[END_REF], in presence of connectivity constraints, checking the existence of a solution is PSPACE-complete [START_REF] Tateo | Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It[END_REF].

Experimental Results

In this section, we evaluate the performance of our algorithm and compare it with the two algorithms of Tateo et al. [START_REF] Tateo | Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It[END_REF], namely, the Sample-Based (SB) and Depth-First Search (DFS) algorithms.

The former algorithm creates an execution by, starting from the initial configuration, exploring only a subset of all the possible connected steps by performing random movements. A heuristic then evaluates the "best" state. Then the process is iterated until the "best" state is the goal state. The latter algorithm is, intuitively, similar to iterations of A* of depth 1. More precisely, the algorithm, starting from the initial configuration, searches the "next best connected state", which minimize a heuristic. From this state the process is iterated until it reaches the goal.

The experiments were carried out on 2 benchmark maps, depicted in experimental analysis of Hollinger and Singh [START_REF] Hollinger | Multirobot Coordination With Periodic Connectivity: Theory and Experiments[END_REF] and Tateo et al. [START_REF] Tateo | Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It[END_REF]. Offices is a map of the SDR offices from the Radish data set [START_REF] Howard | The Robotics Data Set Repository[END_REF]. Open is a map of the McKenna MOUT site. The movement edges follow a 4-way grid (i.e. the agents can move in the 4 directions). Concerning communications, we adopted a distance-based one. In distance-based communication, an agent communicates with all other agents within a maximal distance, called the range; the range is displayed below the maps in Fig. 5.4.

All algorithms were implemented in C++ and run on an Intel i7 5600U 2.60 GHz (3.20 GHz) with 8 GB of available memory (out of 16 GB). We used the open source programs published by [START_REF] Tateo | Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It[END_REF] to run their algorithms (which are also in C++). For both maps and for each number n of agents, with n ∈ {2, 3, . . . , 20}, we had 100 instances, and we gave each algorithm 1 minute per instance. The success rate of an algorithm on these benchmarks is defined as the percentage of instances for which it found an execution in the allocated time. Note that CCBS is an optimal algorithm unlike all other algorithms.

The success rate of the algorithms are given in Figure 5.5 for both class of benchmarks. Figure 5.6 depicts the average size of the execution generated by the algorithm.

The two considered maps are of different nature. Open has fewer obstacles, which are moreover thick (these correspond to buildings), and it has many communication edges; Offices has many thin obstacles through which agents cannot move but can communicate.

Instances on Open seems to be easier to solve since all algorithms achieve a higher success rate for a few agents; while CCBS scales better: the success rate of DFS and SB drop consequently after 10 agents, and CCBS stays above 40 %. However, on Office, SB is able to outperforms all algorithms after 10 agents. The performance of CCBS drops very fast on Office. DFS exhibit the same behaviors on both maps, not scaling beyond 10 agents. Now, we can observe that, as shown by Tateo et al. [START_REF] Tateo | Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It[END_REF], SB generates very long executions, while DFS manages to generate shorter executions. However, we can see that DFS rapidly diverges from the optimal execution.

One would expect CCBS to be outperformed in all instances by approximate algorithms. However, quite surprisingly, CCBS is able to outperforms DFS and SB on Open with a relatively high number of agents. This may be the case as the decoupled structure of CCBS allow the generation of an almost-fully connected execution very early in the computation, while DFS must deal with state-explosion since the first step.

Conclusion

We presented CCBS, the first optimal algorithm for CMAPF which, in some cases, outperforms the state-of-the-art algorithms SB and DFS. The execution generated by CCBS are by an order of magnitude shorter than the most successful algorithm SB. On some maps, CCBS is able to scale to higher number of agents than other algorithms will still being optimal. Furthermore, the scalability displayed by CCBS may show that solvers of CMAPF benefit from a decoupled structure.

We believe that the scalability can be improved further by studied the known enhancement previously introduced for CBS. In CBS, a popular and efficient optimization considers cardinal conflicts [START_REF] Boyarski | ICBS: Improved Conflict-Based Search Algorithm for Multi-Agent Pathfinding[END_REF], which are conflicts that can only be solved by increasing the lengths of the paths of all involved agents. This concept led to the integration of powerful heuristics in CBS [START_REF] Felner | Adding Heuristics to Conflict-Based Search for Multi-Agent Path Finding[END_REF][START_REF] Li | Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search[END_REF]. The adaptation of similar concepts for connectivity is however nontrivial. Furthermore, rather than only addressing connectivity conflicts, one could develop a combination of CCBS and CBS in order to solve CMAPF with collision constraints. Indeed, our approach makes it simple to interleave CCBS with CBS to solve connectivity and collisions during the same search. We leave this interesting research opportunity for future works. Our results open a challenging research avenue for developing such optimizations well adapted for both collision and connectivity constraints.

CHAPTER 6

CMAPF IN PARTIALLY-KNOWN ENVIRONMENTS

Introduction

The coordination of mobile agents is at the heart of many real world problems such as traffic control [START_REF] Dresner | A Multiagent Approach to Autonomous Intersection Management[END_REF], robotics [START_REF] Erdem | A General Formal Framework for Pathfinding Problems with Multiple Agents[END_REF][START_REF] Yu | Planning Optimal Paths for Multiple Robots on Graphs[END_REF], aviation [START_REF] Pallottino | Decentralized Cooperative Policy for Conflict Resolution in Multivehicle Systems[END_REF] and more [START_REF] Silver | Cooperative Pathfinding[END_REF][START_REF] Yu | Optimal Multirobot Path Planning on Graphs: Complete Algorithms and Effective Heuristics[END_REF]. Some of these problems have multiple aspects which make them complex: (1) Some systems are multi-agent, that is, the behaviors of agents influence others' and these influences must be taken into consideration when computing missions; this can be due, for instance, to collisions [START_REF] Ma | AI Buzzwords Explained: Multi-Agent Path Finding (MAPF)[END_REF], sensor interferences [START_REF] Goldberg | Interference as a Tool for Designing and Evaluating Multi-Robot Controllers[END_REF][START_REF] Schneider-Fontán | Territorial multi-robot task division[END_REF] etc.; (2) Some missions must ensure connectivity, that is, ensure periodic or constant connection to a station/agent to share acquired information [3]; (3) The environment may be only partially known, and the agents may discover it during the mission [START_REF] Rao | Robot navigation in unknown terrains: Introductory survey of non-heuristic algorithms[END_REF][START_REF] Thrun | Robotic Mapping: A Survey[END_REF]. Several works have considered problems containing these three aspects. For instance, several algorithmic approaches have been investigated to solve the coordination of multi-robot exploration [START_REF] Burgard | Coordinated multi-robot exploration[END_REF][START_REF] Kai M Wurm | Coordinated multi-robot exploration using a segmentation of the environment[END_REF][START_REF] Matignon | Coordinated multirobot exploration under communication constraints using decentralized markov decision processes[END_REF]. Our objective in this contribution is to present a framework to study the theoretical complexity of planning problems with respect to these three aspects.

The theoretical complexity of some related problems have been studied in the literature. MAPF is an important framework introduced to study collision-free navigation of agents in warehouses [START_REF] Felner | Search-based optimal solvers for the multi-agent pathfinding problem: Summary and challenges[END_REF][START_REF] Ma | AI Buzzwords Explained: Multi-Agent Path Finding (MAPF)[END_REF]. This problem was intensively studied and gave rise to a popular algorithm known as CBS [START_REF] Sharon | Conflict-based search for optimal multi-agent pathfinding[END_REF]. An extension of MAPF with connectivity constraints, called CMAPF, was studied as well by Hollinger and Singh [START_REF] Hollinger | Multirobot Coordination With Periodic Connectivity: Theory and Experiments[END_REF]. The complexity of CMAPF and algorithmic solutions were studied in Tateo et al. [START_REF] Tateo | Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It[END_REF] and Charrier et al. [START_REF] Charrier | Complexity of planning for connected agents[END_REF]. However, CMAPF only addresses the multi-agent and connectivity aspects, and not the partial knowledge of the environment. The latter aspect is considered in the CTP, which is a well-known problem to study the navigation of an agent in a partially known graph [START_REF] Papadimitriou | Shortest paths without a map[END_REF]. While the initial framework was for a single agent, CTP has been extended to multiple agents in the settings of packet routing [START_REF] Itai | Adaptive source routing in high-speed networks[END_REF], multi-robot exploration [START_REF] Burgard | Collaborative multi-robot exploration[END_REF] and more [START_REF] Vlad | A System for Multi-Agent Coordination in Uncertain Environments[END_REF]. While a notion of communication was considered by Zhang and Xu [START_REF] Zhang | The k-Canadian Travelers Problem with Communication[END_REF] and Shiri and Salman [START_REF] Shiri | On the Online Multi-Agent O-D k-Canadian Traveler Problem[END_REF], it is limited to settings where all agents can receive information at all times or only designated agents can send information. In contrast, we are interested in studying the setting where agents' ability to communicate depends on their positions in the graph, and in establishing theoretical complexity results of resulting problems.

In this chapter, we study the theoretical complexity of generating plans for a group of agents to reach a given target configuration. More precisely, we analyze the impact of enforcing or ignoring: (A) connectivity; (B) collision; (C) a bound on the length of the execution. For (A), we consider either fully-connected strategies, requiring that the agents remain connected at all times actual graph: they know that some (communication or movement) edges are certain (they must be present), while some are uncertain (they may be absent). Definition 6.1 (Initial Knowledge). The initial knowledge is modeled by a pair of topological graphs (G 1 , G 2 ), with the graph G 1 = V, E m1 , E c1 a lower bound, and G 2 = V, E m2 , E c2 an upper bound on the knowledge about the actual graph with E m1 ⊆ E m2 and E c1 ⊆ E c2 .

The agents initially know G 1 and G 2 while the actual graph G = V, E m , E c is initially unknown to them. They only know that

E m1 ⊆ E m ⊆ E m2 and E c1 ⊆ E c ⊆ E c2 , written as G 1 ⊆ G ⊆ G 2 . The perfect information case is captured by G 1 = G 2 (= G).
A movement (resp. communication) edge is said to be certain (i.e. sure to be present) if it is in E m1 (resp. E c1 ); it is said uncertain (i.e. can be absent) if it is in E m2 \ E m1 (resp. E c2 \ E c1 ). We assume that the communication edges of the actual graph are undirected, so for all (u, v)

∈ E c2 \ E c1 , either (u, v), (v, u) ∈ E c , or (u, v), (v, u) ∈ E c .
We say that an edge (u, v) is an uncertain undirected movement edge when (u, v), (v, u) ∈ E m2 \E m1 . The environment can leave both edges (u, v), (v, u), remove both edges (u, v), (v, u), but also remove (u, v) and leave (v, u), or remove (v, u) and leave (u, v). That is, the movements edges of the actual graph are not necessarily undirected. Example 6.1. Figure 6.1a depicts an initial knowledge (G 1 , G 2 ). The area is divided in two zones connected by two bridges, represented by the edges (s 2 , s 4 ) and (s 3 , s 5 ), with an uncertainty on their traversability and on the communication between s 1 and s 4 .

A strategy σ a for agent a tells where to go next after a given execution e. Formally: Definition 6.2 (Strategy). A strategy σ a for agent a maps any execution e to a vertex such that (v, σ a (e)) ∈ E m where v is the vertex at which agent a is in the last configuration of e.

A joint strategy π is a tuple π 1 , . . . , π n where π i is a strategy for agent i. The outcome of a joint strategy π starting from configuration c s is the execution e defined by induction as follows: e[0] is c s , and for t ≥ 1, e[t] is the configuration in which agent i is at vertex π i (e[0..t -1]).

In the context of incomplete knowledge, the behaviors of the agents only depend on their observations, similarly to imperfect information games as done by Berthon et al. [START_REF] Berthon | Strategy logic with imperfect information[END_REF]. The strategies, as defined above, do not necessarily take observations of the agents into account. We will now formalize observations and uniform strategies, that is, those respecting the observations of the agents.

In our setting, at any time, an agent observes all movement edges adjacent (both in-and out-coming) to the vertex v it occupies. Moreover, they observe the presence or absence of a communication edge between v and v if v is occupied by another agent with which there is a direct or indirect communication (via other agents). Intuitively, during an execution, at each step, each agent updates their knowledge about the graph with these observations they receive. Moreover, they share all their knowledge with all agents with which they are connected at each step.

The observation of adjacent movement edges has been a recurrent practice in theoretical works [START_REF] Papadimitriou | Shortest paths without a map[END_REF][START_REF] Bar | The Canadian Traveller Problem[END_REF] as well as robotics [START_REF] Dudek | Robotic exploration as graph construction[END_REF][START_REF] Koenig | Greedy Mapping of Terrain[END_REF], and our formalism is inspired from these works. The knowledge of an agent at any time corresponds intuitively to a pair of graphs as in Definition 6.1. For agent a and execution e, let us denote by k a (e) G the knowledge of agent a about the graph after observing the execution e in actual graph G. Given such knowledge K = k a (e) G , the agent can deduce an under-approximation and an over-approximation of the actual graph; let us denote these by G K and G K respectively. In particular, if K is the knowledge the agents have initially, then

G K = G 1 and G K = G 2 .
We present a representation of the knowledge using predicates in the Subsection 6.2.2 where a detailed formalization of k a (e) G can be found.

In the rest of the chapter, we assume all considered strategies to be uniform, that is, they comply with the knowledge of the agents: the strategies prescribe the same move to all executions that are indistinguishable with the agent's observations. Formally, if |e| = |e | and k a (e) G = k a (e ) G , then σ i (e) = σ i (e ).

Complements

We present here a formal modeling of the incomplete knowledge in our setting. In our setting, at any time, an agent observes all movement edges adjacent (in-and outcoming edges) to the vertex v it occupies. Moreover, they observe the presence or absence of a communication edge between (v, v ) if v is occupied by another agent with which there is a direct or indirect communication (via other agents). Intuitively, during an execution, at each step, each agent updates their knowledge about the graph with these observations they receive. Moreover, they share all their knowledge with all agents with which they are connected at each step.

Given graph G = V, E m , E c , let us define the direct observation obs a (c) of agent a at a configuration c to be the set:

o m ca,v | (c a , v ) ∈ E m ∪ o ¬m ca,v | (c a , v ) / ∈ E m (1) ∪ o m v ,ca | (v , c a ) ∈ E m ∪ o ¬m v ,ca | (v , c a ) / ∈ E m (2) ∪ o c ca,c b | j is an agent and (c a , c b ) ∈ E c (3) ∪ o ¬c ca,c b | j is an agent connected to i in c, (c a , c b ) / ∈ E c ( 4
)
where o m u,v , o ¬m u,v , o c u,v and o ¬c u,v are abstract terms that represent the observations. In the definition of obs a (c), points (1) and ( 2) mean that agent a directly observes the set of movement edges adjacent to her current position. Point (3) means that agent a observes a communication edge when she can communicate with another agent b. Point (4) means that agent a observes the absence of a communication edge when she sees that she can not communicate directly with another agent b but can communicate with b via multi-hop. That is, we say that j is an agent connected to i in c when there is a communication path c i 1 , c i 2 , . . . , c i k with i 1 = i and i k = j.

Let O denote the set of all observations. We define the knowledge of an agent as a subset of O. We define the initial knowledge for the pair (G 1 , G 2 ) as follows:

K 0 (G 1 , G 2 ) = o m u,v | (u, v) ∈ E m1 ∪ o c u,v | (u, v) ∈ E c1 ∪ o ¬m u,v | (u, v) / ∈ E m2 ∪ o ¬c u,v | (u, v) / ∈ E c2 where G i = V, E mi , E ci .
This corresponds to the a priori knowledge on the graph all agents have before making any observation.

During the execution, agents update their knowledge at each step, upon visiting a new configuration. Formally, the knowledge k a ((K j ) 1≤j≤n , e) G of agent a after observing execution e in actual graph G, where each agent j starts with initial knowledge K j , is defined by induction on e:

-k a ((K j ) 1≤j≤n , ) G = K a -k a ((K j ) 1≤j≤n , ec) G is the union of: k a ((K j ) 1≤j≤n , e) G ;
(a) obs a (c);

(b)

j connected to i in c (k b ((K j ) 1≤j≤n , e) G ∪ obs b (c). (c)
Intuitively, the knowledge of an agent is composed of (a) her knowledge collected until now, (b) her current observation, and (c) the knowledge of the agents she is connected to and their current observation.

When the agents start with an initial knowledge (G 1 , G 2 ) that is clear from the context, we will omit the tuple (K j ) 1≤j≤n and simply write k a (π) G .

Note that during a connected execution, all agents have an identical knowledge at all times. We thus omit the subscript i, and replace the tuple of initial knowledge sets by a single set K and write k(K, π) G rather than k a ((K j ) 1≤j≤n , π) G .

Decision Problems

We consider the decision problem of reaching a configuration c g from a configuration c s in less than k steps, using uniform strategies. For two configurations c s , c g , let us call a topological graph G (c s , c g )-admissible if there is an execution from c s to c g , which is not necessarily connected. Definition 6.3 (Positive Instance). We say that an instance (G 1 , G 2 , c s , c g , k) is positive if there exists a joint strategy π such that in all (c s , c g )-admissible graphs G satisfying G 1 ⊆ G ⊆ G 2 , the outcome of π starting in c s ends in c g in less than k steps.

Observe that the above problem requires that a strategy ensures the reachability of the target configuration only for graphs that are (c s , c g )-admissible and compatible with the initial knowledge. In fact, intuitively, we would like the strategy to work under all possible graphs G with G 1 ⊆ G ⊆ G 2 . However, requiring a strategy to ensure reachability in a non-admissible graph does not make sense, since even a strategy with full information would fail. We thus require the strategies to make their best efforts, that is, to ensure the objective unless it is physically impossible. Example 6.2. Consider the example of Figure 6.1a. If both bridges (i.e. movement edges (s 2 , s 4 ) and (s 3 , s 5 )) are absent in the actual graph, the graph is not (s 1 , s 6 )-admissible and there cannot be a strategy ensuring reachability. The admissible graphs contain either (s 2 , s 4 ), or (s 3 , s 5 ), or possibly both. Note that, this instance is negative for k < 6 (that is, it does not admit a solution). Indeed, consider a strategy that moves the agent, for instance, to s 2 . In the graph where (s 2 , s 4 ) is absent, the agent would need to come back to s 1 and take the alternative path, which requires an execution of total length 6; and the situation is symmetric if the first move is towards s 3 . The instance is nonetheless positive for k ≥ 6 with the described strategy. However, if the edges (s 2 , s 1 ) and (s 3 , s 1 ) were not present, then the instance would be negative. In fact, once the agent moves to s 2 or s 3 , they get stuck if the graph only contains the other bridge.

We now define the connected version of Definition 6.3. For two configurations c s , c g , we say that a topological graph G is (c s , c g )-c-admissible if there is a connected execution from c s to c g . We will often omit the pair of configurations which will be clear from the context, and write simply admissible or c-admissible. Definition 6.4 (c-Positive Instance). We say that an instance (G 1 , G 2 , c s , c g , k) is c-positive if there exists a joint strategy π such that in all (c s , c g )-c-admissible graphs G satisfying G 1 ⊆ G ⊆ G 2 , the outcome of π starting in c s is connected and ends in c g in less than k steps.

In the connected case, agents cannot visit a disconnected configuration. Hence, the considered strategies only visit configurations that are certainly connected. Observe that agents can make observations about the presence or absence of communication edges while being connected and use this information later. Example 6.3. Let us illustrate the above property on the example of Figure 6.1b. Assume there are two agents, the starting and goal configurations are c s = s 1 , s 6 and c g = s 5 , s 7 , and the only uncertainty is about the movement edges (s 3 , s 5 ) and (s 4 , s 5 ). Here, Agent 2 could immediately move to her target s 7 ; however, she could also cooperate with Agent 1 and lower the total completion time. Indeed, from their start configuration s 1 , s 6 , the agents first move to s 2 , s 4 where Agent 2 observes whether (s 4 , s 5 ) is present. Assume the edge is present. Then, they follow the sequence s 4 , s 6 • s 5 , s 7 ; and otherwise s 3 , s 6 • s 5 , s 7 . Thus, in order to minimize the length of the execution, the agents do not always take their shortest paths but might help other agents by obtaining information about the graph. Consider now the same example in which the communication edge (s 3 , s 6 ) is uncertain. If this edge is absent then Agent 2 cannot help Agent 1 achieve the target faster since if the former moves to s 4 and (s 4 , s 5 ) is absent, then, in order to maintain connectivity, the next configurations should be s 4 , s 6 • s 2 , s 7 • s 3 , s 7 • s 5 , s 7 . An execution of the same size is obtained when Agent 2 moves to s 7 in the first step.

For both Definitions 6.3 and 6.4 above, let us call a joint strategy a witness if it witnesses the fact that the given instance is positive, and respectively, c-positive.

We instantiate the CMAPF problem in four different settings. The four following decision problems are defined depending on whether we consider the connectivity requirement and whether the bound is finite. Note that the bounded problems are the decision problems associated to the optimization problems. Problem 6.1 (bDMAPFI).

-Input: A pair (G 1 , G 2 ), a start configuration c s , a goal configuration c g and a bound k < ∞.

-Output:

Is (G 1 , G 2 , c s , c g , k) positive? Problem 6.2 (bCMAPFI). -Input: A pair (G 1 , G 2 ), a start configuration c s , a goal configuration c g and a bound k < ∞. -Output: Is (G 1 , G 2 , c s , c g , k) c-positive? Problem 6.3 (DMAPFI). -Input: A pair (G 1 , G 2 ), a start configuration c s and a goal configuration c g . -Output: Is (G 1 , G 2 , c s , c g , ∞) positive? Problem 6.4 (CMAPFI). -Input: A pair (G 1 , G 2 ), a start configuration c s and a goal configuration c g . -Output: Is (G 1 , G 2 , c s , c g , ∞) c-positive?
As we will see, the encoding of the integer k does not change the overall complexity. Lower bounds are all obtained directly for the unary encoding; the lower bounds for the binary encoding follows. Concerning the upper bounds, we explain for each case how to design an algorithm with k encoded in binary. in G K , and similarly communication edges revealed by c . Note that k(K 0 , πc ) G only depends on k(K 0 , π) G and c which the algorithm already has. There is an exponential number of possibilities, and these can be enumerated in polynomial space. For each case, we check recursively whether P (G K , G K , c , c g ). Since the knowledge can increase only a polynomial number of times (since the knowledge can only increase when an edge is added or removed), the depth of the recursive calls is polynomial. Thus, overall, the procedure uses polynomial space.

Bounded Case

We now study the existence of a bounded connected strategy. We show that this problem is PSPACE-complete even when the communication graph is complete. Theorem 6.2. bCMAPFI is in PSPACE when the bound is given in binary.

Proof. Let us first prove the upper bound when k is given in unary. As APTIME = PSPACE [START_REF] Ashok | Alternation[END_REF], we give an alternating algorithm that runs in polynomial time, as follows. At each step, the existential player chooses the next connected configuration to move the agents; and the universal player chooses the information about the newly discovered edges. After k steps the algorithm accepts if the target configuration is reached, or the revealed edges mean that the graph is not c-admissible. The number of steps is bounded by k, which is polynomial, thus the algorithm runs in polynomial time.

There is one subtlety to prove the correctness. The alternating algorithm actually corresponds to a slight variant of our setting which can be seen as a game. In our setting, the environment chooses a graph G with G 1 ⊆ G ⊆ G 2 at the beginning, and the agents discover the graph G as they move. In contrast, in the alternating algorithm, the universal player reveals the graph step by step; therefore the environment might adapt the graph to the moves of the existential player. Lemma 6.3. The alternating algorithm is correct.

Proof. First, observe that if the existential player has a strategy σ in the alternating algorithm, then the instance is c-positive. In fact, for any graph G with G 1 ⊆ G ⊆ G 2 , consider strategy τ of the universal player which makes choices according to G. Since this σ wins against τ , either the graph is not admissible or the agents successfully arrive to the target configuration. Conversely, assume that the instance is c-positive, that is, for all choices of an admissible graph G, the agents arrive at a target configuration under some joint strategy σ. We apply σ in the alternating algorithm. Consider any strategy τ of the universal player, and observe the execution induced by (σ, τ ). If the graph induced by τ is revealed not to be admissible, then the existential player wins. Otherwise, consider any admissible graph G with G 1 ⊆ G ⊆ G 2 compatible with the edges revealed during the execution of (σ, τ ). Since σ is winning in the original game when the underlying graph is G, the existential player also wins.

When k is binary, the previous algorithm does not run in polynomial time. However, observe that the number of alternations can be bounded by a polynomial because there is only a polynomial number of steps in which the universal players reveal new information to the coalition of agents. In fact, the universal player is only useful when some agent is at a vertex that has not been seen before, and this can only happen a linear number of times. Furthermore, the previous algorithm runs in polynomial space.

When k is binary, our problem is in STA(poly(n), * , poly(n)) where STA(s(n), t(n), a(n)) is the set of problems decided in space O(s(n)), time O(t(n)) with O(a(n))) alternations. Our problem is in PSPACE thanks to the generalization of Savitch's theorem we prove: Lemma 6.4. STA(poly(n), * , poly(n)) ⊆ PSPACE.

Proof. To build a PSPACE algorithm, we perform a DFS of the computation tree T in a succinct manner. Consider the tree T , built from T , where we only keep vertices in which the universal player makes a decision, while paths along which only the existential player moves are shortcut into single edges. The depth of this tree is polynomial by definition.

The idea is to run a DFS on T to check whether the machine accepts. This can be done in polynomial space provided that the children of all vertices can be computed in polynomial space. Successors of an existential configuration c in T are computed as follows: we generate on-the-fly all possible configurations c and test whether c is reachable from c in the original alternating machine by using a PSPACE oracle. The DFS that runs in PSPACE augmented with this PSPACE oracle gives a polynomial space procedure.

Intuitively, this lemma is proved by guessing the computations between each universal choice by a PSPACE oracle, which yields an overall PSPACE algorithm. Theorem 6.3. bCMAPFI with complete connectivity is PSPACE-hard.

Proof. The lower bound is proven by reduction from TQBF.

Consider a QBF ϕ of the form ∀z 1 ∃z 2 . . . Q n z n ψ where ψ is a Boolean formula in conjunctive normal form with n variables and m clauses.

In the reduction, we call a movement path, from node v to node u, a chain of nodes linking v to u by movement edges. In addition, we denote an occurrence of a positive (resp. negative) literal of a variable z, by z (resp. ¬z)

We create the graphs G 1 and G 2 as described in Figure 6.2. More precisely, for each variable z, we create a gadget shown in Figure 6.2a. For each clause, we create a gadget as depicted in Figure 6.2b. In addition, we create a movement edge between a node v z (resp. v ¬z ) and a node t γ if the literal z (resp. ¬z) is present in the clause γ.

We define the initial and target configurations c s , c g as follows. There is a single agent at each vertex of the form s γ (resp. s z ) whose target is t γ (resp. t z ). Furthermore, at each s z (resp. s ¬z ) there is one agent for each clause that contains z (resp. ¬z) and her target is t z (resp. t ¬z ).

We show that ϕ is true iff

(G 1 , G 2 , c s , c g , k) is c-positive with k = 3(n -1) + 5.
For simplicity, we classify the agents as follows.

-A Variable agent is an agent starting at a node s z ;

-a Clause agent is an agent starting at a node s γ ; -a Positive (resp. negative) occurrence agent is an agent starting at s z (resp. s ¬z ).

s z v z u z u ¬z u z t z s z s ¬z v z v ¬z l z r z r ¬z l ¬z t ¬z t z . . . 3(i -1) + 1 . . . 3(i -1) + 2 . . . 3(i -1) + 2
. . . between u z (resp. u ¬z ) and r z (resp. l ¬z ) beforehand. In fact, otherwise, if the occurrence agent makes a wrong guess between l z and r z , they will not arrive to t z (resp. t ¬z ) at time k. Hence, the joint strategy of the variable agents determines an assignment function which satisfies ϕ.

(v z , t γ ) ∈ E m1 when z is an occurrence in γ (v ¬z , t γ ) ∈ E m1 when ¬z is an occurrence in γ
Our reduction actually builds an undirected movement graph. Thus, PSPACE-hardness holds already for undirected movement graphs. Note that in our current setting, pairs of uncertain edges of the form (u, v) and (v, u) are treated separately, but the lower bound proof still holds when they are seen as one.

Decentralized Reachability

We now tackle the case where agents are allowed to be disconnected; at each configuration, they share their knowledge with all agents to which they are connected. This case is harder because agents no longer follow a centralized strategy and they must cooperate to exchange information at the right moment to reach their targets.

Unbounded Case

Theorem 6.4. DMAPFI is NEXPTIME-complete.

Proof. For the upper bound, an NEXPTIME algorithm consists in guessing uniform strategies for all agents and checking whether the joint strategy is a witness. Such a strategy has exponential size since it is a function of the sets of knowledge of the agents and the current vertex. One can enumerate all graphs G between G 1 and G 2 , and execute the joint strategy on G to check that it ensures the reachability of the target. Moreover, the executions to be checked have at most exponential length. In fact, executions can be seen as paths in a meta-graph where vertices are configurations augmented with the sets of knowledge of the agents. This meta-graph is of exponential size, so it is sufficient to consider executions of exponential length. The overall non-deterministic algorithm is thus in exponential time.

The lower bound is shown by reduction from TDQBF. Given a DQBF ϕ of the form ∀y 1 , . . . , y n ∃x 1 (O x 1 ) . . . ∃x n (O xn ) ψ, we build an instance (G 1 , G 2 , c s , c g , k) of unbounded decentralized reachability. We denote by γ 1 , . . . , γ m the clauses in ψ.

The graph G 1 and G 2 as follows. For each variable z, we create the gadget depicted in Figure 6.3a.

We create the observation gadget for all existential variables x and for all (universal) variables y ∈ O x , depicted in Figure 6.3b. For convenience, we write O for the pair (x, y) corresponding to observation of y by x.

Finally, we create the clause gadget, depicted in Figure 6.3c. A vertex γ i certainly communicates with z iff z ∈ γ i , and with ⊥ z iff ¬z ∈ γ i . Moreover, the vertex v γ communicates with all z and ⊥ z for all variables z. We construct the graph G 1 as follows:

( z , γ i ) ∈ E c 1 when z appears in γ i (⊥ z , γ i ) ∈ E c 1 when ¬z appears in γ i ( z , v γ ) ∈ E c 1 , (⊥ z , v γ ) ∈ E c 1
For each variable z, we create a gadget, as depicted in Figure 6.4a. We create the vertices s z , v z , z , ⊥ z and t z , and we create a movement path of length 3m + 1 from t z to z and ⊥ z . Then, if the variable z is universal, we create a movement path of length 3 × n 2 + 1 from s z to v z . If the variable z is x i , that is the i-th existential variable, we build a movement path of length 3 × n 2 -2|O z | + 1 from s z to v z as follows. We first build a movement path of length 3 × (in -|O z |). We then extend this movement by a vertex ρ y for each y ∈ O z . We extend our path from the last such vertex ρ y to v z by a movement path of length 3 × (n 2 -in). Furthermore, we add a bidirectional edge between ρ y and v y .

We create the clause gadget, depicted in Figure 6.4b, composed of the vertices s γ , v γ , t γ and for all clauses γ i , the vertices u γ i , l γ i , r γ i , s i , c i and t i . We create a movement path of length 3 × n 2 + 2 between s γ and v γ and between all s i and γ i . For all γ i , we create movement edges from u γ i to l γ i and to r γ i , from the vertex γ i to u γ i+1 , or t γ if i = m. In addition, we add a movement edge between v γ and u γ 1 . For all γ i , we add a movement path of length 3m + 1 between vertices γ i and t i . Vertex γ i communicates with z iff z ∈ γ i , and with ⊥ z iff ¬z ∈ γ i . Moreover, vertex v γ communicates with all z and ⊥ z for all variables z.

Graph G 2 contains G 1 and for all universal variables z, we add movement edges: from v z to z and to ⊥ z , and for all clauses γ i , we add movement edges from the vertex γ i to l γ i and to r γ i .

We define the initial and target configurations as c s = s γ , s γ 1 , . . . , s γm , s z 1 , . . . , s zn and c g = t γ , t γ 1 , . . . , t γm , t z 1 , . . . , t zn .

We show that ϕ is a positive instance of TDQBF iff (G 1 , G 2 , c s , c g , k) is positive with k = 3 × n 2 + 2 + 3m + 1. We refer to an agent that starts at s z as the existential agent z if z is an existential variable; the agent is called universal if z is universal. The verification agent is the agent that starts at s γ and the clause agents γ i start at s γ i .

(⇒) Suppose the DQBF holds, and let A be an assignment function. We build a joint strategy. The environment chooses the truth values of variables z by deleting some edges v z to z or v z to ⊥ z . If the environment deletes the edge v z to z , it enforces the agent to pass in ⊥ z , thus the variable z is considered to be false. If the environment deletes the edge v z to ⊥ z , it enforces the agent to pass in z , thus variable z is considered to be true. If the environment deletes neither edge, then we define the strategy for agent a y to choose to pass in y, making y true by default.

The strategy is defined as follows. Each existential agent z follows the movement path of length 3 × n 2 -2|O z | + 1 to v z , but whenever they have vertex v y as a neighbor, they visit v y , come back, and continue their paths. This happens exactly O z times, so at time 3 × n 2 + 1, the existential agent is at u z . Note that along this path the agent has visited all vertices v z with z ∈ O z , thus knows which edge among (v z , z ) and (v z , ⊥ z ) is present. Thus, upon arriving to v z , the agent has the knowledge of the valuation for all variables in O z . Observe also that by construction of the movement paths between s z and v z , the agents never meet in this phase of the execution. Agent z moves to z if A z (ν) = 1 and to ⊥ z otherwise, where ν is the valuation of the variables in O z .

All clause agents reach γ i at time 3 × n 2 + 2. Moreover, the verification agent is at v γ at this point, and all existential and universal variable agents z are at z or ⊥ z . Recall that all these vertices communicate. Since each clause is satisfied by the currently read valuation, each clause agent γ i communicates at least with one existential or universal agent. Thus, the verification agent communicates with all clause agents via these variable agents. Since the clause agents can see which edges are present in the clause gadget, the verification agent has now full information about this gadget, and can continue their path until t γ without backtracking, thus in total time 3 × n 2 + 2 + 3m + 1.

(⇐) Conversely, suppose there is a joint strategy enforcing that the verification agent goes to t γ in k steps. Thus, it means that she must have received all the information about the surroundings of the vertices γ 1 , . . . , γ k , as she has no time to backtrack from a wrong choice. This information can only be sent to the verification agent from the clause agents through the variable agents after 3 × n 2 + 2 steps. The variable agents representing the assignments are connecting (i.e. satisfying) all clauses. Indeed, for all γ i , there is one variable agent z at z if z ∈ γ i and at ⊥ z if ¬z ∈ γ i . Thus, the DQBF is a positive instance of TDQBF.

Discussion

Additional Results

We present results obtained by a simple observation/modification. Unbounded Reachability and Undirected Graphs. Both the unbounded connected and unbounded decentralized reachability become trivial on undirected graphs. This is because we only require reachability for (c-)admissible graphs. In the decentralized case, each agent can run a DFS independently, and eventually reach their targets in at most 2|V | steps, and a similar search can be done by the set of agents in the connected case.

Base Station. Several works consider a designated base vertex to which all agents must stay connected during the execution [START_REF] Tateo | Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It[END_REF][START_REF] Charrier | Reachability and Coverage Planning for Connected Agents[END_REF][START_REF] Charrier | Complexity of planning for connected agents[END_REF]. This concept is only relevant in the connected case. Our results also hold with this additional constraint. In fact, the lower bound of Theorem 6.1 follows from Tateo et al. [START_REF] Tateo | Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It[END_REF], which proves the bound also with a base. In Theorem 6.3, we can add the base vertex as an isolated vertex so that the reduction is still valid.

Collisions. We did not require the paths to be collision-free in the results presented in this paper. However, this property is already ensured by our proofs or can be obtained by simple modifications. The lower bound proof of Theorem 6.1 relies on Theorem 3.2 from Tateo et al. [START_REF] Tateo | Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It[END_REF] which holds with collision constraints as well, so this is also true for our case. The proof of Theorem 6.3 does not generate collision-free paths as the groups of occurrence agents start and finish at the same location and follow almost the same path. This proof can be adapted to prevent collisions by delaying each occurrence agent by 3 steps behind one another. This can be achieved easily by extending the movement paths and shifting the starting location and target location of an agent up by 3 vertices behind the previous agent. The proof of lower bound of Theorem 6.4 features a construction ensuring a collision-free strategy. Indeed, the observations agents only need to take turns to visit the universal variables. Thus, the result holds with collision constraints as well. The algorithms of Theorem 6.1, 6.3, and 6.5 can be adapted by restricting all considered configurations to collision-free ones; while c-admissibility of a graph with collision constraints can be checked using Theorem 3.2.

Graph Classes. The MAPF and CMAPF problems have been studied for different classes of graphs (planar, grid, . . . ). The proof of lower bound in Theorem 6.1 relies on the proof of unbounded reachability done in Charrier et al. [START_REF] Charrier | Complexity of planning for connected agents[END_REF], thus the result of PSPACE-hardness on planar graphs also carries over to our problem. Planar QBF is known to be PSPACE-complete [START_REF] Lichtenstein | Planar Formulae and Their Uses[END_REF], and the construction of Theorem 6.3 is such that when applied to a planar QBF, the resulting graph is planar. Our PSPACE-completeness result thus holds on planar graphs.

Related Work

Different definitions of robust plans have been studied [START_REF] Ma | Multi-Agent Path Finding with Delay Probabilities[END_REF][START_REF] Atzmon | k-Robust Multi-Agent Path Finding[END_REF][START_REF] Atzmon | Probabilistic Robust Multi-Agent Path Finding[END_REF]. A k-robust plan guarantees the reachability of the target in the events of at most k delays. A p-robust plan executes without a conflict with probability at least p. Our framework does not consider delayed agents but focus on synchronous executions with incomplete knowledge of the area.

The problem of MAPF with a dynamic environment has multiple formulations. The Adversarial Cooperative Path-Finding [START_REF] Ivanová | Adversarial Cooperative Path-Finding: Complexity and Algorithms[END_REF] considers that the obstacles are agents which reason to prevent the cooperation to reach its goal. Murano et al. [START_REF] Murano | Multi-agent Path Planning in Known Dynamic Environments[END_REF] considered the problem where the dynamics of the environment is predictable. Additionally, when obstacles have unknown dynamics, one can estimate their movements and plan to minimize the probability of a collision [START_REF] Miura | Probabilistic Uncertainty Modeling of Obstacle Motion for Robot Motion Planning[END_REF], or predict their movements [START_REF] Griswold | Control for mobile robots in the presence of moving objects[END_REF] and plan online the movement of the agents [START_REF] Seok | A View-Time Based Potential Field Method for Moving Obstacle Avoidance[END_REF]. In our setting, the environment is static, thus, all observations are fixed.

MAPF with Uncertainty (MAPFU) asks for a plan which guarantees that mishaps, localization and sensing errors do not impact the proper execution of the plan. This problem can be solved by temporal logic [START_REF] Ulusoy | Robust multi-robot optimal path planning with temporal logic constraints[END_REF], POMDPs [START_REF] Miller | Coordinated Guidance of Autonomous UAVs via Nominal Belief-State Optimization[END_REF], replanning [START_REF] Stentz | Optimal and Efficient Path Planning for Unknown and Dynamic Environments[END_REF][START_REF] Ferguson | Replanning with RRTs[END_REF][START_REF] Likhachev | Anytime Dynamic A*: An Anytime, Replanning Algorithm[END_REF], interaction regions [START_REF] Dresner | A Multiagent Approach to Autonomous Intersection Management[END_REF][START_REF] Ferrari | Multirobot motion coordination in space and time[END_REF], and belief space planning [START_REF] Bry | Rapidly-exploring Random Belief Trees for motion planning under uncertainty[END_REF][START_REF] Gonzalez | Planning with uncertainty in position an optimal and efficient planner[END_REF][START_REF] Prentice | The Belief Roadmap: Efficient Planning in Belief Space by Factoring the Covariance[END_REF]. Nebel et al. [START_REF] Nebel | Implicitly Coordinated Multi-Agent Path Finding under Destination Uncertainty: Success Guarantees and Computational Complexity[END_REF] studied the MAPF problem with an uncertainty on the destination of the agents and lack of communication. The asynchronous movement of the agents, studied in those papers, cannot be expressed in our framework as we require the agent to follow some universal clock to execute their plan.

Perspectives

We proposed a setting for CMAPF in the incomplete case and studied the theoretical complexity of the reachability problem. The first natural question is to find classes of graphs (e.g. grid graphs) on which the reachability problem is easier to solve, as it was done for MAPF in Wang and Botea [START_REF] Ko-Hsin | Tractable Multi-Agent Path Planning on Grid Maps[END_REF] and Banfi et al. [START_REF] Banfi | Intractability of Time-Optimal Multirobot Path Planning on 2D Grid Graphs with Holes[END_REF], and CMAPF in [START_REF] Charrier | Complexity of planning for connected agents[END_REF]. Another possible direction is to study the coverage of all vertices [START_REF] Charrier | Complexity of planning for connected agents[END_REF]. An alternative way to handle non-admissible graphs is to require that agents return to their starting configuration if the graph is discovered not to be admissible. We believe that such variants should be as hard as reachability. Furthermore, there are several possible generalizations that could be considered by introducing dynamic environments (instead of static), faulty sensing of agents, robustness, uncertainty, etc. CHAPTER 7

CONCLUSION

In this chapter, we provide a summary of the contributions of this dissertation. Then, we present the different articles that have been published during the writing of this work. Finally, we provide the reader with interesting future works and research directions which can follow this work.

Contributions

More autonomous agents are being used every day and the tasks they perform become increasingly more complex [START_REF] Ghoseiri | A multiobjective train scheduling model and solution[END_REF][START_REF] Pallottino | Decentralized Cooperative Policy for Conflict Resolution in Multivehicle Systems[END_REF][START_REF] Dresner | A Multiagent Approach to Autonomous Intersection Management[END_REF][START_REF] Peter | Coordinating Hundreds of Cooperative, Autonomous Vehicles in Warehouses[END_REF]. Those applications require multiple agents to cooperate together towards a goal. As the tasks complexify, it is not practical to reason about the group of agents as a single entity. Thus, there is a need for algorithms that let agents communicate and be aware of each other, plan together, avoid mistakes, and "survive" mishaps.

While many works attempted to tackle the problem of planning with communication and/or in a partially-known environment, none of the existing work presented a framework to properly study the complexity and algorithmic methods of multi-agent path planning with a formal communication system. This dissertation has for purpose to fill this gap by providing an in-depth study of the connected multi-agent path planning problems with incomplete knowledge.

Connectivity

Part I introduced a framework which formalizes environment-based communication system for multi-agent path planning problems. This setting allowed us to study connected planning independently of the communication system used by the agents in Chapter 4. Note that, the applications of this framework define the communication, thus, the result of this work hold for most common communication systems (e.g. line-of-sight, radius). This first contribution provided a broad overview of the difficulties of planning with communication as well as some ways to ease the problems. In particular, we identify a class of graphs which correspond to realistic applications and reduces the complexity to LOGSPACE.

Chapter 5 presents an optimal algorithm to solve CMAPF which is able to, in some cases, outperform known approximate algorithms. We provided a proof of its optimality and soundness, and we showed that our algorithm may not terminate on unsatisfiable instances. We provided experimentation which shows that, while outperformed, our algorithm can offer a good alternative by scaling better in connected worlds and generating execution, by an order of magnitude shorter. Finally, as it is based on a similar structure as the well-studied CBS algorithm for MAPF, one can extend it to support the generation of collision-free executions and may adapt some known optimizations.

Incomplete Knowledge

Secondly, we provided an extension of the framework presented in Chapter 4 which can model partially-known environments. The case of incomplete knowledge in multi-agent systems is crucial as almost no real world application can ensure a perfectly known world. Importantly, our framework offers a way to model the loss of communication and the reconnection of agents in a positional manner. We studied the impact of enforcing a permanent connectivity and allowing disconnections. This study gives an initial step towards understanding precisely the cost of communication in unknown worlds.

Publications

The majority of the content of this dissertation has been published in International peerreviewed conferences and journals.

Future Work

In order to conclude this dissertation we would like to give the reader a look beyond the content of our study. In particular, we wish to provide the reader with a view of the potential solutions to solve the high-complexity problems defined in this work.

Our first work, Chapter 4, gave a good overview of the complexity of CMAPF. However, our framework describes an arbitrary communication system, and one may be interested to study the complexity of a specific system (e.g. radius, line-of-sight). Indeed, as shown by the study of the sigh-moveable graphs, in Section 4.5, it may be that some communication systems are easier to plan with. For instance, our constructions in proofs often rely on fully connected locations (see proofs of Section 4.4), which may not be realistic. Furthremore, most of our proofs, even in planar cases, also rely on non-euclidean movement graphs (see proofs of Section 4.7). It may be the case that under a euclidean hypothesis, some problems are simpler, or admits powerful approximation algorithms.

Secondly, we provided a simple algorithmic solution to optimally solve CMAPF in Chapter 5. However, by taking inspiration from the optimizations of CBS, the scalability may be greatly improved. Furthermore, one may wish to combine CCBS with CBS to obtain the first algorithm capable of generating connected and collision-free execution, although it would require rethinking most optimizations of CCBS and CBS. Additionally, CMAPF seems to be a very cooperation-demanding problem, as disconnection is global to the group, a decoupled algorithm may not be the most efficient approach.

We showed that solving the connected variant of CMAPF in an incomplete environment is, in the worst case, as hard as solving CMAPF. However, the algorithmic solutions employed to solve CMAPF are not adaptable to the incomplete knowledge case. Indeed, an unknown environment requires the agents to be equipped with a strategy. Fortunately, related lines of works are that of the CTP and Partially Observable Markov Decision Processes (POMDPs), for which many algorithms have been developed and may be adapted [START_REF] Likhachev | Probabilistic planning with clear preferences on missing information[END_REF][START_REF] Ferguson | PAO for planning with hidden state[END_REF][START_REF] Wagner | A complete multirobot path planning algorithm with performance bounds[END_REF][START_REF] Hansen | LAO*: A heuristic search algorithm that finds solutions with loops[END_REF][START_REF] Bnaya | Repeated-Task Canadian Traveler Problem[END_REF].

Finally, while the PSPACE complexity of the previous problems may still be practical, it leaves little hope for solving the decentralized variant. Fortunately, our problem can be modeled as a Dec-POMDPs and may benefit from the state-of-the-art planners [START_REF] Steeve Dibangoye | Optimally solving Dec-POMDPs as continuous-state MDPs[END_REF][START_REF] Hansen | Dynamic Programming for Partially Observable Stochastic Games[END_REF]6,[START_REF] Oliehoek | Incremental Clustering and Expansion for Faster Optimal Planning in Decentralized POMDPs[END_REF]. Another approach to solve the decentralized case of CMAPF would be to use a Multi-Agent Reinforcement Learning (MARL) approach. Many recent works have been investigating the efficiency of RL in multi-agent systems [START_REF] Hauwere | Contextsensitive reward shaping for sparse interaction multi-agent systems[END_REF][START_REF] Devlin | Theoretical Considerations of Potential-Based Reward Shaping for Multi-Agent Systems[END_REF], see [START_REF] Athanasios | Survey of model-based reinforcement learning: Applications on robotics[END_REF] for a comprehensive survey on robotic applications. Abstract: Path planning is the task of devising a sequence steps for a mobile entity to follow. This task is required at the center of numerous real-world problems. The study of autonomous planning can allow one to reduce congestion, pollution, accidents, costs and more. In some applications, it is important to consider the connectivity of the agents. Although some settings guarantee a permanent connectivity among entities, this is not always true in applications with open environments. Another aspect that can be found in many applications is the lack of complete knowledge of the area in which the entities move. For instance, in exploration missions, the agents are not pro-vided any information of the environment and must discover it by themselves. An important problem, called Multi-Agent Path Finding, is to find a sequence of steps for a group of agents to reach specified targets while avoiding collisions. First, we present a framework to study and model connectivity-based multiagent path planning problems. We provide a detailed initial work on the complexity of this framework and an optimal algorithm to solve it. Second, we extend our connectivity framework to the incomplete knowledge setting and show the complexity of the connected and decentralized computation of plans under partially known environments.

6. 6 99 1. 1

 6991 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 6.6.1 Additional Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 6.6.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 6.6.3 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 7 Conclusion 95 7.1 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 7.1.1 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 7.1.2 Incomplete Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . 96 7.2 Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 7.3 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 Bibliography Example of an execution for two agents in a 2D environment. The start locations are A2 and B5. The goal locations are E2 and D1. . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Example of a connected configuration for three agents on a 2D environment. . . . . . . . 1.3 Example of a state in the exploration of a partially-known environment with 2 agents. . . 2.1 Schematic representation of a two-tape DTM. . . . . . . . . . . . . . . . . . . . . . . . 2.2 Overview of the complexity classes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Examples of topological graphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Example of a covering execution of length 10 with 3 agents. The plan is depicted from left to right and from top to bottom. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Reduction of CMAPF-init UND into CMAPF UND . The node t n+2 communicates with all nodes v such that v communicates with B. . . . . . . . . . . . . . . . . . . . . . . . .4.4 Reduction of CMAPF UND to CMACP-init UND . . . . . . . . . . . . . . . . . . . . . . . 4.5 Reductions of Section 4.4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 Example of an ordering of nodes in V = {c 1 , . . . , c n , B}. . . . . . . . . . . . . . . . . 4.7 Gadgets for reduction of 3-SAT into bCMAPF SM . . . . . . . . . . . . . . . . . . . . . 4.8 Reduction of 3-SAT into bCMAPF SM . Communication edges implied by movement edges are not displayed. The variable x 1 is present in the clause c 1 and c n . . . . . . . . . 4.9 Maps. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.10 Characteristics of the discretized graphs and their relaxations. . . . . . . . . . . . . . . . 4.11 Reductions of Sections 4.5 and 4.6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.12 Summary of all the planar constructions. . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 An example of a topological graph. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 MDDs for agent 1 in Example 5.1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 An example of a topological graph with the negative instance s = s 1 , s 2 with goal g = g 1 , g 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Benchmarks. The two maps used to obtain topological graphs. Obstacles are in black. For each map, we generate a topological graph with a distance-based communication (range we used are depicted below the maps). . . . . . . . . . . . . . . . . . . . . . . . 5.5 Success rate of CCBS, DFS, and SB to solve CMAPF on Offices and Open maps. . . . . 5.6 Average execution size of DFS and CCBS to solve CMAPF on Offices and Open maps. . 6.1 Examples of partially known topological graphs. . . . . . . . . . . . . . . . . . . . . . 6.2 Gadgets for the reduction from TQBF into the bounded reachability problem in the complete connectivity case. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Gadgets in the reduction from DQBF to unbounded decentralized reachability. . . . . . . 6.4 Gadgets for the reduction from DQBF to the bounded decentralized reachability problem.

AFigure 1 . 1 -

 11 Figure 1.1 -Example of an execution for two agents in a 2D environment. The start locations are A2 and B5. The goal locations are E2 and D1.

AFigure 1 . 2 -

 12 Figure 1.2 -Example of a connected configuration for three agents on a 2D environment.

Figure 1 .

 1 Figure 1.2 depicts a connected configuration of three agents. It is worth noting that agents are capable of multi-hop communication. In other words, the agent can relay communication to others. This phenomenon is depicted by agent in D4 connected to agent in E2 through the agent in D2.An example of a partially-known environment is depicted in Figure1.3. We consider that the agent can see at 2 cells away from them (only 1 cell in diagonal). In order to reach their goals, the agents must avoid the obstacles that they will encounter during the mission. It is

AFigure 1 . 3 -

 13 Figure 1.3 -Example of a state in the exploration of a partially-known environment with 2 agents.

Definition 2 . 1 (

 21 Decision Problem). A decision problem is a pair Π = (D, Y ) with D, the domain, a set of instances and Y ⊆ D a set of positive instances.

. 1 .Figure 2 . 1 -

 121 Figure 2.1 -Schematic representation of a two-tape DTM.

Definition 2 . 5 (

 25 Space Function).

S

  A,Π (n) = max d∈D,|d|=n {m | A solves d using m work cells } is the most amount of space the algorithm A uses to solve an instance of size n of a problem Π.

Figure 2 . 2 -

 22 Figure 2.2 -Overview of the complexity classes.

Definition 2 . 19 ( 1 a = c t b and c t- 1 b

 21911 Vertex Collision). Two agents a, b are in vertex collision at a time-step t of an execution e = c 1 , . . . , c when c t a = c t b . Definition 2.20 (Edge Collision). Two agents a, b are in edge collision at a time-step t of an execution e = c 1 , . . . , c when c t-

Problem 2 . 2 (

 22 Bounded MAPF). -Input:A graph G, two configurations c s , c g of size n and a bound k. -Output: Does there exist a collision-free execution e = c s , . . . , c g of cost k? CHAPTER 3

  Figure 4.1.

Figure 4 . 1 -

 41 Figure 4.1 -Examples of topological graphs.

Definition

Definition 4 . 5 (

 45 Configuration). A configuration c of n agents in a topological graph G is a tuples of elements of V of size n, denoted c = c 1 , . . . , c n .

Figure 4 . 2 -

 42 Figure 4.2 -Example of a covering execution of length 10 with 3 agents. The plan is depicted from left to right and from top to bottom.

4 Figure 4 . 5 -

 445 Figure 4.5 -Reductions of Section 4.4.

Figure 4 . 6 -

 46 Figure 4.6 -Example of an ordering of nodes in V = {c 1 , . . . , c n , B}.

Theorem 4 . 5 (

 45 [START_REF] Reingold | Undirected connectivity in log-space[END_REF]). USTCONN is in LOGSPACE. Proposition 4.3. CMAPF SM is in LOGSPACE.

Figure 4 . 7 -

 47 Figure 4.7 -Gadgets for reduction of 3-SAT into bCMAPF SM .

Figure 4 . 8 -

 48 Figure 4.8 -Reduction of 3-SAT into bCMAPF SM . Communication edges implied by movement edges are not displayed. The variable x 1 is present in the clause c 1 and c n .

3 1 :

 1 C := ∅ 2: for all v ∈ V do 3: Q := {v} 4: while Q not empty do 5:

Figure 4 . 9 -

 49 Figure 4.9 -Maps.

Figure 4 . 10 -

 410 Figure 4.10 -Characteristics of the discretized graphs and their relaxations.

8 Figure 4 . 11 -

 8411 Figure 4.11 -Reductions of Sections 4.5 and 4.6.

Theorem 4 . 11 .

 411 The weighted variants of bCMAPF, bCMACP on directed and undirected topological graphs with unary encoding are NP-complete.

Theorem 4 . 14 .

 414 The variants of the problems CMAPF SM , CMAPF CC (resp. CMACP SM and CMACP CC ) with collision constraints are in LOGSPACE (resp. NLOGSPACE).

Figure 4 . 12 -

 412 Figure 4.12 -Summary of all the planar constructions.

Figure 4 .

 4 3 used in proof of Theorem 4.4, shown in the top part of Figure 4.12. We thus obtain G Cover designed for 2n + 4 + 2 = 2n + 6 agents starting at the base B , which is the reduction of Theorem 4.4. The obtained graph is also planar. This shows that CMACP UND is PSPACE-hard on planar graphs. To sum up: Theorem 4.16. CMAPF UND , CMACP-init UND and CMACP UND are PSPACE-hard on planar graphs.

Figure 5 . 1 -Example 5 . 1 .

 5151 Figure 5.1 -An example of a topological graph.

Figure 5 . 2 -

 52 Figure 5.2 -MDDs for agent 1 in Example 5.1.

10 :

 10 discard CHILDREN and insert n again into OPEN. 11: else 12: insert all nodes in CHILDREN into OPEN Algorithm 3 Sub-procedures 1: procedure INSERTROOT 2: root := new node 3: root.cons := ∅ 4: for all agents a do root.exec a := CSP(s a , g a , ∅) 5: root.cost := Cost(exec) 6: insert root into OPEN 7: procedure CREATECHILD(node n, constraint a, v, t ) 8: n := new node with n .cons := n.cons ∪ { a, v, t } 9: for all agents b = a do n .exec b := n.exec b 10: n .exec a := CSP(s a , g a , n .cons) 11: n .cost := Cost(exec) 12: if n .cost = n.cost and n has less conflicts than n then 13: n.exec a := n .exec a 14: raise BYPASS 15: insert n into CHILDREN 16: procedure SPLIT(node n, time-step t, agent a) 17: for all v ∈ V and following (3) do 18: CREATECHILD(n, a, v, t )

Figure 5 . 3 -

 53 Figure 5.3 -An example of a topological graph with the negative instance s = s 1 , s 2 with goal g = g 1 , g 2 .

  4107 #comm edges 39310 (b) Open Map.

Figure 5 . 4 -

 54 Figure 5.4 -Benchmarks. The two maps used to obtain topological graphs. Obstacles are in black. For each map, we generate a topological graph with a distance-based communication (range we used are depicted below the maps).

Figure 5 . 5 -

 55 Figure 5.5 -Success rate of CCBS, DFS, and SB to solve CMAPF on Offices and Open maps.

Figure 5 . 6 -

 56 Figure 5.6 -Average execution size of DFS and CCBS to solve CMAPF on Offices and Open maps.

  An initial knowledge (G 1 , G 2 ).

Figure 6 . 1 -

 61 Figure 6.1 -Examples of partially known topological graphs.

Figure 6 . 2 -

 62 Figure 6.2 -Gadgets for the reduction from TQBF into the bounded reachability problem in the complete connectivity case.

Figure 6 . 3 -

 63 Figure 6.3 -Gadgets in the reduction from DQBF to unbounded decentralized reachability.

Titre:

  Recherche de Chemin Multi-agents Connectés : Comment les Robots Téléphonent au Volant en Toute Impunité Mot clés : Plannification, Système Multi-Agents, Théorie de la complexité, Connectivité, Connaissance Incomplète Résumé : La planification de chemin consiste à concevoir une séquence d'étapes à suivre pour une entité mobile. Cette tâche est au coeur de nombreux problèmes du monde réel. L'étude de la planification autonome peut permettre de réduire la congestion, la pollution, les accidents, les coûts et plus encore. Dans certaines applications, il est important de considérer la connectivité des agents. Bien que certaines configurations garantissent une connectivité permanente entre les entités, ce n'est pas toujours le cas dans les applications avec des environnements ouverts. On retrouve aussi, dans de nombreuses applications, le manque de connaissance complète de la zone dans laquelle les entités se déplacent. Par exemple, dans les missions d'exploration, les agents ne reçoivent aucune in-formation sur l'environnement et doivent le découvrir par eux-mêmes. Un problème important, appelé Multi-Agent Path Finding, consiste à trouver une séquence d'étapes pour qu'un groupe d'agents atteigne des cibles spécifiées tout en évitant les collisions. Tout d'abord, nous présentons un cadre pour étudier et modéliser les problèmes de planification de chemins multi-agents basés sur la connectivité. Nous fournissons un travail initial détaillé sur la complexité de ce cadre et un algorithme optimal pour le résoudre. Deuxièmement, nous étendons notre cadre de connectivité au cadre de connaissance incomplète et montrons la complexité du calcul connecté et décentralisé des plans dans des environnements partiellement connus. Title: Connected Multi-Agent Path Finding: How Robots Get Away with Texting and Driving Keywords: Planning, Multi-Agent Systems, Complexity Theory, Connectivity, Incomplete Knowledge

Table 1 .

 1 3. 1 -Summary of the contribution (1).

	Top. Graph/Problem	CMAPF (Def. 4.7)	CMACP (Def. 4.8)		bCMAPF (Def. 4.9)	bCMACP (Def. 4.10)
	Directed		PSPACE-complete
	(Def. 4.1)		(Th. 4.3)	PSPACE-complete	NP-complete
	Undirected		PSPACE-complete	(Th. 4.4)		[69]
	(Def. 4.2)		[151]			NP-complete
	Sight-Moveable				NP-complete	(Th. 4.8)
	(Def. 4.3)		in LOGSPACE	in NLOGSPACE	(Th. 4.6)
	Complete-Comm.	(Prop. 4.3)	(Prop. 4.4)		in NLOGSPACE
	(Def. 4.4)					(Prop. 4.5)
	Top. Graph/Problem	CMAPFI (Def. 6.4)	DMAPFI (Def. 6.3)		bCMAPFI (Def. 6.2)	bDMAPFI (Def. 6.1)
	Directed	PSPACE-complete NEXPTIME-complete
	(Def. 4.1)	(Th. 6.1)	(Th. 6.4)	PSPACE-complete	NEXPTIME-complete
	Undirected		Trivial			(Th. 6.2, 6.3)	(Th. 6.5)
	(Def. 4.2)		See 6.6.1
			Table 1.2 -Summary of the contribution (2).

  .1.

	Part I, Chapter 4 -Connected Multi-Agent Path Planning
	Class/Problem	CMAPF (Def. 4.7)	CMACP (Def. 4.8)	bCMAPF (Def. 4.9)	bCMACP (Def. 4.10)
	Directed	PSPACE-complete
	(Def. 4.1)	(Th. 4.3)	PSPACE-complete	NP-complete
	Undirected	PSPACE-complete	(Th. 4.4)	[69]
	(Def. 4.2)	[151]			NP-complete
	Sight-Moveable			NP-complete	(Th. 4.8)
	(Def. 4.3)	in LOGSPACE	in NLOGSPACE	(Th. 4.6)
	Complete-Comm.	(Prop. 4.3)	(Prop. 4.4)	in NLOGSPACE
	(Def. 4.4)			(Prop. 4.5)

Table 4 .

 4 1 -Overview of the complexity results.

  , . . . , t n . The graph G contains the graph G: in particular, it contains B that is no longer the base; a new node B is now the base. Let us describe the construction of G .-Nodes We first create two layers of n + 2 vertices. The first layer is composed of the following vertices v 1 , . . . , v n , v n+1 , v n+2 and the second of v 1 , . . . , v n , v n+1 , v n+2 . We also add two nodes t n+1 and t n+2 . -Movement We add movement edges between t n+1 and v n+1 , t n+2 and v n+2 , t n+1 and t n+1 , and t n+2 and t n+2 . Then, the role of t n+1 and t n+2 is to relay the communication from B to nodes in G. We connect B to the first layer, i.e. with a movement edge between B and v i , for all 1 ≤ i ≤ n + 2. The first layer has movement edges to the second layer, i.e. with a movement edge between v i and v i , for all 1 ≤ i ≤ n + 2. The n first vertices of the second layer has movement edges to the initial configuration s such that there is a movement edge from v i to s i , for all 1 ≤ i ≤ n.

	1	t 2	t n
	t n+1	t

n+2 Figure 4.3 -Reduction of CMAPF-init UND into CMAPF UND . The node t n+2 communicates with all nodes v such that v communicates with B.

Proof. The upper bound comes from Proposition 4.1. The lower bound is by reduction from CMAPF-init UND (see Theorem 4.2). Let us denote by a tuple (G, B, n, s, t) the instances of CMAPF-init UND where G is the graph, B the base, n the number of agents, s the initial configuration and t the target configuration. Instances of CMAPF UND will be denoted by (G, B, n, t) as the initial configuration is fixed.

Let (G, B, n, s, t) be an instance of CMAPF-init UND . We show how to map (G, B, n, s, t) to an instance of CMAPF UND in polynomial time. We construct the instance (G , B , n + 2, t ) of CMAPF UND where G is given in Figure

4

.3, B is the base, and the final configuration t is t 1 , . . . , t n , t n+1 , t n+2 . Let us describe more precisely the construction of G . We write s = s 1 , . . . , s n and t = t 1 -Communication We add communication edges from B to t n+1 , from t n+1 to t n+2 as well as from t n+2 to B and if there exists v such that B communicates v then we create a communication edge from t n+2 to v. We add a communication edge from B to v n+1

  configurations s, g (considered as global variables)

	1: INSERTROOT

2: while OPEN is not empty do 3: n := remove the best node from OPEN 4: if n has no conflict then return n.exec 5: CHILDREN := empty list 6: t := time-step of the chosen conflict in n.exec (1) 7: a := agent to split at t in n (2) 8: SPLIT(n, t, a) 9: if BYPASS was raised then

  Gadget for variable z. Both edges (v z , z ) and (v z , ⊥ z ) are certain (resp. uncertain) if z is existential (resp. universal).

			? ∃z	∀z	z				v O	t O
	s z (a) s O v z ⊥ z t z ∀z ? ∃z (b) Gadget for the observation O of universal variable y from v y v x existential variable x.
					r γ 1	t 1		r γ k	t k
					?			?
	s γ	v γ	u γ 1			γ 1	. . .	u γ k	γ k	t γ
					?			?
					l γ 1	s 1		l γ k	s k
						(c) Clause gadget.
			Certain movement edge
			Certain communication edge
		? Uncertain movement edge
		∀z ?	Certain (resp. uncertain) movement
		∃z	edge if z is existential (resp. universal)

The bounded plan is clearly in NP when the bound is written in unary: simply guess a solution of length at most and check that it is correct. When the bound is given in binary, a solution may be in exponential size, and cannot be guessed in polynomial time.

(¬x i , p Proof. Concerning the communication between the base B and the nodes x i (resp. ¬x i ), a path does exist under the communication of B to reach x i (resp. ¬x i ), due to communication induced by the movement. For the other communication edges, they are part of full connected paths which guarantee the sight-moveable condition. This ends the proof of Fact 3. Now let us prove that a 3-SAT instance is satisfiable iff there exists an execution of at most 3 steps in the graph G.

(⇒) We show that if a 3-SAT instance is satisfiable then there exists an execution of at most 3 steps in the graph G built from it. Let val be a truth assignment which satisfies the instance. Recall that there are n + m agents. The first step of the execution consists in moving an agent in each v c i , and for each variable x i , moving one agent to v x i if the val(x i ) = 1 and to v ¬x i otherwise. Note that all staging nodes communicate with B.

In the second step, all agents progress to their unique successors other than during the mission, or a decentralized strategy, allowing agents to disconnect and reconnect. (B)

In some applications, collisions can be handled by a local collision avoidance system [START_REF] Hollinger | Multirobot Coordination With Periodic Connectivity: Theory and Experiments[END_REF], and one can thus abstract away and ignore collisions in graph-based planning algorithms. (C) By providing a bound on the execution length, we can study the complexity of the decision problem associated to the optimization problem. Our results are summarized in Table 6.1. Interestingly, The PSPACE algorithm for the connected problem with a bounded execution is subtle and relies on a variant of the Savitch's theorem [START_REF] Walter | Relationships Between Nondeterministic and Deterministic Tape Complexities[END_REF] we present here. Additionally, the PSPACEcompleteness holds even in the case in which agents can always communicate, thus the hardness of the problem already comes from the incomplete knowledge of the movement graph. For the decentralized case, we prove the NEXPTIME-hardness in the bounded and unbounded cases by two separate reductions from the True Dependency Quantified Boolean Formula Problem (TDQBF) [START_REF] Peterson | Lower Bounds for Multiplayer Noncooperative Games of Incomplete Information[END_REF], thus showing that the problem becomes significantly harder in this case.

Let us compare our contribution with known complexity results. In the fully known environment, the CMAPF problem is PSPACE-complete in the connected and unbounded case [START_REF] Tateo | Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It[END_REF], while it is NP-complete in the bounded case (with the bound given in unary) [START_REF] Hollinger | Multirobot Coordination With Periodic Connectivity: Theory and Experiments[END_REF]. Thus, the partial knowledge of the environment does not render the problem harder in terms of complexity. In contrast, recall that in MAPF (without connectivity), one can check the existence of a solution in polynomial time [START_REF] Yu | Multi-agent Path Planning and Network Flow[END_REF], while the bounded problem is NP-hard [START_REF] Surynek | An Optimization Variant of Multi-Robot Path Planning is Intractable[END_REF], so the hardness is due to connectivity constraints. Some algorithms were presented for CMAPF by Tateo et al. [START_REF] Tateo | Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It[END_REF] that can scale up to about ten agents. Since both problems are similar and belong to PSPACE, one can hope that these approaches can be extended to the partial knowledge case. On the other hand, our results show that the complexity of the decentralized case is significantly higher. While some tools and algorithms are available for Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs), which are in the same complexity class, the scalability is limited and the development of efficient algorithms for this case seems more challenging (see survey of Amato et al. [2]).

Our framework 6.2.1 Modeling Incomplete Knowledge

To formalize CMAPF in the incomplete knowledge setting, let us show how to represent the initial knowledge of the agents, and how their knowledge evolves during the execution. Agents initially know the exact set of vertices, but only have a lower and an upper approximation of the

Quantified Boolean Formula

In this section, we present the True Quantified Boolean Formula Problem (TQBF) and True Dependency Quantified Boolean Formula Problem (TDQBF). These problems are necessary for the reductions presented in the following sections.

Quantified Boolean Formula

The True Quantified Boolean Formula Problem (TQBF) asks whether a given a QBF ϕ is valid. Recall that a QBF ϕ is of the form ∀z 1 ∃z 2 . . . Q n z n ψ where z 1 , . . . , z n are Boolean variables; Q n is ∀ if n is odd, and ∃ if n is even; ψ is a Boolean formula in Conjunctive Normal Form (CNF) over variables z 1 , . . . , z n . TQBF is PSPACE-complete [START_REF] Stockmeyer | Word Problems Requiring Exponential Time (Preliminary Report)[END_REF]. For convenience and simplicity, we say that an existentially (resp. universally) quantified variable is an existential (resp. universal) variable. We will often use x 1 , x 2 , . . . for existential variables and y 1 , y 2 , . . . for universal ones.

Dependency Quantified Boolean Formula

The TDQBF is the problem of deciding whether a given DQBF is valid. A DQBF is a formula in which dependencies of existential variables over universal variables are explicitly specified. A DQBF is of the form ∀y 1 , . . . , y n ∃x 1 (O x 1 ) . . . ∃x n (O xn ) ψ, where each O x i is, the dependency set, a subset of universally quantified variables, and ψ is a Boolean formula in CNF over x 1 , . . . , x n , y 1 , . . . , y n . It is worth noting that a QBF can be seen as a DQBF with

Formally, a DQBF ϕ is valid iff there exists a collection of Skolem functions A = (A x i : {0, 1} Ox i → {0, 1}) i=1..n such that replacing each existential variable x i by a Boolean formula representing A x i , turns ψ into a tautology. TDQBF is NEXPTIME-complete [START_REF] Peterson | Lower Bounds for Multiplayer Noncooperative Games of Incomplete Information[END_REF], and will be used to prove NEXPTIME lower bounds in Section 6.5.

Connected Reachability

We first address the case where agents must be connected at each step of the execution. In this case, agents share their knowledge at all times and thus the group of agents can be considered as a single agent playing against the environment.

Unbounded Case

We first focus on the existence of an unbounded connected strategy. Interestingly, we show that verifying the existence of a connected strategy in a partially known environment is not harder than in a perfectly known environment. Theorem 6.1. CMAPFI is PSPACE-complete.

We define the following recursive property: P (G, G, c, c g ) holds for graphs G, G, and configurations c, c g if either G is not (c s , c g )-c-admissible, or there exists a connected execution π from c to c g in G such that for all G with G ⊆ G ⊆ G, writing K 0 for the initial knowledge for the pair (G, G), there exists

The following two lemmas prove Theorem 6.1.

Lemma 6.1.

Proof. We prove the following more general property by induction on the number of edges present in G 2 and absent in G 1 , that is,

If G = G then either the instance is not c-admissible and, then, P (G, G, c, c g ) holds, or there is a connected execution in G from c to c g in which case the property holds as well.

Assume G G, and consider σ a witness strategy for the instance (G, G, c, c g , ∞). Consider a graph G ⊆ G ⊆ G. If the execution π induced by σ does not reveal any new observation in G, then it must end in c g and P (G, G, c, c g ) holds. Otherwise, let i 0 be the first step where a new observation is made. Since σ is a witness strategy, it is a witness for the instance

number of differences than G and G, we conclude by induction that P (G, G, π[i 0 ], c g ). Thus, P (G, G, c, c g ) holds.

Let us now show that all instances that satisfy the property are c-positive. Assume that the property P (G 1 , G 2 , c s , c g ) holds. We define the joint strategy σ on all graphs G K and executions π in G K , such that P (G K , G K , last(π), c g ), by induction on the length of π.

Assume σ is constructed for an execution π and knowledge K.

then any strategy is a witness strategy so σ can be defined arbitrarily. Otherwise, consider the connected execution π given by P (G K , G K , last(π), c g ). We define σ so that agents follow π

Lemma 6.2. P (G 1 , G 2 , c s , c g ) can be checked in polynomial space.

Proof. The existence of a connected execution can be checked in polynomial space by Theorem 3.2. However, the size of such an execution can be exponential, and checking the property P (G 1 , G 2 , c s , c g ) requires iterating over the step of the execution. We thus need to combine the enumeration of the connected execution as we check P recursively.

The procedure to check P (G, G K , c, c g ) works as follows. We non-deterministically guess a connected execution step by step, from c to c g using the PSPACE algorithm of Theorem 3.2. We thus only keep the last configuration in memory, a binary integer counter to bound the length of the execution (bounded by the number of configurations, thus an exponential), and the current graph G K . If there is no such execution, we accept. Otherwise, at each step, say, after having visited execution π and generated next configuration c we enumerate all possible sets K = k(K 0 , πc ) G , where K 0 is the initial knowledge for the pair (G 1 , G 2 ). This can be done by enumerating all subsets of movement edges adjacent to c , present in G K but not (⇒) Assume that the QBF ϕ is true. There exists a collection of Skolem functions A such that for each existential variable z i (where i is even), and an assignment ν to universally quantified variables in z 1 , z 3 , . . . , z i-1 , A z i (ν) ∈ { , ⊥} is the value assigned to z i such that ϕ is true under assignment ν augmented with the values of A. We construct the following strategy σ, which guarantees that c g is reached in k steps from c s .

Intuitively, the lengths of the initial movement paths are designed so that agents starting at s z i arrive at v z i in the order of their indices. For an existential variable agent, the choice of the successor from v z i determines the value of z i ; while for a universal variable agent, the choice is made by the environment. More precisely, if the agent moves to r z i , then z i is set to true, if she moves to l ¬z i it is set to false.

Formally, all agents start by moving to their respective v nodes (e.g. A clause agent at s γ moves to v γ ). They arrive at these nodes at different moments due to the sizes of their movement paths. An existential variable agent arrives at node v z i at time 3(i -1) + 1. At this point, all universal variable agents among z 1 , z 3 , . . . , z i-1 have arrived to their respective nodes v z j , thus revealing the values of these variables. Let ν be this assignment. If A z i (ν) = , the agent moves to r z i , and otherwise, to l ¬z i .

When a universal variable agent arrives to v z i at time 3(i -1) + 1, she follows the only edge dictated by the environment, either to r z i or to l ¬z i . This assigns to the variable z i in the former case, and ⊥ in the latter case. Observe that if the graph is admissible, then there must exist a path from source to target for each agent; this means that one of these edges must be present.

Consider a positive (resp. negative) occurrence agent associated to a clause γ. This agent arrives to v z i (resp. v ¬z i ) at time 3(i -1) + 2. Observe that the variable agent has already determined the value of z i in the previous step.

• if z i is assigned (resp. ⊥) then the agent moves to t γ , observe which edges are available at t γ , and immediately comes back to v z i (resp. v ¬z i ). Now, the edge between r z i (resp. l ¬z i ) and u z i (resp. u ¬z i ) has been observed by agent z i ; so if this edge is present, she moves to r z i and u z i ; and if not, then the edge from l z i to u z i must be available, and she arrives to t z i (resp.

• if z i is assigned ⊥ (resp. ) then she does not visit t γ , but moves to l z i (resp. l ¬z i ). If the edge between l z i (resp. l ¬z i ) and u z i (resp. u ¬z i ) is available, she moves to t z i (resp. t ¬z i ), otherwise she moves back and reach t z i (resp.

It remains to argue that clause agents can reach their target nodes within k steps. Since ϕ is true, by the definition of A, whatever the choice for the universal variables, some literal of each clause γ is assigned to true. Therefore, the positive or negative occurrence agent corresponding to this literal visits t γ , thus revealing the edges available from t γ to r γ and l γ . Note that at least one of these edges must be available for the graph to be admissible. Thus, a clause agent arriving to v γ at time 3(n -1) + 3 can follow the available path to reach t γ exactly at time k.

(⇐) Let σ be a witness joint strategy. Following σ, each clause agent c must know the available edges in the rest of their paths at time 3(n -1) + 3 since otherwise they cannot ensure reaching t γ at time k. Thus, for each clause γ, the node t γ is visited by some occurrence agent under strategy σ. Furthermore, an occurrence agent z (resp. ¬z) can visit node t γ and still make it to t z (resp. t ¬z ) in time iff the associated variable agent has observed the presence of the edge We define the initial and target configurations as: (⇒) Suppose the DQBF ϕ holds, and let A be the collection of Skolem functions. We build the following joint strategy. The environment chooses the truth values of universal variables z by deleting some edges v z to z or v z to ⊥ z . If the environment deletes the edge v z to z , the agent is forced to pass in ⊥ z , thus the variable z is considered to be false. If the environment deletes the edge v z to ⊥ z , the agent is forced to pass in z , thus variable z is considered to be true. If the environment deletes neither edge, then we define the strategy for agent a y to choose to pass in y, making y true by default.

The rest of the strategy is defined as follows. At the first step, each variable agent for variable z moves to v z , and each observation agent for the pair (x, y) moves to v y , and thus observes the value of universal variable y. At the second step, existential agents remain in place, while observation agents move to v O , thus sharing their observations with the corresponding existential agents. Thus, at this point, each existential agent corresponding to variable x knows the values of all universal variables y ∈ O x . Then, agent z moves to z if A z (ν) = 1 and to ⊥ z otherwise, where ν is the valuation of the variables in O z .

All clause agents move from s i to γ i and remain at γ i for two steps so that all existential and universal variable agents z are at z or ⊥ z . The verification moves to v γ and also waits for two steps. Since each clause is satisfied by the currently read valuation, each clause agent γ i communicates at least with one existential or universal agent. Thus, the verification agent communicates with all clause agents via these variable agents. Since the clause agents communicate with the verification agent at this moment, the latter can see which edges are present in the clause gadget, and can continue go to t γ without getting stuck.

(⇐) Conversely, suppose there is a witness joint strategy, in particular ensuring that the verification agent goes to t z . This means that the agent must have received all the information about the topology around vertices γ 1 , . . . , γ k . But this is only possible if the agents have occupied a configuration in which the verification agent is at v γ , all clause agents are at γ i such that for each clause γ i , there is at least one variable agent z at z if z ∈ γ i and at ⊥ z if ¬z ∈ γ i . Thus, ϕ is a positive instance of TDQBF.

Bounded Case

In the bounded case, the problem is NEXPTIME-complete independently of the encoding of the bound. Moreover, the hardness holds even for undirected graphs. Theorem 6.5. bDMAPFI is NEXPTIME-complete, NEXPTIME-hardness holds for undirected graphs.

Proof. The upper bound when the bound k is given in unary is obtained by the following nondeterministic algorithm:

(1) Guess a strategy σ i for each agent i, up to executions of length ≤ k. Such a strategy can be represented as a tree of depth k, and thus has size exponential in k.

(2) Check that σ i is uniform for agent i.

(3) For all admissible graphs G such that G 1 ⊆ G ⊆ G 2 , execute the joint strategy σ and check that the outcome execution from the initial configuration leads to the target configuration.

The obtained algorithm is non-deterministic and runs in exponential time. Note that the encoding of k is not relevant since for k ≥ 2|V | there is always a solution following the unbounded case.

We now prove the NEXPTIME-hardness result by reduction from TDQBF. Given an instance of TDQBF ∀y 1 , . . . , y n ∃x 1 (O x 1 ) . . . ∃x n (O xn ) ψ, we build an instance of bounded decentralized reachability (G 1 , G 2 , c s , c g , k). We denote the number of clauses by m.