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 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 triobjective search.
more »
« less
A Simple and Fast BiObjective Search Algorithm
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.
more »
« less
 NSFPAR ID:
 10193992
 Date Published:
 Journal Name:
 Proceedings of the International Conference on Automated Planning and Scheduling
 Volume:
 30
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


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 better than the solutions found by BOA*.more » « less

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.more » « less

N/A (Ed.)Abstract—The Resource Constrained Shortest Path Problem (RCSPP) seeks to determine a minimumcost path between a start and a goal location while ensuring that one or multiple types of resource consumed along the path do not exceed their limits. This problem is often solved on a graph where a path is incrementally built from the start towards the goal during the search. RCSPP is computationally challenging as comparing these partial solution paths is based on multiple criteria (i.e., the accumulated cost and resource along the path), and in general, there does not exist a single path that optimizes all criteria simultaneously. Consequently, the search needs to maintain and explore a large number of partial paths in order to find an optimal solution. While a variety of algorithms have been developed to solve RCSPP, they either have little consideration about efficiently comparing and maintaining the partial paths, which reduces their overall runtime efficiency, or are restricted to handle only one resource constraint as opposed to multiple resource constraints. This paper develops Enhanced Resource Constrained A* (ERCA*), a fast A*based algorithm that can find an optimal solution while satisfying multiple resource constraints. ERCA* leverages both the recent advances in multiobjective path planning to efficiently compare and maintain partial paths, and techniques from the existing RCSPP literature. Furthermore, ERCA* has a functional parameter to broker a tradeoff between solution quality and runtime efficiency. The results show ERCA* often runs several orders of magnitude faster than an existing leading algorithm for RCSPP.more » « less

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.more » « less