A Simple and Fast Bi-Objective Search Algorithm
Proceedings of the International Conference on Automated Planning and Scheduling · 01.06.2020 · 30 · 143-151
DOI: 10.1609/icaps.v30i1.6655 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the International Conference on Automated Planning and Scheduling, online erschienen am 01.06.2020. Verfasst von Carlos Hernández Ulloa und 5 weiteren Autor:innen. Die Arbeit wurde bisher 19-mal zitiert (Crossref).
Abstract (Originalsprache)
Many interesting search problems can be formulated as bi-objective 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 bi-objective search algorithms, such as NAMOA*, NAMOA*dr, Bi-Objective Dijkstra, and Bidirectional Bi-Objective Dijkstra.
Zitieren
APA
Ulloa, C. H., Yeoh, W., Baier, J. A., Zhang, H., Suazo, L., & Koenig, S. (2020). A Simple and Fast Bi-Objective Search Algorithm. Proceedings of the International Conference on Automated Planning and Scheduling, 30, 143-151. https://doi.org/10.1609/icaps.v30i1.6655
Vancouver
Ulloa CH, Yeoh W, Baier JA, Zhang H, Suazo L, Koenig S. A Simple and Fast Bi-Objective Search Algorithm. Proceedings of the International Conference on Automated Planning and Scheduling. 2020;30:143-151. doi:10.1609/icaps.v30i1.6655
BibTeX
@article{Ulloa2020,
author = {Ulloa, Carlos Hernández and Yeoh, William and Baier, Jorge A. and Zhang, Han and Suazo, Luis and Koenig, Sven},
title = {A Simple and Fast Bi-Objective Search Algorithm},
journal = {Proceedings of the International Conference on Automated Planning and Scheduling},
year = {2020},
volume = {30},
pages = {143--151},
doi = {10.1609/icaps.v30i1.6655}
}
EUVIMED