DIJKSTRA ALGORITHM USING UAV PATH PLANNING

Abstract

The use of unmanned aerial vehicles (UAV) is increasing today. UAVs can be divided into two parts, which are remote controlled and can travel automatically due to a certain battery problem. Recent research has also focused on the development and application of new algorithms to autonomously control these vehicles and determine the shortest flight paths. Together with these researches, UAVs are used in many civil activities such as weather forecasts, environmental studies and traffic control. Three-dimensional (3D) path planning is an important issue for autonomously moving UAVs. The shortest path for Unmanned Aerial Vehicles (UAV) is determined by using two-dimensional (2D) path planning algorithms using the obstacles in the environment, and allows UAVs to perform their environmental tasks as soon as possible. The purpose of this study is to determine the shortest path to the target point and avoiding obstacles for UAVs using the Dijkstra algorithm. It was developed to evaluate the arrival time of the UAVs in the path planning algorithm with the simulation performed in the MATLAB program. In this study, the obstacles were defined for the purpose of the building with different heights and different widths and 2D and 3D models were carried out, assuming that the UAV flies at certain heights. In addition, the flight of the UAVs in the route planning determined in the real applications was carried out and the data such as battery consumption, amount of battery spent, speed, amount of travel were examined.

Keywords

• UAV
• 2D and 3D
• path planning
• Dijkstra algorithm

DIJKSTRA ALGORİTMASI KULLANILARAK İHA YOL PLANLAMASI

Abstract

İnsansız hava araçlarının (İHA) kullanımı günümüzde giderek artmaktadır. İHA’lar uzaktan kumandalı ve belirli bir batarya probleminden dolayı otomatik olarak seyahat edebilen olmak üzere iki kısma ayrılabilirler. Son dönemde gerçekleştirilen araştırmalar, bu araçları otonom bir şekilde kontrol etmek ve en kısa uçuş yollarını belirlemek için yeni algoritmaların geliştirilmesi ve uygulanması konularına da odaklanmışlardır. Bu araştırmalarla birlite kullanım alanı olarak İHA'lar hava tahminleri, çevre çalışmaları ve trafik kontrolü gibi birçok sivil faaliyette kullanılmaktadır. Otonom hareket eden İHA’lar için üç boyutlu (3D) yol planlaması önemli bir konudur. İnsansız Hava Araçları (İHA) için en kısa yol, çevredeki engelleri kullanarak iki boyutlu (2D) yol planlama algoritmaları kullanılarak belirlenir ve İHA’ların çevre görevlerini mümkün olan en kısa sürede yerine getirmelerine olanak tanır. Bu çalışmanın amacı, Dijkstra algoritması kullanılarak İHA’lar için engellerden kaçınarak ve hedef noktasına giden en kısa yolu belirlemektir. MATLAB programında gerçekleştirilen simülasyon ile yol planlama algoritmasında İHA’ların hedefe varış zamanını değerlendirmek için geliştirilmiştir. Bu çalışma farklı yükseklik ve farklı ene sahip olan bina amacıyla engeller tanımlanmış ve İHA’nın belirli yüksekliklerde uçtuğu kabul edilerek 2D ve 3D modellemeleri gerçekleştirilmiştir. Ayrıca İHA’ların gerçek uygulamalarda belirlenen yol planlamalarında uçuşu gerçekleştirilerek pil tüketimi, harcanan pil miktarı, hızı, alınan yol miktarı gibi verilerde incelenmiştir.

Keywords

• İnsansız hava araçları (İHA)
• 2D ve 3D
• yol planlama
• Dijkstra algoritması

References

