基于改进A*算法的城市物流无人机三维路径规划

Three-dimensional Path Planning of Urban Logistics UAVs

针对无人机在城市物流应用中的路径规划时,需要耗费大量时间和计算资源寻找最优解的问题,提出一种改进A*算法。首先,采用栅格法建立三维环境模型,结合无人机性能构建多约束物流无人机路径规划模型,将路径规划问题转化为在三维空间中的最优路径搜索问题;其次,改进后的A*算法引入了动态步长的概念、Bresenham算法思想以及改进的启发式函数,以提升算法的路径规划质量和效率;最后,通过引入对角线距离、欧氏距离和曼哈顿距离作为改进A*算法的启发式函数。结合所建立的三维环境模型,采用参数搜索方法来计算最优权重值,从而提出一种高效的城市物流无人机三维路径规划的优化算法。算例分析表明,改进后的A*算法相比传统A*算法和JPS算法路径规划的平均时间至少降低了24.84%,所得路径平均长度至少缩短了2.89%,平均搜索节点数量至少减少了82.81%。

In addressing the time-consuming and computationally intensive nature of finding optimal solutions for unmanned aerial vehicle(UAV) path planning in urban logistics applications,an improved A* algorithm was proposed.Firstly,a three-dimensional environmental model was established using grid-based methods,and a multi-constrained logistics UAV path planning model was constructed based on UAV performance,transforming the path planning problem into an optimal path search problem in three-dimensional space.Secondly,the improved A* algorithm incorporates the concept of dynamic step size,Bresenham algorithm principles,and an enhanced heuristic function to enhance the quality and efficiency of the algorithm's path planning.Finally,by introducing diagonal distance,Euclidean distance,and Manhattan distance as the heuristic function for the improved A* algorithm,and combining it with the established three-dimensional environmental model,a parameter search method was used to calculate the optimal weight values,thus proposing an efficient optimization algorithm for three-dimensional path planning of urban logistics UAVs.Case studies indicate that the average time for path planning using the improved A* algorithm is reduced by at least 24.84% compared to traditional A* and JPS algorithms,the average path length is shortened by at least 2.89%,and the average number of search nodes is reduced by at least 82.81%.