Reachability and Coverage Planning for Connected Agents

1 Introduction

A number of use cases of planning rose in informationgathering missions from the development of unmanned autonomous vehicles (UAVs). For instance, in search and rescue missions, a fleet of drones can cover a lot of ground in a short amount of time and report any finding to a mission supervisor to narrow the search for the rescue team. Other examples are the terrain analysis for smart farms and for areas in hazardous locations. For this kind of missions, the information gathered is used for decision making at a supervising station. Thus, the robots need to be constantly in communication with the station to report the information gathered during the mission. The use of multiple UAVs to cover an area not only reduces the time required to complete the mission but also enables reaching locations which may not be reachable with a single drone due to connection constraints.

The original multi-agent path finding problem asks for a plan to reach a configuration of agents in a graph [Ratner and Warmuth, 1986]. However, an important problem for search and rescue missions or terrain analysis is the coverage of an area. We thus study both the reachability and the coverage problems under a connection constraint over the agents which requires them to be connected to the base either directly or via another agent, who can relay its data. We establish the computational complexity of the connected coverage in its general case and for a practical subclass introduced recently [Tateo et al., 2018] in which the UAVs can communicate with others located within one step, called the neighbor-communicable topological graphs. We show that the coverage is PSPACE-complete in the general case, and remains so for neighbor-communicable topological graphs. Thus, restricting to neighbor-communicable graphs does not make the problem feasible, and the relatively high complexity unfortunately remains. Note that this is in line with the PSPACE-completeness of the reachability problem recently reported in [Tateo et al., 2018].

Our main result in this paper is the definition of a class of topological graphs which is well adapted and realistic for UAV missions, and for which the coverage and reachability problems admit efficient algorithms. Our subclass, called sight-moveable graphs, is defined assuming that the UAVs cannot communicate through obstacles and are restricted to line-of-sight communication. This class emerged from an ongoing case study for a drone assisted search and rescue project in which the authors take part 1 . For this class, we prove that both the reachability and coverage problems are in LOGSPACE. This drastically changes the status of this problem since by LOGSPACE ⊆ NC (this is the class of problems solvable in polylogarithmic time in a parallel machine with a polynomial number of processors), one can build an efficient parallel algorithm [Cook, 1979]. The bounded versions are NP-complete. This means efficient SAT solvers can be used directly to compute bounded executions.

In this work, we consider anonymous agents. Furthermore, we consider the collisions to be handled by the agents themselves, hence are not considered along the results of this paper. We depicted a covering execution of a topological graph by 3 UAVs in Figure 1. In this example, the UAVs need to gather information at each node of the graph while staying connected to the base (red node) during the whole mission.

In Section 2, we present the typical notions used in MultiAgent Path Planning (MAPP) and their extension for our case and the known results in connected planning. In Sections 3 to 6, we study the complexity of our problems from the general case to the most restrictive one. We describe the related work in Section 7. We conclude in Section 8.

This paper is the follow-up to the extended abstract presented at the 18th International Conference on Autonomous Agents and Multi Agent Systems (AAMAS 2019) [Charrier et al., 2019]. An extended version 2 is also available.

1 EIT Retina project

2 https://arxiv.org/abs/1903.04300

2 Preliminaries

In most applications of path planning, the space is discretized in order to generate a graph of movements on which algorithms are executed. For instance, regular grids which decompose the space in square, triangular or hexagonal cells, irregular grids with techniques such as quadtrees [Finkel and Bentley, 1974; Knoll, 2006] or Vorono¨ı diagrams comprehensively discussed in the survey [Aurenhammer, 1991].

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.

2.1 Topological Graph

Compared to the graphs used in MAPP, we also consider 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.

Definition 1 (Topological graph). A topological graph is a tupleG = 〈V,→, 〉, with V a finite set of nodes containing a distinguished element B, → ⊆ V × V a set of movement edges and ⊆ V × V a set of undirected communication edges.

The node B symbolizes the supervision base station from which the agents start the mission. A topological graph is undirected if 〈V,→〉 is an undirected graph.

We will now consider three subclasses of interest.

In most situations, if an agent can move to a location in one step, it can also communicate with an agent at that location. This class has been discussed in [Tateo et al., 2018]. We call topological graphs satisfying this requirement neighborcommunicable. An example is given in Figure 2b.

Definition 2 (Neighbor-Communicable topological graph). A neighbor-communicable topological graph is a topological graph such that v → v′ implies v v′ .

