1  Efficient Multi-Robot Motion Planning for Unlabeled Discs in Simple Polygons  Aviv Adler, Mark de Berg, Dan Halperin, and Kiril Solovey  Abstract —We consider the following motion-planning problem: we are given   m   unit discs in a simple polygon with   n   vertices, each at their own start position, and we want to move the discs to a given set of   m   target positions. Contrary to the standard (labeled) version of the problem, each disc is allowed to be moved to any target position, as long as in the end every target position is occupied. We show that this unlabeled version of the problem can be solved in   O   ( n   log   n   +   mn   +   m 2 )   time, assuming that the start and target positions are at least some minimal distance from each other. This is in sharp contrast to the standard (labeled) and more general multi-robot motion planning problem for discs moving in a simple polygon, which is known to be strongly   NP - hard.  I. I NTRODUCTION  The   multi-robot motion-planning problem   is to plan the motions of several robots operating in a common workspace. In its most basic form, the goal is to move each robot from its start position to some designated target position, while avoiding collision with obstacles in the environment and with other robots. Besides its obvious relevance to robotics, the problem has various other applications, for example in the design of computer games or crowd simulation. Multi-robot motion planning is a natural extension of the single-robot motion planning problem, but it is much more complex due to the high number of   degrees of freedom   that it entails, even when the individual robots are as simple as discs.  A. Related work  One of the first occurrences of the multi-robot motion- planning problem in the computational-geometry literature can be found in the series of papers on the   Piano Movers’ Problem  by Schwartz and Sharir. They first considered the problem in a general setting [1] and then narrowed it down to the case of disc robots moving amidst polygonal obstacles [2]. In the latter work an algorithm was presented for the case of two and three robots, with running time of   O ( n 3 )   and   O ( n 13 ) , respectively, where   n   is the complexity of the workspace.  A. Adler is with the Electrical Engineering and Computer Science depart- ment at MIT, Massachusetts, USA. The work has been carried out in part during his visit to Tel Aviv University, enabled by the generous Melvin M. Goldberg Fellowship for Research in Israel. M. de Berg is with the Department of Mathematics and Computing Science, TU Eindhoven, the Netherlands. D. Halperin and K. Solovey are with the Blavatnik School of Computer Science, Tel-Aviv University, Israel. Their work has been supported in part by the 7th Framework Programme for Research of the European Commission, under   FET-Open   grant   number   255827   (CGL—Computational   Geometry Learning), by the Israel Science Foundation (grant no. 1102/11), by the German-Israeli Foundation (grant no. 1150-82.6/2011), and by the Hermann Minkowski–Minerva Center for Geometry at Tel Aviv University.  Later Yap [3] used the   retraction method   to develop a more efficient algorithm, which runs in   O ( n 2 )   and   O ( n 3 )   time for the case of two and three robots, respectively. Several years afterwards, Sharir and Sifrony [4] presented a general approach based on   cell decomposition , which is capable of dealing with various types of robot pairs and which has a running time of   O ( n 2 ) . Moreover, several techniques that reduce the effective number of degrees of freedom of the problem have been proposed [5, 6]. When the number of robots is no longer a fixed con- stant, the multi-robot motion-planning problem becomes hard. Hopcroft et al. [7] showed that even in the relatively sim- ple setting of   n   rectangular robots moving in a rectangular workspace, the problem is already   PSPACE -hard. Moreover, Spirakis and Yap [8] showed that the problem is strongly   NP - hard for disc robots in a simple polygon. In recent years, multi-robot planning has attracted a great deal of attention from the robotics community. This can be mainly attributed to two reasons. First, it is a problem of practical importance. Second, the emergence of the   sampling- based techniques , which are relatively easy to implement, yet are highly effective. These techniques attempt to capture the connectivity of the configuration space through random sam- pling [9, 10]. Although sampling-based algorithms are usually incomplete—they are not guaranteed to find a solution—they tend to be very efficient in practice. Hence, they are con- sidered the method-of-choice for motion-planning problems that involve many degrees of freedom. While sampling-based tools for a single robot can be applied directly to the multi- robot problem by considering the group of robots as one large   composite robot   [11], there is a large body of work that attempts to exploit the unique properties of the multi-robot problem [12, 13, 14, 15, 16, 17]. The aforementioned results deal exclusively with the classi- cal formulation of the multi-robot problem, where the robots are   distinct   and   every   robot   is   assigned   a   specific   target position. The   unlabeled   variant of the problem, where all the robots are assumed to be identical and thus interchangeable, was first considered by Kloder and Hutchinson [18], who de- vised a sampling-based algorithm for the problem. Recently a generalization of the unlabeled problem—the   k -color motion- planning problem —has been proposed, in which there are sev- eral groups of interchangeable robots [19]. Turpin et al. [20] considered a special setting of the unlabeled problem with disc robots, namely where the collection of free configurations surrounding every start or target position is star-shaped. This condition allows them to devise an efficient algorithm that computes   a   solution   in   which   the   maximum   path   length  arXiv:1312.1038v3 [cs.CG] 26 Jan 2015
2  is minimized. Unfortunately the star-shapedness condition is quite restrictive, and in general it will not be satisfied. Other related work includes papers that study the number of   moves   required   to   move   a   set   of   discs   between   two sets of positions in an unbounded workspace, when a move consists of sliding a single disc—see for example the paper by Bereg et al. [21] which provides upper and lower bounds for the unlabeled case, or the paper by Dumitrescu and Jiang [22] who show that deciding whether a collection of labeled or unlabeled discs can be moved between two sets of positions within   k   steps is   NP -hard. Finally, we mention the problem of   pebble motions on graphs , which can be considered as a discrete variant of the multi-robot motion planning problem. In this problem, pebbles need to be moved from one set of vertices of a graph to another, while following a certain set of rules—see for example [23, 24, 25, 26, 27, 28].  B. Our contribution  Surprisingly,   the   unlabeled   version   of   the   multi-robot motion-planning problem has hardly received any attention in the computational-geometry literature. Indeed, we don’t know of any papers that solve the problem in an exact and complete manner, except in a restricted setting studied by Turpin et al. [20] that we mentioned above. We therefore study the following basic variant of the problem: given   m   unit discs in a simple polygon with   n   vertices, each at their own start position, and   m   target positions, find collision-free motions for the discs such that at the end of the motions each disc occupies a target position. We make the additional assumption that the given start and target positions are   well-separated . More precisely, any two of the given start and target positions should be at distance at least 4 from each other. Notice that we only assume this extra separation between the robots in their static initial and goal placements; we do not assume any extra separation (beyond non-collision) between a robot and the obstacles, nor do we enforce any extra separation between the robots during the motion. Even this basic version of the problem turns out to have a rich structure and poses several difficulties and interesting questions. By carefully examining the various properties of the prob- lem we show how to transform it into a discrete pebble- motion problem on graphs. A solution to the pebble prob- lem,   which   can   be   generated   with   rather   straightforward techniques, can then be transformed back into a solution to our continuous motion-planning problem. We mention that a similar transformation was used in [19] in the context of a sampling-based method. Using this transformation we are able to devise an efficient algorithm whose running time is  O   ( n   log   n   +   mn   +   m 2 ) , where   m   is the number of robots and   n   is the complexity of the workspace. To be precise, we show that our algorithm runs in   O ( n   log   n   +   m 2 )   time, and the overall description length of all the paths to be carried out by the robots has complexity   O ( mn   +   m 2 ) . As already mentioned, this is in sharp contrast to the standard (labeled) and more general multi-robot motion planning problem for discs moving in a simple polygon, which is known to be strongly   NP -hard [8]. II. P RELIMINARIES  We consider the problem of   m   indistinguishable unit-disc robots moving in a simple polygonal workspace   W ⊂   R 2   with  n   edges. We define   O   4  =   R 2   \ W   to be the complement of the workspace, and we call   O   the   obstacle space . Since our robots are discs, a placement of a robot is uniquely specified by the location of its center. Hence, we will sometimes refer to points  x   ∈ W   as   configurations , and we will say that a robot is   at configuration   x   when its center is placed at the point   x   ∈   W   . For given   x   ∈   R 2   and   r   ∈   R + , we define   D r   ( x )   to be the open disc of radius   r   centered at   x . We consider the unit-disc robots to be open sets. Thus a robot avoids collision with the obstacle space if and only if its center is at distance at least 1 from   O , that is, when it is at a configuration located in the   free space   F   4  =   { x   ∈   R 2   :  D 1 ( x ) ∩O   =   ∅} . We require the robots to avoid collisions with each other, so if a robot is at configuration   x   then no other robot can be at a configuration   y   ∈   Int( D 2 ( x )) ; here   Int( X )  denotes the interior of the set   X . Furthermore, the notation  ∂ ( X )   will be used to refer the boundary of   X . We call   D 2 ( x )  the   collision disc   of the configuration   x . Besides the simple polygon   W   forming the workspace, we   are   also   given   sets   S   =   { s 1 , s 2 , ..., s m }   and   T   =  { t 1 , t 2 , ..., t m } , such that   S, T   ⊂ F . These are respectively the sets of   start   and   target   configurations of our   m   identical disc robots. We assume that the configurations in   S   and   T   are  well-separated : For any two distinct configurations   x, y   ∈   S   ∪   T  we have   ‖ x   −   y ‖ >   4 . The problem is now to plan a collision-free motion for our   m  unit-disc robots such that each of them starts at a configuration in   S   and ends at a configuration in   T   . Since the robots are indistinguishable (or:   unlabeled ), it does not matter which robot ends up at which target configuration. Formally, we wish to find paths   π i   :   [0 ,   1]   →   F , for   1   6   i   6   m , such that   π i (0) =   s i   and   ⋃ m i =1   π i (1) =   T   . Additionally, we require that the robots do not collide with each other: for every   1   6   i   6   =   j   6   m   and every   ξ   ∈   (0 ,   1) , we require  D 1 ( π i ( ξ ))   ∩ D 1 ( π j   ( ξ )) =   ∅ . Note that the requirement that the robots do not collide with the obstacle space   O   is implied by the paths   π i   being inside the free space   F . III. B ASIC PROPERTIES OF THE FREE SPACE  Recall that the free space   F ⊂ W   is the set of configurations at which a robot does not collide with the obstacle space. The free space may consist of multiple connected components. We denote these components by   F 1 , . . . , F q   , where   q   is the total number of components. For any   i   ∈ { 1 ,   2 , ..., q } , we let  S i   4  =   S   ∩   F i   and   T i   4  =   T   ∩   F i . We assume from now on that  | S i | =   | T i |   for all   1   6   i   6   q —if this is not the case, then the problem instance obviously has no solution—and we define  m i   4  =   | S i | =   | T i |   to be the number of robots in   F i . Before we proceed, we need one more piece of notation. For any   x   ∈ W , we define   obs( x ) , the   obstacle set   of   x , as  obs( x )   4  =   { y   ∈ O   :   ‖ x   −   y ‖ <   1 } . In other words,   obs( x )  contains the points in the obstacle space overlapping with  D 1 ( x ) . Note that   obs( x ) =   ∅   for   x   ∈ F .
3  In the remainder of this section we prove several crucial properties of the free space, which will allow us to transform our problem to a discrete pebble problem. We start with some properties of individual components   F i , and then consider the interaction between robots in different components.  A. Properties of a single connected component of   F  We start with a simple observation, for which we provide a proof for completeness.  Lemma 1.   Each component   F i   is simply connected. Proof:   Suppose for a contradiction that   F i   contains a hole. Then   Compl( F )   4  =   R 2   \ F , the complement of the free space, has multiple connected components. One of these is   C O   , the unbounded component containing   O . Let   C   be another component of   Compl( F ) , and let   x   ∈   C . Since   x   6   ∈ F , there is a point   y   ∈ O   with   ‖ x − y ‖ <   1 . But then   ‖ x ′   − y ‖ <   1   for any point   x ′   on the segment   xy , which implies   xy   ⊂   Compl( F )  and thus contradicts that   C   and   C O   are different components. Now consider any   x   in   R 2 . Recall that   D 2 ( x )   denotes the collision disc of   x , that is,   D 2 ( x )   is the set of all configurations  y   for which another robot placed at   y   collides with a robot at   x . We now define   D ∗ ( x )   to be the part of   D 2 ( x )   that is in the same free-space component as   x , that is,   D ∗ ( x )   4  =   D 2 ( x )   ∩   F i  where   F i   is the free-space component such that   x   ∈   F i . The following three lemmas constitute the theoretical basis on which the correctness and efficiency of our algorithm relies.  Lemma 2.   For any   x   ∈ F , the set   D ∗ ( x )   is connected. Proof:   Assume for a contradiction that   D ∗ ( x )   is not connected. Let   F i   be the free-space component containing   x . Since by definition   x   ∈   D ∗ ( x ) , we can find some   y   ∈   D ∗ ( x )  that is in a different connected component of   D ∗ ( x )   from   x . Since   y   ∈   D ∗ ( x )   ⊂ D 2 ( x ) , the distance between   x   and   y   is at most   2 . Hence, any point on the line segment   xy   is within a distance of   1   of either   x   or   y . Since   x, y   ∈   F i , we know that  xy   ⊂ W , otherwise either   x   or   y   would not be in   F . We also know that   xy   6   ⊂   F i , since otherwise   x   and   y   would not be in different connected components of   D ∗ ( x ) . Because   x, y   ∈   F i , by definition there exists a simple path   π   ⊂   F i   from   x   to  y . Since the workspace is a polygon with finite description complexity, we may assume that   π   has finite complexity as well, which implies that   π   ∩   xy   is composed of finitely many isolated points and closed segments. See Figure 1 (a) for an illustration. We now define   x ′ , y ′   as the points on   π   ∩   xy   ⊂   D ∗ ( x )   such that   x ′ , y ′   are in different connected components of   D ∗ ( x )   and  ‖ x ′   −   y ′ ‖   is minimized given the first condition. Let   π ′   be the subpath of   π   joining   x ′   to   y ′ . Notice that   π   ∩   x ′ y ′   =   { x ′ , y ′ } . Indeed, if there exists a point   z   ∈   π   ∩   Int( x ′ y ′ ) , then   z   must be in a different connected component of   D ∗ ( x )   than either  x ′   or   y ′ , and   ‖ x ′   −   y ′ ‖   would not be the minimum. Since   π  is a simple path, this means that   λ   4  =   π ′   ∪   x ′ y ′   is a simple closed curve. The area enclosed by   λ   (including   λ ) will be referred to as   A . We note that   λ   ⊂ W   since   π ′   ⊂ F ⊂ W  and   x ′ y ′   ⊂   xy   ⊂ W . This immediately implies that   A   ⊂ W , since   W   is a simple polygon. Let   A ∗   4  =   A \F . We claim that   A ∗   ⊂   Int( D 2 ( x )) , which implies that there exists a path in   F i   from   x ′   to   y ′   that goes along   ∂ ( A ∗ )   and is fully contained in   D 2 ( x ) . But this contradicts that   x ′   and   y ′   are in different components of   D ∗ ( x )  and, hence, proves the lemma. It thus remains to prove the claim that   A ∗   ⊂   Int( D 2 ( x )) . Note that for any point   z   ∈   A ∗   and any   w   ∈   obs( z )   we have   zw   ∩   π ′   =   ∅ , since   π ′   ⊂ F . Furthermore, for any   v   ∈  π ′   we have   ‖ w   −   v ‖ >   1 , and as   x ′ , y ′   ∈   π ′   it follows that  ‖ w   −   x ′ ‖ >   1 ,   ‖ w   −   y ′ ‖ >   1 . Assume without loss of generality that   x ′ y ′   is vertical and that locally   A   lies to the right of   x ′ y ′ , as in Figure 1 (a). Let   K   be the circle of radius   1   that passes through   x ′   and   y ′ , and whose center lies to the left of   x ′ y ′ — such a circle always exists since   ‖ x ′   −   y ′ ‖ 6   ‖ x   −   y ‖ 6   2 . (If   ‖ x ′   −   y ′ ‖ = 2   then the center of the circle lies on   x ′ y ′ .) Let   ζ   be the arc of this circle lying to the right of   x ′ y ′ ; note that this is the shorter of the two arcs joining   x ′   and   y ′   if they are of different lengths. Then   A ∗   is a contained entirely within the area enclosed by   ζ   and   x ′ y ′ . Furthermore,   A ∗   ⊂  Int( A )   ∪   Int( x ′ y ′ )   since   π ′   ⊂ F . Therefore, since   x ′ y ′   is a subsegment of   xy   and   ζ   cannot cross   ∂ ( D 2 ( x )) , it follows that  A ∗   ⊂   (Int( A )   ∪   Int( x ′ y ′ ))   ∩   Int( D 2 ( x ))   ⊂   Int( D 2 ( x )) ,  which finishes the proof of the lemma.  B. Interference between different connected components of   F .  Let   F i , F j   be two distinct components of   F , and let   x   ∈   F i  be such that   D 2 ( x )   ∩   F j   6   =   ∅ . We then call   x   an   interference configuration from   F i   to   F j   , and define the   interference set from   F i   to   F j   as   I ( i,j )   4  =   { x   ∈   F i   :   D 2 ( x )   ∩   F j   6   =   ∅} . We also define the   mutual interference set   of   F i , F j   as   I { i,j }   4  =  I ( i,j )   ∪   I ( j,i ) . Intuitively, an interference configuration from   F i  to   F j   is a configuration for a robot in   F i   which could block a path in   F j   , and the interference set is the set of all such points. The mutual interference set of   F i , F j   is the set of all single-robot configurations in either component which might block a valid single-robot path in the other component.  Lemma 3.   For any mutual interference set   I { i,j }   and any two configurations   x 1 , x 2   ∈   I { i,j }   we have   D 2 ( x 1 )   ∩ D 2 ( x 2 )   6   =   ∅ . Proof:   The proof is similar in spirit to the proof of Lemma 2 albeit slightly more involved. Assume for a con- tradiction that   x 1 , x 2   ∈   I { i,j }   and   D 2 ( x 1 )   ∩ D 2 ( x 2 ) =   ∅ . By definition there exist   y 1   ∈ D 2 ( x 1 )   and   y 2   ∈ D 2 ( x 2 )   such that each pair   { x 1 , y 1 } ,   { x 2 , y 2 }   contains one point in   F i   and one point in   F j   . As shown in the proof for Lemma 2, the segments   x 1 y 1 , x 2 y 2   are entirely contained in   W . We may assume that   x 1 y 1   does not cross   x 2 y 2 , since if it did the crossing point would be in   D 2 ( x 1 )   ∩ D 2 ( x 2 )   and we would be done. Therefore, there exists a simple closed curve   λ   ⊂ W  composed of the union of two simple curves   π i , π j   and two line segments   ` 1 , ` 2   such that   π i   ⊂   F i   and   π j   ⊂   F j   , and  ` 1   ⊂   x 1 y 1 , ` 2   ⊂   x 2 y 2 . Note that both   ` 1   and   ` 2   have one endpoint in   F i   and the other in   F j   ; see Figure 1 (b) for an illustration. The end points of   ` 1   consist of   x ′  1 , y ′  1 , such that  x 1 , x ′  1   and   y 1 , y ′  1   belong to the same connected components, and minimize the distance   ‖ x ′  1   −   y ′  1 ‖   ( ` 2   is similarly defined).
4  We refer to the region enclosed by   λ   (including   λ ) as   A . Because   λ   ⊂ W   and   W   is a simple polygon, we know that  A   ⊂ W . Furthermore, since   π i , π j   ⊂ F , for any   x   ∈   Int( A )  and   y   ∈   obs( x )   (by definition,   y   ∈   R 2 \W   so   y   6   ∈   A ; thus,  xy   ∩   λ   6   =   ∅ ), we know that   xy   ∩   π i   =   xy   ∩   π j   =   ∅ . Thus,  xy   ∩   Int( ` 1 )   6   =   ∅   or   xy   ∩   Int( ` 2 )   6   =   ∅ , or both. Let   A ∗   4  =   A \F  and denote by   A ∗  1   the set of configurations   x   ∈   A ∗   for which there exists   y   ∈   obs( x )   such that   xy   ∩   Int( ` 1 )   6   =   ∅ ; the set   A ∗  2  is defined in a similar manner, only that now   xy   ∩ Int( ` 2 )   6   =   ∅ . Note that   A ∗   =   A ∗  1   ∪   A ∗  2 . We claim that   A ∗  1   ∩   A ∗  2   6   =   ∅ . Indeed, if   A ∗  1   ∩   A ∗  2   =   ∅   then there is a path from   x 1   to   y 1   along   ∂ ( A ∗  1 )   that stays in   A   \   A ∗  and, hence, stays in   F , which would contradict that   x 1   ∈   F i  and   y 1   ∈   F j   for   i   6   =   j . Thus, there exists a point   x ∗   ∈   A ∗  1   ∩ A ∗  2 . We define the unit circles   K 1 , K 2   whose boundaries lie on the endpoints of   ` 1 , ` 2   respectively, and whose centers are located π ′  y  y ′  x  x ′  A  ζ  K  A ∗  D 2 ( x )  (a) x 1  y 1  x 2  y 2  x ∗   ` 2 ` 1  D 2 ( x 1 )   D 2 ( x 2 )  A  K 1   K 2  π i  π j  (b) Fig. 1.   (a) An illustration of Lemma 2 . The disc   D 2 ( x )   is drawn in green. The closed curve   λ , which consists of the curve   π ′   and the straight-line   x ′ y ′ , is drawn in blue, and   A   represents the area that is bounded by   λ . The disc   K  of radius   1   that touches   x ′ , y ′   is drawn in pink. Note that the area   A ∗ , which is drawn in red, is contained in   A . The dashed black lines represent   π   \ π ′ . (b) An illustration of Lemma 3, and in particular, the case where   A ∗  1   ∩   A ∗  2   6   =   ∅ . For simplicity of presentation, we assume that   ` 1   =   x 1 y 1   and   ` 2   =   x 2 y 2 .  outside   A . Thus, we have   A ∗  1   ⊂   K 1   and   A ∗  2   ⊂   K 2 . Hence,  x ∗   ∈   K 1   ∩   K 2 , which implies   x ∗   ∈ D 2 ( x 1 )   ∩ D 2 ( x 2 ) , so  D 2 ( x 1 )   ∩ D 2 ( x 2 )   6   =   ∅ , contradicting our initial assumption. The next lemma is a generalization of the previous one. Intuitively, instead of considering a cycle of length 2 among interacting free-space components, we now consider larger cycles.  Lemma 4.   Let   { φ (1) , φ (2) , ..., φ ( h ) } ⊂ { 1 ,   2 , ..., q } , and let  x 1 , x 2 , ..., x h   be points such that for all   i ,   x i   ∈   I { φ ( i ) ,φ ( i +1) } , where   φ ( h   + 1)   ≡   φ (1) . (Thus the list is circular with respect to its index). Then there exists some   i   6   =   j   such that   D 2 ( x i )   ∩ D 2 ( x j   )   6   =   ∅ . Proof:   This   can   be   proved   in   a   manner   completely analogous to the proof of Lemma 3; we will outline the proof here. We assume for a contradiction that   D 2 ( x i )   ∩ D 2 ( x j   ) =   ∅  for all   i   6   =   j . We can argue that we can construct a simple closed curve   λ   ⊂ W   passing through   F φ (1) , F φ (2) , ..., F φ ( h )  (in that order), which is composed of simple closed curves  π i   ⊂   F φ ( i )   and line segments   ` i   ⊂ W   with endpoints in   F φ ( i )  and   F φ ( i +1) . We then consider the area   A   enclosed by   λ   and note that   A   ⊂ W . Let   A ∗   4  =   A \F . If there exists some simple curve   π ∗   ⊂   A ∗   connecting   ` i   to   ` j   for some   i   6   =   j , we can show that there exists some   k   such that   D 2 ( x i )   ∩ D 2 ( x k )   6   =   ∅ , contradicting our assumption. Therefore no such   π ∗   exists for any   i   6   =   j . But this means that there exists some simple path   π ′   ⊂   A   ∩ F   which joins   π i   and   π j   for some   i   6   =   j , which contradicts the fact that   π i   and   π j   belong to different components of   F . IV. A LGORITHM FOR A SINGLE COMPONENT  In this section we consider a single component   F i   of   F . We present an algorithm that solves the problem within   F i , ignoring the possibility that robots in   F i   might collide with robots in other components   F j   . In the next section we will show   how   to   avoid   such   collisions   without   changing   the motion plans within the individual components. As before we set   S i   4  =   S   ∩   F i   and   T i   4  =   T   ∩   F i , and assume   | S i | =   | T i | .  A. The motion graph  The   motion graph   G i   of   F i   is a graph whose vertices repre- sent start or target configurations, and whose edges represent “adjacencies” between these configurations, as defined more precisely below. Recall that for any   x   ∈   F i   we defined   D ∗ ( x )   4  =   D 2 ( x )   ∩   F i  as the part of the collision disc of   x   inside   F i , and re- call from Lemma 2 that   D ∗ ( x )   is connected. Moreover, for any two distinct configurations   x 1 , x 2   ∈   S i   ∪   T i   we have  D ∗ ( x 1 )   ∩   D ∗ ( x 2 ) =   ∅ , because   D 2 ( x 1 )   ∩ D 2 ( x 2 ) =   ∅   by the assumption that the start and target positions are well- separated. The vertices of our motion graph   G i   correspond to the start and target configurations in   S i   ∪ T i . From now on, and with a slight abuse of notation we will not distinguish between configurations in   S i ∪ T i   and their corresponding vertices in   G i . Now consider   F   ∗  i  4  =   F i   \   ⋃  x ∈ S i ∪ T i   D ∗ ( x ) , the complement of the collision discs of the given start and target configura- tions in   F i . This complement consists of several connected
5  components, which we denote by   F   1  i   , F   2  i   , . . . . If the motion graph   G i   contains an edge   ( x 1 , x 2 )   then there is a component  F   ` i   that is adjacent to both   D ∗ ( x 1 )   and   D ∗ ( x 2 ) . In other words, two configurations   x 1   and   x 2   are connected in   G i  if there is a path from   x 1   to   x 2   that stays inside   F i   and does not cross the collision disc of any other configuration  x 3   ∈   S i   ∪   T i . Figure 2 illustrates the definition of   G i . The following observation summarizes the main property of the motion graph.  Observation 1.   Suppose all robots in   F i   are located at a start or target configuration in   S i   ∪   T i , and let   ( x 1 , x 2 )   be any edge in   G i . Then a robot located at   x 1   can move to   x 2   without colliding with any of the other robots.  Remark.   We could also work with the dual graph of the partitioning of   F i   into cells induced by the collision discs. This dual graph would, in addition to vertices representing start and target configurations, also have vertices for the regionss   F   ` i   . For the pebble-motion problem discussed below it is easier to work with the graph as we defined it. This graph may have many more edges, but in the implementation of our algorithm described in Section VI we avoid computing it explicitly.  B. The unlabeled pebble-motion problem  Using the motion graph   G i   we can view the motion- planning problem within   F i   as a pebble-motion problem. (A similar approach was taken in [19], where a sampling-based algorithm for multi-robot motion planning produces multiple pebble problems by random sampling of the configuration space.) To this end we represent a robot located at config- uration   x   ∈   S i   ∪   T i   by a   pebble   on the corresponding vertex in   G i . The pebbles are indistinguishable, like the robots, and they can move along the edges of the graph. At the start of the pebble-motion problem for a graph with vertex set   S i   ∪ T i , with  | S i | =   | T i | , there is a pebble on every vertex   x   ∈   S i . The goal is to move the pebbles such that each pebble ends up in vertex in   T i , under the following conditions: (1) no two pebbles may occupy the same vertex at the same time, and (2) pebbles can only halt at vertices, and (3) at most one pebble may move (that is, be in transit along an edge) at any given time. We call this problem the   unlabeled pebble-motion problem . The following lemma follows immediately from Observation 1. F   3  s 1  s 3  s 2  s 4  t 1  t 2  t 3  t 4  F   2  F   1  (a) G  s 3  s 2  t 4  t 1  s 4  t 2  t 3  s 1   (b) Fig. 2.   (a) A partition of a maximal connected component   F   . The start and target positions consist of the elements   S ′   =   { s 1 , s 2 , s 3 , s 4 } , T   ′   =  { t 1 , t 2 , t 3 , t 4 } , respectively, where the areas   D ∗ ( s )   for   s   ∈   S ′   are drawn in green and   D ∗ ( t )   for   t   ∈   T   ′   are drawn in purple.   F   ∗   consists of the parts  F   1 , F   2 , F   3 . (b) A motion graph of   F   .  Lemma 5.   Any solution to the unlabeled pebble-motion prob- lem on   G i   can be translated into a valid collision-free motion plan for the robots in   F i .  Kornhauser [25, Section 3, first lemma] proved that the unlabeled pebble-motion problem is, in fact, always solvable, and he gave an algorithm to find a solution. Since he did not analyze the running time of his algorithm, we sketch the solution in the proof of the lemma below.  Lemma 6. [25]   For any graph   G   with vertex set   S   ∪   T   where  | S | =   | T   | , there exists a solution to the unlabeled pebble- motion problem. Moreover, a solution can be found in   O ( | S | 2 )  time. Proof:   Let   T G   be a spanning tree of   G . The algorithm performs   O ( | S | )   phases . In each phase, one or more pebbles may be moved and one leaf will be removed from   T G , possibly with a pebble on it. After the phase ends, the algorithm continues with the next phase on the modified tree   T G , until all pebbles have been removed and the problem has been solved. A phase proceeds as follows. If there are leaves   v   that are target vertices then we select such a leaf   v . If   v   does not yet contain a pebble, we find a pebble closest to   v   in   T G —this can be done by a simple breadth-first search—and move it to   v   along the shortest path in   G . Note that the vertices on the shortest path cannot contain other pebbles, since we took a closest pebble. We now remove the leaf   v , together with the pebble occupying it, and end the phase. If all leaves in   T G   are start vertices, then let   v   be such a leaf. If   v   is not occupied by a pebble it can be removed from  T G , and the phase ends. Otherwise a pebble resides in   v , which we move away, as follows. We find the closest unoccupied vertex   w   to   v   of   T G   and move all pebbles on this shortest path (including the pebble on   v ) one step closer to   w , in order of decreasing distance from   w . After we evacuated   v   we remove it from   T G   to end the phase. The algorithm produces paths of total length   O ( | S | 2 ) , and it can easily be implemented to run in   O ( | S | 2 )   time. In some cases   Ω( | S | 2 )   moves are required, e.g., when   G   is a single path with all start positions in the first half of the path and all target positions in the second half.  Lemma 7.   Suppose we have an instance of our multi-robot path planning problem where   | S i | =   | T i |   for every component  F i   of the free space   F . Then for each   F i   there exists a motion plan   Π i   that brings the robots in   F i   from   S i   to   T i , such that they do not collide with the obstacle space nor with the other robots in   F i .  V. C OMBINING SINGLE - COMPONENT PLANS  We now consider possible interactions between robots con- tained in different components   F i   and   F j   of   F . As before, we assume that   | S i | =   | T i |   for all   i . We will show that there exists a permutation   σ   :   { 1 ,   2 , ..., ` } → { 1 ,   2 , ..., ` }   such that we can independently execute the single-component motion plans for each component   F i   as long as we do so in the order  F σ (1) , F σ (2) , ..., F σ ( ` ) . To obtain this order, we define a directed graph representing the structure of   F , which we call the   directed-interference
6  forest   G   = ( V ,   E ) , where the nodes in   V   correspond to the components   F i . We add the directed edge   ( F i , F j   )   to   E   if either there exists a start position   s   ∈   S   such that   s   ∈   I ( i,j ) , or there exists a target position   t   ∈   T   such that   t   ∈   I ( j,i ) . For any   i   ∈ { 1 ,   2 , ..., ` } , we additionally define   N   + ( i )   to be the set of indices of the vertices in the out-neighborhood of   v i ; similarly,   N   − ( i )   is defined as the set of indices of the vertices in the in-neighborhood of   v i . Note that by Lemma 3 and since   S, T   are well separated, we cannot have more than one start or target position in   I { i,j } . This implies that   E   cannot contain both   ( v i , v j   )   and   ( v j   , v i ) . Lemma 4 and the well-separatedness condition additionally imply that   G   cannot have an undirected cycle. Thus,   G   is a directed forest. We now produce the desired ordering using   G . Consider  F i   ∈ V , and suppose that for all   j   ∈   N   + ( i ) , every robot in   F j  is at a start position, and for all   j   ∈   N   − ( i ) , every robot in   F j  is at a target position. Additionally, suppose that for all   j   6   ∈  N   + ( i ) ∪ N   − ( i ) , every robot in   F j   is at a start or target position. Then, by the definition of   G , no robot is at a configuration in  I { i,j }   for any   j   6   =   i ; thus any motion plan for the robots in  F i , such as the one described in Section IV, can be carried out without being blocked by the robots not in   F i . Hence, if we have an ordering   σ   :   { 1 ,   2 , ..., ` } → { 1 ,   2 , ..., ` }   such that for all (directed) edges   ( v i , v j   )   ∈ E ,   σ − 1 ( i )   < σ − 1 ( j ) , where  σ − 1   is the inverse permutation of   σ , then we can execute the motion plans for the robots in   F σ (1) , F σ (2) , ..., F σ ( ` )   in that order. Since   G   is a directed forest such an ordering can be produced using topological sorting on the vertices of   G . Thus, combining this result with Lemma 7 we obtain:  Theorem 8.   Let there be a collection of   m   unlabeled unit-disc robots in a simple polygonal workspace   W ⊂   R 2 , with start and target configurations   S, T   that are well-separated. Then if for every maximal connected component   F i   of   F   (where   F  is the free space for a single unit-disc robot in   W )   | S   ∩   F i | =  | T   ∩   F i | , there exists a collision-free motion plan for these robots starting at   S   which terminates with every position of  T   occupied by a robot.  VI. A LGORITHMIC DETAILS  In this section we fill in a few missing details in the de- scription of our algorithm. Specifically, we present an efficient method for generating motion graphs and describe a technique for generating configuration-space paths that correspond to edges in the motion graphs. We also consider the complexity of the various subsets of   F   used throughout the algorithm.  A. Partitioning   F  We analyze the combinatorial complexity of   F ∗   4  =   F \ ⋃  x ∈ S ∪ T   D ∗ ( x )   and   D   4  =   ⋃  x ∈ S ∪ T   D ∗ ( x ) .  Lemma 9.   The combinatorial complexity of   F ∗   is   O ( m   +   n ) . Proof:   We decompose the complement of the workspace polygon into   O ( n )   trapezoids—this is doable by standard vertical decomposition. We define a set   X , which consists of the trapezoids, and in addition a collection of   O ( m )   unit discs that are centered at the start and target positions. We now observe that the regions in   X   are pairwise interior disjoint (and convex). Hence, it is known [29] that the complexity of the union of the regions in   X , each Minkowski-summed with a unit disc, is linear in the number of regions plus the sum of the complexities of the original regions. As the result of the Minkowski sum operation of   X   with a unit disc is the the area  F ∗ , we conclude that that the complexity of   F ∗   is   O ( m   +   n ) . Note that this upper bound still holds if we consider instead of   F ∗   the union of   F   ∗  i  4  =   F i   \   ⋃  x ∈ S i ∪ T i   D ∗ ( x ) , for all   1   6  i   6   q .  Lemma   10.   The   combinatorial   complexity   of   D   4  = ⋃  x ∈ S ∪ T   D ∗ ( x ) , is   O ( m   +   n ) . Proof:   Denote by   d   4  =   { d 1 , d 2 , . . . }   the segments that define   ∂ ( D ) . Additionally, denote by   f   4  =   { f 1 , f 2 , . . . }   and  f   ∗   4  =   { f   ∗  1   , f   ∗  2   , . . . }   the segments that define   ∂ ( F ) , ∂ ( F ∗ ) , respectively. Note that   ∂ ( D )   consists of segments that are ele- ments of   f, f   ∗   and in addition segments that are subsegments of the elements of   f   , denoted by   f   ′   4  =   { f   ′  1 , f   ′  2 , . . . } . Obviously the complexity of the segments of   d , that are elements of   f   or  f   ∗ , is bounded by   O ( m + n ) . It might happen that the segments of   f   will be split into many subsegments in   f   ′ . However, notice that whenever a segment of   f   is split the endpoints of each subsegment consist of vertices of   ∂ ( F )   or   ∂ ( F ∗ ) . Moreover, exactly two segments in   ∂ ( D )   share an endpoint. Thus, the complexity of   D   is   O ( m   +   n ) .  B. Generating motion graphs  We consider a specific component   F   of   F   and construct its motion graph   G . Denote   F   ∗   4  =   F   \   ⋃  x ∈ ( S ∪ T   ) ∩ F   D ∗ ( x ) . Note that by the analysis in Section V we can ignore the influence of   D 2 ( x )   on connected components in   F   that do not contain   x . We assume that   F   ∗   breaks into   k   maximal connected components   F   1 , . . . , F   k . The construction of   G , along with the paths in   F   that correspond to the edges of   G , is carried out in two steps. First, for every   F   i   we generate the portion of   G , denoted by   G i , whose vertices represent start and target positions that touch the boundary of   F   i . Then, we connect between the various parts of   G . We consider a specific connected component   F   i   of   F   ∗  and describe how the respective portion of the motion graph, namely   G i , is generated. We split the start and target positions that share a boundary with   F   i   into two subsets:   B i   are those positions for which the collision disc intersects the boundary of   F   and   H i   are those positions for which the collision disc floats inside   F   . See Figure 3. We first handle positions in   B i . Consider the outer boundary   Γ i   of   F   i   \   ⋃  x ∈ S ∪ T   D ∗ ( x ) . We argue that each   x   ∈   B i   can contribute exactly one piece to   Γ i .  Lemma 11.   If   x   ∈   B i   then   ∂ ( D 2 ( x ))   ∩   ∂ ( F   i )   consists of a single component. Proof:   By contradiction, assume that the intersection con- sists of two maximal connected components. Denote by   y, y ′  two configurations on the two components. As   F   i   consists of a single connected component of   F   there exists a path   π yy ′   ⊂   F
7  from   y   to   y ′ . Additionally, as   y, y ′ , x   belong to the same connected component of   F   there exist two paths— π xy   from   x  to   y   and   π xy ′   from   x   to   y ′ —that lie entirely in   D ∗ ( x ) . Thus, the area that is bounded by the three paths   π yy ′   , π xy   , π xy ′  contains a patch of forbidden space, which contradicts the fact the our workspace is a simple polygon. For every   x   ∈   B i   we arbitrarily select a representative point   β i ( x )   ∈   ∂ ( D 2 ( x ))   ∩   F   i . We order the points   β i ( x )  clockwise around   Γ i , and store them in a circular list   L i . We now incorporate the remaining start and target positions  H i , namely those positions   x   for which   D 2 ( x )   ∩   ∂ ( F   ) =   ∅ . Each position in   H i   will be connected either to   Γ i   or to the boundary of a collision disc of another position in   H i   as follows. For each   x   ∈   H i   we shoot a vertical ray upwards until it hits   ∂ ( F   i ) . Denote the point where the ray hits   ∂ ( F   i )  by   c . If   c   ∈   ∂ ( D 2 ( x ′ ))   for some   x ′   ∈   H i , x ′   6   =   x   then an edge between   x   and   x ′   is added to   G i . Otherwise, we let  β i ( x )   4  =   c   and insert it into the circular list   L i   representing the points   β i ( x )   along   Γ i   collected so far. After all positions in   H i   have been handled in this manner, for each pair of consecutive points   β i ( x ′ ) , β i ( x ′′ )   in   L i   (along   Γ i ) we add an edge in   G i   between the vertices   x ′   and   x ′′ . (Notice that some of the positions   x   whose   β i ( x )   appear in   L i   belong to   H i ; for example   s 3   in Figure 3.) Finally, the connection between portions of the motion graph   that represent different parts of   F   ∗   is achieved through positions shared between two sets  B i , B j   , for   i   6   =   j .  C. Transforming graph edges into paths in the free space  There are three different types of transformations depending on how the edge was created. Let   ( x, x ′ )   be an edge in   G i . Consider Figure 3 for an illustration. (i) If both   x   and   x ′   belong to   H i   (see   ( s 4 , s 3 )   in the figure) then the path simply consists of the two straight-line segments   xc   and   cx ′ . For the remaining two cases we note that if either vertex, say   x , is in   B i , then part of the path is a simple curve connecting   x   to   β i ( x )   within  D ∗ ( x )   (see the red curves from   s 1   and   t 2   in the figure). We denote this curve by   δ x . (ii)   x, x ′   ∈   B i   and the points   β i ( x )  and   β i ( x ′ )   are consecutive along   Γ i   (see   ( t 1 , t 2 )   in the figure). The path corresponding to the edge   ( x, x ′ )   in this case is a concatenation of three sub-paths:   δ x , the portion of   Γ i   between  β i ( x )   and   β i ( x ′ )   (not passing though the boundary of any other collision disc), and   δ x ′   . (iii)   x   ∈   H i   and   x ′   ∈   B i   (see  ( s 3 , s 2 )   in the figure). The path is again a concatenation of three paths: the line segment   xβ i ( x ) , the portion of   Γ i   between  β i ( x )   and   β i ( x ′ )   (not passing though the boundary of any other collision disc), and   δ x ′   . Notice that for all path types above if a robot   r   moves from   x   to   x ′ ,   x ′   is not occupied, and all other robots occupy positions only at   S   ∪   T   \ { x, x ′ } ,   r   will not collide with any other robot during the motion.  D. Complexity Analysis  We   provide   complexity   analysis   of   our   algorithm   and show that a solution to the problem can be produced within  O   ( ( m   +   n ) log( m   +   n ) +   mn   +   m 2 )   operations, which can be rewritten as   O   ( n   log   n   +   mn   +   m 2 ) . β 3 ( t 2 )  β 3 ( s 3 )  s 3  s 2  s 4  t 1  t 2  t 4  F   3  β 3 ( s 1 )  (a) G 3  s 3  s 2  t 4  t 1  s 4  t 2   (b) Fig. 3.   (a) An illustration of a component   F   3   of   F   ∗   and the structures used for generating the relevant portion of the motion graph. The boundary positions of   F   3   consist of   B 3   :=   { s 2 , t 1 , t 2 , t 4 } , while the hole positions consist of   H 3   :=   { s 3 , s 4 } . For every   x   ∈   H 3   its boundary representative  β 3 ( x )   is illustrated as a large black dot. A path between   t 1   and   t 2   is illustrated in red. (b) The motion graph   G 3   induced by   F   3 .  Recall that the pebble problem solver (Section IV) operates in   O ( m )   phases, where in each phase a leaf node is removed from the spanning tree of   G . We show, using Lemma 9 and Lemma 10, that each phase can be transformed into a set of movements for the robots whose combinatorial complexity is  O ( m   +   n ) . The crucial observation is that in one phase each edge of the motion graph is used at most once. Thus the set of robot movements in one phase is bounded by the complexity of the movements corresponding to all the edges in the graph together. These comprise   O ( m )   line segments, portions of the boundaries   Γ i   (whose complexity is   O ( m   +   n )   by Lemma 9), and the paths   δ x   inside the   D ∗ ( x ) ′ s   (whose complexity is  O ( m   +   n )   by Lemma 10). A path of the latter type,   δ x , might be traversed twice: once for reaching   x   and once for leaving  x . However asymptotically all the movements together have complexity   O ( m   +   n ) . We note that the cost of generating   F , along with its partitions   F ∗   and   D , is bounded by   O   (( m   +   n ) log( m   +   n )) , due to [29]. We also note that deciding whether a solution exists for a certain collection of start and target positions can be carried out in   O (( m + n ) log   n )   as follows. We first compute  F   in   O ( n   log   n )   time, and within the same time preprocess it for efficient point location. Then we query the resulting structure with the   m   points in   S ∪ T   , in   O (log   n )   time each, and verify that in every component   F i   of   F   it holds that   | S i | =   | T i | . Thus, we have the following theorem.  Theorem 12.   Let   W   be a simple polygon with   n   vertices and let   S   =   { s 1 , . . . , s m } , T   =   { t 1 , . . . , t m }   be two sets of   m  points in   W . Additionally, assume that for every two distinct element   x, x ′   of   S   ∪   T   it holds that   ‖ x   −   x ′ ‖ >   4 . Then, given  m   unlabeled unit disc robots, our algorithm can determine whether a path moving the   m   robots from   S   to   T   exists in  O   (( m   +   n ) log   n )   time. If a path exists the algorithm finds it in   O   ( n   log   n   +   mn   +   m 2 )   time.  VII. S EPARATION AND SOLVABILITY  Our results from the previous section imply that a separation distance of   4   ensures that the problem always has a solution,
8  assuming that each connected component contains the same number of start and target positions. However, for smaller separation values this does not have to be the case. We define a magnitude   λ   to be the minimum separation between start and target positions of unlabeled discs in a simple polygon, that guarantees that a solution always exists assuming that each connected component contains the same number of start and target positions. Our work in the previous sections shows that   λ   6   4 . The following proposition provides a lower bound for the value of   λ .  Proposition 13.   λ   >   4 √ 2   −   2( ≈   3 . 646) . Proof:   We describe a concrete example where the value of  λ   has to be greater than   4 √ 2   −   2   to guarantee solvability. See Figure 4. The two robots   r 1 , r 2 , placed at   s 1 , s 2 , respectively, need to leave through the corridor of width   2   located below their initial positions in order to reach   t 1 , t 2 . Denote the separation between the start positions by   2 +   ρ . We wish to find the maximal value   ρ   for which the problem does not have a solution. It is clear that the two robots cannot enter the corridor simultaneously. Therefore, if a solution exists there also exists one where   r 2   stays put in   s 2   until   r 1   is well down the corridor. We describe a path of   r 1   in which it maintains a maximal distance from   s 2 : first   r 1   has to slide along the edge   AB , when arriving at   B   it revolves around it and then slides down along the other edge connected to   B . This path has a circular arc which is induced by the rotation about   B   (depicted by the red arrow). The dashed red arc depicts the trace of the boundary of   r 1   throughout this motion. Denote by   M   the tangent point between   r 2   at   s 2   and the edge   CD . Note that the robots would collide when   r 1   is rotated around   B   in case that   ‖ B   − s 2 ‖ <   3 . Thus, it must be that   ‖ B   −  M   ‖ >   2 √ 2 . As the segment   AD   consists of the subsegments  AB, BM, M D , it follows that  4 +   ρ   =   ‖ A   −   D ‖  =   ‖ A   −   B ‖ + ‖ B   −   M   ‖ + ‖ M   −   D ‖  >   1 +   ρ  2 + 2 √ 2 + 1 = 2 + 2 √ 2 +   ρ  2   ,  and we conclude that   ρ   >   4 √ 2   −   4 , and also   λ   >   ρ   + 2 = 4 √ 2   −   2 . VIII. O PEN PROBLEMS AND FUTURE WORK  We have studied a basic variant of the multi-robot motion- planning problem, where the goal is to find collision-free motions that bring a given set of indistinguishable unit discs in a simple polygon to a given set of target positions. Under the condition that the start and target positions are separated from each other by a distance of at least   4 , we developed an algorithm that solves the problem in time polynomial in the complexity of the polygon as well as in the number of discs: quadratic in the number of robots and near-linear in the complexity of the polygon. Our result should be contrasted with the labeled counterpart of the problem, which is   NP -hard [8]. In the   NP -hardness 1 +   ρ/ 2   1 +   ρ/ 2  4 +   ρ  2 +   ρ  B  s 2  M   D A  2   s 1  t 1   t 2  C  Fig. 4.   It follows from our paper that when the start and goal positions are well separated, then there is always a solution when each free-space component has the same number of start and goal positions. However, it is not true when the separation condition is not met. In the given example, the two robots need to leave the through a corridor of width   2   located below their initial positions. This is only possible when   ρ   >   4 √ 2   −   2 , as otherwise the robots will not be able to get to the corridor without colliding with each other. See proof of Proposition 13 for more details.  proof the discs have different radii, however, and there is no restriction on the separation of the start and target position. Thus one of the main open questions resulting from our study is to settle the complexity of the unlabeled problem without this extra separation condition. Very recently, we have made progress in this direction, by showing that the general unlabeled problem is   PSPACE -hard [30]. It should be noted that this proof applies to a slightly different setting that consists of unit-square robots translating amidst polygonal obstacles. A natural question that arises is what happens when the separation of start or target positions is equal to   2 +   ρ , where  0   < ρ <   2 ? Would it be possible to design an algorithm, whose running time is polynomial in   m   and   n , and also depends in some manner on   ρ ? We believe that the work by Alt et al. [31] would be a good starting point for this line of work. Following our discussion in Section VII, it will also be interesting to find the exact threshold above which a problem is always solvable. R EFERENCES  [1] J. T. Schwartz and M. Sharir, “On the piano movers problem: II. General techniques for computing topolog- ical properties of real algebraic manifolds,”   Advances in applied Mathematics , vol. 4, no. 3, pp. 298–351, 1983. [2] ——, “On the piano movers problem: III. Coordinating the motion of several independent bodies,”   International Journal of Robotics Research , vol. 2, no. 3, pp. 46–75, 1983. [3] C.-K. Yap, “Coordinating the motion of several discs,” Courant Institute of Mathematical Sciences, Michigan State University, New York, Tech. Rep., 1984. [4] M. Sharir and S. Sifrony, “Coordinated motion planning for two independent robots,”   Annals of Mathematics and Artificial Intelligence , vol. 3, no. 1, pp. 107–130, 1991.
9  [5] B. Aronov, M. de Berg, A. F. van der Stappen, P. ˇ Svestka, and J. Vleugels, “Motion planning for multiple robots,”  Discrete & Computational Geometry , vol. 22, no. 4, pp. 505–525, 1999. [6] J. van den Berg, J. Snoeyink, M. C. Lin, and D. Manocha, “Centralized path planning for multiple robots: Optimal decoupling into sequential plans,” in   Robotics: Science and Systems (RSS) , 2009. [7] J. E. Hopcroft, J. T. Schwartz, and M. Sharir, “On the complexity of motion planning for multiple indepen- dent objects; PSPACE-hardness of the “Warehouseman’s problem”,”   International Journal of Robotics Research , vol. 3, no. 4, pp. 76–88, 1984. [8] P. G. Spirakis and C.-K. Yap, “Strong NP-hardness of moving many discs,”   Information Processing Letters , vol. 19, no. 1, pp. 55–59, 1984. [9] L. E. Kavraki, P.   ˇ Svestka, J.-C. Latombe, and M. H. Overmars, “Probabilistic roadmaps for path planning in high dimensional configuration spaces,”   IEEE Transac- tions on Robotics and Automation , vol. 12, no. 4, pp. 566–580, 1996. [10] J. J. Kuffner and S. M. Lavalle, “RRT-Connect: An efficient   approach   to   single-query   path   planning,”   in  International Conference on Robotics and Automation (ICRA) , 2000, pp. 995–1001. [11] G. Sanchez and J.-C. Latombe, “Using a PRM planner to compare centralized and decoupled planning for multi- robot systems,” in   International Conference on Robotics and Automation (ICRA) , 2002. [12] S. Hirsch and D. Halperin, “Hybrid motion planning: Coordinating two discs moving among polygonal ob- stacles in the plane,” in   Workshop on the Algorithmic Foundations of Robotics (WAFR) .   Springer, 2002, pp. 239–255. [13] O. Salzman, M. Hemmer, and D. Halperin, “On the power of manifold samples in exploring configuration spaces and the dimensionality of narrow passages,”   to appear, Workshop on the Algorithmic Foundations of Robotics (WAFR) , 2012. [14] K. Solovey, O. Salzman, and D. Halperin, “Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planning,”   CoRR , vol. abs/1305.2889, 2013. [15] P.   ˇ Svestka   and   M.   H.   Overmars,   “Coordinated   path planning for multiple robots,”   Robotics and Autonomous Systems , vol. 23, pp. 125–152, 1998. [16] G. Wagner and H. Choset, “M*: A complete multirobot path planning algorithm with performance bounds,” in  International Conference on Intelligent Robots and Sys- tems (IROS) , 2011, pp. 3260–3267. [17] G.   Wagner,   M.   Kang,   and   H.   Choset,   “Probabilistic path planning for multiple robots with subdimensional expansion,” in   International Conference on Robotics and Automation (ICRA) , 2012, pp. 2886–2892. [18] S.   Kloder   and   S.   Hutchinson,   “Path   planning   for permutation-invariant multi-robot formations,” in   ICRA , 2005, pp. 1797–1802. [19] K. Solovey and D. Halperin, “ k -color multi-robot motion planning,”   International Journal of Robotics Research , 2013, in press (already appeared on-line). [20] M.   Turpin,   N.   Michael,   and   V.   Kumar,   “Concurrent assignment and planning of trajectories for large teams of interchangeable robots,” in   International Conference on Robotics and Automation (ICRA) , 2013, pp. 842–848. [21] S. Bereg, A. Dumitrescu, and J. Pach, “Sliding disks in the plane,”   International Journal of Computational Geometry and Applications , vol. 18, no. 5, pp. 373–387, 2008. [22] A. Dumitrescu and M. Jiang, “On reconfiguration of disks in the plane and related problems,”   Computational Geometry: Theory and Applications , vol. 46, no. 3, pp. 191 – 202, 2013. [23] O. Goldreich, “Shortest move-sequence in the general- ized 15-puzzle is NP-hard,”   Manuscript, Laboratory for Computer Science, MIT , vol. 1, 1984. [24] G. Goraly and R. Hassin, “Multi-color pebble motion on graphs,”   Algorithmica , vol. 58, no. 3, pp. 610–636, 2010. [25] D. Kornhauser, “Coordinating pebble motion on graphs, the diameter of permutation groups, and applications,” M.Sc. Thesis, Department of Electrical Engineering and Computer Scienec, Massachusetts Institute of Technol- ogy, 1984. [26] A. Krontiris, R. Luna, and K. E. Bekris, “From feasibility tests to path planners for multi-agent pathfinding,” in  Symposium on Combinatorial Search , 2013. [27] C.   H.   Papadimitriou,   P.   Raghavan,   M.   Sudan,   and H. Tamaki, “Motion planning on a graph,” in   Foundations of Computer Science , 1994, pp. 511–520. [28] J. Yu and S. M. LaValle, “Distance optimal formation control on graphs with a tight convergence time guaran- tee,” in   IEEE International Conference on Decision and Control , 2012, pp. 4023–4028. [29] K. Kedem, R. Livne, J. Pach, and M. Sharir, “On the union of jordan regions and collision-free translational motion amidst polygonal obstacles,”   Discrete & Compu- tational Geometry , vol. 1, pp. 59–70, 1986. [30] K.   Solovey   and   D.   Halperin,   “PSPACE-hardness   of unlabeled motion planning and variants,”   CoRR , vol. abs/1408.2260, 2014. [31] H.   Alt,   R.   Fleischer,   M.   Kaufmann,   K.   Mehlhorn, S. N ̈ aher, S. Schirra, and C. Uhrig, “Approximate motion planning and the complexity of the boundary of the union of simple geometric figures,”   Algorithmica , vol. 8, no. 1- 6, pp. 391–406, 1992.