Computer Engineering and Applications ›› 2020, Vol. 56 ›› Issue (16): 118-123.DOI: 10.3778/j.issn.1002-8331.1905-0442

Previous Articles     Next Articles

Method of PRM Path Optimization Based on Key Nodes and Smooth Processing

WEI Nianwei, JIANG Yuanyuan, LIU Yanbin, XIN Yuanfang, HONG Yan   

  1. College of Electrical and Information Engineering, Anhui University of Science and Technology, Huainan, Anhui 232001, China
  • Online:2020-08-15 Published:2020-08-11



  1. 安徽理工大学 电气与信息工程学院,安徽 淮南 232001


Aiming at the problem that the excessive path inflection nodes and steep partial turning angles of Probability Roadmap(PRM) algorithm used in mobile robot path planning, a PRM path optimization method is proposed. The PRM algorithm uses random sampling when constructing the path network graph, the path is not optimal and there are too many nodes in the path. Douglas-Peucker(D-P) algorithm is used to extract the key nodes in the initial path nodes generated by PRM. Then the key nodes are instead of the original initial path nodes in order to reduce the number of inflection nodes in the path. Moreover, using Clothoid curve to smooth the new path generated by key nodes. Simulation results show that the optimization method can reduce the number of path nodes and make the path smoother.

Key words: Probabilistic Roadmap(PRM), key nodes, Clothoid curve, path optimization


针对移动机器人路径规划采用的概率路图(Probabilistic Roadmap,PRM)算法存在路径拐点过多以及部分转角过陡的问题,提出一种PRM路径优化方法。PRM算法在构建路径网络图时采用随机采样,路径并非最优,路径节点过多,使用Douglas-Peucker(D-P)算法提取PRM算法生成初始路径节点中的关键节点,用关键节点代替原来的初始路径节点,以减少路径中拐点的个数。使用Clothoid曲线对新生成的路径进行平滑处理,达到路径优化的目的。仿真结果表明该优化方法能减少路径节点的个数,并使路径更加平滑。

关键词: 概率路图(PRM), 关键节点, Clothoid曲线, 路径优化