关键节点和平滑处理的PRM路径优化方法

doi:10.3778/j.issn.1002-8331.1905-0442

计算机工程与应用 ›› 2020, Vol. 56 ›› Issue (16): 118-123.DOI: 10.3778/j.issn.1002-8331.1905-0442

关键节点和平滑处理的PRM路径优化方法

魏念巍，姜媛媛，刘延彬，辛元芳，洪炎

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

出版日期:2020-08-15 发布日期:2020-08-11

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

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

College of Electrical and Information Engineering, Anhui University of Science and Technology, Huainan, Anhui 232001, China

Online:2020-08-15 Published:2020-08-11

摘要/Abstract

摘要：

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

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

Abstract:

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

魏念巍，姜媛媛，刘延彬，辛元芳，洪炎. 关键节点和平滑处理的PRM路径优化方法[J]. 计算机工程与应用, 2020, 56(16): 118-123.

WEI Nianwei, JIANG Yuanyuan, LIU Yanbin, XIN Yuanfang, HONG Yan. Method of PRM Path Optimization Based on Key Nodes and Smooth Processing[J]. Computer Engineering and Applications, 2020, 56(16): 118-123.

[1]	王嘉月，史立. 考虑电池损耗的电动冷藏车路径及充电策略[J]. 计算机工程与应用, 2021, 57(24): 283-289.
[2]	胡小兵，陈树念，张盈斐，谷升豪. 求解多目标路径优化问题的涟漪扩散算法[J]. 计算机工程与应用, 2021, 57(23): 81-90.
[3]	熊兴隆，刘佳，李猛，马愈昭. 基于无人机-配送车联合配送的优化算法研究[J]. 计算机工程与应用, 2021, 57(19): 259-266.
[4]	张浩宇，应健锋，宋晨钰，王可可，易茂祥. 针对电路关键路径的硬件木马监测与防护[J]. 计算机工程与应用, 2020, 56(6): 73-78.
[5]	彭露，陈淮莉. 改进遗传算法下的无水港集货路径优化研究[J]. 计算机工程与应用, 2020, 56(14): 250-256.
[6]	蒋丽，王静，梁昌勇，赵树平. 基于改进蚁群算法的众包配送路径研究[J]. 计算机工程与应用, 2019, 55(8): 244-249.
[7]	姚坤，杨斌，朱小林. 考虑时变交通状况的低碳车辆路径优化[J]. 计算机工程与应用, 2019, 55(3): 231-237.
[8]	姚书婷，胡志华，魏晨. 多禁止时间窗约束的路径恢复问题研究[J]. 计算机工程与应用, 2019, 55(12): 265-270.
[9]	邓烨，朱万红，王凤山，刘华丽. 应急物流车辆调度多目标鲁棒优化研究[J]. 计算机工程与应用, 2019, 55(1): 248-255.
[10]	王转，裴泽平. 启发式路径下节约里程的订单分批算法[J]. 计算机工程与应用, 2018, 54(23): 203-209.
[11]	汤旻安1，2，谷宝慧1. 改进PSO在AGV系统路径优化调度中的应用研究[J]. 计算机工程与应用, 2016, 52(3): 261-265.
[12]	姜海洋，周宽久，林林，郝佳亮，郭铖. 战时运输风险评估模型及其路径优化研究[J]. 计算机工程与应用, 2016, 52(17): 235-242.
[13]	陈海松，贺伟雄，楼增龙，彭永飞. 应急条件下边防地区路径优化算法研究[J]. 计算机工程与应用, 2016, 52(1): 33-36.
[14]	蒋国清1，潘勇2，胡飞跃1. 两阶段式的物流配送路径优化方法[J]. 计算机工程与应用, 2015, 51(2): 255-258.
[15]	李雪竹. 基于免疫萤火虫算法的RFID仓储车辆动态调度[J]. 计算机工程与应用, 2014, 50(6): 235-239.

关键节点和平滑处理的PRM路径优化方法

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics