Multi-objective AI planning suffers from a lack of benchmarks exhibiting
known Pareto Fronts. In this work, we propose a tunable benchmark generator,
together with a dedicated solver that provably computes the true Pareto front
of the resulting instances. First, we prove a proposition allowing us to
characterize the optimal plans for a constrained version of the problem, and
then show how to reduce the general problem to the constrained one. Second, we
provide a constructive way to find all the Pareto-optimal plans and discuss the
complexity of the algorithm. We provide an implementation that allows the
solver to handle realistic instances in a reasonable time. Finally, as a
practical demonstration, we used this solver to find all Pareto-optimal plans
between the two largest airports in the world, considering the routes between
the 50 largest airports, spherical distances between airports and a made-up
risk.

本文提出了一种可调式基准生成器以及相应的求解器，能够可靠地计算得出所得实例的真实 Pareto 前沿，并讨论了算法的复杂度和如何找出所有 Pareto 最优解。实际演示表明，我们的求解器可以在合理的时间内找到世界上两个最大机场之间的所有 Pareto 最优计划。