Fixed-path coordination

Suppose that each robot ${\cal A}^i$ is constrained to follow a path $\tau_i : [0,1] \rightarrow {\cal C}^i_{free}$, which can be computed using any ordinary motion planning technique. For $m$ robots, an $m$-dimensional state space called a coordination space is defined that schedules the motions of the robots along their paths so that they will not collide [746]. One important feature is that time will only be implicitly represented in the coordination space. An algorithm must compute a path in the coordination space, from which explicit timings can be easily extracted.

For $m$ robots, the coordination space $X$ is defined as the $m$-dimensional unit cube $X = [0,1]^m$. Figure 7.9 depicts an example for which $m = 3$. The $i$th coordinate of $X$ represents the domain, $S_i = [0,1]$, of the path $\tau_i$. Let $s_i$ denote a point in $S_i$ (it is also the $i$th component of $x$). A state, $x \in X$, indicates the configuration of every robot. For each $i$, the configuration $q^i \in {\cal C}^i$ is given by $q^i = \tau_i(s_i)$. At state $(0,\ldots,0) \in X$, every robot is in its initial configuration, ${q^i_{I}}= \tau_i(0)$, and at state $(1,\ldots,1) \in X$, every robot is in its goal configuration, ${q^i_{G}}= \tau_i(1)$. Any continuous path, ${h}: [0,1] \rightarrow X$, for which ${h}(0) = (0,\ldots,0)$ and ${h}(1) = (1,\ldots,1)$, moves the robots to their goal configurations. The path ${h}$ does not even need to be monotonic, in contrast to prioritized planning.

Figure 7.9: The obstacles that arise from coordinating $m$ robots are always cylindrical. The set of all $\frac {1}{2} m (m-1)$ axis-aligned 2D projections completely characterizes ${X_{obs}}$.

One important concern has been neglected so far. What prevents us from designing ${h}$ as a straight-line path between the opposite corners of $[0,1]^m$? We have not yet taken into account the collisions between the robots. This forms an obstacle region ${X_{obs}}$ that must be avoided when designing a path through $X$. Thus, the task is to design ${h}: [0,1] \rightarrow {X_{free}}$, in which ${X_{free}}= X \setminus {X_{obs}}$.

The definition of ${X_{obs}}$ is very similar to (7.8) and (7.10), except that here the state-space dimension is much smaller. Each $q^i$ is replaced by a single parameter. The cylindrical structure, however, is still retained, as shown in Figure 7.9. Each cylinder of ${X_{obs}}$ is

$$X^{ij}_{obs} = \{ (s_1,\ldots,s_m) \in X \;\vert\; {\cal A}^i(\tau_i(s_i)) \cap {\cal A}^j(\tau_j(s_j)) \not = \emptyset \} ,$$ (7.11)

which are combined to yield

$${X_{obs}}= \bigcup_{ij, \;\;i \not = j} X^{ij}_{obs} .$$ (7.12)

Standard motion planning algorithms can be applied to the coordination space because there is no monotonicity requirement on ${h}$. If 1) ${\cal W}= {\mathbb{R}}^2$, 2) $m=2$ (two robots), 3) the obstacles and robots are polygonal, and 4) the paths, $\tau_i$, are piecewise-linear, then ${X_{obs}}$ is a polygonal region in $X$. This enables the methods of Section 6.2, for a polygonal ${\cal C}_{obs}$, to directly apply after the representation of ${X_{obs}}$ is explicitly constructed. For $m > 2$, the multi-dimensional version of vertical cell decomposition given for $m = 3$ in Section 6.3.3 can be applied. For general coordination problems, cylindrical algebraic decomposition or Canny's roadmap algorithm can be applied. For the problem of robots in ${\cal W}= {\mathbb{R}}^2$ that either translate or move along circular paths, a resolution complete planning method based on the exact determination of ${X_{obs}}$ using special collision detection methods is given in [886].

For very challenging coordination problems, sampling-based solutions may yield practical solutions. Perhaps one of the simplest solutions is to place a grid over $X$ and adapt the classical search algorithms, as described in Section 5.4.2 [606,746]. Other possibilities include using the RDTs of Section 5.5 or, if the multiple-query framework is appropriate, then the sampling-based roadmap methods of 5.6 are suitable. Methods for validating the path segments, which were covered in Section 5.3.4, can be adapted without trouble to the case of coordination spaces.

Thus far, the particular speeds of the robots have been neglected. For explanation purposes, consider the case of $m=2$. Moving vertically or horizontally in $X$ holds one robot fixed while the other moves at some maximum speed. Moving diagonally in $X$ moves both robots, and their relative speeds depend on the slope of the path. To carefully regulate these speeds, it may be necessary to reparameterize the paths by distance. In this case each axis of $X$ represents the distance traveled, instead of $[0,1]$.