1. Arıca, N., Cicibaş, H., & Demir, K. A. (2012). İnsansız Hava Araçları için Çok Kriterli Güzergâh Planlama Modeli. Journal of Defense Sciences/Savunma Bilmleri Dergisi, 11(1).
2. Cabreira, T. M., Brisolara, L. B., & Ferreira Jr, P. R. (2019). Survey on coverage path planning with unmanned aerial vehicles. Drones, 3(1), 4.
3. Dhulkefl, E. J., & Durdu, A. (2019). Path planning algorithms for unmanned aerial vehicles. International Journal of Trend in Scientific Research and Development (ijtsrd), 359-362.
4. Foo, J. L., Knutzon, J., Oliver, J., & Winer, E. (2006). Three-dimensional path planning of unmanned aerial vehicles using particle swarm optimization. Paper presented at the 11th AIAA/ISSMO multidisciplinary analysis and optimization conference.
5. Fusic, S. J., Ramkumar, P., & Hariharan, K. (2018). Path planning of robot using modified dijkstra Algorithm. Paper presented at the 2018 National Power Engineering Conference (NPEC).
6. Galvez, R. L., Dadios, E. P., & Bandala, A. A. (2014). Path planning for quadrotor UAV using genetic algorithm. Paper presented at the 2014 International Conference on Humanoid, Nanotechnology, Information Technology, Communication and Control, Environment and Management (HNICEM).
7. Gao, X.-G., Fu, X.-W., & Chen, D.-Q. (2005). A genetic-algorithm-based approach to UAV path planning problem. Paper presented at the Proceedings of the WSEAS International Conference on Simulation, Modeling, and Optimization.
8. Jevtić, A., Andina, D., Jaimes, A., Gomez, J., & Jamshidi, M. (2010). Unmanned aerial vehicle route optimization using ant system algorithm. Paper presented at the 2010 5th International Conference on System of Systems Engineering.

9. Kim, I., Shin, S., Wu, J., Kim, S.-D., & Kim, C.-G. (2017). Obstacle avoidance path planning for UAV using reinforcement learning under simulated environment. Paper presented at the IASER 3rd International Conference on Electronics, Electrical Engineering, Computer Science, Okinawa.
10. Lei, W., LI, B.-j., YIN, Z.-h., Cheng, Z., Xin, Z., & CHU, Y.-n. (2017). An Improved Artificial Potential Field for Unmanned Aerial Vehicles Path Planning. DEStech Transactions on Computer Science and Engineering(cst).
11. Medeiros, F. L. L., & Da Silva, J. D. S. (2010). A Dijkstra algorithm for fixed-wing UAV motion planning based on terrain elevation. Paper presented at the Brazilian Symposium on Artificial Intelligence.
12. Mozaffari, M., Saad, W., Bennis, M., & Debbah, M. (2016). Optimal transport theory for power-efficient deployment of unmanned aerial vehicles. Paper presented at the 2016 IEEE international conference on communications (ICC).
13. Omar, R., & Gu, D. (2010). 3D Path Planning for Unmanned Aerial Vehicles using Visibility Line based Method. Paper presented at the ICINCO (1).
14. Singh, Y., Sharma, S., Sutton, R., & Hatton, D. (2018). Towards use of dijkstra algorithm for optimal navigation of an unmanned surface vehicle in a real-time marine environment with results from artificial potential field. TransNav, International Journal on Marine Navigation and Safety od Sea Transportation, 12(1).
15. Tong, H. (2012). Path planning of UAV based on Voronoi diagram and DPSO. Procedia Engineering, 29, 4198-4203.
16. Tseng, F.-H. (2011). Li-Der Chou, and Han-Chieh Chao.". A survey of black hole attacks in wireless mobile ad hoc networks, 1-16.
17. Vladareanu, V., Boscoianu, E.-C., Sandru, O.-I., & Boscoianu, M. (2016). Development Of Intelligent Algorithms For Uav Planning And Control. Scientific Research & Education in the Air Force-AFASES, 1, 221-226.
18. Wang, H., Lyu, W., Yao, P., Liang, X., & Liu, C. (2015). Three-dimensional path planning for unmanned aerial vehicle based on interfered fluid dynamical system. Chinese Journal of Aeronautics, 28(1), 229-239.
19. Wu, T.-F., Tsai, P.-S., Hu, N.-T., & Chen, J.-Y. (2017). Combining turning point detection and Dijkstra’s algorithm to search the shortest path. Advances in Mechanical Engineering, 9(2), 1687814016683353.
20. Wzorek, M., & Doherty, P. (2006). Reconfigurable path planning for an autonomous unmanned aerial vehicle. Paper presented at the 2006 International Conference on Hybrid Information Technology.
21. Yang, L., Qi, J., Song, D., Xiao, J., Han, J., & Xia, Y. (2016). Survey of robot 3D path planning algorithms. Journal of Control Science and Engineering, 2016.
22. Yong-Fei, M., Luo, Z., & Luo-Sheng, X. (2013). Application of improved sparse A* algorithm in UAV path planning. Information Technology Journal, 12(17), 4058.
23. Zhuoning, D., Rulin, Z., Zongji, C., & Rui, Z. (2010). Study on UAV path planning approach based on fuzzy virtual force. Chinese Journal of Aeronautics, 23(3), 341-350.