Enhancing UAV Navigation in Dynamic Environments: A Detailed Integration of Fick's Law Algorithm for Optimal Pathfinding in Complex Terrains

Gregorius Airlangga

doi:10.12928/biste.v5i4.9697

Authors

Gregorius Airlangga Universitas Katolik Indonesia Atma Jaya

DOI:

https://doi.org/10.12928/biste.v5i4.9697

Keywords:

UAV, Navigation, PSO, Dynamic Path Planning, 3D, Python

Abstract

In the realm of Unmanned Aerial Vehicles (UAVs), efficient navigation in complex environments is crucial, necessitating advanced pathfinding algorithms. This study introduces the Fick's Law Algorithm (FLA) for UAV path optimization, drawing inspiration from the principles of molecular diffusion, and positions it in the context of existing algorithms such as A* and Dijkstra's. Through a comparative analysis, we highlight FLA's unique approach and advantages in terms of computational efficiency and adaptability to dynamic obstacles. Our experiment, conducted in a simulated three-dimensional space with static and dynamic obstacles, involves an extensive quantitative analysis. FLA's performance is quantified through metrics like path length reduction, computation time, and obstacle avoidance efficacy, demonstrating a marked improvement over traditional methods. The technical foundation of FLA is detailed, emphasizing its iterative adaptation based on a cost function that accounts for path length and obstacle avoidance. The algorithm's rapid convergence towards an optimal solution is evidenced by a significant decrease in the cost function, supported by data from our convergence graph. Visualizations in both 2D and 3D effectively illustrate the UAV’s trajectory, highlighting FLA's efficiency in real-time path correction and obstacle negotiation. Furthermore, we discuss FLA's practical implications, outlining its adaptability in various real-world UAV applications, while also acknowledging its limitations and potential challenges. This exploration extends FLA's relevance beyond theoretical contexts, suggesting its efficacy in real-world scenarios. Looking ahead, future work will not only focus on enhancing FLA's computational efficiency but also on developing specific methodologies for real-world testing. These include adaptive scaling for different UAV models and environments, as well as integration with UAV hardware systems. Our study establishes FLA as a potent tool for autonomous UAV navigation, offering significant contributions to the field of dynamic path optimization.

References

M. Deng, Q. Yang, and Y. Peng, “A Real-Time Path Planning Method for Urban Low-Altitude Logistics UAVs,” Sensors, vol. 23, no. 17, p. 7472, 2023, https://doi.org/10.3390/s23177472.

P. Han, X. Yang, Y. Zhao, X. Guan, and S. Wang, “Quantitative ground risk assessment for urban logistical unmanned aerial vehicle (UAV) based on bayesian network,” Sustainability, vol. 14, no. 9, p. 5733, 2022, https://doi.org/10.3390/su14095733.

G. Aiello, R. Inguanta, G. D’Angelo, and M. Venticinque, “Energy consumption model of aerial urban logistic infrastructures,” Energies, vol. 14, no. 18, p. 5998, 2021, https://doi.org/10.3390/en14185998.

S. Shao, Y. Peng, C. He, and Y. Du, “Efficient path planning for UAV formation via comprehensively improved particle swarm optimization,” ISA Trans., vol. 97, pp. 415–430, 2020, https://doi.org/10.1016/j.isatra.2019.08.018.

Z. Qadir, M. H. Zafar, S. K. R. Moosavi, K. N. Le, and M. A. P. Mahmud, “Autonomous UAV path-planning optimization using metaheuristic approach for predisaster assessment,” IEEE Internet Things J., vol. 9, no. 14, pp. 12505–12514, 2021, https://doi.org/10.1109/JIOT.2021.3137331.

C. Xu, M. Xu, and C. Yin, “Optimized multi-UAV cooperative path planning under the complex confrontation environment,” Comput. Commun., vol. 162, pp. 196–203, 2020, https://doi.org/10.1016/j.comcom.2020.04.050.

