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. As a running example, we use planning problems where an agent moves inside an environment with randomly moving obstacles and restricted observability. 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. Furthermore, this method gives guarantees on safety constraints, which is not supported by the majority of the existing solvers.
Introduction
In robot navigation, agents often operate under "partial observability"—they know their own location but can only perceive obstacles within a limited range. Mathematically, these scenarios are modeled as Partially Observable Markov Decision Processes (POMDPs). Solving POMDPs is notoriously difficult because traditional methods require tracking a "belief state" (a probability distribution over all possible world configurations), leading to an infinite or exponentially large state space. Standard solvers often fail on even small $6 \times 6$ grids. This research introduces a framework to synthesize "safe" strategies—guaranteed to reach a goal while avoiding collisions—without the computational overhead of full belief-state tracking.
Methodology: Game-Based Abstraction (GBAR)
The core contribution is an abstraction-refinement framework that transforms complex POMDPs into solvable probabilistic two-player games (PGs). This approach exploits the structural property that agents in navigation tasks usually know their own position, localizing uncertainty to the environment.
Abstraction to Probabilistic Games
Instead of tracking beliefs, the method groups world states that produce identical observations into a single "block." This is modeled as a Probabilistic Two-Player Game:
- Player 1 (The Agent): Selects the next move.
- Player 2 (The Adversary): Represents environmental uncertainty. Since the agent does not know the exact concrete state within a block, the adversary is allowed to "pick" the worst-case concrete state to resolve the move.
Soundness and Refinement
Because the uncertainty is treated adversarially, any safety probability calculated in this game serves as a guaranteed lower bound for the actual POMDP. If the initial abstraction is too coarse (causing the safety probability to drop below a required threshold), the framework refines the model by incorporating observation history. For example, remembering an obstacle's position from one step ago prevents the adversary from making that obstacle "teleport" in the next step, thereby tightening the safety bounds.
Experimental Results
The framework was tested against a suite of benchmark scenarios (SC1–SC5) involving various grid sizes and obstacle configurations.
- Massive Scalability: The framework successfully solved $50 \times 50$ grid worlds, resulting in PGs with over 1.3 million states. In contrast, the state-of-the-art
PRISM-pomdpsolver failed to handle a $6 \times 6$ grid. - Performance: For smaller models where comparison was possible, the abstraction method was often three orders of magnitude faster than traditional point-based POMDP solvers.
- Formal Guarantees: Unlike most heuristic solvers, this method provides explicit safety thresholds (e.g., "this path is 98% safe"). In complex "blind spot" scenarios, history-based refinement improved safety probabilities from ~40% to over 88%.
Conclusion
By treating partial observability as an adversarial game rather than a probabilistic inference problem, this framework bypasses the state-explosion problem inherent in belief-state tracking. While the method is an under-approximation (it may fail to find a strategy even if one exists), its scalability and formal safety guarantees represent a significant advancement for autonomous planning in uncertain environments. Future work includes extending the framework to multi-agent systems and non-deterministic obstacle behavior.
Summary updated