Approximating perfect recall when model checking strategic abilities: theory and applications
File(s)sminton,+12539-Article+(PDF)-30032-1-11-20220314.pdf (868.34 KB)
Published version
Author(s)
Belardinelli, Francesco
Lomuscio, Alessio
Malvone, Vadim
Yu, Emily
Type
Journal Article
Abstract
The model checking problem for multi-agent systems against specifications in the alternating-time temporal logic ATL, hence ATL∗, under perfect recall and imperfect information is known to be undecidable. To tackle this problem, in this paper we investigate a notion of bounded recall under incomplete information. We present a novel three-valued semantics for ATL∗ in this setting and analyse the corresponding model checking problem. We show that the three-valued semantics here introduced is an approximation of the classic two-valued semantics, then give a sound, albeit partial, algorithm for model checking two-valued perfect recall via its approximation as three-valued bounded recall. Finally, we extend MCMAS, an open-source model checker for ATL and other agent specifications, to incorporate bounded recall; we illustrate its use and present experimental results.
Date Issued
2022
Date Acceptance
2022-03-01
Citation
Journal of Artificial Intelligence Research, 2022, 73, pp.897-932
ISSN
1076-9757
Publisher
AI Access Foundation
Start Page
897
End Page
932
Journal / Book Title
Journal of Artificial Intelligence Research
Volume
73
Copyright Statement
© 2022 AI Access Foundation. All rights reserved. Belardinelli, Francesco, et al. "Approximating perfect recall when model checking strategic abilities: Theory and applications." Journal of Artificial Intelligence Research 73 (2022): 897-932.
Identifier
https://www.webofscience.com/api/gateway?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000773339700001&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=a2bf6146997ec60c407a63945d4e92bb
Subjects
ABSTRACTION-REFINEMENT
Computer Science
Computer Science, Artificial Intelligence
Science & Technology
Technology
Publication Status
Published
Date Publish Online
2022-03-17