Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

In multiobjective 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 componentwise sum of the cost vectors of the edges of the former path is 'less than' the componentwise sum of the cost vectors of the edges of the latter path. The Paretooptimal 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 multiobjective search timeconsuming. In this paper, we therefore study how to find an approximate Paretooptimal solution set for a userprovided vector of approximation factors. The size of such a solution set can be significantly smaller than the size of the Paretooptimal solution set, which enables the design of approximate multiobjective search algorithms that are efficient and produce small solution sets. We present such an algorithm in this paper, called A*pex. A*pex builds on PPA*, a stateoftheart approximate biobjective search algorithm (where there are only two cost components) but (1) makes PPA* more efficient for biobjective search and (2) generalizes it to multiobjective search for any numbermore »Free, publiclyaccessible full text available January 1, 2023

The Paretooptimal frontier for a biobjective search problem instance consists of all solutions that are not worse than any other solution in both objectives. The size of the Paretooptimal frontier can be exponential in the size of the input graph, and hence finding it can be hard. Some existing works leverage a userspecified approximation factor ε to compute an approximate Paretooptimal frontier that can be significantly smaller than the Paretooptimal frontier. In this paper, we propose an anytime approximate biobjective search algorithm, called Anytime BiObjective A*ε (ABOA*ε). ABOA*ε is useful when deliberation time is limited. It first finds an approximate Paretooptimal frontier quickly, iteratively improves it while time allows, and eventually finds the Paretooptimal frontier. It efficiently reuses the search effort from previous iterations and makes use of a novel pruning technique. Our experimental results show that ABOA*ε substantially outperforms baseline algorithms that do not reuse previous search effort, both in terms of runtime and number of node expansions. In fact, the most advanced variant of ABOA*ε even slightly outperforms BOA*, a stateoftheart biobjective search algorithm, for finding the Paretooptimal frontier. Moreover, given only a limited amount of deliberation time, ABOA*ε finds solutions that collectively approximate the Paretooptimal frontier muchmore »Free, publiclyaccessible full text available January 1, 2023

There are many settings that extend the basic shortestpath search problem. In BoundedCost Search, we are given a constant bound, and the task is to find a solution within the bound. In BiObjective Search, each edge is associated with two costs (objectives), and the task is to minimize both objectives. In this paper, we combine both settings into a new setting of BoundedCost BiObjective Search. We are given two bounds, one for each objective, and the task is to find a solution within these bounds. We provide a scheme for normalizing the two objectives, introduce several algorithms for this new setting and compare them experimentally.Free, publiclyaccessible full text available January 1, 2023