TY - GEN
T1 - Heuristic search planning with multi-objective probabilistic LTL constraints
AU - Baumgartner, Peter
AU - Thiébaux, Sylvie
AU - Trevizan, Felipe
N1 - Publisher Copyright:
Copyright © 2018, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
PY - 2018
Y1 - 2018
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85088270447&partnerID=8YFLogxK
M3 - Conference contribution
T3 - Principles of Knowledge Representation and Reasoning: Proceedings of the 16th International Conference, KR 2018
SP - 415
EP - 424
BT - Principles of Knowledge Representation and Reasoning
A2 - Thielscher, Michael
A2 - Toni, Francesca
A2 - Wolter, Frank
PB - AAAI Press
T2 - 16th International Conference on the Principles of Knowledge Representation and Reasoning, KR 2018
Y2 - 30 October 2018 through 2 November 2018
ER -