结合B样条优化的UAV多区域路径规划融合算法

A Fused Algorithm for the planning of UAV Path between Multiple areas Combined with B-spline Optimization

摘要:

为解决无人机(UAV,Unmanned Aerial Vehicle)在多个目标区域之间快速找到最佳遍历路径的类旅行商问题(TSP,Travelling Salesman Problem),设计一种基于蚁群算法、A*算法以及三次B样条优化的融合规划算法；尽管蚁群算法相对其他优化算法在解决TSP问题上有较为良好的表现,但其规划路径处理时间长、生成路径转折多、路径质量和安全性较差；算法首先改进传统A*算法的节点扩展方式,快速生成两两目标区之间的局部路径,然后将蚁群算法和改进A*算法融合使用进行全局路径规划,最后结合改进三次B样条对路径进行平滑处理;基于栅格地图的仿真结果证明了该算法相比传统算法具有更好的高效性和稳定性。

Abstract:

In order to solve the TSP (Traveling Salesman Problem) of Unmanned Aerial Vehicle (UAV) which wants to quickly find the best traversal path between multiple target areas, a fusion programming algorithm based on Ant Colony Algorithm, A * algorithm and cubic B-spline optimization is designed; Although Ant Colony Algorithm has a better performance than other optimization algorithms in solving TSP, its planning path processing time is long, the generated path turns more, and the quality and security of path are poor; The algorithm firstly improves the node expansion mode of the traditional A * algorithm to quickly generate the local path between two target areas, then combines the Ant Colony Algorithm and the improved A * algorithm for global path planning, and finally smoothes the path combined with cubic B-spline; The simulation results based on grid map show that the algorithm has better efficiency and stability than the traditional algorithm.