Article

Modeling and verifying multi-agent behaviors using predicate/transition nets

Authors:

Thomas Ioerger,

John YenAuthors Info & Claims

SEKE '02: Proceedings of the 14th international conference on Software engineering and knowledge engineering

Pages 193 - 200

https://doi.org/10.1145/568760.568794

Published: 15 July 2002 Publication History

Abstract

In a multi-agent system, how agents accomplish a goal task is usually specified by multi-agent plans built from basic actions (e.g. operators) of which the agents are capable. A critical problem with such an approach is how can the designer make sure the plans are reliable. To tackle this problem, this paper presents a formal approach for modeling and analyzing multi-agent behaviors using Predicate/Transition (PrT) nets, a high-level formalism of Petri nets. We construct a multi-agent model by representing agent capabilities as transitions. To verify a multi-agent PrT model, we adapt the planning graphs as a compact structure for the reachability analysis. We also demonstrate that, based on the PrT model, whether parallel actions specified in multi-agent plans can be executed in parallel and whether the plans guarantee the achievement of the goal can be verified by analyzing the dependency relations among the transitions.

References

[1]

D. Kinny, M. Ljungberg, A. S. Rao, E. A. Sonenberg, G. Tidhar, and E. Werner, "Planned Team Activity," Proceedings of the fourth European Workshop on Modeling Autonomous Agents in a Multi-Agent World (MAAMAW'92), 1992.]]

Digital Library

[2]

J. Yen, J. Yin, T. R. Ioerger, M. S. Miller, D. Xu, and R. A. Volz, "CAST: Collaborative Agents for Simulating Teamwork," Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI'2001), Seattle, WA, 2001.]]

[3]

B. Grosz and S. Kraus, "Collaborative Plans for Complex Group Actions," Artificial Intelligence, vol. 86, pp. 269-357, 1996.]]

Digital Library

[4]

M. J. Katz and J. S. Rosenschein, "Plans for Multiple Agents," in Distributed Artificial Intelligence, vol. II, L. Gasser and M. N. Huhns, Eds. London: Pitman/Morgan Kaufmann Publishers, 1989, pp. 197-228.]]

Digital Library

[5]

Blum and M. L. Furst, "Fast Planning through Planning Graph Analysis," Artificial Intelligence, vol. 90, pp. 281-300, 1997.]]

Digital Library

[6]

H. J. Genrich, "Predicate/Transitions Nets," in In Petri Nets: Central Models and Their Properties: Advances in Petri Nets, vol. 254, Lecture Notes in Computer Science: Springer-Verlag, 1987, pp. 207-247.]]

Digital Library

[7]

T. Murata, "Petri Nets: Properties, Analysis and Applications," Proceedings of the Institute of Electrical and Electronics Engineers, vol. 77, pp. 541-580, 1989.]]

[8]

P. R. Cohen and H. J. Levesque, "Intention Is Choice With Commitment," Artificial Intelligence, vol. 42, pp. 213-261, 1990.]]

Digital Library

[9]

Y. Shoham, "Agent-Oriented Programming," Artificial Intelligence, vol. 60, pp. 51-92, 1993.]]

Digital Library

[10]

M. Wooldridge and P. Ciancarini, "Agent-Oriented Software Engineering: The State of the Art," in Handbook of Software Engineering and Knowledge Engineering: World Scientific Publishing Co., 2001.]]

Digital Library

[11]

J. Y. Halpern and M. Y. Vardi, "Modeling Checking vs. Theorem Proving: A Manifesto," Proceedings of KR-91. Also in Lifshitz V. Artificial Intelligence and Mathematical Theory of Computation, Papers in Honor of John McCarthy, San Diego, 1991.]]

Digital Library

[12]

J. Wing, "A Specifier's Introduction to Formal Methods," Computer, pp. 8-24, 1990.]]

Digital Library

[13]

D. Moldt and F. Wienberg, "Multi-Agent-Systems Based on Colored Petri Nets," Proceedings of the 18th International Conference ICATPN'97, Toulouse, France, 1997.]]

Digital Library

[14]

H. Xu and S. M. Shatz, "A Framework for Modeling Agent-Oriented Software," Proceedings of the 21st International Conference on Distributed Computing Systems (ICDCS), Phoenix, Arizona, 2001.]]

Digital Library

[15]

D. Friha, D. Buchs, and P. Berry, "Multi-Agent System Specification using CO-OPN," University of Geneva, Technical Report CUI No. TR-93/80 Oct. 1991 1991.]]

[16]

T. Murata, P. C. Nelson, and J. Yim, "Predicate-Transition Net Model for Multiple Agent Planning," Information Science, vol. 57/58, pp. 361-384, 1991.]]

Digital Library

[17]

M. Lindqvist, "Parameterized Reachability Trees for Predicate/Transition Nets," Proceedings of the 11th International Conference on Applications and Theory of Petri Nets, Paris, 1990.]]

[18]

G. S. T. a. M. J. Flynn, "Detection and Parallel Execution of Independent Instructions," IEEE Transactions Software Engineering, vol. C-19, pp. 889-895, 1970.]]

[19]

C. Knoblock, "Generating Parallel Exectuion Plans with a Partial-Order Planner," Proceedings of Artificial Intelligence Planning and Scheduling 1994, Chicago, 1994.]]

Cited By

