A simple and fast bi-objective search algorithm

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

Research output: Contribution to journalConference articlepeer-review

26 Citations (Scopus)

Abstract

Many interesting search problems can be formulated as biobjective 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 biobjective search algorithms, such as NAMOA*, NAMOA*dr, Bi-Objective Dijkstra, and Bidirectional Bi-Objective Dijkstra.

Original languageEnglish
Pages (from-to)143-151
Number of pages9
JournalProceedings International Conference on Automated Planning and Scheduling, ICAPS
Volume30
Publication statusPublished - 29 May 2020
Event30th International Conference on Automated Planning and Scheduling, ICAPS 2020 - Nancy, France
Duration: 26 Oct 202030 Oct 2020

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computer Science Applications
  • Information Systems and Management

Fingerprint

Dive into the research topics of 'A simple and fast bi-objective search algorithm'. Together they form a unique fingerprint.

Cite this