Bounded-Cost Bi-Objective Heuristic Search


  • 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



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


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.