Aldahash NKing SBenabid A(2023)Interaction Petri Nets for Modeling Multiagent Interactions2023 Congress in Computer Science, Computer Engineering, & Applied Computing (CSCE)10.1109/CSCE60160.2023.00339(2061-2068)Online publication date: 24-Jul-2023
https://doi.org/10.1109/CSCE60160.2023.00339
Van TFredivianus NTran HGeihs KHuynh T(2018)Formal Verification of ALICA Multi-agent Plans Using Model CheckingProceedings of the 9th International Symposium on Information and Communication Technology10.1145/3287921.3287947(351-358)Online publication date: 6-Dec-2018
https://dl.acm.org/doi/10.1145/3287921.3287947
Bakar NSelamat A(2018)Agent systems verificationApplied Intelligence10.1007/s10489-017-1112-z48:5(1251-1274)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s10489-017-1112-z
Show More Cited By

Index Terms

Modeling and verifying multi-agent behaviors using predicate/transition nets
1. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence
      1. Intelligent agents
      2. Multi-agent systems
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Formal software verification
  2. Software organization and properties
    1. Software functional properties
      1. Formal methods
    2. Software system structures
      1. Software system models
        Petri nets

Recommendations

Modelling actor programs using Predicate/Transition nets
PDP '95: Proceedings of the 3rd Euromicro Workshop on Parallel and Distributed Processing

The actor model is a model of concurrent computation which is powerful enough to represent all the operations needed to exploit parallel and distributed machines. In this paper, we propose to model actor programs with Predicate/Transition nets. ...
Verifying heterogeneous multi-agent programs
AAMAS '14: Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems

We present a new approach to verifying heterogeneous multi-agent programs --- multi-agent systems in which the agents are implemented in different (BDI-based) agent programming languages. Our approach is based on meta-APL, a BDI-based agent programming ...
Model checking multi-agent systems with logic based Petri nets

We introduce a class of Petri nets, simple logic Petri nets ( SLPN ), that are based on logical expressions . We show how this type of nets can be efficiently mapped into logic programs with negation: the corresponding answer sets describe ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

SEKE '02: Proceedings of the 14th international conference on Software engineering and knowledge engineering

July 2002

859 pages

ISBN:1581135564

DOI:10.1145/568760

Conference Chairs:
Genny Tortora,
Shi-Kuo Chang

Copyright © 2002 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 July 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SEKE02

SEKE02: 14th International Conference on Software Engineering and Knowledge Engineering

July 15 - 19, 2002

Ischia, Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
262
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Aldahash NKing SBenabid A(2023)Interaction Petri Nets for Modeling Multiagent Interactions2023 Congress in Computer Science, Computer Engineering, & Applied Computing (CSCE)10.1109/CSCE60160.2023.00339(2061-2068)Online publication date: 24-Jul-2023
https://doi.org/10.1109/CSCE60160.2023.00339
Van TFredivianus NTran HGeihs KHuynh T(2018)Formal Verification of ALICA Multi-agent Plans Using Model CheckingProceedings of the 9th International Symposium on Information and Communication Technology10.1145/3287921.3287947(351-358)Online publication date: 6-Dec-2018
https://dl.acm.org/doi/10.1145/3287921.3287947
Bakar NSelamat A(2018)Agent systems verificationApplied Intelligence10.1007/s10489-017-1112-z48:5(1251-1274)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s10489-017-1112-z
Farinelli ARaeissi MMarchi NBrooks NScerri P(2017)Interacting with team oriented plans in multi-robot systemsAutonomous Agents and Multi-Agent Systems10.1007/s10458-016-9344-631:2(332-361)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s10458-016-9344-6
Chu WYang CLu CChang CHsueh NHsu THung S(2014)An Approach of Quality of Service Assurance for Enterprise Cloud Computing (QoSAECC)2014 International Conference on Trustworthy Systems and their Applications10.1109/TSA.2014.11(7-13)Online publication date: Jun-2014
https://doi.org/10.1109/TSA.2014.11
Brooks Nde Visser EChabuk TFreedy EScerri PGini MShehory OIto TJonker C(2013)An approach to team programming with markup for operator interactionProceedings of the 2013 international conference on Autonomous agents and multi-agent systems10.5555/2484920.2485222(1355-1356)Online publication date: 6-May-2013
https://dl.acm.org/doi/10.5555/2484920.2485222
Brooks Nde Visser EChabuk TFreedy EScerri PGini MShehory OIto TJonker C(2013)An approach to team programming with markup for operator interactionProceedings of the 2013 international conference on Autonomous agents and multi-agent systems10.5555/2484920.2485107(1133-1134)Online publication date: 6-May-2013
https://dl.acm.org/doi/10.5555/2484920.2485107
Borhen MHassine KBarkaoui K(2013)Modeling Migration of Mobile AgentsBusiness Process Management Workshops10.1007/978-3-642-36285-9_54(530-540)Online publication date: 2013
https://doi.org/10.1007/978-3-642-36285-9_54
Hamrouni NAbderrahim Z(2012)Looking for verification and validation of a Multi agent System using new formalism: APN2012 6th International Conference on Sciences of Electronics, Technologies of Information and Telecommunications (SETIT)10.1109/SETIT.2012.6481885(30-35)Online publication date: Mar-2012
https://doi.org/10.1109/SETIT.2012.6481885
Reza HOgaard K(2011)Modeling of UAS Swarms Using Dynamic and Re-Configurable Software ArchitectureProceedings of the 2011 21st International Conference on Systems Engineering10.1109/ICSEng.2011.75(377-382)Online publication date: 16-Aug-2011
https://dl.acm.org/doi/10.1109/ICSEng.2011.75
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten