# Heuristic Search for Multi-Objective Probabilistic Planning

arXiv: https://arxiv.org/abs/2303.14363 · HTML: https://mlsanity.com/paper/2303.14363/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 27 references that are in the map.
- First posted on arXiv 25 Mar 2023.

## Builds on (most cited first, 2 of 2)

- [Topological Value Iteration Algorithms](https://mlsanity.com/paper/1401.3910/) (2014)
- [Convex Hull Monte-Carlo Tree Search](https://mlsanity.com/paper/2003.04445/) (2020)

## Built on by (most cited first, 4 of 4)

- [Runtime Analysis of Evolutionary Algorithms for Multi-party Multi-objective Optimization](https://mlsanity.com/paper/2501.16336/) (2025)
- [Uncertain Machine Ethics Planning](https://mlsanity.com/paper/2505.04352/) (2025)
- [Solving Constrained Stochastic Shortest Path Problems with Scalarisation](https://mlsanity.com/paper/2508.17446/) (2025)
- [Multi-Objective Search: Algorithms, Applications, and Emerging Directions](https://mlsanity.com/paper/2510.25504/) (2025)

## Abstract (arXiv)

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.