TY - JOUR
T1 - A simple and fast bi-objective search algorithm
AU - Ulloa, Carlos Hernández
AU - Yeoh, William
AU - Baier, Jorge A.
AU - Zhang, Han
AU - Suazo, Luis
AU - Koenig, Sven
N1 - Funding Information:
The research at the University of Southern California was supported by the National Science Foundation (NSF) under grant numbers 1409987, 1724392, 1817189, 1837779, and 1935712. The research at Washington University in St. Louis was supported by NSF under grant numbers 1812619 and 1838364. Jorge Baier was supported by a FondDCC grant from the Dept. of Computer Science at PUC Chile.
Publisher Copyright:
Copyright © 2020, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2020/5/29
Y1 - 2020/5/29
N2 - 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. Bi-objective 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 Pareto-optimal 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 Bi-Objective 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 state-of-the-art biobjective search algorithms, such as NAMOA*, NAMOA*dr, Bi-Objective Dijkstra, and Bidirectional Bi-Objective Dijkstra.
AB - 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. Bi-objective 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 Pareto-optimal 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 Bi-Objective 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 state-of-the-art biobjective search algorithms, such as NAMOA*, NAMOA*dr, Bi-Objective Dijkstra, and Bidirectional Bi-Objective Dijkstra.
UR - http://www.scopus.com/inward/record.url?scp=85088518834&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:85088518834
SN - 2334-0835
VL - 30
SP - 143
EP - 151
JO - Proceedings International Conference on Automated Planning and Scheduling, ICAPS
JF - Proceedings International Conference on Automated Planning and Scheduling, ICAPS
T2 - 30th International Conference on Automated Planning and Scheduling, ICAPS 2020
Y2 - 26 October 2020 through 30 October 2020
ER -