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.
...dex2.eps,width=1.7in} \\
(a) & & (b) \\

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.

Steven M LaValle 2012-04-20