Groupe Colline : De l’émergence aux systèmes multi-agents Responsable : Gauthier Picard (EMSE)

L’émergence porte sur l’apparition de structures nouvelles et cohérentes, de formes, de propriétés durant le processus d’auto-organisation dans les systèmes complexes [24]. Ainsi, le processus d’émergence est vu comme une boîte noire. On ne peut discerner que les entrées de plus bas niveaux et les sorties de plus hauts niveaux.
C’est dans la deuxième moitié du XXe siècle que la science s’est dotée de moyens en phy-sique, en mathématiques et en informatique pour explorer les systèmes complexes où l’émergence prend sa source. C’est notamment le cas de plusieurs théories :

  • la théorie des systèmes complexes adaptatifs (notamment au Santa Fe Institute avec Holland, Kauffman et Langton) : l’émergence fait référence aux " patterns " du macro niveau apparaissant dans les systèmes d’agents en interaction ;
  • la théorie des systèmes dynamiques non linéaires issue de la théorie du chaos : le travail porte en grande partie sur les attracteurs ; l’école synergétique fondée parHaken qui étudie l’auto-organisation dans les systèmes physiques ;
  • la thermodynamique " loin et autour de l’équilibre " introduite par Prigogine : les phénomènes émergents sont les structures dissipatives apparaissant à partir de conditions loin de l’équilibre.
La question de l’émergence suscite un regain d’intérêt dans l’étude des systèmes artificiels car si nous disposions de méthodes garantissant l’émergence de fonctions désirées sans les avoir explicitement spécifiées, cela réduirait du même coup la charge et la durée de concep-tion.

L’étude de l’émergence par expérimentation

Les SMA étant des collectifs d’agents autonomes en interaction ils peuvent constituer un cadre technologique pertinent pour observer - et maîtriser - l’émergence de phénomènes. C’est l’objet du groupe de travail Colline (COLLectif, INteraction, Emergence). L’imprévu étant inhérent à la vie de ces systèmes, l’auto-organisation, qui correspond à un changement décidé de manière autonome, devient un moyen pour parvenir à surmonter les perturbations éventuelles de l’environnement.
La problématique du groupe est d’étudier les théories, méthodes et techniques pour abou-tir au phénomène émergent désiré en modifiant l’organisation d’un système. Nous abordons ces questions d’émergence et d’autoorganisation notamment à partir d’études de cas grâce auxquelles chaque participant peut concrètement montrer son approche.
Nous étudions actuellement celle de la gestion d’une chaîne de production autour d’une plate-forme MASC qui a été développée spécifiquement. Les scénarios supposent l’arrivée dans le temps de pièces sur lesquelles doivent s’effectuer des usinages de durée variable et selon une séquence déterminée, mais qui doivent aussi être usinées avant une certaine date. Durant ces sessions de nouvelles pièces arrivent avec leurs délais, des pannes surviennent sur les stations de travail ou des opérateurs peuvent faire défaut de manière inopinée. L’émergence ne porte pas sur l’apparition d’un phénomène inattendu, car l’activité collective ne produit que des pièces usinées. Mais dans la capacité à trouver des solutions optimales ou quasi-optimales alors que les agents (possiblement les pièces, les stations ou les opérateurs) n’ont qu’une connaissance très partielle du problème global et que des événements imprévus sont fréquents. Des résultats très intéressants ont été obtenus comparativement à des algo-rithmes standards de résolution de problèmes de satisfaction de contraintes distribués (DisCSP) [15].

Techniques multi-agents auto-organisatrices

Plusieurs mécanismes conduisant à l’auto-organisation et conséquemment à l’émergence de phénomènes - ont été étudiés dans diverses applications [5]. Ils peuvent globalement être décomposés en quatre classes [50] selon les mécanismes employés :
  • Les interactions directes entre agents employant des principes de diffusion et de lo-calisation : ces mécanismes conduisent à des modifications de la topologie et donc du place-ment des agents et de leurs capacités d’échanges. Cette approche a notamment été étudiée dans les projets Rivage et TOTA [51][37].
  • Les interactions indirectes entre agents telles la stigmergie : cette méthode a conduit à des résultats concrets pour la coordination globale de tâches. C’est le cas pour la gestion de production [31] [8] [47].
  • Les comportements de renforcement des agents : une récompense renforce le com-portement de l’agent, tandis qu’une punition inhibe celui-ci. Un exemple typique de cette approche est donné dans [56].
  • La coopération locale entre agents où l’agent cherche à atteindre ses objectifs tout en respectant au mieux les besoins des agents voisins pour satisfaire les leurs. Cette approche est employée dans la théorie des Amas, par exemple pour la gestion d’emploi du temps ou l’affectation de fréquences [45][46].

