---
title: "Parallelizing Multi-Objective A* Search (Extended Abstract)"
authors:
  - "Saman Ahmadi"
  - "Nathan R. Sturtevant"
  - "Andrea Raith"
  - "Daniel Harabor"
  - "Mahdi Jalili"
doi: "10.24963/ijcai.2026/915"
url: "https://ijcai.org/proceedings/2026/915"
pdf: "https://ijcai.org/proceedings/2026/0915.pdf"
venue: "Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence"
year: 2026
pages: "8215-8220"
track: "Sister Conferences Best Papers"
keywords:
  - "Search: Heuristic search"
  - "AI: Planning and Scheduling"
---

# Parallelizing Multi-Objective A* Search (Extended Abstract)

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

*Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence*, pages 8215-8220. DOI: [10.24963/ijcai.2026/915](https://doi.org/10.24963/ijcai.2026/915)

## 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.