Bounded-Cost Bi-Objective Heuristic Search

Authors

  • Shawn Skyler Ben-Gurion University
  • Dor Atzmon Ben-Gurion University
  • Ariel Felner Ben-Gurion University
  • Oren Salzman Technion
  • Han Zhang University of Southern California
  • Sven Koenig University of Southern California
  • William Yeoh Washington University in St. Louis
  • Carlos Hernández Ulloa Universidad Andrés Bello

DOI:

https://doi.org/10.1609/socs.v15i1.21774

Keywords:

Problem Solving Using Search, Combinatorial Optimization, Analysis Of Search Algorithms, Bounding And Pruning Techniques

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.

Downloads

Published

2022-07-17