Parallelizing Multi-Objective A* Search (Extended Abstract)

Ahmadi, Saman; Sturtevant, Nathan R.; Raith, Andrea; Harabor, Daniel; Jalili, Mahdi

doi:10.24963/ijcai.2026/915

Parallelizing Multi-Objective A* Search (Extended Abstract)

Saman Ahmadi, Nathan R. Sturtevant, Andrea Raith, Daniel Harabor, Mahdi Jalili

Download BibTeX Cite

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence. Sister Conferences Best Papers. Pages 8215-8220.

https://doi.org/10.24963/ijcai.2026/915

Keywords

Search: Heuristic search
AI: Planning and Scheduling

Abstract

The Multi-objective Shortest Path (MOSP) problem is a classic network optimization problem that aims to find all Pareto-optimal paths between two points in a graph with multiple edge costs. Recent studies on multi-objective search with A* (MOA*) have demonstrated strong performance on challenging MOSP instances. This paper presents a novel search framework that enables efficient parallelization of MOA* through different objective orderings and a unique upper-bounding strategy that, in certain cases, allows the problem dimensionality to be reduced to one. Results demonstrate that the proposed framework can significantly improve the performance of MOA*, with speedups increasing proportionally to the number of objectives.

Saman Ahmadi, Nathan R. Sturtevant, Andrea Raith, Daniel Harabor, and Mahdi Jalili. 2026. Parallelizing Multi-Objective A* Search (Extended Abstract). In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26. IJCAI, 8215–8220. https://doi.org/10.24963/ijcai.2026/915

@inproceedings{ijcai2026p915,
  title     = {Parallelizing Multi-Objective A* Search (Extended Abstract)},
  author    = {Ahmadi, Saman and Sturtevant, Nathan R. and Raith, Andrea and Harabor, Daniel and Jalili, Mahdi},
  booktitle = {Proceedings of the Thirty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-26}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Diego Calvanese},
  pages     = {8215--8220},
  year      = {2026},
  month     = {8},
  note      = {Sister Conferences Best Papers},
  doi       = {10.24963/ijcai.2026/915},
  url       = {https://doi.org/10.24963/ijcai.2026/915},
}

TY  - CPAPER
TI  - Parallelizing Multi-Objective A* Search (Extended Abstract)
AU  - Ahmadi, Saman
AU  - Sturtevant, Nathan R.
AU  - Raith, Andrea
AU  - Harabor, Daniel
AU  - Jalili, Mahdi
T2  - Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2026
SP  - 8215
EP  - 8220
DO  - 10.24963/ijcai.2026/915
UR  - https://doi.org/10.24963/ijcai.2026/915
ER  -