Article

Multiagent Planning as Control Synthesis

Authors:

Kiam-Tian Seow,

Makoto YokooAuthors Info & Claims

AAMAS '04: Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems - Volume 2

Pages 972 - 979

Published: 19 July 2004 Publication History

Abstract

This paper proposes a new multiagent planning approach to coordination synthesis that views distributed agents as discrete-event processes. The connection between discrete-event control synthesis and coordination planning is first established, thereby enabling the exploitation of the vast body of knowledge and associated software synthesis tools from ýThe Supervisory Control of Discrete-Event Systemsý for automatic coordination synthesis of distributed agents. Importantly, these coordinating agents designed collectively generate a behaviour guaranteed not to contradict any specified inter-agent constraint, is nonblocking and optimal. A simple planning methodology is proposed in terms of procedures supported by CTCT, an existing, freely available design tool developed based on the control synthesis framework.Asimple example illustrates the use of the CTCT-based methodology to synthesize coordination modules for distributed agents. Discussions in relation to previous work examine the relative significance of the new multiagent planning framework.

References

[1]

{1} S. Cammarata, D. MacArthur, and R. Steeb. Strategies of cooperation in distributed problem solving. In Proceedings of The International Joint Conference on Artificial Intelligence, pages 767-770, Karlsruhe, Germany, August 1983.

[2]

{2} E. M. Clarke and E. A. Emerson. Design and synthesis of synchronization skeletons using branching time temporal logic. In Proceedings of 1981 Workshop on Logics of Programs, pages 52-71. Springer Verlag, New York, 1982.

Digital Library

[3]

{3} E. M. Clarke, O. Grumberg, and D. A. Peled. Model Checking. MIT Press, Cambridge, MA, U.S.A, 2000.

Digital Library

[4]

{4} K. S. Decker and V. R. Lesser. Designing a family of coordination algorithms. In Proceedings of The First International Conference on MultiAgent Systems (IC- MAS95), pages 73-80, San Francisco, USA, June 1995.

[5]

{5} E. H. Durfee. Planning in distributed artificial intelligence. In G. M. P. O. 'Hare and N. R. Jennings, editors, Foundations of Distributed Artificial Intelligence, pages 231-245. John Wiley and Sons, Inc., New York, 1996.

Digital Library

[6]

{6} E. Ephrati and J. S. Rosenschein. Multi-agent planning as the process of merging distributed sub-plans. In Proceedings of The Twelfth International Workshop on Distributed Artificial Intelligence, pages 115-129, Hidden Valley, PA, U.S.A, May 1993.

[7]

{7} M. P. Georgeff. Communication and action in multiagent planning. In Proceedings of The National Conference on Artificial Intelligence, pages 125-129, Washington, DC, U.S.A, August 1983.

[8]

{8} F. Giunchiglia and P. Traverso. Planning as model checking. In L. Cavedon, A. Rao, and W. Wobcke, editors, Recent Advances in AI Planning, Lecture Notes in Artificial Intelligence, Vol 1809 - Subseries of LNCS, pages 1-20. Springer Verlag, Berlin, Heidelberg, Germany, 1999.

Digital Library

[9]

{9} J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Reading, MA: Addison-Wesley, 1979.

Digital Library

[10]

{10} T. Ishida, M. Yokoo, and L. Gasser. An organizational approach to adaptive production systems. In Proceedings of the Eighth National Conference on Artificial Intelligence , pages 52-58, Boston, MA, U.S.A, July 1990.

[11]

{11} N.R. Jennings. Coordination techniques for distributed artificial intelligence. In G. M. P.O.'Hare and N.R. Jennings, editors, Foundations of Distributed Artificial Intelligence , pages 187-210. John Wiley and Sons, Inc., New York, 1996.

Digital Library

[12]

{12} N. R. Jennings. On agent-based software engineering. Artificial Intelligence, 117(2):277-296, 2000.

Digital Library

[13]

{13} T. W. Malone and K. Crowston. The interdisciplinary study of coordination. ACM Computing Surveys , 26(1):87-119, March 1994.

Digital Library

[14]

{14} G. A. Papadopoulos. Models and technologies for the coordination of internet agents: A survey. In A. Omicini, F. Zambonelli, M. Klusch, and R. Tolksdorf, editors, Coordination of Internet Agents: Models, Technologies, and Applications, chapter 2, pages 25-56. Springer Verlag, March 2001.

Digital Library

[15]

{15} P. J. Ramadge and W. M. Wonham. Supervisory control of a class of discrete event processes. SIAM Journal of Control and Optimization, 25(1):206-230, January 1987.

Digital Library

[16]

{16} R. Su and W. M. Wonham. Supervisor reduction for discrete-event systems. In Proceedings of The 2001 Conference on Information Sciences and Systems, pages 786-791, The Johns Hopkins University, Baltimore, Maryland, U.S.A, March 2001.

[17]

{17} W. van der Hoek and M. Wooldridge. Tractable multiagent planning for epistemic goals. In Proceedings of The First International Conference on Autonomous Agents and MultiAgent Systems (AAMAS2002), pages 1167- 1174, Bologna, Italy, July 2002.

