@article{Hernández Ulloa_Yeoh_Baier_Zhang_Suazo_Koenig_2020, title={A Simple and Fast Bi-Objective Search Algorithm}, volume={30}, url={https://ojs.aaai.org/index.php/ICAPS/article/view/6655}, abstractNote={<p>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 <em>s</em>, they perform a <em>dominance check</em> to determine whether this path dominates any of the previously found paths to <em>s</em> or whether any of the previously found paths to <em>s</em> 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.</p>}, number={1}, journal={Proceedings of the International Conference on Automated Planning and Scheduling}, author={Hernández Ulloa, Carlos and Yeoh, William and Baier, Jorge A. and Zhang, Han and Suazo, Luis and Koenig, Sven}, year={2020}, month={Jun.}, pages={143-151} }