Parallelizing Multi-objective A* Search (Extended Abstract)

Abstract

The Multi-objective Shortest Path (MOSP) problem 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* have demonstrated superior performance in solving difficult MOSP instances. This paper proposes a novel parallel multi-objective search framework that can accelerate recent A*-based solutions by several factors.