In this paper we discuss how a network of sensors and robots can cooperate to solve important robotics problems such as localization and navigation. We use a robot to localize sensor nodes, and we then use these localized nodes to navigate robots and humans through the sensorized space. We explore these novel ideas with results from two large-scale sensor network and robot experiments involving 50 motes, two types of flying robot: an autonomous helicopter and a large indoor cable array robot, and a human-network interface. We present the distributed algorithms for localization, geographic routing, path definition and incremental navigation. We also describe how a human can be guided using a simple hand-held device that interfaces to this same environmental infrastructure.
Get full access to this article
View all access options for this article.
References
1.
Agre, J. and Clare, L. 2000. An integrated architecture for cooperative sensing networks . IEEE Computer33: 106-108 .
2.
Basagni, S., Chlamtac, I., and Syrotiuk, V. R. 1998. A distance routing algorithm for mobility (dream) . Proceedings of the 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM), Dallas, TX, October 25-30, pp. 76-84 .
3.
Basch, J., Guibas, L. J., and Zhang, L. 1997. Proximity problems on moving points . Proceedings of the 13th Symposium of Computational Geometry, Comp Geom 1997: Nice, France; the Galsyan paper appeared in the following conference: Information Processing in Sensor Networks (IPSN-2004), Berkeley, CA, pp. 344-351 .
4.
Batalin, M. and Sukhatme, G. 2005. Coverage, exploration and deployment by a mobile robot and communication network . Journal of Robotic Systems, Telecommunication Systems Journal, Special Issue on Wireless Sensor Networks, 26(2): 181-196 (2004).
5.
Bulusu, N., Heidemann, J., and Estrin, D. 2001. Adaptive beacom placement . Proceedings of the 21st Conference on Distributed Computing Systems, Phoenix, AZ.
6.
Buskey, G., Corke, P., Roberts, J., Ridley, P., and Wyeth, G. 2003. The CSIRO autonomous helicopter project . Experimental Robotics VIII, B. Siciliano and P. Dario, editors, Vol.5of STAR, Springer-Verlag, Berlin.
7.
Chang, J.-H. and Tassiulas, L. 1999. Routing for maximum system lifetime in wireless ad hoc networks . Proceedings of the 37th Annual Allerton Conference on Communication, Control and Computing, Monticello, IL.
8.
Chang, J.-H. and Tassiulas, L. 2000a. Energy conserving routing in wireless ad hoc networks . Proceedings of IEEE INFOCOM, Tel Aviv, Israel, March.
9.
Chang, J.-H. and Tassiulas, L. 2000b. Fast approximate algorithms for maximum lifetime routing in wireless ad hoc networks . Proceedings of NETWORKING 2000, Lecture Notes in Computer Science, Vol. 1815, Springer-Verlag, Berlin, pp. 702-713 .
10.
Chen, J. K. Y. and Hudson, R. 2002. Source localization and beamforming . IEEE Signal Processing Magazine19: 30-39 .
11.
Chen, B., Jamieson, K., Balakrishnan, H., and Morris, R. 2001. Span: an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks . Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MOBICOM), Rome, Italy, July 16-21.
12.
Cheng, C., Riley, R., Kumar, S. P. R., and Garcia-Luna-Aceves, J. J. 1989. A loop-free extended Bellman-Ford routing protocol without bouncing effect . Computer Communication Review19: 224-236 .
13.
Corke, P., Peterson, R., and Rus, D. 2003. Networked robots: flying robot navigation with a sensor net . Proceedings of the 2003 International Symposium on Robotics Research, Siena, Italy.
14.
Das, A., Kantor, G., Kumar, V., Pereira, G., Peterson, R., Rus, D., Singh, S., and Spletzer, J. 2003. Distributed search and rescue with robot and sensor teams . International Conference on Field and Service Robotics, Japan, July 14-16.
15.
Estrin, D., Govindan, R., Heidemann, J., and Kumar, S. 1999. Next century challenges: scalable coordination in sensor networks . Proceedings of theAnnual International Conference on Mobile Computing and Networking (MobiCom), Seattle, WA, August.
16.
Galstyan, A., Krishnamachari, B., and Lerman, K. 2003. Distributed on-line localization in sensor networks using a moving target . ACM SENSSYS.
17.
Guibas, L. 2002. Sensing, tracking, and reasoning with relations . IEEE Signal Processing Magazine19: 73-85 .
18.
Gupta, P. and Kumar, P. R. 1998. Critical power for asymptotic connectivity in wireless networks . Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor ofW. H. Fleming, Birkhäuser, Boston, pp. 547-566 .
19.
Haas, Z. J. 1997. A new routing protocol for the reconfigurable wireless network . Proceedings of the 1997 IEEE 6th International Conference on Universal Personal Communications (ICUPC’97), San Diego, CA, October, pp. 562-566 .
20.
Hill, J., Szewczyk, R., Woo, A., Hollar, S., Culler, D., and Pister, K. 2000. System architecture directions for network sensors . Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), Cambridge, MA, November 12-15.
21.
Hill, J., Bounadonna, P., and Culler, D. 2001. Active message communication for tiny network sensors . INFOCOM 2001, 20th Annual Joint Conference of the IEEE Computer and Communications Societies, Anchorage, Alaska, April 22-26.
22.
Johnson, D. B. and Maltz, D.A. 1996. Dynamic source routing in ad hoc wireless networks. Mobile Computing, T. Imielinski and H. Korth, editors, Kluwer Academic, Dordrecht , pp. 153-181.
23.
Karlin, S. and Taylor, H. M. 1975. A First Course in Stochastic Processes, 2nd edn, Academic Press, New York .
24.
Karp, B. and Kung, H. 2000. GPSR: Greedy Perimeter Stateless Routing for wireless networks . Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MOBICOM), Boston MA, August 6-11.
25.
Ko, Y. B. and Vaidya, N. H. 1998. Location-aided routing (LAR) in mobile ad hoc networks . Proceedings of the 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM), Dallas, TX, October 25-30, pp. 66-75 .
26.
Kotay, K., Peterson, R., and Rus, D. 2005. Experiments with robots and sensor networks for mapping and navigation . Proceedings of the 5th International Conference on Field and Service Robotics (FSR05), North Queensland, Australia, July.
27.
Kotz, D., Gray, R., Nog, S., Rus, D., Chawla, S., and Cybenko, G. 1997. Agent Tcl: targeting the needs of mobile computers . IEEE Internet Computing1: 58-67 .
28.
Kotz, D., Newport, C., Gray, R. S., Liu, J., Yuan, Y., and Elliott, C. 2004. Experimental evaluation of wireless simulation assumptions . Proceedings of the ACM/IEEE International Symposium on Modeling, Analysis and Simulation ofWireless and Mobile Systems (MSWiM), Venice, Italy, October 4-6, pp. 78-82 .
29.
Li, Q., Aslam, J., and Rus, D. 2001. On-line power-aware routing in wireless ad hoc networks . Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MOBICOM), Rome, Italy, July 16- 21, pp. 97-107 .
30.
Li, D., Wong, K., Hu, Y. H., and Sayeed, A. 2002. Detection, classification, and tracking of targets . IEEE Signal Processing Magazine19: 17-29 .
31.
Li, Q., de Rosa, M., and Rus, D. 2003. Distributed algorithms for guiding navigation across a sensor net . Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MobiCom), San Diego, CA, September 14-19.
32.
Murthy, S. and Garcia-Luna-Aceves, J. J. 1996. An efficient routing protocol for wireless networks . ACM/Baltzer Journal on Mobile Networks and Applications Vol. MANET, pp. 183-197 .
33.
Okino, C. and Cybenko, G. 1999. Modeling and analysis of active messages in volatile networks . Proceedings of the 37thAllerton Conference on Communication, Control, and Computing, Monticello, IL, September.
34.
Peterson, R. and Rus, D. 2002. Interacting with a sensor network . Proceedings of the 2002 Australian Conference on Robotics and Automation, Auckland, NZ, November.
35.
Pottie, G. J. 1998. Wireless sensor networks . IEEE Information Theory Workshop, San Diego, CA, pp. 139-140 .
36.
Pradhan, S., Kusuma, J., and Ramchandran, K. 2002. Distributed compression in a dense microsens or network . IEEE Signal Processing Magazine19: 51-60 .
37.
Ramanathan, R. and Hain, R. 2000. Topology control of multihop wireless networks using transmit power adjustment . INFOCOM 2000, Tel Aviv, Israel, March.
38.
Rappaport, T. and Sandhu, S. 1994. Radio-wave propagation for emerging wireless personal-communication systems . IEEE Antennas and Propagation Magazine36: 14-24 .
Simmons, R. and James, D. 2001. Inter-Process Communication, 3.4 edn, Carnegie-Mellon University .
41.
Singh, S., Woo, M., and Raghavendra, C. S. 1998. Power-aware routing in mobile ad hoc networks . Proceedings of the 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking, Dallas, TX, October, pp. 181-190 .
42.
Wattenhofer, R., Li, L., Bahl, P., and Wang, Y. 2001. Distrib. topology control for power efficient operation in multihop wireless ad hoc networks . INFOCOM 2001, 20th Annual Joint Conference of the IEEE Computer and Communications Societies, Anchorage, Alaska, April 22-26.
43.
Xu, Y., Heidemann, J., and Estrin, D. 2001. Geography-informed energy conservation for ad hoc routing . Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MOBICOM), Rome, Italy, July 16-21.
44.
Zhao, F., Shin, J., and Reich, J. 2002. Information-driven dynamic sensor collaboration for tracking applications . IEEE Signal Processing Magazine19: 61-72 .
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