Another class of graphs is that of sight-moveable and is the main one for which we give efficient algorithms. First, this class requires the movement edges to be undirected and reflexive. Second, whenever an agent can communicate with another node, then it can also move to that node while maintaining the communication. This intuitively means that the communication is restricted to line-of-sight and is disallowed through obstacles. The formal definition follows, and an example is depicted in Figure 2c.

Definition 3 (Sight-Moveable topological graph). A sightmoveable topological graph is an undirected neighborcommunicable topological graph in which for all v ∈ V , v → v and whenever v v′ , there exists a sequence ρ = 〈ρ1, . . . , ρn〉 of nodes such that v = ρ1, v′ = ρn, v ρi and ρi → ρi+1 for all i ∈ {1, . . . , n}.

Last, we define the complete-communication topological graphs which are simply sight-moveable topological graphs with a complete communication topology. This subclass can model that the communication is not perturbed in the area. An example of such a graph is depicted in Figure 2d, and the formal definition is the following.

Definition 4 (Complete-Communication topological graph). A complete-communication topological graph is a sightmoveable topological graph such that = V ×V .

Observe that complete-communication graphs are reflexive, undirected, connected graphs with = V ×V .

2.2 Execution

An execution, in MAPP, is a finite sequence of configurations describing the placement of the agents during the mission. The formal definition of a configuration is the following.

Definition 5 (Configuration). A configuration c of n agents in a topological graph G is an element of V n denoted c = 〈c1, . . . , cn〉 in which ci is the location of agent i such that the graph 〈Va, ∩ (Va×Va)〉 is connected with Va = {B, c1, . . . , cn}. We extend the notation → and denote c → c′ when ci → c′i for all 1 ≤ i ≤ n.

MAPP asks to associate an agent to a specific goal. However, given that we are interested in covering an area with a fleet of agents, the anonymity is useful to get more efficient plans.

Anonymity. In the rest of this paper, agents are anonymous. In other words, a configuration c is equivalent to a configuration c′ iff c is a permutation of c′ .

Moreover, an important notion in MAPP is the computation of collision-free plans. In the drone case, in which we are particularly interested, one can place drones at different heights to avoid collisions. Additionally, most drones are, nowadays, equipped with local collision avoidance systems.

Collisions. We do not deal with meet- or head-oncollisions of agents, i.e. we allow two agents to be located in a same node, and to move in opposite directions of an edge within a step.

An execution e of length ℓ with n agents in a graph G is a sequence of configuration 〈c1 , . . . , cℓ 〉 such that for ci → ci+1 for all 1 ≤ i < ℓ.

A covering execution e = 〈c1 , . . . cℓ 〉 of length ℓ with n agents in a graph G is an execution such that c1 = cℓ = 〈B, . . . ,B〉 and for all v ∈ V , there exists i ∈ {1, . . . , ℓ} with v appearing in ci .

2.3 Decision Problems

We define the MAPP problems, the Reachability problem along with its bounded version, bReachability, for the makespan optimization of the plan. In addition, we define the Coverage problem and the bounded coverage, bCoverage.

Definition 6 (Reachability). Given a topological graph G, n ∈ N written in unary and a configuration c of size n, decide if there is an execution 〈c1 , . . . , cℓ 〉 in G such that c1 = 〈B, . . . , B〉 and cℓ = c.

Definition 7 (bReachability). Given a topological graph G, n ∈ N written in unary and a configuration c of size n and ℓ ∈ N written in unary, decide if there is an execution 〈c1 , . . . , cℓ′ 〉 in G s.t. ℓ′ ≤ ℓ and cℓ′ = c.

Definition 8 (Coverage). Given a topological graph G and n ∈ N written in unary, decide if there exists a covering execution with n agents.

Definition 9 (bCoverage). Given a topological graph G, n, ℓ ∈ N written in unary, decide if there exists a covering execution of length ℓ′ such ℓ′ ≤ ℓ.

We study the restrictions of the above problems to classes of topological graphs. We denote PC the problem P (one of the four above problems) restricted to a class C of topological graphs (C can either be dir for directed, nc for neighborcommunicable, und for undirected, sm for sight-moveable or cc for complete-communication topological graphs).

2.4 Known Results

The complexity of the decision problem associated to the minimization of the makespan with non-anonymous agents and collision, is known to be NP-hard [Ratner and Warmuth, 1986]. Throughout the study of MAPP, NP-hardness was shown to hold on planar graphs [Yu, 2016] and, later, on 2D grid graphs [Banfi et al., 2017]. Variants of MAPP have been studied such as the package-exchange robot-routing problem [Ma et al., 2016] where the robots are anonymous but not the package they exchange, is shown to be NP-hard. A class of grid graphs was shown to be solvable in polynomial time [Wang and Botea, 2009].

