Résilience et auto-réparation de processus de décisions multi-agents. Application à l’auto-configuration d’environnements intelligents
Pierre Rust1 ; Gauthier Picard2 ; Fano Ramparany3
1 Orange Labs, France
2 ONERA/DTIS, Université de Toulouse
3 Orange Labs
Revue Ouverte d'Intelligence Artificielle, Volume 3 (2022) no. 5-6, pp. 587-623.

Dans cet article, nous définissons la notion de k-résilience de graphes de calculs en support aux décisions d’agents opérées sur des systèmes dynamiques. Nous proposons une méthode d’auto-réparation de la distribution des calculs, DRPM[DMCM], afin d’assurer la continuité des décisions collectives suite à la disparition d’agents, grâce au déploiement de réplicas de calculs. Nous nous intéressons ici à la réparation de processus d’optimisation sous contraintes, où les calculs sont des variables de décision ou des contraintes distribuées sur l’ensemble des agents. Nous appliquons la modélisation sous contraintes distribuées à un problème de coordination multi-agents d’objets dans le cadre de la maison intelligente (SECP) afin d’y appliquer nos techniques de réparation. Nous évaluons expérimentalement les performances de DRPM[DMCM], sur différentes topologies de systèmes opérant des algorithmes (A-MaxSumou A-DSA) pour résoudre des problèmes classiques (aléatoire, coloration de graphe, Ising) et des instances de SECP, alors que des agents disparaissent en cours de fonctionnement.

In this paper we define the notion of k-resilience for computational graphs in support of agents’ decisions on dynamic systems. We propose a method to self-repair the computation distribution, DRPM[DMCM], as to ensure the continuity of collective decisions following the disappearance of agents, through the deployment of replicas calculations. We are interested here in constraint optimization process repair, where the computations are decision variables or distributed constraints. We model a smart environment configuration problem as a distributed constraint optimization problem to be repaired by our repair techniques. We experimentally evaluate the performance of DRPM[DMCM] on different topologies of systems operating algorithms (A-MaxSumor A-DSA) to solve classic problems (random, graph coloring, Ising) and SECP instances, while agents disappear at runtime.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/roia.44
Mot clés : DCOP, résilience, auto-réparation, environnement intelligent
Mots clés : DCOP, resilience, self-repair, smart environment
Pierre Rust 1 ; Gauthier Picard 2 ; Fano Ramparany 3

