Manipulation graph

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

  1. Compute the connected components of $ {X_{tra}}$ to yield the vertices of $ {\cal G}_m$.
  2. Compute the edges of $ {\cal G}_m$ by applying ordinary motion planning methods to each pair of vertices of $ {\cal G}_m$.
  3. Apply motion planning methods to connect the initial and goal states to every possible vertex of $ {X_{tra}}$ that can be reached without a mode transition.
  4. Search $ {\cal G}_m$ 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 $ \sigma $, the actions that cause the required mode changes).
This can be considered as an example of hierarchical planning, as described in Section 1.4.

Figure 7.17: This example was solved in [244] using the manipulation planning framework and the visibility-based roadmap planner. It is very challenging because the same part must be regrasped in many places.
\begin{figure}\centerline{\psfig{figure=figs/,width=\columnwidth} }\end{figure}

Figure 7.18: This manipulation planning example was solved in [915] and involves 90 movable pieces of furniture. Some of them must be dragged out of the way to solve the problem. Paths for two different queries are shown.
\begin{figure}\centerline{\psfig{figure=figs/,width=\columnwidth} }\end{figure}

Steven M LaValle 2012-04-20