Partially observable Markov decision processes (POMDPs) are a natural model for scenarios where one has to deal with incomplete knowledge and random events.
 Applications include, but are not limited to, robotics and motion planning.
 However, many relevant properties of POMDPs are either undecidable or very expensive to compute in terms of both runtime and memory consumption.
 In our work, we develop a game-based abstraction method that is able to deliver safe bounds and tight
  approximations for important sub-classes of such properties.
 We discuss the theoretical implications and showcase the applicability of our results on a broad spectrum of benchmarks.
 We developed a game-based abstraction technique to synthesize strategies for a class of POMDPs. This class encompasses typical grid-based motion planning problems under restricted observability of the environment. For these scenarios, we efficiently compute strategies that allow the agent to maneuver the grid in order to reach a given goal state while at the same time avoiding collisions with faster moving obstacles. Experiments show that our approach can handle state spaces up to three orders of magnitude larger than general-purpose state-of-the-art POMDP solvers in less time, while at the same time using fewer states to represent the same grid sizes.
This paper provides a game-based abstraction scheme to compute provably sound policies for POMDPs.
{"src": "scitldr-AIC_train", "paper_id": "rJeKVt-iaV"}