Motion Planning under Partial Observability using Game-Based Abstraction

Leonore Winterer, Sebastian Junges, Ralf Wimmer, Nils Jansen, Ufuk Topcu, Joost-Pieter Katoen, Bernd Becker

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.

The proposed abstraction refinement framework for POMDPs.

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.

A fragment of the game-based abstraction showing state transitions and branching.

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

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.
BibTeX
@inproceedings{winterer2017motion,
  author = {Leonore Winterer and Sebastian Junges and Ralf Wimmer and Nils Jansen and Ufuk Topcu and Joost-Pieter Katoen and Bernd Becker},
  title = {{Motion Planning under Partial Observability using Game-Based Abstraction}},
  booktitle = {CDC},
  year = {2017},
  doi = {10.1109/cdc.2017.8263971},
}
Figure