AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / SOCS-22 Volume 15

Bounded-Cost Bi-Objective Heuristic Search

Authors

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

Ben-Gurion University,Ben-Gurion University,Ben-Gurion University,Technion,University of Southern California,University of Southern California,Washington University in St. Louis,Universidad Andrés Bello


Proceedings:

SOCS-22 Volume 15

Volume

Issue:

Vol. 15 No. 1 (2022): Fifteenth International Symposium on Combinatorial Search

Track:

Short Papers

Downloads:

Download PDF

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.

DOI:

10.1609/socs.v15i1.21774


SOCS

Vol. 15 No. 1 (2022): Fifteenth International Symposium on Combinatorial Search



Published by , . All rights reserved.


Copyright ,