用新方法让无人机在城市飞行时更快更安全地规划路径。
Learning-accelerated A* Search for Risk-aware Path Planning
- 给A*算法增加安全维度，解决有风险约束的最短路径问题。
- 用Transformer网络设计智能启发式函数，提速超10倍且路径更优。
- 适合无人机、自动驾驶等需要实时避险的高安全性场景。
自主无人机在城市环境中的飞行安全至关重要。在人口密集区域，路径规划必须考虑风险因素，以生成有效且安全的航迹，即风险感知路径规划。该问题可建模为受限最短路径（CSP）问题，旨在找到满足特定安全阈值的最短路径。然而，CSP属于NP难问题，计算成本极高。尽管传统方法能精确求解，但速度极慢。本文提出一种改进的A*算法（称为ASD A*），通过引入额外的安全维度，使A*能够处理CSP问题。此外，我们开发了一种基于Transformer神经网络的定制学习型启发式函数，显著降低计算负担并提升ASD A*的性能。所提方法在随机与真实场景仿真中均得到充分验证。
原文摘要 · Abstract (English)
Safety is a critical concern for urban flights of autonomous Unmanned Aerial Vehicles. In populated environments, risk should be accounted for to produce an effective and safe path, known as risk-aware path planning. Risk-aware path planning can be modeled as a Constrained Shortest Path (CSP) problem, aiming to identify the shortest possible route that adheres to specified safety thresholds. CSP is NP-hard and poses significant computational challenges. Although many traditional methods can solve it accurately, all of them are very slow. Our method introduces an additional safety dimension to the traditional A* (called ASD A*), enabling A* to handle CSP. Furthermore, we develop a custom learning-based heuristic using transformer-based neural networks, which significantly reduces the computational load and improves the performance of the ASD A* algorithm. The proposed method is well-validated with both random and realistic simulation scenarios.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。