A*pex: Efficient Approximate Multi-Objective Search on Graphs

Authors

  • Han Zhang University of Southern California
  • Oren Salzman Technion, Israel Institute of Technology
  • T. K. Satish Kumar University of Southern California
  • Ariel Felner Ben-Gurion University of the Negev
  • Carlos Hernández Ulloa Universidad San Sebastian
  • Sven Koenig University of Southern California

Keywords:

Multi-Objective Shortest Path, Pareto Frontier, Heuristic Search

Abstract

In multi-objective search, edges are annotated with cost vectors consisting of multiple cost components. A path dominates another path with the same start and goal vertices iff the component-wise sum of the cost vectors of the edges of the former path is ``less than'' the component-wise sum of the cost vectors of the edges of the latter path. The Pareto-optimal solution set is the set of all undominated paths from a given start vertex to a given goal vertex. Its size can be exponential in the size of the graph being searched, which makes multi-objective search time-consuming. In this paper, we therefore study how to find an approximate Pareto-optimal solution set for a user-provided vector of approximation factors. The size of such a solution set can be significantly smaller than the size of the Pareto-optimal solution set, which enables the design of approximate multi-objective search algorithms that are efficient and produce small solution sets. We present such an algorithm in this paper which we call A*pex and which builds on PP-A*, a state-of-the-art approximate bi-objective search algorithm (where there are only two cost components) but (1) makes PP-A* more efficient for bi-objective search and (2) generalizes it to multi-objective search for any number of cost components. We first analyze the correctness of A*pex and then experimentally demonstrate its efficiency advantage over existing approximate algorithms for bi- and tri-objective search.

Downloads

Published

2022-06-13

How to Cite

Zhang, H., Salzman, O., Kumar, T. K. S., Felner, A., Hernández Ulloa, C., & Koenig, S. (2022). A*pex: Efficient Approximate Multi-Objective Search on Graphs. Proceedings of the International Conference on Automated Planning and Scheduling, 32(1), 394-403. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/19825