Abstract
Partially Observable Stochastic Shortest-Path Games (POSSPGs) represent a challenging class of problems where an agent must reach a goal state at minimum cost while navigating an environment with limited information and facing a perfectly informed adversary. Traditional methods often rely on discount factors to ensure convergence, which can distort the true shortest-path objective. This paper introduces the first algorithm specifically designed for POSSPGs. By decomposing the infinite-horizon problem into a sequence of depth-limited "cutoff" games and employing a novel auxiliary upper bound, the proposed method achieves significant computational speedups—up to 37x—over standard discounted-reward approximations.
Introduction
In real-world applications such as robotic warehouse navigation or security patrolling, agents often aim to reach a target state in the shortest possible time. These scenarios are modeled as Stochastic Shortest Path (SSP) problems. When an adversary is introduced, the problem becomes an SSP Game, and when the agent's information is limited, it evolves into a Partially Observable (PO) SSP Game.
Solving POSSPGs is computationally intensive. Most existing algorithms for partially observable games utilize a discount factor ($\gamma < 1$) to guarantee mathematical convergence. However, in shortest-path problems, every step carries an equal cost until the goal is reached, making the undiscounted total cost the primary metric of interest. Without a discount factor, traditional heuristic search methods often fail to provide convergence guarantees or tight solution bounds.
Methodology
The authors focus on games with one-sided observability: the agent (Player 1) has partial information, while the adversary (Player 2) has perfect information. This assumption models a robust planning scenario against a worst-case opponent. The core of the solution is Algorithm 2 (HSVI for POSSPGs), which integrates three key innovations:
- k-cutoff Games: The infinite-horizon game is approximated by a version that terminates after $k$ steps. If the goal is not reached, a known uniform strategy is applied.
- Finite-Horizon HSVI (FH-HSVI): The researchers adapted the Heuristic Search Value Iteration (HSVI) algorithm to function without discount factors by partitioning the value function based on the remaining steps in the $k$-cutoff game.
- Auxiliary Upper Bound ($V^+$): To prevent the need for excessively large $k$ values, a global upper bound is maintained. This bound is derived from a version of the game where the agent is granted perfect information, allowing for early termination when the solution quality is sufficient.
Experimental Evaluation
The algorithm was evaluated using a Pursuit-Evasion Game on various grid sizes. In this setup, a team of two pursuers (Player 1) attempts to capture an evader (Player 2). The pursuers have partial information (knowing only their own locations), while the evader has full knowledge of all positions.
Key Results
The proposed approach was compared against the state-of-the-art HSVI for discounted games, using discount factors close to 1 (e.g., $\gamma = 0.999$) to approximate the undiscounted setting.
As shown in the table above, the new algorithm demonstrates superior scalability and speed. On a $3 \times 5$ grid, it reached a solution in 607 seconds, whereas the traditional discounted approach required 15,259 seconds—a 25x improvement. On larger instances, such as $3 \times 6$ grids, the traditional method failed to converge to a meaningful bound within 10 hours, while the new algorithm maintained a much tighter gap.
Conclusion
By bypassing the need for discount factors and utilizing finite-horizon approximations with auxiliary bounds, this research provides a robust framework for solving POSSPGs. The results indicate that information asymmetry can be leveraged to avoid the "infinite regress" of beliefs typically found in partially observable games. Future work will explore extending this framework to two-sided partial observability and safety-critical objectives where the probability of reaching a goal safely is maximized.
Summary updated