Heuristic-Search Approaches for the Multi-Objective Shortest-Path Problem: Progress and Research Opportunities

Oren Salzman, Ariel Felner, Carlos Hernandez, Han Zhang, Shao-Hung Chan and Sven Koenig.
International Joint Conference on Artificial Intelligence (IJCAI), pages 6759-6768, 2023.
[bibtex] [pdf] [publisher]

@inproceedings{SalzmanIJCAI23,
    author    = {Oren Salzman and Ariel Felner and Carlos Hernandez and Han Zhang and Shao-Hung Chan and Sven Koenig},
    title     = {Heuristic-Search Approaches for the Multi-Objective Shortest-Path Problem: Progress and Research Opportunities},
    booktitle = {Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)},
    pages     = {6759--6768},
    year      = {2023}
}

Abstract

In the multi-objective shortest-path problem we are interested in computing a path, or a set of paths that simultaneously balance multiple cost functions. This problem is important for a diverse range of applications such as transporting hazardous materials considering travel distance and risk. This family of problems is not new with results dating back to the 1970’s. Nevertheless, the significant progress made in the field of heuristic search resulted in a new and growing interest in the subfield of multi-objective search. Consequently, in this paper we review the fundamental problems and techniques common to most algorithms and provide a general overview of the field. We then continue to describe recent work with an emphasis on new challenges that emerged and the resulting research opportunities.