IEEE Robotics & Automation Magazine - December 2016 - 113

computational complexity of a deterministic sampling method
can be too high to obtain a solution within a certain time requirement. Therefore, this method is typically limited to lowdimensional solution spaces as the size of the grid grows
exponentially with the dimension of the solution space [24].
A multiresolution deterministic sampling representation, such
as a quadtree (2-D) or an octree (3-D) [30], is an option if the
computational complexity is limiting. As this representation
can represent volumes with a lower resolution, it is typically
more efficient for planning purposes than a regular, deterministic representation. A random sampling method is even
of a lower complexity, as it generally requires fewer samples to
represent the world space than a deterministic sampling
method. As a result, it can be applied to higher-dimensional
solution spaces.
R5) Is the environment cluttered? In a cluttered environment, care needs to be taken to prevent the incompleteness
when using an approximate representation method. The
resolution of sampling must be dense enough to allow the
robot to pass through the smallest clearance between obstacles. In particular, for random sampling methods, it is important that the used sampling strategy ensures dense
enough sampling in small passages. This difficulty that the
sampling-based planners face, known as the "narrow passage problem" [31], can be overcome using different sampling strategies [3], [24].
R6) Can the planner be used for multiple queries? It can be
beneficial to use a road map representation if a motion planner
must generate multiple solutions within the same world space.
This can be an explicit representation, such as a Voronoi diagram or visibility graph [4], but also an implicit variant, such as
a PRM [25] or PRM ) [26]. A road map only needs to be computed once and can subsequently be used for multiple searches;
hence, the computational complexity of the representation is
limited to a precomputation step. A road map can be recomputed or updated if the environment changes. On the other
hand, if only one solution is required, it is not necessary to generate a complete representation of the world space. Representation and searching could then be interleaved using a
single-query planner such as an RRT [27], EST [12], RRT )
[26], or RRT# [28]. Note that these algorithms do not require a
search method as is introduced in the "Selecting a Search Algorithm Class" section.
Selecting a Search Algorithm Class
The sections "Selecting an Approach to Combine Algorithm
Classes" and "Selecting a Representation Class" discuss the
available approaches to combine the motion-planning algorithms and the available classes of representation algorithms.
In this section, two available classes of search algorithms are
discussed: 1) uninformed and 2) informed. Depending on the
designer's requirements, these classes of algorithms can be
combined with additional features, such as incremental replanning and anytime behavior. A method, shown in Figure 3,
is provided to select a suitable class of search algorithms,
given an approach to combine the motion-planning algo-

S1) Heuristic
Possible?
Representation

No

Yes
Refer to the Section
"Method to Select a
Representation Class"

Uninformed
Search [32]

Informed
Search
[8], [32]
R2) Solution Space?
C

S

[34], [37]

[8], [37]

Yes

Add Anytime
[8], [33], [37]
Yes

S2) Significantly Changing No S3) Required (Is a solution
Environment?
required at anytime?)
Yes
S3) Required (Is a solution No
required at anytime?)

Add Anytime
Incremental
Replanning [8]
Add Incremental
Replanning
[8], [36]

Figure 3. A method to arrive at an appropriate class of search
algorithms. The numbers S1-S3 (purple) correspond to the
design criteria posed in the "Method to Select a Search Algorithm
Class" section, and R2 (red) corresponds to a criterion posed in
the "Selecting a Representation Class" section.

rithms (see "Selecting an Approach to Combine Algorithm
Classes" section).
Search Algorithm Classes
Most representations transform the continuous problem of finding a solution in the free space into a discrete problem of searching a graph with the nodes that represent the configurations or
states of the robot. Therefore, uninformed and informed search
algorithms can be applied.
An uninformed search algorithm moves through the graph
without any preference for the location of the goal. Wellknown algorithms are the breadth-first search algorithm and
depth-first search algorithm. An optimal path with respect to a
specified cost criterion can be achieved using Dijkstra's algorithm [32].
If the direction of the goal node is known, the search can
be directed, i.e., it can be biased toward the goal. A search algorithm that includes information about the goal is called an
informed search algorithm. To achieve this, a heuristic is formulated, i.e., a function of nodes that hypothesizes cost toward the goal node. The choice for the next node to explore is
then based on this heuristic cost, e.g., defined as the Euclidean
distance toward the goal. The most well-known algorithm is
the A ) algorithm. Similar to the uninformed algorithms, A )
also returns the optimal path, but the search typically is of
DECEMBER 2016

*

IEEE ROBOTICS & AUTOMATION MAGAZINE

*

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