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.
Solving partially observable stochastic shortest-path games
01.01.2021
Tomášek P, Horák K, Aradhye A, Bošanský B, Chatterjee K. Solving partially observable stochastic shortest-path games. In: 30th International Joint Conference on Artificial Intelligence . International Joint Conferences on Artificial Intelligence; 2021:4182-4189. doi: 10.24963/ijcai.2021/575
Aufsatz (Konferenz)
Elektronische Ressource
Englisch
DDC: | 629 |
Research on Dynamic Stochastic Shortest Path Problem
ASCE | 2010
|Some recent results on the control of partially observable stochastic systems
Springer Verlag | 1982
|Solving Fuzzy Shortest Path Problem with Decision Maker’s Perspective
Springer Verlag | 2021
|Efficient Algorithms for Solving the Shortest Covering Path Problem
Online Contents | 1994
|