Parallelizing Multi-objective A* Search
This work addresses network optimization challenges for applications requiring efficient multi-objective pathfinding, representing an incremental advancement in parallel search methods.
The paper tackled the Multi-objective Shortest Path problem by developing a novel parallelization framework for MOA* search, which improved performance with speed-ups proportional to the problem dimension.
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.