Heuristic search planning with multi-objective probabilistic LTL constraints

Peter Baumgartner, Sylvie Thiébaux, Felipe Trevizan

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

    7 Citations (Scopus)

    Abstract

    We present an algorithm for computing cost-optimal stochastic policies for Stochastic Shortest Path problems (SSPs) subject to multi-objective PLTL constraints, i.e., conjunctions of probabilistic LTL formulas. Established algorithms capable of solving this problem typically stem from the area of probabilistic verification, and struggle with the large state spaces and constraint types found in automated planning. Our approach differs in two crucial ways. Firstly it operates entirely on-the-fly, bypassing the expensive construction of Rabin automata for the formulas and their prohibitive prior synchronisation with the full state space of the SSP. Secondly, it extends recent heuristic search algorithms and admissible heuristics for cost-constrained SSPs, to enable pruning regions made infeasible by the PLTL constraints. We prove our algorithm correct and optimal, and demonstrate encouraging scalability results.

    Original languageEnglish
    Title of host publicationPrinciples of Knowledge Representation and Reasoning
    Subtitle of host publicationProceedings of the 16th International Conference, KR 2018
    EditorsMichael Thielscher, Francesca Toni, Frank Wolter
    PublisherAAAI Press
    Pages415-424
    Number of pages10
    ISBN (Electronic)9781577358039
    Publication statusPublished - 2018
    Event16th International Conference on the Principles of Knowledge Representation and Reasoning, KR 2018 - Tempe, United States
    Duration: 30 Oct 20182 Nov 2018

    Publication series

    NamePrinciples of Knowledge Representation and Reasoning: Proceedings of the 16th International Conference, KR 2018

    Conference

    Conference16th International Conference on the Principles of Knowledge Representation and Reasoning, KR 2018
    Country/TerritoryUnited States
    CityTempe
    Period30/10/182/11/18

    Fingerprint

    Dive into the research topics of 'Heuristic search planning with multi-objective probabilistic LTL constraints'. Together they form a unique fingerprint.

    Cite this