The connected version of MAPP was introduced in [Hollinger and Singh, 2012], 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 agents in a bounded amount of steps is NP-hard:

Theorem 10. bReachability restricted to undirected topological graphs is NP-hard [Hollinger and Singh, 2012].

In [Tateo et al., 2018], it is shown that deciding the existence of a feasible plan is PSPACE-complete:

Theorem 11. Reachability restricted to undirected topological graphs is PSPACE-complete [Tateo et al., 2018].

Authors prove this result for graphs with self-loops and a base [Tateo et al., 2018] as in our setting (see Discussion following Theorem 1). The only difference with our setting is that the agents start at a specific configuration in [Tateo et al., 2018]. Nevertheless, it can be shown that their complexity result holds for our problem by a simple but subtle construction given in the extended version.

In the rest of the paper, we study the upper bounds and the lower bounds complexity of the defined decision problems on the previously defined topological graphs. The following sections present our results, respectively, for the general case, the neighbor-communicable graphs, sight-moveable graphs, and complete-communication graphs.

3 Directed Topological Graphs

For the bounded versions, we can guess and check a path of bounded length in polynomial-time since the input is encoded in unary:

Proposition 12. bCoveragedir and bReachabilitydir are in NP.

For the unbounded problems, we can design a straightforward NPSPACE algorithm that guesses an execution by keeping in memory the last configuration, and, for Coveragedir, the set of visited regions. We conclude with Savitch's Theorem (NPSPACE=PSPACE)[Savitch, 1970]:

Theorem 13. Coveragedir and Reachabilitydir are PSPACE-complete.

The lower bound of Reachabilitydir is given in Theorem 11. We now concentrate on Coveragedir.

Lemma 14. Coveragedir is PSPACE-hard.

Proof. The proof is by reduction from Reachabilitydir in which the base node has a self-loop. As noted in the remark following Theorem 11, this problem remains PSPACE-hard. We map an instance (G, c) of Reachabilitydir to the instance G′ of Coveragedir where G′ is depicted in Fig. 3. Let k denote the number of agents in the instance (G, c). G′ contains G as a subgraph, plus fresh nodes v1, . . . , vk and s1, . . . , sk. An agent can move from any node of G to v1 and back.

Node s1 can communicate with the base B, and node vk can communicate with all nodes of G′ . Furthermore, we have the communication edges (si, si+1) and (vi, vi+1) for all 1 ≤

i ≤ k - 1. Now we prove that the k agents can progress to the configuration (c1, . . . , ck) in G if and only if there exists a covering execution in G′ .

(⇒) If the agents are in the configuration (c1, . . . , ck) then they can progress in one step to configuration (s1, . . . , sk). Then, they have no choice but progress to the configuration (v1, . . . , vk). Once in this configuration, the agent placed on the node vk communicates with the base and with all other agents. This agent stays at vk. Meanwhile the agent placed on the node v1 will visit all unvisited nodes of G and come back to v1 while keeping communication to the base through the agent placed on vk. Meanwhile, agents placed on v2, . . . , vk-1 come back to B. Finally, when all the nodes have been visited, both agents on v1 and vk come back to B. (⇐) If there exists a covering execution of the whole graph G′ , it means all nodes have been visited. In particular, node sk has been visited and let us consider the first time tsk when

sk is visited. Time tsk - 1 denotes the time just before tsk .

Fact 15. At time tsk - 1, no node vi and no node si were visited.

Proof. Suppose by contradiction that a node vi was visited by some agent before tsk , then the only possibility such an agent to communicate to the base is that there is also an agent at vk at time tsk . But then, it means that sk was visited strictly before tsk , leading to a contradiction. Thus, no node vi were visited at time tsk (thus at time tsk -1).

As no node vi are visited before tsk , no node si are visited before tsk - 1.

Proof. At time tsk , as the agent at sk needs to communicate with the base, the only possibility is that the configuration is 〈s1, . . . , sk〉. Thus, the only possibility is that configuration is 〈c1, . . . , ck〉.

Facts 15 implies that the prefix from time 0 to time tsk - 1 of the covering execution is an execution in G. Fact 16 implies that sub-execution reaches 〈c1, . . . , ck〉.

4 Neighbor-Communicable Topological Graphs

In this subsection, we show that our problems remain hard for neighbor-communicable graphs.

Theorem 17. Coveragenc is PSPACE-complete.

Proof. The upper bound is given by Theorem 13.

For the lower bound on Coveragenc, the reduction given in Figure 3 is not adapted for neighbor communicable graphs. Indeed, all nodes may be visited although c1, . . . , ck is not reached: v1 and vk can be reached by two lines of agents connected to the base, making the coverage of the full graph possible. We nevertheless give a similar reduction by adapting the previous reduction.

