Author name cluster

Luis Suazo

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

2 author rows

AIJ Journal 2023 Journal Article

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

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

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. 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.

Details DOI

SoCS Conference 2020 Conference Paper

A Simple and Fast Bi-Objective Search Algorithm

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

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-ﬁrst 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 ﬁnd 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 efﬁciently, requiring at least a full iteration over the Open list per check. In this paper, we present the ﬁrst multi-objective algorithm that performs these checks efﬁciently. 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.

Details

ICAPS Conference 2020 Conference Paper

A Simple and Fast Bi-Objective Search Algorithm

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

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.

Details