Distributed multi-robot sweep coverage for a region with unknown workload distribution

Abstract

This paper considers the scenario where multiple robots collaboratively cover a region in which the exact distribution of workload is unknown prior to the operation. The workload distribution is not uniform in the region, meaning that the time required to cover a unit area varies at different locations of the region. In our approach, we divide the target region into multiple horizontal stripes, and the robots sweep the current stripe while partitioning the next stripe concurrently. We propose a distributed workload partition algorithm and prove that the operation time on each stripe converges to the minimum under the discrete-time update law. We conduct comprehensive simulation studies and compare our method with the existing methods to verify the theoretical results and the advantage of the proposed method. Flight experiments on mini drones are also conducted to demonstrate the practicality of the proposed algorithm.

Keywords

Multi-robot systems / Coverage control / Distributed control

References

[1] M. S. Couceiro, D. Portugal, J. F. Ferreira, R. P. Rocha, in 2019 IEEE/SICE International Symposium on System Integration (SII). SEMFIRE: Towards a new generation of forestry maintenance multi-robot systems, (2019), pp. 270–276. https://doi.org/10.1109/SII.2019.8700403.

[2] A. J. Healey, in Proceedings of the 40th IEEE Conference on Decision and Control (Cat. No.01CH37228), 2. Application of formation control for multi-vehicle robotic minesweeping, (2001), pp. 1497–1502 vol.2. https://doi.org/10.1109/CDC.2001.981106.

[3] S. Bernardini, F. Jovan, Z. Jiang, S. Watson, A. Weightman, P. Moradi, T. Richardson, R. Sadeghian, S. Sareh, in Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS ’20). A Multi-Robot Platform for the Autonomous Operation and Maintenance of Offshore Wind Farms (International Foundation for Autonomous Agents and Multiagent SystemsRichland, pp. 1696–1700.

[4] GalceranE., CarrerasM.. A survey on coverage path planning for robotics. Robot. Auton. Syst., 2013, 61(12):1258-1276

[5] A. V. Savkin, T. M. Cheng, Z. Xi, F. Javed, A. S. Matveev, H. Nguyen, IntroductionJohn Wiley & Sons, Ltd, 2015). https://doi.org/10.1002/9781119058052.ch1.

[6] CabreiraT. M., BrisolaraL. B., Ferreira JrP. R.. Survey on coverage path planning with unmanned aerial vehicles. Drones, 2019, 3(1):4

[7] DoitsidisL., WeissS., RenzagliaA., AchtelikM. W., KosmatopoulosE., SiegwartR., ScaramuzzaD.. Optimal surveillance coverage for teams of micro aerial vehicles in gps-denied environments using onboard vision. Auton. Robot., 2012, 33(1-2):173-188

[8] AvellarG. S., PereiraG. A., PimentaL. C., IscoldP.. Multi-uav routing for area coverage and remote sensing with minimum time. Sensors, 2015, 15(11):27783-27803

[9] WuL., XiongY., WuM., HeY., SheJ.. A task assignment method for sweep coverage optimization based on crowdsensing. IEEE Internet Things J., 2019, 6(6):10686-10699

[10] J. D. Kelly, D. M. Lofaro, D. Sofge, in 2020 17th International Conference on Ubiquitous Robots (UR). Persistent Area Coverage for Swarms Utilizing Deployment Entropy with Potential Fields, (2020), pp. 479–486. https://doi.org/10.1109/UR49135.2020.9144917.

[11] GageD. W.. Command Control for Many-Robot Systems. AUVS-92, Nineteenth Ann AUVS Tech. Symp., 1992, 10(June):15

[12] ShiM., QinK., LiuJ.. Cooperative multi-agent sweep coverage control for unknown areas of irregular shape. IET Control Theory Appl., 2018, 12(14):1983-1994

[13] ZhaiC.. Sweep coverage of discrete time multi-robot networks with general topologies. Kybernetika, 2014, 50(1):19-31

[14] RekleitisI., NewA. P., RankinE. S., ChosetH.. Efficient boustrophedon multi-robot coverage: an algorithmic approach. Ann. Math. Artif. Intell., 2008, 52(2-4):109-142

[15] ChosetH., PignonP.. ZelinskyA.. Coverage Path Planning: The Boustrophedon Cellular Decomposition. Field and Service Robotics, 1998 London Springer 203-209

[16] VincentP., RubinI.. A Framework and Analysis for Cooperative Search Using UAV Swarms. Proceedings of the 2004 ACM Symposium on Applied Computing (SAC ’04), 2004 New York Association for Computing Machinery 79-86 https://doi.org/10.1145/967900.967919

[17] ZhaiC., HongY.. Decentralized sweep coverage algorithm for multi-agent systems with workload uncertainties. Automatica, 2013, 49(7):2154-2159 https://doi.org/10.1016/j.automatica.2013.03.017

[18] Olfati-SaberR., FaxJ. A., MurrayR. M.. Consensus and cooperation in networked multi-agent systems. Proc. IEEE, 2007, 95(1):215-233

[19] NesterovY.. Introductory Lectures on Convex Optimization: A Basic Course, 2004 Boston Springer US https://doi.org/10.1007/978-1-4419-8853-9_2

[20] CaiG., ChenB. M., LeeT. H.. Unmanned Rotorcraft Systems, 2011 London Springer London https://doi.org/10.1007/978-0-85729-635-1_8