Theoretical Study on Multi-objective Heuristic Search

Shawn Skyler; Shahaf Shperberg; Dor Atzmon; Ariel Felner; Oren Salzman; Shao-Hung Chan; Han Zhang; Sven Koenig

IJCAI 2024poster0 citations

Theoretical Study on Multi-objective Heuristic Search

Shawn Skyler, Shahaf Shperberg, Dor Atzmon, Ariel Felner, Oren Salzman, Shao-Hung Chan, Han Zhang, Sven Koenig

Abstract

This paper provides a theoretical study on Multi-Objective Heuristic Search. We first classify states in the state space into must-expand, maybe-expand, and never-expand states and then transfer these definitions to nodes in the search tree. We then formalize a framework that generalizes A* to Multi-Objective Search. We study different ways to order nodes under this framework and their relation to traditional tie-breaking policies and provide theoretical findings. Finally, we study and empirically compare different ordering functions.

Search: S: Heuristic searchSearch: S: OtherSearch: General

BibTeX

@inproceedings{ijcai2024p776,
  title     = {Theoretical Study on Multi-objective Heuristic Search},
  author    = {Skyler, Shawn and Shperberg, Shahaf and Atzmon, Dor and Felner, Ariel and Salzman, Oren and Chan, Shao-Hung and Zhang, Han and Koenig, Sven and Yeoh, William and Hernandez Ulloa, Carlos},
  booktitle = {Proceedings of the Thirty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-24}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Kate Larson},
  pages     = {7021--7028},
  year      = {2024},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2024/776},
  url       = {https://doi.org/10.24963/ijcai.2024/776},
}