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.