Multilevel Planning Framework {#multiLevelPlanning}
[TOC]
When dealing with high-dimensional motion planning problems, we often cannot solve them directly because our algorithms either run out of memory or the runtime quickly blows up. To combat this curse of dimensionality, we can instead plan on different levels of abstractions. To plan on different levels of abstractions, we develop the multilevel planning framework. In this framework we use internally the language of Fiber Bundles to model abstractions as sequences of admissible lower-dimensional projections of the state space.
High-level introduction
Instead of planning on a single state space, we instead use a sequence of state
spaces, which allows a planner to exploit those spaces to quickly find
solutions. To use the multilevel planning framework, you only need to
specify a sequence of ompl::base::SpaceInformationPtr together with
corresponding ompl::base::StateValidityChecker functions. You can use any
sequence and any validiy checker you like. However, if you want to be sure that
the algorithm finds a solution, you need to make sure that those functions are
admissible. Admissible here means that if there exists a valid solution on the
original state space, and you project this solution onto a lower-dimensional
space in your sequence, then this solution must be feasible. In practice, you
can achieve admissibility by constraint relaxation operations, like shrinking
obstacles, shrinking links, removing non-holonomic constraints, removing links,
removing subsystems or removing robots (from a set of robots).
Some examples of admissible projections are shown in the Figure below. We show three examples. In the first example, we remove the arms of PR2 (which might be irrelevant when moving through long corridors). In the second example, we remove some fingers of the Shadow hand which might not be relevant for a particular grasp. In the third example, we nest an inscribed sphere in an airplane. While the airplane might have non-holonomic constraints, the sphere is holonomic. The validity checker in each case corresponds to checking collision of the lower-dimensional robot.
\htmlonly
