用图融合方法让无人机路径规划扩展到1万点,效果优于现有技术。
Enhancing Large-scale UAV Route Planing with Global and Local Features via Reinforcement Graph Fusion
- 通过三角剖分提取全局特征子图,再融合局部解
- 在1万点规模下仍保持高质量解,超越当前最优方法
- 无需训练即可兼容多种求解器,适合实际应用
尽管无人机路径规划(UAVRP)在精度、速度和并行性方面取得显著进展,但现有求解器在处理大规模实例时仍面临扩展性挑战。本文提出一种通用框架,使现有UAVRP求解器可稳健扩展至最多10,000个点的规模,使用标准测试集验证。该问题本质上是大规模TSP问题。框架包含三步:首先利用Delaunay三角剖分从大实例中提取保留全局特征的子图;其次嵌入TSP求解器获取子结果并进行图融合;最后采用可定制的解码策略生成高质量路径,并引入热图预热过程。为验证灵活性,我们集成两种代表性TSP求解器,在大规模TSP基准数据集上与现有算法对比。结果明确表明,本框架能高效扩展现有求解器处理大规模实例,且持续优于当前最先进方法。由于无需额外训练或微调,该框架通用性强,有望推动端到端UAVRP求解器研究,促进更多方法应用于真实场景。
原文摘要 · Abstract (English)
Numerous remarkable advancements have been made in accuracy, speed, and parallelism for solving the Unmanned Aerial Vehicle Route Planing (UAVRP). However, existing UAVRP solvers face challenges when attempting to scale effectively and efficiently for larger instances. In this paper, we present a generalization framework that enables current UAVRP solvers to robustly extend their capabilities to larger instances, accommodating up to 10,000 points, using widely recognized test sets. The UAVRP under a large number of patrol points is a typical large-scale TSP problem.Our proposed framework comprises three distinct steps. Firstly, we employ Delaunay triangulation to extract subgraphs from large instances while preserving global features. Secondly, we utilize an embedded TSP solver to obtain sub-results, followed by graph fusion. Finally, we implement a decoding strategy customizable to the user's requirements, resulting in high-quality solutions, complemented by a warming-up process for the heatmap. To demonstrate the flexibility of our approach, we integrate two representative TSP solvers into our framework and conduct a comprehensive comparative analysis against existing algorithms using large TSP benchmark datasets. The results unequivocally demonstrate that our framework efficiently scales existing TSP solvers to handle large instances and consistently outperforms state-of-the-art (SOTA) methods. Furthermore, since our proposed framework does not necessitate additional training or fine-tuning, we believe that its generality can significantly advance research on end-to-end UAVRP solvers, enabling the application of a broader range of methods to real-world scenarios.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。