Multi-Robot Coverage with Reeb Graph Clusteringand Optimized Sweeping Patterns

• Autorzy: Szklarski Jacek Tomasz

Identyfikatory

DOI

10.24423/cames.581

• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

coverage path planning; motion planning; multi-robot

PL

planowanie ścieżki pokrycia; planowanie ruchu; robot wielofunkcyjny

• Wydawca: Instytut Podstawowych Problemów Techniki PAN
• Czasopismo: Computer Assisted Methods in Engineering and Science
• Rocznik: 2022
• Tom: Vol. 29, no. 4
• Strony: 379--395
• Opis fizyczny: Bibliogr 24 poz., il., rys., tab., wykr.

Twórcy

autor

Szklarski Jacek Tomasz

• Institute of Fundamental Technological Research, Polish Academy of Sciences,Warsaw, Poland

Bibliografia

• 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 comple- tion 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, Dis- tributed 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.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).