A Symbolic SAT-based Algorithm for Almost-sure Reachability with Small Strategies in POMDPs

2015-11-26 · Krishnendu Chatterjee, Martin Chmelik, Jessica Davies

POMDPs are standard models for probabilistic planning problems, where an agent interacts with an uncertain environment. We study the problem of almost-sure reachability, where given a set of target states, the question is to decide whether there is a policy to ensure that the target set is reached with probability 1 (almost-surely). While in general the problem is EXPTIME-complete, in many practical cases policies with a small amount of memory suffice. Moreover, the existing solution to the problem is explicit, which first requires to construct explicitly an exponential reduction to a belief-support MDP. In this work, we first study the existence of observation-stationary strategies, which is NP-complete, and then small-memory strategies. We present a symbolic algorithm by an efficient encoding to SAT and using a SAT solver for the problem. We report experimental results demonstrating the scalability of our symbolic (SAT-based) approach.

📄 PDF Abstract BibTeX arXiv:1511.08456

Code (0)

등록된 구현이 없습니다.

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…

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

Symbolic Control for Stochastic Systems via Finite Parity Games

2021-01-04 · Rupak Majumdar, Kaushik Mallik, Anne-Kathrin Schmuck, Sadegh Soudjani

We consider the problem of computing the maximal probability of satisfying an omega-regular specification for stochastic nonlinear systems evolving in discrete time. The problem reduces, after automata-theoretic construc…

Goal Space Abstraction in Hierarchical Reinforcement Learning via Set-Based Reachability Analysis

2023-09-14 · Mehdi Zadem, Sergio Mover, Sao Mai Nguyen

Open-ended learning benefits immensely from the use of symbolic methods for goal representation as they offer ways to structure knowledge for efficient and transferable learning. However, the existing Hierarchical Reinfo…

Hierarchical Reinforcement Learning reinforcement-learning

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…