Computer Engineering and Applications ›› 2020, Vol. 56 ›› Issue (19): 273-278.DOI: 10.3778/j.issn.1002-8331.1812-0298

Previous Articles    

Optimal Path Planning of RRT in Multi-intersection Environment

LONG Jianquan, LIANG Yanyang   

  1. School of Information Engineering, Southwest University of Science and Technology, Mianyang, Sichuan 621010, China
  • Online:2020-10-01 Published:2020-09-29

多路口环境下RRT的最优路径规划

龙建全,梁艳阳   

  1. 西南科技大学 信息工程学院,四川 绵阳 621010

Abstract:

In multi-intersection environment, RRT has the problems of long search time, wide search range and uneven path. A hybrid strategy based on landmark guidance and increasing sampling area is proposed to guide RRT algorithm to search for targets. Firstly, the map will be preprocessed to remove the smaller obstacles, save the large obstacles as far as possible, and get the preprocessed map. In the new map, the intersection area is set up withlandmark, and the combination of visual areas of landmark should cover the whole map. Then, according to the connected areas on the new map, by searching for the optimal combination of landmark from the starting point to the end point, a moving growth sampling area is constructed between the two adjacent landmark to guide the RRT algorithm to search for the target quickly. Finally, the RRT algorithm is pruned by tree branches and secondary Bezier curve fitting generates smooth path. The effectiveness, rationality and correctness of the algorithm are verified by simulation experiments.

Key words: Rapidly exploring Random Tree(RRT), landmark guidance, growing sampling area, quick search, Bezier curve

摘要:

针对于多路口环境下RRT的搜索时间长,搜索范围广和路径不平整的问题。提出一种基于路标引导和增长采样区域的混合策略来引导RRT算法向目标搜索。将对地图做预处理,处理掉较小的障碍物,尽可能保存大障碍物,得到预处理地图;在新地图上路口区域设置路标点,路标点的可视区域的组合要覆盖整个地图,根据其在新地图上的连通区域,通过寻找出一组从起点到终点的最优路标点组合,以相邻两路标之间构建移动增长采样区域来引导RRT算法快速向目标搜索;用树枝修剪和二次贝塞尔曲线拟合生成光滑路径。通过仿真实验验证了算法的有效性、合理性和正确性。

关键词: 快速扩展随机树(RRT), 路标引导, 增长采样区域, 快速搜索, 贝塞尔曲线拟合