The details are given in the extended version.

5 Sight-Moveable Topological Graphs

In this subsection, we show that Reachabilitysm and Coveragesm are in LOGSPACE while the bounded version bReachabilitysm is NP-complete.

5.1 Upper Bounds

The results of this subsection rely on the problem of checking the connectivity of two nodes s and t in an undirected graph, namely USTCONN.

Theorem18. USTCONN is in LOGSPACE[Reingold, 2008]. Proposition 19. Reachabilitysm is in LOGSPACE.

Proof. The idea of the proof is to reduce Reachabilitysm to UCONN, that is the problem of deciding whether an undirected graph is connected. From Theorem 18, we can reduce UCONN to USTCONN by simply looping over all pairs of nodes (s, t) and checking for a path from s to t. Therefore, UCONN is in LOGSPACE.

Now we describe the logarithmic space reduction of Reachabilitysm to UCONN. Let G = 〈V,→, 〉 a sight-moveable topological graph and c a configuration. Let V ′ = {c1, . . . , cn,B}. The configuration c is reachable iff the restriction of G′ := (V, ) to the nodes in V ′ is -connected. Indeed, if it is, then c is reachable: each agent follows some →-path from B to ci contained in a -path from B to ci. In other words, (G, c) is a positive Reachabilitysm-instance iff G′ is a positive UCONN-instance. The reduction is in logarithmic space: we compute G′ by enumerating all (u, v) -edges 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. [Sipser, 1997], Ch. 8, Def. 8.21).

Proof. First we prove that the bounded version of the connectivity in undirected graphs is also in LOGSPACE.

Lemma 21. Bounded-USTCONN, that is the problem, giving an undirected graph G, two nodes s, t, an integer n written in binary, of deciding whether there is a path of length at most n from s to t in G is in LOGSPACE.

Proof. We reduce Bounded-USTCONN to USTCONN in logarithmic space as follows. From a BoundedUSTCONN instance (G, s, t, n) we construct in logarithmic space a USTCONN instance (G′ , s′ , t′ ): 1. The nodes of G′

are pairs (v, j) where v is a node of G and j is an integer in {0, n} but smaller than the number of nodes in G′ ; 2. 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).

Now let G = 〈V,→, 〉 be a sight-moveable topological graph and n an integer written in binary. There is a path from any node v to the base B with at most n communication edges iff (G, n) is a positive instance of Coverage. Thus, we test sequentially, for all v, that ((V, ), v,B, n) is a positive instance of Bounded-USTCONN . Hence, we obtain an algorithm in logarithmic space to decide Coverage.

5.2 Lower Bounds

We now focus on the NP lower bound of bReachabilitysm.

Proposition 22. bReachabilitysm is NP-hard for a fixed execution length ℓ ≥ 3.

Proof. The proof is by polynomial time reduction from 3-SAT problem (see [Karp, 1972]). Given a 3-SAT instance, set of clauses c1, . . . , cm with variables x1, . . . , xn, we describe the construction of an instance (G, c) of bReachabilitysm with k = n + m agents.

The topological graph G = 〈V,→, 〉 is constructed as follows. We start by placing the base B from which the agents start their mission.

Please recall that a sight-moveable graph is also a neighbor-communicable graph so all movements edges are also communication edges in the construction below even if not explicitly stated.

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

For each clause c, we construct a gadget composed of 3 nodes depicted in Figure 5b. We create a node c, a staging node nc and a goal node gc. We add movement edges from B to nc, from nc to c and from c to gc. The communication between a clause c and a literal x or ¬x is dictated by the existence of the literal in the clause: ci xj if and only if xj ∈ ci; and ci ¬xj if and only if ¬xj ∈ ci.

We add movement edges from gxi to gxi+1 , and from gci to gci+1 for all 1 ≤ i < n, as well as we from gxn to gc1 . Last, we add a fully connected path containing 3 fresh nodes from gx1 to the base such that gx1 B, 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. The snakelike path from gx1 to B is the fully connected path.

From a 3-SAT instance, one can construct the graph G and ask for an execution of length 3 to reach the configuration 〈gx1 , . . . , gxn , gc1 , . . . , gcm 〉.

The rest of the proof is given in the extended version.

From Propositions 12 and 22, we have:

Theorem 23. bReachabilitysm is NP-complete.

6 Complete-Communication Topological Graphs

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

Proposition 24. bReachabilitycc is in LOGSPACE.

