Nous étudions ici le problème de l’allocation continue de jobs concurrents, composés de tâches situées, sous-jacent au déploiement distribué du patron de conception MapReduce sur une grappe de serveurs. Afin de mettre en œuvre notre stratégie multi-agents qui vise à minimiser le délai moyen de réalisation des jobs (flowtime), nous proposons une architecture composite d’agent qui permet la concurrence des négociations et des consommations. Nos expérimentations montrent que, lorsqu’elle est exécutée de manière concurrente au processus de consommation, notre stratégie de réallocation : (1) réduit significativement le temps de réordonnancement ; (2) améliore le délai moyen de réalisation ; (3) ne pénalise pas la consommation ; (4) est robuste aux aléas d’exécution ; et (5) s’adapte à la libération de jobs.
In this paper, we study the problem of continous allocation of concurrent jobs, composed of situated tasks, underlying the distributed deployment of the MapReduce design pattern on a cluster. In order to implement our multi-agent strategy that aims at minimizing the mean flowtime of jobs, we propose a composite agent architecture that allows negotiation and consumption concurrency. Our experiments show that, when executed concurrently with the consumption process, our reallocation strategy: (1) significantly reduces the rescheduling time; (2) improves the flowtime; (3) does not penalise the consumption; (4) is robust to execution hazards; and (5) adapts to the release of jobs.
Keywords: Multi-Agents Systems, Distributed Problem Solving, Agent-based Negotiation, Agent Architecture
Ellie Beauprez 1 ; Anne-Cécile Caron 1 ; Maxime Morge 2 ; Jean-Christophe Routier 1
CC-BY 4.0
@article{ROIA_2024__5_4_9_0,
author = {Ellie Beauprez and Anne-C\'ecile Caron and Maxime Morge and Jean-Christophe Routier},
title = {N\'egociation pour la consommation adaptative d{\textquoteright}allocation continue},
journal = {Revue Ouverte d'Intelligence Artificielle},
pages = {9--35},
publisher = {Association pour la diffusion de la recherche francophone en intelligence artificielle},
volume = {5},
number = {4},
year = {2024},
doi = {10.5802/roia.85},
language = {fr},
url = {https://roia.centre-mersenne.org/articles/10.5802/roia.85/}
}
TY - JOUR AU - Ellie Beauprez AU - Anne-Cécile Caron AU - Maxime Morge AU - Jean-Christophe Routier TI - Négociation pour la consommation adaptative d’allocation continue JO - Revue Ouverte d'Intelligence Artificielle PY - 2024 SP - 9 EP - 35 VL - 5 IS - 4 PB - Association pour la diffusion de la recherche francophone en intelligence artificielle UR - https://roia.centre-mersenne.org/articles/10.5802/roia.85/ DO - 10.5802/roia.85 LA - fr ID - ROIA_2024__5_4_9_0 ER -
%0 Journal Article %A Ellie Beauprez %A Anne-Cécile Caron %A Maxime Morge %A Jean-Christophe Routier %T Négociation pour la consommation adaptative d’allocation continue %J Revue Ouverte d'Intelligence Artificielle %D 2024 %P 9-35 %V 5 %N 4 %I Association pour la diffusion de la recherche francophone en intelligence artificielle %U https://roia.centre-mersenne.org/articles/10.5802/roia.85/ %R 10.5802/roia.85 %G fr %F ROIA_2024__5_4_9_0
Ellie Beauprez; Anne-Cécile Caron; Maxime Morge; Jean-Christophe Routier. Négociation pour la consommation adaptative d’allocation continue. Revue Ouverte d'Intelligence Artificielle, Post-actes des Journées Francophones sur les Systèmes Multi-Agents (JFSMA 2023), Volume 5 (2024) no. 4, pp. 9-35. doi : 10.5802/roia.85. https://roia.centre-mersenne.org/articles/10.5802/roia.85/
[1] Négociation multi-agents pour la réallocation dynamique de tâches, Thèse de doctorat, Université de Lille, Septembre (2019)
[2] Réaffectation de tâches de la théorie à la pratique : état de l’art et retour d’expérience, Actes des Journées Francophones sur les Systèmes Multi-Agents (JFSMA), Cépaduès, 2021, pp. 51-60
[3] Échange de tâches pour la réduction de la durée moyenne de réalisation, Actes des Journées Francophones sur les Systèmes Multi-Agents (JFSMA), Cépaduès, 2022, pp. 19-28
[4] Consommation adaptative par négociation continue, Actes des Journées Francophones sur les Systèmes Multi-Agents (JFSMA), Cépaduès, 2023, pp. 21-30
[5] Délégation de lots de tâches pour la réduction de la durée moyenne de réalisation, ROIA, Volume 4 (2023) no. 2, pp. 193-221 | DOI
[6] Scala implementation of the Extended Multi-agents Situated Task Allocation, https://gitlab.univ-lille.fr/maxime.morge/smastaplus, 2020
[7] Combining re-allocating and re-scheduling for dynamic multi-robot task allocation, Proc. of IEEE International Conference on Systems, Man, and Cybernetics (SMC), 2016, pp. 395-400 | DOI
[8] Consensus-based decentralized auctions for robust task allocation, IEEE Transactions on Robotics, Volume 25 (2009) no. 4, pp. 912-926 | DOI
[9] Resource allocation in dynamic multiagent systems (2021) (https://arxiv.org/abs/2102.08317)
[10] The Power of Swap Deals in Distributed Resource Allocation, Proc. of International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2015, pp. 625-633
[11] MapReduce : Simplified Data Processing on Large Clusters, Proc. of The Sixth Symposium on Operating System Design and Implementation, 2004, pp. 137-150
[12] Negotiating Socially Optimal Allocations of Resources, Journal of Artificial Intelligence Research, Volume 25 (2006), pp. 315-348 | DOI
[13] The power of sequential single-item auctions for agent coordination, Proc. of The Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference (AAAI), Volume 2006, 2006, pp. 1625-1629
[14] Analysis of dynamic task allocation in multi-robot systems, The International Journal of Robotics Research, Volume 25 (2006) no. 3, pp. 225-241 | DOI
[15] Akka is the implementation of the Actor Model on the JVM, http://akka.io, 2020
[16] Resilient task allocation in heterogeneous multi-robot systems, IEEE Robotics and Automation Letters, Volume 6 (2021) no. 2, pp. 1327-1334 | DOI
[17] The dynamic hungarian algorithm for the assignment problem with changing costs, Robotics Institute, Pittsburgh, PA, Tech. Rep. CMU-RI-TR-07-27 (2007), p. 19
[18] When to do your own thing : Analysis of cost uncertainties in multi-robot task allocation at run-time, Proc. of IEEE International Conference on Robotics and Automation, 2015, pp. 1249-1254 | DOI
Cité par Sources :