基于改进RRT^(*)算法的城市低空路径规划方法研究

Research on Urban Low-altitude Path Planning Method based on Improved RRT^(*)Algorithm

随着无人机监测、巡查和测绘等低空技术得到广泛应用,低空长距离空中路径规划成为低空航空器应用面临的一个挑战。而传统快速扩展随机树(Rapidly-Exploring Random Trees/RRT)及其改进算法在大范围长距离低空三维空间下面临计算效率慢的问题,对此,本文提出一种带有R树空间索引的双向启发式RRT^(*)算法,该算法在双向RRT^(*)算法基础上为随机采样过程设置了启发函数,使得在面对狭小城市障碍物之间空隙时,能够避免局部最小值情况的出现。在此基础上为城市障碍物建立R树空间索引,减少了海量障碍物情况下碰撞检测的时间,提高了低空长距离空中路径规划效率。此外,为了得到更加符合无人机运动规律的路径,提高算法的实用性,在采样过程中设置转弯阈值控制转弯角度,并且对规划结果路径使用3次B-spline函数进行路径平滑。最后在武汉市三维城市场景中,利用武汉市建筑物数据进行了实验,实验证明相比已有算法,本文提出的带有R树空间索引的双向启发式RRT^(*)算法相比较RRT算法和双向RRT^(*)算法在500 m、2000 m、10000 m不同距离下规划时间均降低了90%以上;采样次数相比RRT算法在不同距离下分别降低了51.6%、75%、86.7%,相比双向RRT^(*)算法在不同距离下分别降低了20%、24.7%、57.3%;转弯次数相比RRT算法在不同距离下分别降低了77.3%、73.5%、78.3%,相比双向RRT^(*)算法在不同距离下分别降低了37.5%、30.8%、16.8%;同时带有R树空间索引的双向启发式RRT^(*)算法得到的结果路径长度相比其他2种算法也有缩短。该算法应用于低空长距离空中路径规划能够有效提高计算效率,降低规划时间,减少采样次数,缩短结果路径,减少转弯次数,丰富无人机的应用场景。

With the wide application of Unmanned Aerial Vehicle(UAV)monitoring,inspection,mapping,and other low-altitude technologies,low-altitude and long-distance aerial path planning has become a great challenge for low-altitude aircraft applications.However,the traditional Rapidly Exploring Random Trees(RRT)and its improved algorithm face the problem of slow computational efficiency in a large-range,long-distance,lowelevation three-dimensional space.Therefore,a bidirectional heuristic RRT^(*)algorithm with R-tree spatial index is proposed in this paper.Based on the bidirectional RRT^(*)algorithm,the heuristic function is set for random sampling process to avoid the occurrence of local minimum when facing the gap between small urban obstacles.On this basis,R tree spatial index is established for urban obstacles,which reduces the time of collision detection in the case of massive obstacles and improves the efficiency of low altitude and long distance air path planning.In addition,in order to obtain a path more in line with the motion law of unmanned aerial vehicle and improve the practicability of the algorithm,a turning threshold is set in the sampling process to control the turning angle to prevent it from being too large,and the planning result path is smoothed by using the cubic B-spline function.Finally,in the three-dimensional city scene of Wuhan,the experiment is carried out using the 3 D building data of Wuhan.The experiment results show that,compared with RRT algorithm and bidirectional RRT^(*)algorithm,the planning time of the two-way heuristic RRT^(*)algorithm with R-tree spatial index is reduced by more than 90%at different distances,i.e.,500 m,2000 m,and 10000 m.Compared to RRT algorithm,the sampling time is reduced by 51.6%,75%,and 86.7%,respectively,at different distances;and compared to bidirectional RRT^(*)algorithm,the sampling time is reduced by 20%,24.7%,and 57.3%,respectively,at different distances.Compared to RRT algorithm,the turning time is reduced by 77.3%,73.5%,and 78.3%,respectively,at different distances;and compared to bidirectional RRT^(*)algorithm,it is reduced by 37.5%,30.8%,and 16.8%,respectively,at different distances.The result path length of the bidirectional heuristic RRT^(*)algorithm with R-tree spatial index is also shorter than that of the other two algorithms.Our algorithm applied to low-altitude long-distance air path planning can effectively improve the calculation efficiency and reduce the planning time,reduce sampling times,shorten the result path,reduce the swerve times,and enrich the application scenarios of unmanned aerial vehicle.