无人机航路规划中的变步长A*算法

摘要

To realize autonomous route planning of UAVs under different conditions, a kind of A * algorithm with changeable steps is presented. The points to be extended during iteration are the point lattice with different degrees and different steps in searching area, which can guarantee that each searching be carried out in a large area with enough graph distinguish precision. Then, based on the idea of Sparse A * Search (SAS) ,an improved method with less computational complexity and higher speed is provided to the extending method of each step; and based on the idea of Dynamic A* Search ( D * Search), an improved method which can be applied to real-time route planning is provided. Simulation results show that the algorithm can successfully realize battlefield penetration route planning in complicated battlefield environment and realize real-time route planning in unknown environment by setting parameters properly.%为了实现无人机在不同条件下的自主航路规划,提出一种变步长的A*方法.此时,每步迭代的可拓展点为搜索区域内不同搜索角度、不同拓展步长的点阵.这样保证了每次搜索能在一个较大的区域进行,并能保证每次搜索对地图的分辨精度.然后,依据稀疏A*方法(SAS)的思想,对单步迭代的拓展方法给出了减少运算量、加快运算速度的改进方案;依据动态A*方法(D*)的思想,给出了应用于实时航路规划的改进方案.仿真结果表明,通过适当配置参数,算法可以成功地实现复杂战场环境下的战区穿越突防航路规划以及未知环境下的在线实时航路规划.