Bounded-Cost Bi-Objective Heuristic Search

Shawn Skyler, Dor Atzmon, Ariel Felner, Oren Salzman, Han Zhang, Sven Koenig, William Yeoh, Carlos Hernández Ulloa

Abstract

There are many settings that extend the basic shortest path search problem. In Bounded-Cost Search, we are given a constant bound and the task is to find a solution within the bound. In Bi-Objective Search, each edge is associated with two costs (objectives) and the task is to minimize both objectives. In this paper, we combine both these settings into a new setting of Bounded-Cost Bi-Objective Search. We are given two bounds, one for each objective and the task is to find a solution within these bounds. We provide a scheme for normalizing the two objectives. We then introduce several algorithms for this new setting and compare them experimentally.
BibTeX
@inproceedings{skyler2022bounded,
  author = {Shawn Skyler and Dor Atzmon and Ariel Felner and Oren Salzman and Han Zhang and Sven Koenig and William Yeoh and Carlos Hernández Ulloa},
  title = {{Bounded-Cost Bi-Objective Heuristic Search}},
  booktitle = {SOCS},
  year = {2022},
  doi = {10.1609/socs.v15i1.21774},
}

Loading related content...

Figure