
Research
Abstracts  2006 
Passive Mobile Robot Localization within a Fixed Beacon FieldCarrick Detweiler, John Leonard, Daniela Rus & Seth TellerIntroductionWe are working on an intuitive geometric algorithm for the localization of mobile nodes in networks of sensors and robots using rangeonly or angleonly 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 optimalthat 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 ContextMost current localization methods make use of range or angle measurements to other nodes (predeployed 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 noncooperative target. The method is also applicable to low cost underwater robots, such as AMOUR [1], and other nonrobotic mobile agents, such as animals and people. Algorithm Intuition: RangeOnly LocalizationHere we will describe the intuition behind the rangeonly version of the algorithm while omitting the details due to lack of space. Figure 1 shows critical steps in the rangeonly 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.
Figure 1: Example of the rangeonly localization algorithm. 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. OptimalityWe 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 WorkWe 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 SenSys '05: Proceedings of the 3rd international conference on Embedded networked sensor systems (New York, NY, USA, 2005), ACM Press, pp. 154165. 

