基于DKRRT*-APF算法的无人系统轨迹规划

doi:10.13229/j.cnki.jdxbgxb20221026

摘要/Abstract

摘要：

针对传统快速扩展随机树（RRT）算法规划的路径随机性强、收敛速度慢、不具备连续性、无法满足大多数机器人的动力学约束以及Kinodynamic RRT^*算法规划路径符合动力学约束但搜索速度较慢的问题，本文基于Kinodynamic RRT^*算法，提出了一种DKRRT^*-APF算法。将Kinodynamic RRT^*节点扩展由单向扩展改进为双向扩展，以提高路径搜索效率。在采样阶段引入了人工势场（APF）算法地图势场的思想，设计了特殊的引力函数和斥力函数，使地图中目标点和障碍物为采样节点提供一定的目标导向和避障功能，缩短轨迹规划时间。为验证算法的可行性，使用双积分动力学无人车模型和四旋翼动力学无人机模型对DKRRT^*-APF算法进行了仿真测试。仿真结果表明，DKRRT^*-APF算法规划轨迹符合无人系统的动力学约束。在轨迹平均损耗相同的情况下，DKRRT^*-APF算法的平均生成节点数和平均轨迹规划时间相比于Kinodynamic RRT^*算法得到了有效改善。

关键词: 计算机应用, 全局路径规划, 快速随机探索树, 人工势场法

Abstract:

In allusion to the disadvantages of traditional RRT algorithm such as strong randomness， slow convergence， lack of continuity and being unable to meet the dynamic constraints of most robots， and Kinodynamic RRT^* algorithm which conforms to dynamic constraints but have a slow search speed， a DKRRT^*-APF algorithm besed on Kinodynamic RRT^* algorithm was proposed. Kinodynamic RRT^* node expansion was improved from unidirectional expansion to bidirectional expansion to speed up trajectory search efficiency； meanwhile， in the sampling stage of Kinodynamic RRT^*， the idea of map potential field of APF algorithm was introduced， and special gravity function and repulsion function were designed to make the target points and obstacles in the map provide some target guidance and obstacle avoidance effect for the sampling nodes， and shorten trajectory planning time. To verify the feasibility of this idea， the DKRRT^*-APF algorithm was tested by using the double integral dynamic unmanned vehicle model and the linearized unmanned quadrotor model. The simulation results show that the trajectory planning by DKRRT^*-APF algorithm conforms to the dynamic constraints of the robot model. When the average trajectory loss is the same， the average number of generated nodes and the average trajectory planning time of DKRRT^*-APF algorithm are effectively improved compared with KRRT*.

Key words: computer application, global path planning, rapidly-exploring random trees, artificial potential field method

中图分类号:

F416.67

吴振宇,刘小飞,王义普. 基于DKRRT^*-APF算法的无人系统轨迹规划[J]. 吉林大学学报(工学版), 2023, 53(3): 781-791.

