IEEE Robotics & Automation Magazine - March 2014 - 65

and field robots. As it is difficult to generate trajectories by
inverting the nonlinear, coupled equations of robot motion
with limited computational resources, efficient sampling
techniques must be developed to achieve the real-time performance in practical applications. This challenge drives applications away from naturally recombinant structures and
toward sampling-based techniques that search in the space of
sequential robot inputs. We assert that there is a need for a
universal planning, navigation, and control framework that
applies broadly across a wide range of platforms.
This article serves as an accessible summary of a decade
of work on a number of programs that relate to the use of
high-fidelity predictive models in mobile robot planning,
navigation, and control. Herein, we review our model-based
approach to trajectory generation, model calibration, and
graph design with applications for local and global motions
planning. We achieve generality by hiding the implementation of the predictive motion model from the optimizer, enabling rapid and successful deployment of such techniques
on a diverse set of mobile robot systems (Figure 1).
Trajectory Generation
A trajectory generator must be able to determine the action
^u ^ x, t hh that satisfies a set of state constraints ^ x C ^ t hh or
minimize a cost function ^ J ^ x, t hh or both subject to initial
state constraints ^ x ^t 0hh and the predictive motion model
xo ^ x, u, t h . Many techniques have been proposed, developed,
and applied to solve this constrained optimization problem
for the mobile robots. Our approach, detailed in [1], transforms the general problem of optimal control to parametric
optimal control by parameterizing the space of inputs (1).
This technique reduces searching in the space of all possible
actions to a more computationally effective representation
where the shape of inputs is controlled by a small number of
degrees of freedom
u ^ x, t h " u ^ p, x, t h .

these matrices are found using forward simulations of the
predictive motion model with small perturbations of individual action parameters. When it is not necessary to minimize a cost function in addition to satisfying terminal
boundary state constraints, the expression in (2) can be linearized and inverted to estimate a set of parameter corrections that satisfies the initial state, predictive motion model,
and terminal boundary state constraints
p i +1 = p i - ;

2Dx ^ p ih -1
E Dx ^ p i h
2p i

One of the challenges
of applying such techniques for mobile robot
trajectory planning involves how the parameter
space is reduced to search
efficiently and avoid local
optima. Some of the initial
work on this topic applied
polynomial functions of
curvature parameterized
by signed distance to express the space of candidate vehicle motions [2].
These expressions were
well suited to indoor mobile robot applications
because, for simple kinematic predictive motion
models, the shape of the

i $ 0.

(3)

A formulation that
calibrates the predictive
motion model can be used
either online or offline, by
observing its integrated
effect over short time
intervals, and comparing
that result to direct
measurements.

(1)

Given an initial guess of action parameters p 0, the trajectory generation problem becomes one of finding a correction
Dp that satisfies the following expression:
x C ^t 1h =

#t t xo ^x, u^ p 0 + Dp, x, t h, t hdt.
1

(2)

Solving this expression directly is impractical, if not impossible, for the mobile robots operating in realistic threedimensional (3-D) terrain with nontrivial actions. For
mobile robots operating on planar surfaces that are even, (2)
contains trigonometric expressions that render it nonintegrable for nonconstant linear and angular velocities. For
physical systems that navigate on rough (two-and-a-half or
3-D) terrain, it becomes nonintegrable in any case. Our approach alternatively generates numerical estimates of the Jacobian and Hessian to iteratively refine the initial guess until
the boundary state constraints are satisfied, the minimumcost solution is found, or both. The partial derivatives in

(a)

(b)

(c)

(d)

Figure 1. The experimental platforms used during the evolution
of our hierarchical trajectory planning approach: (a) Rocky 8,
(b) Crusher, (c) LAGR, and (d) Boss.

MARCH 2014

IEEE ROBOTICS & AUTOMATION MAGAZINE

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