Digital Library

[18]

{18} G. Weiss, editor. Multiagent System: A Modern Approach to Distributed Artificial Intelligence. The MIT Press, London, U. K, 1999.

Digital Library

[19]

{19} P. Wolper and Z. Manna. Synthesis of communicating processes from temporal logic specifications. In Proceedings of the 1981 Workshop on Logics of Programs, pages 253-281. Springer Verlag, New York, 1982.

Digital Library

[20]

{20} W. M. Wonham. Design Software: CTCT. Version 71 for MS-DOS in Windows 95/98/2000, developed by Systems Control Group, University of Toronto, updated 1st July 2003. http://www.control.utoronto.ca /people/ profs/wonham /wonham.html.

[21]

{21} W. M. Wonham. Notes on Control of Discrete-Event Systems ECE 1636F/1637S 1997-98. Systems Control Group, University of Toronto, updated 1st July 2003. http://www.control.utoronto.ca / DES.

[22]

{22} M. Wooldridge. The computational complexity of agent design problems. In Proceedings of The Fourth International Conference on MultiAgent Systems (IC- MAS2000), pages 341-348, Boston, MA, U.S.A, July 2000.

Digital Library

[23]

{23} M. Wooldridge and P. E. Dunne. Optimistic and disjunctive agent design problems. In Pre-Proceedings of The Seventh International Workshop on Agent Theories, Architectures and Languages, pages 1-14, Boston, MA, U.S.A, July 2000.

Digital Library

[24]

{24} M. Yokoo. Distributed Constraint Satisfaction: Foundations of Cooperation in Multi-Agent Systems. Springer Verlag, 2000. Springer Series on Agent Technology.

Digital Library

Cited By

Pham MSeow KSierra CCastelfranchi CDecker KSichman J(2009)On-line coordination among discrete-event agentsProceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems - Volume 210.5555/1558109.1558223(1223-1224)Online publication date: 10-May-2009
https://dl.acm.org/doi/10.5555/1558109.1558223
Pham MSeow K(2009)On-line CoordinationProceedings of the 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology - Volume 0210.1109/WI-IAT.2009.172(315-322)Online publication date: 15-Sep-2009
https://dl.acm.org/doi/10.1109/WI-IAT.2009.172
Lass RSultanik ERegli W(2008)Dynamic distributed constraint reasoningProceedings of the 23rd national conference on Artificial intelligence - Volume 310.5555/1620270.1620308(1466-1469)Online publication date: 13-Jul-2008
https://dl.acm.org/doi/10.5555/1620270.1620308

Index Terms

Multiagent Planning as Control Synthesis
1. Computing methodologies
  1. Artificial intelligence

Recommendations

Continual planning and acting in dynamic multiagent environments

In order to behave intelligently, artificial agents must be able to deliberatively plan their future actions. Unfortunately, realistic agent environments are usually highly dynamic and only partially observable, which makes planning computationally ...
Multiagent Reinforcement Social Learning toward Coordination in Cooperative Multiagent Systems

Most previous works on coordination in cooperative multiagent systems study the problem of how two (or more) players can coordinate on Pareto-optimal Nash equilibrium(s) through fixed and repeated interactions in the context of cooperative games. ...
Multiagent planning through plan repair
AAMAS '05: Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems

We present a novel approach to multiagent planning for self-interested agents. The main idea behind our approach is that multiagent planning systems should be built upon (single-agent) plan repair systems. In our system agents can exchange goals and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

AAMAS '04: Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems - Volume 2

July 2004

464 pages

ISBN:1581138644

Sponsors

SIGAI: ACM Special Interest Group on Artificial Intelligence

Publisher

IEEE Computer Society

United States

Publication History

Published: 19 July 2004

Check for updates

Author Tags

Qualifiers

Article

Conference

AAMAS04

Sponsor:

SIGAI

AAMAS04: The Third International Joint Conference on Autonomous Agents and Multi-Agent Systems 2004

July 19 - 23, 2004

New York, New York

Acceptance Rates

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
12
Total Downloads

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

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pham MSeow KSierra CCastelfranchi CDecker KSichman J(2009)On-line coordination among discrete-event agentsProceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems - Volume 210.5555/1558109.1558223(1223-1224)Online publication date: 10-May-2009
https://dl.acm.org/doi/10.5555/1558109.1558223
Pham MSeow K(2009)On-line CoordinationProceedings of the 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology - Volume 0210.1109/WI-IAT.2009.172(315-322)Online publication date: 15-Sep-2009
https://dl.acm.org/doi/10.1109/WI-IAT.2009.172
Lass RSultanik ERegli W(2008)Dynamic distributed constraint reasoningProceedings of the 23rd national conference on Artificial intelligence - Volume 310.5555/1620270.1620308(1466-1469)Online publication date: 13-Jul-2008
https://dl.acm.org/doi/10.5555/1620270.1620308

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.

Media

Figures

Other

Tables

View Table of Contents