Progression Heuristics for Planning with Probabilistic LTL Constraints

Mallet, I., Thiébaux, S. and Trevizan, F. To appear in Proc. of 35th AAAI Conference on Artificial Intelligence.

We are working on the camera-ready of this paper and it will be available soon. Bellow is the abstract of this paper.

Probabilistic planning subject to multi-objective probabilistic temporal logic (PLTL) constraints models the problem of computing safe and robust behaviours for agents in stochastic environments. We present novel admissible heuristics to guide the search for cost-optimal policies for these problems. These heuristics project and decompose LTL formulae obtained by progression to estimate the probability that an extension of a partial policy satisfies the constraints. Their computation with linear programming is integrated with the recent PLTL-dual heuristic search algorithm, enabling more aggressive pruning of regions violating the constraints. Our experiments show that they further widen the scalability gap between heuristic search and verification approaches to these planning problems.

  • News and Highlights
    • New heuristics for SSPs with PLTL constraints! This time based on progression (AAAI'21).
    • STRIPS-HGN: First algorithm capable of learning domain-independent heuristics from scratch (ICAPS'20).
    • New insights and results for ASNets on JAIR
    • Guiding search using generalized policies from ASNets (SoCS'19)
    • PLTL-dual: First heuristic search algorithm for SSPs and MDPs with Probabilistic LTL constraints (KR'18).
    • ASNets: Learning generalized policies for SSPs using neural nets (AAAI'18).
    • h-pom, h-roc, and i2-dual won the best paper award at ICAPS'17!
    • New efficient approach to solve SSPs and C-SSPs with dead ends (UAI'17).
    • h-pom and h-roc: the first heuristics able to handle probabilities and costs for SSPs and C-SSPs (ICAPS'17).
    • i-dual won the best paper award at ICAPS'16!
    • QTM won the Kikuchi-Karlaftis best paper award at TRB'16! (demo).
  • Word cloud of my papers
  • wordcloud
    large wordcloud