A Unified Framework for POMDPs with Constraints and Durative Actions

  • Duoaa Magdi Khalifa

Student thesis: Master's Thesis


Partially Observable Markov Decision Process (POMDP) is a fundamental model for probabilistic planning in stochastic domains. More recently, constrained POMDP and chance-constrained POMDP extend the model allowing constraints to be specified on some aspects of the policy in addition to the objective function. Despite their expressive power, these models assume all actions take a fixed duration, which poses a limitation in modeling real-world planning problems. In this work, we propose a unified model for durative POMDP and its constrained extensions. We then formulate the model as an integer linear program (ILP) and solve it using one of the existing solvers. Then we take a step further and propose a heuristic-based search approach that can efficiently prune the space state by the means of solving successive partial ILP programs. Finally, we evaluate our results and show that our approach is empirically superior to the state-of-the-art fixed-horizon chance-constrained POMDP solver.
Date of AwardDec 2020
Original languageAmerican English


  • Planning
  • Durative actions
  • Constraints
  • Heuristic-based algorithm.

Cite this