אריאל פלנר

In multi-objective search, we consider a graph whose edges are annotated with multiple cost components. A typical task is to compute the Pareto frontier, i.e., the set of all undominated paths from a given start state to a given goal state of the graph. However, the size of the Pareto frontier can be exponential in the size of the graph, and computing the entire Pareto frontier can be very time-consuming. Therefore, in this paper, we study how to find an approximate frontier for a user-provided approximation factor. Such a frontier can be significantly smaller than the Pareto frontier, enabling the design of efficient approximate multi-objective search algorithms. We present such an algorithm called A*pex, which uses an efficient, albeit approximate, representation of paths with similar costs to compute an approximate frontier. During the search, it avoids storing all paths explicitly, thereby reducing the search effort. We show that A*pex can be used as an algorithmic building block to solve additional problems by presenting (1) an anytime variant of A*pex, which computes an initial approximate frontier quickly and then works to find better approximate frontiers until eventually finding the entire Pareto frontier and (2) a variant of A*pex for approximately solving the Weight-Constrained Shortest Path (WCSP) problem, a problem that is closely related to multi-objective search. For evaluation, we use road networks from the 9th DIMACS Implementation Challenge: Shortest Path for evaluation. Our experimental results show that A*pex and its WCSP variant can outperform respective state-of-the-art algorithms by orders of magnitude in terms of runtime. We also show that the anytime variant of A*pex often computes better approximate frontiers than state-of-the-art algorithms, given a limited runtime.