Abstract
We study synthesis problems with constraints in partially observable Markov decision processes (POMDPs), where the objective is to compute a strategy for an agent that is guaranteed to satisfy certain safety and performance specifications. Verification and strategy synthesis for POMDPs are, however, computationally intractable in general. We alleviate this difficulty by focusing on planning applications and exploiting typical structural properties of such scenarios; for instance, we assume that the agent has the ability to observe its own position inside an environment. We propose an abstraction refinement framework which turns such a POMDP model into a (fully observable) probabilistic two-player game (PG). For the obtained PGs, efficient verification and synthesis tools allow to determine strategies with optimal safety and performance measures, which approximate optimal schedulers on the POMDP. If the approximation is too coarse to satisfy the given specifications, an refinement scheme improves the computed strategies. We demonstrate that the proposed method advances the state of the art by solving problems several orders-of-magnitude larger than those that can be handled by existing POMDP solvers.
Introduction
In robotics and autonomous systems, agents rarely have perfect information. They operate in Partially Observable Markov Decision Processes (POMDPs), where sensors are noisy or have limited range. For example, a robot might know its own position but only see a moving obstacle if it's within a specific radius.
The standard approach to solving POMDPs involves tracking a "belief state"—a probability distribution over all possible configurations of the world. However, the belief space is often infinite or astronomically large, making exact verification and strategy synthesis computationally intractable. Existing solvers often fail on even modest $10 \times 10$ grid worlds. This paper introduces a scalable framework for finding safe strategies by transforming POMDPs into fully observable, probabilistic two-player games.
The GBAR Framework
The authors propose a Game-Based Abstraction (GBAR) approach. Instead of calculating complex probability distributions, they simplify the model through a multi-step pipeline that moves from problem description to an optimal strategy.
Abstraction to Games
The core idea is to group all states that produce the same observation into a single "abstract state." This turns the POMDP into a Probabilistic Two-Player Game (PG):
- Player 1 (The Agent): Chooses an action (e.g., "move north").
- Player 2 (The Environment/Adversary): Resolves the uncertainty. If the agent doesn't know exactly where an obstacle is, Player 2 picks the "worst-case" concrete location for that obstacle within the current observation block.
Because Player 2 is adversarial, any safety guarantee found in this game is a "lower bound." If a strategy is $95\%$ safe in the game, it is guaranteed to be at least $95\%$ safe in the real POMDP.
Refinement and Scalability
If the initial abstraction is too pessimistic, the framework uses history-based refinement. By remembering where an obstacle was last seen, the model restricts where Player 2 can place it in the next step, tightening the safety bounds. This process expands the game tree to include relevant historical context without exploding the state space unnecessarily.
By "lumping" states together, the state space of the game remains significantly smaller than the underlying POMDP, allowing the use of efficient model-checking tools like PRISM-games.
Experimental Evaluation
The method was evaluated on several navigation scenarios (SC1–SC5) involving varying grid sizes and moving obstacles. Key results include:
- Massive Speedup: While standard POMDP solvers timed out on a $6 \times 6$ grid, the abstraction method solved $50 \times 50$ grids (with over 1.3 million states) in minutes.
- Scalability: The approach handled problems roughly three orders of magnitude larger than previous state-of-the-art methods.
- High-Quality Strategies: Testing the game-derived strategy back on the original POMDP showed that safety probabilities were often near-optimal, frequently reaching $99\%+$ safety in complex environments.
Conclusion
By treating sensor uncertainty as an adversarial opponent, this framework provides a robust and scalable solution for motion planning under partial observability. While the method is an under-approximation and may require refinement to find a valid strategy, its ability to handle massive state spaces marks a significant advancement in the verification of autonomous systems.
Summary updated