Solving Partially Observable Stochastic Shortest-Path Games

Tomášek, Petr; Horák, Karel; Aradhye, Aditya; Bošanský, Branislav; Chatterjee, Krishnendu

doi:10.24963/ijcai.2021/575

Solving Partially Observable Stochastic Shortest-Path Games

Petr Tomášek, Karel Horák, Aditya Aradhye, Branislav Bošanský, Krishnendu Chatterjee

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 4182-4189.

https://doi.org/10.24963/ijcai.2021/575

Keywords

Uncertainty in AI: Sequential Decision Making
Agent-based and Multi-agent Systems: Noncooperative Games
Planning and Scheduling: Planning with Incomplete Information

Abstract

We study the two-player zero-sum extension of the partially observable stochastic shortest-path problem where one agent has only partial information about the environment.

We formulate this problem as a partially observable stochastic game (POSG): given a set of target states and negative rewards for each transition, the player with imperfect information maximizes the expected undiscounted total reward until a target state is reached. The second player with the perfect information aims for the opposite.

We base our formalism on POSGs with one-sided observability (OS-POSGs) and give the following contributions:

(1) we introduce a novel heuristic search value iteration algorithm that iteratively solves depth-limited variants of the game,

(2) we derive the bound on the depth guaranteeing an arbitrary precision, (3) we propose a novel upper-bound estimation that allows early terminations, and

(4) we experimentally evaluate the algorithm on a pursuit-evasion game.

Petr Tomášek, Karel Horák, Aditya Aradhye, Branislav Bošanský, and Krishnendu Chatterjee. 2021. Solving Partially Observable Stochastic Shortest-Path Games. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 4182–4189. https://doi.org/10.24963/ijcai.2021/575

@inproceedings{ijcai2021p575,
  title     = {Solving Partially Observable Stochastic Shortest-Path Games},
  author    = {Tomášek, Petr and Horák, Karel and Aradhye, Aditya and Bošanský, Branislav and Chatterjee, Krishnendu},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {4182--4189},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/575},
  url       = {https://doi.org/10.24963/ijcai.2021/575},
}

TY  - CPAPER
TI  - Solving Partially Observable Stochastic Shortest-Path Games
AU  - Tomášek, Petr
AU  - Horák, Karel
AU  - Aradhye, Aditya
AU  - Bošanský, Branislav
AU  - Chatterjee, Krishnendu
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 4182
EP  - 4189
DO  - 10.24963/ijcai.2021/575
UR  - https://doi.org/10.24963/ijcai.2021/575
ER  -