Multi-Robot Coverage with Reeb Graph Clustering and Optimized Sweeping Patterns

Jacek Tomasz Szklarski

doi:10.24423/cames.581

Jacek Tomasz Szklarski Institute of Fundamental Technological Research, Polish Academy of Sciences

DOI: http://dx.doi.org/10.24423/cames.581

Abstract

In order to perform mapping, inspecting, searching, painting, cleaning, and other similar tasks, mobile robots have to act according to a coverage plan. Finding a trajectory that a robot should follow requires an appropriate coverage path planning (CPP) algorithm and is a non-trivial problem, especially if a cooperating group of robots is considered. We propose that the multi-robot CPP can be solved by: decomposing the input occupancy grid map into cells, generating a corresponding Reeb graph, clustering the graph into N_r clusters, and solving the associated equality generalized traveling salesman problem in order to obtain optimal back-and-forth sweeping patterns on the clusters. This last step has been proven to be one of the most efficient ways to find trajectories for a single robot [5]. The discussed approach is motivated by a specific application: industrial cleaning of large warehouses by N_r autonomic mobile cleaners (the cleaning radius of a robot is much smaller than the area to be cleaned). The total time required for cleaning is to be minimized. By means of statistical analysis, using an extensive, realistic set of synthetic maps, it is shown that the proposed algorithm meets the criteria for applying it in the production process.

Keywords

coverage path planning, motion planning, multi-robot,

References

1. R. Almadhoun, T. Taha, L. Seneviratne, Y. Zweiri, A survey on multi-robot coverage path planning for model reconstruction and mapping, SN Applied Sciences, 1(8): 1–24, 2019, doi: 10.1007/s42452-019-0872-y.
2. E.M. Arkin, S.P. Fekete, J.S.B. Mitchell, Approximation algorithms for lawn mowing and milling, Computational Geometry, 17(1–2): 25–50, 2000, doi: 10.1016/S0925-7721(00)00015-8.
3. G.S.C. Avellar, G.A.S. Pereira, L.C.A. Pimenta, P. Iscold, Multi-UAV routing for area coverage and remote sensing with minimum time, Sensors, 15(11): 27783–27803, 2015, doi: 10.3390/s151127783.
4. H. Azpúrua, G.M. Freitas, D.G. Macharet, M.F.M. Campos, Multi-robot coverage path planning using hexagonal segmentation for geophysical surveys, Robotica, 36(8): 1144–1166, 2018, doi: 10.1017/S0263574718000292.
5. R. Bähnemann, N. Lawrance, J.J. Chung, M. Pantic, R. Siegwart, J. Nieto, Revisiting boustrophedon coverage path planning as a generalized traveling salesman problem, [in:] Field and Service Robotics, pp. 277–290, Springer, 2021.
6. J. Bedkowski, K. Majek, P. Majek, P. Musialik, M. Pełka, A. Nüchter, Intelligent mobile system for improving spatial design support and security inside buildings, Mobile Networks and Applications, 21(2): 313–326, 2016, doi: 10.1007/s11036-015-0654-8.
7. H. Choset, Coverage for robotics – A survey of recent results, Annals of Mathematics and Artificial Intelligence, 31(1): 113–126, 2001, doi: 10.1023/A:1016639210559.
8. P. Dasgupta, A. Muñoz-Meléndez, K.R. Guruprasad, Multi-robot terrain coverage and task allocation for autonomous detection of landmines, [in:] Sensors, and Command, Control, Communications, and Intelligence (C3I) Technologies for Homeland Security and Homeland Defense XI, Vol. 8359, pp. 98–111, SPIE, 2012.
9. K. Easton, J. Burdick, A coverage algorithm for multi-robot boundary inspection, [in:] Proceedings of the 2005 IEEE International Conference on Robotics and Automation, (ICRA 2005), pp. 727–734, IEEE, 2005.
10. M. Fischetti, J.J.S. González, P. Toth, A branch-and-cut algorithm for the symmetric generalized traveling salesman problem, Operations Research, 45(3): 378–394, 1997, doi: 10.1287/opre.45.3.378.
11. E. Galceran, M. Carreras, 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.
12. G. Gutin, D. Karapetyan, A memetic algorithm for the generalized traveling salesman problem, Natural Computing, 9(1): 47–60, 2010.
13. A. Janchiv, D. Batsaikhan, B. Kim, W.G. Lee, S.-G. Lee, Time-efficient and complete coverage path planning based on ow networks for multi-robots, International Journal of Control, Automation and Systems, 11(2): 369–376, 2013, doi: 10.1007/s12555-011-0184-5.
14. N. Karapetyan, K. Benson, C. McKinney, P. Taslakian, I. Rekleitis, Efficient multi-robot coverage of a known environment, [in:] 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 1846–1852, IEEE, 2017.
15. T. Li, D. Ho, C. Li, D. Zhu, C. Wang, M.Q.-H. Meng, HouseExpo: A large-scale 2D indoor layout dataset for learning-based algorithms on mobile robots, [in:] 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 5839–5846, IEEE, 2020.
16. L.D. Nielsen, I. Sung, P. Nielsen, Convex decomposition for a coverage path planning for autonomous vehicles: Interior extension of edges, Sensors, 19(19): 4165, 2019, doi: 10.3390/s19194165.
17. M. Ozkan, A. Yazici, M. Kapanoglu, O. Parlaktuna, A genetic algorithm for task completion time minimization for multi-robot sensor-based coverage, [in:] Control Applications (CCA) & Intelligent Control (ISIC), pp. 1164–1169, IEEE, 2009.
18. I. Rekleitis, A.P. New, E.S. Rankin, H. Choset, Efficient boustrophedon multi-robot coverage: An algorithmic approach, Annals of Mathematics and Artificial Intelligence, 52(2): 109–142, 2008, doi: 10.1007/s10472-009-9120-2.
19. A. Renzaglia, L. Doitsidis, S.A. Chatzichristofis, A. Martinelli, E.B. Kosmatopoulos, Distributed multi-robot coverage using micro aerial vehicles, [in:] 2013 21st Mediterranean Conference on Control & Automation (MED), pp. 963–968, IEEE, 2013.
20. A. Renzaglia, L. Doitsidis, A. Martinelli, E.B. Kosmatopoulos, Multi-robot three-dimensional coverage of unknown areas, The International Journal of Robotics Research, 31(6): 738–752, 2012, doi: 10.1177/0278364912439332.
21. S. Saeedi, M. Trentini, M. Seto, H. Li, Multiple-robot simultaneous localization and mapping: A review, Journal of Field Robotics, 33(1): 3–46, 2016, doi: 10.1002/rob.21620.
22. J. Szklarski, Ł. Białek, A. Szałs, Paraconsistent reasoning in cops and robber game with uncertain information: A simulation-based analysis, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 27(03): 429–455, 2019, doi: 10.1142/S021848851950020X.
23. Z. Yan, N. Jouandeau, A.A. Cherif, A survey and analysis of multi-robot coordination, International Journal of Advanced Robotic Systems, 10(12), 2013, doi: 10.5772/57313.
24. L. Zeng, G.M. Bone, Mobile robot collision avoidance in human environments, International Journal of Advanced Robotic Systems, 10(1): 41, 2013, doi: 10.5772/54933.