IEEE Robotics & Automation Magazine - December 2016 - 114

lower computational complexity, i.e., it explores less space
and, thus, returns a solution faster [32]. To ensure completeness and optimality, a heuristic must satisfy two properties:
1) consistency and 2) admissibility [32]. A heuristic that satisfies these two properties never overestimates the cost of
reaching the goal.
Method to Select a Search Algorithm Class
Given an approach to combine motion-planning algorithms,
the following design criteria, numbered S1-S3, form a method to select a suitable class of search algorithms. The method
is shown in Figure 3.
S1) Can a heuristic be defined to speed up the search? The use
of a heuristic to the goal can reduce the complexity of a search
[8]. An informed search is preferred over an uninformed search,
if a consistent and admissible heuristic [32] can be defined. In
particular, for a search in a high-dimensional solution space, a
heuristic can greatly reduce the complexity. A heuristic is then
typically informed with more than just the distance to the goal
by using a search in a lower dimension as a heuristic to inform a
search in the full dimension of the solution space [33], [34]. For
example, a planner that does a search in the state space S can be
informed with a heuristic that does a search in the configuration
space C. This heuristic search ignores robot constraints and
moving obstacles, but it can reduce the search space of S substantially, and, thus, it can return a solution faster. The reduction
in the space depends on whether the heuristic solution is expected to be close to the optimal solution.
The single-query planners introduced in the "Selecting a
Representation Class" section can also benefit from adding a
goal bias or other heuristic to the sampling algorithm. Examples of such approaches can be found in [35].
S2) Does the environment change significantly between consecutive searches? A plan can become infeasible during execution
because of appearing or moving obstacles. Therefore, a motion
planner can adopt a replanning strategy. Replanning can be performed by computing an entirely new plan. One could also use
incremental replanning using the results of previous searches to
generate a new plan faster [36]. The benefit of considering previous solutions depends on the environment. If there is no significant change, a replan can be acquired faster, but when the results
of previous solutions are less useful, it can even be disadvantageous to the task of arriving at a new solution [8].
S3) Is a solution required at anytime? It is desirable to
achieve a solution as fast as possible. However, this solution is
typically not optimal. An anytime search algorithm can return
a solution within a certain time constraint and with a certain
bound on its suboptimality [8]. As time allows, this bound is
tightened, and, given enough time, the optimal solution is returned [37]. An optimal search algorithm typically acquires
this solution faster, but an anytime algorithm allows a robot to
start executing an initial suboptimal solution and improve this
solution along the way; examples can also be found in [26].
This concludes this discussion of the motion-planning
method. An overview of the requirements and the corresponding design criteria is presented in Table 1. This overview
114

IEEE ROBOTICS & AUTOMATION MAGAZINE

DECEMBER 2016

Table 1. The design requirements and the
corresponding selection criteria of the method.
Requirement

Design Criterium

Environment
Known/unknown

A1, A6

Uncertainty in obstacle representation A2, A4, A6
Moving obstacles
A3, A4, A6, S2
Robot model
Correctness
Kinodynamic constraints

R1
A4, A5, A6, A7, R2

Application
Completeness

A2, A4, A5, R1, R3,
R4, R5

Optimality

A3, A4, A5, R3, R4, S3

Computational complexity

A3, A4, A5, A6, A7,
R4, R6, S1

shows that several design criteria involve multiple requirements. This clearly indicates the tradeoffs that are commonly
present when designing a navigation system, e.g., one could try
to design a system that returns optimal solutions in the presence of moving obstacles, but this would be computationally
extremely complex. More of these tradeoffs can be derived
from Table 1.
Method Verification
Three use cases from the literature involving the application of a
motion planner in practice are evaluated to verify the proposed
method: 1) the PR2 service robot that autonomously navigated
a marathon distance of 42.15 km in a real office environment
[13], 2) the autonomous vehicle Boss that won the U.S. Defense
Advanced Research Projects Agency Urban Challenge [38], and
3) a flexible automated guided vehicle (AGV) in partially structured warehouses [39].
Application of the Method to Use Case I
The PR2 service robot has an omnidirectional base platform with a top speed of 1 m/s. It navigates an office environment that is cluttered with a variety of arbitrarily
shaped obstacles [13].
Selecting an Approach to Combine Algorithm Classes
The office environment is only partly known, so the robot must
replan as it receives new information about the world (A1). The
depth accuracy of the sensors that are used for navigation is 1.5 cm.
Hence, the resulting uncertainty must be captured in a bounded uncertainty region (A2). The office environment is populated by people, so the environment contains moving obstacles
(A3). The trajectories of people are unpredictable (A4), and the
world space is only partially known. Therefore, the representation of the world space will change rapidly. As the robot is desired to navigate at a reasonable speed of about 0.5 m/s, a
reactive approach is the most suitable approach to avoid collision in real-time (A5 and A6). A reactive approach requires an

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