IEEE Robotics & Automation Magazine - June 2011 - 117

*
construct a partial map of E and maintain its position and
orientation with respect to its map. A naive way to attempt
this is to enumerate all possible E 2 E that are consistent
with the history I-state, and for each one, enumerate all possible (i, j) 2 Z 3 Z and orientations in D. Such a filter would
live in an I-space I ¼ pow(Z 3 Z 3 D 3 E), with each Istate being a subset of I . An immediate problem is that
every I-state describes a complicated, infinite set of
possibilities.
A slightly more clever way to handle this is to compress
the information into a single map, as shown in Figure 14(b).
Rather than be forced to label every (i, j) 2 Z 3 Z as "black"
or "white," we can assign a third label, "unknown." Initially,
the tile that contains the robot is "white" and all others are
"unknown." As the robot is blocked by walls, some tiles
become labeled as "black." The result is a partial map that
has a finite number of "white" and "black" tiles, with all
other tiles being labeled "unknown." An I-state can be
described as two finite sets W (white tiles) and B (black
tiles), which are disjoint subsets of Z 3 Z. Any tile not
included in W or B is assumed to be "unknown."
Now consider a successful search plan that uses this filter. For any "unknown" tile that is adjacent to a "white"
tile, we attempt to move the robot onto it to determine
how to label it. This process repeats until no more
"unknown" tiles are reachable, which implies that the environment has been completely explored.
A far more interesting filter and plan are given in [4].
Their filter maintains I-states that use only logarithmic
memory in terms of the number of tiles, whereas recording
the entire map would use linear memory. They show that
with very little space, not nearly enough to build a map, the
environment can nevertheless be systematically searched.
For this case, the I-state keeps track of only one coordinate
(for example, in the north-south direction) and the orientation, expressed with 2 b. A plan is defined in [4] that is guaranteed to visit all white tiles using only this information.
Moving to continuous spaces leads to the familiar
simultaneous robot localization and mapping (SLAM)
problem [7], [18]. For the localization problem alone, a
Kalman filter is used. In this case, the filter I-state is
i ¼ (l, R) in which l is the robot configuration estimate
and R is the covariance. The Kalman filter computes transitions that follow the form (13). When mapping is combined, each filter I-state encodes a probability distribution
over possible maps and configurations. The I-space I
becomes so large that sampling-based particle filters are
developed to approximately compute (13).
A full geometric map is useful for many tasks; however, the I-space can be dramatically reduced by focusing
on a particular task. An example from [19] is briefly
described here. Consider a simple gap sensor placed on a
mobile robot in a polygonal environment, as shown in
Figure 15. Suppose the task is to optimally navigate the
robot in terms of the shortest possible Euclidean distance.
The robot is not given a map of the environment. Instead,

it uses gap observations and records an association
between gaps when two gaps merge into one. It is shown
in [19] that this precisely corresponds to the discovery of
a bitangent edge, which is a key part of the shortest path
graph (alternatively called reduced visibility graph), a data
structure that encodes the common edges of optimal
paths from all initial-goal pairs of positions. The filter Istate records a tree, shown in Figure 16, that indicates how
the gaps merged. The tree itself is combinatorial (no geometric data) and precisely encodes the structure needed for
optimal robot navigation from the robot's current location.
The robot is equipped with an action that allows it to chase
any gap until that gap disappears or splits into other gaps.
Using the tree, it can optimally navigate to any place that
it has previously seen. The set of all trees forms the filter
I-space I from which distance-optimal navigation can
be entirely solved in an unknown environment without
measuring distances.
Challenges
Because of the wide variety of tasks and possible combinations of sensors and control models, many challenges
remain to design planning algorithms by reducing the

g1
φ

φ
g2

g5
g3

(a)

g4
(b)

Figure 15. Consider a robot placed in a simple polygon. (a) A
strong sensor could omnidirectionally seem to provide a
distance measurement along every direction from 0 to 2p. (b) A
gap sensor can only indicate that there are discontinuities in
depth. A cyclic list of gaps fg1 , g2 , g3 , g4 , g5 g is obtained, with no
angle or distance measurements.

4
5

1
2

3
3
4

(a)

5
(b)

Figure 16. (a) The gap navigation tree captures the structure of
the shortest paths to the current robot location (the white circle
on the left). (b) The tree precisely characterizes how the
shortest paths to the robot location are structured.

JUNE 2011

IEEE ROBOTICS & AUTOMATION MAGAZINE

117

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