提出并行化多目标A*搜索框架，提升复杂路径规划效率。
Parallelizing Multi-objective A* Search
- 通过不同目标顺序的并行搜索，加速多目标路径求解。
- 在特定情况下将问题维度降为1，显著减少计算开销。
- 适合需要高效求解多目标最短路径的系统设计者参考。
多目标最短路径（MOSP）问题是一类经典的网络优化问题，旨在寻找图中两点间所有帕累托最优路径。近期基于A*的多目标搜索（MOA*）方法在解决复杂MOSP实例方面表现出色。本文提出一种新型搜索框架，可高效实现MOA*在不同目标顺序下的并行化。该框架引入独特的上界策略，在某些情况下能将问题维度降至1，从而降低计算复杂度。实验表明，所提框架可显著提升现有基于A*的解决方案性能，加速比与问题维度成正比。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。