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

Article

Collaborative Exploration of Unknown Environments with Teams of Mobile Robots

Authors:

Wolfram Burgard,

Frank SchneiderAuthors Info & Claims

Revised Papers from the International Seminar on Advances in Plan-Based Control of Robotic Agents,

Pages 52 - 70

Published: 21 October 2001 Publication History

Abstract

In this paper we consider the problem of exploring an unknown environment by a team of robots. As in single-robot exploration the goal is to minimize the overall exploration time. The key problem to be solved in the context of multiple robots is to choose appropriate target points for the individual robots so that they simultaneously explore different regions of the environment. We present an approach for the coordination of multiple robots which, in contrast to previous approaches, simultaneously takes into account the cost of reaching a target point and its utility. The utility of a target point is given by the size of the unexplored area that a robot can cover with its sensors upon reaching that location. Whenever a target point is assigned to a specific robot, the utility of the unexplored area visible from this target position is reduced for the other robots. This way, a team of multiple robots assigns different target points to the individual robots. The technique has been implemented and tested extensively in real-world experiments and simulation runs. The results given in this paper demonstrate that our coordination technique significantly reduces the exploration time compared to previous approaches.

References

[1]

S. Albers and M.R. Henzinger. Exploring unknown environments. SIAM Journal on Computing, 29:1164-1188, 2000.

[2]

S. Albers, K. Kursawe, and S. Schuierer. Exloring unknown environments with obstacles. In Proc. of the 10th Symposium on Discrete Algorithms, 1999.

[3]

D. Apostolopoulos, L. Pedersen, B. Shamah, K. Shillcutt, M.D. Wagner, and W.R.L. Whittaker. Robotic antarctic meteorite search: Outcomes. In Proc. of the IEEE International Conference on Robotics and Automation (ICRA), pages 4174-4179, 2001.

[4]

T. Balch and R.C. Arkin. Communication in reactive multiagent robotic systems. Journal of Autonomous Robots, 1(1):27-52, 1994.

[5]

R.E. Bellman. Dynamic Programming. Princeton University Press, Princeton, NJ, 1957.

[6]

M. Bender and D. Slonim. The power of team exploration: Two robots can learn unlabeled directed graphs. In Proc. of the 35rd Annual Symposium on Foundations of Computer Science, pages 75-85, 1994.

[7]

A. Billard, A.J. Ijspeert, and A. Martinoli. A multi-robot system for adaptive exploration of a fast changing environment: Probabilistic modelling and experimental study. Connection Science, 11(3/4):357-377, 2000.

[8]

W. Burgard, M. Moors, D. Fox, R. Simmons, and S. Thrun. Collaborative multirobot exploration. In Proc. of the IEEE International Conference on Robotics and Automation (ICRA), 2000.

[9]

Y.U. Cao, A.S. Fukunaga, and A.B. Khang. Cooperative mobile robotics: Antecedents and directions. Autonomous Robots, 4, 1997.

[10]

J.A. Castellanos, J.M.M. Montiel, J. Neira, and J.D. Tardós. The SPmap: A probabilistic framework for simultaneous localization and map building. IEEE Transactions on Robotics and Automation, 15(5):948-953, 1999.

[11]

H. Choset. Topological simultaneous localization and mapping (slam): Toward exact localization without explicit localization. IEEE Transactions on Robotics and Automation, 17(2), April 2001.

[12]

W. Cohen. Adaptive mapping and navigation by teams of simple robots. Journal of Robotics and Autonomous Systems, 18:411-434, 1996.

[13]

X. Deng, T. Kameda, and C. Papadimitriou. How to learn in an unknown environment. In Proc. of the 32nd Symposium on the Foundations of Comp. Sci., pages 298-303. IEEE Computer Society Press, Los Alamitos, CA, 1991.

[14]

X. Deng and C. Papadimitriou. How to learn in an unknown environment: The rectilinear case. Journal of the ACM, 45(2):215-245, 1998.

[15]

