Simple and efficient bi-objective search algorithms via fast dominance checks

Simple item page
dc.contributor.authorHernandez, Carlos
dc.contributor.authorYeoh, William
dc.contributor.authorBaier, Jorge A.
dc.contributor.authorZhang, Han
dc.contributor.authorSuazo, Luis
dc.contributor.authorKoenig, Sven
dc.contributor.authorSalzman, Oren
dc.date.accessioned2025-01-20T20:20:17Z
dc.date.available2025-01-20T20:20:17Z
dc.date.issued2023
dc.description.abstractMany 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. Instead of looking for a single optimal path, we compute a Pareto-optimal frontier in bi-objective search, which is a set of paths in which no two paths dominate each other. Bi-objective search algorithms perform dominance checks each time a new path is discovered. Thus, the efficiency of these checks is key to performance. In this article, we propose algorithms for two kinds of bi-objective search problems. First, we consider the problem of computing the Pareto-optimal frontier of the paths that connect a given start state with a given goal state. We propose Bi-Objective A* (BOA*), a heuristic search algorithm based on A*, for this problem. Second, we consider the problem of computing one Pareto-optimal frontier for each state s of the search graph, which contains the paths that connect a given start state with s. We propose Bi-Objective Dijkstra (BOD), which is based on BOA*, for this problem. A common feature of BOA* and BOD is that all dominance checks are performed in constant time, unlike the dominance checks of previous algorithms. We show in our experimental evaluation that both BOA* and BOD are substantially faster than state-of-the-art bi-objective search algorithms. (c) 2022 Published by Elsevier B.V.
dc.fuente.origenWOS
dc.identifier.doi10.1016/j.artint.2022.103807
dc.identifier.eissn1872-7921
dc.identifier.issn0004-3702
dc.identifier.urihttps://doi.org/10.1016/j.artint.2022.103807
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/92571
dc.identifier.wosidWOS:000885986700002
dc.language.isoen
dc.revistaArtificial intelligence
dc.rightsacceso restringido
dc.subjectA*
dc.subjectBi-objective search
dc.subjectDijkstra's algorithm
dc.subjectHeuristic search
dc.subject.ods11 Sustainable Cities and Communities
dc.subject.odspa11 Ciudades y comunidades sostenibles
dc.titleSimple and efficient bi-objective search algorithms via fast dominance checks
dc.typeartículo
dc.volumen314
sipa.indexWOS
sipa.trazabilidadWOS;2025-01-12
Files
Collections
Artículos de revistas