Arthur Queffelec Nukkai

Ocan Sankur

François Schwarzentruber

Complexity of Planning for Connected Agents in a Partially Known Environment

Keywords: multi-agent path finding, multi-agent planning, connectivity, imperfect knowledge, decentralized planning

The Connected Multi-Agent Path Finding (CMAPF) problem asks for a plan to move a group of agents in a graph while respecting a connectivity constraint.

We study a generalization of CMAPF in which the graph is not entirely known in advance, but is discovered by the agents during their mission. We present a framework introducing this notion and study the problem of searching for a strategy to reach a configuration in this setting. We prove the problem to be PSPACE-complete when requiring all agents to be connected at all times, and NEXPTIME-hard in the decentralized case.

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 Email addresses: arthur.queffelec@nukkai.fr (Arthur Queffelec), ocan.sankur@irisa.fr (Ocan Sankur), francois.schwarzentruber@irisa.fr (François Schwarzentruber) 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 [START_REF] Amigoni | Multirobot exploration of communication-restricted environments: A survey[END_REF]; [START_REF] Yu | Planning optimal paths for multiple robots on graphs[END_REF] 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 multirobot exploration[END_REF][START_REF] Wurm | Coordinated multi-robot exploration using a segmentation of the environment[END_REF][START_REF] Matignon | Coordinated multi-robot exploration under communication constraints using decentralized Markov decision processes[END_REF]. However, the theoretical complexity of the underlying decision problems has not been addressed before. Our objective in this paper is to present a framework to study the theoretical complexity of planning problems on discrete graph models with respect to these three aspects.

