基于改进A*算法的无人机三维空间避障路径规划

Obstacle Avoidance Path Planning of UAV in 3D Space based on Improved A* Algorithm

摘要:

无人机在有障碍物的三维空间环境中飞行,采用常规A*算法进行避障航线的规划存在搜索节点多、搜索区域大、搜索时间长、搜索效率低、生成的航线拐角多且含有大量非必要冗余航点、没有考虑无人机自身体积与尺寸而引发的飞行中与障碍物边界碰撞的航线不安全等问题。因此，设计一种改进A*算法,首先,考虑无人机本身体积与尺寸,提出一种消除边界碰撞事故的子节点扩展方法；其次,改进评价函数,减少往复搜索次数,缩小搜索区域面积,提高搜索效率；然后,根据Floyd思想,对生成的航线进行简化处理,消除航线中的冗余航路点,减少航线转角数量,达到简化航线并改善航线平滑度的效果；最后,非线性仿真及飞行试验表明了改进的A*算法生成的航线更加安全、高效,并使无人机的飞行连续和顺畅。

Abstract:

When a UAV flies in the space with obstacles, the traditional A* algorithm has many problems in obstacle avoidance route planning, such as many search nodes, long search time, low search efficiency, uneven path, redundant path points, many turning points, and unsafe path caused by collision without considering the volume of UAV itself. An improved A* algorithm is designed. Firstly, considering the volume of UAV, a collision free extended sub node method is proposed. Secondly, the cost-function is optimized to reduce sub interval search, save search time and improve search efficiency. Then, Floyd algorithm is introduced to simplify the path and eliminate a large number of redundant points and turning points. Finally, the path is smoothed by spline interpolation cubic function, which eliminates the inflection point of the path and improves the smoothness of the path. The simulation results show that the path generated by the improved a* algorithm is more safe and efficient, and makes the flight action of UAV more continuous and smooth.