G. Dissanayake, H. Durrant-Whyte, and T. Bailey. A computationally efficient solution to the simultaneous localisation and map building (SLAM) problem. Working notes of ICRA 2000 Workshop W4: Mobile Robot Navigation and Mapping, April 2000.

[16]

G. Dudek, M. Jenkin, E. Milios, and D. Wilkes. Robotic exploration as graph construction. IEEE Transactions on Robotics and Automation, 7(6):859-865, 1991.

[17]

G. Dudek, M. Jenkin, E. Milios, and D. Wilkes. A taxonomy for multi-agent robotics. Autonomous Robots, 3(4), 1996.

[18]

T. Edlinger and E. von Puttkamer. Exploration of an indoor-environment by an autonomous mobile robot. In Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 1994.

[19]

H. Endres, W. Feiten, and G. Lawitzky. Field test of a navigation system: Autonomous cleaning in supermarkets. In Proc. of the IEEE International Conference on Robotics and Automation (ICRA), 1998.

[20]

M. Fontan and M. Mataric. Territorial multi-robot task division. IEEE Transactions on Robotics and Automation, 14(5), 1998.

[21]

D. Fox, W. Burgard, H. Kruppa, and S. Thrun. Collaborative multi-robot localization. In Proc. of the 23rd German Conference on Artificial Intelligence. Springer Verlag, 1999.

[22]

D. Goldberg and M. Mataric. Interference as a tool for designing and evaluating multi-robot controllers. Journal of Robotics and Autonomous Systems, 8:637-642, 1997.

[23]

H.H. González-Baños, E. Mao, J.C. Latombe, T.M. Murali, and A. Efrat. Planning robot motion strategies for efficient model construction. In Proc. Intl. Symp. on Robotics Research (ISRR), 1999.

[24]

R. Grabowski, L.E. Navarro-Serment, C.J.J. Paredis, and P.K. Khosla. Heterogeneous teams of modular robots for mapping and exploration. Journal of Autonomous Robots, 8(3):293-308, 2000.

[25]

D. Guzzoni, A. Cheyer, L. Julia, and K. Konolige. Many robots make short work. AI Magazine, 18(1):55-64, 1997.

[26]

D.F. Hougen, S. Benjaafar, J.C. Bonney, J.R. Budenske, M. Dvorak, M. Gini, H. French, D.G. Krantz, P.Y. Li, F. Malver, B. Nelson, N. Papanikolopoulos, P.E. Rybski, S.A. Stoeter, R. Voyles, and K.B. Yesin. A miniature robotic system for reconnaissance and surveillance. In Proc. of the IEEE International Conference on Robotics and Automation (ICRA), 2000.

[27]

R.A. Howard. Dynamic Programming and Markov Processes. MIT Press and Wiley, 1960.

[28]

Y. Huang, Z. Cao, S. Oh, E. Kattan, and E. Hall. Automatic operation for a robot lawn mower. In SPIE Conference on Mobile Robots, volume 727, pages 344-354, 1986.

[29]

D. Jung and A. Zelinksy. An architecture for distributed cooperative planning in a behaviour-based multi-robot system. Journal of Robotics and Autonomous Systems, 26(2-3):149-174, 1999.

[30]

S. Koenig, B. Szymanski, and Y. Liu. Efficient and inefficient ant coverage methods. Annals of Mathematics and Artificial Intelligence, In Print.

[31]

S. Koenig, C. Tovey, and W. Halliburton. Greedy mapping of terrain. In Proc. of the IEEE International Conference on Robotics and Automation (ICRA), 2001.

[32]

B. Kuipers and Y.-T. Byun. A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations. Journal of Robotics and Autonomous Systems, 8:47-63, 1991.

[33]

D. Kurabayashi, J. Ota, T. Arai, and E. Yoshida. Cooperative sweeping by multiple mobile robots. In Proc. of the IEEE International Conference on Robotics and Automation (ICRA), pages 1744-1749, 1996.

[34]

