TY - GEN
T1 - Approximating perfect recall when model checking strategic abilities
AU - Belardinelli, Francesco
AU - Lomuscio, Alessio
AU - Malvone, Vadim
N1 - Publisher Copyright:
© 2018, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
PY - 2018/1/1
Y1 - 2018/1/1
N2 - We investigate the notion of bounded recall in the context of model checking ATL* and ATL specifications in multi-agent systems with imperfect information. We present a novel three-valued semantics for ATL*, respectively ATL, under bounded recall and imperfect information, and study the corresponding model checking problems. Most importantly, we show that the three-valued semantics constitutes an approximation with respect to the traditional two-valued semantics. In the light of this we construct a sound, albeit partial, algorithm for model checking two-valued perfect recall via its approximation as three-valued bounded recall.
AB - We investigate the notion of bounded recall in the context of model checking ATL* and ATL specifications in multi-agent systems with imperfect information. We present a novel three-valued semantics for ATL*, respectively ATL, under bounded recall and imperfect information, and study the corresponding model checking problems. Most importantly, we show that the three-valued semantics constitutes an approximation with respect to the traditional two-valued semantics. In the light of this we construct a sound, albeit partial, algorithm for model checking two-valued perfect recall via its approximation as three-valued bounded recall.
UR - https://www.scopus.com/pages/publications/85077065046
M3 - Conference contribution
AN - SCOPUS:85077065046
T3 - Principles of Knowledge Representation and Reasoning: Proceedings of the 16th International Conference, KR 2018
SP - 435
EP - 444
BT - Principles of Knowledge Representation and Reasoning
A2 - Thielscher, Michael
A2 - Toni, Francesca
A2 - Wolter, Frank
PB - AAAI Press
T2 - 16th International Conference on the Principles of Knowledge Representation and Reasoning, KR 2018
Y2 - 30 October 2018 through 2 November 2018
ER -