Desmétriques pour l’évaluation des solutions émergentes

Ces travaux représentent un premier pas vers l’étude et la compréhension des solutions émergentes de résolution de problèmes difficiles. Les perspectives de développement et les enjeux concernent l’établissement de métriques pour l’évaluation des solutions émergentes de résolution de problèmes ainsi que l’étude des problèmes multi-échelles et dynamiques en temps continu (biologie computationnelle, conception de systèmes complexes, par exemple). En effet, les approches émergentes pourront montrer leur intérêt applicatif dès lors que leur avantages seront soulignés par des mesures sur des propriétés propres aux systèmes auto-organisateurs : dynamique (adaptation aux perturbations, minimisation de l’impact endogène d’un changement, etc.), décentralisation (taux de distributivité, taux de centralisation, nombre de points de rupture, etc.).

  • [24] G.a Di Marzo Serugendo, M.-P Gleizes, and A. Karageorgos. Self-Organisation and Emergence in Multi-Agent Systems : An Overview. Dans : Informatica, Vol. 30 N. 1, p.45-54, January 2006.
  • [15] G. Clair, M.-P. Gleizes, E. Kaddoum and G. Picard. Self-Regulation in Self-Organising Multi-Agent Systems for Adaptive and Intelligent Manufacturing Control. In Second IEEE International Conference on Self-Adaption and Self-Organization (SASO 2008), Venice, Italy, October 20-24, 2008.
  • [5] C. Bernon, V. Chevrier, V. Hilaire, and P. Marrow, Applications of self-organising multi-agent systems : an initial framework of comparison. Informatica, Slovenia. 2005.
  • [50] G. Serugendo,M-P Gleizes et A. Karageorgos (2006) Sel-organization and emer-gence in MAS : an overview, Informatica, vol. 30, 45-54.
  • [51] D. Servat, J. Leonard, E. Perrier, and J. P. Treuil. The Rivage project : a new ap-proach for simulating runoff dynamics. J.Feyen and K.Wiyo, (Eds.). Modelling of trans-port processes in soils, pp. 592- 601. Wageningen Press, Leuven, 1999.
  • [37] M. Mamei, M. Vasirani, and F. Zambonelli. Selforganising spatial shapes in mobile particles : the TOTA approach. Engineering Self-Organising System. S. Brueckner et al. (Eds), Lecture Notes in Artificial Intelligence, volume 3464, pp. 138-153. Springer-Verlag, Berlin, 2005.
  • [31] T. Ishida, L. Gasser, and M. Yoko. Organisation selfdesign in distributed produc-tion systems. IEEE Transactions on Knowledge and Data Engineering, 4(2) : 123-134, IEEE Computer Society, Los Alamitos, CA, USA, 1992.
  • [8] S. Brueckner. Return from the Ant : Synthetic Ecosystems for Manufacturing Control. PhD thesis, Depar tment of Computer Science, Humboldt University Berlin, 2000.
  • [45] G. Picard, C. Bernon and M.-P. Gleizes. ETTO : Emergent Timetabling Organiza-tion. In proc. of CEEMAS’ 05, volume 3690 of LNAI, Springer-Verlag, pages 440- 449, 2005.
  • [46] G. Picard, M.-P. Gleizes, and P. Glize. Distributed Frequency Assignment Using Cooperative Self- Organization. In First IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO’07), Boston, Mass., USA, July 9-11, 2007.
  • [47] A. Reitbauer, A. Battino, A. Karageorgos, N.Mehandjiev, P. Valckenaers, and B. Saint-Germain - The MaBE middleware : extending multi-agent systems to enable open business collaboration. In 6th IFIP International Conference on Information Technology for Balanced Automation Systems inManufacturing and Services (BASYS’04), 2004.
  • [56] D. Weyns, K. Schelfthout, T. Holvoet, and O.Glorieux. Role based model for adap-tive Agents. Fourth Symposium on Adaptive Agents and Multiagent Systems at the AISB ’04 Convention, 2004.

Accueil  | Actualités  | Groupes  | Equipes  | Livres  | Cours  | HDRs / Thèses  | JFSMA  | Liens  | 


GDRI3 CNRS


Modifié en par Cédric Herpson