1  Optimal Multi-Robot Path Planning on Graphs: Structure and Computational Complexity  Jingjin Yu   Steven M. LaValle  Abstract  We study the problem of optimal multi-robot path planning on graphs (MPP) over four distinct minimization objectives: the total arrival time, the makespan (last arrival time), the total distance, and the maximum (single-robot traveled) distance. On the structure side, we show that each pair of these four objectives induces a Pareto front and cannot always be optimized simultaneously. Then, through reductions from 3SAT, we further establish that computation over each objective is an NP-hard task, providing evidence that solving MPP optimally is generally intractable. Nevertheless, in a related paper Yu and LaValle (2015), we design complete algorithms and efficient heuristics for optimizing all four objectives, capable of solving MPP optimally or near-optimally for hundreds of robots in challenging setups.  I. I NTRODUCTION  In this paper, we study the problem of optimal   multi-robot path planning on graphs   (MPP), focusing on   structural and computational complexity   issues. In an MPP instance, the robots are uniquely labeled and uniform sized spheres confined to an arbitrary connected graph. The robots may move from a vertex to an adjacent one in one time step in the absence of collision, which may occur when two robots simultaneously move to the same vertex or along the same edge in different directions. Over the basic MPP formulation, we look at four minimization objectives: the total arrival time, the makespan (last arrival time), the total distance, and the maximum (single-robot traveled) distance. In addition to showing that each pair of these objectives induces a Pareto optimal structure, we prove that all four objectives are NP-hard to optimize.  Related work.   Research on discrete multi-robot path planning problems can be traced back to the mathematical study of the   15 -puzzle Loyd (1959), in which   15   labeled ( 1 - 15 ) square game pieces, confined on a   4   ×   4   grid, must be moved to a row major ordering from some initial configuration. Note that only a single piece may be moved at a time. In Story (1879), it is observed that the feasibility of the   15 -puzzle is decided by the   parity   of the game setup. A while later, Wilson generalizes the observation, proving that the feasibility of moving   n   −   1   labeled   pebbles   on an   n -vertex   2 -connected graph depends on whether the graph is bipartite Wilson (1974). An algorithm for solving a feasible instance is also supplied in the work. A further generalization to arbitrary connected graph and arbitrary number of pebbles (but less than   n , the number of vertices of the underlying graph) is proposed in Kornhauser et al. (1984), which also gives a bound of   Θ( n 3 )   as the number of moves required for solving a feasible instance. Motivated by applications toward computer games and multi-robot systems, concurrent movements are introduced and studied extensively in the past decade Silver (2005); Jansen and Sturtevant (2008); Luna and Bekris (2011); Wagner and Choset (2011); Standley and Korf (2011). We refer to these problems under the umbrella term of   multi-robot path planning , or MPP. 1   Although the study in Kornhauser et al. (1984) assumes a single pebble (agent/robot) movement per time step, the   Θ( n 3 )   bound on the number of moves continues to hold when synchronous robot movements are allowed. With multi-robot applications in mind, in Yu and Rus (2014), the   Θ( n 3 )   bound is shown to extend when there are as many robots as graph vertices. As finding feasible solutions is a largely solved issue, most multi-robot path planning work has an emphasis on optimality. A lingering question in the pursuit of efficient algorithms for optimal MPP is the structure and complexity of such problems. In particular, if it is unclear whether an optimal MPP formulation is computationally intractable, then polynomial-time algorithm should be sought after. When there are   n   −   1   robots on a   n -vertex graph, finding the shortest sequence of moves that solves a given problem has long been established as NP-hard Goldreich (1984), even when the underlying graph is a grid Ratner and Warmuth (1990). Note that in such cases, because only a single move is allowed in a time step, time- and distance-based optimality objectives are equivalent. When there are less than   n   −   1   robots with synchronous robot movements allowed, it is unclear that time- and distance-based objectives are again the same. Moreover, results like Goldreich (1984); Ratner and Warmuth (1990) do not carry over to show that optimal MPP with synchronous moves are again intractable. The only available complexity result for optimal MPP can be found in Surynek (2010), which shows that minimum makespan MPP is intractable through a rather involved reduction.  Contributions.   To resolve issues surrounding the structural and complexity of optimal MPP, in this work, we carry out a systematic study on optimal MPP covering four global and arguably the most common time- and distance-based minimization  Jingjin Yu is with the Computer Science and Artificial Intelligence Lab, Massachusetts Institute of Technology, Cambridge, MA 02139, USA. E-mail: jingjin@csail.mit.edu. Steven M. LaValle is with the Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA. E-mail: lavalle@illinois.edu.  1 Another common name for these problems is   coorperative path-finding .  arXiv:1507.03289v1 [cs.RO] 12 Jul 2015
2  objectives. First, for each pair of the four objectives, through an infinite class of problem instances, we show that the pair of objectives cannot be optimized by a single solution. Moreover, the difference 2   between optimal solutions for these objectives can be arbitrarily large. Second, through reductions from the classical NP-hard 3SAT problem, we prove that optimizing each of the four objectives is computationally intractable. We further establish that some of these problems remain hard even when there are only two groups of interchangeable robots (optimal MPP is solvable in polynomial time when there is a single group of robots Yu and LaValle (2013a)). Our relatively straightforward reduction schemes preserve the structure of 3SAT, clearly illustrating the source of difficulty that renders optimal MPP problems hard. The rest of the paper is organized as follows. In Section II, we define the four optimal MPP problems and provide necessary background materials. We discuss the Pareto optimal structures in Section III and prove the NP-hardness of optimizing these objectives in Section IV and Section V. We conclude in Section VI. This paper is partly based on Yu and LaValle (2013b). In comparison to Yu and LaValle (2013b), an additional optimality objective is introduced. Most significantly, we have devised new and much simplified proofs for the distance-optimal cases. II. P RELIMINARIES  We now define MPP and the optimality objectives studied in this paper. Following the problem statements, we provide a brief description of 3SAT, a version of the   boolean satisfiability problem , on which our complexity proofs are based.  A. Multi-Robot Path Planning on Graphs  Let   G   = ( V, E )   be a connected, undirected, simple graph, with   V   =   { v i }   being the vertex set and   E   =   { ( v i , v j   ) }   the edge set. Let   R   =   { r 1 , . . . , r n }   be a set of   n   robots. The robots move at discrete time steps ( i.e. , at   t   = 0 ,   1 , . . . ). At time step  t   = 0 , each robot occupies a distinct vertex of   G . In general, at any time step   t   = 0 ,   1 , . . . , the robots assume a   configuration  that is an injective map from   R   to   V   . The   start   (or   initial ) and   goal   configurations of the robots are denoted as   x I   and   x G , respectively. As an example, Fig. 1(a) shows a possible configuration of   9   robots on a   3   ×   3   grid graph. 3   Fig. 1(b) shows a possible goal configuration, in which the robots are ordered according to what is commonly known as the row major ordering. 9   1 4  8   3 2  6   5 7 1   3 2  4   6 5  7   9 8  (a)   (b)  Fig. 1.   a) A 9-puzzle problem. b) The desired goal configuration.  For robot motion, during a discrete time step, each robot may either stay at its current vertex or move to an adjacent vertex. To formally describe a plan, let a   scheduled path   be a map   p i   :   Z +   →   V   , in which   Z +   :=   N   ∪ { 0 } . A scheduled path   p i  is   feasible   if it satisfies 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   k   ∈   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). As an illustration, Fig. 2 shows the feasible and infeasible moves for two robots during a single time step   4 . The   multi-robot path planning on graph   (MPP) problem is defined as follows. 2  1 2 1 2 1  (a)   (b)   (c)  Fig. 2.   Some feasible and infeasible moves for two robots. a) A feasible synchronous move. b) An infeasible synchronous move in which two robot collide “head-on”. c) An infeasible synchronous move in which two robots “meet” at a vertex.  Problem 1 (Multi-robot Path Planning on Graphs)   Given a   4 -tuple   ( G, R, x I   , x G ) , find a set of paths   P   =   { p 1 , . . . , p n }  such that   p i ’s are feasible paths for respective robots   r i ’s and no two paths   p i , p j   are in collision.  2 For a pair of objectives, let   ( a ∗  1   , a 2 )   and   ( a 1 , a ∗  2   )   be two solution vectors on the Pareto front such that   a ∗  1   is the optimal solution for the first objective and   a ∗  2   the optimal solution for the second objective. The difference may be measured as   ‖ ( a ∗  1   , a 2 )   −   ( a 1 , a ∗  2   ) ‖ ∞   with   ‖ · ‖ ∞   being the   L ∞ -norm.  3 In this paper, we generally use shaded discs to mark start locations of robots and discs without shading for goal locations.  4 We assume that the graph   G   only allows “meet” or “head-on” collisions. The assumption is mild. For example, a (arbitrary dimensional) grid with unit edge distance is such a graph for robots of with radii of no more than   √ 2 / 4 .
3  For example, Fig. 1(a) and Fig. 1(b) define an MPP problem on the   3   ×   3   grid. We call this particular problem the   9-puzzle  problem (a variant of the 15-puzzle Ratner and Warmuth (1990)), which readily generalizes to   N   2 -puzzles.  Remark.   With a few exceptions ( e.g. , Standley and Korf (2011)), most existing studies on discrete multi-robot path planning problems require empty vertices as swap spaces. In contrast, our MPP formulation allows synchronized rotations of robots along fully occupied cycles (see,   e.g. , Fig. 1 and 3).   4  B. Optimal Formulations  Let   P   =   { p 1 , . . . , p n }   be an arbitrary feasible solution to some fixed MPP instance. For a path   p i   ∈   P   , let   len ( p i )   denote 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 a path   p i , may visit the same edge multiple times. Recall that   t i   denotes the arrival time of robot   r i . In the study of optimal MPP, we examine four most common, global objectives with two focusing on time optimality and two focusing on distance optimality. Below, each objective is defined formally, followed by the corresponding decision version of the MPP problem. Note that these decision versions are necessary for stating the complexity ( i.e.   NP-completeness) results.  Objective 1 (Total Arrival Time)   Compute a path set   P   that minimizes   ∑ n i =1   t i .  MTATMPP (Minimum Total Arrival Time MPP) INSTANCE: An instance of MPP, and   K   ∈   Z . QUESTION: Is there a solution path set   P   with a total arrival time no more than   K ?  Objective 2 (Makespan)   Compute a path set   P   that minimizes   max 1 ≤ i ≤ n   t i .  M3PP (Minimum Makespan MPP) INSTANCE: An instance of MPP, and   K   ∈   Z . QUESTION: Is there a solution path set   P   with a makespan no more than   K ?  Objective 3 (Total Distance)   Compute a path set   P   that minimizes   ∑ n i =1   len ( p i ) .  MTDMPP (Minimum Total Distance MPP) INSTANCE: An instance of MPP, and   K   ∈   Z . QUESTION: Is there a solution path set   P   with a total path distance no more than   K ?  Objective 4 (Maximum Distance)   Compute a path set   P   that minimizes   max 1 ≤ i ≤ n   len ( p i ) .  MMDMPP (Minimum Maximum Distance MPP) INSTANCE: An instance of MPP, and   K   ∈   Z . QUESTION: Is there a solution path set   P   in which every path has a distance no more than   K ? The intuitive meaning of these objectives is clear from the definitions. Here, we provide a concrete example of a minimum makespan solution to the   9-puzzle   problem given in Fig. 1. Since there is no empty vertex, the robots can only rotate together with other robots in a synchronous manner. A solution with minimum makespan is given in Fig. 3. The time optimality of the solution is evident as it takes at least four steps for robot 9 to reach its goal.  Fig. 3.   A 4-step solution from our algorithm. The directed edges show the moving directions of the robots at the tail of the edges.  C. The   3SAT   Problem  All NP-hardness proofs in this paper are based on many-one reductions from NP-complete versions of the boolean satisfiability problem. In comparison to the conference paper Yu and LaValle (2013b), we have made an attempt to unify the proof strategy so that all reductions in the current work are based on the classical 3SAT problem Garey and Johnson (1979). In addition to greatly simplifying the NP-hardness proof for distance optimal MPP problems (see Section V), the unification suggests that
4  time- and distance-optimal MPP problems have the same source of complexity,   i.e. , the intractability arises from the sharing of paths between robots traveling in opposite directions. A 3SAT instance is defined by a 2-tuple   ( X, C )   in which   X   =   { x 1 , . . . , x n }   is the set of   binary variables   and   C   =  { c 1 , . . . , c m }   is the set of   disjunctive clauses . Each clause   c j   ∈   C   takes the form of   c j   =   y 1  j   ∨   y 2  j   ∨   y 3  j   , with each   y k j   ,   1   ≤   k   ≤   3  a   literal . That is,   y k j   ∈ { x 1 ,   ¬ x 1 , . . . , x n ,   ¬ x n } . Without loss of generality, we may assume that for fixed   1   ≤   j   ≤   m ,   y 1  j   , y 2  j   , and   y 3  j   are all distinct and do not contain literals of the same variable. An   assignment   of true or false values to the variables is represented as   {  ̃ x 1 , . . . ,    ̃ x n } . Throughout this paper, the 3SAT instance  X   =   { x 1 , x 2 , x 3 , x 4 } , C   =   { x 1   ∨ ¬ x 3   ∨   x 4 ,   ¬ x 1   ∨   x 2   ∨ ¬ x 4 ,   ¬ x 2   ∨   x 3   ∨   x 4 }   (1) is employed when a concrete 3SAT example is required. III. P ARETO   O PTIMAL   S TRUCTURE   B ETWEEN   O BJECTIVES  When it comes to optimization problems with multiple objectives, one generally expects a Pareto optimal structure. That is, fixing a problem instance, it is often unlikely that the optimal solution for one objective is also the optimal solution for a second objective. Optimal MPP is no exception: the solution vectors for each pair of Objectives 1 to 4 form a Pareto front. In this section, for each pair of objectives, we provide an infinite family of MPP instances for which the two objectives are optimized by different solutions. This structural study promotes our understanding of the target problem, which in turn helps us design algorithms for solving the problem. We start with the two time-based objectives.  Lemma 1   For MPP, optimality cannot always be simultaneously achieved for minimum total arrival time and minimum makespan. 2  1  2  1  3  3  Fig. 4.   A class of problems for which minimum makespan and minimum total arrival time cannot be simultaneously achieved in a single solution.  P ROOF . In Fig. 4, the start and goal vertices of robots   1 - 3   are as marked. Let the distance between each pair of the consecutive discs on the left side of the oval be one. Let the distance of the longer path on the right (between robot 3’s starting location and 2’s goal location) be some   x   ≥   1 . Given the arrangement of the robots, optimal solutions require the robots to all move in the clockwise direction or all move in the counterclockwise direction until they reach their goals. If the robots all move in the clockwise direction, the cost vector for total arrival time and makespan is   (2 x   + 3 , x   + 1) . The cost vector becomes  ( x   + 12 , x   + 4)   when the robots move in the counterclockwise direction. Thus, clockwise moves always yield solutions with minimum makespans. However, when   x >   9 , the solution corresponding to counterclockwise movements has a smaller total arrival time.     The construction from Fig. 4 also applies to show the general incompatibility between sum ( i.e. , total distance or time) objectives and maximum ( i.e. , maximum distance and time) objectives.  Lemma 2   For MPP, optimality cannot always be simultaneously achieved for (i) minimum total distance and minimum maximum distance, (ii) minimum total time and minimum maximum distance, and (iii) minimum total distance and minimum makespan.  P ROOF . The solution vectors from the proof of Lemma 1 coincide with the solution vectors for maximum distance and total distance; the clockwise and counterclockwise solutions yield solution vectors with total distance and maximum distance as   (2 x   + 3 , x   + 1)   and   ( x   + 12 , x   + 4) , respectively. Therefore, total distance and maximum distance objectives cannot be simultaneously minimized, which proves the claim for   (i) . Following the same reasoning, the claim also holds for   (ii)   and   (iii) .     For the other two pairings, a different set of problems are needed.  Lemma 3   For MPP, optimality cannot always be simultaneously achieved for minimum total arrival time and minimum total distance.
5 2  1  2  1  3  3  4  4  Fig. 5.   A class of problems for which minimum total arrival time and minimum total distance cannot be simultaneously achieved in a single solution.  P ROOF . In Fig. 5, the starts and goals of robots   1 - 4   are as marked. The distance between any adjacent pair of nodes (discs and black dots) is one. The solution with minimum total arrival time sends robots   1 - 3   through the solid path on the left and robot 4 through the dotted path on the right. This yields a total arrival time of   3 + 4 + 5 + 4 = 16   and a total distance of  3 + 3 + 3 + 4 = 13 . On the other hand, the solution with minimum total distance sends all robots from the left path, which yields a total arrival time of   18   and a total distance of   12 . By extending the lengths of the two vertical edges in the middle, we get an infinite family of examples.     Remark.   Using the construction from Fig. 5, we could show that maximum distance of an MPP solution cannot always be minimized in conjunction with makespan. To see this, note that the solution that minimize makespan requires robot   4   to go through the right vertical edge, which inevitably lengthens the distance traveled by the robot.   4  With Lemmas 1-3 and the accompanying remark, we reach the following conclusion concerning the structures of optimal MPP problems.  Theorem 4   For MPP, a solution that simultaneously minimizes any pair of objectives from Objectives 1-4 cannot always be found.  IV. C OMPUTATIONAL   C OMPLEXITY OF   T IME -O PTIMAL   MPP F ORMULATIONS  In this section and Section V, we show that optimizing each of the Objectives 1-4 is NP-hard. We devote this section to the discussion of time optimality. First, we prove that computing a minimum total arrival time solution is an intractable task.  Theorem 5   MTATMPP   is NP-complete.  P ROOF .   Instance construction.   We reduce from 3SAT to MTATMPP. From a 3SAT instance (the 3SAT instance (1) is used as the example), an MTATMPP instance is constructed as follows. For each variable   x i , two paths of length   m   + 2   each, joined at the end, are added. For our example, this step yields the four horizontal strips, stacked vertically, in the middle of Fig. 6. For convenience, we call the two paths of the   i -th horizontal strip (for variable   x i ) the   i -th upper and lower paths. At the left end of the construct ( i.e. , vertex   v x i   ) sits a   variable robot   r x i   , with its goal vertex   v g x i   at the right end. Robot   r x i  needs at least   m   + 2   steps to reach it goal. Next, for each clause   c j   =   y 1  j   ∨   y 2  j   ∨   y 3  j   , a   clause   robot   r c j   is set to start from the vertex   v c j   (see Fig. 6). The vertex   v c j   is connected to three paths associated with the three variables corresponding to   c j   ’s three literals. If a literal takes the non-negated (resp., negated) form of variable   x i , then   v c j   is connected to the   i -th upper (resp., lower) path at a vertex of distance   j   from  v x i   . For example, for   c 1   =   x 1   ∨ ¬ x 3   ∨   x 4 ,   v c 1   is connected to the first upper, third lower, and fourth upper paths, all at vertices of distance   1   from the left ends of the horizontal strips. After the clause structures are created, the goals for the   r c j   ’s are added. For this purpose, a path of length   m   −   1   is added ( e.g.   the leftmost path with blue vertices in Fig. 6), with the left vertex being the goal for   r c 1   and the right vertex the goal for   r c m   . The goal vertex for   r c m   ,   v g c m   , is connected to all   v x i   ’s, the start vertices of robots   r x i   ’s. Having constructed an MPP instance, setting   K   = ( n   +   m )( m   + 2)   fully describes an instance of MTATMPP. Fig. 6 gives the complete graph for the MTATMPP instance constructed from the example 3SAT instance. Here,   n   = 4   and   m   = 3 , which makes   K   = 35 .  Many-one reduction . If the 3SAT instance is satisfiable, let    ̃ x 1 , . . . ,    ̃ x n   be an assignment of the truth values to the variables. For each variable   x i , if    ̃ x i   is true (resp., false), then let robot   r x i   take the lower (resp., upper) path on its strip. The upper (resp., lower) path is then free to use for transporting the robots corresponding to the clauses,   r c j   ’s. All   m   +   n   robots can start moving at time step zero and arrive at their desired goals at time step   m   + 2 . The total time is then   ( m   +   n )( m   + 2) . On the other hand, if the MPP instance has a solution with total arrival time   ( n   +   m )( m   + 2) , then every robot must start moving at time step zero, follow a shortest path, and never stop until it reaches its goal. This forces every robot   r x i   to take either the upper or lower path on its own horizontal strip, which prevents any robot   r c j   from using the same path in the opposite direction. If robot   r x i   uses the upper (resp., lower) path, let    ̃ x i   =   f alse   (resp.,   true ). The resulting assignment    ̃ x 1 , . . . ,    ̃ x n
6 x 1  v  x 4  v  c 1  v   c 2  v   c 3  v  c 1  v   g  x 2  v  x 3  v  c 2  v   g   c 3  v   g  x 1  v   g  x 4  v   g  x 3  v   g  x 2  v   g  Fig. 6.   Reduction of 3SAT to MTATMPP with   K   = 5 .  satisfies the 3SAT instance. This proves the NP-hardness of MTATMPP. Because MTATMPP is also in NP (checking that a given solution uses no more than some total time   K   is easy), it is NP-complete.     Remark.   3SAT’s complexity arises because the values of many binary variables in an instance, which model input signals to a set of connected logical gates, must be simultaneously decided. In the proof of Theorem 5, we could simulate the logical- gate-like structure of 3SAT due to the time synchronization among the robots required from an optimal solution. Since all robots must move the same number of time steps in our construction, the number of candidate paths is very limited. There are two such paths for each variable robot and three such paths for a clause robot. Then, the individual paths for the clause robots effectively simulate a integrated circuit. The choice among three possible paths simulates an   or   gate and sequentially arranged goals simulate an   and   gate. The forced time synchronization also enabled the use a minimum number of robots; only   n   (the number of variable) robots are used to simulate the choice between true and false for a variable, and only   m   robots are used to simulate the conjunctions of   m   disjunctive clauses.   4  The carefully constructed reduction scheme for proving Theorem 5 readily extends to show that minimizing the makespan is also NP-hard.  Theorem 6   M3PP   is NP-complete.  P ROOF . In the proof of Theorem 5, after the MPP instance is created, setting   K   =   m   + 2   as the minimum makespan produces an M3PP instance from the 3SAT instance. The rest of the proof remains the same.     Remark.   Previously, complexity results on optimal MPP problems mostly focus on variants of the 15-puzzle with a single empty vertex for swapping. In that case, only one robot may move in a time step, thus rendering time optimality equivalent to distance optimality. This is no longer the case here. One exception is Surynek (2010), which addresses the time optimality of parallel pebble motion problems. As explained in Yu and Rus (2014), Theorem 6 can be established through a reduction from the NP-hard minimum makespan   parallel pebble motion   problem from Surynek (2010). The proof technique given in Surynek (2010) is however highly involved and seems unnecessarily complex. The proof presented here, in addition to working for proving Theorem 5, is much more direct. Moreover, the reduction ( e.g. , Fig. 6) clearly illustrates what makes finding time optimal solutions hard: When multiple robots move in opposite directions thorough a few shared paths, it is critical that the right paths are picked if time optimality is desired. In fact, our proof technique allows us to establish an even stronger intractability result that is surprising: computing a time optimal solution is NP-hard even when there are only two groups of interchangeable robots. By a   group of interchangeable robots , we mean that the goals for these robots are not fixed   a priori . Instead, all that is required is that each goal assigned to the group is occupied by some robot from the group in the end. An intuitive way to think about this is to view the two groups of robots as two teams with one red team and one blue team. The task is to move the each team of robots from some initial formation to some target formation. Note that if there is a single group of robots, time optimal solution can be computed in polynomial time Yu and LaValle (2013a). However, once we go from a single group to two groups, this is no longer the case.   4
7  Theorem 7   MTATMPP   and   M3PP   remain NP-complete when robots are partitioned into two or more groups in which robots within each group are interchangeable.  P ROOF . In the reduction from 3SAT, let the variable robots belong to one group and the clause robots belong to another group. Note that this does not change the shortest path for any of the robot. To see that this is the case, we first note that each variable robot still requires at least   m   + 2   time steps to go from the left end of a horizontal strip to the right end of a horizontal strip. For a clause robot, although some robots can now reach a goal faster ( e.g. , the distance between   v g c 1   and  v c m   is only   3   instead of   m   + 2 = 5 ), occupying the goal vertex   v g c 1   requires at least   m   + 2   time steps. Moreover, this is only possible for the clause robot starting at   v c 1   to do so. After this,   v g c 2   can only be reached by the clause robot at   v c 2   in   m   + 2  steps. Inductively, a minimum time solution (makespan or total arrival time) requires the clause robot starting at   v c j   to go to  v g c i   , which requires   m   + 2   time steps. Through this analysis, we have established the equivalence between many robots and two groups of robots in terms of the reduction from 3SAT to MTATMPP and M3PP, which then shows that MTATMPP and M3PP are NP-complete even when there are only two groups of robots. It is straightforward to add additional robot groups. For example, to have three groups, we may simply split the group of variables robots into two arbitrary (non-empty) groups.     Remark.   In viewing the result from Yu and LaValle (2013a) and Theorem 7, MTATMPP and M3PP experience a   sharp  transition in computational complexity as the robots go from a single group to two groups. The intuitive explanation behind the sudden change is the following. When there is a single group of robots, no two robots will ever need to run in opposite directions. That is, the situation illustrated in Fig. 2(b) never happens when there is a single group of robots ( i.e.   all robots are interchangeable), because two such robots can simply “exchange” goals and reduce travel distance (and time). The situation in Fig. 2(c) may still happen for a single group of robots, but it is possible to show that there is only a limited number (no more than the total number of robots) of such “meet” conflicts. Moreover, these conflicts can be resolved globally to obtain an optimal solution.   4  V. C OMPUTATIONAL   C OMPLEXITY OF   D ISTANCE -O PTIMAL   MPP F ORMULATIONS  Since computing time-optimal solutions for MPP is NP-hard, conceivably, computing distance-optimal solutions for MPP is likely to be an intractable task as well. However, showing this rigorously turns out to be much more challenging. Intuitively, proving that finding distance-optimal solutions is NP-hard is more involved because there is no longer the need to synchronize the movements between all robots time-wise; robots now only affect each other through physical interactions. As a consequence, simulating a circuit like structure, as we have done in the time-optimal case, becomes tricky for the distance-optimal case. To accomplish this, in Yu and LaValle (2013b), we have resorted to adopt a complex reduction from 2/2/4-SAT 5   Ratner and Warmuth (1990). Although we are able to prove the NP-hardness of MTDMPP in Yu and LaValle (2013b), much of the effort there went to coming up with a   locking mechanism   for preserving the structure of 2/2/4-SAT during its reduction to MTDMPP. The complicated locking mechanism then unfortunately masks the intrinsic structure that makes MTDMPP intractable. Moreover, the same structure does not readily extend to show the intractability of MMDMPP. Here, we address these issues with a direct reduction from 3SAT to MTDMPP. The update reduction scheme can also be easily adopted to show the NP-hardness of MMDMPP.  A. Total Distance Objective  As we want to prove the intractability MTDMPP using a reduction from 3SAT, it is essential to preserve the structure that renders 3SAT hard. Because distance-optimal solutions for MPP do not require time synchronization, to retain the structure of 3SAT, some form of locking mechanism is necessary to restrict undesirable (time-parametrized) robot paths. We achieve this through the addition of a large number of robots int the reduced MPP instance. Fig. 7 provides the essential pieces (gadgets) needed for the construction of the MTDMPP instance and illustrates how the pieces connect to each other. There are four types of gadgets in the construction:   (i)   n   variable gadgets , one of which is shown in the pink block in Fig. 7,   (ii)   m   clause source gadgets , one of which is shown in (the green block),   (iii)   m   clause sink gadgets , one of which is shown in (the orange block), and   (iv)   a single   exchange gadget   (the blue block). All vertices in Fig. 7 marked with solid circles have robots occupied on them in the beginning. In the following, the construction of each type of gadgets is described in detail.  Clause gadgets . A clause gadget (in the case of Fig. 7, for the clause   c 1   from (1)) has a source part and a sink part. In general, for a clause   c i , the clause sink gadget contains three vertices that are unoccupied in the begining,   v g c i   , v 2 g c i   , and   v 3 g c i   . The clause source gadget has 6 vertices, partitioned here into two layers of three vertices each. The bottom layer has three vertices named   v ks c j   ,   1   ≤   k   ≤   3 . The top layer has names depending the actual content of the clause. We use clause   c 1   from (1)  5   2/2/4-SAT is a specialized, NP-hard version of the boolean satisfiability problem. In a 2/2/4-SAT, there are   n   variables and   n   clauses. Each variable appears exactly four times as literals, twice negated and twice non-negated. Each clause contains exactly four literals.
8 c 1  v   1 s   c 1  v   2 s   c 1  v   3 s  c 1  v   g   c 1  v   3 g  c 1  v   2 g  1 x c 3  v   s  c 1  v   1 g   c 3  v   1 g  c 2  v   1 g  c 1  v   s  c 2  v   s  x 1  v   1 t   x 1  v   2 t   x 1  v   3 t   x 1  v   4 t  x 1  v   1 f   x 1  v   2 f   x 1  v   3 f   x 1  v   4 f  x 1  v   `  x 1  v   r  c 1  v   x 1   c 1  v   x 3   c 1  v   x 4 1 c  1 c  clause   source   gadget clause   sink   gadget variable   gadget exchange  gadget  Fig. 7.   Essential gadgets and their interconnection for the construction of a MTDMPP instance from a 3SAT instance.  as an example to illustrate the naming scheme. For   c 1   =   x 1   ∨ ¬ x 3   ∨   x 4 , the top three vertices are named   v c 1 x 1   ,   v c 1 x 3   , and  v c 1 x 4   , respectively. There are three robots starting from a clause source gadget, initially residing on vertices   v ks c j   ,   1   ≤   k   ≤   3 .  Variable gadgets.   A variable gadget has the same graph structure, a   (2 m   + 4) -cycle, as that from Fig. 6. The difference here is that all vertices have robots on them initially; the construction for time-optimal MPP only has one robot on each of such gadgets. We name the vertices on the   (2 m   + 4) -cycle as illustrated in Fig. 7; the superscript letters   r, `, t,   and   f   represent  right ,   left ,   true , and   false , respectively. The connections between the variable gadget and the clause source/sink gadgets are similar to that from Fig. 6 as well, although slightly more complex. Using clause   c 1   as an example,   v 1 s c 1   , v 2 s c 1   , and   v 3 s c 1   are each connected to   v 1 t x 1   ,   v 1 f x 3   , and   v 1 t x 4   . Then   v g c 1   ,   v 2 g c 1   , and   v 3 g c 1   are each connected to   v 4 f x 1   ,   v 4 t x 3   , and   v 4 f x 4   . Note that vertices   v 1 f x 3   ,   v 1 t x 4   ,  v 4 t x 3   , and   v 4 f x 4   , which are on variable gadgets for   x 3   or   x 4 , are not shown in Fig. 7.  Exchange gadget.   The last essential piece of the graph structure, the exchange gadget, has   2 m   vertices,   v 1 s c j   and   v 1 g c j   for  1   ≤   j   ≤   m . The vertices   v s c 1   and   v 1 g c m   are connected to   v l x i   for all   1   ≤   i   ≤   n . All   2 m   vertices are occupied by robots. With the individual gadgets fully specified, we piece together the gadgets for a reduction from 3SAT to MTDMPP.  Theorem 8   MTDMPP   is NP-complete.  P ROOF .   Instance construction . The full graph structure of the reduced MTDMPP instance from the 3SAT instance (1), along with the starting robot locations, is given in Fig. 8. To complete the MTDMPP instance, we need to specify goals for all robots and then set the value of   K . The goals for the robots are assigned as follows. (i) If a robot start from a vertex named with “s” in the superscript, then the goal for the robot is the correspondingly named vertex with a “g” in the superscript. For example, the robot starting from   v 1 s c 1   must go to   v 1 g c 1   . (ii) The robots on   v 1 g c j   ,   1   ≤   j   ≤   m   ( i.e. , the vertices on the lower portion of the exchange gadget) must go to   v s c j   ( i.e.   the diagonal location on the exchange gadget). (iii)   For robots on a variable gadget, if a robot resides on a vertex connecting to a clause source gadget,   e.g. ,   v jt x i   or   v jf x i   , the robot then must go to the closest   v c j   x i   vertex, which is unique. For example, for the robot starting on   v 1 t x 1   , its goal vertex is   v c 1 x 1   . (iv)   For all other robots on a variable gadget, the robot must reach the opposite (farthest) location on the gadget. For example, a robot from   v ` x 1   must go to   v r x 1   . To set the value of   K , we collect the minimum distance required for each robot to reach its goal, which is straightforward to observe. Table I lists these distance for most of the robots with the exception of robots starting on a variable gadget. If a robot starts on a variable gadget vertex that is adjacent to a clause source gadget, it only needs to travel two steps to reach its goal ( e.g. , the robot on   v 1 t x 1   needs to go   v c 1 x 1   ). For all other robots on variable gadgets, they need to travel a minimum distance of   m   + 2   to reach the opposite side. The MTDMPP instance is fully specified by setting   K   as the sum of all these minimum individual distances.  Many-one reduction . We first show that if the 3SAT instance has a satisfactory assignment, then all robots can follow their shortest possible paths to reach their respective goals. Since the variable gadgets are filled with robots, for robots to follow shortest possible paths, robots on a single variable gadget can only move in either clockwise or counterclockwise direction but not both (this will be made more formal shortly). The direction with with robots on a variable gadget rotates is decided by the
9 1 c  4 x  2 c   3 c  3 c   2 c   1 c  1 x  3 x  2 x  Fig. 8.   The full graph structure and the starting configuration of a MTDMPP instance reduced from the 3SAT instance given in (1). TABLE I M INIMUM REQUIRED DISTANCE FOR ROBOTS NOT STARTING FROM A VARIABLE GADGET . Start vertex   v 1 s c j   v 2 s c j   , v 3 s c j   v s c j   v 1 g c j  Min distance   m   + 2   m   + 4   m   + 3   m  assignment of true or false to the corresponding variable. If a variable is set to true (resp., false), then the direction of rotation on the corresponding variable gadget is counterclockwise (resp., clockwise). Note that this convention is similar to that in the time-optimal case. Once the direction of rotation along each variable gadget is decided, we use this information to pick the “correct” variable gadgets to move the robots starting on   v ks c j   ,   1   ≤   k   ≤   3 . We point out that the important robots here are the robots starting on   v 1 s c j   ,   1   ≤   j   ≤   m   because these robots must end up on the exchange gadget. For such a robot to move to the exchange gadget, it must first reach the left end of a variable gadget. This can be guaranteed as follows. For a clause   c j   , one of its literal, corresponding to a variable   x i , must be true given a satisfiable assignment. We let the robot starting on   v 1 s c j   move to the variable gadget for   x i . Now if the literal is   x i   =   true   (resp.,   ¬ x i   =   true ), then the robot starting on   v 1 s c j   will be moved to the upper (resp., lower) path on the   i -th variable gadget. At the same time, the rotation direction of the variable gadget is counterclockwise (resp., clockwise). Therefore, in either case, the robot starting on   v 1 s c j   can reach the left most vertex ( e.g. ,  v ` x i   ) following the rotation direction of the   i -th variable gadget. Subsequently, the robot can be moved to the exchange gadget and swap out the robot starting on   v s c j   . As a concrete example, for   c 1   =   x 1   ∨ ¬ x 3   ∨   x 4 , if   x 1   is set to true in a satisfiable assignment, then robot starting at   v 1 s c 1  can move to   v 1 t x 1   (see Fig. 7), via rotations of robots along the 6-cycle   v 1 s c 1   −   v 1 t x 1   −   v 2 s c 1   −   v 1 f x 3   −   v 3 s c 1   −   v 1 t x 4   . The robot can then move to   v ` x 1   following the counterclockwise rotation of the variable gadget for   x 1 . After describing the key moves, we now provide the full set of movements yielding the minimum total distance solution. First, all robots starting on clause source gadgets are moved out of these gadgets via rotations along   6 -cycles stated above. Then, robots on the variable gadgets will start synchronous rotations. Whenever a robot starting from some   v 1 s c j   reach some  v ` x i   , robots on the exchange gadget will rotate counterclockwise to move the robot from   v ` x i   to the exchange gadget. These steps are repeated until the robots starting on   v ` x i   reach   v r x i   for all   1   ≤   i   ≤   n . Lastly, vertices on the clause sink gadgets get filled with appropriate robots. It is straightforward to check such a plan enables all robots to reach their goals following their respective shortest paths. Having established the reduction in one direction, we also need to show that if the MPP instance has a minimum possible total distance solution, then the corresponding 3SAT instance is satisfiable. To show this, we first establish what possible moves can happen at a given stage if the minimum possible total distance is to be reached. In the beginning, it is clear that robots on the exchange gadget cannot move. Also, rotations along any variable gadget cannot happen either because this will cause robots on vertices like   v 1 t x 1   to travel extra distances. The only possible move in the beginning then must involve robots on a clause gadget. Assume the clause source gadget for some   c j   is involved. To avoid traveling extra distance, this forces
10  all robots on the clause source gadget   c j   to move synchronously. To see this, note that a robot starting from a clause source gadget must move out of the gadget in one step. And this will cause an adjacent robot on a variable gadget to move to the clause source gadget, also due to the minimum distance constraint. This in turn forces another robot on the same clause source gadget to move to a variable gadget. In the case of   c 1 , this means the first move must be a synchronous rotation along a 6-cycle, for example   v 1 s c 1   −   v 1 t x 1   −   v 2 s c 1   −   v 1 f x 3   −   v 3 s c 1   −   v 1 t x 4   . Once a clause source gadget interacts with (three) variable gadgets, there cannot be further interactions between the clause source gadget and the rest of the MPP instance graph. After this first step, some variable gadget may start rotating. Before a variable gadget can start rotating, all its interaction with clause source gadgets must be fully complete (because, for example, the robot starting at   v 1 t x 1   must be moved out of the variable gadget to avoid traveling extra distances). This also means that there is no interaction ( i.e. , flow of robots) between any two variable gadgets. Therefore, once a variable gadget starts rotating, it only has limited interaction with the exchange gadget until it completes   m   + 2   rotations, all in the same direction (either clockwise or counterclockwise), after which some robots will move out of it to clause sink gadgets. To summarize the previous two paragraphs, a clause source gadget can interact (only once and simultaneously) with three variable gadgets in a single synchronized rotation. On the other hand, each variable gadget must first complete its interaction with all (neighboring) clause source gadgets before it can rotate. Then, the variable gadget must decide a direction to rotate for  m   + 2   times. Since we assume that we have a total distance optimal solution, this means the rotation directions of the variable gadgets are known. This in turn means that we know robots on   v 1 s c j   ,   1   ≤   j   ≤   m   should go to which variable gadgets so the rotation of the variable gadgets will allow them to travel to their goals on the exchange gadget along a minimum distance path. As we have established in the proof of Theorem 5, this is equivalent to finding a satisfactory assignment for the corresponding 3SAT instance. So far we have established the NP-hardness of MTDMPP. Because MTDMPP is easily seen to be in NP, it is NP-complete.     B. Maximum Distance Objective  Using the same general technique and with some added effort, we can establish that MMDMPP is also intractable.  Theorem 9   MMDMPP   is NP-complete.  P ROOF . The reduction used here is a modification of that from the proof of Theorem 8. For the given 3SAT instance (1), the MMDMPP instance uses the same four types of gadgets as the MTDMPP instance. Moreover, only small parts of the gadgets are changed. In particular, the interconnections between the gadgets ( e.g. , Fig. 8) remain identical. The updated construction of the gadgets, adopted from Fig. 7, is given in Fig. 9; the vertex labels are omitted. The difference here is that additional one-way paths are appended to some vertices to make all robots travel the same (shortest) distance of  m +4 . For example, since robots starting from   v 1 s c j   ,   1   ≤   j   ≤   m , need to travel   m +2   steps to reach their goals in the MTDMPP instance, we let these robots travel two additional steps (reflected by the sequence of length two paths in the lower part of the blue exchange gadget). Note that for variable gadgets, we attach a path of length two to each of its vertex unless the vertex is connected to a clause sink gadget. In the case of the variable gadget for   x 1 , no path of length two is added to the third upper vertex ( i.e. ,   v 3 t x 1   in Fig. 7) and the fourth lower vertex ( i.e. ,   v 4 f x 1   in Fig. 7). 1 x  1 c  1 c  Fig. 9.   Reduction of 3SAT to MMDMPP with   K   =   m   + 4   .  We note that each added vertex can only be used for a specific robot. Otherwise, some robot must travel more than a distance of   m   + 4   to reach the designed goal. To complete the proof, we only need to show that if the MMDMPP instance has a yes
11  answer, then the corresponding 3SAT instance is satisfiable. We establish this by showing that the newly added vertices and edges do not make the problem easier to solve. The added vertices and edges on a clause source gadget can only be used after the interaction of the clause source with adjacent variable gadgets is complete. Also, the added vertex and edge on a clause sink gadget can only be used after the rotation of a variable gadget is fully complete ( i.e. ,   m   + 2   rotations). Therefore, added structures on the clause source/sink gadgets do not allow additional path flexibility. Similarly, the added vertices and edges on the exchange gadget can only be used after all rotations of the exchange gadget are complete ( i.e. ,   m   rotations). Therefore, the added structures on the exchange gadgets do not allow additional path flexibility. The case of the variable gadget is more tricky because one variable gadget may finish all its   m   + 2   rotations and then move all the robots out of the   (2 m   + 4) -cycle. This potentially can then be used for other robots to pass through. However, we note that any robot that does this must come from a different variable gadget or a non-adjacent clause source gadget. It is straightforward to check that such moves will incur extra travel distance for the robots that are involved. Therefore, the min-max distance requirement does not allow any robot to use an “un-intended” variable gadget as part of its path. This then returns us to the MTDMPP case. The rest of the proof follows that of Theorem 8.     VI. C ONCLUSION  In this paper, we have investigated the structural and complexity of optimal MPP problems that minimize the total arrival time, the makespan, the total distance, and the maximum distance for MPP. We show that each pair of these objectives cannot be simultaneously optimized. We then further establish that optimizing over each of these objectives is NP-hard. We conclude that these common time- and distance-based optimality objectives are computationally intractable, suggesting that algorithm designers should look for approximations and heuristics in resolving these problems. Our study also raises interesting questions with practical implications; we mention two here. On the structure side, although the objectives are in a sense “incompatible”, they are nevertheless highly similar. For example, our observation seems to suggest that the time horizon required for minimizing the maximum distance is no more than twice of that needed for minimizing the makespan. A more careful look at such issues could reveal additional structures which may lead to better algorithm design. On the complexity side, unlike the time-optimal case, the NP-hardness proofs for MTDMPP and MMDMPP do not readily extend to show that these problems remain hard for two groups of robots. We believe that this is indeed the case and leave it as a conjecture.  Conjecture 10   MTDMPP   and   MMDMPP   remain NP-hard when there are only two groups of robots.  R EFERENCES J. Yu and S. M. LaValle, “Optimal multi-robot path planning on graphs: Complete algorithms and effective heuristics,” 2015, reference to be updated. S. Loyd,   Mathematical Puzzles of Sam Loyd .   New York: Dover, 1959. 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. 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. D. Silver, “Cooperative pathfinding,” in   The 1st Conference on Artificial Intelligence and Interactive Digital Entertainment , 2005, pp. 23–28. R. Jansen and N. Sturtevant, “A new approach to cooperative pathfinding,” in   In International Conference on Autonomous Agents and Multiagent Systems , 2008, pp. 1401–1404. R. Luna and K. E. Bekris, “Push and swap: Fast cooperative path-finding with completeness guarantees,” in   Proceedings International Joint Conference on Artificial Intelligence , 2011, pp. 294–300. 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. T. Standley and R. Korf, “Complete algorithms for cooperative pathfinding problems,” in   Proceedings International Joint Conference on Artificial Intelligence , 2011, pp. 668–673. 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. 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, “Multi-agent path planning and network flow,” in   Algorithmic Foundations of Robotics X, Springer Tracts in Advanced Robotics (STAR) .   Springer Berlin/Heidelberg, 2013, vol. 86, pp. 157–173. ——, “Structure and intractability of optimal multi-robot path planning on graphs,” in   Proceedings AAAI National Conference on Artificial Intelligence , 2013, pp. 1444–1449. M. R. Garey and D. S. Johnson,   Computers and Intractability: A Guide to the Theory of NP-Completeness .   W. H. Freeman, 1979.