1 Orange Labs, France
2 ONERA/DTIS, Université de Toulouse
3 Orange Labs
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits 
@article{ROIA_2022__3_5-6_587_0,
     author = {Pierre Rust and Gauthier Picard and Fano Ramparany},
     title = {R\'esilience et auto-r\'eparation de processus de d\'ecisions multi-agents. {Application} \`a l{\textquoteright}auto-configuration d{\textquoteright}environnements intelligents},
     journal = {Revue Ouverte d'Intelligence Artificielle},
     pages = {587--623},
     publisher = {Association pour la diffusion de la recherche francophone en intelligence artificielle},
     volume = {3},
     number = {5-6},
     year = {2022},
     doi = {10.5802/roia.44},
     language = {fr},
     url = {https://roia.centre-mersenne.org/articles/10.5802/roia.44/}
}
TY  - JOUR
AU  - Pierre Rust
AU  - Gauthier Picard
AU  - Fano Ramparany
TI  - Résilience et auto-réparation de processus de décisions multi-agents. Application à l’auto-configuration d’environnements intelligents
JO  - Revue Ouverte d'Intelligence Artificielle
PY  - 2022
SP  - 587
EP  - 623
VL  - 3
IS  - 5-6
PB  - Association pour la diffusion de la recherche francophone en intelligence artificielle
UR  - https://roia.centre-mersenne.org/articles/10.5802/roia.44/
DO  - 10.5802/roia.44
LA  - fr
ID  - ROIA_2022__3_5-6_587_0
ER  - 
%0 Journal Article
%A Pierre Rust
%A Gauthier Picard
%A Fano Ramparany
%T Résilience et auto-réparation de processus de décisions multi-agents. Application à l’auto-configuration d’environnements intelligents
%J Revue Ouverte d'Intelligence Artificielle
%D 2022
%P 587-623
%V 3
%N 5-6
%I Association pour la diffusion de la recherche francophone en intelligence artificielle
%U https://roia.centre-mersenne.org/articles/10.5802/roia.44/
%R 10.5802/roia.44
%G fr
%F ROIA_2022__3_5-6_587_0
Pierre Rust; Gauthier Picard; Fano Ramparany. Résilience et auto-réparation de processus de décisions multi-agents. Application à l’auto-configuration d’environnements intelligents. Revue Ouverte d'Intelligence Artificielle, Volume 3 (2022) no. 5-6, pp. 587-623. doi : 10.5802/roia.44. https://roia.centre-mersenne.org/articles/10.5802/roia.44/

[1] Albert Barabasi; Réka Albert Emergence of Scaling in Random Networks, Science, Volume 286 (1999-10-15) no. 5439, pp. 509-512 | DOI | MR | Zbl

[2] F. Bonomi; R. Milito; J. Zhu; S. Addepalli, Proceedings of the First Edition of the MCC Workshop on Mobile Cloud Computing (MCC ’12) (2012), pp. 13-16 | DOI

[3] F. Chakchouk; S. Piechowiak; R. Mandiau; J. Vion; M. Soui; K. Ghedira, Distributed Computing and Artificial Intelligence, 15th International Conference, Volume 800 (2019), pp. 204-212 http://link.springer.com/10.1007/978-3-319-94649-8_25 (Accessed 2019-04-29) | DOI

[4] L. Cohen; R. Zivan, Autonomous Agents and Multiagent Systems (2017), pp. 111-124 | DOI

[5] R. Dechter Constraint Processing, Morgan Kaufmann, 2003, 481 pages

[6] V. Degeler; A. Lazovik, 2013 IEEE 25th International Conference on Tools with Artificial Intelligence (2013-11), pp. 167-174 | DOI

[7] A. Farinelli; A. Rogers; A. Petcu; N. R. Jennings, International Conference on Autonomous Agents and Multiagent Systems (AAMAS’08) (2008), pp. 639-646 http://dl.acm.org/citation.cfm?id=1402298.1402313 | DOI

[8] A. Farinelli; A. Rogers; A. Petcu; N. R. Jennings, Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (2008), p. 639-646. | DOI

[9] F. Fioretto; E. Pontelli; W. Yeoh, Proceedings of the International Workshop on Artificial Intelligence for Smart Grids and Smart Buildings (2017), p. 7

[10] F. Fioretto; E. Pontelli; W. Yeoh Distributed Constraint Optimization Problems and Applications : A Survey, Journal of Artificial Intelligence Research, Volume 61 (2018-03-29), pp. 623-698 | arXiv | DOI | MR | Zbl

[11] S. Fitzpatrick; L. Meertens Distributed Coordination through Anarchic Optimization, Distributed Sensor Networks, Springer, 2003, pp. 257-295 | DOI

[12] Z. Guessoum; J.-P. Briot; N. Faci, JFSMA (2004), pp. 135-148

[13] K. D. Hoang; F. Fioretto; P. Hou; Ma. Yokoo; W. Yeoh; R. Zivan, Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems (2016), pp. 597-605

[14] K. D. Hoang; P. Hou; F. Fioretto; W. Yeoh; R. Zivan; M. Yokoo, Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems (AAMAS ’17) (2017), pp. 212-220

[15] E. Kaldeli; E. U. Warriach; A. Lazovik; M. Aiello Coordinating the Web of Services for a Smart Home, ACM Transactions on the Web, Volume 7 (2013-05-01) no. 2, pp. 1-40 | DOI

[16] M. Khan; L. Tran-Thanh; W. Yeoh; N. R. Jennings, Roceedings of the International Conference on Autonomous Agents and Multiagent Systems (2018), pp. 1613-1621

[17] W. Kluegel; M. A. Iqbal; F. Fioretto; W. Yeoh; E. Pontelli, Autonomous Agents and Multiagent Systems, Volume 10643 (2017), pp. 125-142 | DOI

[18] R. N. Lass; E. Sultanik; W. C. Regli, AAAI (2008), pp. 1466-1469

[19] R. T. Maheswaran; J. P. Pearce; M. Tambe, ISCA PDCS (2004), pp. 432-439

[20] R.T. Maheswaran; J.P. Pearce; M. Tambe, Proc. of the 17th International Conference on Parallel and Distributed Computing Systems (PDCS) (2004), pp. 432-439

[21] G. Malewicz; M. H. Austern; A. J.C Bik; J. C. Dehnert; I. Horn; N. Leiser; G. Czajkowski, Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data (SIGMOD ’10) (2010), pp. 135-146 | DOI

[22] P. J. Modi; W. Shen; M. Tambe; M. Yokoo ADOPT : Asynchronous distributed constraint optimization with quality guarantees, Artificial Intelligence Journal, Volume 161 (2005) no. 1, pp. 149-180 | DOI | MR | Zbl

[23] Y. Naveh; R. Zivan; W. Yeoh, 8th International Workshop on Optimisation in Multi-Agent Systems (OPTMAS 2017) (2017), p. 14

[24] M. T. Özsu; P. Valduriez Data Replication, Principles of Distributed Database Systems, Springer, New York, 2011, pp. 459-495 | DOI

[25] C. Parra; D. Romero; S. Mosser; R. Rouvoy; L. Duchien; L. Seinturier, Proceedings of the 27th Annual ACM Symposium on Applied Computing - SAC ’12 (2012), pp. 486-491 | DOI

[26] F. Pecora; A. Cesta DCOP for Smart Homes : A Case Study, Computational Intelligence, Volume 23 (2007) no. 4, pp. 395-419 | DOI | MR

[27] A. Petcu; B. Faltings, International Joint Conference on Artificial Intelligence (IJCAI’05) (2005), pp. 266-271

[28] A. Petcu; B. Faltings, Proceedings of the National Conference on Artificial Intelligence, Volume 20 (2005), pp. 449-454

[29] A. Petcu; B. Faltings, 2007 IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT’07) (2007-11), pp. 321-327 | DOI

[30] S. Russel; P. Norvig Artificial Intelligence : a Modern Approach, Prentice-Hall, 2009

[31] P. Rust; G. Picard; F. Ramparany, 8th International Workshop on Optimisation in Multi-Agent Systems (OPTMAS 2017) (2017) https://www.cs.nmsu.edu/~wyeoh/OPTMAS2017/

[32] P. Rust; G. Picard; F. Ramparany, Autonomous Agents and Multiagent Systems – AAMAS 2017 Workshops, Best Papers, Sao Paulo, Brazil, May 8-12, 2017, Revised Selected Papers (Lecture Notes in Artificial Intelligence (LNAI)), Volume 10642 (2017), pp. 116-137 https://www.cs.nmsu.edu/~wyeoh/OPTMAS2017/docs/OptMAS_2017_paper_4.pdf (Extended Version) | DOI

[33] P. Rust; G. Picard; F. Ramparany, International Workshop on Optimisation in Multi-Agent Systems (OptMAS@AAMAS 2019) (2019)

[34] P. Rust; G. Picard; F. Ramparany, Systèmes Multi-Agents et simulation - Vingt-septièmes journées francophones sur les systèmes multi-agents, JFSMA 2019, Toulouse, France, July 3-5, 2019 (2019), pp. 31-40

[35] T. Saraç; A. Sipahioglu Generalized quadratic multiple knapsack problem and two solution approaches, Computers & Operations Research, Volume 43 (2014) no. Supplement C, pp. 78-89 http://www.sciencedirect.com/science/article/pii/S0305054813002244 | DOI | MR | Zbl

[36] H. Song; S. Barrett; A. Clarke; S. Clarke, Model-Driven Engineering Languages and Systems, Volume 8107 (2013), pp. 555-571 | DOI

[37] A. Stimson Photometry and Radiometry for Engineers, John Wiley & Sons Inc, 1974, 446 pages

[38] M. Vinyals; M. Pujol; J. A. Rodriguez-Aguilar; J. Cerquides, Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems : Volume 1 - Volume 1 (AAMAS ’10) (2010), pp. 149-156

[39] M. Vinyals; J. A. Rodriguez-Aguilar; J. Cerquides Constructing a unifying theory of dynamic programming DCOP algorithms via the generalized distributive law, Autonomous Agents and Multi-Agent Systems, Volume 22 (2010) no. 3, pp. 439-464 | DOI

[40] R. Wattenhofer Principles of Distributed Computing, 2015

[41] O. Wolfson; A. Milo The Multicast Policy and Its Relationship to Replicated Data Placement, ACM Trans. Database Syst., Volume 16 (1991) no. 1, pp. 181-205 | DOI | MR

[42] W. Yeoh; P. Varakantham; X. Sun; S. Koenig, 2015 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT) (2015), pp. 257-264 | DOI

[43] M. Yokoo; T. Ishida; E.H. Durfee; K. Kuwabara, [1992] Proceedings of the 12th International Conference on Distributed Computing Systems (1992), pp. 614-621 | DOI

[44] W. Zhang; G. Wang; L. Wittenburg, Proceedings of AAAI Workshop on Probabilistic Approaches in Search (2002)

Cité par Sources :