Domain-Independent Heuristics in Probabilistic Planning. Klößner, T. In Proceedings of the 20th ICAPS Doctoral Consortium (ICAPS DC 2022), pages 27–31, 2022.
Domain-Independent Heuristics in Probabilistic Planning [pdf]Paper  Domain-Independent Heuristics in Probabilistic Planning [link]Presentation  abstract   bibtex   9 downloads  
It has been almost two decades since MDP heuristic search algorithms have been developed. These algorithms guarantee to find an optimal policy for the initial state for several optimization objectives without necessarily expanding the entire state space, if provided with a heuristic that provides optimistic state value estimates. While a large and diverse set of such domain-independent heuristic families is available in classical planning, the same cannot be said about probabilistic planning. So far, except for the particular case of occupation measure heuristics for (constrained) Stochastic Shortest Path Problems, most of the attempts at constructing heuristics pursue the very simple approach of using a classical heuristic on the all-outcomes determinization of the planning problem, in which the probabilistic effect of an action can be chosen at will. Because this approach is agnostic to the uncertainty in the underlying problem, these heuristics are often not very informative. In this thesis, we will investigate heuristics for probabilistic planning which are formulated on the underlying probabilistic model directly instead of delegating to a classical heuristic on the determinization. To this end, we mainly focus on abstraction heuristics, in particular Pattern Database heuristics and Merge-and-Shrink heuristics.

Downloads: 9