On the Encoding and Solving of Partial Information Games - Sorbonne Université Access content directly
Conference Papers Year : 2021

On the Encoding and Solving of Partial Information Games

Abstract

In this paper we address partial information games restricted to memoryless strategies. Our contribution is threefold. First, we prove that for partial information games, deciding the existence of memoryless strategies is NP-complete, even for games with only reachability objectives. The second contribution of this paper is a SAT/SMT-based encoding of a partial information game altogether with the correctness proof of this encoding. Finally, we apply our methodology to automatically synthesize strategies for oblivious mobile robots. We prove that synthesizing memoryless strategies is equivalent to providing a distributed protocol for the robots. Interestingly, our work is the first that combines two-player games theory and SMT-solvers in the context of mobile robots with promising results and therefore it is highly valuable for distributed computing theory where a broad class of open problems are still to be investigated.
No file

Dates and versions

hal-02979574 , version 1 (27-10-2020)

Identifiers

Cite

Yackolley Amoussou-Guenou, Souheib Baarir, Maria Potop-Butucaru, Nathalie Sznajder, Léo Tible, et al.. On the Encoding and Solving of Partial Information Games. 8th International Conference on Networked Systems - NETYS 2020, Jun 2020, Marrakech, Morocco. pp.60-76, ⟨10.1007/978-3-030-67087-0_5⟩. ⟨hal-02979574⟩
77 View
0 Download

Altmetric

Share

Gmail Facebook X LinkedIn More