摘要
针对传统RRT^(*)算法(Rapidly-Exploring Random Tree,RRT)在全局路径规划过程中存在收敛速度慢、搜索路径不平滑、内存占用多等问题,提出了一种APF-RRT^(*)(Artificial Potential Field,APF)融合搜索算法。首先,为了加快RRT^(*)算法在搜寻过程中的收敛速度,在算法中利用人工势场引导快速扩展随机树向目标点生长,在RRT^(*)算法扩展节点时加入APF的目标引力与障碍物斥力思想;其次,对融合算法在空间中的采样范围做出改进,使算法在APF产生的合力特定范围内进行采样,提高算法在空间中的搜索效率,减少无用节点的扩展;最后,对融合算法规划的路径进行平滑优化,减少不必要的路径,降低无人机实际飞行的代价。在多种不同障碍物环境下进行了对比仿真实验,融合算法相较于传统RRT和RRT^(*)算法搜索效率显著提升,路径代价与平滑度得到进一步优化,且降低了随机树无用节点的扩展,节点的利用率得到大幅提升。
Aiming at the problems of slow convergence speed,unsmooth search path and high memory consumption in the global path planning process of traditional RRT^(*),an APF-RRT^(*)fusion search algorithm was proposed.Firstly,in order to accelerate the convergence speed of RRT^(*)algorithm in the search process,the artificial potential field was used to guide the fast expanding random tree to grow to the target point,and the idea of target gravity and obstacle repulsion of APF was added when RRT^(*)algorithm expanded nodes;Secondly,the sampling range of the fusion algorithm in space was improved to make the algorithm sample in the specific range of the resultant force generated by APF,so as to improve the search efficiency of the algorithm in space and reduce the expansion of useless nodes;Finally,the path planned by the fusion algorithm was smoothed to reduce the unnecessary path and the actual flight cost of UAV.Compared with the traditional RRT and RRT^(*)algorithms,the fusion algorithm improves the search efficiency significantly,optimizes the path cost and smoothness,reduces the expansion of useless nodes in the random tree,and greatly improves the utilization of nodes.
作者
徐小强
宋子奇
冒燕
郭利荣
XU Xiao-qiang;SONG Zi-qi;MAO Yan;GUO Li-rong(School of Automation,Wuhan University of Technology,Wuhan 430070,China;PLA NO 93993,Lanzhou 730300,China)
出处
《武汉理工大学学报》
CAS
2021年第9期72-78,共7页
Journal of Wuhan University of Technology
基金
军内计划科研项目(XK2019009)
中央高校基本科研业务费专项资金(2019IVA045)
山东省自然科学基金(ZR2020MF111)。
关键词
快速搜索随机树算法
人工势场法
全局路径规划
无人机
Rapidly-Exploring Random Tree(RRT)
artificial potential field method(APF)
global path planning
unmanned aerial vehicle(UAV)