The theoretical complexity of several related problems has attracted attention, and several results are available in the literature. Multi-Agent Path Finding (MAPF) is an important framework introduced to study collision-free navigation of agents in warehouses (see [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 Conflict-Based Search (CBS) [START_REF] Sharon | Conflict-based search for optimal multi-agent pathfinding[END_REF].

An extension of MAPF with connectivity constraints, called Connected MAPF (CMAPF), was studied as well [START_REF] Hollinger | Multirobot coordination with periodic connectivity: Theory and experiments[END_REF]; while the theoretical complexity and some algorithmic solutions are presented in [START_REF] Tateo | Multiagent connected path planning: PSPACE-completeness and how to deal with it[END_REF][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 Canadian Traveler Problem (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 defined 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] Lita | A system for multi-agent coordination in uncertain environments[END_REF]. While a notion of communication was considered in [START_REF] Zhang | The k-Canadian travelers problem with communication[END_REF][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. However, communication abilities are more restricted in some applications where agents may be required to serve as relays in order to maintain a fully connected communication topology. We are interested in studying the setting where agents' ability to communicate depends on their positions in the graph. The positions in the graph where communication is possible can be derived from the underlying communication model for the application at hand [START_REF] Amigoni | Multirobot exploration of communication-restricted environments: A survey[END_REF].

In this paper, 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 the following aspects on complexity: (A) connectivity; (B) collisions; (C) bound on the length of the execution. For (A), we consider either fully-connected strategies, requiring that the agents remain connected at all times during the mission, or decentralized strategies, allowing agents to disconnect and reconnect. While a decentralized framework might be sufficient in many cases, some applications do require a constant connection to be maintained among all agents, for instance, in order to implement a video stream 1 .

The survey in [START_REF] Amigoni | Multirobot exploration of communication-restricted environments: A survey[END_REF] presents a discussion on various connectivity requirements.

(B) While collision constraints are necessary to consider in most planning application, some works have ignored them during the high-level planning assuming a local collision avoidance system (e.g. [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]). Although we believe that it is more natural to include these constraints, studying separately the case with and without collision constraints has the advantage of understanding the source of complexity in planning algorithms with various aspects. We will indeed present our results with and without these constraints and show that the problems are hard even without these. (C) Providing an upper bound on the length of the executions is natural when one is looking to compute short plans. In fact, the bounded problem is the decision problem corresponding to the optimization problem where the goal is to minimize the length of the plan.

Our results are summarized in Table 1. The PSPACE algorithm for the connected problem with a bounded execution is subtle and relies on a vari-ant of the Savitch's theorem [START_REF] Savitch | Relationships between nondeterministic and deterministic tape complexities[END_REF] we present here. Interestingly, 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 consider a setting where the planning is centralized but the execution itself is decentralized. In other words, the agents know the entire strategy profile, but do not have access to full observation during the execution. In this setting, we prove the NEXPTIMEhardness 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. We distinguish the case of the binary and unary encodings of the bound. We also present a matching NEXPTIME upper bounds in some cases and a general 2NEXPTIME upper bounds (see Table 1).

Let us compare our results 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 (with collision constraints but 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 PSPACE-hardness is due to connectivity constraints. Some algorithms were presented for CMAPF in [START_REF] Tateo | Multiagent connected path planning: PSPACE-completeness and how to deal with it[END_REF] but these did not take collision constraints into account. 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 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 [START_REF] Amato | Decentralized control of partially observable Markov decision processes[END_REF] for a survey). This suggests that efforts might be directed in designing, e.g. heuristic approaches, rather than complete algorithms which will not scale. A preliminary version of this work appeared in [START_REF] Queffelec | Planning for connected agents in a partially known environment[END_REF] in which several results

were presented without proof, or with short sketches, and the imperfect information formalism was only informally described. This paper is an improved version with detailed formalism, examples, and full proofs.

Overview. In Section 2, we present preliminary definitions; and in Section 3, we present our framework, including the modeling of information exchange between agents, and we formally define the problems we study. Section 4 contains our complexity results for the connected case, and Section 5 for the decentralized case. Last, Section 6 contains conclucions and discussions.

Preliminaries

Connected MAPF. We consider a setting where agents move on a graph, with the vertices being their possible locations and the movement edges defining how We suppose that each vertex has a self-loop movement edge and a self-loop communication edge. This respectively represents the ability of an agent to stay at their location and to communicate with a nearby agent (i.e. at the same location/vertex).

Although we present our setting mainly for directed graphs, we also consider the undirected graphs in which E m contains subsets of vertices of cardinal 2, and contains all singletons (self-loops).

Definition 2. A configuration of size n is a tuple c = c 1 , . . . , c n ∈ V n where c i is the vertex of agent i.

In our setting, each agent simultaneously moves from their current vertex to an adjacent vertex at each step. We thus write c → c when (c i , c i ) ∈ E m for all 1 ≤ i ≤ n. This means that each agent i can move from their vertex c i in c

to their vertex c i in c in one step.

Definition 3 (Execution). An execution π is a sequence of configurations

π[0], π[1], . . . , π[ ] such that π[t] → π[t + 1] for all t ∈ {0, . . . , -1}.
The length of π = π[0], π [START_REF] Dresner | A multiagent approach to autonomous intersection management[END_REF], . . . , π[ ] is and is denoted by π : it is the number of steps in the execution. We write π[0..t] to denote the sub-execution

π[0], π[1], . . . , π[t] of π.
Moreover, last(π) denotes the last configuration of π.

We say that a configuration c is connected iff the subgraph of the vertices occupied by the agents form a connected graph for relation E c , i.e. the graph

V a , E c ∩ (V a ×V a ) is connected with V a = {c 1 , . . . , c n }.
An execution is said to be connected iff all its configurations are connected. The Connected Multi-Agent

Path Finding problem consists in finding a connected execution for the agents from a given initial configuration to a target configuration. We summarize below the known complexity results for the CMAPF problem.

Theorem 1 ([18]

). The problem of deciding whether, in a given instance (G, c s , c t , k)

where k is unary, there is a connected execution from c s to c t of length at most k is NP-complete.

Theorem 2 ([19]

). The problem of deciding whether for a given instance (G, c s , c t , ∞), there exists a connected execution from c s to c t is PSPACE-complete.

Note that we first present our results without collision constraints (that is, allowing several agents to be on a given vertex at the same time). We then explain in Section 6.1 how to incorporate these constraints to obtain the results in the general setting with connectivity and collision constraints. This is thus similar to CMAPF with perfect knowledge, which is not harder to compute with or without collision constraints [START_REF] Tateo | Multiagent connected path planning: PSPACE-completeness and how to deal with it[END_REF][START_REF] Charrier | Complexity of planning for connected agents[END_REF]. 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 5.

Dependency

Our framework

Modeling Imperfect Information

To formalize CMAPF in the imperfect information setting, let us show how to represent the initial knowledge of the agents, and how the information they have evolves during the execution. Agents initially know the exact set of vertices, but only have a lower and an upper approximation of the actual graph: they know that some (communication or movement) edges are certainly present or certainly absent, while some are uncertain (they may be present or absent).

Definition 4 (Initial Knowledge). The initial knowledge is modeled by a pair of topological graphs (G 1 , G 2 ), with the graph G 1 = V, E m 1 , E c 1 a lower bound, and G 2 = V, E m 2 , E c 2 an upper bound on the knowledge about the actual graph

with E m 1 ⊆ E m 2 and E c 1 ⊆ E c 2 .
The agents initially know given 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 m 1 ⊆ E m ⊆ E m 2 and E c 1 ⊆ E c ⊆ E c 2 , 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 m 1 (resp. E c 1 ); it is said uncertain (i.e. can be absent) if it is in E m 2 \ E m 1 (resp. E c 2 \ E c 1 )
. We assume that the communication edges of the actual graph are undirected, so for all (u, v) Remark 1 (Undirected Graphs). We will also consider the case of undirected graphs. In this case, we suppose that the agents know that G is undirected, that A history contains a graph G, and an execution (Definition 3) in that graph.

∈ E c 2 \ E c 1 , either (u, v), (v, u) ∈ E c , or (u, v), (v, u) ∈ E c .
is, E m 1 , E m ,
In our setting, the graph G is chosen by an adversary such that

G 1 ⊆ G ⊆ G 2 .
A strategy σ i for agent i tells where to go next at a given history. Formally: Definition 5. A strategy σ i for agent i maps any graph G and any execution π in G to a vertex such that (v, σ i (π)) ∈ E m where v is the vertex at which agent i is in the last configuration of π.

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 π defined by induction as follows:

π[0] is c s , and for t ≥ 1, π[t] is the configuration in which agent i is at vertex σ i (π[0..t -1]).
In the context of imperfect information, the behaviors of the agents only depend on their observations, as in imperfect information games as in [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 they occupy. 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-Noy | 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 4. For agent i and execution π, let us denote by k i (π) G the knowledge of agent i about the graph after observing the execution π in actual graph G. Given such knowledge K = k i (π) 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 .
In general, G K contains edges that are certainly in the graph given the current knowledge, while G K also contains those that may be in the graph. The latter are the edges of G 2 that were not ruled out by the current knowledge.

We will now formalize these definitions.

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

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

i 1 = i and i k = j, that is, (c i l , c i l+1 ) ∈ E c for 1 ≤ l ≤ k -1.
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 m 1 } ∪ {o c u,v | (u, v) ∈ E c 1 }∪ {o ¬m u,v | (u, v) / ∈ E m 2 } ∪ {o ¬c u,v | (u, v) / ∈ E c 2 } where G i = V, E m i , E c i .
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 i ( K, π) G of agent i after observing execution π in actual graph G, with K = (K j ) 1≤j≤n , where each agent j starts with initial knowledge K j , is defined by induction on π:

• k i ( K, ) G = K i • k i ( K, πc) G is the union of: k i ((K j ) 1≤j≤n , π) G ;
(a)

obs i (c); (b) j connected to i in c (k j ( K, π) G ∪ obs j (c)). (c)
Intuitively, the knowledge of an agent is composed of (a) her knowledge collected until that point, (b) her current observation, and (c) the knowledge of the agents she is connected to and their current knowledge.

When the agents start with an initial knowledge (G 1 , G 2 ) that is clear from the context, we will omit the tuple K = (K j ) 1≤j≤n and simply write k i (π) 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 i ( K, π) G .
In the rest of the paper, 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.

Definition 6 (Uniform Strategies). Let G be a topological graph, (G 1 , G 2 ) an initial knowledge, and write

K = (K 0 (G 1 , G 2 )) 1≤j≤n . A strategy σ i for agent i is uniform if for all executions π, π such that 1. π = π (π and π have the same length), 2. k i ( K, π) G = k i ( K, π ) G ,
3. for all t ∈ {0, . . . , π }, for all agents j, (a

) (i is connected to j in π[t]) iff (i is connected to j in π [t]);
(b) and for all j, if i and j are connected then π

[t] j = π [t] j , we have σ i (π) = σ i (π ).
In the previous definition, agents' strategies may depend on the length of the current history. We are also interested in a particular class of strategies whose decisions only depend on the current knowledge, and not on the length of the history. These strategies appear in the literature in some restricted settings such as two-player games with imperfect information, and they are known to suffice for winning for reachability or safety objectives in such games [START_REF] Raskin | Algorithms for omega-regular games with imperfect information[END_REF].

Definition 7 (Knowledge-based Strategies). Let G be a topological graph, (G 1 , G 2 )
an initial knowledge. A strategy σ i for agent i is knowledge-based if for all executions π, π such that such that

1. k i ( K, π) G = k i ( K, π ) G ,
2. for all agents j, (a) (i is connected to j in last(π)) iff (i is connected to j in last(π ));

(b) and for all j, if i and j are connected then last(π) j = last(π ) j , we have σ i (π) = σ i (π ).

We will see in Section 5 that knowledge-based strategies are not always sufficient in our case.

Decision Problems

We consider the decision problem of reaching a configuration c t from a configuration c s in less than k steps, using uniform strategies. For two configurations c s , c t , let us call a topological graph G (c s , c t )-admissible if there is an execution from c s to c t , which is not necessarily connected.

Definition 8. We say that an instance (G 1 , G 2 , c s , c t , k) is positive if there exists a joint strategy σ such that in all (c s , c t )-admissible graphs G satisfying

G 1 ⊆ G ⊆ G 2
, the outcome of σ starting in c s ends in c t 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 t )-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 2. Consider the example of Figure 2. 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 8. For two configurations c s , c t , we say that a topological graph G is (c s , c t )-c-admissible if there is a connected execution from c s to c t . We will often omit the pair of configurations which will be clear from the context, and write simply admissible or c-admissible.

Definition 9. We say that an instance 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

(G 1 , G 2 , c s , c t , k) is c-positive if there exists a joint strategy σ such that in all (c s , c t )-c-admissible graphs G satisfying G 1 ⊆ G ⊆ G 2 ,
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 8 and 9 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 Connected MAPF 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.

Bounded Decentralized Reachability. Is given instance (G 1 , G 2 , c s , c t , k), with k < ∞, positive? Bounded Connected Reachability. Is given instance (G 1 , G 2 , c s , c t , k), with k < ∞, c-positive? Unbounded Decentralized Reachability. Is given instance (G 1 , G 2 , c s , c t , ∞) positive? Unbounded Connected Reachability. Is given instance (G 1 , G 2 , c s , c t , ∞) c-positive?
The bounded problems will be considered both for the unary and the binary encodings of the bound k. Lower bounds are all obtained for the unary encoding; these imply the same lower bounds for the binary encoding. Concerning the upper bounds, we explain for each case how to design an algorithm with k encoded in unary or binary. We also consider these problems distinguishing directed and undirected graphs.

The complexity results are summarized in Table 1. We establish these results in the subsequent sections.

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 entity 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 3. The unbounded connected reachability problem is PSPACE-complete both for directed and undirected graphs.

The PSPACE lower bound follows from Theorem 2 with G 1 = G 2 .

For the upper bound, let us explain the intuition of the algorithm. Fix in-

stance I = (G 1 , G 2 , c s , c t , ∞). If I is c-positive, then G 2 must admit a connected
execution π from c s to c t such that along this execution, whenever the absence of a set of edges is revealed, there should still exist a connected execution from the current configuration to c t , unless the graph reveals to be not c-admissible. This is a recursive property that is necessary since it is satisfied by all witness strategies. We prove that it is also sufficient for c-positive instances.

We now formalize this intuition. Let us define the following recursive property: P (G, G, c, c t ) holds for graphs G, G, and configurations c, c t if either G is not (c s , c t )-c-admissible, or there exists a connected execution π from c to c t 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 1

≤ i 0 ≤ π + 1 with k(K 0 , c) G = k(K 0 , π[0..i 0 -1]) G , and either π[i 0 ] = c t or (k(K 0 , c) G K = k(K 0 , π[0..i 0 ]) G and P (G K , G K , π[i 0 ], c t )).
The following two lemmas prove Theorem 3.

Lemma 1. An instance I = (G 1 , G 2 , c s , c t , ∞) is c-positive if,

and only if

P (G 1 , G 2 , c s , c t ).
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, |E m 2 | -|E m 1 | + |E c 2 | -|E c 1 |: For all graphs G 1 ⊆ G ⊆ G ⊆ G 2 , and configurations c, if the instance (G, G, c, c t , ∞) is c-positive then P (G, G, c, c t ).
If G = G then either the instance is not c-admissible and, P (G, G, c, c t ) holds, or there is a connected execution π in G from c to c t in which case the property holds as well with i 0 = π + 1.

Assume G G, and consider σ a witness strategy for the instance (G, G, c, c t , ∞). Let us now show that all instances that satisfy the property are c-positive.

Assume P (G 1 , G 2 , c s , c t ) 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 t ), by induction on the length of π.

Assume σ is constructed for an execution π and knowledge K. If G K is not cadmissible, 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 t ) as well as the index i 0 . We define σ so that agents follow π until index i 0 , in which case either π [i 0 ] = c t , or P (G K , G K , ππ [1..i 0 ], c t ). In the former case, π has reached the goal configuration; in the latter case, we extend the execution by the induction hypothesis.

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

Proof. The existence of a connected execution can be checked in polynomial space by Theorem 2. However, the size of such an execution can be exponential, and checking P (G 1 , G 2 , c s , c t ) 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 t ) works as follows. We non-deterministically guess a connected execution from c to c t in G K step by step, using the PSPACE algorithm of Theorem 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 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 t ). 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. Let us first prove the upper bound when k is given in unary.

