[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Model Checking Properties of Multi-agent Systems with Imperfect Information and Imperfect Recall

  • Conference paper
Intelligent Systems'2014

Part of the book series: Advances in Intelligent Systems and Computing ((AISC,volume 322))

Abstract

The problem of practical model checking Alternating-time Temporal Logic (ATL) formulae under imperfect information and imperfect recall is considered. This is done by synthesis and subsequent verification of strategies, until a good one is found. To reduce the complexity of the problem we define an equivalence relation on strategies. Then an algorithm for model checking a class of modal properties with a single coalitional modality is presented, which utilises the observation that there is no need to verify more than one strategy from an equivalence class. The experimental results of the approach are also discussed.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 143.50
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 179.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Ågotnes, T.: A note on syntactic characterization of incomplete information in ATEL. In: Procedings of the Workshop on Knowledge and Games, Liverpool, pp. 34–42 (2004)

    Google Scholar 

  2. Alur, R., Henzinger, T.A., Kupferman, O.: Alternating-time Temporal Logic. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), pp. 100–109. IEEE Computer Society Press (1997)

    Google Scholar 

  3. Alur, R., Henzinger, T.A., Kupferman, O.: Alternating-time Temporal Logic. Journal of the ACM 49, 672–713 (2002)

    Article  MathSciNet  Google Scholar 

  4. Bulling, N., Jamroga, W.: Comparing variants of strategic ability. Journal of Autonomous Agents and Multi-Agent Systems 28(3), 474–518 (2014)

    Article  Google Scholar 

  5. Jamroga, W.: Some remarks on alternating temporal epistemic logic. In: Dunin-Keplicz, B., Verbrugge, R. (eds.) Proceedings of Formal Approaches to Multi-Agent Systems (FAMAS 2003), pp. 133–140 (2003)

    Google Scholar 

  6. Jamroga, W., Dix, J.: Model checking ATL ir is indeed \(\Delta_2^P\)-complete. In: Proceedings of EUMAS 2006 (2006)

    Google Scholar 

  7. Jamroga, W., van der Hoek, W.: Agents that know how to play. Fundamenta Informaticae 63(2-3), 185–219 (2004)

    MATH  MathSciNet  Google Scholar 

  8. Jonker, G.: Feasible strategies in Alternating-time Temporal Epistemic Logic, master thesis, University of Utrecht (2003)

    Google Scholar 

  9. Lomuscio, A., Qu, H., Raimondi, F.: MCMAS: A model checker for the verification of multi-agent systems. In: Bouajjani, A., Maler, O. (eds.) CAV 2009. LNCS, vol. 5643, pp. 682–688. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Systems Research Institute, Polish Academy of Sciences, Warsaw, Poland

    Jerzy Pilecki

  2. Polish-Japanese Institute of Information Technology, Warsaw, Poland

    Marek A. Bednarczyk

  3. Institute of Computer Science, Polish Academy of Sciences, Warsaw, Poland

    Marek A. Bednarczyk

  4. Computer Science and Communications Research Unit, & Interdisciplinary Centre for Security, Reliability and Trust, University of Luxembourg, Luxembourg, Luxembourg

    Wojciech Jamroga

  5. Department of Informatics, Clausthal University of Technology, Clausthal-Zellerfeld, Germany

    Wojciech Jamroga

Authors
  1. Jerzy Pilecki
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marek A. Bednarczyk
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Wojciech Jamroga
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. School of Computing and Communications, Lancaster University, Lancaster, United Kingdom

    P. Angelov

  2. Institute of Biophysics and Biomedical Engineering, Bulgarian Academy of Sciences, Sofia, Bulgaria

    K.T. Atanassov

  3. Intelligent Systems Department, Bulgarian Academy of Sciences Inst. of Infor. & Communication Techn., Sofia, Bulgaria

    L. Doukovska

  4. Metalurgy, University of Chemical Technology and, Sofia, Bulgaria

    M. Hadjiski

  5. University of Library Studies and IT (ULSIT), Sofia, Bulgaria

    V. Jotsov

  6. Systems Research Institute, Polish Academy of Sciences, Warsaw, Poland

    J. Kacprzyk

  7. Knowledge Engineering and Discovery Research Institute, Auckland University of Technology, Auckland, New Zealand

    N. Kasabov

  8. Intelligent Systems Laboratory, Prof. Assen Zlatarov University Faculty of Technical Sciences, Bourgas, Bulgaria

    S. Sotirov

  9. Systems Research Institute, Polish Academy of Sciences, Warsaw, Poland

    E. Szmidt

  10. Systems Research Institute, Polish Academy of Sciences, Warsaw, Poland

    S. Zadrożny

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer International Publishing Switzerland

About this paper

Cite this paper

Pilecki, J., Bednarczyk, M.A., Jamroga, W. (2015). Model Checking Properties of Multi-agent Systems with Imperfect Information and Imperfect Recall. In: Angelov, P., et al. Intelligent Systems'2014. Advances in Intelligent Systems and Computing, vol 322. Springer, Cham. https://doi.org/10.1007/978-3-319-11313-5_37

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-11313-5_37

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-11312-8

  • Online ISBN: 978-3-319-11313-5

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics

Search

Navigation