An Abstraction-Based Method for Verifying Strategic Properties in Multi-Agent Systems with Imperfect Information
Abstract
We investigate the verification of Multi-agent Systems against strategic properties expressed in Alternating-time Temporal Logic under the assumptions of imperfect information and perfect recall. To this end, we develop a three-valued semantics for concurrent game structures upon which we define an abstraction method. We prove that concurrent game structures with imperfect information admit perfect information abstractions that preserve three-valued satisfaction. Further, we present a refinement procedure to deal with cases where the value of a specification is undefined. We illustrate the overall procedure in a variant of the Train Gate Controller scenario under imperfect information and perfect recall.
Cite
Text
Belardinelli et al. "An Abstraction-Based Method for Verifying Strategic Properties in Multi-Agent Systems with Imperfect Information." AAAI Conference on Artificial Intelligence, 2019. doi:10.1609/AAAI.V33I01.33016030Markdown
[Belardinelli et al. "An Abstraction-Based Method for Verifying Strategic Properties in Multi-Agent Systems with Imperfect Information." AAAI Conference on Artificial Intelligence, 2019.](https://mlanthology.org/aaai/2019/belardinelli2019aaai-abstraction/) doi:10.1609/AAAI.V33I01.33016030BibTeX
@inproceedings{belardinelli2019aaai-abstraction,
title = {{An Abstraction-Based Method for Verifying Strategic Properties in Multi-Agent Systems with Imperfect Information}},
author = {Belardinelli, Francesco and Lomuscio, Alessio and Malvone, Vadim},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2019},
pages = {6030-6037},
doi = {10.1609/AAAI.V33I01.33016030},
url = {https://mlanthology.org/aaai/2019/belardinelli2019aaai-abstraction/}
}