Theorem 4. The bounded connected reachability problem is in PSPACE when the bound is given in unary, both for directed and undirected graphs.

As APTIME = PSPACE [START_REF] Chandra | 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 3. The alternating algorithm decides the bounded connected reachability problem.

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, there is a joint strategy σ ensuring that such that for all choices of an admissible graph G, the agents arrive at a target configuration. 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 player reveals 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, or when two agents are at different vertices and observe whether a communication edge is present or absent. The number of times this happens is quadratic in the number of vertices. 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. We prove here the following generalization of Savitch's theorem which proves that our problem is in 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.

Thus:

Theorem 5. The bounded connected reachability problem is in PSPACE when the bound is given in binary, both for directed and undirected graphs.

We say that a topological graph has a complete connectivity graph if there are communication edges between all pairs of vertices. The hardness of the bounded connected reachability holds even in this case, regardless of the encoding used for the given bound.

Theorem 6. The bounded connected reachability problem with a complete connectivity graph is PSPACE-hard both in unary and binary encodings. Moreover, PSPACE-hardness holds for undirected graphs.

Proof. The lower bound is proven by reduction from the true QBF problem.

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 4. More precisely, for each variable z, we create a gadget shown in Figure 4a. Here, a b . . . N represents an undirected movement path from u to v with N edges connecting vertices u and v (with N -1 fresh intermediate vertices). When N = 0, we identify vertices u and v. For each clause, we create a gadget as depicted in Figure 4b. 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 t 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 t , k) is c-positive with k = 3(n-1)+5.

