IEEE Robotics & Automation Magazine - September 2013 - 39

the greedy strategy considers all neighboring locations of the
robot as candidate-sensing locations and computes the posterior covariance by simulating an EKF update at each sensing
location with a discretized set of possible bearing measurements. The greedy strategy then picks the candidate location
where the determinant of the posterior is minimum.
Enumeration Tree
We extend the objective function of the greedy strategy to
look ahead k measurements, in the enumeration tree strategy.
We build a min-max tree that explores the set of all sensing
locations and all possible measurements that can be obtained,
since the uncertainty depends on both. The tree consists of
two types of nodes at alternate levels (Figure 6): MAX nodes
(u i) represent neighboring robot locations to the current, and
MIN nodes (z i) represent the discretized set of possible measurements. Each node stores an estimate of the target's state
and covariance by simulating EKF updates based on the sensing locations and bearing measurements stored along the
path in the tree. Details are presented in [4].
Once the tree is built, the min-max values for each node
are propagated bottom-up starting with the leaf. The min-

MIN
u1
MAX
z1
MIN

Leaf

...

u2
......

z12
u8

u8
z1

Neigboring
Locations
...

.....

z12

Candidate
Measurements
u8

.....

Figure 6. Min-max tree: u 1, f, u 8 are the neighboring locations
for the robot, and z 1, f, z 12 are candidate bearing measurements.

Localization Experiment
r1

10
r2

0
Y(m)

r3
-10

-20
-30

-40
-40 -30 -20 -10
0
X(m)

Figure 7. Localization experiments with the greedy strategy.
Ellipses shown encompass the 1 - v uncertainty after each
measurement. We use the second measurement to disambiguate
which side the tag lies from bearing obtained at r1 . Bearing
measurements are shown as solid green lines.

max value for the leaf nodes is defined as the determinant of
the simulated posterior covariance matrix stored at that
node. The min-max value for all MAX nodes is the MAX of
min-max values of its children, and that for nonleaf MIN
nodes is MIN of min-max values of its children.
During execution, the robot chooses the MAX node
with the minimum min-max value as the next sensing location at each iteration. The MIN node is chosen as per the
actual bearing obtained. Since we use discrete measurement samples, there might not be a node with bearing
exactly equal to the actual measurement. In addition, there
is uncertainty associated with the position of the robot
itself. Hence, we use the Bhattacharya Distance [18] to find
a MIN node with posterior covariance closest to the covariance after the measurement update.
Simulations and Experiments
We first compared the performance of the three active
localization strategies in simulation. We ran 100 random trials
with the true tag 25 m away from the starting position of the
robot in each trial. A grid side length 3 m was used to generate sensing locations for
three measurements. We
generated noisy bearing
The coverage algorithm
measurements by corrupting the true bearing with
finds a path with length
Gaussian noise (v = 15c).
The mean errors for
at most a constant factor
FIM, greedy, and enumeration tree were 6.30, 5.98,
of the optimal algorithm.
and 5.73 m, and the mean
determinant of the final
covariances were 54.81, 40.59, and 48.36 units, respectively.
The poor performance for the FIM strategy can be attributed to the fact that it is an open-loop strategy that depends
on the initial estimate. Furthermore, it computes locations
that minimize the lower bound on final uncertainty of an
efficient estimator (i.e., an estimator whose variance is equal
to the CRLB). Since EKF is not an efficient filter, there is no
guarantee that it would achieve this lower bound. On the
other hand, the enumeration tree and the greedy strategy
compute the actual covariance of the EKF estimator and
pick the location that would minimize its determinant.
Although the enumeration tree performs better than the
greedy strategy, the performance gains are not significant to
warrant the extra computational time. Hence, we decided to
use the greedy strategy on our system in field experiments.
To test the system, we conducted field trials with a reference
tag submerged in a lake at a known position. The results
from one such trial are shown in Figure 7. Sensing locations
r4, r5, and r6 were obtained by running the greedy strategy.
The resulting 1 - v uncertainty ellipses are shown (in blue)
along with the tag estimates (shown as red crosses). The true
location of the tag is marked by a black star. The final error of
this triangulation was 1.21 m, with 1 - v bounds of 3.3 and
2.7 m in the x- and y-directions, respectively.
september 2013

IEEE ROBOTICS & AUTOMATION MAGAZINE

Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - September 2013