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, , to be a garage for are 1) while at configuration , it is impossible for any other robots to collide with it (i.e., in all coordination states for which the th coordinate is , no collision occurs); and 2) is always reachable by from . If each robot has a roadmap and a garage, and if the planning method for is complete, then the overall planning algorithm is complete. If the planning method in uses some weaker notion of completeness, then this is also maintained. For example, a resolution complete planner for yields a resolution complete approach to the problem in Formulation 7.2.
Steven M LaValle 2012-04-20