Journal of Jilin University(Engineering and Technology Edition) ›› 2023, Vol. 53 ›› Issue (3): 781-791.doi: 10.13229/j.cnki.jdxbgxb20221026

Previous Articles    

Trajectory planning of unmanned system based on DKRRT*⁃APF algorithm

Zhen-yu WU1(),Xiao-fei LIU2,Yi-pu WANG1   

  1. 1.School of Innovation and Entrepreneurship，Dalian University of Technology，Dalian 116024，China
    2.School of Control Science and Engineering，Dalian University of Technology，Dalian 116024，China
  • Received:2022-12-12 Online:2023-03-01 Published:2023-03-29

RICH HTML

 5   

PDF (PC)

112

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

CLC Number: 

  • F416.67

Fig.1

Schematic diagram of node adjustment using APF algorithm"

Fig.2

Schematic diagram of double tree expansion"

Fig.3

Gravitational relation curve"

Fig.4

Repulsion curve"

Fig.5

Flow chart of DKRRT*-APF algorithm"

Fig.6

Module 1：process of KRRT* algorithm expansion and reconstruction of search tree"

Table 1

Map1：complex map obstacle information"

序号位置信息序号位置信息
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）

Table 2

Map2：Narrow passage map obstacle information"

序号位置信息序号位置信息
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）

Fig.7

A double integral dynamic sweeper"

Fig.8

Effect comparison of double integral unmanned vehicle model"

Table 3

Experimental results of double integral unmanned vehicle model"

类别平均损耗平均迭代次数平均耗时/ms
KRRT*（地图一）104.9191.705718.64
KRRT*-APF（地图一）101.7754.522483.40
DKRRT*-APF（地图一）109.3527.231241.54
KRRT*（地图二）126.2645.141128.61
KRRT*-APF（地图二）123.4735.20967.80
DKRRT*-APF（地图二）124.9323.72595.86

Fig.9

A quadrotor unmanned aerial vehicle"

Fig.10

Effect comparison of linearized quadrotor model"

Table 4

Experimental results of linearizedquadrotor model"

类别平均损耗平均迭代次数平均耗时/ms
KRRT*（地图一）15.7342.05558.26
KRRT*-APF（地图一）16.7621.74252.41
DKRRT*-APF（地图一）17.1211.93155.81
KRRT*（地图二）19.0330.45542.89
KRRT*-APF（地图二）18.8326.04417.72
DKRRT*-APF（地图二）19.5720.07306.83
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.
[1] Hong-yang PAN,Zhao LIU,Bo YANG,Geng SUN,Yan-heng LIU. Overview of swarm intelligence methods for unmanned aerial vehicle systems based on new⁃generation information technology [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(3): 629-642.
[2] Peng GUO,Wen-chao ZHAO,Kun LEI. Dual⁃resource constrained flexible job shop optimal scheduling based on an improved Jaya algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(2): 480-487.
[3] Jin-Zhen Liu,Guo-Hui Gao,Hui Xiong. Multi⁃scale attention network for brain tissue segmentation [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(2): 576-583.
[4] Xian-yu QI,Wei WANG,Lin WANG,Yu-fei ZHAO,Yan-peng DONG. Semantic topological map building with object semantic grid map [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(2): 569-575.
[5] Xiao-hu SHI,Jia-qi WU,Chun-guo WU,Shi CHENG,Xiao-hui WENG,Zhi-yong CHANG. Residual network based curve enhanced lane detection method [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(2): 584-592.
[6] Fu-heng QU,Tian-yu DING,Yang LU,Yong YANG,Ya-ting HU. Fast image codeword search algorithm based on neighborhood similarity [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(8): 1865-1871.
[7] Tian BAI,Ming-wei XU,Si-ming LIU,Ji-an ZHANG,Zhe WANG. Dispute focus identification of pleading text based on deep neural network [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(8): 1872-1880.
[8] Feng-feng ZHOU,Hai-yang ZHU. SEE： sense EEG⁃based emotion algorithm via three⁃step feature selection strategy [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(8): 1834-1841.
[9] Gui-he QIN,Jun-feng HUANG,Ming-hui SUN. Text input based on two⁃handed keyboard in virtual environment [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(8): 1881-1888.
[10] Feng-feng ZHOU,Yi-chi ZHANG. Unsupervised feature engineering algorithm BioSAE based on sparse autoencoder [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(7): 1645-1656.
[11] Jun WANG,Yan-hui XU,Li LI. Data fusion privacy protection method with low energy consumption and integrity verification [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(7): 1657-1665.
[12] Yao-long KANG,Li-lu FENG,Jing-an ZHANG,Fu CHEN. Outlier mining algorithm for high dimensional categorical data streams based on spectral clustering [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(6): 1422-1427.
[13] Wen-jun WANG,Yin-feng YU. Automatic completion algorithm for missing links in nowledge graph considering data sparsity [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(6): 1428-1433.
[14] Xue-yun CHEN,Xue-yu BEI,Qu YAO,Xin JIN. Pedestrian segmentation and detection in multi-scene based on G-UNet [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(4): 925-933.
[15] Shi-min FANG. Multiple source data selective integration algorithm based on frequent pattern tree [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(4): 885-890.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd