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.

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.