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