A Simple and Fast Bi-Objective Search Algorithm

Carlos Hernández Ulloa, William Yeoh, Jorge A. Baier, Han Zhang, Luis Suazo, Sven Koenig

 PosterID: 33
picture_as_pdf PDF
library_books Slides
library_books Poster
menu_book BibTeX
Many interesting search problems can be formulated as bi-objective search problems; for example, transportation problems where both travel distance and time need to be minimized. Multi-objective best-first search algorithms need to maintain the set of undominated paths from the start state to each state to compute a set of paths from a given start state to a given goal state (the Pareto-optimal solutions) such that no path in the set is dominated by another path in the set. Each time they find a new path to a state n, they perform a dominance check to determine whether such a path dominates any of the previously found paths to n. Existing algorithms do not perform these checks efficiently, requiring at least a full iteration over the Open list per check. In this paper, we present the first multi-objective algorithm that performs these checks efficiently. Indeed, Bi-Objective A*(BOA*)—our algorithm—requires constant time to check for dominance. Our experimental evaluation shows that BOA* is orders-of-magnitude faster than state-of-the-art search algorithms, such as NAMOA*, Bi-Objective Dijkstra, and Bidirectional Bi-Objective Dijkstra.

Session Am3: Search & Hybrid Planning
Canb 10/28/2020, 10:00 – 11:00
10/30/2020, 03:00 – 04:00
Paris 10/28/2020, 00:00 – 01:00
10/29/2020, 17:00 – 18:00
NYC 10/27/2020, 19:00 – 20:00
10/29/2020, 12:00 – 13:00
LA 10/27/2020, 16:00 – 17:00
10/29/2020, 09:00 – 10:00
Contact: icaps20-support (at) googlegroups.com
Copyright ©2020 by ICAPS.