#### 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 fixed paths can be considered as a singular -simplex. For example, the problem in Figure 7.9 can be considered as a singular -simplex, . In Section 6.3.1, the domain of a -simplex was defined using , a -dimensional ball; however, a cube, , also works because and are homeomorphic.

For a topological space, , let a -cube (which is also a singular -simplex), , be a continuous mapping . A cube complex is obtained by connecting together -cubes of different dimensions. Every -cube for has faces, which are -cubes that are obtained as follows. Let denote a point in . For each , one face is obtained by setting and another is obtained by setting .

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, must be a collection of simplexes that satisfy the following requirements:

1. Any face, , of a cube is also in .
2. The intersection of the images of any two -cubes , is either empty or there exists some cube, for , which is a common face of both and .

Let denote a topological graph (which may also be a roadmap) for robot . The graph edges are paths of the form . Before covering formal definitions of the resulting complex, consider Figure 7.10a, in which moves along three paths connected in a T'' junction and 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 -cubes (i.e., squares), one -cube (i.e., line segment), and eight 0-cubes (i.e., corner points).

Now suppose more generally that there are two robots, and , with associated topological graphs, and , respectively. Suppose that and have and edges, respectively. A 2D cube complex, , is obtained as follows. Let denote the th path of , and let denote the th path of . A -cube (square) exists in for every way to select an edge from each graph. Thus, there are -cubes, one for each pair , such that and . The -cubes are generated for pairs of the form for and , or for and . The 0-cubes (corner points) are reached for each pair such that and .

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

Steven M LaValle 2012-04-20