[en] The usage of Unmanned Aerial Vehicles (UAVs) is gradually gaining momentum for commercial applications. The vast majority considers a single UAV, which comes with several constraints such as its range of operations or the number of sensors it can carry. Using multiple autonomous UAVs simultaneously as a swarm makes it possible to overcome these limitations. However, manually designing complex emerging behaviours like swarming is a difficult and tedious task especially for such distributed systems which performance is hardly predictable. This article therefore proposes to automate the design of UAV swarming behaviours by defining a multi-objective optimisation problem, so called Coverage of a Connected-UAV Swarm (CCUS), and designing a Q-Learning based Hyper-Heuristic (QLHH) for generating distributed CCUS heuristics. Experimental results demonstrate the capacity of QLHH to generate efficient heuristics for any instance from a given class.
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)
External co-authors :
yes
Language :
English
Title :
Automating the Design of Efficient Distributed Behaviours for a Swarm of UAVs
Publication date :
December 2020
Event name :
2020 IEEE Symposium Series on Computational Intelligence (SSCI)
Event place :
Canberra, Australia
Event date :
from 01-12-2020 to 04-12-2020
Audience :
International
Main work title :
IEEE Symposium Series on Computational Intelligence, Canberra 1-4 December 2020
R. Arnold, K. Carey, B. Abruzzo, and C. Korpela, "What is A Robot Swarm: A Definition for Swarming Robotics," in 2019 IEEE 10th Annual Ubiquitous Computing, Electronics & Mobile Communication Conference (UEMCON). New York City, NY, USA: IEEE, Oct. 2019, pp. 0074-0081.
F. Aznar, M. Pujol, R. Rizo, and C. Rizo, "Modelling multiRotor UAVs swarm deployment using virtual pheromones," PLOS ONE, vol. 13, no. 1, 2018.
C. Atten, L. Channouf, G. Danoy, and P. Bouvry, "UAV Fleet Mobility Model with Multiple Pheromones for Tracking Moving Observation Targets," in Applications of Evolutionary Computation. Cham: Springer International Publishing, 2016, vol. 9597, pp. 332-347.
G. Danoy, M. R. Brust, and P. Bouvry, "Connectivity Stability in Autonomous MultiLevel UAV Swarms for Wide Area Monitoring," in Proceedings of the 5th ACM Symposium on Development and Analysis of Intelligent Vehicular Networks and Applications-DIVANet '15. ACM Press, 2015, pp. 1-8.
M. R. Brust, M. Zurad, L. Hentges, L. Gomes, G. Danoy, and P. Bouvry, "Target Tracking Optimization of UAV Swarms Based on Dual-Pheromone Clustering," in 2017 3rd IEEE International Conference on Cybernetics (CYBCONF). IEEE, Jun. 2017, pp. 1-8.
M. R. Brust, H. Frey, and S. Rothkugel, "Dynamic multiHop clustering for mobile hybrid wireless networks," in Proceedings of the 2nd international conference on Ubiquitous information management and communication-ICUIMC '08. ACM Press, 2008, p. 130.
M. Birattari, A. Ligot, D. Bozhinoski, M. Brambilla, G. Francesca, L. Garattoni, D. Garzon Ramos, K. Hasselmann, M. Kegeleirs, J. Kuckling, F. Pagnozzi, A. Roli, M. Salman, and T. Stutzle, "Automatic Off-Line Design of Robot Swarms: A Manifesto," Frontiers in Robotics and AI, vol. 6, Jul. 2019.
E. K. Burke, M. Gendreau, M. Hyde, G. Kendall, G. Ochoa, E. O zcan, and R. Qu, "HyperHeuristics: A survey of the state of the art," Journal of the Operational Research Society, vol. 64, no. 12, pp. 1695-1724, 2013.
P. Cowling, G. Kendall, and E. Soubeiga, "A Hyperheuristic Approach to Scheduling a Sales Summit," in Practice and Theory of Automated Timetabling III. Springer, 2001, vol. 2079, pp. 176-190.
D. Wolpert and W. Macready, "No free lunch theorems for optimization," IEEE Trans. on Evol.computation, vol. 1, no. 1, pp. 67-82, 1997.
G. Duflo, E. Kieffer, M. R. Brust, G. Danoy, and P. Bouvry, "A GP HyperHeuristic Approach for Generating TSP Heuristics," in 2019 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). IEEE, May 2019, pp. 521-529.
J. H. Drake, M. Hyde, K. Ibrahim, and E. Ozcan, "A genetic programming hyperHeuristic for the multidimensional knapsack problem," Kybernetes, vol. 43, no. 9/10, pp. 1500-1511, Nov. 2014.
E. Kieffer, G. Danoy, M. R. Brust, P. Bouvry, and A. Nagih, "Tackling LargeScale and Combinatorial BiLevel Problems with a Genetic Programming HyperHeuristic," IEEE Transactions on Evolutionary Computation, pp. 1-1, 2019.
H. Dai, E. B. Khalil, Y. Zhang, B. Dilkina, and L. Song, "Learning Combinatorial Optimization Algorithms over Graphs," arXiv:1704.01665 , Apr. 2017, arXiv: 1704.01665.
T. Stutzle and M. LopezIbanez, "Automated Design of Metaheuristic Algorithms," in Handbook of Metaheuristics. Springer International Publishing, 2019, vol. 272, pp. 541-579.
A. Babic, N. Miskovic, and Z. Vukic, "Heuristics pool for hyperheuristic selection during task allocation in a heterogeneous swarm of marine robots," IFACPapersOnLine, vol. 51, no. 29, pp. 412-417, 2018.
S. A. van der Stockt and A. P. Engelbrecht, "Analysis of selection hyperheuristics for populationBased metaHeuristics in real-valued dynamic optimization," Swarm and Evolutionary Computation, vol. 43, pp. 127-146, 2018.
K. Tuyls and P. Stone, "Multiagent Learning Paradigms," in MultiAgent Systems and Agreement Technologies. Cham: Springer Int. Publishing, 2018, vol. 10767, pp. 3-21.
L. Busoniu, R. Babuska, and B. De Schutter, "MultiAgent Reinforcement Learning: An Overview," in Innovations in MultiAgent Systems and Applications-1. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, vol. 310, pp. 183-221.
K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGAII," IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182-197, Apr. 2002.
Chunming Liu, Xin Xu, and Dewen Hu, "Multiobjective Reinforcement Learning: A Comprehensive Overview," IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 45, no. 3, pp. 385-398, Mar. 2015.
K. Van Moffaert, M. M. Drugan, and A. Nowe, "Scalarized multiobjective reinforcement learning: Novel design techniques," in 2013 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADPRL). IEEE, 2013, pp. 191-199.
K. Van Moffaert and A. Nowe, "Multi-objective reinforcement learning using sets of pareto dominating policies," J. Mach. Learn. Res., vol. 15, no. 1, p. 3483-3512, Jan. 2014.
S. Varrette, P. Bouvry, H. Cartiaux, and F. Georgatos, "Management of an academic hpc cluster: The ul experience," in Proc. of the 2014 Intl. Conf. on High Performance Computing & Simulation (HPCS 2014). Bologna, Italy: IEEE, July 2014, pp. 959-967.
