IEEE Robotics & Automation Magazine - December 2012 - 77

Furthermore, OMPL includes a means of combining state
spaces using the class CompoundStateSpace. A combined state
space implements the functionality of a regular state space on
top of the corresponding functionality from the maintained
set of state spaces. This allows trivial construction of more
complex state spaces from simpler ones. For example
SE3StateSpace [the space of rigid body transformations in
three-dimensional (3-D)] is just a combination of
SO3StateSpace (the space of rotations) and RealVectorStateSpace
(the space of translations). Instances of CompoundStateSpace
can be constructed at run time, which is necessary for constructing a state space from an input file specification, as is
done, for example, in ROS. For a mobile manipulator, one
could construct a CompoundStateSpace with the two arms and
the mobile base as substate spaces. An arm typically has a
number of rotational joints and can be modeled by either a
RealVectorStateSpace (if the joints have limits) or a
CompoundStateSpace with copies of SO(2). The state space for
the base can simply be SE(2) (the space rigid body transformations in the plane).
State spaces optionally include specifications of projections
to Euclidean spaces (ProjectionEvaluator). Low-dimensional
Euclidean projections are used by several sampling-based
planning algorithms (e.g., KPIECE [16], SBL [30], EST [12])
to guide their search for a feasible path, as it is much easier to
keep track of coverage (i.e., which areas have been sufficiently
explored and which areas should be explored further) in such
low-dimensional spaces.
In addition to states and state spaces, some algorithms
in OMPL require a means to represent controls. Control
spaces (ControlSpace) mirror the structure of state spaces
and provide functionality specific to controls, so that planning algorithms can be implemented in a generic way. The
only available implementations of control spaces are the
Euclidean space and a space for discrete modes, because so
far there has not been a need for control spaces with more

complex topologies. However, the API allows one to define
such control spaces.
State Validation and Propagation
Whether a state is valid or not depends on the planning context. In many cases, state validity simply means that a robot is
not in collision with any obstacles, but in general any condition on a state can be used. In OMPL.app (see the section on
OMPL.app: A GUI for OMPL) we have predefined a state
validity checker for rigid body motion planning. We have also
implemented a state validity checker that uses the ODE (see
the section on motion planning using a physics engine). If
these built-in state validity checkers cannot be used for the
system of interest, a user needs to implement their own.
Based on a given state validity checker, a default
MotionValidator is constructed that checks whether the interpolation between two states at a certain resolution produces
states that are all valid. However, it possible to plug in a different MotionValidator. For example, one might want to add support for continuous collision checking, which can adaptively
check for collisions and provide exact guarantees for state
validity [31].
For planning with controls, a user needs to specify how
the system evolves when certain controls are applied for
some period of time starting from a given state. This is called
state propagation in OMPL. In the simplest case, a state
propagator is essentially a lightweight wrapper around a
numerical integrator for systems of the form ˙q = f (q, u),
where q is a state vector and u a vector of controls. To facilitate planning for such systems, we have implemented generic
support for ODE solvers and we have integrated Boost.
Odeint [32], a new library for solving ODEs. Given a userprovided function that implements f (q, u) for the system of
interest, OMPL can plan for such systems. Alternatively, one
can use variational integrators [33], or a physics engine to
perform state propagation.

Motion Planning Using a Physics Engine
OMPL has built-in support for using the ODE physics engine.
Support for other physics engines, such as Bullet, is planned
for a future release. We expect that the approach described
below can be followed for these physics engines (and others)
as well.
The ODE state space consists of the state spaces of the
robot and any movable objects in the environment. The user
specifies which joints are controlled by the planner and maps
those to a ControlSpace. The user can also specify which
collisions are allowed (e.g., contact with the support plane)
and which ones are not (such as driving into a wall). This
simple setup allows one to plan for systems that are difficult
to describe with differential equations. The user does not need
to worry about all the different possible contact modes that
occur when a car drives off a ramp (Figure S2) or when a robot
pushes one or more obstacles (Figure S3).

Figure S2. A car-like robot driving off a ramp.

Figure S3. A yellow robot needs to push obstacles
to get to its goal.

december 2012

IEEE ROBOTICS & AUTOMATION MAGAZINE

Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - December 2012