Collective and Emergent Problem Solving Based on Multi-Agent Systems: Principles and Applications
Résolution Émergente et Collective de Problèmes par Systèmes Multi-Agents: Principes et Applications
OPEN ACCESS
A multi-agent system is composed of numerous entities,called agents,interacting in various ways between them and their common environment.This technology is applied in many domains like computer vision,robotics,system simulation or electronic commerce.We consider that problems occuring in signal processing could also be tackled by this technology.
We present first the basic tools available for multi-agent systems designers:models,platforms and methodologies.Two projects illustrate our purpose:SCALA in the management of aerospace fighter patrol,and goods routing. We focus then on the adaptation ability of these systems considered as an emergent problem solving question.We detailed in this field the AMAS (Adaptive Multi-Agent System) theory allowing a MAS design where the global fonction is derived from the cooperative self-organisation of its components.An example on flood forecast gives implementation information of this theory.
Résumé
Un système multi-agent est constitué d’un grand nombre d’entités,appelées agents,en interaction entre elles au sein d’un même environnement. Cette technologie aborde de nombreux domaines d’applications comme la vision par ordinateur,la robotique,la simulation de systèmes,le commerce électronique. Nous considérons que les questions abordées en traitement du signal sont très pertinentes dans un cadre multi-agent. Nous présentons d’abord les principaux outils dont disposent les concepteurs de systèmes multi-agents à savoir:des modèles,des plates-formes et des méthodes de développement. Puis,le projet SCALA de simulation de résolution de problèmes par des patrouilles aériennes et un projet de simulation de système de transports illustrent la résolution de problèmes à l’aide de systèmes multi-agents.
Ensuite,nous nous intéressons plus particulièrement aux capacités d’adaptation de tels systèmes que nous abordons comme une question de résolution émergente de problèmes. Dans ce cadre nous décrivons en détail la théorie AMAS (Adaptive Multi-Agent System) qui permet de concevoir des systèmes dont la fonction globale émerge à partir d’un processus d’auto-organisation coopérative de ses parties. Une application en prévision de crues donne une indication plus précise des capacités de telles approches.
Multi-agent systems, cooperation, self-organisation, emergence, neo-computation.
Mots clés
Système multi-agent,coopération,auto-organisation,emergence,néo-computation.
APPRIOU A. (2003), Conférence COGIS: Commande, Optimisation, Gestion Intelligente & architecture des Senseurs pour les systèmes – Rapport DGA: N° MS 03I018/DSP/SREA/SC/SR – Juin 2003.
ARLABOSSE F., GLEIZES M.-P., OCCELLO M. (2004), Méthodes de conception, Observatoire Français des Techniques Avancées: Systèmes Multi-Agents Série ARAGO 29.
BELLIFEMINE F., POGGI A., RIMASSA G. (2001), Developing multi agent systems with a FIPA-compliant agent framework, Software Practice & Experience, 31:103-128.
BERGENTI F., GLEIZES M.-P., ZAMBONELLI F. (2004), Methodologies and Software Engineering for Agent Systems, Kluwer.
BERNON C., GLEIZES M.-P., PICARD G., and GLIZE P. (2002), The ADELFE Methodology For an Intranet System Design, Fourth International Bi-Conference Workshop on Agent-Oriented Information Systems (AOIS-2002), 27-28 May 2002, Toronto (Ontario, Canada) at CAiSE’02. BERTALANFFY VON L., « Théorie générale des systèmes », Editions Dunod, 1993.
BOISSIERO.,GITTONS.,GLIZEP. (2004),Caractéristiques des systèmes et des applications Observatoire Français des Techniques Avancées: Systèmes Multi-Agents Série ARAGO 29.
BOND A.H., GASSER L. (1988), Readings in Distributed Artificial Intelligence, Morgan Kaufman.
BROOKS R. A. (1986), A robust control system for a mobile robot. IEEE Journal of Robotics and Automation, 2(1):14-23, 1986.
BRUNNER K. A. (2002), What’s Emergent in Emergent Computing?, Proceedings of the EMCSR, E. Trappl editor.
BURA S., DROGOULA., FERBER J., JACOPIN E. (1991), Eco-résolution: un modèle de résolution de problèmes par interactions RFIA.
BURRAFATO P., COSSENTINO M. (2002), Designing a Multi-Agent Solution for a Bookstore with the PASSI Methodology, AOIS’02 at CAiSE’02, Toronto, May 2002.
CAIRE G., LEAL F., CHAINHO P., EVANS R., GARIJO F., GOMEZ J., PAVON G., KEARNEY P., STARK J. and MASSONET P. (2001), Agent Oriented Analysis using MESSAGE/UML – AOSE 2001.
CAMPS V., GLEIZES M.-P., GLIZE P. (1998), Une théorie des phénomènes globaux fondée sur des interactions locales,Actes des Sixième journées francophones IAD&SMA Pont-à-Mousson, Editions Hermès, Novembre, 1998.
CASTRO J., KOLP M. and MYLOPOULOS J. (2001), À Requirementsdriven Development Methodology, In Proceedings of the 13th International Conference on Advanced Information Systems Engineering (CAiSE’01), Stafford, UK – June 2001.
SMITH R.G., (1980) The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver. IEEE Transactions on Computers C-29(12).
DEGIRMENCIYAN-CARTAULT I., MARC F., (2002), SCALA: une approche multi-agent pour la conception de systèmes complexes, Journées Francophones sur les Systèmes Multi-Agents, P. Mathieu et J.P. Müller éditeurs, Hermès, 2002.
DELOACH S.A., WOOD M. (2001), Developing Multiagent Systems with agentTool, in Intelligent Agents VII. AgentTheories Architectures and Languages, 7th International Workshop (ATAL 2000, Boston, MA,USA, July 7-9, 2000), C. Castelfranchi,Y. Lesperance (Eds.). LNCS Vol. 1986, Springer Verlag, Berlin, 2001.
DEMAZEAUY. (2001),VOYELLES, Habilitation à Diriger des recherches, INP Grenoble, 2001.
DROGOULA., FERRAND N., MÜLLER J.P. (2004), Emergence: de l’articulation du local au global, Observatoire Français des Techniques Avancées: Systèmes Multi-Agents Série ARAGO 29.
ENGELMORE R., MORGAN T. (1988), Blackboard systems. – Addison Wesley 1988.
FERBER J. (1995), Les systèmes multi-agents. Vers une intelligence collective, Editions InterEditions 1995.
FININT., FRITZSON R., MCKAY D., MCENTIRE R. (1994), « KQML as an Agent Communication Language», Proceedings of the 3rd International Conference on Information and Knowledge Management (CIKM’94), 1994.
FIPA (2000), Contract net interaction protocol specification, 2000. Identifier 00029, http://www.pa.org/specs/pa00029/.
FORREST J. (1990), « Emergent computation: self-organizing, collective, and cooperative phenomena in natural and artificial computing networks », Proceedings of the ninth annual CLNS conference, 1990.
GASSER L., BRAGANZA C., HERMAN N. (1987), Implementing Distributed AI Systems Using MACE. Proceeding of the Third IEEE Conference on Artificial Intelligence Applications 1987, (p 315-320).
GEORGÉ J.-P., GLEIZES M.-P., GLIZE P., and RÉGIS C. (2003), Realtime Simulation for Flood Forecast: an Adaptive Multi-Agent System STAFF, Proc. of the AISB’03 symposium on Adaptive Agents and Multi-Agent Systems, Univ. of Wales,Aberystwyth, 2003.
GEORGÉ J.-P., GLEIZES M.-P., GLIZE P. (2003), Conception de systèmes adaptatifs à fonctionnalité émergente: la théorie des AMAS - Revue d’Intelligence Artificielle, 2003.
GEORGÉ J.-P., EDMONDS B., GLIZE P. (2004), Self-organizing adaptivemulti-agent systems work, Chapter 16 in Methodologies and Software Engineering for Agent. The Agent-Oriented Software Engineering handbook, Bergenti F., Gleizes M.-P., Zambonelli F. Editors, Kluwer Publishing.
GLEIZES M.-P., GLIZE P. (1990), Les systèmes multi-experts. Collection technologie de pointe. Editions HERMES 1990.
GOLDSTEIN J. (1999), Emergence as a Construct: History and issues, Emergence Volume 1, Issue 1.
GUESSOUM Z., DOJAT M. (1996), A real-time agent model in an asynchronous object environment, in W Van de Velde et J. Perram (eds) Agent Breaking Away LNAI, Vol 1038, pp. 190-203 Eindhoven Springer Verlag, 1996.
GUTKNECHT O., FERBER J. (1998), À meta-model for the analysis and design of organizations in Multi-Agent Systems, In Demazeau Y., editor, Proceedings of ICMAS’98, Paris, France. IEEE Computer Society, 1998.
HLA 1, High Level Architecture – Livre pédagogique http://www.mite.org/technology/hla-book
HLA2 Standardisation HLA: DMSO http://dmso.mil SISO http://siso.sc.ist.ucf.edu/
JACOBSON I.,BOOCH G. and RUMBAUGH J. (1999), The Unified Software Development Process,Addison-Wesley, 1999.
KAEBLING L.P., LITTMAN M.L., MOORE A.W. (1996), Reinforcement learning: a Survey, Journal of Artificial Intelligence Research 4, (1996), 237-285.
KINNY D., GEORGEFF M. and RAO A. (1996), À Methodology and Modelling Technique for Systems of BDI Agents, In Van Der Velde, W., Perram, J. (eds.): Agents Breaking Away: Proc. of the Seventh European Workshop on Modelling Autonomous Agents in a MultiAgent World, 1996. MAAMAW’96, (LNAI Vol. 1038). SpringerVerlag: Heidelberg, Germany (1996).
LIND J. (2001), Iterative Software Engineering for Multiagent Systems: the MASSIVE Method, LNCS Vol. 1994, 2001.
MATHIEU P., TAQUETA. (2000), Une forme de négociation pour les systèmes multi-agents Journées francophones IAD-SMA, St Jean de Vêtre, Hermès, 2000.
ODELL J., PARUNAK H.V. and BAUER B. (2000), Extending UML for Agents, In Proceedings of the Agent Oriented Information Systems (AOIS) Workshop at the 17th National Conference on Artificial Intelligence (AAAI), 2000.
PADGHAM L., and WINIKOFF M. (2002), Prometheus: A Pragmatic Methodology for Engineering Intelligent Agents, Workshop on Agent-Oriented Methodologies at OOPSLA 2002.
PIERRE D., BOURDON F., NÉGRET J.-M. (2004), Standards et normes In journée 29 « Systèmes multi-agents » de l’Observatoire Français des Techniques Avancées - Arago, 2004.
PFEIFER R., SCHEIER C. (2001), Understanding intelligence, The MIT Press, 2001.
RAO A.S., GEORGEFF M. (1991), Modeling Rational Agents within a BDI-Architecture In J. F. Allen, R. Fikes and E. Sandewall (Eds.), Proceedings of the International Conference on Knowledge Representation and Reasoning, Cambridge, MA, PP 473-484 Morgan Kaufmann.
REE (2004), Revue de l’électricité et de l’électronique, Numéro spécial «Exploitation intelligente des senseurs dans les systèmes complexes», ISSN 1265-6534, n° 6/7.
RÉGIS C., SONTHEIMER T., GLEIZES M.-P., GLIZE P. (2002), STAFF: un système multi-agent adaptatif en prévision de crues, 10e Journées Francophones d’Intelligence Artificielle Distribuée et des Systèmes Multi-Agents, Editions Hermès.
SIERRA C. (2002), Autonomous Agents and Multi-Agent Systems, Upgrade: European Online Magazine, Editors: Barber F., Botti V.J., Koehler J. http://www.upgrade-cepis.org, Vol. 3 N°5.
SONTHEIMER T. (1999), Modèle adaptatif de prévision de crues par systèmes multi-agents auto-organisateurs – Rapport de stage Institut Universitaire Professionnalisé – Direction Régionale de l’Environnement Midi-Pyrénées.
SONTHEIMER T., CORNUAU P., VIDAL J.J., GLIZE P. (2001), Application d’un système adaptatif pour la prévision des crues dans le bassin de la Garonne. Conférence SIRNAT’01, Systèmes d’Informations et Risques Naturels.
STONE P., VELOSO M. (2000), Multiagent Systems: A Survey from a Machine Learning Perspective, Autonomous Robots 8, pp345-383, 2000, Kluwer Academic Publishers.
WEISS G., editor (1997), Distributed Artificial Intelligence Meets Machine Learning, Lecture Notes in Artificial Intelligence Volume 1221, Springer-Verlag.
WITTIG T., (1992) ARCHON, an architecture for multi-agent systemsThies Wittig editor - Ellis Horwood Limited, 1992.
WOLPERT D. H. and MACREADY W. G. (1997), No free lunch theorems for optimization, IEEE Transactions on Evolutionary Computation Vol.1 N°1.
WOOLDRIDGE M., JENNINGS N.R. (1995), Intelligent Agents: Theory and Practice. In Knowledge Engineering Review Vol.10 N°2.
WOOLDRIDGE M., JENNINGS N.R. and KINNY D. (1999), A Methodology for Agent-Oriented Analysis and Design, In Proceedings of the 3rd International Conference on Autonomous Agents (Agents 99), pp 69-76, Seattle, WA, May 1999.