Article

Finding uniform strategies for multi-agent systems

Authors:

Jan Calta,

Dmitry Shkatov,

Holger SchlingloffAuthors Info & Claims

CLIMA'10: Proceedings of the 11th international conference on Computational logic in multi-agent systems

Pages 135 - 152

Published: 16 August 2010 Publication History

Abstract

We present an algorithm for finding uniform strategies in multi-agent systems with incomplete information. The algorithm finds all maximal uniform strategies for agents with incomplete information for enforcing a property expressible in the language of Alternating-time Temporal Logic ATL. The main application of the algorithm is automated program synthesis for systems that can be modeled as multi-agent systems with incomplete information (e.g., decentralized distributed systems).

References

[1]

SAFER - Seismic eArly warning For EuRope (2010), http://www.saferproject.net

Google Scholar

[2]

Alur, R., Henzinger, T.A., Kupferman, O.: Alternating-time temporal logic. J. ACM 49(5), 672-713 (2002).

Digital Library

Google Scholar

[3]

Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16(9), 575-577 (1973).

Digital Library

Google Scholar

[4]

Goranko, V., Shkatov, D.: Tableau-based decision procedures for logics of strategic ability in multi-agent systems. ACM Transactions on Computational Logic (2009).

Digital Library

Google Scholar

[5]

Jamroga, W., Ågotnes, T.: Constructive knowledge: what agents can achieve under imperfect information. Journal of Applied Non-classical Logics 17(4), 423-475 (2007).

Crossref

Google Scholar

[6]

Jamroga, W., Ågotnes, T.: Modular interpreted systems. In: Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 2007 (2007).

Digital Library

Google Scholar

[7]

Jamroga, W., Dix, J.: Model checking abilities under incomplete information is indeed delta2-complete. In: Proceedings of the 4th European Workshop on Multi-Agent Systems, EUMAS 2006 (2006).

Google Scholar

[8]

Jamroga, W.: Some remarks on alternating temporal epistemic logic. In: Dunin-Keplicz, B., Verbrugge, R. (eds.) Formal Approaches to Multiagent Systems 2003, pp. 133-140 (2003).

Google Scholar

[9]

Moon, J., Moser, L.: On cliques in graphs. Israel Journal of Mathematics 3(1), 23-28 (1965).

Crossref

Google Scholar

[10]

Schobbens, P.-Y.: Alternating-time logic with imperfect recall. Electronic Notes in Theoretical Computer Science 85(2), 82-93 (2004).

Crossref

Google Scholar

[11]

Tomita, E., Tanaka, A., Takahashi, H.: The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical Computer Science 363(1), 28-42 (2006).

Digital Library

Google Scholar

[12]

van der Hoek, W., Wooldridge, M.: Cooperation, knowledge, and time: Alternating-time temporal epistemic logic and its applications. Studia Logica (2003).

Google Scholar

Cited By

View all

Kurpiewski DKnapik MJamroga WElkind EVeloso MAgmon NTaylor M(2019)On Domination and Control in Strategic AbilityProceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3306127.3331693(197-205)Online publication date: 8-May-2019
https://dl.acm.org/doi/10.5555/3306127.3331693
Huang XMeyden R(2018)An Epistemic Strategy LogicACM Transactions on Computational Logic10.1145/323376919:4(1-45)Online publication date: 30-Nov-2018
https://dl.acm.org/doi/10.1145/3233769
Calta JShkatov D(2011)Synthesizing strategies for homogenous multi-agent systems with incomplete informationProceedings of the 12th international conference on Computational logic in multi-agent systems10.5555/2044543.2044556(122-138)Online publication date: 17-Jul-2011
https://dl.acm.org/doi/10.5555/2044543.2044556

Recommendations

Rational Teams: Logical Aspects of Multi-Agent Systems
Multiagent Systems (FAMAS'03)

This paper describes a possible extension to the logical framework KARO to make it able to handle multiple agents. The KARO framework, which was initially developed by van der Hoek, van Linder and Meyer, makes use of epistemic and dynamic logics to ...
Rational Teams: Logical Aspects of Multi-Agent Systems
Multiagent Systems (FAMAS'03)

This paper describes a possible extension to the logical framework KARO to make it able to handle multiple agents. The KARO framework, which was initially developed by van der Hoek, van Linder and Meyer, makes use of epistemic and dynamic logics to ...
Multi-agent systems
Encyclopedia of Computer Science

Multi-agent systems are computational systems in which several artificial "agents", which are programs, interact or work together over a communications network to perform some set of tasks jointly or to satisfy some set of goals. These systems may ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

CLIMA'10: Proceedings of the 11th international conference on Computational logic in multi-agent systems

August 2010

256 pages

ISBN:3642149766

Editors:
Jürgen Dix
Clausthal University of Technology, Clausthal-Zellerfeld, Germany
,
João Leite
CENTRIA, Universidade Nova de Lisboa, Caparica, Portugal
,
Guido Governatori
NICTA, St Lucia, QLD, Australia
,
Wojtek Jamroga
University of Luxembourg, Luxembourg, Luxembourg

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 16 August 2010

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kurpiewski DKnapik MJamroga WElkind EVeloso MAgmon NTaylor M(2019)On Domination and Control in Strategic AbilityProceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3306127.3331693(197-205)Online publication date: 8-May-2019
https://dl.acm.org/doi/10.5555/3306127.3331693
Huang XMeyden R(2018)An Epistemic Strategy LogicACM Transactions on Computational Logic10.1145/323376919:4(1-45)Online publication date: 30-Nov-2018
https://dl.acm.org/doi/10.1145/3233769
Calta JShkatov D(2011)Synthesizing strategies for homogenous multi-agent systems with incomplete informationProceedings of the 12th international conference on Computational logic in multi-agent systems10.5555/2044543.2044556(122-138)Online publication date: 17-Jul-2011
https://dl.acm.org/doi/10.5555/2044543.2044556

Abstract

References

Cited By

Recommendations

Rational Teams: Logical Aspects of Multi-Agent Systems

Rational Teams: Logical Aspects of Multi-Agent Systems

Multi-agent systems

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations