Au cours de la dernière décennie, des applications industrielles des systèmes multi-robots ont vu le jour. Parmi ces applications, on trouve des systèmes chargés de missions de pick and delivery, tels que le fameux terminal portuaire autonome de Rotterdam, mais aussi de nombreuses propositions de systèmes chargés de tâches de surveillance. Or, une étape clef de l’exécution de toute mission multi-robots est la résolution du problème d’allocation de tâches au système multi-robots. Ce problème consiste à assigner les tâches de la mission aux robots, et devient un problème d’optimisation combinatoire lorsque l’on associe à la simple allocation des tâches, un objectif d’optimisation représentant les performances du système. Pour résoudre le problème d’allocation de tâches au système multi-robots, les chercheurs ont proposé plusieurs approches. Parmi ces propositions, une classe de méthodes approchées, basées sur les mécanismes d’enchères, a retenu l’attention des chercheurs pour leur capacité à rapidement réallouer les tâches si cela permet d’améliorer l’exécution de la mission. Dans ce papier, nous introduisons un nouveau terme dans l’évaluation des mises dans le cadre d’un protocole d’allocation de tâches par enchères. Ce nouveau terme permet de prendre en compte la connectivité du réseau de communication, qui représente les liaisons de communication entre les membres du système multi-robots. Cet élément est important pour garantir l’efficacité des méthodes basées enchères, puisqu’elles se basent sur le partage d’information entre les membres du système multi-robots pour produire des allocations performantes. Après avoir décrit notre protocole d’enchères, nous avons analysé chacune de ses étapes pour établir des bornes sur sa complexité en temps de calcul et sur la taille des messages échangés au cours de la mission. Nous avons évalué notre méthode dans un scénario de patrouille, et avons montré grâce à des simulations numériques que la préservation des communications améliore la robustesse du système multi-robots face à des évènements dynamiques, survenant au cours de la mission de façon imprévisible, et altérant ses conditions d’exécution.
In the last ten years, various industrial applications of multi-robot systems have emerged. Among these are systems executing pick and delivery missions, such as the well known autonomous terminal in Rotterdam, as well as many systems tasked with surveillance missions. A key step in the execution of any multi-robot mission is the resolution of the multi-robot task allocation problem. It consists in assigning the tasks of the mission to the robots. If one needs to optimize an objective representing the performances of the system while assigning the tasks, it becomes an integer programming problem. To solve multi-robot task allocation, researchers have proposed many approaches. Among these proposals, a class of approximate methods, based on auction mechanisms, has drawn the attention of researchers for their ability to quickly reallocate tasks if this improves the execution of the mission. In this paper, we introduce a new term in the evaluation of bids for an auction based task allocation protocol. This new term enables us account for the connectivity of the communication network, which represents the communication links between the robots. The connectivity of the communication network is key to the efficiency of auction-based methods, as they need to share auction messages as broadly as possible to produce efficient allocations. We evaluated our method in a surveillance scenario. We derived theoretical bounds of the time complexity of the evaluation of the bids and of the size of the data shared during the mission. We demonstrated through simulation experiments that improved communications increase the robustness of the multi-robot system to dynamic events.
Accepté le :
Publié le :
Keywords: Multi-Robot Systems, Task Allocation, Auction-Based Approaches, Multi-Robot Patrol.
Félix Quinton 1 ; Christophe Grand 2 ; Charles Lesire 2
CC-BY 4.0
@article{ROIA_2023__4_2_97_0,
author = {F\'elix Quinton and Christophe Grand and Charles Lesire},
title = {Ench\`eres pour le {Maintien} des {Communications} lors de {l{\textquoteright}Allocation} de {T\^aches} pour des {Missions} {Multi-robots}},
journal = {Revue Ouverte d'Intelligence Artificielle},
pages = {97--122},
publisher = {Association pour la diffusion de la recherche francophone en intelligence artificielle},
volume = {4},
number = {2},
year = {2023},
doi = {10.5802/roia.58},
language = {fr},
url = {https://roia.centre-mersenne.org/articles/10.5802/roia.58/}
}
TY - JOUR AU - Félix Quinton AU - Christophe Grand AU - Charles Lesire TI - Enchères pour le Maintien des Communications lors de l’Allocation de Tâches pour des Missions Multi-robots JO - Revue Ouverte d'Intelligence Artificielle PY - 2023 SP - 97 EP - 122 VL - 4 IS - 2 PB - Association pour la diffusion de la recherche francophone en intelligence artificielle UR - https://roia.centre-mersenne.org/articles/10.5802/roia.58/ DO - 10.5802/roia.58 LA - fr ID - ROIA_2023__4_2_97_0 ER -
%0 Journal Article %A Félix Quinton %A Christophe Grand %A Charles Lesire %T Enchères pour le Maintien des Communications lors de l’Allocation de Tâches pour des Missions Multi-robots %J Revue Ouverte d'Intelligence Artificielle %D 2023 %P 97-122 %V 4 %N 2 %I Association pour la diffusion de la recherche francophone en intelligence artificielle %U https://roia.centre-mersenne.org/articles/10.5802/roia.58/ %R 10.5802/roia.58 %G fr %F ROIA_2023__4_2_97_0
Félix Quinton; Christophe Grand; Charles Lesire. Enchères pour le Maintien des Communications lors de l’Allocation de Tâches pour des Missions Multi-robots. Revue Ouverte d'Intelligence Artificielle, Volume 4 (2023) no. 2, pp. 97-122. doi : 10.5802/roia.58. https://roia.centre-mersenne.org/articles/10.5802/roia.58/
[1] Minimal time dynamic task allocation for a swarm of robots, International Journal of Mechanical Engineering and Robotics Research, Volume 6 (2017) no. 6, pp. 481-487 | DOI
[2] Communication of behavorial state in multi-agent retrieval tasks, IEEE International Conference on Robotics and Automation (ICRA), Volume 3, Atlanta, GA, USA (1993), pp. 588-594 | DOI
[3] Task Allocation Using a Team of Robots, Current Robotics Reports, Volume 3 (2022), pp. 227-238 | DOI
[4] Indoor automation with many mobile robots, IEEE International Workshop on Intelligent Robots and Systems, Towards a New Frontier of Applications, Volume 1, Ibaraki, Japan (1990), pp. 67-72 | DOI
[5] Energy-constrained multi-UAV coverage path planning for an aerial imagery mission using column generation, Journal of Intelligent & Robotic Systems, Volume 97 (2020) no. 1, pp. 125-139 | DOI
[6] Introduction to algorithms, MIT press, 2009, pp. 603-613
[7] Market-based multirobot coordination : A survey and analysis, Proceedings of the IEEE, Volume 94 (2006) no. 7, pp. 1257-1270 | DOI
[8] et al. A note on two problems in connexion with graphs, Numerische mathematik, Volume 1 (1959) no. 1, pp. 269-271 | DOI | MR
[9] A market-based task allocation framework for autonomous underwater surveillance networks, OCEANS 2017, Aberdeen, Scotland, UK (2017) | DOI
[10] Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), Volume 34 (1987) no. 3, pp. 596-615 | DOI | MR | Zbl
[11] A formal analysis and taxonomy of task allocation in multi-robot systems, The International Journal of Robotics Research (IJRR), Volume 23 (2004) no. 9, pp. 939-954 | DOI
[12] Repeated auctions for reallocation of tasks with pickup and delivery upon robot failure, International Conference on Principles and Practice of Multi-Agent Systems, Dunedin, New Zealand (2013) | DOI
[13] Improved trade-based multi-robot coordination, IEEE Joint International Information Technology and Artificial Intelligence Conference, Chongqing, China (2011) | DOI
[14] A comparative study of market-based and threshold-based task allocation, International Symposium on Distributed Autonomous Robotic Systems (DARS), Minneapolis, MN, USA (2006) | DOI
[15] Multi-robot task allocation : A review of the state-of-the-art, Cooperative Robots and Sensor Networks, Springer, 2015, pp. 31-51 | DOI
[16] Autonomous and Market-Based Fault Tolerant Algorithms for Multi-Robot Cooperation, Journal of Information Science and Engineering, Volume 30 (2014) no. 2, pp. 483-500 | DOI
[17] et al. Heterogeneous multirobot coordination with spatial and temporal constraints, Proceedings of the 20th National Conference on Artificial Intelligence, Volume 5, AAAI (2005), pp. 1292-1297
[18] Adaptive Fuzzy Control for Coordinated Multiple Robots With Constraint Using Impedance Learning, IEEE Transactions on Cybernetics, Volume 49 (2019) no. 8, pp. 3052-3063 | DOI
[19] xBots : An approach to generating and executing optimal multi-robot plans with cross-schedule dependencies, 2012 IEEE International Conference on Robotics and Automation, IEEE (2012), pp. 115-122 | DOI
[20] Multi-robot task allocation based on cloud ant colony algorithm, International Conference on Neural Information Processing, Springer (2017), pp. 3-10 | DOI
[21] Simultaneous auctions for "Rendez-Vous" coordination phases in multi-robot multi-task mission, IEEE/WIC/ACM International Joint Conferences on Web Intelligence and Intelligent Agent Technologies, Atlanta, GA, USA (2013), pp. 67-74 | DOI
[22] Multi-agent patrolling : An empirical analysis of alternative architectures, International Workshop on Multi-Agent Systems and Agent-Based Simulation (MABS), Bologna, Italy (2002)
[23] Online scheduling of a fleet of autonomous vehicles using agent-based procurement auctions, IEEE International Conference on Service Operations and Logistics, and Informatics (SOLI), Bari, Italy (2017) | DOI
[24] Multi-robot task allocation problem with multiple nonlinear criteria using branch and bound and genetic algorithms, Intelligent Service Robotics, Volume 14 (2021) no. 5, pp. 707-727 | DOI
[25] Auction aggregation protocols for wireless robot-robot coordination, International Conference on Ad-Hoc Networks and Wireless (ADHOC-NOW, Murcia, Spain (2009) | DOI
[26] Simulated annealing for multi-robot hierarchical task allocation with flexible constraints and objective functions, Workshop on Network Robot Systems : Toward intelligent robotic systems integrated with environments. Int. Conf. on Intelligent Robots and Systems (2006)
[27] A survey of multi-robot task allocation (2010) (Technical report)
[28] An empirical study of task bundling for sequential stochastic tasks in multi-robot task allocation (2016) (Technical report)
[29] Auctions for multi-robot task allocation in communication limited environments, Autonomous Robots, Volume 44 (2020), p. 547–584 | DOI
[30] Optimal bid valuation using path finding for multi-robot task allocation, Journal of Intelligent Manufacturing, Volume 26 (2015), pp. 1049-1062 | DOI
[31] Adaptive heterogeneous multi-robot teams, Neurocomputing, Volume 28 (1999) no. 1, pp. 75-92 | DOI
[32] Performance based task assignment in multi-robot patrolling, ACM Symposium on Applied Computing, Coimbra, Portugal (2013) | DOI
[33] Auction-based strategies for the open-system patrolling task, International Conference on Principles and Practice of Multi-Agent Systems (PRIMA), Kuching, Malaysia (2012) | DOI
[34] Multi-Robot Persistent Surveillance With Connectivity Constraints, IEEE Access, Volume 8 (2020), pp. 15093-15109 | DOI
[35] Simultaneous task allocation and planning for temporal logic goals in heterogeneous multi-robot systems, The international journal of robotics research, Volume 37 (2018) no. 7, pp. 818-838 | DOI
[36] Review on state-of-the-art dynamic task allocation strategies for multiple-robot systems, Industrial Robot : the international journal of robotics research and application, Volume 47 (2020) no. 6, pp. 929-942 | DOI
[37] Adaptive patrol for a group of robots, IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Las Vegas, NV, USA (2003) | DOI
[38] Distributed multi-robot coordination in area exploration, Robotics and Autonomous Systems, Volume 54 (2006) no. 12, p. 945–955 | DOI
[39] The Contract Net Protocol : High-Level Communication and Control in a Distributed Problem Solver, IEEE Transactions on Computers, Volume C-29 (1980) no. 12, pp. 1104-1113 | DOI
[40] Distributed sequential auctions for multiple UAV task allocation, American Control Conference (ACC), New York, NY, USA (2007)
[41] Multi-UAV task allocation with communication faults, American Control Conference, Montreal, Canada (2012) | DOI
[42] A distributed market-based algorithm for the multi-robot assignment problem, Procedia Computer Science, Volume 32 (2014), pp. 1108-1114 | DOI
[43] Simulated Annealing Algorithms for the Heterogeneous Robots Task Scheduling Problem in Heterogeneous Robotic Order Fulfillment Systems, International Conference on Intelligent Autonomous Systems, Volume 412, Springer (2022), pp. 276-287 | DOI
[44] Multi-robot task allocation algorithm based on anxiety model and modified contract network protocol, IEEE Information Technology, Networking, Electronic and Automation Control Conference, Chengdu, China (2017) | DOI
[45] Event-based planning and control for multi-robot coordination, IEEE International Conference on Robotics and Automation (ICRA), Atlanta, GA, USA (1993) | DOI
[46] Multi-robot patrol : A distributed algorithm based on expected idleness, International Journal of Advanced Robotic Systems, Volume 3 (2016) no. 6 | DOI
[47] A heuristic distributed task allocation method for multivehicle multitask problems and its application to search and rescue scenario, IEEE transactions on cybernetics, Volume 46 (2015) no. 4, pp. 902-915 | DOI
[48] A tabu search algorithm for simultaneous machine/AGV scheduling problem, International Journal of Production Research, Volume 52 (2014) no. 19, pp. 5748-5763 | DOI
Cité par Sources :