An Improved Dynamic Step Size RRT Algorithm in Complex Environments

Yuwei Zhang; Ruirong Wang; Chunlei Song; Jianhua Xu

doi:10.1109/CCDC52312.2021.9602069

An Improved Dynamic Step Size RRT Algorithm in Complex Environments

Yuwei Zhang, Ruirong Wang, Chunlei Song, Jianhua Xu

School of Automation

Beijing Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

10 Citations (Scopus)

Abstract

Rapidly exploring Random Tree(RRT) is an efficient path planning algorithm based on random sampling, which plays an important role in the robot field and autonomous driving field. However, due to the randomness of sampling, its results are usually not optimal. This paper proposes a dynamic step size RRT algorithm, which mainly improves the traditional RRT as follows. First, combined with the Artificial Potential Field(APF), the target makes heuristic guidance for the sampling process. And then, the step size is adaptively changed according to the density of obstacles. After that, a one-shot heuristic strategy is used to speed up the search process. Finally, a bi-directional pruning strategy is adopted to reduce the path length by merging points. The simulation results show that the improved RRT algorithm can find the target faster and better.

Original language	English
Title of host publication	Proceedings of the 33rd Chinese Control and Decision Conference, CCDC 2021
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	3835-3840
Number of pages	6
ISBN (Electronic)	9781665440899
DOIs	https://doi.org/10.1109/CCDC52312.2021.9602069
Publication status	Published - 2021
Event	33rd Chinese Control and Decision Conference, CCDC 2021 - Kunming, China Duration: 22 May 2021 → 24 May 2021

Publication series

Name	Proceedings of the 33rd Chinese Control and Decision Conference, CCDC 2021

Conference

Conference	33rd Chinese Control and Decision Conference, CCDC 2021
Country/Territory	China
City	Kunming
Period	22/05/21 → 24/05/21

Keywords

APF
Bi-directional Pruning
Dynamic Step Size
RRT

Access to Document

10.1109/CCDC52312.2021.9602069

Cite this

Zhang, Y., Wang, R., Song, C., & Xu, J. (2021). An Improved Dynamic Step Size RRT Algorithm in Complex Environments. In Proceedings of the 33rd Chinese Control and Decision Conference, CCDC 2021 (pp. 3835-3840). (Proceedings of the 33rd Chinese Control and Decision Conference, CCDC 2021). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CCDC52312.2021.9602069

@inproceedings{e0881d1e465d40adaeeb7368bfbb93e1,

title = "An Improved Dynamic Step Size RRT Algorithm in Complex Environments",

abstract = "Rapidly exploring Random Tree(RRT) is an efficient path planning algorithm based on random sampling, which plays an important role in the robot field and autonomous driving field. However, due to the randomness of sampling, its results are usually not optimal. This paper proposes a dynamic step size RRT algorithm, which mainly improves the traditional RRT as follows. First, combined with the Artificial Potential Field(APF), the target makes heuristic guidance for the sampling process. And then, the step size is adaptively changed according to the density of obstacles. After that, a one-shot heuristic strategy is used to speed up the search process. Finally, a bi-directional pruning strategy is adopted to reduce the path length by merging points. The simulation results show that the improved RRT algorithm can find the target faster and better.",

keywords = "APF, Bi-directional Pruning, Dynamic Step Size, RRT",

author = "Yuwei Zhang and Ruirong Wang and Chunlei Song and Jianhua Xu",

note = "Publisher Copyright: {\textcopyright} 2021 IEEE.; 33rd Chinese Control and Decision Conference, CCDC 2021 ; Conference date: 22-05-2021 Through 24-05-2021",

year = "2021",

doi = "10.1109/CCDC52312.2021.9602069",

language = "English",

series = "Proceedings of the 33rd Chinese Control and Decision Conference, CCDC 2021",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "3835--3840",

booktitle = "Proceedings of the 33rd Chinese Control and Decision Conference, CCDC 2021",

address = "United States",

}

Zhang, Y, Wang, R, Song, C & Xu, J 2021, An Improved Dynamic Step Size RRT Algorithm in Complex Environments. in Proceedings of the 33rd Chinese Control and Decision Conference, CCDC 2021. Proceedings of the 33rd Chinese Control and Decision Conference, CCDC 2021, Institute of Electrical and Electronics Engineers Inc., pp. 3835-3840, 33rd Chinese Control and Decision Conference, CCDC 2021, Kunming, China, 22/05/21. https://doi.org/10.1109/CCDC52312.2021.9602069

An Improved Dynamic Step Size RRT Algorithm in Complex Environments. / Zhang, Yuwei; Wang, Ruirong; Song, Chunlei et al.
Proceedings of the 33rd Chinese Control and Decision Conference, CCDC 2021. Institute of Electrical and Electronics Engineers Inc., 2021. p. 3835-3840 (Proceedings of the 33rd Chinese Control and Decision Conference, CCDC 2021).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - An Improved Dynamic Step Size RRT Algorithm in Complex Environments

AU - Zhang, Yuwei

AU - Wang, Ruirong

AU - Song, Chunlei

AU - Xu, Jianhua

PY - 2021

Y1 - 2021

N2 - Rapidly exploring Random Tree(RRT) is an efficient path planning algorithm based on random sampling, which plays an important role in the robot field and autonomous driving field. However, due to the randomness of sampling, its results are usually not optimal. This paper proposes a dynamic step size RRT algorithm, which mainly improves the traditional RRT as follows. First, combined with the Artificial Potential Field(APF), the target makes heuristic guidance for the sampling process. And then, the step size is adaptively changed according to the density of obstacles. After that, a one-shot heuristic strategy is used to speed up the search process. Finally, a bi-directional pruning strategy is adopted to reduce the path length by merging points. The simulation results show that the improved RRT algorithm can find the target faster and better.

AB - Rapidly exploring Random Tree(RRT) is an efficient path planning algorithm based on random sampling, which plays an important role in the robot field and autonomous driving field. However, due to the randomness of sampling, its results are usually not optimal. This paper proposes a dynamic step size RRT algorithm, which mainly improves the traditional RRT as follows. First, combined with the Artificial Potential Field(APF), the target makes heuristic guidance for the sampling process. And then, the step size is adaptively changed according to the density of obstacles. After that, a one-shot heuristic strategy is used to speed up the search process. Finally, a bi-directional pruning strategy is adopted to reduce the path length by merging points. The simulation results show that the improved RRT algorithm can find the target faster and better.

KW - APF

KW - Bi-directional Pruning

KW - Dynamic Step Size

KW - RRT

UR - https://www.scopus.com/pages/publications/85125186362

U2 - 10.1109/CCDC52312.2021.9602069

DO - 10.1109/CCDC52312.2021.9602069

M3 - Conference contribution

AN - SCOPUS:85125186362

T3 - Proceedings of the 33rd Chinese Control and Decision Conference, CCDC 2021

SP - 3835

EP - 3840

BT - Proceedings of the 33rd Chinese Control and Decision Conference, CCDC 2021

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 33rd Chinese Control and Decision Conference, CCDC 2021

Y2 - 22 May 2021 through 24 May 2021

ER -

An Improved Dynamic Step Size RRT Algorithm in Complex Environments

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this