Proof. From Lemma 21, one can construct an algorithm in LOGSPACE for bReachabilitycc. Indeed, given a configuration c and ℓ ∈ N, the straightforward iteration on the locations ci followed by the verification of a path of at most ℓ (given in unary) steps from B to ci yields a sound and complete algorithm for bReachabilitycc.

Our NP lower bound proof of the bCoveragecc 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 [Itai et al., 1982].

Theorem 25. bCoveragecc is NP-complete.

The upper bound follows from Proposition 12. The NPhardness proof is given in the extended version.

7 RelatedWork

The coverage planning is an interesting approach to path planning. Indeed, a covering plan can be used for fields such as floor cleaning, lawn mowing, etc. A survey of this field appears in [Choset, 2001]. This multi-agent extension has the ability to reduce the length of the overall mission and also reach parts of the area a single agent would not able to. This problem was studied in [Rekleitis et al., 1997] for two agents. As shown in the survey by Chen et al. [Chen et al., 2014], many coverage problems have been addressed by using analytic techniques. For instance, in [Yanmaz, 2012] and [Teacy et al., 2010], they consider UAVs that should cover an area while staying connected to the base, but only empirically study some path planning algorithms without proving formally their soundness and completeness.

We advocate formal methods that give formal guarantees and have already been applied to generate plans for robots and UAVs. Model checking has been applied to robot planning (see [Lacerda et al., 2014]) and to UAVs [Webster et al., 2011]. Humphrey [Humphrey, 2013] shows how to use LTL (linear-temporal logic) model checking for capturing response and fairness properties in cooperation (for instance, if a task is requested then it is eventually performed).

Bodin et al. [Bodin et al., 2018] treat a similar problem except that the UAVs cover the graph without returning to the base. Without the return-to-the-base constraint, we claim that all our hardness results still hold, except for bCoveragecc. They provide an implementation by describing the problem in Planning Domain Description Language and then run the planner Functional Strips [Franc`es et al., 2017].

Murano et al. [Murano et al., 2015] advocate for a graphtheoretic representations of states, that is, by assigning locations to agents as in Definition 5. In [Aminof et al., 2016;

Rubin, 2015], a general formalism is given to specify LTL and monadic second-order logic properties, which are expressive enough to describe the connectivity constraint. They provide an algorithm for parametrized verification in the sense that they check a temporal property in a class of graphs. This is relevant for partially-known environments. The algorithm described is non-elementary (i.e. the running time cannot bounded by any tower of exponentials) and therefore not usable in practice. We believe that this is an important problem and our paper identifies an efficient and relevant fragment.

The multiple traveling salesman problem (mTSP) is a generalization of the traveling salesman problem (TSP) in which multiple salesmen are located at a depot [Anbuudayasankar et al., 2016]. mTSP asks for the coverage of all cities so as to minimize the total plan cost by visiting each city exactly once. An overview of TSP and its extensions are presented [Matai et al., 2010]. The Coverage problem is related to mTSP, since we use results on Hamiltonian cycle to prove the NP-hardness of bCoveragecc. However, we wish to minimize the length of the execution and not the cost of the execution. Those problems are equivalent on unit graphs, but it is not trivial to use general results on mTSP in order to solve Coverage. Furthermore, to the best of our knowledge, connected versions of mTSP and VRP have not been studied.

8 Conclusion

Sight-moveable topological graphs we introduced only constrain the communication graph. One can be interested to constrain the movement graph to be planar or a 2D grid given the common usage of grid modelling of the environment. Given the intractability of MAPP on planar graphs [Yu, 2016] and on general 2D grid graphs [Banfi et al., 2017], it is likely that this problem is intractable as well. Furthermore, in [Tateo et al., 2018], the decision is proved to stay PSPACE-complete on planar graphs and grids as well. However, one can study this problem on solid grid graphs, given that the Hamiltonian cycle is tractable on such graphs [Umans and Lenhart, 1997].

Note that our NP lower bounds hold without the anonymity of the agents. Indeed, the bCoverage case is straightforward and for bReachability case, each agent can be associated to a clause or variable, so the reduction would still hold.

We do not know if Coverage remains PSPACE-hard when the →-relation is symmetric (see Figure 6). We think this open issue is important since symmetric →-relations (if UAVs can go from v to v′ , they can also come back from v′ to v) are relevant for practical applications. We plan to study the parametrized complexity [Downey and Fellows, 1999] of our problems - parameters could be for instance the treewidth of the topological graph or the number of UAVs.

Acknowledgements

This work was partially supported by UAV Retina Funded by EIT Digital. Special thanks to Franc¸ois Bodin for initiating the idea of this work. We thank Eva Soulier for the provided work during her internship.