The manipulation planning problem generally can be solved by forming a
manipulation graph,
[16,17]. Let a
*connected component* of refer to any connected component
of
that is lifted into the state space by ignoring the mode.
There are two copies of the connected component of
, one for
each mode. For each connected component of , a vertex exists
in
. An edge is defined for each transfer path or transit
path that connects two connected components of . The general
approach to manipulation planning then is as follows:

- Compute the connected components of to yield the vertices of .
- Compute the edges of by applying ordinary motion planning methods to each pair of vertices of .
- Apply motion planning methods to connect the initial and goal states to every possible vertex of that can be reached without a mode transition.
- Search for a path that connects the initial and goal states. If one exists, then extract the corresponding solution as a sequence of transit and transfer paths (this yields , the actions that cause the required mode changes).

Steven M LaValle 2012-04-20