Admissible Heuristics for Multi-Objective Planning


  • Florian Geißer Australian National University
  • Patrik Haslum Australian National University
  • Sylvie Thiébaux Australian National University
  • Felipe Trevizan Australian National University



Multi-objective Planning, Heuristic Search, Deterministic Planning, Classical Planning


Planning problems of practical relevance commonly include multiple objectives that are difficult to weight a priori. Several heuristic search algorithms computing the Pareto front of non-dominated solutions have been proposed to handle these multi-objective (MO) planning problems. However, the design of informative admissible heuristics to guide these algorithms has not received the same level of attention. The standard practice is to use the so-called ideal point combination, which applies a single-objective heuristic to each objective independently, without capturing any of the trade-offs between them. This paper fills this gap: we extend several classes of classical planning heuristics to the multi-objective case, in such a way as to reflect the tradeoffs underlying the various objectives. We find that MO abstraction heuristics achieve overall the best performance, but that not every MO generalisation pays off.




How to Cite

Geißer, F., Haslum, P., Thiébaux, S., & Trevizan, F. (2022). Admissible Heuristics for Multi-Objective Planning. Proceedings of the International Conference on Automated Planning and Scheduling, 32(1), 100-109.