Research Abstracts - 2006

Passive Mobile Robot Localization within a Fixed Beacon Field

Carrick Detweiler, John Leonard, Daniela Rus & Seth Teller

Introduction

We are working on an intuitive geometric algorithm for the localization of mobile nodes in networks of sensors and robots using range-only or angle-only measurements. The algorithm is a minimalistic approach to localization and tracking when dead reckoning is too inaccurate to be useful. The only knowledge required about the mobile node is its maximum speed. Geometric regions are formed and grown to account for the motion of the mobile node. New measurements introduce new constraints which are propagated back in time to refine previous localization regions. The mobile robots are passive listeners while the sensor nodes actively broadcast making the algorithm scalable to many mobile nodes while maintaining the privacy of individual nodes. We prove that the localization regions found are optimal--that is, they are the smallest regions which must contain the mobile node at that time. We prove that each new measurement requires quadratic time in the number of measurements to update the system, however, we demonstrate experimentally that this can be reduced to constant time.

Research Context

Most current localization methods make use of range or angle measurements to other nodes (pre-deployed beacons or other robots) to constrain dead reckoning error growth. We are interested in the class of mobile agents which do not have dead reckoning or it is too inaccurate to be useful. This includes the important case of passively tracking a non-cooperative target. The method is also applicable to low cost underwater robots, such as AMOUR [1], and other non-robotic mobile agents, such as animals and people.

Algorithm Intuition: Range-Only Localization

Here we will describe the intuition behind the range-only version of the algorithm while omitting the details due to lack of space. Figure 1 shows critical steps in the range-only localization of mobile Node m. Node m is moving through a field of localized static nodes (Nodes a, b, c) along the trajectory indicated by the dotted line.

(a)	(b)	(c)
(d)	(e)	(f)

At time t Node m passively obtains a range to Node a. This allows Node m to localize itself to the circle indicated in Figure 1(a). At time t+1 Node m has moved along the trajectory as shown in Figure 1(b). It expands its localization estimation to the annulus in Figure 1(b). Node m then enters the communication range of Node b and obtains a ranging to Node b (see Figure 1(c)). Next, Node m intersects the circle and annulus to obtain a localization region for time t+1 as indicated by the bold red arcs in Figure 1(d).

The range taken at time t+1 can be used to improve the localization at time t as shown in Figure 1(e). The arcs from time t+1 are expanded to account for all locations the mobile node could have come from. This is then intersected with the range taken at time t to obtain the refined location region illustrated by the bold blue arcs. Figure 1(f) shows the final result. Note that for times t and t+1 there are two possible location regions. This is because two range measurements do not provide sufficient information to fully constrain the system. Range measurements from other nodes will quickly eliminate this.

Optimality

We prove that the localization regions that are found are optimal. That is, they are the smallest possible regions that must contain the true location of the mobile node. We additionally prove that each new measurement requires quadratic time in the number of measurements to update the system, however, we demonstrate experimentally that this can be reduced to constant time. The details of this can be found in upcoming publications.

Future Work

We are currently in the process of performing experiments with our underwater sensor network and robot [1] to validate our algorithm.

References

[1] Vasilescu, I., Kotay, K., Rus, D., Dunbabin, M., and Corke, P. Data collection, storage, and retrieval with an underwater sensor network. In Sen-Sys '05: Proceedings of the 3rd international conference on Embedded networked sensor systems (New York, NY, USA, 2005), ACM Press, pp. 154-165.