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.

本篇论文旨在将启发式搜索算法应用于多目标随机最短路径 (MOSSPs) 问题，提出了基于相对快速的 MOLAO* 和 MOLRTDP 两种算法，以及一系列能够应对随机、多目标特点的启发式函数，通过实验证明了新算法及函数的有效性。