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 »
This content will become publicly available on January 1, 2023
Anytime Approximate BiObjective Search
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 much more »
 Award ID(s):
 2121028
 Publication Date:
 NSFPAR ID:
 10350232
 Journal Name:
 Proceedings of the Symposium on Combinatorial Search (SoCS)
 Sponsoring Org:
 National Science Foundation
More Like this


Many interesting search problems can be formulated as biobjective search problems, that is, search problems where two kinds of costs have to be minimized, for example, travel distance and time for transportation problems. Biobjective search algorithms have to maintain the set of undominated paths from the start state to each state to compute the set of paths from the start state to the goal state that are not dominated by some other path from the start state to the goal state (called the Paretooptimal solution set). Each time they find a new path to a state s, they perform a dominance check to determine whether this path dominates any of the previously found paths to s or whether any of the previously found paths to s dominates this path. Existing algorithms do not perform these checks efficiently. On the other hand, our BiObjective A* (BOA*) algorithm requires only constant time per check. In our experimental evaluation, we show that BOA* can run an order of magnitude (or more) faster than stateoftheart biobjective search algorithms, such as NAMOA*, NAMOA*dr, BiObjective Dijkstra, and Bidirectional BiObjective Dijkstra.

NA (Ed.)This work addresses a MultiObjective Shortest Path Problem (MOSPP) on a graph where the goal is to find a set of Paretooptimal solutions from a start node to a destination in the graph. A family of approaches based on MOA* have been developed to solve MOSPP in the literature. Typically, these approaches maintain a “frontier” set at each node during the search process to keep track of the nondominated, partial paths to reach that node. This search process becomes computationally expensive when the number of objectives increases as the number of Paretooptimal solutions becomes large. In this work, we introduce a new method to efficiently maintain these frontiers for multiple objectives by incrementally constructing balanced binary search trees within the MOA* search framework. We first show that our approach correctly finds the Paretooptimal front, and then provide extensive simulation results for problems with three, four and five objectives to show that our method runs faster than existing techniques by up to an order of magnitude.

At the heart of both lossy compression and clustering is a tradeoff between the fidelity and size of the learned representation. Our goal is to map out and study the Pareto frontier that quantifies this tradeoff. We focus on the optimization of the Deterministic Information Bottleneck (DIB) objective over the space of hard clusterings. To this end, we introduce the primal DIB problem, which we show results in a much richer frontier than its previously studied Lagrangian relaxation when optimized over discrete search spaces. We present an algorithm for mapping out the Pareto frontier of the primal DIB tradeoff that is also applicable to other twoobjective clustering problems. We study general properties of the Pareto frontier, and we give both analytic and numerical evidence for logarithmic sparsity of the frontier in general. We provide evidence that our algorithm has polynomial scaling despite the superexponential search space, and additionally, we propose a modification to the algorithm that can be used where sampling noise is expected to be significant. Finally, we use our algorithm to map the DIB frontier of three different tasks: compressing the English alphabet, extracting informative color classes from natural images, and compressing a group theoryinspired dataset, revealing interestingmore »

A key challenge in conformer sampling is finding lowenergy conformations with a small number of energy evaluations. We recently demonstrated the Bayesian Optimization Algorithm (BOA) is an effective method for finding the lowest energy conformation of a small molecule. Our approach balances between exploitation and exploration, and is more efficient than exhaustive or random search methods. Here, we extend strategies used on proteins and oligopeptides ( e.g. Ramachandran plots of secondary structure) and study correlated torsions in small molecules. We use bivariate von Mises distributions to capture correlations, and use them to constrain the search space. We validate the performance of our new method, Bayesian Optimization with Knowledgebased Expected Improvement (BOKEI), on a dataset consisting of 533 diverse small molecules, using (i) a force field (MMFF94); and (ii) a semiempirical method (GFN2), as the objective function. We compare the search performance of BOKEI, BOA with Expected Improvement (BOAEI), and a genetic algorithm (GA), using a fixed number of energy evaluations. In more than 60% of the cases examined, BOKEI finds lower energy conformations than global optimization with BOAEI or GA. More importantly, we find correlated torsions in up to 15% of small molecules in larger data sets, up to 8more »