Optimal multirobot coverage path planning: ideal-shaped spanning tree. (English) Zbl 1427.90318
Summary: The present paper attempts to find the optimal coverage path for multiple robots in a given area including obstacles. For single robot coverage path planning (CPP) problem, an improved ant colony optimization (ACO) algorithm is proposed to construct the best spanning tree and then obtain the optimal path, which contributes to minimizing the energy/time consumption. For the multirobot case, first the DARP (Divide Areas based on Robots Initial Positions) algorithm is utilized to divide the area into separate equal subareas, so much so that it transforms the mCPP problem into several CPP problems, degrading the computation complexity. During the second phase, spanning tree in each subarea is constructed by the aforementioned algorithm. In the last phase, the specific end nodes are exchanged among subareas to achieve ideal-shaped spanning trees, which can also decrease the number of turns in coverage path. And the complete algorithms are proven to be approximately polynomial algorithms. Finally,
the simulation confirms the complete algorithms’ advantages: complete coverage, nonbacktracks, minimum length, zero preparation time, and the least number of turns.
MSC:
| 90C90 | Applications of mathematical programming |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
References:
| [1] | Goldberg, K., Robotics: Countering singularity sensationalism, Nature, 526, 7573, 320-321 (2015) · doi:10.1038/526320a |
| [2] | Waharte, S.; Trigoni, N., Supporting search and rescue operations with UAVs, Proceedings of the International Conference on Emerging Security Technologies (EST ’10) · doi:10.1109/est.2010.31 |
| [3] | Nikolic, J.; Burri, M.; Rehder, J.; Leutenegger, S.; Huerzeler, C.; Siegwart, R., A UAV system for inspection of industrial facilities, Proceedings of the 2013 IEEE Aerospace Conference, AERO 2013 |
| [4] | Casbeer, D. W.; Kingston, D. B.; Beard, R. W.; Mc lain, T. W., Cooperative forest fire surveillance using a team of small unmanned air vehicles, International Journal of Systems Science, 37, 6, 351-360 (2006) · Zbl 1101.93055 · doi:10.1080/00207720500438480 |
| [5] | Gabriely, Y.; Rimon, E., Spanning-tree based coverage of continuous areas by a mobile robot, Annals of Mathematics and Artificial Intelligence, 31, 1-4, 77-98 (2001) · Zbl 1314.68318 |
| [6] | Zheng, X.; Jain, S.; Koenig, S.; Kempe, D., Multi-robot forest coverage, Proceedings of the IEEE IRS/RSJ International Conference on Intelligent Robots and Systems, IROS 2005 |
| [7] | Kapoutsis, A. C.; Chatzichristofis, S. A.; Kosmatopoulos, E. B., DARP: Divide Areas Algorithm for Optimal Multi-Robot Coverage Path Planning, Journal of Intelligent & Robotic Systems, 86, 3-4, 663-680 (2017) · doi:10.1007/s10846-016-0461-x |
| [8] | Galceran, E.; Carreras, M., A survey on coverage path planning for robotics, Robotics and Autonomous Systems, 61, 12, 1258-1276 (2013) · doi:10.1016/j.robot.2013.09.004 |
| [9] | Choset, H.; Lynch, K.; Hutchinson, S.; Kantor, G.; Burgard, W.; Kavraki, L.; Thrun, S., Principles of Robot Motion: Theory Algorithms and Implementation (2005), The MIT Press · Zbl 1081.68700 |
| [10] | Choset, H.; Acar, E.; Rizzi, A. A.; Luntz, J., Exact cellular decompositions in terms of critical points of Morse functions, Proceedings of the ICRA 2000: IEEE International Conference on Robotics and Automation |
| [11] | Choset, H.; Pignon, P., Coverage path planning: the boustrophedon cellular decomposition, Proceedings of International Conference on Field and Service Robotics |
| [12] | Araujo, J. F.; Sujit, P. B.; Sousa, J. B., Multiple UAV area decomposition and coverage, Proceedings of the 2013 IEEE Symposium on Computational Intelligence for Security and Defense Applications, CISDA 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013 |
| [13] | Li, Y.; Chen, H.; Joo Er, M.; Wang, X., Coverage path planning for UAVs based on enhanced exact cellular decomposition method, Mechatronics, 21, 5, 876-885 (2011) · doi:10.1016/j.mechatronics.2010.10.009 |
| [14] | Acar, E. U.; Choset, H.; Rizzi, A. A.; Atkar, P. N.; Hull, D., Morse decompositions for coverage tasks, International Journal of Robotics Research, 21, 4, 331-344 (2002) · doi:10.1177/027836402320556359 |
| [15] | Hazon, N.; Kaminka, G. A., Redundancy, efficiency and robustness in multi-robot coverage, Proceedings of the 2005 IEEE International Conference on Robotics and Automation |
| [16] | Agmon, N.; Hazon, N.; Kaminka, G. A., Constructing spanning trees for efficient multi-robot coverage, Proceedings of the 2006 IEEE International Conference on Robotics and Automation, ICRA 2006 |
| [17] | Elmaliach, Y.; Agmon, N.; Kaminka, G. A., Multi-robot area patrol under frequency constraints, Annals of Mathematics and Artificial Intelligence, 57, 3-4, 293-320 (2009) · Zbl 1253.68317 · doi:10.1007/s10472-010-9193-y |
| [18] | Hert, S.; Lumelsky, V., Polygon area decomposition for multiple-robot workspace division, International Journal of Computational Geometry and Applications, 8, 4, 437-466 (1998) · Zbl 1035.68536 · doi:10.1142/S0218195998000230 |
| [19] | Maza, I.; Ollero, A., Multiple UAV cooperative searching operation using polygon area decomposition and efficient coverage algorithms, Distributed Autonomous Robotic Systems, 6, 221-230 (2007), Tokyo, Japan: Springer, Tokyo, Japan · Zbl 1217.93016 |
| [20] | Lloyd, S. P., Least squares quantization in PCM, IEEE Transactions on Information Theory, 28, 2, 129-137 (1982) · Zbl 0504.94015 · doi:10.1109/TIT.1982.1056489 |
| [21] | Aurenhammer, F., Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys, 23, 3, 345-405 (1991) · doi:10.1145/116873.116880 |
| [22] | Puig, D.; Garcia, M. A.; Wu, L., A new global optimization strategy for coordinated multi-robot exploration: development and comparative evaluation, Robotics and Autonomous Systems, 59, 9, 635-653 (2011) · doi:10.1016/j.robot.2011.05.004 |
| [23] | Bast, H.; Hert, S., The area partitioning problem, Proceedings of the 12th Canadian Conference on Computational Geometry Fredericton |
| [24] | Rubinstein, A., Perfect equilibrium in a bargaining model, Econometrica, 50, 1, 97-109 (1982) · Zbl 0474.90092 · doi:10.2307/1912531 |
| [25] | Colorni, A.; Dorigo, M.; Maniezzo, V., Distributed optimization by ant colonies, Proceedings of the 1st European Conference on Artificial Life |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
