Bi-Objective Search with Bi-directional A* (Extended Abstract)

Authors

  • Saman Ahmadi Department of Data Science and Artificial Intelligence, Monash University, Australia CSIRO Data61, Australia
  • Guido Tack Department of Data Science and Artificial Intelligence, Monash University, Australia
  • Daniel D. Harabor Department of Data Science and Artificial Intelligence, Monash University, Australia
  • Philip Kilby CSIRO Data61, Australia

DOI:

https://doi.org/10.1609/socs.v12i1.18563

Keywords:

Analysis Of Search Algorithms, Bounding And Pruning Techniques

Abstract

Bi-objective search is a problem of finding a set of optimal solutions in a two-dimensional domain. This study proposes several enhancements to the state-of-the-art bi-objective search with A* and develops its bi-directional variant. Our experimental results on benchmark instances show that our enhanced algorithm is on average five times faster than the state of the art bi-objective search algorithms.

Downloads

Published

2021-07-22