We classify the agents as follows. • A Variable agent is an agent starting at a node 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) . . . 3(i -1) + 1 . . . 3(i -1) + 1 . . . 3(n -i) +
• 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 ).

(⇒) 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 for each assignment ν to universally quantified variables in z 1 , z 3 , . . . , z i-1 ,

A zi (ν) ∈ { , ⊥} 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 t is reached in k steps from c s .

Intuitively, the lengths of the initial movement paths are designed so that agents starting at s zi arrive at v zi in the order of their indices. For an existential variable agent, the choice of the successor from v zi 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 zi , then z i is set to true, if she moves to l ¬zi it is set to false.

Formally, all agents are at their initial vertices at time τ = 0. They 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 zi at time τ = 3(i -1). At this point, all universal variable agents among z 1 , z 3 , . . . , z i-1 have arrived to their respective nodes v zj , thus revealing the values of these variables. Let ν be this assignment. If A zi (ν) = , the agent moves to r zi , and otherwise, to l ¬zi .

When a universal variable agent arrives to v zi at time 3(i -1), she follows an available edge chosen by the environment (or by convention r zi if both are available), either to r zi or to l ¬zi . 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.

must go from v z to t γ and come back to v z since any other way of visiting t γ would yield an execution longer than k.

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 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. Observe that under σ, some occurrence agents may arrive to their target vertices at time k -2 as this was the case in the first part of the proof. Notice that these agents cannot reveal any new information on the graph in just two steps, so their behaviors in the last two steps is harmless.

Hence, the joint strategy of the variable agents does determine an assignment function which satisfies ϕ.

The reduction was described for directed edges, but it also holds for the same construction with undirected edges, so PSPACE-hardness holds for undirected movement graphs as well.

Observe that the bound k = 3(n -1) + 5 computed in this reduction can be written in polynomial space, so PSPACE-hardness holds when the bound is encoded in unary.

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.

Upper bounds

We start with decision procedures for the bounded case by distinguishing the cases of unary and binary encodings. All decision procedures described in this section hold both for directed and undirected graphs, except for Theorem 8.

Theorem 7. The bounded decentralized reachability problem is in NEXPTIME, when the bound is given in unary, and in 2NEXPTIME when the bound is in binary.

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

1. Guess a strategy σ i for each agent i, up to executions of length ≤ k. Such a strategy is a function that maps each history whose executions are of length at most k to an action. A history is made of a graph G and an execution. The number of graphs G is exponential in the size of the input, and the number of configurations is exponential in the number of agents.

So the number of executions is exponential in k and in the number of agents. Therefore, the size of σ i is exponential in the input size. This guessing step thus requires exponential time.

2. Check that σ i is uniform for agent i. This step requires exponential time.

One can in fact enumerate all pairs of histories up to length k, check whether they are equivalent in the sense of Definition 6, and in this case check whether σ i prescribes the same action.

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. This step can also be done in exponential time. In fact, one can enumerate all admissble graphs in exponential time, and for each graph, generate the resulting execution up to length k.

The obtained algorithm is non-deterministic and runs in exponential time when k is in unary. When k is given in binary, the same procedure runs in doubly exponential time.

