The Pareto-optimal frontier for a bi-objective search problem instance consists of all solutions that are not worse than any other solution in both objectives. The size of the Pareto-optimal frontier can be exponential in the size of the input graph, and hence finding it can be hard. Some existing works leverage a user-specified approximation factor ε to compute an approximate Pareto-optimal frontier that can be significantly smaller than the Pareto-optimal frontier. In this paper, we propose an anytime approximate bi-objective search algorithm, called Anytime Bi-Objective A*-ε (A-BOA*ε). A-BOA*ε is useful when deliberation time is limited. It first finds an approximate Pareto-optimal frontier quickly, iteratively improves it while time allows, and eventually finds the Pareto-optimal frontier. It efficiently reuses the search effort from previous iterations and makes use of a novel pruning technique. Our experimental results show that A-BOA*ε 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 A-BOA*ε even slightly outperforms BOA*, a state-of-the-art bi-objective search algorithm, for finding the Pareto-optimal frontier. Moreover, given only a limited amount of deliberation time, A-BOA*ε finds solutions that collectively approximate the Pareto-optimal frontier much better than the solutions found by BOA*.
more »
« less
Enhanced multi-objective A* using balanced binary search trees
This work addresses a Multi-Objective Shortest Path Problem
(MO-SPP) on a graph where the goal is to find a set of
Pareto-optimal solutions from a start node to a destination
in the graph. A family of approaches based on MOA* have
been developed to solve MO-SPP in the literature. Typically,
these approaches maintain a “frontier” set at each node during
the search process to keep track of the non-dominated, partial
paths to reach that node. This search process becomes computationally
expensive when the number of objectives increases
as the number of Pareto-optimal 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 Pareto-optimal 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.
more »
« less
- Award ID(s):
- 2120529
- NSF-PAR ID:
- 10354018
- Editor(s):
- NA
- Date Published:
- Journal Name:
- Proceedings of the International Symposium on Combinatorial Search
- Volume:
- 15
- Issue:
- 1
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
more » « less
We initiate the study of fair distribution of delivery tasks among a set of agents wherein delivery jobs are placed along the vertices of a graph. Our goal is to fairly distribute delivery costs (modeled as a submodular function) among a fixed set of agents while satisfying some desirable notions of economic efficiency. We adopt well-established fairness concepts—such as envy-freeness up to one item (EF1) and minimax share (MMS)—to our setting and show that fairness is often incompatible with the efficiency notion of social optimality. Yet, we characterize instances that admit fair and socially optimal solutions by exploiting graph structures. We further show that achieving fairness along with Pareto optimality is computationally intractable. Nonetheless, we design an XP algorithm (parameterized by the number of agents) for finding MMS and Pareto optimal solutions on every tree instance, and show that the same algorithm can be modified to find efficient solutions along with EF1, when such solutions exist. We complement these results by theoretically and experimentally analyzing the price of fairness.
-
more » « less
Dynamic coded x-ray tomosynthesis (CXT) uses a set of encoded x-ray sources to interrogate objects lying on a moving conveyor mechanism. The object is reconstructed from the encoded measurements received by the uniform linear array detectors. We propose a multi-objective optimization (MO) method for structured illuminations to balance the reconstruction quality and radiation dose in a dynamic CXT system. The MO framework is established based on a dynamic sensing geometry with binary coding masks. The Strength Pareto Evolutionary Algorithm 2 is used to solve the MO problem by jointly optimizing the coding masks, locations of x-ray sources, and exposure moments. Computational experiments are implemented to assess the proposed MO method. They show that the proposed strategy can obtain a set of Pareto optimal solutions with different levels of radiation dose and better reconstruction quality than the initial setting.
-
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, called A*pex. A*pex builds on PPA*, a state-of-the-art approximate bi-objective search algorithm (where there are only two cost components) but (1) makes PPA* 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.more » « less
-
Issues of fairness often arise in graphical neural networks used for misinformation detection. However, improving fairness can often come at the cost of reducing accuracy and vice versa. Therefore, we formulate the task of balancing accuracy and fairness as a multi-objective optimization (MOO) problem where we seek to find a set of Pareto optimal solutions. Traditional first-order approaches to solving MOO problems such as multigradient descent can be costly, especially with large neural networks. Instead, we describe a more efficient approach using the predictor-corrector method. Given an initial Pareto optimal point, this approach predicts the direction of a neighboring solution and refines this prediction using a few steps of multigradient descent. We show experimentally that this approach allows for the generation of high-quality Pareto fronts faster than baseline optimization methods.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
