Chapter 2
Introduction to Sampling-based Motion
Planning
To put OMPL in context, a short introduction to the principles of sampling-based motion planning
is first given. Robotic motion planning seeks to find a solution to the problem of “Go from the
start to the goal while respecting all of the robot’s constraints." From a computational point of
view, however, such an inquiry can be very difficult when the robot has a large number of degrees
of freedom. For simplicity, consider the classical motion planning problem known as the piano
mover’s problem. In this formulation, there exists a rigid object in 3D (the piano), as well as a set
of known obstacles. The goal of the piano mover’s problem is to find a collision-free path for the
piano that begins at its starting position and ends at a prescribed goal configuration. Computing the
exact solution to this problem is very difficult. In this setup, the piano has six degrees of freedom:
three for movement in the coordinate planes (
x
,
y
,
z
), and three more to represent rotation along the
axes of these coordinate planes (roll, pitch, yaw). To solve the piano mover’s problem we must
compute a set of continuous changes in all six of these values in order to navigate the piano from
its starting configuration to the goal configuration while avoiding obstacles in the environment. It
has been shown that finding a solution for the piano mover’s problem is
PSPACE
-hard, indicating
computational intractability in the degrees of freedom of the robot [1, 2, 3].
2.1 Historical Notes
OMPL specializes in sampling-based motion planning, which is presented in Section 2.2. To
put sampling-based methods in context, a very brief historical overview to the methods that have
been proposed for motion planning is presented. Most of these methods were developed before
sampling-based planning, but are still applicable in many scenarios.
Exact and Approximate Cell Decomposition
In some instances, it is possible to partition the
workspace into discrete cells corresponding to the obstacle free portion of the environment. This
decomposition can then be modeled as a graph (roadmap), where the vertices represent the individual
2
评论0