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 New Approach for the Resource Constrained Shortest Path Problem
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
 Award ID(s):
 2120529
 NSFPAR ID:
 10466861
 Publisher / Repository:
 IEEE
 Date Published:
 Journal Name:
 IEEE Transactions on Intelligent Transportation Systems
 ISSN:
 00000000
 Subject(s) / Keyword(s):
 Index Terms—Path Planning, Heuristic Search, Shortest Path
 Format(s):
 Medium: X
 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.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

We consider a variant of the MultiAgent PathFinding problem that seeks both task assignments and collisionfree paths for a set of agents navigating on a graph, while minimizing the sum of costs of all agents. Our approach extends ConflictBased Search (CBS), a framework that has been previously used to find collisionfree paths for a given fixed task assignment. Our approach is based on two key ideas: (i) we operate on a search forest rather than a search tree; and (ii) we create the forest on demand, avoiding a factorial explosion of all possible task assignments. We show that our new algorithm, CBSTA, is complete and optimal. The CBS framework allows us to extend our method to ECBSTA, a bounded suboptimal version. We provide extensive empirical results comparing CBSTA to task assignment followed by CBS, ConflictBased MinCostFlow (CBM), and an integer linear program (ILP) solution, demonstrating the advantages of our algorithm. Our results highlight a significant advantage in jointly optimizing the task assignment and path planning for very dense cases compared to the traditional method of solving those two problems independently. For large environments with many robots we show that the traditional approach is reasonable, but that we can achieve similar results with the same runtime but stronger suboptimality guarantees.more » « less

Conventional MultiAgent Path Finding (MAPF) problems aim to compute an ensemble of collisionfree paths for multiple agents from their respective starting locations to preallocated destinations. This work considers a generalized version of MAPF called MultiAgent Combinatorial Path Finding (MCPF) where agents must collectively visit a large number of intermediate target locations along their paths before arriving at destinations. This problem involves not only planning collisionfree paths for multiple agents but also assigning targets and specifying the visiting order for each agent (i.e., target sequencing). To solve the problem, we leverage ConflictBased Search (CBS) for MAPF and propose a novel approach called ConflictBased Steiner Search (CBSS). CBSS interleaves (1) the collision resolution strategy in CBS to bypass the curse of dimensionality in MAPF and (2) multiple traveling salesman algorithms to handle the combinatorics in target sequencing, to compute optimal or bounded suboptimal paths for agents while visiting all the targets. We also develop two variants of CBSS that trade off runtime against solution optimality. Our test results verify the advantage of CBSS over the baselines in terms of computing cheaper paths and improving success rates within a runtime limit for up to 20 agents and 50 targets. Finally, we run both Gazebo simulation and physical robot tests to validate that the planned paths are executablemore » « less