Connectivity-based Localization in Robot Networks (2009)
Consider a small team of autononomous robots, each equipped with a radio, that are deployed in an ad-hoc fashion and whose goal it is to act as signal relay nodes to form a temporary, adaptive, and highly robust communication network. To perform this type of self-optimization and self-healing, relative localization (i.e. knowing direction and distance to every other robot in the network) is necessary. In a sense, the problem is similar to the one studied in ad-hoc sensor networks. The key differences are that (1) anchor nodes with known locations are not available; that (2) the connectivity graph is very sparse, because of a comparatively small number of nodes involved; and that (3) the communication nodes are actually mobile robots such that apart from location we also have to estimate the directions to other nodes (which can not be obtained from a single time slice). To solve this problem, we propose a global approach that exploits the mobility of the robots to obtain multiple connectivity measurements over a small time window. Together with the odometry of individual robots, we then try to estimate underlying locations that best explain the observerd connectivity data by minimizing a suitable stress function. Through simulation of a concrete real-world scenario we show that our approach performs reasonably well with as few as ten robots. We examine its performance both under outdoor and indoor conditions (i.e. uniform and non-uniform signal propagation). In addition, we also consider the case where we are able to observe the distance between connected tobots, which further improves accuracy substantially.
In International Workshop on Robotic Wireless Sensor Networks (IEEE DCOSS '09), June 2009.

Mazda Ahmadi Formerly affiliated Ph.D. Student mazda [at] cs utexas edu
Tobias Jung Postdoctoral Alumni tjung [at] ulg ac be
Peter Stone Faculty pstone [at] cs utexas edu