多策略模式下RRT算法的优化  

Improvement of the RRT Algorithm in Multi-Strategy

作　　者：笪晨 宋天麟[1] 施维 DA Chen;SONG Tian-lin;SHI Wei(College of Applied Technology,Soochow University,Kunshan 215300,China)

机构地区：[1]苏州大学应用技术学院,昆山215300

出　　处：《组合机床与自动化加工技术》2022年第12期128-131,135,共5页Modular Machine Tool & Automatic Manufacturing Technique

基　　金：2021年江苏省大学生创新创业训练计划资助项目(202113984010Y)。

摘　　要：快速扩展随机树算法(RRT)在导航领域得到了广泛的使用,但是仍然存在采样点随机性强、方向性弱、算法规划效率低等问题。在面对复杂环境时,算法不稳定且路径重复性低。针对这种情况,提出了一种多策略模式下改进的RRT算法(以下简称为M-RRT),能够在复杂环境中提高路径寻优的稳定性和效率。首先对地图进行预处理保证最优性,接着模拟植物生长和光线反射定律提供引导点,然后依据评价函数设定动态步长,最后结合剪枝优化与曲线拟合的方法优化路径。实验证明M-RRT算法比Dijkstra算法路径长度减少了6%,比RRT算法时间减少了53%,在3000次迭代和100次的实验下导航全部成功且路径长度标准差小于2%。利用图像预处理、光线反射和植物生长的方法能够弥补RRT算法在复杂、大面积地图导航中存在的不足。Rapidly-exploring random trees(RRT)has been widely used in the field of navigation,but there are still some problems,such as strong randomness,weak directionality and low efficiency.This algorithm is unstable and the path repeatability is low when facing the complex environment.In view of this situation,an improved RRT algorithm in multiple strategy mode(M-RRT)is proposed,which can improve the stability and efficiency of path optimization in complex environment.Firstly,preprocess the map to ensure the optimality of this map,then simulate the plant growth and light reflection law to provide the guidance points,next set the dynamic step according to the evaluation function,and finally combine the methods of pruning optimization and curve fitting to reduce the path length.Experiments show that the path length of the M-RRT algorithm is reduced by 6%compared with the Dijkstra algorithm,the time is reduced by 53%compared with the RRT algorithm.The navigation is successful under 3000 iterations and 100 experiments,the standard deviation of the path length is less than 2%.The methods of image preprocessing,light reflection and plant growth are used to make up for the shortcomings of RRT algorithm in complex and large-area map navigation.

关 键 词：路径规划 模拟植物生长 RRT算法 多策略融合 路径优化 

分 类 号：TH165[机械工程—机械制造及自动化] TG659[金属学及工艺—金属切削加工及机床]