R. Kurazume and N. Shigemi. Cooperative positioning with multiple robots. In Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 1994.

[35]

D. Lee and M. Recce. Quantitative evaluation of the exploration strategies of a mobile robot. International Journal of Robotics Research, 16(4):413-447, 1997.

[36]

J.J. Leonard and H.J.S. Feder. A computationally efficient method for large-scale concurrent mapping and localization. In J. Hollerbach and D. Koditschek, editors, Proceedings of the Ninth International Symposium on Robotics Research, 1999.

[37]

S. Lumelsky, S. Mukhopadhyay, and K. Sun. Dynamic path planning in sensor-based terrain acquisition. IEEE Transactions on Robotics and Automation, 6(4):462-472, 1990.

[38]

M.J. Mataric and G. Sukhatme. Task-allocation and coordination of multiple robots for planetary exploration. In Proc. of the International Conference on Advanced Robotics, 2001.

[39]

S.J. Moorehead, R. Simmons, and W.L. Whittaker. Autonomous exploration using multiple sources of information. In Proc. of the IEEE International Conference on Robotics and Automation (ICRA), 2001.

[40]

M. Moors. Koordinierte Multi-Robot Exploration. Master's thesis, Department of Computer Science, University of Bonn, 2000. In German.

[41]

H.P. Moravec. Sensor fusion in certainty grids for mobile robots. AI Magazine, pages 61-74, Summer 1988.

[42]

N. Rao, S. Hareti, W. Shi, and S. Iyengar. Robot navigation in unknown terrains: Introductory survey of non-heuristic algorithms. Technical Report ORNL/TM- 12410, Oak Ridge National Laboratory, 1993.

[43]

I. Rekleitis, G. Dudek, and E. Milios. Multi-robot exploration of an unknown environment, efficiently reducing the odometry error. In Proc. of International Joint Conference in Artificial Intelligence (IJCAI), 1997.

[44]

I. Rekleitis, G. Dudek, and E. Milios. Accurate mapping of an unknown world and online landmark positioning. In Proc. of Vision Interface (VI), 1998.

[45]

I. Rekleitis, R. Sim, G. Dudek, and E. Milios. Collaborative exploration for the construction of visual maps. In Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2001.

[46]

N. Roy and G. Dudek. Collaborative robot exploration and rendezvous: Algorithms, performance bounds and observations. Journal of Autonomous Robots, 11(2):117-136, 2001.

[47]

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

[48]

M. Simoncelli, G. Zunino, H.I. Christensen, and K. Lange. Autonomous pool cleaning: Self localization and autonomous navigation for cleaning. Journal of Autonomous Robots, 9(3):261-270, 2000.

[49]

K. Singh and K. Fujimura. Map making by cooperating mobile robots. In Proc. of the IEEE International Conference on Robotics and Automation (ICRA), pages 254-259, 1993.

[50]

A. Stentz. Optimal and efficient path planning for partially-known environments. In Proc. of the IEEE International Conference on Robotics and Automation (ICRA), pages 3310-3317, 1994.

[51]

C.J. Taylor and D.J. Kriegman. Exloration strategies for mobile robots. In Proc. of the IEEE International Conference on Robotics and Automation (ICRA), pages 248-253, 1993.

[52]

S. Thrun. A probabilistic online mapping algorithm for teams of mobile robots. International Journal of Robotics Research, 20(5):335-363, 2001.

[53]

B. Yamauchi. Frontier-based exploration using multiple robots. In Proceedings of the Second International Conference on Autonomous Agents, pages 47-53, 1998.

[54]

B. Yamauchi, A. Schultz, and W. Adams. Integrating exploration and localization for mobile robots. Adaptive Systems, 7(2), 1999.

Cited By

