IEEE Robotics & Automation Magazine - March 2014 - 69

terrestrial vehicles operating in outdoor environments. We
can apply these methods to mobile manipulators by augmenting the search space with configuration constraints of the manipulator. Figure 7 illustrates slices of a local search graph
generated by sampling constraints that included the terminal
position of the end-effector and orientation of the base with
respect to the initial pose. We applied this technique for intelligent teleoperation of a Learning Applied to Ground Robots
(LAGR) platform mobile robot [12] outfitted with a five degrees-of-freedom manipulator to autonomously approach objects of interest. More details on experiments involving the
application of our approach to local search graphs on mobile
manipulators can be found in [13].
For each of these robots, we constructed local search
graphs by sampling in the space of boundary state constraints. The rules for how boundary state constraints are
distributed in the local search graph are dependent on the
characteristics of the robot, application, and environment.
This flexibility, coupled with the capacity to efficiently generate trajectories subject to an arbitrary predictive motion
model, provides us with a simple set of tools for generating
local search graphs that are well separated, feasible, and efficient to compute.
Global Search Graphs
Global search graphs represent chains of possible decisions
that are searched to find a minimum-cost path from the
initial state to some set of goal states. These approximations
of the space of all robot motions typically exhibit longer sequences of robot decisions, lower fidelity of robot motions,
and coarser resolution of robot state than their local search
graph counterpart. Search in global search graphs typically
involves search implemented with data structures with divergent (acyclic) or recombinant (cyclic) connectivity. Common examples of divergent structures are trees, which can
be generated using the previously described input-space
sampling methods. A well-studied implementation of divergent motion planning search spaces is the rapidly exploring randomized tree [8], where heuristics are used to
bias sampling toward unexplored regions. Grids are the
most common type of recombinant graph search space.
Vertices corresponding to state values are regularly sampled
throughout the state space, and edges express the cost and
existence of the motions required to transition between adjacent vertices.
Our approach to global search graph construction uses a
special type of trajectory library composed of motions that
satisfy differential constraints and conforms to a regularly distributed set of boundary states [14]. The position dimensions
are sampled as a uniform grid (rectangular, hexagonal, or
other repeating unit). The choice of grid resolution significantly depends on specifics of the system: it is chosen to be
commensurate with the trajectory following accuracy of the
robot controller and the feature size of the robot's perception
system (e.g., for occupancy grid approaches, the resolution of
this grid). Intuitively, search fixed to the grid resolution could

(a)

(b)

(c)

Figure 5. Local search graphs with varying initial angular velocities
subject to uniformly sampled terminal boundary constraints:
(a) turning left, (b) driving straight, and (c) turning right.

MARCH 2014

IEEE ROBOTICS & AUTOMATION MAGAZINE

Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - March 2014