Open protocol design for complex interactions in multi-agent systems

ABSTRACT

This paper proposes a generic approach or protocol engineering through the analysis,the specification,and the verification of such protocols when several agents are involved. This approach is three folds:1)Starting from semi-formal specification by means o Protocol Diagrams (AUML),both formal specification of interaction protocols and their verification are allowed thanks to Colored Petri Nets (CPN);2) Debugging and qualitative analysis o interactions are based on distributed observation associated with the true concurrency semantics (i.e.CPN unfolding)and ;3)CPN formalism is extended to Recursive CPN (RCPN)with abstraction in order to deal with open protocols.The main interest of abstraction is the design of fexible protocols giving agents more autonomy during interaction.In addition,abstraction allows concise modeling and easier verification. measures,performance measures .

REFERENCES

• 1: R. S. Cost,Y. Chen,T. Finin,Y. Labrou,and Y. Peng. Modeling agent conversations with colored Petri nets.In proc. of the 3rd International Conference on Autonomous Agents (Agents '99), Workshop on Agent Conversation Policies, Seattle, Washington ,May 1999
• 2: M. d'Inverno , D. Kinny , M. Luck, Interaction Protocols in Agentis, Proceedings of the 3rd International Conference on Multi Agent Systems, p.112, July 03-07, 1998
• 3: A. El-Fallah-Seghrouchni and S. Haddad. A recursive model or distributed planning. In proc. of the 2nd International Conference on Multi-Agent Systems, Kyoto, Japon , 1996
• 4: A. El-Fallah-Seghrouchni, S. Haddad, and H. Mazouzi. A formal study of interactions in multi-agent systems. In Proc.of the 14th International Conference on Computers and Their Applications (ISCA CATA-99), ISBN:1-880843-27-7, Cancun, Mexico , pages 240--245, April 1999
• 5: Amal El Fallah-Seghrouchni , Serge Haddad , Hamza Mazouzi, Protocol Engineering for Multi-agent Interaction, Proceedings of the 9th European Workshop on Modelling Autonomous Agents in a Multi-Agent World: MultiAgent System Engineering, p.89-101, June 30-July 02, 1999
• 6: Javier Esparza , Stefan Römer , Walter Vogler, An Improvement of McMillan's Unfolding Algorithm, Proceedings of the Second International Workshop on Tools and Algorithms for Construction and Analysis of Systems, p.87-106, March 27-29, 1996
• 7: J.Fidge. Timestamps in message passing systems that preserve the partial order ring. In Proc.11th Australian Computer Science Conference , pages 55--66, february 1988
• 8: FIPA. Foundation or intelligent physical agents. FIPA 97 Specification. Part 2, Agent Communication Language, http://www..pa.org , 1997
• 9: Serge Haddad , Denis Poitrenaud, Theoretical Aspects of Recursive Petri Nets, Proceedings of the 20th International Conference on Application and Theory of Petri Nets, p.228-247, June 21-25, 1999
• 10: Kurt Jensen, Coloured Petri nets: basic concepts, analysis methods and practical use, vol. 2, Springer-Verlag, London, 1995
• 11: K. Jensen. Design/cpn, version 4.0. http://www.daimi.au.dk/designCPN/, University of Aarhus, Denmark, 1999
• 12: Kurt Jensen , Grzegorz Rozenberg, High-level Petri nets: theory and application, Springer-Verlag, London, 1991
• 13: P. King and R. Pooley. Using UML to derive stochastic petri net models. In Proc. of the 5th UK Performance Engineering Workshop (UKPEW '99), pages 45--56, 1999
• 14: J. Koning, G. Francois,and Y. Demazeau. Formalization and pre-validation or interaction protocols in multi agent systems. In 13th European Conference on Artificial Intelligence, Brighton, 1998, 1998
• 15: Jean-Luc Koning , Marc-Philippe Huget , Jun Wei , Xu Wang, Extended Modeling Languages for Interaction Protocol Design, Revised Papers and Invited Contributions from the Second International Workshop on Agent-Oriented Software Engineering II, p.68-83, May 29, 2001
• 16: KQML.Specification of the kqml agent-communication language. Technical report, DARPA Knowledge Sharing Initiative External Interfaces Working Group, http://www.cs.umbc.edu/agents/kse/kqml/, 1993
• 17: Kenneth L. McMillan, Using Unfoldings to Avoid the State Explosion Problem in the Verification of Asynchronous Circuits, Proceedings of the Fourth International Workshop on Computer Aided Verification, p.164-177, June 29-July 01, 1992
• 18: M. Niellsen, G. Plotkin, and G. Winskel. Petri nets, event structures and domains. Theoretical Computer Science ,13(1):85--108, 1980
• 19: J. Odell, H. V. D. Parunak, and B. Bauer. Extending UML or agents. In Proc. of Agent-Oriented Information Systems (AOIS) Workshop at AAAI, 2000
• 20: James Odell , H. Van Dyke Parunak , Bernhard Bauer, Representing agent interaction protocols in UML, First international workshop, AOSE 2000 on Agent-oriented software engineering, p.121-140, January 2001, Limerick, Ireland
• 21: V. Parunak. Visualizing agent conversations: Using enhanced Dooley graphs or agent design and analysis. In Proc. of International Conference on Multi Agent Systems (ICMAS '96), AAAI press., pages 275--282, 1996
• 22: R. G. Pettit and H. Gomaa. Validation of dynamic behavior in UML using colored Petri nets. In Proc.of UML'2000, 2000

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Formal methods

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Validation

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Pattern analysis

General Terms:
Design, Verification

Keywords:
AUML, colored petri nets, distributed observation, formal specification, protocol diagrams, true concurrency, validation