Although we are only able to obtain an upper bound of 2NEXPTIME in the general case when the bound is given in binary, we present two cases where a NEXPTIME procedure exists. First, in the case of undirected graphs, the bound can be assumed to be linear in the size of the input, thus the unary case can be applied:

Theorem 8. For undirected graphs, the bounded decentralized reachability problem is in NEXPTIME when the bound is given in binary.

Proof. For undirected graphs, there is always a winning strategy that finishes in time O(|V |). In fact, each agent can explore the graph in O(|V |) steps, and reach their target vertex if it is reachable. Because the graph is undirected, they will not be blocked and reach their targets if it is reachable. The bound can thus be assumed to be linear in the size of the input; and we can conclude with the unary case of Theorem 7.

We show that an NEXPTIME procedure can be obtained for directed graphs and binary encoding when strategies are restricted to knowledge-based ones.

These strategies are known to suffice for winning in the adversarial setting of two-player games with imperfect information [START_REF] Raskin | Algorithms for omega-regular games with imperfect information[END_REF]; although we do not know whether they are sufficient for the decentralized reachability problem.

Theorem 9. For knowledge-based strategies, the bounded decentralized reachability problem is in NEXPTIME when the bound is given in binary.

Proof. An NEXPTIME algorithm consists in guessing knowledge-based strategies for all agents and checking whether the joint strategy is a witness. Each knowledge-based strategy has exponential size since it is a function of the current knowledge and of the current vertex, and there are exponentially many knowledge sets. 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. This check can be done in exponential time by using a binary counter up to the given bound.

The case of knowledge-based strategies also allows us to obtain a decision procedure in the unbounded case. However the case of the unbounded decentralized reachability problem for general uniform strategies is open.

Theorem 10. For knowledge-based strategies, the unbounded decentralized reachability problem is in NEXPTIME.

Proof. We proceed as in the proof of Theorem 9 and guess a joint strategy made of knowledge-based strategies. The domain of the guessed joint strategy (made of n knowledge-based strategies) is of exponential size. So the induced execution either reaches the goal or cycles within exponential number of steps. We can thus simulate the execution until this bound using a binary counter for each graph G between G 1 and G 2 , and check whether the guessed joint strategy is a witness, in exponential time.

Let us show that knowledge-based strategies are not sufficient in the sense that there may not be a knowledge-based solution in positive instances of the bounded or unbounded decentralized reachability. Example 4. Consider the topological graph of Figure 5 with three agents:

G L R A L A R A B L B R B ? ?
Agents X A , X B , X G start, respectively at vertices A, B, and G, and they all want to go to G. Agents X A and X B need to know which one of the edges among L → G and R → G is present in order to reach G. This is easy for X A since they are connected to X G and has this information from the start. Assume L → G is present; then X A moves to vertices A L , L, G. In the meantime, X B can wait at B until X A reaches L, at which point they have necessary information to move to G as well. However, if only R → G is present, then X A moves through A R , R, G, and B will never comminicate with X A . The strategy for X B is to wait at B for two steps; if they get connect to X A , then they move towards L, otherwise, they move towards R. This, however, is not a knowledgebased strategy since in the latter case, the knowledge of X B does not change between the first step where they must idle at B, and the third step where they must move towards R. In fact, this instance does not admit a solution with knowledge-based strategies. After reaching γ 1 , the agent will enter in the subgadget for checking that γ 2 is true, and so on. The journey of the agent ends in the subgadget for checking that γ m is true. Then, the agent can reach their target t γ . Moreover, there are agents, called a i , starting at s i and ending at t i . They are called clause agents.

( 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
These are responsible for informing the verification agent about the available edges in this gadget. This will be explained below.

The gadgets have the following communication edges. Each vertex γ i certainly communicates with z iff z ∈ γ i (z appears positively in γ i ), and with ⊥ z iff ¬z ∈ γ i (z appears negatively in γ i ). Moreover, the vertex v γ communicates with all z and ⊥ z for all variables z.

We define the initial and target configurations as Let us give some intuition about the reduction. Assuming the DQBF ϕ is valid, one can build a witness strategy as follows. The variable agents starting at s z (at time 0) for some universal variable z are forced to follow a path not deleted by the environment, which determines the value of z. An observation agent starting at s (x,y) can observe the value of its respective universal variable y (by visiting v y at time 1), and then inform their respective existential agent a x thanks to the communication edge between v (x,y) and v x , at time 2. Thus, agents starting at an existential s z are aware of the values of all (universal) variables in O z and choose an appropriate value so as to satisfy ϕ. At time 3

c s = s γ ,
(after 3 steps), the agent starting in s γ is in v γ . Each agent starting in s i is in γ i . Also each variable agent have chosen the values of the variables and is either in z or ⊥ z . Thanks to the communication edges, and because ϕ is true, each γ i communicates with at least some z or ⊥ z , thus also with the agent at v γ .

Therefore, the latter agent knows about all available edges in the clause gadget and can successfully go to t γ .

The following lemma formalizes this intuition, and proves Theorem 11.

Lemma 5. DQBF ϕ is valid if and only if

(G 1 , G 2 , c s , c t , ∞) is positive.
replaced bold movement edges). Variable agents, observation agents, clause agents all perform 3 steps followed by 1 + 3m (3 + 1 + 3m = 4 + 3m) steps in these paths. The verification agent makes first 3 steps, and 3 steps in each clause subgadgets, plus one last step (3 + 3m + 1 = 4 + 3m). So the length of all executions is 4 + 3m.

⇐ Conversely, suppose there is a witness joint strategy. In particular, as all agents reach their goals in at most 4 + 3m steps, it means that they cannot backtrack, that is, all agents behave as if the graph was directed as in Figure 6 (otherwise the execution will be strictly longer than 4 + 3m). So the same arguments in the proof of the ⇐-direction of Lemma 5 apply, and φ is valid.

