Heuristic Search in Dual Space for Constrained Fixed-Horizon POMDPs with Durative Actions

Majid Khonji, Duoaa Khalifa

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Abstract

    The Partially Observable Markov Decision Process (POMDP) is widely used in probabilistic planning for stochastic domains. However, current extensions, such as constrained and chance-constrained POMDPs, have limitations in modeling real-world planning problems because they assume that all actions have a fixed duration. To address this issue, we propose a unified model that encompasses durative POMDP and its constrained extensions. To solve the durative POMDP and its constrained extensions, we first convert them into an Integer Linear Programming (ILP) formulation. This approach leverages existing solvers in the ILP literature and provides a foundation for solving these problems. We then introduce a heuristic search approach that prunes the search space, which is guided by solving successive partial ILP programs. Our empirical evaluation results show that our approach outperforms the current state-of-the-art fixed-horizon chance-constrained POMDP solver.

    Original languageBritish English
    Title of host publicationAAAI-23 Special Tracks
    EditorsBrian Williams, Yiling Chen, Jennifer Neville
    Pages14927-14936
    Number of pages10
    ISBN (Electronic)9781577358800
    StatePublished - 27 Jun 2023
    Event37th AAAI Conference on Artificial Intelligence, AAAI 2023 - Washington, United States
    Duration: 7 Feb 202314 Feb 2023

    Publication series

    NameProceedings of the 37th AAAI Conference on Artificial Intelligence, AAAI 2023
    Volume37

    Conference

    Conference37th AAAI Conference on Artificial Intelligence, AAAI 2023
    Country/TerritoryUnited States
    CityWashington
    Period7/02/2314/02/23

    Fingerprint

    Dive into the research topics of 'Heuristic Search in Dual Space for Constrained Fixed-Horizon POMDPs with Durative Actions'. Together they form a unique fingerprint.

    Cite this