IEEE Robotics & Automation Magazine - December 2016 - 115

obstacle avoidance algorithm and a global planner (see "Approaches to Combine Algorithm Classes" section).

error recovery. The latter planner is used for the verification
of the method.

Selecting a Representation Class
With only 5-cm clearance on both sides when traversing a typical doorway, a circular approximation of the PR2 will result in
incompleteness. Thus, the robot is best described by a rigid body
(R1). The solution space consists of multiple rooms and
corridors and, therefore, lends itself for a topological representation. This representation reduces the size of the solution space of
the global planner, which is equal to C (R2). An approximate
representation method is preferred over an exact representation
method as the obstacles are of arbitrary shape and their representation is uncertain (R3). The environment is cluttered with
small obstacles, such as office supplies; thus, dense sampling is
required to prevent incompleteness. A deterministic sampling
method is, therefore, preferred over a stochastic sampling method (R4). A multiresolution representation is advised to negotiate
the computational complexity as an office environment has large
open space but also consists of cluttered occupied spaces.

Selecting an Approach to Combine Algorithm Classes
Replanning is required, as Boss faces unknown spaces as it navigates (A1). Boss' sensors have a limited resolution, and thus a
bounded uncertainty region is necessary (A2). During navigation, the vehicle encounters other vehicles (A3) whose future
trajectories are predictable in short term (A4); hence, a time
dimension can be added for a time-optimal solution. A solution
in the form of a plan in the full-dimensional solution space is
necessary to be time optimal, but as vehicles are only predictable
in the short term, it is only necessary to consider a time dimension for that short term (A5). A plan is necessary to consider the
kinematic constraints of the vehicle (A6). To achieve a local optimal solution, a hierarchical approach is suggested (A7).

Selecting a Search Algorithm Class
The PR2 is supplied with a navigation goal. The direction of
this goal can be used as a heuristic to speed up the search
(S1). In a cluttered office environment, a replan can be significantly different from an original search, and, thus, recomputing an entire new plan is preferred (S2). It is not required for a
robot to obtain a solution immediately upon a goal request,
but it is desirable. Therefore, the search algorithm can be extended with an anytime algorithm (S3).
Comparison of the Method's Outcome
and the Use Case
Similar to the prescription by the method, the PR2 motion
planner [13] operates with a reactive approach as it uses a
global planner and a local obstacle avoidance algorithm [20].
The local algorithm uses a rigid body description, but the robot's shape is approximated by an inscribed circle in the global representation of the world space. This can result in
incompleteness as the global planner may produce a path
through a narrow passage, e.g., a half-opened door that the
local planner cannot execute. We identified this as a limitation [13]. As the method prescribes, this can be prevented if
the global planner would also use a rigid body description of
the robot. A motion planner for the PR2 that does this is presented in [40]. The PR2 motion planner does not use a topological representation on top of the global configuration
space representation, e.g., as used in [23]. This is, however,
identified for a future work. Furthermore, the global planner
uses an informed search algorithm (A)) like the method indicated, but it is not an anytime algorithm.
Application of the Method to Use Case II
The autonomous driving vehicle Boss uses two different planners [38]: one during nominal on-road driving and one during more unstructured driving, e.g., in a parking lot or during

Selecting a Representation Class
A vehicle is subject to kinematic constraints that must be considered while planning (R1). The velocity also needs to be considered during planning to generate feasible motions in the
presence of obstacles, resulting in S as a solution space (R2).
Given the dimension and size of the solution space, a stochastic sampling method is suitable (R4). Sampling is required to
be dense (R5), especially near the goal configuration as this is
typically in a narrow part of the environment such as a parking
lot. A single-query planner suits as previous solutions are not
reusable (R6).
Selecting a Search Algorithm Class
The vehicle is supplied with a navigation goal that can be
used as a heuristic (S1). Incrementally updating the solution
as new information is acquired can be beneficial, as a traffic
environment, in general, is not very cluttered (S2). To prevent the vehicle from stopping to calculate a plan, it is important that it returns a solution within a certain time constraint.
Hence, an incremental, anytime replanning algorithm is necessary (S3).
Comparison of the Method's Outcome and the Use Case
Boss uses a hierarchical approach [33], which is also prescribed
by the method. The approach includes a global planner that
searches for a feasible motion plan in four-dimensional (4-D)
(x, y, i, v) and a local motion planner operating in the same
space, which selects a trajectory that follows the global plan.
Short, feasible maneuvers are computed offline to substantially
reduce the time to acquire a solution. These maneuvers are
concatenated at planning time in a single-query fashion to obtain a motion plan. In the vicinity of the vehicle and the goal, the
search is dense, like the method indicated, while in other areas,
the set of possible maneuvers is more coarse. A combination of
heuristics is used to further reduce the time to acquire a solution. Similar to the method's prescription, an incremental, anytime algorithm is used. In contrast to the method, a time
dimension is not explicitly incorporated to deal with other moving vehicles. This is solved by marking the space that another
DECEMBER 2016

IEEE ROBOTICS & AUTOMATION MAGAZINE

115

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