[en] The use of Unmanned Aerial Vehicles (UAVs) has shown a drastic increase in interest in the past few years. Current applications mainly depend on single UAV operations, which face critical limitations such as mission range or resilience. Using several autonomous UAVs as a swarm is a promising approach to overcome these. However, designing an efficient swarm is a challenging task, since its global behaviour emerges solely from local decisions and interactions. These properties make classical multirobot design techniques not applicable, while evolutionary swarm robotics is typically limited to a single use case. This work, thus, proposes an automated swarming algorithm design approach, and more precisely, a generative hyper-heuristic relying on multi-objective reinforcement learning, that permits us to obtain not only efficient but also reusable swarming behaviours. Experimental results on a three-objective variant of the Coverage of a Connected UAV Swarm problem demonstrate that it not only permits one to generate swarming heuristics that outperform the state-of-the-art in terms of coverage by a swarm of UAVs but also provides high stability. Indeed, it is empirically demonstrated that the model trained on a certain class of instances generates heuristics and is capable of performing well on instances with a different size or swarm density.
Disciplines :
Computer science
Author, co-author :
Duflo, Gabriel ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > PCOG
Danoy, Grégoire ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
Talbi, El-Ghazali ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Bouvry, Pascal ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
Birattari M. Ligot A. Bozhinoski D. Brambilla M. Francesca G. Garattoni L. Garzón Ramos D. Hasselmann K. Kegeleirs M. Kuckling J. et al. Automatic Off-Line Design of Robot Swarms: A Manifesto Front. Robot. AI 2019 6 59 10.3389/frobt.2019.00059 33501074
Silva F. Duarte M. Correia L. Oliveira S.M. Christensen A.L. Open Issues in Evolutionary Robotics Evol. Comput. 2016 24 205 236 10.1162/EVCO_a_00172 26581015
Francesca G. Birattari M. Automatic Design of Robot Swarms: Achievements and Challenges Front. Robot. AI 2019 3 29 10.3389/frobt.2016.00029
Arnold R. Carey K. Abruzzo B. Korpela C. What is A Robot Swarm: A Definition for Swarming Robotics Proceedings of the 2019 IEEE 10th Annual Ubiquitous Computing, Electronics & Mobile Communication Conference New York, NY, USA 10–12 October 2019 0074 0081
Brambilla M. Ferrante E. Birattari M. Dorigo M. Swarm robotics: A review from the swarm engineering perspective Swarm Intell. 2013 7 1 41 10.1007/s11721-012-0075-2
Schranz M. Umlauft M. Sende M. Elmenreich W. Swarm Robotic Behaviors and Current Applications Front. Robot. AI 2020 7 36 10.3389/frobt.2020.00036 33501204
Cabreira T.M. Brisolara L.B. Ferreira P.R. Jr. Survey on Coverage Path Planning with Unmanned Aerial Vehicles Drones 2019 3 4 10.3390/drones3010004
Siemiatkowska B. Stecz W. A Framework for Planning and Execution of Drone Swarm Missions in a Hostile Environment Sensors 2021 21 4150 10.3390/s21124150 34204272
Semiz F. Polat F. Solving the area coverage problem with UAVs: A vehicle routing with time windows variation Robot. Auton. Syst. 2020 126 103435 10.1016/j.robot.2020.103435
Nouyan S. Campo A. Dorigo M. Path formation in a robot swarm: Self-organized strategies to find your way home Swarm Intell. 2008 2 1 23 10.1007/s11721-007-0009-6
Ducatelle F. Di Caro G.A. Pinciroli C. Mondada F. Gambardella L.M. Communication assisted navigation in robotic swarms: Self-organization and cooperation Proceedings of the 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems San Francisco, CA, USA 25–30 September 2011 4981 4988
Sun X. Liu T. Hu C. Fu Q. Yue S. ColCOS Φ: A Multiple Pheromone Communication System for Swarm Robotics and Social Insects Research Proceedings of the 2019 IEEE 4th International Conference on Advanced Robotics and Mechatronics (ICARM) Toyonaka, Japan 3–5 July 2019 59 66
Na S. Qiu Y. Turgut A.E. Ulrich J. Krajník T. Yue S. Lennox B. Arvin F. Bio-inspired artificial pheromone system for swarm robotics applications Adapt. Behav. 2021 29 395 415 10.1177/1059712320918936
Liu T. Sun X. Hu C. Fu Q. Isakhani H. Yue S. Investigating Multiple Pheromones in Swarm Robots—A Case Study of Multi-Robot Deployment Proceedings of the 2020 5th International Conference on Advanced Robotics and Mechatronics (ICARM) Shenzhen, China 18–21 December 2020 595 601
Liu T. Sun X. Hu C. Fu Q. Yue S. A Multiple Pheromone Communication System for Swarm Intelligence IEEE Access 2021 9 148721 148737 10.1109/ACCESS.2021.3124386
Kuiper E. Nadjm-Tehrani S. Mobility Models for UAV Group Reconnaissance Applications Proceedings of the 2006 International Conference on Wireless and Mobile Communications (ICWMC’06) Bucharest, Romania 29–31 July 2006 IEEE Bucharest, Romania 2006 33
Rosalie M. Danoy G. Chaumette S. Bouvry P. Chaos-enhanced mobility models for multilevel swarms of UAVs Swarm Evol. Comput. 2018 41 36 48 10.1016/j.swevo.2018.01.002
Danoy G. Brust M.R. Bouvry P. Connectivity Stability in Autonomous Multi-level UAV Swarms for Wide Area Monitoring Proceedings of the 5th ACM Symposium on Development and Analysis of Intelligent Vehicular Networks and Applications—DIVANet ’15 Cancun, Mexico 2–6 November 2015 ACM Press Cancun, Mexico 2015 1 8 10.1145/2815347.2815351
Brust M.R. Zurad M. Hentges L. Gomes L. Danoy G. Bouvry P. Target Tracking Optimization of UAV Swarms Based on Dual-Pheromone Clustering Proceedings of the 3rd IEEE International Conference on Cybernetics Exeter, UK 21–23 June 2017 1 8
Hunt E.R. Jones S. Hauert S. Testing the limits of pheromone stigmergy in high-density robot swarms R. Soc. Open Sci. 2019 6 190225 10.1098/rsos.190225 31827817
Burke E.K. Gendreau M. Hyde M. Kendall G. Ochoa G. Özcan E. Qu R. Hyper-heuristics: A survey of the state of the art J. Oper. Res. Soc. 2013 64 1695 1724 10.1057/jors.2013.71
Epitropakis M.G. Burke E.K. Hyper-heuristics Handbook of Heuristics Martí R. Pardalos P.M. Resende M.G.C. Springer International Publishing Cham, Switzerland 2018 489 545
Burke E.K. Hyde M.R. Kendall G. Ochoa G. Özcan E. Woodward J.R. A Classification of Hyper-Heuristic Approaches: Revisited Handbook of Metaheuristics Gendreau M. Potvin J.Y. Springer International Publishing Cham, Switzerland 2019 Volume 272 453 477
Li K. Malik J. Learning to Optimize Proceedings of the 5th International Conference on Learning Representations, ICLR 2017 Toulon, France 24–26 April 2017
Cowling P. Kendall G. Soubeiga E. A Hyperheuristic Approach to Scheduling a Sales Summit Practice and Theory of Automated Timetabling III Goos G. Hartmanis J. van Leeuwen J. Burke E. Erben W. Springer Berlin/Heidelberg, Germany 2001 Volume 2079 176 190
Birattari M. Ligot A. Francesca G. AutoMoDe: A Modular Approach to the Automatic Off-Line Design and Fine-Tuning of Control Software for Robot Swarms Automated Design of Machine Learning and Search Algorithms Pillay N. Qu R. Natural Computing Series Springer International Publishing Cham, Switzerland 2021 73 90
Ligot A. Cotorruelo A. Garone E. Birattari M. Towards an Empirical Practice in Off-line Fully-automatic Design of Robot Swarms IEEE Trans. Evol. Comput. 2022 1 10.1109/TEVC.2022.3144848
Yu S. Aleti A. Barca J.C. Song A. Hyper-heuristic Online Learning for Self-assembling Swarm Robots Computational Science—ICCS 2018 Shi Y. Fu H. Tian Y. Krzhizhanovskaya V.V. Lees M.H. Dongarra J. Sloot P.M.A. Springer International Publishing Berlin/Heidelberg, Germany 2018 Volume 10860 167 180
Yu S. Song A. Aleti A. A Study on Online Hyper-heuristic Learning for Swarm Robots Proceedings of the IEEE Congress on Evolutionary Computation Wellington, New Zealand 10–13 June 2019 2721 2728
Nagavalli S. Chakraborty N. Sycara K. Automated sequencing of swarm behaviors for supervisory control of robotic swarms Proceedings of the 2017 IEEE International Conference on Robotics and Automation (ICRA) Singapore 29 May–3 June 2017 2674 2681
Duflo G. Danoy G. Talbi E.G. Bouvry P. A Q-Learning Based Hyper-Heuristic for Generating Efficient UAV Swarming Behaviours Proceedings of the Intelligent Information and Database Systems Nguyen N.T. Chittayasothorn S. Niyato D. Trawiński B. Springer International Publishing Cham, Switzerland 2021 768 781 10.1007/978-3-030-73280-6_61
Duflo G. Danoy G. Talbi E.G. Bouvry P. Automating the Design of Efficient Distributed Behaviours for a Swarm of UAVs Proceedings of the 2020 IEEE Symposium Series on Computational Intelligence (SSCI) Canberra, Australia 1–4 December 2020 489 496
Van Moffaert K. Drugan M.M. Nowe A. Scalarized multi-objective reinforcement learning: Novel design techniques Proceedings of the 2013 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADPRL) Singapore 16–19 April 2013 191 199
Brust M.R. Frey H. Rothkugel S. Dynamic Multi-Hop Clustering for Mobile Hybrid Wireless Networks Proceedings of the 2nd International Conference on Ubiquitous Information Management and Communication, ICUIMC ’08 Suwon, Korea 31 January–1 February 2008 Association for Computing Machinery New York, NY, USA 2008 130 135 10.1145/1352793.1352820
Varrette S. Bouvry P. Cartiaux H. Georgatos F. Management of an Academic HPC Cluster: The UL Experience Proceedings of the 2014 International Conference on High Performance Computing & Simulation (HPCS 2014) Bologna, Italy 21–25 July 2014 959 967