Chapter 2. Introduction to Sampling-based Motion Planning
cells and edges indicate adjacency among the cells. Utilizing this graph, the problem of moving a
point robot becomes a classical search from the cell with the starting position to the cell containing
the goal position. Such a formulation also works well in “controllable” systems (e.g., omni-
directional base). There are cases though, for example when the robot has complex non-linear
dynamics, where it is not clear how to move the system from one cell to an adjacent cell. It should
also be noted that the motion of robots are computed in states spaces that are high-dimensional.
Partitioning these spaces into free (or approximately free) cells is difficult and impractical in most
cases.
Control-based Methods
Control-based methods attempt to model the equations of motion of
the system and apply ideas from control theory in order to navigate a system along a specified
trajectory. These approaches operate in the continuous space, and typically employ a feedback loop
in order to effectively maneuver the system with minimal error. Using a control-based approach
to navigate a robot is very fast and can be done in an online manner, which is necessary in many
applications. Computing a desirable and feasible trajectory can be very difficult, however, in systems
with complex dynamics and/or cluttered environments, which heavily restrict the valid motions.
Potential Fields
Conceptually, potential fields are a simple and intuitive idea. The classical
potential field involves computing a vector at each point in the workspace by calculating the sum of
an attractive force emanating from the goal, and a repulsive force from all of the obstacles. The
point robot can then navigate using gradient descent to follow the potentials to the goal. Potential
fields have been generalized to systems with a rigid body by considering multiple points on the
robot, and can operate in real-time. Navigating a system using a potential field, however, can fail
due to local minima in the field itself, which stem from the heuristic combination of the forces in
the workspace. Ideally the field would be constructed in the state space of the system, but this is
equivalent to solving the original problem. Some approaches consider a navigation function where
the potential field is guaranteed to have a single minimum, but computing such a function is possible
only in low-dimensional spaces and is non-trivial.
Randomized Planning
Randomization in otherwise deterministic planners has shown to be very
effective. In potential fields, for example, Brownian motions in which a random action is applied
for a specific amount of time have been shown to be highly effective in guiding a system out of a
local minima. Randomized methods have also been applied to non-holonomic systems, particularly
in the field of sampling-based planning. Sampling-based methods were inspired by randomization,
and the use of samples, random or deterministic, when planning are particularly effective for high
degree of freedom systems or those with complex dynamics.
2.2 Sampling-based Motion Planning
Sampling-based motion planning is a powerful concept that employs sampling of the state space of
the robot in order to quickly and effectively answer planning queries, especially for systems with
Open Motion Planning Library : A Primer k 3
评论0
最新资源