RAPID RANDOM TREE AND DUBINS PATH ALGORITHM FOR DRONE OBSTACLE AVOIDANCE

Authors

  • Nur Aliah Saparin Faculty of Mechanical Engineering, Faculty of Engineering, Universiti Teknologi Malaysia, 81310 UTM Johor Bahru, Johor, Malaysia
  • Mastura Ab Wahid Faculty of Mechanical Engineering, Faculty of Engineering, Universiti Teknologi Malaysia, 81310 UTM Johor Bahru, Johor, Malaysia
  • Norazila Othman Faculty of Mechanical Engineering, Faculty of Engineering, Universiti Teknologi Malaysia, 81310 UTM Johor Bahru, Johor, Malaysia

DOI:

https://doi.org/10.11113/jm.v48.523

Abstract

Unmanned aerial vehicles (UAVs) have been commonly used for domestic and military surveillance. Path planning algorithms are one of the many tools that can be used to control UAVs to make the flight autonomous and decrease the involvement of human pilots. The purpose of this study is to develop and implement path planning algorithms to enhance the navigation capabilities of drones in complex environments. Rapidly-exploring Random Tree (RRT) is one of the algorithms that uses sampling based methods to find possible flight paths in highly-dimension space. This research presents the simulation of the algorithm testing in various maps with randomly placed obstacles in MATLAB software to see whether the algorithm managed to manoeuvre around the obstacle successfully with minimum collisions. To further refine the generated path, Dubins path smoothing techniques are implemented in the simulation, to ensure a smoother and more feasible trajectories for drone navigation. The path generated is observed through the result shown in the simulation in both 2D view and 3D view for 3 different random cases. To summarize, the application of Dubins path smoothing significantly improves the efficiency of the path-planning algorithm and reduces the time to complete the obstacle navigation by 10-27% depending on the complexity of the map. The smoothed paths are more direct, involve fewer abrupt turns, and consistently reduce the time to reach the goal across different maps.

References

Mahmoud, M. S., Oyedeji, M. O., & Xia, Y. (2021). Path planning in autonomous aerial vehicles. In Advanced Distributed Consensus for Multiagent Systems (pp. 331–362). Elsevier. https://doi.org/10.1016/b978-0-12-821186-1.00018-0

Radmanesh, M., Kumar, M., Guentert, P. H., & Sarim, M. (2018). Overview of Path-Planning and Obstacle Avoidance Algorithms for UAVs: A Comparative Study. Unmanned Systems, 6(2), 95–118. https://doi.org/10.1142/S2301385018400022

Dhulkefl, E. J., & Durdu, A. (2019). Path Planning Algorithms for Unmanned Aerial Vehicles. International Journal of Trend in Scientific Research and Development, Volume-3(Issue-4), 359–362. https://doi.org/10.31142/ijtsrd23696

Gugan, G., & Haque, A. (2023). Path Planning for Autonomous Drones: Challenges and Future Directions. In Drones (Vol. 7, Issue 3). MDPI. https://doi.org/10.3390/drones7030169

Karur, K., Sharma, N., Dharmatti, C., & Siegel, J. E. (2021). A Survey of Path Planning Algorithms for Mobile Robots. Vehicles, 3(3), 448–468. https://doi.org/10.3390/vehicles3030027

Tony, L. A., Ghose, D., & Chakravarthy, A. (2018). Precision UAV Collision Avoidance Using Computationally Efficient Avoidance Maps. 2018 AIAA Guidance, Navigation, and Control Conference. https://doi.org/10.2514/6.2018-0875

Zhang, R., Guo, H., Andriukaitis, D., Li, Y., Królczyk, G., & Li, Z. (2024). Intelligent path planning by an improved RRT algorithm with dual grid map. Alexandria Engineering Journal, 88, 91–104. https://doi.org/10.1016/j.aej.2023.12.044

Jeauneau, V., Jouanneau, L., & Kotenkoff, A. (2018). Path planner methods for UAVs in real environment. IFAC-PapersOnLine, 51(22), 292–297. https://doi.org/10.1016/j.ifacol.2018.11.557

Vasudevan, V. (2021). Obstacle Detection and Avoidance Algorithm in Drones: Airsim Simulation with HIL (Doctoral dissertation, California State University, Northridge).

Xu, Z., Hu, J., Ma, Y., Wang, M., & Zhao, C. (2019). A Study on Path Planning Algorithms of UAV Collision Avoidance. Xibei Gongye Daxue Xuebao/Journal of Northwestern Polytechnical University, 37(1), 100–106. https://doi.org/10.1051/jnwpu/20193710100

Yang, Y., Leeghim, H., & Kim, D. (2022). Dubins Path-Oriented Rapidly Exploring Random Tree* for Three-Dimensional Path Planning of Unmanned Aerial Vehicles. Electronics, 11(15), 2338. https://doi.org/10.3390/electronics11152338

Ravankar, A., Ravankar, A. A., Kobayashi, Y., Hoshino, Y., & Peng, C. C. (2018). Path smoothing techniques in robot navigation: State-of-the-art, current and future challenges. In Sensors (Switzerland) (Vol. 18, Issue 9). MDPI AG. https://doi.org/10.3390/s18093170

Shkel, A. M., & Lumelsky, V. (2001). Classification of the Dubins set. Robotics and Autonomous Systems, 34(4), 179–202. https://doi.org/10.1016/s0921-8890(00)00127-5

Y. Oh, K. Cho and S. Oh, "Robust Multi-Objective Path Planning for Flying Robots under Wind Disturbance," 2018 15th International Conference on Ubiquitous Robots (UR), Honolulu, HI, USA, 2018, pp. 670-675, doi: 10.1109/URAI.2018.8441822.

LaValle, Steven. "Rapidly-exploring random trees: A new tool for path planning." Research Report 9811 (1998).

Yang Y, Leeghim H, Kim D. Dubins Path-Oriented Rapidly Exploring Random Tree* for Three-Dimensional Path Planning of Unmanned Aerial Vehicles. Electronics. 2022; 11(15):2338. https://doi.org/10.3390/electronics11152338

Published

2025-01-10

How to Cite

Saparin, N. A., Ab Wahid, M., & Othman, N. (2025). RAPID RANDOM TREE AND DUBINS PATH ALGORITHM FOR DRONE OBSTACLE AVOIDANCE. Jurnal Mekanikal, 48(1). https://doi.org/10.11113/jm.v48.523

Issue

Section

Mechanical