Sensor Synthesis for POMDPs with Reachability Objectives

2017-09-29 · Krishnendu Chatterjee, Martin Chmelik, Ufuk Topcu

Partially observable Markov decision processes (POMDPs) are widely used in probabilistic planning problems in which an agent interacts with an environment using noisy and imprecise sensors. We study a setting in which the sensors are only partially defined and the goal is to synthesize "weakest" additional sensors, such that in the resulting POMDP, there is a small-memory policy for the agent that almost-surely (with probability~1) satisfies a reachability objective. We show that the problem is NP-complete, and present a symbolic algorithm by encoding the problem into SAT instances. We illustrate trade-offs between the amount of memory of the policy and the number of additional sensors on a simple example. We have implemented our approach and consider three classical POMDP examples from the literature, and show that in all the examples the number of sensors can be significantly decreased (as compared to the existing solutions in the literature) without increasing the complexity of the policies.

📄 PDF Abstract BibTeX arXiv:1710.00675

Code (0)

등록된 구현이 없습니다.

Bounded Policy Synthesis for POMDPs with Safe-Reachability Objectives

2018-01-29 · Yue Wang, Swarat Chaudhuri, Lydia E. Kavraki

Planning robust executions under uncertainty is a fundamental challenge for building autonomous robots. Partially Observable Markov Decision Processes (POMDPs) provide a standard framework for modeling uncertainty in man…

valid

Computing the Reachability Value of Posterior-Deterministic POMDPs

2026-02-07 · Nathanaël Fijalkow, Arka Ghosh, Roman Kniazev, Guillermo A. Pérez 외 arxiv

Partially observable Markov decision processes (POMDPs) are a fundamental model for sequential decision-making under uncertainty. However, many verification and synthesis problems for POMDPs are undecidable or intractabl…

Enforcing Almost-Sure Reachability in POMDPs

2020-06-30 · Sebastian Junges, Nils Jansen, Sanjit A. Seshia

Partially-Observable Markov Decision Processes (POMDPs) are a well-known stochastic model for sequential decision making under limited information. We consider the EXPTIME-hard problem of synthesising policies that almos…

Decision Making reinforcement-learning Reinforcement Learning (RL)Safe Exploration+1

Sound Heuristic Search Value Iteration for Undiscounted POMDPs with Reachability Objectives

2024-06-05 · Qi Heng Ho, Martin S. Feather, Federico Rossi, Zachary N. Sunberg 외

Partially Observable Markov Decision Processes (POMDPs) are powerful models for sequential decision making under transition and observation uncertainties. This paper studies the challenging yet important problem in POMDP…

Decision Making Efficient Exploration Heuristic Search Sequential Decision Making

Optimal Cost Almost-sure Reachability in POMDPs

2014-11-14 · Krishnendu Chatterjee, Martin Chmelík, Raghav Gupta, Ayush Kanodia

We consider partially observable Markov decision processes (POMDPs) with a set of target states and every transition is associated with an integer cost. The optimization objective we study asks to minimize the expected t…