More Web Proxy on the site http://driver.im/

article

An Incremental Self-Deployment Algorithm for Mobile Sensor Networks

Authors:

Maja J. Matarić,

Gaurav S. SukhatmeAuthors Info & Claims

Autonomous Robots, Volume 13, Issue 2

Pages 113 - 126

https://doi.org/10.1023/A:1019625207705

Published: 01 September 2002 Publication History

Abstract

This paper describes an incremental deployment algorithm for mobile sensor networks. A mobile sensor network is a distributed collection of nodes, each of which has sensing, computation, communication and locomotion capabilities. The algorithm described in this paper will deploy such nodes one-at-a-time into an unknown environment, with each node making use of information gathered by previously deployed nodes to determine its deployment location. The algorithm is designed to maximize network ‘coverage' while simultaneously ensuring that nodes retain line-of-sight relationships with one another. This latter constraint arises from the need to localize the nodes in an unknown environment: in our previous work on i>team localization (A. Howard, M.J. Matariý, and G.S. Sukhatme, in i>Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, EPFL, Switzerland, 2002; i>IEEE Transactions on Robotics and Autonomous Systems, 2002) we have shown how nodes can localize themselves by using i>other nodes as landmarks. This paper describes the incremental deployment algorithm and presents the results from an extensive series of simulation experiments. These experiments serve to both validate the algorithm and illuminate its empirical properties.

References

[1]

Balch, T. and Hybinette, M. 2000. Behavior-based coordination of large-scale robot formations. In Proceedings of the Fourth International Conference on Multiagent Systems (ICMAS'00) , Boston, MA, USA, pp. 363-364.

Digital Library

[2]

Bulusu, N., Heidemann, J., and Estrin, D. 2001. Adaptive beacon placement. In Proceedings of the Twenty First International Conference on Distributed Computing Systems (ICDCS-21) , Pheonix, Arizona.

Digital Library

[3]

Burgard, W., Moors, M., Fox, D., Simmons, R., and Thrun, S. 2000. Collaborative multi-robot exploration. In Proc. of IEEE International Conferenceon Robotics and Automation (ICRA) , Vol. 1, pp. 476-481.

[4]

Dedeoglu, G. and Sukhatme, G. S. 2000. Landmark-based matching algorithms for cooperative mapping by autonomous robots. In Distributed Autonomous Robotics Systems , Vol. 4, L.E. Parker, G. W. Bekey, and J. Barhen (Eds.), Springer: Berlin, pp. 251-260.

[5]

Dijkstra, E. W. 1959. A note on two problems in connection with graphs. Numerische Mathematik , 1: 269-271.

Digital Library

[6]

Elfes, A. 1987. Sonar-based real-world mapping and navigation. IEEE Journal of Robotics and Automation , RA-3(3): 249-265.

[7]

Elfes, A. 1990. Occupancy grids: A stochastic spatial representation for active robot perception. In Proceedings of the Sixth Conference on Uncertainty in AI . Morgan Kaufmann: San Mateo, CA.

[8]

Fredslund, J. and Matari¿, M. J. 2001. Robot formations using only local sensing and control. In International Symposium on Computational Intelligence in Robotics and Automation (IEEE CIRA 2001) , Banff, Alberta, Canada.

[9]

Gage, D. W. 1992. Command control for many-robot systems. In AUVS-92, the Nineteenth Annual AUVS Technical Symposium . Hunstville Alabama, USA, pp. 22-24. Reprinted in Unmanned Systems Magazine , Fall 1992, 10(4): 28-34.

[10]

Gerkey, B. P., Vaughan, R. T., Støy, K., Howard, A., Sukhatme, G. S., and Matari¿, M. J. 2001. Most valuable player: A robot device server for distributed control. In Proc. of the IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems (IROS01) , Wailea, Hawaii, pp. 1226-1231.

[11]

Howard, A., Matari¿, M. J., and Sukhatme, G. S. 2002a. An incremental deployment algorithm for mobile robot teams. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems , EPFL, Switzerland, to appear.

[12]

Howard, A., Matari¿, M. J., and Sukhatme, G. S. 2002b. Localization for mobile robot teams using maximum likelihood estimation. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems , EPFL, Switzerland, to appear.

[13]

Howard, A., Matari¿, M. J., and Sukhatme, G. S. 2002c. Mobile sensor network deployment using potential fields: A distributed, scalable solution to the area coverage problem. In Distributed Autonomous Robotic Systems 5: Proceedings of the 6th International Conference on Distributed Autonomous Robotic Systems (DARS02) , Fukuoka, Japan, pp. 299-308.

[14]

Howard, A., Matari¿, M. J., and Sukhatme, G. S. 2002d. Team localization: A maximum likelihood approach. IEEE Transactions on Robotics and Autonomous Systems , submitted May 2002.

Digital Library

[15]

Intanagonwiwat, C., Govindan, R., and Estrin, D. 2000. Directed diffusion: A scalable and robust communication paradigm for sensor networks. In Proceedings of the Sixth Annual International Conference on Mobile Computing and Networks (MobiCOM 2000) , Boston, Massachusetts, pp. 56-67.

Digital Library

[16]

López-Sánchez, M., Esteva, F., de Mántaras, R. L., Sierra, C., and Amat, J. 1998. Map generation by cooperative low-cost robots in structured unknown environments. Autonomous Robots , 5(1): 53-61.

Digital Library

[17]

Lozano-Perez, T. and Mason, M. 1984. Automatic synthesis of fine-motion strategies for robots. International Journal of Robotics Research , 3(1): 3-24.

[18]

O'Rourke, J. 1987. Art Gallery Theorems and Algorithms , Oxford University Press: New York.

Digital Library

[19]

Payton, D., Daily, M., Estkowski, R., Howard, M., and Lee, C. 2001. Pheromone robotics. Autonomous Robots , 11(3): 319-324.

Digital Library

[20]

Rekleitis, I. M., Dudek, G., and Milios, E. E. 2000. Graph-based exploration using multiple robots. In Distributed Autonomous Robotics Systems , Vol. 4, L. E. Parker, G. W. Bekey, and J. Barhen (Eds.), Springer: Berlin, pp. 241-250.

[21]

Scheider, F. E., Wildermuth, D., and Wolf, H.-L. 2000. Motion coordination in formations of multiple mobile robots using a potential field approach. In Distributed Autonomous Robotics Systems , Vol. 4, L. E. Parker, G. W. Bekey, and J. Barhen (Eds.), Springer: Berlin, pp. 305-314.

[22]

Simmons, R., Apfelbaum, D., Burgard, W., Fox, D., Moors, M., Thrun, S., and Younes, H. 2000. Coordination for multi-robot exploration and mapping. In Proc. of the Seventeenth National Conference on Artificial Intelligence (AAAI-2000) , pp. 852-858.

Digital Library

[23]

Thrun, S., Burgard, W., and Fox, D. 2000. A real-time algorithm for mobile robot mapping with applications to multi-robot and 3D mapping. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA2000) , Vol. 1, pp. 321- 328.