Zhen-yu WU,Xiao-fei LIU,Yi-pu WANG. Trajectory planning of unmanned system based on DKRRT^*⁃APF algorithm[J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(3): 781-791.

图/表 14

图1

图2

图3

图4

图5

图6

表1

表2

图7

图8

表3

图9

图10

表4

参考文献 20

1	Lamini C, Benhlima S, Elbekri A. Genetic algorithm based approach for autonomous mobile robot path planning[J]. Procedia Computer Science, 2018, 127: 180-189.
2	Mustafa S, Mohamad R, Deris S. Optimal path test data generation based on hybrid negative selection algorithm and genetic algorithm[J]. PLoS ONE, 2020, 15(11): 1-21.
3	王晓燕, 杨乐, 张宇, 等. 基于改进势场蚁群算法的机器人路径规划[J]. 控制与决策, 2018, 33(10): 1775-1781.
	Wang Xiao-yan, Yang Le, Zhang Yu, et al. Robot path planning based on improved potential field ant colony algorithm[J]. Control and Decision, 2018, 33(10): 1775-1781.
4	Sedighi S, Nguyen D V, Kuhnert K D. Guided hybrid a-star path planning algorithm for valet parking applications[C]∥2019 5th International Conference on Control, Automation and Robotics (ICCAR), Beijing, China, 2019: 570-575.
5	罗强, 王海宝, 崔小劲, 等. 改进人工势场法自主移动机器人路径规划[J]. 控制工程, 2019, 26(6): 1091-1098.
	Luo Qiang, Wang Hai-bao, Cui Xiao-jing, et al. Improved artificial potential field method for path planning of autonomous mobile robot[J]. Control Engineering of China, 2019, 26(6): 1091-1098.
6	Sang H, You Y, Sun X, et al. The hybrid path planning algorithm based on improved A^* and artificial potential field for unmanned surface vehicle formations[J]. Ocean Engineering, 2021, 223(3/4): 1-16.
7	刘恩海, 高文斌, 孔瑞平, 等. 改进的RRT路径规划算法[J]. 计算机工程与设计, 2019, 40(8): 2253-2258.
	Liu En-hai, Gao Wen-bin, Kong Rui-ping, et al. Improved RRT path planning algorithm[J]. Computer Engineering and Design, 2019, 40(8): 2253-2258.
8	Hu B, Cao Z C, Zhou M C. An efficient RRT-based framework for planning short and smooth wheeled robot motion under kinodynamic constraints[J]. IEEE Transactions on Industrial Electronics, 2020, PP(99): 3292-3302.
9	张伟民, 付仕雄. 基于改进RRT^*算法的移动机器人路径规划[J]. 华中科技大学学报:自然科学版, 2021, 49(1): 31-36.
	Zhang Wei-min, Fu Shi-xiong. Path planning of mobile robot based on improved RRT^* algorithm[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2021, 49(1): 31-36.
10	张亚琨, 高泽东, 曹杰, 等. 多采样寻优的双向RRT路径规划算法[J].计算机仿真,2019, 36(2): 319-324.
	Zhang Ya-kun, Gao Ze-dong, Cao Jie, et al. Bidirectional RRT path planning algorithm based on multi sampling optimization[J]. Computer Simulation, 2019, 36(2): 319-324.
11	王硕, 段蓉凯, 廖与禾.机器人路径规划中快速扩展随机树算法的改进研究[J].西安交通大学学报, 2022, 56(7): 1-8.
	Wang Shuo, Duan Rong-kai, Liao Yu-he. Research on improvement of rapidly expanding random tree algorithm in robot path planning[J]. Journal of Xi'an Jiaotong University, 2022, 56(7): 1-8.
12	王杨斌, 章伟, 王为科, 等. 改进Informed-RRT^*的动态环境路径规划算法[J]. 电光与控制, 2022, 29(5): 28-32.
	Wang Yang-bin, Zhang Wei, Wang Wei-ke, et al. Improved informed RRT^* path planning algorithm for dynamic environment[J]. Electronics Optics & Control, 2022, 29(5): 28-32.
13	Wang W, Zuo L, Xu X. A learning-based multi-RRT approach for robot path planning in narrow passages[J]. Journal of Intelligent and Robotic Systems, 2018, 90(1): 81-100.
14	Wang J K, Chi W Z, Li C M, et al. Neural RRT^*: learning-based optimal path planning[J]. IEEE Transactions on Automation Science and Engineering, 2020, 17(4): 1748-1758.
15	Webb D J, Berg J. Kinodynamic RRT*: asymptotically optimal motion planning for robots with linear dynamics[C]∥IEEE International Conference on Robotics & Automation, Karlsruhe, Germany, 2013: 5054-5061.
16	Fan X, Guo Y, Liu H, et al. Improved artificial potential field method applied for AUV path planning[J]. Mathematical Problems in Engineering, 2020(1): 1-21.
17	王兵, 吴洪亮, 牛新征. 基于改进势场法的机器人路径规划[J]. 计算机科学, 2022, 49(7): 196-203.
	Wang bin, Wu Hong-liang, Niu Xing-zheng. Robot path planning based on improved potential field method[J]. Computer Science, 2022, 49(7): 196-203.
18	甘新基. 基于Bézier曲线的差速驱动机器人混合避障路径规划算法[J]. 吉林大学学报: 理学版, 2021, 59(4): 943-949.
	Gan Xin-ji. Path planning algorithm for hybrid obstacle avoidance of differential drive robot based on Bézier curve[J]. Journal of Jilin University (Science Edition), 2021, 59(4): 943-949.
19	Chen L, Lv Z, Shen X, et al. Adaptive attitude control for a coaxial tilt-rotor UAV via immersion and invariance methodology[J]. IEEE/CAA Journal of Automatica Sinica, 2022, 9(9):1710-1713.
20	Lv Z Y, Wu Y H, Sun X M, et al. Fixed-time control for a quadrotor with a cable-suspended load[J]. IEEE Transactions on Intelligent Transportation Systems, 2022(99): 1-12.

相关文章 15

[1]	潘弘洋,刘昭,杨波,孙庚,刘衍珩. 基于新一代通信技术的无人机系统群体智能方法综述[J]. 吉林大学学报(工学版), 2023, 53(3): 629-642.
[2]	郭鹏,赵文超,雷坤. 基于改进Jaya算法的双资源约束柔性作业车间调度[J]. 吉林大学学报(工学版), 2023, 53(2): 480-487.
[3]	刘近贞,高国辉,熊慧. 用于脑组织分割的多尺度注意网络[J]. 吉林大学学报(工学版), 2023, 53(2): 576-583.
[4]	祁贤雨,王巍,王琳,赵玉飞,董彦鹏. 基于物体语义栅格地图的语义拓扑地图构建方法[J]. 吉林大学学报(工学版), 2023, 53(2): 569-575.
[5]	时小虎,吴佳琦,吴春国,程石,翁小辉,常志勇. 基于残差网络的弯道增强车道线检测方法[J]. 吉林大学学报(工学版), 2023, 53(2): 584-592.
[6]	曲福恒,丁天雨,陆洋,杨勇,胡雅婷. 基于邻域相似性的图像码字快速搜索算法[J]. 吉林大学学报(工学版), 2022, 52(8): 1865-1871.
[7]	白天,徐明蔚,刘思铭,张佶安,王喆. 基于深度神经网络的诉辩文本争议焦点识别[J]. 吉林大学学报(工学版), 2022, 52(8): 1872-1880.
[8]	周丰丰,朱海洋. 基于三段式特征选择策略的脑电情感识别算法SEE[J]. 吉林大学学报(工学版), 2022, 52(8): 1834-1841.
[9]	赵宏伟,张健荣,朱隽平,李海. 基于对比自监督学习的图像分类框架[J]. 吉林大学学报(工学版), 2022, 52(8): 1850-1856.
[10]	秦贵和,黄俊锋,孙铭会. 基于双手键盘的虚拟现实文本输入[J]. 吉林大学学报(工学版), 2022, 52(8): 1881-1888.
[11]	胡丹,孟新. 基于时变网格的对地观测卫星搜索海上船舶方法[J]. 吉林大学学报(工学版), 2022, 52(8): 1896-1903.
[12]	周丰丰,张亦弛. 基于稀疏自编码器的无监督特征工程算法BioSAE[J]. 吉林大学学报(工学版), 2022, 52(7): 1645-1656.
[13]	王军,徐彦惠,李莉. 低能耗支持完整性验证的数据融合隐私保护方法[J]. 吉林大学学报(工学版), 2022, 52(7): 1657-1665.
[14]	康耀龙,冯丽露,张景安,陈富. 基于谱聚类的高维类别属性数据流离群点挖掘算法[J]. 吉林大学学报(工学版), 2022, 52(6): 1422-1427.
[15]	王文军,余银峰. 考虑数据稀疏的知识图谱缺失连接自动补全算法[J]. 吉林大学学报(工学版), 2022, 52(6): 1428-1433.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

序号	位置信息	序号	位置信息
1	（20，80，4，7）	17	（50，50，3，17）
2	（20，30，5，10）	18	（55，10，5，9）
3	（60，30，6，7）	19	（70，20，3，13）
4	（50，70，8，5）	20	（90，10，5，9）
5	（70，60，2，8）	21	（85，90，5，12）
6	（30，30，1，9）	22	（10，90，5，8）
7	（25，50，3，9）	23	（65，93，7，9）
8	（30，10，5，13）	24	（95，60，5，12）
9	（90，80，3，11）	25	（80，64，3，9）
10	（40，40，5，16）	26	（40，27，5，10）
11	（78，45，6，5）	27	（65，50，4，15）
12	（10，13，4，8）	28	（75，80，3，14）
13	（60，70，2，9）	29	（10，70，3，19）
14	（10，40，5，10）	30	（90，48，2，12）
15	（20，60，5，12）	31	（75，10，3，13）
16	（35，85，5，8）	32	（92，30，4，14）

序号	位置信息	序号	位置信息
1	（30，95，5，20）	10	（70，95，5，20）
2	（30，85，5，20）	11	（70，85，5，20）
3	（30，65，5，20）	12	（70，65，5，20）
4	（30，55，5，20）	13	（70，55，5，20）
5	（30，45，5，20）	14	（70，45，5，20）
6	（30，35，5，20）	15	（70，35，5，20）
7	（30，25，5，20）	16	（70，25，5，20）
8	（30，15，5，20）	17	（70，15，5，20）
9	（30，5，5，20）	18	（70，5，5，20）

类别	平均损耗	平均迭代次数	平均耗时/ms
KRRT^*（地图一）	104.91	91.70	5718.64
KRRT^*-APF（地图一）	101.77	54.52	2483.40
DKRRT^*-APF（地图一）	109.35	27.23	1241.54
KRRT^*（地图二）	126.26	45.14	1128.61
KRRT^*-APF（地图二）	123.47	35.20	967.80
DKRRT^*-APF（地图二）	124.93	23.72	595.86

类别	平均损耗	平均迭代次数	平均耗时/ms
KRRT^*（地图一）	15.73	42.05	558.26
KRRT^*-APF（地图一）	16.76	21.74	252.41
DKRRT^*-APF（地图一）	17.12	11.93	155.81
KRRT^*（地图二）	19.03	30.45	542.89
KRRT^*-APF（地图二）	18.83	26.04	417.72
DKRRT^*-APF（地图二）	19.57	20.07	306.83