均匀分布Logistic混沌序列的RRT*路径规划算法研究

马小陆; 袁书生; 王兵; 吴紫恒

doi:10.13433/j.cnki.1003-8728.20200411

均匀分布Logistic混沌序列的RRT*路径规划算法研究

doi: 10.13433/j.cnki.1003-8728.20200411

马小陆^{1, 2,},
袁书生^{1, 2},
王兵^{1, 2},
吴紫恒^{1, 2}

1.
安徽工业大学电气与信息工程学院，安徽马鞍山　243032
2.
特种重载机器人安徽省重点实验室，安徽马鞍山　243032

基金项目: 国家自然科学基金项目（61472282）、安徽高校自然科学研究重点项目（KJ2019A0065）、安徽省教育厅高校科学研究重大项目（KJ2019ZD05）及特种重载机器人安徽省重点实验室开放课题（TZJQR004-2020）

详细信息

作者简介:
马小陆（1979−），副教授，硕士生导师，博士，研究方向为嵌入式和服务机器人，77578249@qq.com

中图分类号: P242.6
计量
- 文章访问数: 138
- HTML全文浏览量: 39
- PDF下载量: 12
- 被引次数: 0
出版历程
- 收稿日期: 2020-09-21
- 录用日期: 2021-12-16
- 刊出日期: 2022-09-05

Research on RRT * Path Planning Algorithm for Uniformly Distributed Logistic Chaotic Sequence

MA Xiaolu^{1, 2
,},
YUAN Shusheng^{1, 2},
WANG Bing^{1, 2},
WU Ziheng^{1, 2}

1.
School of Electrical and Information Engineering, Anhui University of Technology, Maanshan 243032, Anhui, China
2.
Open Project of AnHui Province Key Laboratory of Special and Heavy Load Robot, Maanshan 243032, Anhui, China

摘要

摘要: 针对RRT*算法存在收敛速度慢的问题，提出了一种均匀Logistic混沌序列采样的RRT*路径规划算法。该方法使用均匀分布Logistic混沌序列方法代替RRT*算法中随机数方法，保证了采样点的随机性和遍历性，提高了通过障碍物区域的概率，加速了随机树重布线的效率。最后通过仿真和实验证明，均匀分布Logistic混沌序列采样的RRT*算法比传统的RRT*算法的采样点少、路径规划时间短和稳定性好。
- 路径规划 /
- Logistic混沌序列 /
- RRT* /
- 概率采样
Abstract: In view of the slow convergence rate of RRT* algorithm, a new RRT* path planning algorithm of uniform Logistic chaotic sequence sampling is proposed in this paper. The method uses uniformly distributed Logistic chaotic sequence instead of random numbers in the traditional RRT* algorithm, which ensures the randomness and ergodicity of sampling points. The algorithm improves the probability of passing through the obstacle area, and also accelerates the efficiency of random tree rerouting. Finally, it is proved by simulation and experiment that new RRT* algorithm based on uniformly distributed Logistic chaotic sequence sampling has fewer sampling points、shorter path planning time and good stability than traditional RRT* algorithm.
- path planning /
- logistic chaotic sequence /
- RRT* /
- probability sampling

HTML全文

图 1 Logistic映射分叉图

下载: 全尺寸图片幻灯片

图 2 非均匀分布的Logistic混沌序列统计直方图

下载: 全尺寸图片幻灯片

图 3 均匀分布的Logistic混沌序列统计直方图

下载: 全尺寸图片幻灯片

图 4 RRT算法扩展模型

下载: 全尺寸图片幻灯片

图 5 RRT*算法的父节点重写

下载: 全尺寸图片幻灯片

图 6 RRT*算法的随机树重新布线

下载: 全尺寸图片幻灯片

图 7 RRT*算法路径扩展陷入障碍物模型

下载: 全尺寸图片幻灯片

图 8 两种方法角度上采样简化模型

下载: 全尺寸图片幻灯片

图 9 随机树重新布线概率模型

下载: 全尺寸图片幻灯片

图 10 仿真试验用地图

下载: 全尺寸图片幻灯片

图 11 成功规划路径的平均长度变化折线图

下载: 全尺寸图片幻灯片

图 12 成功规划路径的平均时间变化折线图

下载: 全尺寸图片幻灯片

图 13 规划路径成功率变化折线图

下载: 全尺寸图片幻灯片

图 14 成功规划路径最短路径长度变化曲线图

下载: 全尺寸图片幻灯片

图 15 成功规划路径最长路径长度变化曲线图

下载: 全尺寸图片幻灯片

图 16 理想状态的路径

下载: 全尺寸图片幻灯片

图 17 RRT*算法规划出的最长路径

下载: 全尺寸图片幻灯片

图 18 移动机器人底盘系统架构图

下载: 全尺寸图片幻灯片

图 19 机器人底盘实物外部

下载: 全尺寸图片幻灯片

图 20 底盘实物图内部

下载: 全尺寸图片幻灯片

图 21 试验用地图

下载: 全尺寸图片幻灯片

图 22 路径规划试验结果图

下载: 全尺寸图片幻灯片

表 1 成功规划路径的平均长度 m

采样次数	1500	1600	1700	1800	1900	2000
RRT*	1064.788	1039.036	1023.120	984.208	1013.093	996.081
改进的RRT*	1032.264	986.249	984.477	982.246	980.986	979.308

下载: 导出CSV

表 2 成功规划路径的平均时间 s

采样次数	1500	1600	1700	1800	1900	2000
RRT*	1.848	2.063	2.126	2.028	2.234	2.478
改进的RRT*	1.769	2.047	2.089	2.113	2.273	2.451