Belbachir ABenabid S(2018)An efficient cooperative exploration strategy for wireless sensor networkIntelligent Service Robotics10.1007/s11370-018-0249-x11:3(237-246)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1007/s11370-018-0249-x
Wu QMiao C(2013)CuriosityACM Computing Surveys10.1145/2543581.254358546:2(1-26)Online publication date: 27-Dec-2013
https://dl.acm.org/doi/10.1145/2543581.2543585
Bautin ASimonin OCharpillet F(2012)MinPosProceedings of the 5th international conference on Intelligent Robotics and Applications - Volume Part II10.1007/978-3-642-33515-0_49(496-508)Online publication date: 3-Oct-2012
https://dl.acm.org/doi/10.1007/978-3-642-33515-0_49
Show More Cited By

Collaborative Exploration of Unknown Environments with Teams of Mobile Robots
1. Computer systems organization
  1. Embedded and cyber-physical systems
2. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Planning and scheduling

Recommendations

Autonomous Mobile Robots in Unknown Outdoor Environments
Sensor-Based Motion Planning of Wheeled Mobile Robots in Unknown Dynamic Environments

This paper presents a new sensor-based online method for generating collision-free paths for differential-drive wheeled mobile robots pursuing a moving target amidst dynamic and static obstacles. At each iteration, the set of all collision-free ...
Fuzzy Motion Planning of Mobile Robots in Unknown Environments

A fuzzy algorithm is proposed to navigate a mobile robot from a given initial configuration to a desired final configuration in an unknown environment filled with obstacles. The mobile robot is equipped with an electronic compass and two optical ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Revised Papers from the International Seminar on Advances in Plan-Based Control of Robotic Agents,

October 2001

289 pages

ISBN:3540001689

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 21 October 2001

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Belbachir ABenabid S(2018)An efficient cooperative exploration strategy for wireless sensor networkIntelligent Service Robotics10.1007/s11370-018-0249-x11:3(237-246)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1007/s11370-018-0249-x
Wu QMiao C(2013)CuriosityACM Computing Surveys10.1145/2543581.254358546:2(1-26)Online publication date: 27-Dec-2013
https://dl.acm.org/doi/10.1145/2543581.2543585
Bautin ASimonin OCharpillet F(2012)MinPosProceedings of the 5th international conference on Intelligent Robotics and Applications - Volume Part II10.1007/978-3-642-33515-0_49(496-508)Online publication date: 3-Oct-2012
https://dl.acm.org/doi/10.1007/978-3-642-33515-0_49
Macedo LTavares MGaspar PCardoso A(2011)Uncertainty and novelty-based selective attention in the collaborative exploration of unknown environmentsProceedings of the 15th Portugese conference on Progress in artificial intelligence10.5555/2051115.2051163(521-535)Online publication date: 10-Oct-2011
https://dl.acm.org/doi/10.5555/2051115.2051163
Nieuwenhuisen MSchulz DBehnke S(2011)Exploration strategies for building compact maps in unbounded environmentsProceedings of the 4th international conference on Intelligent Robotics and Applications - Volume Part I10.1007/978-3-642-25486-4_4(33-43)Online publication date: 6-Dec-2011
https://dl.acm.org/doi/10.1007/978-3-642-25486-4_4
Al-Khawaldah MLivatino SLee D(2010)Weight parameters tuning for frontier-based cooperating robots explorationProceedings of the 9th WSEAS international conference on Signal processing, robotics and automation10.5555/1807817.1807837(97-102)Online publication date: 20-Feb-2010
https://dl.acm.org/doi/10.5555/1807817.1807837
Al Khawaldah MLivatino SMing L(2010)Wall-following exploration with two cooperating mobile robotsProceedings of the 9th WSEAS international conference on Signal processing, robotics and automation10.5555/1807817.1807834(80-85)Online publication date: 20-Feb-2010
https://dl.acm.org/doi/10.5555/1807817.1807834
Macedo LCardoso A(2004)Exploration of Unknown Environments with Motivational AgentsProceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems - Volume 110.5555/1018409.1018764(328-335)Online publication date: 19-Jul-2004
https://dl.acm.org/doi/10.5555/1018409.1018764

View Options

View options

Media

Figures

Other

Tables

View Table of Contents