1  Intractability of Optimal Multi-Robot Path Planning on Planar Graphs  Jingjin Yu 1  Abstract  We study the computational complexity of optimally solving multi-robot path planning problems on planar graphs. For four common time- and distance-based objectives, we show that the associated path optimization problems for multiple robots are all NP-complete, even when the underlying graph is planar. Establishing the computational intractability of optimal multi-robot path planning problems on planar graphs has important practical implications. In particular, our result suggests the preferred approach toward solving such problems, when the number of robots is large, is to augment the planar environment to reduce the sharing of paths among robots traveling in opposite directions on those paths. Indeed, such efficiency boosting structures, such as highways and elevated intersections, are ubiquitous in robotics and transportation applications.  Index Terms  NP-hardness, multi-robot path planning, planar graphs, transportation networks, boolean satisfiability problems.  I. I NTRODUCTION  I N this paper, we establish the computational complexity of optimally solving multi-robot path planning problems on planar graphs. In such a problem, a set of robots is initially located on the vertices of a connected planar graph. The task is to move the robots to a different set of vertices (each robot must reach a specific goal) of equal cardinality, in an optimal manner and collision free. Here, we look at four common optimality objectives with two focused on time optimality and two focused on distance optimality. For each of these objectives, we prove that the associated multi-robot optimal path planning problem is NP-hard. Since the decision versions of these problems are in NP, they are NP-complete.  Motivation and related work.   Our study is primarily motivated by the emerging trend in deploying multi- robot systems to automatically carry out complex tasks B ̈ ohringer (2004); Grocholsky et al. (2006); Wurman et al. (2008); Knepper et al. (2013). In these and many other applications, it is often highly desirable to plan for and control the robots so that they could optimally reach their respective target locations according to some metric, such as time- or distance-based measures. For example, for the Kiva Systems’ robots operating in a warehouse Wurman et al. (2008), the end goal is to put together orders for shipment as quickly as possible. This translates to a time-optimal travel requirement for the robots. A natural question then arises: can we solve these optimization problems for large problem instances efficiently, for example in low polynomial time? Knowing the answer to this question has important practical relevance. If the answer is positive, then the accompanying algorithmic solution will boost operating efficiency. On the other hand, if the answer is negative, one should perhaps look beyond algorithmic solutions in solving such problems, especially when the problem instance becomes larger and larger. For example, engineering the environment ( i.e. , the underlying graph structure in our problem) has long been applied in transportation system design, which frequently employs highways and elevated intersections to improve traffic throughput. Similar effort for simplifying problem solving is also observed in robotics applications Roozbehani and D’Andrea (2011), in which “highways” are designed to speed up the operation of Kiva Systems’ mobile robots. As our study establishes a firm “no” answer to this complexity question, our results offer theoretical justification for adopting environment engineering as a preferred approach for attacking optimal multi-robot path planning and closely related transportation problems, through the computation angle.  1 J. Yu is with the Department of Computer Science, Rutgers University at New Brunswick, Piscataway, New Jersey, USA 08854. E-mail:  jingjin.yu@rutgers.edu . This work is supported by a startup fund from Rutgers Unviersity.  arXiv:1504.02072v3 [cs.RO] 6 Dec 2015
2  The study of multi-robot path planning in a graph-theoretic setting originates from the mathematical study of the 15-puzzle Story (1879); Wilson (1974), popularized by Sam Loyd Loyd (1959). A generalized version of the problem, called the   pebble motion   problem, is proposed in Kornhauser et al. (1984), for which a cubic time algorithm is provided to find a feasible solution. Although only a single robot is allowed to move in a time step in the formulation given in Kornhauser et al. (1984), it is conceivable that multiple robots could be allowed to move simultaneously as long as no collision is incurred between any two robots. We denote this version of the problem, allowing concurrent collision-free robot movements, as MPP, which stands for Multi-robot Path Planning on graphs. Given the immediate applicability of MPP to domains such as computer games and robotics, many algorithms have been proposed to solve it according to some optimality criteria Ryan (2008); Standley and Korf (2011); Wagner and Choset (2011); Surynek (2012), of which most are time- or distance-based. Whereas great progress has been made, no algorithm is known to optimally solve these problems in polynomial time. This suggests that the problem may be computationally intractable. Indeed, the intractability of optimally solving MPP and related problems has been established Goldreich (1984); Ratner and Warmuth (1990); Surynek (2010); Yu and LaValle (2013a). However, to the best of our knowledge, no existing work addresses a planar setting while allowing general concurrent movements from multiple robots, which directly mirrors environments such as warehouses for Kiva’s robots or road networks for automobiles. We note that, the formulation in Ratner and Warmuth (1990) works with grids which are planar. However, in Ratner and Warmuth (1990), only a single robot is allowed to move to the single empty (swap) vertex at each time step ( i.e. , it works with a restricted MPP formulation); no concurrent robot movement is permitted. In contrast, we allow synchronous robot motion on graphs containing an arbitrary number of empty vertices, including the case with no swap vertex. The computational complexity of multi-robot path planning in two-dimensional continuous domains has also been extensively studied. The feasibility problem of translating rectangular blocks in a rectangular workspace has long been established as PSPACE-hard Hopcroft et al. (1984). The problem becomes strongly NP-hard when the blocks become discs with varying radii residing in a simple polygon Spirakis and Yap (1984). Recently, it is shown that the problem is PSPACE-hard even for unlabeled squares Solovey and Halperin (2015), the proof of which uses the non-deterministic constraint logic model Hearn and Demaine (2005). We mention that, the associated hardness proofs on feasibility from these work do not readily extend to optimal MPP for two reasons:   (i)   these proofs rely on geometric arguments, and   (ii)   the feasibility of graph-based MPP is in P Yu and Rus (2014).  Contributions.   Denoting the planar version of the MPP problem as PMPP, the main contribution of our work is showing rigorously that computing many time- and distance-optimal solutions for PMPP is NP-hard. For time- optimality, we further prove that such intractability persists even when there are only two groups of robots such that the robots are indistinguishable within each group. Moreover, due to the obvious NP membership of these problems, the decision versions of these problems are NP-complete. From a practical standpoint, because PMPP relates to real world path planning and transportation problems in which robots or vehicles move on some form of road networks embedded in a two-dimensional plane, our NP- hardness result convincingly demonstrates that such problems are computationally demanding to optimally solve. This suggests, for optimally coordinating the movements of a large number of robots (or vehicles) in a planar setting, environment augmentation should be explored in addition to algorithmic improvements. Indeed, in practice, we observe that engineered solutions such as highways and elevated intersections are widely adopted, which can be readily justified with our findings.  Organization.   The rest of the paper is organized as follows. We define the PMPP and optimal versions of the problem In Section II. In Section III, we prove the NP-hardness of the time-optimal formulations and also show the intractability remains when there are only two groups of robots. In Section IV, we show the intractability of distance-optimal formulations. We conclude the paper in Section V. II. M ULTI - ROBOT   P ATH   P LANNING ON   P LANAR   G RAPHS : B ASIC AND   O PTIMAL   F ORMULATIONS  A. The multi-robot path planning problem  Let   G   = ( V, E )   be a   connected ,   undirected ,   simple ,   planar graph , with   V   =   { v i }   being the vertex set and  E   =   { ( v i , v j   ) }   the edge set with unit edge length. A graph is   planar   if its edges can be embedded in the two- dimensional plane without any two edges crossing each other. Let   R   =   { r 1 , . . . , r n }   be a set of   n   robots. A robot
3  may stay still or move at unit speed along edges of   G . A   configuration   of the robots is an injective map from   R  to   V   . The start and goal configurations of the robots are denoted as   x I   and   x G , respectively. A   scheduled path   is a map   p i   :   Z +   →   V   , in which   Z +   :=   N   ∪ { 0 } . A path set   P   =   { p 1 , . . . , p n }   is   feasible  if it takes the robots to their respective goals. More formally,   P   =   { p i }   must satisfy the following properties: 1)   p i (0) =   x I   ( r i ) . 2) For each   i , there exists a smallest   t i   ∈   Z +   such that   p i ( t i ) =   x G ( r i ) . 3) For any   t   ≥   t i ,  p i ( t )   ≡   x G ( r i ) . 4) For any   0   ≤   t < t i ,   ( p i ( t ) , p i ( t   + 1))   ∈   E   or   p i ( t ) =   p i ( t   + 1)   (if   p i ( t ) =   p i ( t   + 1) , robot   r i  stays at vertex   p i ( t )   between the time steps   t   and   t   + 1 ). We say that two paths   p i , p j   are in   collision   if there exists  t   ∈   Z +   such that   p i ( t ) =   p j   ( t )   (meet-collision) or   ( p i ( t ) , p i ( t   + 1)) = ( p j   ( t   + 1) , p j   ( t ))   (head-on-collision) 1 .  Problem 1 (Planar Multi-Robot Path Planning (PMPP))   Given   ( G, R, x I   , x G ) , find a feasible path set   P   =  { p 1 , . . . , p n }   such that no two paths   p i , p j   ∈   P   are in collision.  Remark.   We point out that the feasibility of PMPP can be decided in linear time and a feasible PMPP instance can be solved in polynomial time Yu and Rus (2014). Alternatively, if there is a single robot, optimal path planning is also in P Dijkstra (1959).   4  B. Optimal Formulations  Let   P   =   { p 1 , . . . , p n }   be an arbitrary feasible solution to a fixed PMPP instance. For a path   p i   ∈   P   ,   len ( p i )  denotes the length of the path   p i , which is increased by one each time when the robot   r i   passes an edge. A robot, following   p i , may visit the same edge multiple times. Recall that   t i   denotes the arrival time of robot   r i . In optimizing over the solutions to PMPP, we examine four common objectives with two focusing on time optimality and two focusing on distance optimality. Each objective is stated together with the corresponding decision problem required for stating NP-completeness results.  Objective 1 (Min Total Time)   Compute a path set   P   that minimizes  n ∑  i =1  t i .  MTTP MPP   (Min Total Time PMPP) Instance: An instance of PMPP, and   k   ∈   Z . Question: Is there a solution path set   P   with a total arrival time no more than   k ?  Objective 2 (Min Makespan)   Compute a path set   P   that minimizes  max  1 ≤ i ≤ n   t i .  MMP MPP   (Min Makespan PMPP) Instance: An instance of PMPP, and   k   ∈   Z . Question: Is there a solution path set   P   with a makespan no more than   k ?  Objective 3 (Min Total Distance)   Compute a path set   P   that minimizes  n ∑  i =1  len ( p i ) .  MTDP MPP   (Min Total Distance PMPP) Instance: An instance of PMPP, and   k   ∈   Z . Question: Is there a solution path set   P   with a total path distance no more than   k ?  1 We assume that the graph   G   only allows “meet” or “head-on” collisions. For example, a (arbitrary dimensional) grid with unit edge distance is such a graph for robots with radii of no more than   √ 2 / 4 .
4  Objective 4 (Min Max Distance)   Compute a path set   P   that minimizes  max  1 ≤ i ≤ n   len ( p i ) .  MMDP MPP   (Min Max Distance PMPP) Instance: An instance of PMPP, and   k   ∈   Z . Question: Is there a solution path set   P   in which every path has a distance no more than   k ? We illustrate what these objectives achieve using the example shown in Fig. 1. The individual costs incurred 2  1  2  1  3  3  4  4  Fig. 1.   An instance of a planar multi-robot path planning problem. The labeled, shaded discs are the start locations of the robots and the labeled, unshaded discs are the goal locations.  by the robots are listed in Table I. In a minimum total time solution, robots   1 ,   2 , and   3   must sequentially travel through the bold (blue) vertical edge on the left side of Fig. 1, yielding arrival times of   3 ,   4 , and   5 , respectively. Robot   4   should instead travel through the bold (green) vertical edge on the right, yielding an arrival time of   5 . This solution is also a min-max time solution for this particular example. For distance-optimal solutions, all robots should go through the bold vertical edge on the left, yielding a per-robot distance of   3 . In general, however, an arbitrary pair of these four objectives creates a Pareto front (see   e.g. , Yu and LaValle (2013a)). That is, it is not always possible to simultaneously optimize any two of these four objectives.  Remark.   It is important to note the relationship between PMPP and MPP, the non-planar formulation with the only distinction being that   G   is not required to be planar. The computational intractability of MPP has been established in Yu and LaValle (2013a) for several objectives. We note that if an optimal PMPP formulation is NP-hard, then the corresponding MPP formulation is also NP-hard. This is true because MPP contains PMPP. The NP-hardness of an optimal MPP problem, however, does not directly imply the NP-hardness of the corresponding PMPP problem because a non-planar graph cannot be readily turned into a planar graph.   4  TABLE I M INIMUM REQUIRED TIME AND DISTANCE FOR THE ROBOTS . Robot   1   2   3   4 Total time / max time   3   4   5   5 Total distance / max distance   3   3   3   3  III. I NTRACTABILITY OF   T IME -O PTIMAL   F ORMULATIONS  To show intractability, our general strategy is a reduction from a special 3-SAT problem Garey and Johnson (1979) called the   monotone planar   3-SAT de Berg and Khosravi (2010), which we denote as MP3SAT. Starting from an arbitrary MP3SAT instance, we construct a corresponding optimal PMPP instance (for each of the four objectives) in polynomial time. Our PMPP instances are constructed in two phases. In the first phase, we provide a high-level, skeleton graph structure containing   directed paths . In the second phase, we fill in the details on how to  simulate   these directed paths in a PMPP instance (as directed paths are not allowed in PMPP). We then show the MP3SAT instance is satisfiable if and only if the PMPP instance has a certain optimal solution. Because MP3SAT is NP-hard de Berg and Khosravi (2010), this implies that the various optimal PMPP problems are also NP-hard.
5  Our main goal in this section is proving the intractability of computing time-optimal solutions for PMPP,   i.e ,  Theorem 1   MTTP MPP   and   MMP MPP   are both NP-hard.  As the complete proof of Theorem 1 is involved, we begin with a sketch including the necessary preliminaries. A more rigorous proof then follows.  A. Reducing   MP3SAT   to   MMP MPP : A Sketch  We first introduce MP3SAT, an instance of which has the following structure. There are   n   variables,   x 1 , . . . , x n , and   m   disjunctive clauses,   c 1 , . . . , c m . Each clause   c j   contains up to three literals that can either be all non-negated or all negated. A clause with only non-negated (resp., negated) literals is called a   positive   (resp.,   negative ) clause. This is the   monotone   element of the MP3SAT problem. To describe the   planarity   element, we construct a graph based on a monotone 3-SAT   instance. Given the monotone instance   ( { x 1 , . . . , x 5 } ,   { c 1   =   x 1   ∨   x 4   ∨   x 5 , c 2   =  x 2   ∨   x 3 , c 3   =   ¬ x 1   ∨ ¬ x 2   ∨ ¬ x 3 , c 4   =   ¬ x 3   ∨ ¬ x 4   ∨ ¬ x 5 } )   as an example (see Fig. 2), we do the following: 1) Add a vertex for each variable   x i   and each clause   c j   , 2) Add an edge between two consecutive variable vertices   x i   and   x ( i +1)   mod   n   (the blue cycle of variables in Fig. 2), 3) For a variable   x i   and a clause   c j   , if   c j   has   x i   or   ¬ x i   as a literal, add an edge between vertex   x i   and vertex  c j   . 1 x   2 x   3 x   4 x   5 x  1 c  2 c  4 c 3 c  Fig. 2.   The   monotone planar   3-SAT instance   ( { x 1 , . . . , x 5 } ,   { c 1   =   x 1   ∨ x 4   ∨ x 5 , c 2   =   x 2   ∨ x 3 , c 3   =   ¬ x 1   ∨¬ x 2 ¬ x 3 , c 4   =   ¬ x 3   ∨¬ x 4 ¬ x 5 } ))  represented as a planar graph.  The planar element of MP3SAT requires that the graph constructed following these rules is planar. In particular, this implies that the positive clauses and the negative clauses are separated by the circle formed by the edges between variable vertices. MP3SAT is NP-hard de Berg and Khosravi (2010). From the planar structure, we assign each clause a   nesting level   that is defined recursively. In the planar graph ( e.g. , Fig. 2), if a clause vertex shares a face (a connected 2D region enclosed by edges) with the edge   ( x n , x 1 ) , then it is assigned a nesting level of   0 . Otherwise, a clause vertex is assigned a nesting level of   `   if there is a minimum of   `   −   1   faces between the clause vertex and the edge   ( x n , x 1 ) , without crossing any other   ( x i , x i +1 )   edge. In our example,   c 1 ,   c 3 , and   c 4   all have a nesting level of   0   and   c 2   is at level   1 . We say that   c j 1   is   directly nested   in   c j 2  when the nesting level of   c j 1   and   c j 2   differ by one, and   c j 1   is separated from   ( x n , x 1 )   by edges containing   c j 2   . In our example,   c 2   is directly nested in   c 1 . After introducing MP3SAT, we construct a MMP MPP   instance from a MP3SAT instance, using the MP3SAT instance from Fig. 2 as an example. Here, we sketch the construction and the associated reduction proof. The skeleton of the converted MMP MPP   instance is given in Fig. 3. The key idea behind the reduction is to create  clause robots   and force unidirectional travel of these robots through   variable channels   (the orange paths between  x i   and   ¬ x i ). For a clause   c j   , we denote the corresponding robot as   r c j   . In comparison to Fig. 2, each variable vertex is split into an edge and we delete the edges between consecutive variables ( i.e. , the edges   ( x i , x ( i +1)   mod   n )  are removed). The edges between variable vertices and clause vertices are split into “directional paths” that enforce
6 1 x   2 x   3 x   4 x   5 x  1 c  2 c  3 c   4 c  3 x :   4 x :   5 x : 2 x : 1 x :  4 c  g  3 c  g  2 c  g  1 c  g  Fig. 3.   The skeleton of the MMP MPP   instance reduced from the MP3SAT instance   ( { x 1 , . . . , x 5 } ,   { c 1   =   x 1   ∨ x 4   ∨ x 5 , c 2   =   x 2   ∨ x 3 , c 3   =  ¬ x 1   ∨ ¬ x 2 ¬ x 3 , c 4   =   ¬ x 3   ∨ ¬ x 4 ¬ x 5 } )) , as visualized in Fig. 2.  the motion direction of robots along these paths. We will explain in more detail how such directional paths can be realized. If some clauses are nested in other clauses in the graph structure (for example,   c 2   is nested inside   c 1  due to the planarity requirement), additional paths are created to connect these clauses vertices, pointing from the inner clause to the outer clause ( e.g. , the pink   ( c 2 , c 1 )   directional path). Finally, we create additional paths leading to the goals for the clause robots. These goal vertices are marked as   c g j   in Fig. 3. We connect these paths to all clause vertices having a nesting level   0   ( c 1 , c 3 , and   c 4 ) on the opposite side (see Fig. 3). Roughly, the reduction works as follows. If the MP3SAT instance is satisfiable, then each clause robot can find a variable channel in the middle that will not have other clause robots using it from the opposite direction. This is true due to the monotone arrangement of the clauses. For example, the clause robot   r c 2   , starting from vertex  c 2 , may choose to go to   x 2 , corresponding to setting   x 2   =   true . If   x 2   =   true , then   c 3   cannot be true by setting  ¬ x 2   =   true . Overall, for our example, we may set   x 1   =   x 2   =   x 4   =   x 5   =   true   and   x 3   =   f alse . We can then let   r c 1   and   r c 2   go through variable channels for   x 1   and   x 2 , respectively, in the downward direction. Similarly, we can let   r c 3   and   r c 4   go through variable channel for   x 3 , in the upward direction. Once these clause robots reach the other side of the variable channels, they can use the directional paths to reach their respective goals. Note that these paths are of appropriate lengths to make sure that the robots will not be delayed unnecessarily. For example, we will make robot   r c 4   spend a little more time to reach the variable channel for   x 3   than it does for robot   r c 3   . On the other hand, if a satisfiable assignment is not available, either a variable channel must be shared between both positive and negative clause robots or some clause robots must take a detour and use a variable channel of which the corresponding variable does not belong to the literals of that clause ( e.g. , if   r c 2   goes to   c 1   first and then   x 1 ;   x 1  does not appear in   c 2 ). Both cases result in delays in the arrival of some robots.  B. Reducing Planar   3-SAT   to   MMP MPP : The Details  We now provide the details leading to a complete proof of Theorem 1, starting from completing the MMP MPP  instance outlined in Fig. 3. The instances is constructed with a particular   k   = 12 m   so that the MP3SAT instance is satisfiable if and only if the corresponding MMP MPP   instance has an optimal solution with   12 m   time steps. First, we specify the lengths of different types of paths in Fig. 3. 1)   Variable channels . A variable channel is a path of length   6 m   between   x i   and   ¬ x i   (orange ones in Fig. 3).
7  2)   Directional path from   c j   to a variable channel . We call such a path a   forward path   from   c j   . For a clause vertex   c j   , the forward path from   c j   to   x i   or   ¬ x i   (if one exists) has length   2 j . For example, the blue path from   c 1   to   x 1 , x 4 , and   x 5   in Fig. 3 all have length two, whereas the paths from   c 2   to   x 2   and   x 3   are both of length four. 3)   Directional path between clause vertices . If a clause   c j 1   is directly nested inside   c j 2   , we add a directional path from   c j 1   to   c j 2   and give it a length of two. These paths allow a clause robot to have a shortest path to its goal no matter which variable channel it goes through. For example, the pink path from   c 2   to   c 1   in Fig. 3 is such a path, which allows   r c 3   to go through   ¬ x 2 ,   x 2 ,   c 2 ,   c 1 , and   c g  4   to reach   c g  3   (in   12 m   steps, as we establish shortly). 4)   Directional path from a variable channel to   c j   . We call such a path a   backward   path to   c j   . For a clause   c j  with a nesting level   ` , a backward path from   x i   or   ¬ x i   to   c j   has a length of   2( m   −   ` ) . For example, the path going from   x 2   to   c 2   has a length of   2(4   −   1) = 6   and the path from   x 1   to   c 1   has a length of   2(4   −   0) = 8 . This ensures that paths like   x 1 c 1   and   x 2 c 2 c 1   have the same length. 5)   Goal paths for the clause robots . The paths on which the goals of the clause robots are located (green paths in Fig. 3) have lengths such that the shortest path from from   c j   to   c g j   has a length of   12 m , which can always be realized. Note that such constructions are not unique. However, the construction can be made unique,   e.g. , by minimizing the number of added vertices. For the example given in Fig. 3, the path lengths are added in Fig 4. It is straightforward to check that all the clause robots will require a minimum of   12 m   = 48   steps to reach their respective goal vertices. 3 x :   4 x :   5 x : 2 x : 1 x :  1 x   2 x   3 x   4 x   5 x  1 c  2 c  4 c  g  3 c  g  24   24 24 24 24  2 8   6  2  4 6 4 2   2 8   8  8 2  3 c   4 c 2 c  g  1 c  g  8   8 8   8   8   8 6 6   6 8   8   8  12   12 2  Fig. 4.   The skeleton of the MMP MPP   instance reduced from the MP3SAT instance   ( { x 1 , . . . , x 5 } ,   { c 1   =   x 1   ∨ x 4   ∨ x 5 , c 2   =   x 2   ∨ x 3 , c 3   =  ¬ x 1   ∨ ¬ x 2 ¬ x 3 , c 4   =   ¬ x 3   ∨ ¬ x 4 ¬ x 5 } )) , with path lengths added. Possible routes taken by the four clause robots following shortest paths are marked with red (downward) and black (upward) dotted lines.  The last main missing piece from the MMP MPP   instance is how to enforce the directional paths. There are three types of directional paths: forward paths from clause vertices, backward paths to clause vertices, and paths connecting two clause vertices. The method for enabling these directional paths are all similar; we do so by replacing each of these “directional” paths with a two-piece gadget, which is a simple, specialized sub-structure. We use examples to illustrate the gadget construction for each type of directional paths. For the forward paths from clause vertices to variable channels, we only want to allow a clause robot to pass through the path at   t   = 0 . For example, for the forward path from   c 3   to   ¬ x 1   in Fig. 4, we only want to allow robot  r c 3   to pass through at time step   t   = 0   to time step   t   = 6 . This can be enforced using the path gadget illustrated
8 3 c   1 x :  1  p   2  p  12 m   { 1  1 r 12 m   { 1 r   1 r g  12 m   { 1 r   g  12 m   { 1  Fig. 5.   A gadget to enable unidirectional paths. The paths in the yellow shaded area are added to the path from   c 3   to   ¬ x 1 .  in Fig. 5, which also adds   12 m   −   1   additional robots. As shown in the figure, we attach a path ( p 1 ) to the second vertex on the path from   c 3   to   ¬ x 1   (in this case   r g  12 m − 1 , which is also the goal vertex for robot   r 12 m − 1 ). We then attach another path ( p 2 ) at the same vertex. We put the   12 m   −   1   robots on   p 1   and require them to go to   p 2 . We make it so that each robot on   p 1   requires   12 m   steps to reach its goal on   p 2 . The robots are placed on   p 1   to allow desired clause robots to pass through. In the case of the path from   c 3   to   ¬ x 1 , no robot on   p 1   will move to   r g  12 m − 1  at   t   = 1 , thus allowing robot   r c 3   to go to   r g  12 m − 1   at   t   = 1 . After   t   = 1 , a continuous stream of robots on   p 1   will move through   r g  12 m − 1 , forbidding any additional clause robots to move through the path connecting   c 3   and   ¬ x 1 . We are left with two types of directional paths: backward paths to clause vertices and paths connecting two clause vertices. The gadget for these two types of directional paths are actually identical, since the utility of these paths is to allow a clause robot to move to its goal   after   passing through a variable channel. We use the directional path from   c 2   to   c 1   as an example. All we need to do is to forbid the path being used at all before   t   = 6 m , thus preventing undesirable behaviors such as allowing   r c 2   to move from   c 2   to   c 1 . We may do so simply by letting robots flowing through the path continuously for the first   6 m   steps (see Fig. 6). After that, the path becomes available for traversal in both directions. Nevertheless, such a path is effectively unidirectional because no clause robot can use it from the other direction ( i.e. , from   c 1   to   c 2 ) when time optimality is enforced: if a robot uses such a path in the wrong direction after   6 m   steps, it cannot reach its goal in   12 m   steps. 2 c   1 c  6 m   12 m   { 1  1 r 6 m r   6 m r   g  1 r   g  Fig. 6.   A gadget to enable unidirectional path from   c 2   to   c 1   that prevents traversing in the first   6 m   time steps.  Finally, every variable channel is a simple straight line path of length   6 m   without any additional robot on it. To tally the number of vertices of the resulting instance, the skeleton graph has   O ( mn )   vertices ( e.g. , Fig. 4 can be decomposed into   2 n   paths between   c g  3   and   c g  1 , with each such path having length   O ( m ) ). Then, there are no more than   O ( m )   forward and backward paths, and no more than   m   paths between clause vertices. Since each of these three types of paths has   O ( m )   vertices, the entire construction has   O ( mn   +   m 2 )   vertices and fewer robots, which can be done in polynomial time. Note that this analysis applies to all constructions in this paper.  Fig. 7.   A possible arrangement of forward paths for a clause.
9  Remark.   It is straightforward to verify that the gadgets used in our construction do not change the planarity of the graph. Some readers may have concerns on the apparent difference of the edge lengths in the instance construction process–some edges seem longer than others whereas we assume every edge takes the same amount of time and distance to traverse. We note that edge lengths can always be made equal by scaling up the path lengths and bending certain paths. As an illustration, Fig. 7 shows how forward paths for clauses (of length   16   each) may be arranged while leaving space for backward paths and gadget paths. In general, linear scaling of path lengths creates quadratic amount of space for the accommodation of path length disparities.   4  P ROOF OF   T HEOREM   1. From the partially constructed MMP MPP   instance, we obtain a complete instance by setting   k   = 12 m . If the MP3SAT instance has a satisfiable assignment, then we can obtain collision free paths for all robots to simultaneously reach their goals in   12 m   time steps. To do so, we simply let a positive clause robot  r c j   go from   c j   to some   x i   that is part of   c j   and is set to true in the assignment. We do the same for the negative clause robots, sending   r c j ′   to some   ¬ x i ′   that makes   c j ′   true. Because a variable   x i   will not be set to true and false simultaneously in a satisfiable assignment, a positive clause robot and a negative clause robot will never reach the two ends of the same variable channel. All clause robots can then follow the directional paths to reach their goals in   12 m   steps. As mentioned earlier, in our example (Fig. 4), we may set all variables but   x 3   to true. We then let  r c 1   go to   x 1 ,   r c 2   go to   x 2 ,   r c 3   and   r c 4   go to   ¬ x 3   (the paths are illustrated in Fig. 4). All robots will reach their respective goals at   t   = 48 . On the other hand, if the constructed PMPP instance has a solution requiring only   12 m   steps for all robots, then every single robot must start moving at   t   = 0 , follow a shortest path, and never stop until the goal is reached. In particular, this means that a positive clause robot and a negative clause robot can never share the same variable channel. This is true because a positive (resp., negative) clause robot can reach some   x i   (resp.,   ¬ x i ) at   0   < t   ≤   2 m . Since a variable channel has a length of   6 m , sharing it by a positive and a negative clause robot means that some robot must take more than   12 m   steps to reach its goal since the channel can only be used in one direction at a time. After it is used in one direction, more than   6 m   time steps has already passed. We then simply set a variable  x i   to be true (resp., false) if the corresponding channel is used by a positive (resp., negative) clause robot. Such an assignment is a satisfiable one for the original MP3SAT problem. This proves that MMP MPP   is NP-hard. To see that MTTP MPP   is NP-hard, we simply reuse the same construction but set   k   to be   12 m   multiplied by the total number of robots. The rest of the proof remains the same.     Remark.   As we know, the problem of planning time optimal trajectories when all robots are interchangeable is efficiently solvable Yu and LaValle (2013b). By interchangeable, we mean that it is only required that all the goals are occupied by robots; it does not matter which robot occupies which goal. That is, there is a single   group   or   team  of robots. In the case of PMPP, there are   n   groups of robots (each group has a single robot). A natural question then arises: for how many groups of robots will optimal PMPP problems become hard? It turns out two groups of robots are enough to make such problems computationally intractable.   4  Theorem 2   MTTP MPP   and   MMP MPP   remain NP-hard, even when there are only two groups of robots.  P ROOF . In the proof for Theorem 1, we group all positive clause robots and the associated robots on the path gadgets as one group.The rest of the robots form the other group. That is, referring to Fig. 4, all robots above the set of variable channels belong to one group and all robots below belong to another. In our example, this means that   r c 1   and   r c 2   may go to either   c g  1   or   c g  2 . Same is true for robots   r c 3   and   r c 4   . It is straightforward to check that the robots for enforcing the directional paths (Fig. 5 and Fig. 6) cannot be used for other purposes as every robot must continuously move   12 m   steps. Otherwise, time optimality will be affected. The proof of Theorem 1 can then be applied to show that such formulations with two groups of robots remain NP-hard.     IV. I NTRACTABILITY OF   D ISTANCE -O PTIMAL   F ORMULATIONS  The intractability of distance-optimal formulations of PMPP is more challenging to prove, owing to to the fact that it is not necessary to time-synchronize the paths of the robots, thus allowing more combinations of robot
10  movements. Nevertheless, we again reduce from MP3SAT and build distance optimal PMPP instances, starting with MTDP MPP . The skeleton of the constructed MTDP MPP   instance is shown in Fig. 8, which has a structure similar to that of the converted MMP MPP   instance from Fig. 4. Like in Fig. 4, the lengths of the paths are given. The main difference at the skeleton level is that for distance optimality, we want to make sure that the shortest paths for all clause robots have not only the same length, but also in a sense “parallel” to each other. This is put in place to force a stronger form of synchronization among the robots. Again, we will show that the MP3SAT instance is satisfiable if and only if the corresponding MTDP MPP   has certain optimal solution cost. 1 x   2 x   3 x   4 x   5 x  1 c  2 c  3 c   4 c  3 x :   4 x :   5 x : 2 x : 1 x :  4 c  g  3 c  g  2 c  g  1 c  g  16   16 16 16 16  8 16   12  4  8 12   8 8   8 16   16 16   16   16   16   16 16 8   8   8 8   8   8  1 1 1 1 2 2  v  Fig. 8.   The skeleton of the MTDP MPP   instance reduced from the same MP3SAT instance   ( { x 1 , . . . , x 5 } ,   { c 1   =   x 1   ∨   x 4   ∨   x 5 , c 2   =  x 2   ∨   x 3 , c 3   =   ¬ x 1   ∨ ¬ x 2 ¬ x 3 , c 4   =   ¬ x 3   ∨ ¬ x 4 ¬ x 5 } )) , with path lengths added.  The path lengths are set as follows: 1)   Forward path from   c j   . All such paths have lengths of   2 m . This is 8 in our example. 2)   Directional path between clause vertices . If a clause   c j 1   is directly nested inside a clause vertex   c j 2   , we add a path from   c j 1   to   c j 2   and make it have length 4. 3)   Backward path to   c j   . Let the nesting level of   c j   be   ` j   , then such paths have lengths   4( m   −   ` j   ) . For example,  x 2 c 2   has length   16   −   4 = 12 . This ensures that directional paths from all variable channels to a clause vertex of nesting level   0   have the same length ( e.g. ,   x 1 c 1   and   x 2 c 2 c 1 ), which is   4 m . 4)   Variable channels . Each variable channel (orange paths in Fig. 3) has a length of   4 m . 5)   Goal paths for the clause robots . The length from any goal vertex for a clause robot to the closest clause vertex with a nesting level of   0   is   2 . For example,   c 1 c g  3   or   c 3 c g  1 . There are no additional structures on these paths. Based on these path length settings, each clause robot requires a distance of at least   10 m +2   to reach its goal. We now describe the details needed to specify the full MTDP MPP   instance. Since time synchronization is no longer helpful, gadgets such as those from Fig. 5 and Fig. 6 are no longer useful. Instead, we need a different method of enforcing directional paths that penalizes robot traveling in an undesirable direction. For a forward path from a clause vertex, for example from   c 3   to   ¬ x 1 , we construct the gadget illustrated in Fig. 9 to enforce unidirectional traversal. In the figure, the initial and final configurations of the gadget are shown in the left and the right picture (the shaded regions), respectively. Such a construction allows only clockwise rotation of the gadget cycle; rotating counterclockwise will incur a large distance penalty. Note that the added robots will incur more distance penalty if they travel outside the gadget structure. For backward paths to   c j   , as well as the directional paths connecting   c j 1   to   c j 2   , we let such a path be a simple straight line path. For example, the path   c 2 c 1   is a simple linear path of length   4   with no additional robots in the
11 3 c   1 x :  1 r  8 m r  8 m r  1 r  r   3 c   r   3 c  3 c   1 x :  2 m   { 2 r  2 m   { 1 r  Fig. 9.   A gadget to enable (total) distance optimal, unidirectional traversal from   c 3   to   ¬ x 1 . [left] The initial gadget configuration. [right] The target (goal) gadget configuration.  middle. Note that a clause robot will never use such a path before crossing a variable channel since going through such a path adds the needed distance. For example, going from   c 1   to   x 1   along the forward path requires a distance of   8   but going along the backward path requires a distance of   16 . Finally, a variable channel has the structure illustrated in Fig. 10. The gadget contains a cycle of   12 m   vertices, with   10 m   additional robots on the cycle. For each of the   10 m   added robots, we require it to reach the diagonal location on the cycle. In particular, we marked the goals for robots   r 1 , r 2 m +1 , r 2 m +2 , and   r 10 m   in Fig. 10 (the red nodes). Given such a gadget, for all   10 m   robots to travel the minimum possible distance (which is   6 m   for each robot), the robots must either all rotate clockwise or all counterclockwise along the cycle. Effectively, such a gadget allows unidirectional traversal along the upper path between   x 1   and   ¬ x 1 , creating a unidirectional variable channel for clause robots. 1 x :  1 r  1 x  2 m   + 1 r 2 m   + 2 r   10 m r  2 m   + 2 r   g  2 m   + 1 r   g  1 r g  10 m r   g  Fig. 10.   The variable channel gadget for   x 1   in the total distance optimal case. To ensure the robots on the gadget travel the shortest possible distance, all these robots may only move either in the same (clockwise or counterclockwise) direction.  We now show that computing distance optimal solution for PMPP problems is also NP-hard.  Theorem 3   MTDP MPP   is NP-hard.  P ROOF . Given the PMPP instance that has been constructed, we obtain a complete MTDP MPP   instance by setting  k   to be the sum of the minimum possible distance for all the robots. Assuming the MP3SAT   instance has a satisfiable assignment, we let a clause robot move to a variable channel whose end literal makes that clause true. In our example, we may again let all variables but   x 3   be true. We then let   r c 1   go to   x 1 ,   r c 2   go to   x 2 , and both   r c 3  and   r c 4   go to   ¬ x 3 . There robots can then pass the variable channel to reach their respective goals. It is clear that all robots may do so following a shortest possible path. In particular, a variable channel can transfer up to   m   clause robots in one direction optimally. Also, we note that the clause robots only need to synchronize their movements at variable channels. Otherwise, the order of their movements do not affect distance optimality. For example, the movement of   r c 1   and   r c 2   can be mostly decoupled; they only share one edge in their respective shortest paths (the edge   ( c 3 , v )   in Fig. 8). On the other hand, if the MTDP MPP   instance has a distance optimal solution of   k   total steps, each robot must follow a shortest possible path. For a clause robot   r c j   to follow a shortest path, it must first travel along a forward path gadget that go from   c j   to a variable channel, in   2 m   steps. Because a variable channel can only be used in one direction to optimally transfer clause robots, the distance optimal solution partitions the variable channels into two sets based on the travel direction of the clause robots. Similar to the time-optimal case, based on this partition of variable channels, a satisfiable assignment for the corresponding MP3SAT instance can then be easily extracted.   
12  Theorem 4   MMDP MPP   is NP-hard.  P ROOF . In our construction of the MTDP MPP   instance, there are three different shortest distances for the robots that are involved. A clause robot needs to travel   10 m   + 2   steps, a robot added to a directional path gadget needs to travel   2 m   −   2   steps, and a robot added to the variable gadget needs to travel   6 m   steps. However, we can easily change the gadgets such that all the involved robots need to travel   10 m   + 2   steps. For the forward path gadget pictured in Fig. 9, we may do so by making the lower path of the cycle much larger ( e.g. , to have about   30 m  vertices and robots, see Fig. 11) to again ensure unidirectional traversal through the gadget. For the variable channel 3 c   1 x :  1 r  30 m r  r   3 c   r   3 c  3 c   1 x :  2 m   { 2 r  2 m   { 1 r   8 m +3  1 r  Fig. 11.   A gadget to enable distance optimal, unidirectional traversal from   c 3   to   ¬ x 1   while ensuring the added robots move at least  10 m   + 2   steps. [left] The initial gadget configuration. [right] The target (goal) gadget configuration.  gadget, we may simply enlarge the cycle to have   20 m   + 4   vertices, add more robots, and again make all the added robots go to diagonal locations. After the gadget modifications are complete, we obtain a complete MMDP MPP  instance by setting   k   = 10 m   + 2 . The rest of the proof is then identical to that for MTDP MPP .     V. C ONCLUSION AND   D ISCUSSION  In this paper, we have established the NP-hardness of four common versions of optimal multi-robot path planning problems on planar graphs. Because these problems are clearly in NP, we may further conclude that they are NP- complete,   i.e. ,  Theorem 5   MTTP MPP ,   MMP MPP ,   MTDP MPP , and   MMDP MPP   are all NP-complete problems.  Theorem 5 implies that optimal planning and control of multiple robots in a discrete planar environment, such as coordinating many automobiles on a planar road network to minimize delay, is a computationally intractable task. In particular, the difficulty appears to arise when two or more groups of robots want to move in opposite directions through the same set of channels, thus creating resource contention among the robots. From a practical standpoint, our observation suggests that the best approach towards solving such problems, as the number of robots becomes large, is perhaps to engineer the environment carefully to minimize path sharing among the robots. Alternatively, an equally interesting open question is whether optimal MPP and PMPP problems are APX-hard or they admit polynomial time approximation schemes (PTAS). R EFERENCES  K. F. B ̈ ohringer, “Towards optimal strategies for moving droplets in digital microfluidic systems,” in   Proceedings IEEE International Conference on Robotics & Automation , 2004. B. Grocholsky, J. Keller, V. Kumar, and G. Pappas, “Cooperative air and ground surveillance,”   IEEE Robotics and Automation Magazine , vol. 13, no. 3, pp. 16–25, Sep 2006. P. R. Wurman, R. D’Andrea, and M. Mountz, “Coordinating hundreds of cooperative, autonomous vehicles in warehouses,”   AI Magazine , vol. 29, no. 1, pp. 9–19, 2008. R. Knepper, T. Layton, J. Romanishin, and D. Rus, “Ikeabot: An autonomous multi-robot coordinated furniture assembly system,” in  Proceedings IEEE International Conference on Robotics & Automation , 2013, pp. 855–862. H. Roozbehani and R. D’Andrea, “Adaptive highways on a grid,” in   Robotics Research .   Springer, 2011, pp. 661–680. E. W. Story, “Note on the ‘15’ puzzle,”   American Journal of Mathematics , vol. 2, pp. 399–404, 1879. R. M. Wilson, “Graph puzzles, homotopy, and the alternating group,”   Journal of Combinatorial Theory (B) , vol. 16, pp. 86–96, 1974. S. Loyd,   Mathematical Puzzles of Sam Loyd .   New York: Dover, 1959. D. Kornhauser, G. Miller, and P. Spirakis, “Coordinating pebble motion on graphs, the diameter of permutation groups, and applications,” in   Proceedings IEEE Symposium on Foundations of Computer Science , 1984, pp. 241–250.
13  M. R. K. Ryan, “Exploiting subgraph structure in multi-robot path planning,”   Journal of Artificial Intelligence Research , vol. 31, pp. 497–542, 2008. T. Standley and R. Korf, “Complete algorithms for cooperative pathfinding problems,” in   Proceedings International Joint Conference on Artificial Intelligence , 2011, pp. 668–673. G. Wagner and H. Choset, “M*: A complete multirobot path planning algorithm with performance bounds,” in   Proceedings IEEE/RSJ International Conference on Intelligent Robots & Systems , 2011, pp. 3260–3267. P. Surynek, “Towards optimal cooperative path planning in hard setups through satisfiability solving,” in   Proceedings 12th Pacific Rim International Conference on Artificial Intelligence , 2012. O. Goldreich, “Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard,” 1984, laboratory for Computer Science, Massachusetts Institute of Technology, Unpublished manuscript. D. Ratner and M. Warmuth, “The   ( n 2   −   1) -puzzle and related relocation problems,”   Journal of Symbolic Computation , vol. 10, pp. 111–137, 1990. P. Surynek, “An optimization variant of multi-robot path planning is intractable,” in   Proceedings AAAI National Conference on Artificial Intelligence , 2010, pp. 1261–1263. J. Yu and S. M. LaValle, “Structure and intractability of optimal multi-robot path planning on graphs,” in   Proceedings AAAI National Conference on Artificial Intelligence , 2013, pp. 1444–1449. J. E. Hopcroft, J. T. Schwartz, and M. Sharir, “On the complexity of motion planning for multiple independent objects; PSPACE-hardness of the “warehouseman’s problem”,”   The International Journal of Robotics Research , vol. 3, no. 4, pp. 76–88, 1984. P. Spirakis and C. K. Yap, “Strong NP-hardness of moving many discs,”   Information Processing Letters , vol. 19, no. 1, pp. 55–59, 1984. K. Solovey and D. Halperin, “On the hardness of unlabeled multi-robot motion planning,” in   Robotics: Science and Systems (RSS) , 2015. R. A. Hearn and E. D. Demaine, “PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation,”   Theoretical Computer Science , vol. 343, no. 1, pp. 72–96, 2005. J. Yu and D. Rus, “Pebble motion on graphs with rotations: Efficient feasibility tests and planning,” in   Proceedings Workshop on Algorithmic Foundations of Robotics , 2014. E. W. Dijkstra, “A note on two problems in connexion with graphs,”   Numerische mathematik , vol. 1, no. 1, pp. 269–271, 1959. M. R. Garey and D. S. Johnson,   Computers and Intractability: A Guide to the Theory of NP-Completeness .   W. H. Freeman, 1979. M. de Berg and A. Khosravi, “Optimal binary space partitions in the plane,” in   Computing and Combinatorics .   Springer, 2010, pp. 216–225. J. Yu and S. M. LaValle, “Multi-agent path planning and network flow,” in   Algorithmic Foundations of Robotics X, Springer Tracts in Advanced Robotics .   Springer Berlin/Heidelberg, 2013, vol. 86, pp. 157–173.