Cube complex

How is the coordination space represented when there are multiple paths for each robot? It turns out that a cube complex is obtained, which is a special kind of singular complex (recall from Section 6.3.1). The coordination space for $m$ fixed paths can be considered as a singular $m$-simplex. For example, the problem in Figure 7.9 can be considered as a singular $3$-simplex, $[0,1]^3 \rightarrow X$. In Section 6.3.1, the domain of a $k$-simplex was defined using $B^k$, a $k$-dimensional ball; however, a cube, $[0,1]^k$, also works because $B^k$ and $[0,1]^k$ are homeomorphic.

For a topological space, $X$, let a $k$-cube (which is also a singular $k$-simplex), ${\square}_k$, be a continuous mapping ${\sigma}: [0,1]^k \rightarrow X$. A cube complex is obtained by connecting together $k$-cubes of different dimensions. Every $k$-cube for $k \geq 1$ has $2k$ faces, which are $(k-1)$-cubes that are obtained as follows. Let $(s_1,\ldots,s_k)$ denote a point in $[0,1]^k$. For each $i \in \{ 1,\ldots,k\}$, one face is obtained by setting $s_i = 0$ and another is obtained by setting $s_i = 1$.

The cubes must fit together nicely, much in the same way that the simplexes of a simplicial complex were required to fit together. To be a cube complex, ${\cal K}$ must be a collection of simplexes that satisfy the following requirements:

1. Any face, ${\square}_{k-1}$, of a cube ${\square}_k \in {\cal K}$ is also in ${\cal K}$.
2. The intersection of the images of any two $k$-cubes ${\square}_k,{\square}^\prime_k \in {\cal K}$, is either empty or there exists some cube, ${\square}_i \in {\cal K}$ for $i < k$, which is a common face of both ${\square}_k$ and ${\square}^\prime_k$.

Let ${\cal G}_i$ denote a topological graph (which may also be a roadmap) for robot ${\cal A}^i$. The graph edges are paths of the form $\tau : [0,1] \rightarrow {\cal C}^i_{free}$. Before covering formal definitions of the resulting complex, consider Figure 7.10a, in which ${\cal A}^1$ moves along three paths connected in a ``T'' junction and ${\cal A}^2$ moves along one path. In this case, three 2D fixed-path coordination spaces are attached together along one common edge, as shown in Figure 7.10b. The resulting cube complex is defined by three $2$-cubes (i.e., squares), one $1$-cube (i.e., line segment), and eight 0-cubes (i.e., corner points).

Figure 7.10: (a) An example in which ${\cal A}^1$ moves along three paths, and ${\cal A}^2$ moves along one. (b) The corresponding coordination space.

Now suppose more generally that there are two robots, ${\cal A}^1$ and ${\cal A}^2$, with associated topological graphs, ${\cal G}_1(V_1,E_1)$ and ${\cal G}_2(V_2,E_2)$, respectively. Suppose that ${\cal G}$ and ${\cal G}_2$ have $n_1$ and $n_2$ edges, respectively. A 2D cube complex, ${\cal K}$, is obtained as follows. Let $\tau_i$ denote the $i$th path of ${\cal G}_1$, and let $\sigma_j$ denote the $j$th path of ${\cal G}_2$. A $2$-cube (square) exists in ${\cal K}$ for every way to select an edge from each graph. Thus, there are $n_1 n_2$ $2$-cubes, one for each pair $(\tau_i,\sigma_j)$, such that $\tau_i \in E_1$ and $\sigma_j \in E_2$. The $1$-cubes are generated for pairs of the form $(v_i,\sigma_j)$ for $v_i \in V_1$ and $\sigma_j \in E_2$, or $(\tau_i,v_j)$ for $\tau_i \in E_1$ and $v_j \in V_2$. The 0-cubes (corner points) are reached for each pair $(v_i,v_j)$ such that $v_i \in V_1$ and $v_j \in V_2$.

If there are $m$ robots, then an $m$-dimensional cube complex arises. Every $m$-cube corresponds to a unique combination of paths, one for each robot. The $(m-1)$-cubes are the faces of the $m$-cubes. This continues iteratively until the 0-cubes are reached.