[24]

Thrun, S., Fox, D., Burgard, W., and Dellaert, F. 2001. Robust Monte Carlo localization for mobile robots. Artificial Intelligence Journal , 128(1/2): 99-141.

Digital Library

[25]

Vaughan, R. T. 2000. Stage: A multiple robot simulator. Technical Report IRIS-00-393, Institute for Robotics and Intelligent Systems, University of Southern California.

[26]

Winfield, A. F. 2000. Distributed sensing and data collection via broken ad hoc wireless connected networks of mobile robots. In Distributed Autonomous Robotics Systems , Vol. 4, L. E. Parker, G. W. Bekey, and J. Barhen (Eds.), Springer: Berlin, pp. 273-282.

[27]

Yamauchi, B. 1997. Frontier-based approach for autonomous exploration. In Proceedings of the IEEE International Symposium on Computational Intelligence, Robotics and Automation , pp. 146- 151.

Digital Library

[28]

Yamauchi, B., Shultz, A., and Adams, W. 1998. Mobile robot exploration and map-building with continuous localization. In Proceedings of the 1998 IEEE/RSJ International Conference on Robotics and Automation , Vol. 4, San Francisco, USA, pp. 3175- 3720.

[29]

Zelinksy, A. 1992. A mobile robot exploration algorithm. IEEE Transactions on Robotics and Automation , 8(2): 707-717.

Cited By

Rappel OAmir MBruckstein AAgmon NAn BRicci AYeoh W(2023)Stigmergy-based, Dual-Layer Coverage of Unknown RegionsProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598796(1439-1447)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598796
Hasbach JBennewitz M(2022)The design of self-organizing human–swarm intelligenceAdaptive Behavior - Animals, Animats, Software Agents, Robots, Adaptive Systems10.1177/1059712321101755030:4(361-386)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1177/10597123211017550
Mertzios GMichail OSkretas GSpirakis PTheofilatos M(2022)The Complexity of Growing a GraphAlgorithmics of Wireless Networks10.1007/978-3-031-22050-0_9(123-137)Online publication date: 8-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-22050-0_9
Show More Cited By