下载: 导出CSV

表 3 成功规划路径次数

采样次数	1500	1600	1700	1800	1900	2000
RRT*	10	18	22	19	16	29
改进的RRT*	14	17	21	23	27	30

下载: 导出CSV

表 4 成功规划路径最短路径长度 m

采样次数	1500	1600	1700	1800	1900	2000
RRT*	974.746	969.514	966.860	969.731	969.166	966.208
改进的RRT*	968.285	968.757	971.231	966.611	968.456	964.156

下载: 导出CSV

表 5 成功规划路径最大路径长度 m

采样次数	1500	1600	1700	1800	1900	2000
RRT*	1252.945	1527.964	1430.475	998.435	1496.203	1457.971
改进的RRT*	1326.664	1024.406	999.034	994.307	993.545	992.241

下载: 导出CSV

表 6 目标点1下两种算法性能比较

算法	平均采样次数	平均规划时间/ms	平均路径长度/m
改进的RRT*	296	61.47	7.224
RRT*	435	106.53	7.383

下载: 导出CSV

表 7 目标点2下两种算法性能比较

算法	平均采样次数	平均规划时间/ms	平均路径长度/m
改进的RRT*	297	47.53	6.440
RRT*	404	134.03	6.322

下载: 导出CSV

参考文献(14)

[1]	LAVALLE S M. Rapidly-exploring random trees: a new tool for path planning[R]. Ames, USA: Iowa State University, 1998
[2]	KARAMAN S, FRAZZOLI E. Incremental sampling-based algorithms for optimal motion planning[Z]. arXiv preprint arXiv: 1005.0416, 2010
[3]	刘建宇, 范平清. 基于改进的RRT-connect算法机械臂路径规划[J]. 计算机工程与应用, 2021, 57(6): 274-278 doi: 10.3778/j.issn.1002-8331.1911-0316 LIU J Y, FAN P Q. Path planning of manipulator based on improved RRT-connect algorithm[J]. Computer Engineering and Applications, 2021, 57(6): 274-278 (in Chinese) doi: 10.3778/j.issn.1002-8331.1911-0316
[4]	LOEVE J W. Finding time-optimal trajectories for the resonating arm using the RRT* algorithm[D]. Delft: Delft University of Technology, 2012
[5]	王嘉琦. 基于改进RRT算法的无人机避障路径规划 [D]. 南昌: 南昌航空大学, 2019 WANG J Q. Obstacle avoidance path planning for UAV based on improved RRT algorithm [D]. Nanchang: Nanchang Hangkong University, 2019 (in Chinese)
[6]	陈晋音, 胡可科, 李玉玮. 基于MB-RRT的无人机多点航迹规划算法研究[J]. 计算机科学, 2018, 45(S1): 85-90 CHEN J Y, HU K K, LI Y W. Research on UAV multi-point navigation algorithm based on MB-RRT[J]. Computer Science, 2018, 45(S1): 85-90 (in Chinese)
[7]	VLASAL J, SOJIK M, HANZÁLEK Z. Accelerated RRT* and its evaluation on autonomous parking[Z]. arXiv preprint arXiv: 2002.04521, 2020
[8]	裴以建, 杨超杰, 杨亮亮. 基于改进RRT的移动机器人路径规划算法[J]. 计算机工程, 2019, 45(5): 285-290,297 PEI Y J, YANG C J, YANG L L. Path planning algorithm for mobile robot based on improved RRT[J]. Computer Engineering, 2019, 45(5): 285-290,297 (in Chinese)
[9]	ADIYATOV O, VAROL H A. A novel RRT*-based algorithm for motion planning in dynamic environments[C]//2017 IEEE International Conference on Mechatronics and Automation (ICMA). Takamatsu, Japan: IEEE, 2017: 1416-1421
[10]	JORDAN M, PEREZ A. Optimal bidirectional Rapidly-exploring random trees[R]. Cambridge, MA: Massachusetts Institute of Technology, 2013
[11]	潘思宇, 徐向荣. 基于改进RRT的移动机器人运动规划算法[J]. 山西大学学报(自然科学版), 2017, 40(2): 244-254 PAN S Y, XU X R. Improved RRT-based motion planning algorithm for mobile robot[J]. Journal of Shanxi University (Natural Science Edition), 2017, 40(2): 244-254 (in Chinese)
[12]	QURESHI A H, AYAZ Y. Intelligent bidirectional rapidly-exploring random trees for optimal motion planning in complex cluttered environments[J]. Robotics and Autonomous Systems, 2015, 68: 1-11 doi: 10.1016/j.robot.2015.02.007
[13]	范九伦, 张雪锋. 分段Logistic混沌映射及其性能分析[J]. 电子学报, 2009, 37(4): 720-725 doi: 10.3321/j.issn:0372-2112.2009.04.009 FAN J L, ZHANG X F. Piecewise Logistic chaotic map and its performance analysis[J]. Acta Electronica Sinica, 2009, 37(4): 720-725 (in Chinese) doi: 10.3321/j.issn:0372-2112.2009.04.009
[14]	曹光辉, 胡凯, 佟维. 基于Logistic均匀分布图像置乱方法[J]. 物理学报, 2011, 60(11): 110508 doi: 10.7498/aps.60.110508 CAO G H, HU K, TONG W. Image scrambling based on Logistic uniform distribution[J]. Acta Physica Sinica, 2011, 60(11): 110508 (in Chinese) doi: 10.7498/aps.60.110508