IEEE Robotics & Automation Magazine - June 2011 - 115

*
GÃk (xk )

¼ min l(xk , uk )
uk 2U(xk )

xkþ1 2X

GÃkþ1 (xkþ1 )P(xkþ1 jxk , uk ) ,

(11)

which again provides value-iteration methods and in some
cases Dijkstra-like algorithms. There are also variations
for optimizing worst-case performance, computing gametheoretic equilibria, and reinforcement learning, in which
the transition equation must be learned in the process of
determining the optimal plan.
Challenges
Feedback motion planning appears to be significantly
more challenging than path planning. Some current challenges are
l The curse of dimensionality seems worse. Methods are
limited to a few dimensions in practice. Cell decomposition
methods do not scale well with dimension and optimal
planning methods require high-resolution sampling. Can
implicit volumetric representations be constructed and utilized efficiently via sampling?
l Merging with the "Differential Constraints" section
leads to both complicated differential constraints and
feedback. Hybrid systems models sometimes help by
switching controllers over cells during a decomposition
[5]. Another possibility is to track space-filling trees,
grown backwards from the goal, as opposed to single
paths [17]. If optimality is not required, there are great
opportunities to improve planning efficiency.
l If a fast-enough path-planning algorithm exists for a
problem, then the feedback plan could be a dynamic
replanner that recomputes the path as the robot ends up
in unexpected states or obstacle change. When is this
kind of solution advantageous and how does it relate to
explicitly computing p : X ! U?
l Perhaps the plan as a mapping p : X ! U is too constraining. Would it be preferable to compute a plan that
indicates for every state a set of possible actions that are
all guaranteed to make progress toward the goal? This
would leave more flexibility during execution to account
for unexpected events.
Sensing Uncertainty
Recall from the "Limitations of Path Planning" section
that, after following the classical steps in Figure 1, the
information requirements are driven artificially high:
complete state information, including the models of the
obstacles, is needed at all times. On the other hand, we
see numerous examples in robotics and nature of simple
systems that cannot possibly build complete maps of
their environment while nevertheless accomplishing
interesting tasks. A simple Roomba vacuum cleaner can
obtain a reasonable level of coverage with poor sensors
and no prior obstacle knowledge. Ants are able to

construct complex living spaces and transport food and
materials. Since maintaining the entire state seems futile
for most problems, it makes sense to start with the
desired task and determine what information is required
to solve it. This could lead to a minimalist approach in
which a cheap combination of simple sensors, actuators,
and computation is sufficient.
The goal in this section is to give you a basic idea of
how planning appears from this perspective. There are
many open challenges and directions for future research.
The presentation here gives representative examples rather
than complete modeling alternatives; for more details, see
[12] and [13].
Let X be a state space that is typically much larger than C.
A state x 2 X may contain robot configuration parameters,
configuration velocities, and even a complete representation
of the obstacles O & W. A change in x could correspond to
a moving robot or a change in obstacles. In this case, X is not
even assumed to be a manifold (it is just a large set). Suppose
x0 ¼ f (x, u) for u 2 U is a discrete-time state-transition
equation that indicates how the entire world changes.
In this section, the state x is hidden from the robot. The
only information it receives from the external world is from
sensor mappings of the form h : X ! Y, in which Y is a set
of sensor outputs, called the observation space. Consider h
as a many-to-one mapping. A weaker sensor causes more
states to produce the same output. In other words, the preimage hÀ1 (y) ¼ fx 2 X j y ¼ h(x)g is larger.
At any time during execution, the complete set of information available to the robot consists of all sensor observations and all actions that were applied (and any given
initial conditions). This is called the history information
state (or I-state); if an observation and action occur at each
stage, then it appears at stage k as
gk ¼ (u1 , . . . , ukÀ1 , y1 , . . . , yk ):

(12)

Imagine placing a set of all possible gk for all k ! 1 in a
large set I hist called the history I-space. Although I hist is
enormous, the state gk 2 I hist is at least not hidden from
the robot. We can therefore define an information feedback plan p : I hist ! U.
Of course, I hist is so large that it is impractical to work
directly with it. Therefore, we design a filter that compresses
each gk to retain only some task-critical pieces of information.
The result is an implied information mapping j : I hist ! I
into some new filter I-space I . As new information, ukÀ1 and
yk , becomes available, the filter I-state ik 2 I becomes
updated through a filter transition equation
ik ¼ /(ikÀ1 , ukÀ1 , yk ):

(13)

Now let I be any I-space. Generally, the planning problem is to choose each uk so that some predetermined goal
is achieved. Let G & I be called a goal region in the I-space.
Starting from an initial I-state i0 2 I , what sequence of
JUNE 2011

IEEE ROBOTICS & AUTOMATION MAGAZINE

115

Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - June 2011