Remark 2. It can be shown that the NEXPTIME-hardness holds in directed graphs for a fixed bound k = 6 with a simple modification to the reduction above. In fact, the clause gadget can be split into m different smaller gadgets, with separate agents inside each one. The gadget for clause i would start at a fresh copy of the state s γ , and from v γ , would go to u γi directly, with the goal vertex being γ i . In other terms, all clauses can be verified in parallel.

Discussion

Collision Constraints

An execution is collision-free if in all its configurations, all agents are at distinct vertices. In its most general form, the problems we study require finding a bounded or unbounded connected and collision-free execution. The results presented above ignored collisions. Nevertheless, this property is already ensured by our proofs or can be obtained by simple modifications.

Note that we consider here a simple form of collision constraints which only require agents to be at distinct vertices at each time step. Stronger requirements have been considered in the literature such as avoiding head-on collisions (two agents swapping their locations within one step), or cyclic movements, such as, one agent going from v 1 to v 2 , another from v 2 to v 3 , and a third one going from v 3 to v 1 ; e.g. [START_REF] Zhang | Collision-free route planning for multiple agvs in an automated warehouse based on collision classification[END_REF].

The centralized case. The lower bound proof of Theorem 3 relies on Theorem 2 from [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.

In the proof of Theorem 6, we may consider non 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. More precisely, we extend the path between s z and v z (respectively, the path between s ¬z and v ¬z ) with 3m edges; and we extend the path between u z and t z , and the one between s γ and v γ with 3m edges as well. We select k = 3(n -1) + 5 + 3m

(that is, we also extend the considered bound by 3m.) Now we redefine the starting and goal vertices of the occurrence agents; these remain the same for all other agents. We consider an arbitrary order of the occurrence agents for each literal z or ¬z. For each literal, say z, the first occurrence agent starts at s z and their goal is between u z and t z precisely at a distance of k -2 edges from s z . The second occurrence agent starts at a distance of 3 edges from the first occurrence agent, and their goal is again between u z and t z , at a distance of k -2. The construction of Theorem 6 is adapted immediately to this variant.

In particular, the distance of 3 between the agents ensure that during the joint strategy of the proof of Theorem 6, agents never collide.

The upper bounds of Theorems 3 and 4 are adapted easily by adding the requirement that the guessed configurations must be collision-free.

The decentralized case. The reductions of Theorems 11 and 12 (see Figure 6) involve collisions. These can be adapted to obtain collision-free strategies when the formula is valid. Here the only collisions in the constructed strategy is between observation agents for observations of the form (x, y) and (x , y) since both visit v y at the same time. We can enforce that the observation agents visit the vertices v y at different times as follows. We extend the initial path in each gadget by n edges, where n is the number of variables. This means that in variable gadgets, there is a now a path of length n + 2 from s z to v z ; in the clause gadget, there is a path of length n + 3 from s γ to v γ ; and similarly from each s i to γ i . In observation gadgets, we replace the path s (x,y) → v y → v (x,y) of length 2 by s (x,y) → i v y → n-i v (x,y) if x is the i-th variable, where → i denotes a path of length i. Thus, observation agents visit v y at distinct times. In the unbounded case, the proof carries directly, and the presented strategy reaches the goal configuration with a delay of n without collisions. In the bounded case, the bound k must thus be increased by n.

All upper bounds based on nondeterministic procedures are adapted easily by additionally checking that the guessed joint strategy ensures collision-free executions under all possible graphs. The only exception is Theorem 8 since agents may not be able to explore the graph simultaneously.

In this case, with the additional assumption that E m ⊆ E c , one can obtain a polynomial bound on the length of the execution by the following joint strategy. problem (without connectivity constraints), which is known to admit solutions of size polynomial in the size of the graph [START_REF] Yu | Pebble motion on graphs with rotations: Efficient feasibility tests and planning algorithms[END_REF]. This shows that an execution of polynomial size always exists. One can thus conclude using Theorem 7adapted to take collisions into account.

Other Extensions

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 3 follows from [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, we can add the base vertex as an isolated vertex so that the reduction is still valid.

Graph Classes. The MAPF and CMAPF problems have been studied for different classes of graphs such as planar or grid graphs. The proof of lower bound in Theorem 3 relies on the proof of unbounded reachability done in [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.

Related Work

Different definitions of robust plans [START_REF] Ma | Multi-agent path finding with delay probabilities[END_REF][START_REF] Atzmon | krobust multi-agent path finding[END_REF][START_REF] Atzmon | Probabilistic robust multi-agent path finding[END_REF] have been studied. 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 imperfect 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. [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.

Interestingly CMAPF with perfect information is a special case of classical planning which is PSPACE-complete too [START_REF] Bylander | The computational complexity of propositional STRIPS planning[END_REF]. The connected reachability problem presented in this article is imperfect information and actions are deterministic and therefore can be represented as a deterministic POMDP (partiallyobservable Markov decision process) ( [START_REF] Littman | Algorithms for sequential decision-making[END_REF], [START_REF] Bonet | Deterministic POMDPs revisited[END_REF]), for which deciding the existence of a policy is PSPACE-complete (as our problem, see Theorem 3). Our complexity in our single metagent, which is the set of all connected agents is lower than the one presented in [START_REF] Rintanen | Complexity of planning with partial observability[END_REF]. The decentralized case can been seen as a particular case of decPOMDP (decentralized POMDP) [START_REF] Oliehoek | A Concise Introduction to Decentralized POMDPs[END_REF], and even QdecPOMDP (qualitative decentralized POMDP) [START_REF] Brafman | Qualitative planning under partial observability in multi-agent domains[END_REF]. Finite-horizon (in unary) planning in QdecPOMDP and decPOMDP is NEXPTIME-complete [START_REF] Bernstein | The complexity of decentralized control of Markov decision processes[END_REF], and our lower bound result can be seen as a refinement of that lower bound (Theorem 12).

Perspectives.

We proposed a setting for CMAPF in the imperfect 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 [START_REF] Wang | Tractable multi-agent path planning on grid 1165 maps[END_REF][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, and uncertainty.

  Undirected movement edges in E mCommunication edge in E c

Figure 1 :

 1 Figure 1: Example of a topological graph.

Figure 1

 1 Figure 1 gives an example of a topological graph. For instance, an agent can go from 1 to 3 in one step. Two agents at vertices 1 and 5 can communicate, but two agents at 1 and 4 cannot.

Figure 2 :

 2 Figure 2: An initial knowledge (G 1 , G 2 ).

Figure 3 :

 3 Figure 3: An initial knowledge of a topological graph (undirected case). Vertex s 7 has communication edges with all other vertices.

  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 t and P (G, G, c, c t ) 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 (G K , G K , π[i 0 ], c t , ∞) as well where K = k(π[0..i 0 ]) G . Since G K and G K have a smaller number of differences than G and G, we conclude by induction that P (G, G, π[i 0 ], c t ). Thus, P (G, G, c, c t ) holds.

Lemma 4 .

 4 STA(poly(n), * , poly(n)) ⊆ PSPACE.

Figure 4 :

 4 Figure 4: Gadgets for the reduction from QBF to the bounded reachability problem in the complete connectivity case.

Figure 5 :

 5 Figure 5: Instance where knowledge-based strategies are not sufficient.

Figure 6 :

 6 Figure 6: Gadgets in the reduction from DQBF to unbounded decentralized reachability (Theorem 11). The gadgets are the same in Theorem 12 with a minor difference: we replace (1) plain certain movement edges by undirected movement edges, and (2) bold certain movement edges by a path of length 1 + 3m where m is the number of clauses.

Agent 1

 1 starts by exploring all possible edges in linear time by avoiding other agents' positions, and returns to their initial position. After 2|E m | steps, Agent 2 similarly explores as much as they can without entering other agents' vertices, etc. When we are done iterating through all agents, each edge was visited at least by one agent, although not all agents may know the whole graph if the starting configuration is not connected. They then start sharing their knowledge by repeating the same steps, as follows. Agent 1 explores again a maximal set of vertices without visiting other agents' vertices, as in the first phase. During this traversal, because E m ⊆ E c , Agent 1 has communicated with all agents whose vertices are reachable while avoiding collisions, and thus shares their knowledge with them. Then, Agent i with i ≥ 2 runs again a traversal. Agents repeat this procedure n times. Notice that after the i-th iteration, each agent has received the knowledge of all agents whose vertices are reachable by a path containing at most i vertices occupied by other agents. Therefore, after the n-th iteration, all agents who belong to the same connected component of the graph know precisely the whole connected component. At this point, connectivity constraints are irrelevant, and the problem becomes an instance of the MAPF

Table 1 :

 1

Complexity Results for both the decentralized case (agents may disconnect and each agent is autonomous and has its own strategy and the connected case (agents must remain connected and the set of agents can be considered as a single meta-agent). The plan can be bounded by a threshold given either in unary or binary, or is unbounded (i.e. can be arbitrary long).

  and E m 2 are undirected graphs. Figure2depicts 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 whether each bridge is open and on the communication between s 1 and s 4 .

	Note that movement (resp.communication) edges that are not even in E m 2
	(resp. E c 2 ) are certainly absent.
	Example 1.

  3 Variable gadget for variable z. Edges between vz and l¬z, and between vz and rz are both certain if z is existential and both uncertain if z is universal.

				?		. . . 3(n -i)
				?
				∀z
		?	∃z
		?	∀z
				∃z
				?		. . . 3(n -i)
				?
	(a) s γ	. . . 3(n -1) + 3	v γ	r γ l γ	? ?	t γ
		(b) Clause gadget γ.
		Certain Movement edge
	?	Uncertain Movement edge

∀z ? ∃z Movement edge that is certain if z is existential and uncertain if z is universal . . . N Movement path with a total of N edges (vz, tγ ) ∈ E m 1 when z occurs in γ (v¬z, tγ ) ∈ E m 1 when ¬z occurs in γ

  , . . . , y n ∃x 1 (O x1 ) . . . ∃x n (O xn ) ψ, we build an instance (G 1 , G 2 , c s , c t , +∞) of unbounded decentralized reachability. We denote by γ 1 , . . . , γ m the clauses in ψ.The graph G 1 and G 2 are as follows. For each variable z, we create the gadget depicted in Figure6a. In this gadget, an agent denoted by a z , starts at s z , simulates the choice of the truth value of variable z and ends at t z . This agent a z is a variable agent and is said to be existential if z is an existential variable, and universal if z is a universal variable.We create the observation gadget for all existential variables x and for all (universal) variables y ∈ O x , depicted in Figure6b. For convenience, we write O 1 , . . . , O ω the finite list of such pairs (x, y) corresponding to observation of the truth value of universal variable y by the existential variable x. Such a pair (x, y) is simply called an observation. In this gadget, nodes v y and v x coincide with the node v z in the gadget for variable z for z = x and z = y. The agent a (x,y) that starts in s (x,y) is called an observation agent.Finally, we create the clause gadget, depicted in Figure6c. In this gadget, an agent, denoted by a γ , called the verification agent, will start at node s γ , and first reach v γ . After that node, they enter the subgadget for checking that the first clause γ 1 is true, and can reach node γ 1 without being stuck as we will see. Clause gadget. A verification agent starting in sγ can get stuck if some clause γ1, . . . , γm is not true. In the subgadget for clause γ1, the agent starting in s1 will reach γ1, and communicate with all variable agents whose valuations satisfy a literal in γ1. If the clause γ1 is satisfied by some variable valuation, the verification agent will be informed of the available edge to go to γ1.

			v (x,y)
	5.2. Lower Bound: The Unbounded Case Theorem 11. The unbounded decentralized reachability problem is NEXPTIME-hard. The lower bound is shown by a poly-time reduction from TDQBF. Given a DQBF ϕ = v z ∀z z ⊥ z t z ? ∃z ∀z ? ∃z (a) Gadget for variable z. Both edges (vz, z ) and (vz, ⊥z) are certain (resp. uncertain) if z is existential (resp. universal). The agent of this gadget will assign the truth value to variable z. s (x,y) v y v x t (x,y) (b) Gadget for the observation (x, y) of univer-sal variable y from existential variable x. At vy, the agent of this gadget will learn the truth value of y (enforced by the nature). At v (x,y) , it will share that information with the agent that will choose the value of x. rγ 1 t1 ? ? rγ m tm ? ? ∀y 1 s z vγ uγ 1 γ1 . . . uγ m γm tγ
		lγ 1	lγ m
	sγ
		s1	sm
	(c) Certain movement edge
		Certain communication edge
	?	Uncertain movement edge
	∀z ?	Certain (resp. uncertain) movement edge if z is existential (resp. universal)
	∃z

  s 1 , . . . , s m , s x1 , . . . , s xn , s y1 , . . . , s yn , s O1 , . . . , s Oω , c t = t γ , t 1 , . . . , t m , t x1 , . . . , t xn , t y1 , . . . , t yn , t O1 , . . . , t Oω .

This was the case, for instance, in the UAV Retina project in which the authors participated.

Acknowledgement. We thank the anonymous reviewer whose careful reading and suggestions substantially improved both the content and the presentation.

In particular, they suggested Example 4.

All variable agents then move to their respective target vertices t z which they reach precisely at time τ = k.

Consider a positive (resp. negative) occurrence agent associated to a clause γ.

This agent arrives to v zi (resp. v ¬zi ) at time 3(i -1) + 1. 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 occurrence agent moves to t γ , observes which edges are available at t γ , and immediately comes back to v zi (resp. v ¬zi ). Now, the edge between r zi (resp. l ¬zi ) and u zi (resp. u ¬zi ) has been observed by agent z i ; so if this edge is present, she moves to r zi and u zi ; and if not, then the edge from l zi to u zi must be available, and she reaches t zi (resp. t ¬zi ) at time τ = k.

• if z i is assigned ⊥ (resp. ) then the occurrence agent does not visit t γ , but moves to l zi (resp. l ¬zi ). If the edge between l zi (resp. l ¬zi ) and u zi (resp. u ¬zi ) is available, she moves to t zi (resp. t ¬zi ), otherwise she moves back and reach t zi (resp. t ¬zi ) at time k, through r zi (resp. r ¬zi ). The agent then reaches her target at time τ = k -2 in the first case, and at τ = k in the latter case.

It remains to argue that clause agents can reach their target vertices 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 = 3(n -1) + 5.

(⇐) 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 beforehand necessarily by some occurrence agent. In fact, if t γ was visited by another agent, then they would not be able to reach their target vertex before τ = k. Note also that, for instance a positive occurrence agent Proof. (⇒) Suppose the DQBF ϕ is valid, 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 through ⊥ 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 through z , thus variable z is considered to be true. If the environment deletes neither edge, then we define the strategy for universal agent a z to choose to pass through z , making the proposition z 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 (maybe forced by the environnement) of universal variable y. At the second step, existential agents are at v x in place, while observation agents move to v (x,y) , 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 a x moves to x if A x (ν) = 1 and to ⊥ x otherwise, where ν is the valuation of the variables in O x . The same occurs for universal variables y: a y moves to the unique successor left, or to y by default, if both successors are still reachable.

Between time 0 and 3, all clause agents move from s i to γ i , and the verification agent moves to v γ . At time 3, all existential and universal variable agents a z are at z or ⊥ z . Since each clause is satisfied by the currently read valuation, each clause agent a 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 .

Due to the directed edges, all agents must remain their designated gadgets in order to reach their targets. So 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.

Lower Bound: The Bounded Case

Theorem 12. The bounded decentralized reachability problem is NEXPTIMEhard both for directed and undirected graphs.

We prove the NEXPTIME-hardness result by poly-time reduction from TDQBF.

Given an instance of TDQBF ∀y 1 , . . . , y n ∃x 1 (O x1 ) . . . ∃x n (O xn ) ψ, we build an instance similar to the one discussed for Theorem 11, see Figure 6.

Let us now prove how to adapt the proof for undirected graphs. The naive adaptation would be to consider the construction given in Figure 6 but consider all edges as undirected. This will not work since for instance the existential variable agents could backtrack: they could choose to go to z and to return later on to ⊥ z . The trick is to avoid backtracking is to replace the certain movement edges depicted in bold in Figure 6 by a sufficiently long path, and to bound the total length of the execution. In this way, agents would not have the required time to backtrack. More precisely, the reduction is similar except that:

• certain movement edges that are not depicted in bold in Figure 6 are replaced by undirected movement edges;

• certain movement edges that are drawn in bold in Figure 6 are replaced by paths of length 1 + 3m, where m is the number of clauses in ψ.

• we fix the bound k = 4 + 3m. Lemma 6. DQBF ϕ is valid if and only if (G 1 , G 2 , c s , c t , 4 + 3m) is positive.

Proof. ⇒ Suppose the DQBF φ valid. We construct the strategies for the agent as in Lemma 5 (except that agents make 1 + 3m steps in the paths that