基于动态视场的深度启发改进3维A*算法

Deep Heuristic-Improved 3D A* Algorithm Based on Dynamic Field-of-View

  • 摘要: 针对A*算法在山地场景下因启发函数建模不准确导致搜索效率低的问题, 提出基于动态视场的深度启发改进3维A*算法。该改进A*算法以一种深度启发网络构建启发函数模型, 并从泛化能力和建模精度两方面优化模型的性能。在提高泛化能力方面, 设计一种局部动态视场模型, 增强深度启发网络对关键地形信息的抓取能力, 进而使其适应各种不同地形场景; 在提高建模精度方面, 设计一种基于距离权重因子的损失函数模型, 缩小3维场景下深度启发网络对远距离路径的代价估计偏差。仿真实验表明, 所提出的算法相比于现有基于深度学习法改进的A*算法, 在3维场景下的路径代价预测精度平均提高45.2%, 平均搜索效率提升12.8%, 平均路径质量提升1.2%;对比现有基于经验建模法改进的A*算法, 搜索效率亦有明显提高。

     

    Abstract: In order to solve the problem of low search efficiency of A^\ast algorithm in mountainous terrain scenarios due to inaccurate heuristic function modeling, a deep heuristic-improved 3D A^\ast algorithm based on dynamic field-of-view is proposed. In the improved A^\ast algorithm, a deep heuristic network is used to construct heuristic function model, and further the performance of the model is optimized in terms of generalization ability and modeling accuracy. In order to improve the generalization ability, a local dynamic field-of-view model is designed, which enhances the ability of deep heuristic network to capture the key terrain information, and then makes it adapt to various terrain scenarios. In order to improve the modeling accuracy, a loss function model based on the distance weight factor is designed to reduce the cost estimation deviation of the deep heuristic network for the long-distance paths in 3D scenarios. Simulation experiments show that compared with the existing deep learning-based improved A^\ast algorithm, the proposed algorithm can improve the prediction accuracy of path cost by 45.2% on average, the average search efficiency by 12.8%, and the average path quality by 1.2% in 3D scenarios. Compared with the existing improved A^\ast algorithm based on empirical modeling, the search efficiency is also significantly improved.

     

/

返回文章
返回