B. Han et al., “Grid-optimized UAV indoor path planning algorithms in a complex environment,” Int. J. Appl. Earth Obs. Geoinf., vol. 111, p. 102857, 2022, https://doi.org/10.1016/j.jag.2022.102857.

S. Xiao, X. Tan, and J. Wang, “A simulated annealing algorithm and grid map-based UAV coverage path planning method for 3D reconstruction,” Electronics, vol. 10, no. 7, p. 853, 2021, https://doi.org/10.3390/electronics10070853.

T. Musil, M. Petrl’ik, and M. Saska, “SphereMap: Dynamic Multi-Layer Graph Structure for Rapid Safety-Aware UAV Planning,” IEEE Robot. Autom. Lett., vol. 7, no. 4, pp. 11007–11014, 2022, https://doi.org/10.1109/LRA.2022.3195194.

P. Wang, H. Mutahira, J. Kim, and M. S. Muhammad, “ABA*--Adaptive Bidirectional A* Algorithm for Aerial Robot Path Planning,” IEEE Access, 2023, https://doi.org/10.1109/ACCESS.2023.3317918.

L. Jarin-Lipschitz, X. Liu, Y. Tao, and V. Kumar, “Experiments in adaptive replanning for fast autonomous flight in forests,” in 2022 International Conference on Robotics and Automation (ICRA), pp. 8185–8191, 2022, https://doi.org/10.1109/ICRA46639.2022.9812235.

M. F. Aslan, A. Durdu, and K. Sabanci, “Goal distance-based UAV path planning approach, path optimization and learning-based path estimation: GDRRT*, PSO-GDRRT* and BiLSTM-PSO-GDRRT,” Appl. Soft Comput., vol. 137, p. 110156, 2023, https://doi.org/10.1016/j.asoc.2023.110156.

A. Puente-Castro, D. Rivero, A. Pazos, and E. Fernandez-Blanco, “A review of artificial intelligence applied to path planning in UAV swarms,” Neural Comput. Appl., pp. 1–18, 2022, https://doi.org/10.1007/s00521-021-06569-4.

Y. Bai, H. Zhao, X. Zhang, Z. Chang, R. Jäntti and K. Yang, "Toward Autonomous Multi-UAV Wireless Network: A Survey of Reinforcement Learning-Based Approaches," in IEEE Communications Surveys & Tutorials, vol. 25, no. 4, pp. 3038-3067, 2023, https://doi.org/10.1109/COMST.2023.3323344.

S. Kuutti, R. Bowden, Y. Jin, P. Barber, and S. Fallah, “A survey of deep learning applications to autonomous vehicle control,” IEEE Trans. Intell. Transp. Syst., vol. 22, no. 2, pp. 712–733, 2020, https://doi.org/10.1109/TITS.2019.2962338.

J J. Wu et al., "An Adaptive Conversion Speed Q-Learning Algorithm for Search and Rescue UAV Path Planning in Unknown Environments," in IEEE Transactions on Vehicular Technology, vol. 72, no. 12, pp. 15391-15404, 2023, https://doi.org/10.1109/TVT.2023.3297837.

C. Chronis, G. Anagnostopoulos, E. Politi, G. Dimitrakopoulos and I. Varlamis, "Dynamic Navigation in Unconstrained Environments Using Reinforcement Learning Algorithms," in IEEE Access, vol. 11, pp. 117984-118001, 2023, https://doi.org/10.1109/ACCESS.2023.3326435.

J. Williams et al., "Online 3D Frontier-Based UGV and UAV Exploration Using Direct Point Cloud Visibility," 2020 IEEE International Conference on Multisensor Fusion and Integration for Intelligent Systems (MFI), pp. 263-270, 2020, https://doi.org/10.1109/MFI49285.2020.9235268.

J. W. Davis and J. Hachtel, “A* Search: What’s in a Name?,” Commun. ACM, vol. 63, no. 1, pp. 36–37, 2019, https://doi.org/10.1145/3326600.

A. Paredes, “Structural Bias in Heuristic Search (Student Abstract),” in Proceedings of the International Symposium on Combinatorial Search, vol. 16, no. 1, pp. 196–197, 2023, https://doi.org/10.1609/socs.v16i1.27311.

