Heuristic Search for Multi-Objective Probabilistic Planning
This work addresses multi-objective probabilistic planning for AI and operations research, but it is incremental as it extends existing SSP methods to a more expressive class.
The paper tackles the problem of multi-objective stochastic shortest paths (MOSSPs) by extending heuristic search algorithms to compute non-dominated policies, with experiments showing benefits and heuristic merits.
Heuristic search is a powerful approach that has successfully been applied to a broad class of planning problems, including classical planning, multi-objective planning, and probabilistic planning modelled as a stochastic shortest path (SSP) problem. Here, we extend the reach of heuristic search to a more expressive class of problems, namely multi-objective stochastic shortest paths (MOSSPs), which require computing a coverage set of non-dominated policies. We design new heuristic search algorithms MOLAO* and MOLRTDP, which extend well-known SSP algorithms to the multi-objective case. We further construct a spectrum of domain-independent heuristic functions differing in their ability to take into account the stochastic and multi-objective features of the problem to guide the search. Our experiments demonstrate the benefits of these algorithms and the relative merits of the heuristics.