Path Planning Algorithms in Unknown and Unstructured Environments for UAVs

• Lidia Rocha UFSCar
• Kelen Vivaldini UFSCar

DOI: https://doi.org/10.5753/wtdr_ctdr.2022.226888

Resumo

For an Unmanned Aerial Vehicle to become autonomous, it must perform actions without human interference. Regardless of its application area, path planning is required to carry out a mission. Nowadays, several applications require the UAV to operate in an unknown, 3D, and unstructured environment. Another essential point is considering the movement restrictions in the execution of the movements, where achieving smooth curves reduces the number of stops on 90 degrees curves. One observable aspect among the existing and most used techniques is ”which would be the best technique to work in each of these environments”. This work aims to answer this question with a deeper analysis of all path planning categories: classic, metaheuristic, and machine learning. We develop our planner to analyze these techniques considering completeness, distance, time, CPU usage, memory usage, collision prevention, and robustness. This planner is modular, so it is possible to add new techniques and scenarios to be studied. We also performed tests in simulated and real environments.

Referências

Benevides, J. R., Inoue, R. S., Paiva, M. A., and Terra, M. H. (2019). Ros-based robust and recursive optimal control of commercial quadrotors. In 15th Int. Conf. on Automation Science and Engineering (CASE), pages 998-1003. IEEE.

Báča, T., Petrlík, M., Vrba, M., Spurný, V., Pěnička, R., Hert, D., and Saska, M. (2020). The MRS UAV system: Pushing the frontiers of reproducible research, real-world deployment, and education with autonomous unmanned aerial vehicles.

Dokeroglu, T., Sevinc, E., Kucukyilmaz, T., and Cosar, A. (2019). A survey on new generation metaheuristic algorithms. Computers & Industrial Engineering, 137:106040.

Forster, C., Carlone, L., Dellaert, F., and Scaramuzza, D. (2016). On-manifold preintegration for real-time visual-inertial odometry. IEEE Trans. on Robotics, 33(1):1-21.

Goel, U., Varshney, S., Jain, A., Maheshwari, S., and Shukla, A. (2018). Three dimensional path planning for UAVs in dynamic environment using glow-worm swarm optimization. Procedia computer science, 133:230-239.

Li, J., Yang, S. X., and Xu, Z. (2019). A survey on robot path planning using bio-inspired algorithms. In 2019 IEEE International Conference on Robotics and Biomimetics (ROBIO), pages 2111-2116. IEEE.

Li, W. (2019). An improved artificial potential field method based on chaos theory for UAV route planning. In 2019 34rd Youth Academic Annual Conference of Chinese Association of Automation (YAC), pages 47-51. IEEE.

McIntyre, D., Naeem, W., and Xu, X. (2016). Cooperative obstacle avoidance using bidirectional artificial potential fields. In 2016 UKACC 11th International Conference on Control (CONTROL), pages 1-6. IEEE.

McKinley, S. and Levine, M. (1998). Cubic spline interpolation. Redwoods College.

Mohsan, S. A. H., Khan, M. A., Noor, F., Ullah, I., and Alsharif, M. H. (2022). Towards the unmanned aerial vehicles (uavs): A comprehensive review. Drones, 6(6):147.

Nguyen, A., Nguyen, H., Tran, V., Pham, H. X., and Pestana, J. (2021). A visual real-time fire detection using single shot multibox detector for uav-based fire surveillance. In 2020 IEEE Eighth International Conference on Communications and Electronics (ICCE), pages 338-343. IEEE.

Noreen, I., Khan, A., Asghar, K., and Habib, Z. (2019). A path-planning performance comparison of RRT*-AB with MEA* in a 2-dimensional environment. Symmetry.

Pandey, P., Shukla, A., and Tiwari, R. (2018). Three-dimensional path planning for unmanned aerial vehicles using glowworm swarm optimization algorithm. International Journal of System Assurance Engineering and Management, 9(4):836-852.

Patle, B., Pandey, A., Parhi, D., Jagadeesh, A., et al. (2019). A review: On path planning strategies for navigation of mobile robot. Defence Technology.

Perez-Grau, F. J., Ragel, R., Caballero, F., Viguria, A., and Ollero, A. An architecture for robust UAV navigation in gps-denied areas. Journal of Field Robotics.

Qu, C., Gai, W., Zhong, M., and Zhang, J. (2020). A novel reinforcement learning based grey wolf optimizer algorithm for unmanned aerial vehicles (UAVs) path planning. Applied Soft Computing, 89:106099.

Rocha, L., Aniceto, M., Araújo, I., and Vivaldini, K. (2021). A uav global planner to improve path planning in unstructured environments. In 2021 International Conference on Unmanned Aircraft Systems (ICUAS), pages 688-697.

Rocha, L. and Vivaldini, K. (2020). Comparison between meta-heuristic algorithms for path planning. In Anais do VIII Workshop de Teses e Dissertações em Robótica/Concurso de Teses e Dissertações em Robótica. SBC.

Rocha, L. and Vivaldini, K. (2022). A 3d benchmark for uav path planning algorithms: Missions complexity, evaluation and performance. In 2022 International Conference on Unmanned Aircraft Systems (ICUAS), pages 412-420.

Sankararaman, S. and Goebel, K. (2018). Computational architecture for autonomous decision-making in unmanned aerial vehicles. In Micro-and Nanotech. Sensors, Sys., and App. X, volume 10639, page 106391Y. Inter. Society for Optics and Photonics.

She, R. and Ouyang, Y. (2021). Efficiency of uav-based last-mile delivery under congestion in low-altitude air. Transp. Research Part C: Emerging Technologies, 122:102878.

Xu, Z., Deng, D., and Shimada, K. (2021). Autonomous uav exploration of dynamic environments via incremental sampling and probabilistic roadmap. IEEE Robotics and Automation Letters, 6(2):2729-2736.

Zhang, D., Xu, Y., and Yao, X. (2018). An improved path planning algorithm for unmanned aerial vehicle based on RRT-connect. In 2018 37th Chinese Control Conference (CCC), pages 4854-4858. IEEE.