Z. Yu, X. Yu, T. Zhou, Y. Chen, Y. Liu, and B. Li, “ODIN: Object Density Aware Index for CkNN Queries over Moving Objects on Road Networks,” arXiv preprint arXiv:2312.12688, 2023, https://doi.org/10.48550/arXiv.2312.12688.

A. Sedeño-Noda and M. Colebrook, “A biobjective Dijkstra algorithm,” Eur. J. Oper. Res., vol. 276, no. 1, pp. 106–118, 2019, https://doi.org/10.1016/j.ejor.2019.01.007.

K. Wei, Y. Gao, W. Zhang, and S. Lin, “A modified Dijkstra’s algorithm for solving the problem of finding the maximum load path,” in 2019 IEEE 2nd International Conference on Information and Computer Technologies (ICICT), pp. 10–13, 2019, https://doi.org/10.1109/INFOCT.2019.8711024.

W. Li, L. Wang, A. Zou, J. Cai, H. He, and T. Tan, “Path planning for uav based on improved prm,” Energies, vol. 15, no. 19, p. 7267, 2022, https://doi.org/10.3390/en15197267.

Q. Jin, Q. Hu, P. Zhao, S. Wang, and M. Ai, “An Improved Probabilistic Roadmap Planning Method for Safe Indoor Flights of Unmanned Aerial Vehicles,” Drones, vol. 7, no. 2, p. 92, 2023, https://doi.org/10.3390/drones7020092.

Z. Xu, D. Deng, and K. Shimada, “Autonomous UAV exploration of dynamic environments via incremental sampling and probabilistic roadmap,” IEEE Robot. Autom. Lett., vol. 6, no. 2, pp. 2729–2736, 2021, https://doi.org/10.1109/LRA.2021.3062008.

S. Julius Fusic and R. Sitharthan, “Improved RRT* Algorithm-Based Path Planning for Unmanned Aerial Vehicle in a 3D Metropolitan Environment,” Unmanned Syst., pp. 1–17, 2023, https://doi.org/10.1142/S2301385024500225.

F. Kiani, A. Seyyedabbasi, R. Aliyev, M. U. Gulle, H. Basyildiz, and M. A. Shah, “Adapted-RRT: novel hybrid method to solve three-dimensional path planning problem using sampling and metaheuristic-based algorithms,” Neural Comput. Appl., vol. 33, no. 22, pp. 15569–15599, 2021, https://doi.org/10.1007/s00521-021-06179-0.

P. Luong, F. Gagnon, L.-N. Tran, and F. Labeau, “Deep reinforcement learning-based resource allocation in cooperative UAV-assisted wireless networks,” IEEE Trans. Wirel. Commun., vol. 20, no. 11, pp. 7610–7625, 2021, https://doi.org/10.1109/TWC.2021.3086503.

P. Horstrand, R. Guerra, A. Rodríguez, M. Díaz, S. López and J. F. López, "A UAV Platform Based on a Hyperspectral Sensor for Image Capturing and On-Board Processing," in IEEE Access, vol. 7, pp. 66919-66938, 2019, https://doi.org/10.1109/ACCESS.2019.2913957.

F. L. Sacomano Filho, A. C. Santos, A. Vié, and G. C. Krieger Filho, “A new robust modeling strategy for multi-component droplet heat and mass transfer in general ambient conditions,” Int. J. Heat Mass Transf., vol. 194, p. 123102, 2022, https://doi.org/10.1016/j.ijheatmasstransfer.2022.123102.

D. Van Huynh, T. Do-Duy, L. D. Nguyen, M.-T. Le, N.-S. Vo, and T. Q. Duong, “Real-time optimized path planning and energy consumption for data collection in unmanned ariel vehicles-aided intelligent wireless sensing,” IEEE Trans. Ind. Informatics, vol. 18, no. 4, pp. 2753–2761, 2021, https://doi.org/10.1109/TII.2021.3114358.