Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (10): 2865-2869.DOI: 10.11772/j.issn.1001-9081.2019030508

• Artificial intelligence • Previous Articles     Next Articles

Narrow channel path planning based on bidirectional rapidly-exploring random tree

FU Jiupeng, ZENG Guohui, HUANG Bo, FANG Zhijun   

  1. School of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China
  • Received:2019-03-27 Revised:2019-05-16 Online:2019-10-14 Published:2019-10-10
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61603242), the Project of Jiangxi Province Economic Crime Investigation and Collaborative Innovation Center of Prevention and Control Technology (JXJZXTCX-030).

基于双向快速探索随机树的狭窄通道路径规划

付久鹏, 曾国辉, 黄勃, 方志军   

  1. 上海工程技术大学 电子电气工程学院, 上海 201620
  • 通讯作者: 曾国辉
  • 作者简介:付久鹏(1994-),男,江苏扬州人,硕士研究生,主要研究方向:机器人路径规划、智能控制;曾国辉(1975-),男,江西乐安人,副教授,博士,主要研究方向:机器人控制、电力电子及其控制;黄勃(1985-),男,湖北武汉人,讲师,博士,主要研究方向:需求工程、软件工程、人工智能;方志军(1971-),男,江西鄱阳人,教授,博士,主要研究方向:模式识别、智能计算、视频分析。
  • 基金资助:
    国家自然科学基金资助项目(61603242);江西省经济犯罪侦查与防控技术协同创新中心开放课题(JXJZXTCX-030)。

Abstract: In the process of mobile robot path planning, it is difficult for the Rapidly-exploration Random Tree (RRT) algorithm to sample narrow channels. In order to deal with this problem, an improved bridge detection algorithm was proposed, which is dedicated to narrow channel sampling. Firstly, the environment map was pre-processed and the obstacle edge coordinate set was extracted as the sampling space for the bridge detection algorithm, thus avoiding a large number of invalid sampling points and making the sampling points distribution of the narrow channel more rational. Secondly, the process for bridge endpoint construction was improved, and the operation efficiency of the bridge detection algorithm was increased. Finally, a slight variant Connect algorithm was used to expand the narrow channel sample points rapidly. For the narrow channel environment map in the experiment, the improved algorithm has the success rate increased from 68% to 92% compared with the original RRT-Connect algorithm. Experimental results show that the proposed algorithm can sample the narrow channel well and improve the efficiency of path planning.

Key words: path planning, Rapidly-exploring Random Tree (RRT), narrow channel, bridge detection algorithm, obstacle edge detection

摘要: 针对移动机器人路径规划过程中基于快速探索随机树(RRT)算法难以对窄道进行采样的问题,提出一种专门用于狭窄通道路径规划的改进桥梁检测算法。首先对环境地图预处理并提取出障碍物边缘节点集合作为桥梁检测算法的采样空间,从而避免了大量无效采样点,并使窄道样本点分布更加合理化;其次改进了桥梁端点的构建过程,提高了桥梁检测算法的运算效率;最后使用一种轻微变异Connect算法快速扩展窄道样本点。对于实验中的窄道环境地图,与原始RRT-Connect算法相比较,所提改进算法的路径探索成功率由68%提高到92%。实验结果表明,该算法能够较好地完成窄道样本点采样并有效地提高路径规划效率。

关键词: 路径规划, 快速探索随机树, 狭窄通道, 桥梁检测算法, 障碍物边缘检测

CLC Number: