---
title: "Solving Partially Observable Stochastic Shortest-Path Games"
authors:
  - "Petr Tomášek"
  - "Karel Horák"
  - "Aditya Aradhye"
  - "Branislav Bošanský"
  - "Krishnendu Chatterjee"
doi: "10.24963/ijcai.2021/575"
url: "https://ijcai.org/proceedings/2021/575"
pdf: "https://ijcai.org/proceedings/2021/0575.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "4182-4189"
track: "Main Track"
keywords:
  - "Uncertainty in AI: Sequential Decision Making"
  - "Agent-based and Multi-agent Systems: Noncooperative Games"
  - "Planning and Scheduling: Planning with Incomplete Information"
---

# Solving Partially Observable Stochastic Shortest-Path Games

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

*Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence*, pages 4182-4189. DOI: [10.24963/ijcai.2021/575](https://doi.org/10.24963/ijcai.2021/575)

## 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.