Algorithmic synthesis of knowledge-based strategies in pursuit-evasion games with imperfect information

Sammanfattning

We study pursuit-evasion games played on finite grids where the pursuers have “corridor vision”. We propose a formal translation from such games to the Multi-agent Game with Imperfect Information Against Nature (MAGIIAN) framework. Previous research has not yielded any second-order knowledge-based strategies in pursuit-evasion games played on grid that performs better than all first-order ones, which suggests that MAGIIANs representing such games would be stable after the first MKBSC iteration. After applying the MKBSC to games obtained by our translation, we found no games that were stable after the first iteration. However, optimal and surely winning strategies using first-order knowledge exist in all games studied. Additionally, MAGIIANs representing pursuit-evasion games with synchronous movement seem to diverge, while turn-based games appear to stabilise.