Abstract

Abstract: 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. 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. A*pex can be used as an algorithmic building block to solve additional problems. Thus, we present (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. 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.

Download the paper in pdf.

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.