Adaptive Bi-Directional RRT Algorithm for Three-Dimensional Path Planning of Unmanned Aerial Vehicles in Complex Environments
This paper proposes an Adaptive Bi-directional Rapidly-exploring Random Tree (ABi-RRT) algorithm with the objective of addressing challenges in three-dimensional path planning of unmanned aerial vehicle (UAV) operating in complex environments. The algorithm utilizes an adaptive sampling strategy and...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2025-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10869387/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1823859643401633792 |
|---|---|
| author | Nan Li Sang Ik Han |
| author_facet | Nan Li Sang Ik Han |
| author_sort | Nan Li |
| collection | DOAJ |
| description | This paper proposes an Adaptive Bi-directional Rapidly-exploring Random Tree (ABi-RRT) algorithm with the objective of addressing challenges in three-dimensional path planning of unmanned aerial vehicle (UAV) operating in complex environments. The algorithm utilizes an adaptive sampling strategy and an adjustable step size to enhance performance relative to the Bi-RRT algorithm. In contrast to the Bi-RRT algorithm, which utilizes a random sampling strategy and a fixed step size, potentially leading to inefficiencies and limited search effectiveness, the ABi-RRT algorithm incorporates a dynamic mechanism. This mechanism adjusts the sampling strategy and step size based on the complexity of the search environment. This adaptive approach reduces the randomness in sampling, improves the target-oriented nature of the search, and consequently enhances overall search efficiency. Additionally, a greedy path pruning algorithm is integrated to minimize the path length and reduce the number of points along the path. The utilization of cubic B-spline curves further improves the coherence and smoothness of the generated paths. Simulation results demonstrate that the ABi-RRT algorithm can rapidly and effectively produce paths that are smoother, shorter, and of superior quality compared to existing RRT algorithms. Notably, the ABi-RRT algorithm achieves a 100% success rate in path planning. Furthermore, its average running time is significantly reduced, outperforming the ABA* and AAE-RRT* algorithms by approximately a factor of fifteen and three, respectively. This performance is particularly valuable for UAVs operating under stringent performance constraints in complex three-dimensional environments. |
| format | Article |
| id | doaj-art-ccca1286015e4481848c166fa0e90d7f |
| institution | Kabale University |
| issn | 2169-3536 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj-art-ccca1286015e4481848c166fa0e90d7f2025-02-11T00:01:37ZengIEEEIEEE Access2169-35362025-01-0113237482376710.1109/ACCESS.2025.353769710869387Adaptive Bi-Directional RRT Algorithm for Three-Dimensional Path Planning of Unmanned Aerial Vehicles in Complex EnvironmentsNan Li0https://orcid.org/0009-0005-8300-3200Sang Ik Han1https://orcid.org/0000-0002-5263-4932Department of Information and Communication, Semyung University, Jecheon-si, Republic of KoreaSchool of Smart IT, Semyung University, Jecheon-si, Republic of KoreaThis paper proposes an Adaptive Bi-directional Rapidly-exploring Random Tree (ABi-RRT) algorithm with the objective of addressing challenges in three-dimensional path planning of unmanned aerial vehicle (UAV) operating in complex environments. The algorithm utilizes an adaptive sampling strategy and an adjustable step size to enhance performance relative to the Bi-RRT algorithm. In contrast to the Bi-RRT algorithm, which utilizes a random sampling strategy and a fixed step size, potentially leading to inefficiencies and limited search effectiveness, the ABi-RRT algorithm incorporates a dynamic mechanism. This mechanism adjusts the sampling strategy and step size based on the complexity of the search environment. This adaptive approach reduces the randomness in sampling, improves the target-oriented nature of the search, and consequently enhances overall search efficiency. Additionally, a greedy path pruning algorithm is integrated to minimize the path length and reduce the number of points along the path. The utilization of cubic B-spline curves further improves the coherence and smoothness of the generated paths. Simulation results demonstrate that the ABi-RRT algorithm can rapidly and effectively produce paths that are smoother, shorter, and of superior quality compared to existing RRT algorithms. Notably, the ABi-RRT algorithm achieves a 100% success rate in path planning. Furthermore, its average running time is significantly reduced, outperforming the ABA* and AAE-RRT* algorithms by approximately a factor of fifteen and three, respectively. This performance is particularly valuable for UAVs operating under stringent performance constraints in complex three-dimensional environments.https://ieeexplore.ieee.org/document/10869387/Three-dimensional path planningunmanned aerial vehicleadaptive bi-directional RRTpath pruningcubic B-spline |
| spellingShingle | Nan Li Sang Ik Han Adaptive Bi-Directional RRT Algorithm for Three-Dimensional Path Planning of Unmanned Aerial Vehicles in Complex Environments IEEE Access Three-dimensional path planning unmanned aerial vehicle adaptive bi-directional RRT path pruning cubic B-spline |
| title | Adaptive Bi-Directional RRT Algorithm for Three-Dimensional Path Planning of Unmanned Aerial Vehicles in Complex Environments |
| title_full | Adaptive Bi-Directional RRT Algorithm for Three-Dimensional Path Planning of Unmanned Aerial Vehicles in Complex Environments |
| title_fullStr | Adaptive Bi-Directional RRT Algorithm for Three-Dimensional Path Planning of Unmanned Aerial Vehicles in Complex Environments |
| title_full_unstemmed | Adaptive Bi-Directional RRT Algorithm for Three-Dimensional Path Planning of Unmanned Aerial Vehicles in Complex Environments |
| title_short | Adaptive Bi-Directional RRT Algorithm for Three-Dimensional Path Planning of Unmanned Aerial Vehicles in Complex Environments |
| title_sort | adaptive bi directional rrt algorithm for three dimensional path planning of unmanned aerial vehicles in complex environments |
| topic | Three-dimensional path planning unmanned aerial vehicle adaptive bi-directional RRT path pruning cubic B-spline |
| url | https://ieeexplore.ieee.org/document/10869387/ |
| work_keys_str_mv | AT nanli adaptivebidirectionalrrtalgorithmforthreedimensionalpathplanningofunmannedaerialvehiclesincomplexenvironments AT sangikhan adaptivebidirectionalrrtalgorithmforthreedimensionalpathplanningofunmannedaerialvehiclesincomplexenvironments |