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 many applications. In this work, we study POMDPs with safe-reachability objectives, which require that with a probability above some threshold, a goal state is eventually reached while keeping the probability of visiting unsafe states below some threshold. This POMDP formulation is different from the traditional POMDP models with optimality objectives and we show that in some cases, POMDPs with safe-reachability objectives can provide a better guarantee of both safety and reachability than the existing POMDP models through an example. A key algorithmic problem for POMDPs is policy synthesis, which requires reasoning over a vast space of beliefs (probability distributions). To address this challenge, we introduce the notion of a goal-constrained belief space, which only contains beliefs reachable from the initial belief under desired executions that can achieve the given safe-reachability objective. Our method compactly represents this space over a bounded horizon using symbolic constraints, and employs an incremental Satisfiability Modulo Theories (SMT) solver to efficiently search for a valid policy over it. We evaluate our method using a case study involving a partially observable robotic domain with uncertain obstacles. The results show that our method can synthesize policies over large belief spaces with a small number of SMT solver calls by focusing on the goal-constrained belief space.

📄 PDF Abstract BibTeX arXiv:1801.09780

Code (0)

등록된 구현이 없습니다.

Tasks

valid

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

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 th…

Verifiable RNN-Based Policies for POMDPs Under Temporal Logic Constraints

2020-02-13 · Steven Carr, Nils Jansen, Ufuk Topcu

Recurrent neural networks (RNNs) have emerged as an effective representation of control policies in sequential decision-making problems. However, a major drawback in the application of RNN-based policies is the difficult…

Decision Making Diagnostic Sequential Decision Making

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…

Safety-Constrained Reinforcement Learning with Post-Training Reachability Verification for Robot Navigation

2026-05-13 · Qisong He, Xinmiao Huang, Jinwei Hu, Zhuoyun Li 외 arxiv

Safe navigation for mobile robots demands policies that remain reliable under the high-consequence perception uncertainty of cluttered environments. Yet most existing safe reinforcement learning (RL) methods assess safet…

Reinforcement Learning Robot Navigation