Fixed-roadmap coordination

The fixed-path coordination approach still may not solve the problem in Figure 7.8 if the paths are designed independently. Fortunately, fixed-path coordination can be extended to enable each robot to move over a roadmap or topological graph. This still yields a coordination space that has only one dimension per robot, and the resulting planning methods are much closer to being complete, assuming each robot utilizes a roadmap that has many alternative paths. There is also motivation to study this problem by itself because of automated guided vehicles (AGVs), which often move in factories on a network of predetermined paths. In this case, coordinating the robots is the planning problem, as opposed to being a simplification of Formulation 7.2.

One way to obtain completeness for Formulation 7.2 is to design the independent roadmaps so that each robot has its own garage configuration. The conditions for a configuration, $q^i$, to be a garage for ${\cal A}^i$ are 1) while at configuration $q^i$, it is impossible for any other robots to collide with it (i.e., in all coordination states for which the $i$th coordinate is $q^i$, no collision occurs); and 2) $q^i$ is always reachable by ${\cal A}^i$ from ${x_{I}}$. If each robot has a roadmap and a garage, and if the planning method for $X$ is complete, then the overall planning algorithm is complete. If the planning method in $X$ uses some weaker notion of completeness, then this is also maintained. For example, a resolution complete planner for $X$ yields a resolution complete approach to the problem in Formulation 7.2.