Heuristic Search for Multi-Objective Probabilistic Planning
Dillon Z. Chen, Felipe Trevizan, Sylvie Thiébaux
Abstract
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.
BibTeX
@article{Chen_Trevizan_Thiébaux_2023, title={Heuristic Search for Multi-Objective Probabilistic Planning}, volume={37}, url={https://ojs.aaai.org/index.php/AAAI/article/view/26409}, DOI={10.1609/aaai.v37i10.26409}, abstractNote={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.}, number={10}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Chen, Dillon Z. and Trevizan, Felipe and Thiébaux, Sylvie}, year={2023}, month={Jun.}, pages={11945-11954} }