Novosibirsk State University Journal of Information Technologies
Scientic Journal

ISSN 2410-0420 (Online), ISSN 1818-7900 (Print)

Switch to
Russian

All Issues >> Contents: Volume 14, Issue No 2 (2016)

Path Planning for Multi-Robot Exploration Using Frontier Space Clusterization
Dmitriy Evgenevich Kuzakov, Mihail Stanislavovich Diakov, Mikhail Mikhailovich Lavrentyev

Novosibirsk State University
SoftLab-NSK Co. Ltd
Institute of Automation and Electrometry SB RAS

Abstract
In this paper, a path planning algorithm for multi-robot exploration is presented. It is developed for exploration in initially unknown areas. The algorithm is based on a novel method of choosing exploration targets. This method uses clusterization of frontier space – part of explored map space which is situated on its border with an unexplored part. Every robot is being associated with a cluster. Then the exploration target for the robot is chosen from associated cluster with a priority function. This function defines utility for choosing a map cell considering traverse cost, information gain and distance to other robots' targets.

Key Words
multi-robot exploration, frontier space clusterization, frontier-based algorithm

How to cite:
Kuzakov D. E., Diakov M. S., Lavrentyev M. M. Path Planning for Multi-Robot Exploration Using Frontier Space Clusterization // Vestnik NSU Series: Information Technologies. - 2016. - Volume 14, Issue No 2. - P. 59-71. - ISSN 1818-7900. (in Russian).

Full Text in Russian

Available in PDF

References
1. Gabrielly Y., Rimon E. Spanning-tree based coverage of continuous areas by a mobile robot // Annals of Mathematics and Artificial Intelligence. 2001. No. 31. P. 77–98.
2. Hazon N., Kaminka G. On redundancy, efficiency and robustness in coverage for multi-robot // Robot Autonomous System. 2008. No. 56. P. 1102–1114.
3. Murphy L., Newman P. Using incomplete online metric maps for topological exploration with the gap navigation tree // IEEE International Conference on Robotics and Automation, 2008. P. 2717–2722.
4. Santosh D., Achar S., Jawahar C. V. Autonomous image-based exploration for mobile robot navigation // IEEE International Conference on Robotics and Automation, 2008. P. 47–60.
5. Andries M., Charpillet F. Multi-robot exploration of unknown environments with identication of exploration completion and post-exploration rendezvous using ant algorithms // IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). 2013. P. 5571–5578.
6. Liu T. M., Lyons D. M. Leveraging Area Bounds Information for Autonomous Multi-Robot Exploration.
7. Senthilkumar K., Bharadwaj K. Multi-robot terrain coverage by constructing multiple spanning trees simultaneously // International Journal of Robotics and Automation. 2010. Vol. 3. No. 25. P. 195–203.
8. Lau H. Behavioural approach for multi-robot exploration // Proc. of the 2003 Australasian Conference on Robotics and Automation, 2003.
9. Yamauchi B. A frontier-based approach for autonomous exploration // IEEE International Symposium on Computational Intelligence in Robotics and Automation, 1997. P. 146–151.
10. Gonzalez-Banos H. H., Latombe J. C. Navigation strategies for exploring indoor environments // The International Journal of Robotics Research. 2002. Vol. 21, 10–11. P. 829–848.
11. Marjovi A., Marques L. Multi-robot topological exploration using olfactory cues // Distributed Autonomous Robotic Systems. 2013. P. 47–60.
12. Burgard W., Moors M., Fox D., Simmons R., Thrun S. Collaborative multi-robot exploration // IEEE International Conference on Robotics and Automation. 2000. Vol. 1. P. 476–481.
13. Al Khawaldah M., Al-Khedher M., Al-Adwan I., Al Rawashdeh A. An Autonomous Exploration Strategy for Cooperative Mobile Robots // Journal of Software Engineering and Applications. 2014. Vol. 7. No. 3. P. 142–149.
14. Solanas A., Garcia M. A. Coordinated multi-robot exploration through unsupervised clustering of unknown space // IEEE/RSJ International Conference on Intelligent Robots and Systems. 2004. Vol. 1. P. 717–721.
15. Steinhaus H. Sur la division des corp materiels en parties // Bull. Acad. Polon. Sci. 1956. Vol. 1. P. 801–804.
16. Kuhn H. W. The Hungarian method for the assignment problem // Naval Research Logistics. 1955. Vol. 2, 1–2. P. 83–97.
17. Dolgov D., Thrun S., Montemerlo M., Diebel J. Path Planning for Autonomous Vehicles in Unknown Semi-structured Environments // The International Journal of Robotics Research. 2010. No. 29. P. 485–501.
18. Bradski G. Clustering and Search in Multi-Dimensional Spaces // Dr. Dobb’s Journal of Software Tools. 2000.

Publication information
Main title Vestnik NSU Series: Information Technologies, Volume 14, Issue No 2 (2016).
Parallel title: Novosibirsk State University Journal of Information Technologies Volume 14, Issue No 2 (2016).

Key title: Vestnik Novosibirskogo gosudarstvennogo universiteta. Seriâ: Informacionnye tehnologii
Abbreviated key title: Vestn. Novosib. Gos. Univ., Ser.: Inf. Tehnol.
Variant title: Vestnik NGU. Seriâ: Informacionnye tehnologii

Year of Publication: 2016
ISSN: 1818-7900 (Print), ISSN 2410-0420 (Online)
Publisher: Novosibirsk State University Press
DSpace handle


|Home Page| |All Issues| |Information for Authors| |Journal Boards| |Ethical principles| |Editorial Policy| |Contact Information| |Old Site in Russian|

inftech@vestnik.nsu.ru
© 2006-2017, Novosibirsk State University.