Index Terms

An Incremental Self-Deployment Algorithm for Mobile Sensor Networks

Recommendations

Deploying sensors for maximum coverage in sensor networks
IWCMC '07: Proceedings of the 2007 international conference on Wireless communications and mobile computing

Sensing coverage is an important issue in wireless mobile sensor networks. The strategy of how to deploy sensor nodes in an environment, especially in unknown large environment, will affect the utility of the network just like the quality of ...
Adaptive Triangular Deployment Algorithm for Unattended Mobile Sensor Networks

In this paper, we present a novel sensor deployment algorithm, called the adaptive triangular deployment (ATRI) algorithm, for large-scale unattended mobile sensor networks. The ATRI algorithm aims at maximizing coverage area and minimizing coverage ...
Connectivity-Guaranteed and Obstacle-Adaptive Deployment Schemes for Mobile Sensor Networks
ICDCS '08: Proceedings of the 2008 The 28th International Conference on Distributed Computing Systems

Mobile sensors can move and self-deploy into a network. While focusing on the problems of coverage, existing deployment schemes mostly over-simplify the conditions for network connectivity: they either assume that the communication range is large enough ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Autonomous Robots

Autonomous Robots Volume 13, Issue 2

September 2002

72 pages

ISSN:0929-5593

Issue’s Table of Contents

Copyright © Copyright © 2002 Kluwer Academic Publishers.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 September 2002

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

112
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Rappel OAmir MBruckstein AAgmon NAn BRicci AYeoh W(2023)Stigmergy-based, Dual-Layer Coverage of Unknown RegionsProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598796(1439-1447)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598796
Hasbach JBennewitz M(2022)The design of self-organizing human–swarm intelligenceAdaptive Behavior - Animals, Animats, Software Agents, Robots, Adaptive Systems10.1177/1059712321101755030:4(361-386)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1177/10597123211017550
Mertzios GMichail OSkretas GSpirakis PTheofilatos M(2022)The Complexity of Growing a GraphAlgorithmics of Wireless Networks10.1007/978-3-031-22050-0_9(123-137)Online publication date: 8-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-22050-0_9
Banfi JLi ABasilico NRekleitis IAmigoni F(2021)Asynchronous multirobot exploration under recurrent connectivity constraints2016 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA.2016.7487763(5491-5498)Online publication date: 10-Mar-2021
https://dl.acm.org/doi/10.1109/ICRA.2016.7487763
Hung PVinh TNgo T(2021)Distributed coverage control for networked multi-robot systems in any environments2016 IEEE International Conference on Advanced Intelligent Mechatronics (AIM)10.1109/AIM.2016.7576911(1067-1072)Online publication date: 11-Mar-2021
https://dl.acm.org/doi/10.1109/AIM.2016.7576911
Zerbel NTumer KEl Fallah Seghrouchni ASukthankar GAn BYorke-Smith N(2020)The Power of SuggestionProceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3398761.3398945(1602-1610)Online publication date: 5-May-2020
https://dl.acm.org/doi/10.5555/3398761.3398945
Chen XRuiz CZeng SGao LPurohit ACarpin SZhang P(2020)H-DrunkWalkACM Transactions on Sensor Networks10.1145/338209416:2(1-27)Online publication date: 17-Apr-2020
https://dl.acm.org/doi/10.1145/3382094
Poudel PSharma G(2020)Fast Uniform Scattering on a Grid for Asynchronous Oblivious RobotsStabilization, Safety, and Security of Distributed Systems10.1007/978-3-030-64348-5_17(211-228)Online publication date: 18-Nov-2020
https://dl.acm.org/doi/10.1007/978-3-030-64348-5_17
Amir MBruckstein AElkind EVeloso MAgmon NTaylor M(2019)Minimizing Travel in the Uniform Dispersal Problem for Robotic SensorsProceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3306127.3331682(113-121)Online publication date: 8-May-2019
https://dl.acm.org/doi/10.5555/3306127.3331682
Nwadiugwu WKim DLee J(2019)Energy-efficient real-time deployment of mobile sensors in disaster-prone locationInternational Journal of Communication Networks and Distributed Systems10.1504/ijcnds.2019.10191823:3(307-327)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1504/ijcnds.2019.101918
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents