首页|高密度场景下基于改进A*算法的无人机路径规划

高密度场景下基于改进A*算法的无人机路径规划

扫码查看
针对无人机在高密度障碍物的城市环境飞行中路径规划实时性难以满足的问题,在A*算法基础上结合跳点搜索(Jump Point Search,JPS)策略,提出一种Jump A*(JA*)算法.将A*算法进行三维扩展,并提出了一种三维对角距离精确表示了实际路径代价,缩短了搜索时间.在二维JPS策略的基础上拓展得到了三维JPS策略,代替了A*算法中的几何邻居扩展,大大减少了扩展结点数.对障碍物密度0.1~0.4的复杂三维栅格地图进行了路径规划仿真.仿真结果表明,JA*算法相较于A*算法,在高密度多障碍物的近地城市环境下,路径长度几乎不变,评估节点数大幅度减小,搜索速度具有显著提升.
Unmanned Aerial Vehicle Path Planning Based on Improved A*Algorithm in High-density Scenarios
In response to the challenge of achieving real-time path planning for unmanned aerial vehicles flying in High-density ur-ban environments with numerous obstacles,this paper introduces a novel algorithm known as Jump A*(JA*).Building upon A*algo-rithm and incorporating Jump Point Search(JPS)strategy,JA* algorithm is proposed.Initially,we extend A* algorithm into three di-mensions and introduce a three-dimensional diagonal distance measurement that precisely represents actual path cost,thereby reducing search time.Subsequently,building upon the two-dimensional Jump Point Search strategy,we extend it to three dimensions,resulting in a 3D-JPS strategy.This 3D-JPS strategy replaces the geometric neighbor expansion used in A* algorithm and significantly reduces the number of expanded nodes.We conducted path planning simulations on complex three-dimensional grid maps with obstacle densities ranging from 0.1 to 0.4.Simulation results indicate that,in comparison to A* algorithm,JA* algorithm exhibits almost iden-tical path lengths while significantly reducing the number of evaluated nodes.This substantial reduction in node expansion leads to a notable improvement in search speed,particularly in near-ground urban environments characterized by High-density obstacles.

path planningJPSA* algorithm3D grid maphigh-density obstacles

赵烈海、李大鹏

展开 >

南京邮电大学通信与信息工程学院,江苏南京 210003

路径规划 跳点搜索 A*算法 三维栅格地图 高密度障碍物

2024

无线电通信技术
中国电子科技集团公司第五十四研究所

无线电通信技术

北大核心
影响因子:0.745
ISSN:1003-3114
年,卷(期):2024.50(4)