Parallelizing Multi-objective A* Search
Open Access
- 16 September 2025
- journal article
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the International Conference on Automated Planning and Scheduling
- Vol. 35 (1) , 131-139
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 superior performance in solving difficult MOSP instances. This paper presents a novel search framework that allows efficient parallelization of MOA* with different objective orders. The framework incorporates a unique upper-bounding strategy that helps the search reduce the problem's dimensionality to one in certain cases. Experimental results demonstrate that the proposed framework can enhance the performance of recent A*-based solutions, with the speed-up proportional to the problem dimension.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Enhanced methods for the weight constrained shortest path problemNetworks, 2024
- Multi-objective routing and scheduling for airport ground movementTransportation Research Part C: Emerging Technologies, 2020
- Dimensionality reduction in multiobjective shortest path searchComputers & Operations Research, 2015
- An Interactive Algorithm for Multi-objective Route PlanningJournal of Optimization Theory and Applications, 2011
- A Critical Assessment of Benchmark Comparison in PlanningJournal of Artificial Intelligence Research, 2002
- A Formal Basis for the Heuristic Determination of Minimum Cost PathsIEEE Transactions on Systems Science and Cybernetics, 1968