The week's pick
Reseach Article
Multi-UAV Path Planning using Modified Dijkstra's Algorithm
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 175 - Number 28 |
| Year of Publication: 2020 |
| Authors: Dhruv Karve, Farhan Kapadia |
10.5120/ijca2020920816
|
Dhruv Karve, Farhan Kapadia . Multi-UAV Path Planning using Modified Dijkstra's Algorithm. International Journal of Computer Applications. 175, 28 ( Oct 2020), 26-33. DOI=10.5120/ijca2020920816
Abstract
Unmanned Aerial Vehicles (UAVs), informally referred to as drones, are ubiquitous in various fields today. The widespread applications and popularity of drones arise from the fact that these automatic devices can cover large distances efficiently and without the need of an operator on board. However, to cover these large distances in an efficient manner, an efficacious algorithm is also necessary. In order to optimize not just the distance between the source and the destination but also satisfy various other constraints such as covering the maximum area possible using the least number of drones and visiting the closest charging stations to complete the journey within the battery life, a modified version of Dijkstra’s Algorithm has been used. There already exist algorithms to optimize the path of a drone but very few algorithms also take constraints such as energy cost and area maximization into account. This was the inspiration to take up this project; to devise an algorithm that satisfies the aforementioned constraints while also remaining pertinent to the main objective of multiple UAVs path optimization algorithms - distance and cost minimization.
References
- Eman Alsafi and Soha S. Zaghloul (2017). Drone Route Planning for Military Image Acquisition Using Parallel Simulated Annealing.
- “Wing - X, the Moonshot Factory” [Online]. Available: https://x.company/projects/wing/
- “Amazon.com: Prime Air” [Online]. Available: https://www.amazon.com/Amazon-Prime-Air/b?ie=UTF8&node=8037720011
- Sahingoz, O. K. (2013). Generation of Bezier Curve-Based Flyable Trajectories for Multi-UAV Systems with Parallel Genetic Algorithm. Journal of Intelligent & Robotic Systems.
- Sahingoz, O. K. (2013). Flyable path planning for a multi-UAV system with Genetic Algorithms and Bezier curves. 2013 International Conference on Unmanned Aircraft Systems (ICUAS).
- Wang, K., Yuan, B., Zhao, M., & Lu, Y. (2019). Cooperative route planning for the drone and truck in delivery services: A bi-objective optimisation approach.
- Moon, S., Oh, E., & Shim, D. H. (2012). An Integral Framework of Task Assignment and Path Planning for Multiple Unmanned Aerial Vehicles in Dynamic Environments.
- Gjorshevski, H., Trivodaliev, K., Kosovic, I. N., Kalajdziski, S., & Stojkoska, B. R. (2018). Dynamic Programming Approach for Drone Routes Planning.
- Sahana, S. K., & Jain, A. (2014). High Performance Ant Colony Optimizer (HPACO) for Travelling Salesman Problem (TSP).
- Risald, Mirino, A. E., & Suyoto. (2017). Best routes selection using Dijkstra and Floyd-Warshall algorithm. 2017 11th International Conference on Information & Communication Technology and System (ICTS).
- Fan, D., & Shi, P. (2010). Improvement of Dijkstra’s algorithm and its application in route planning.
- Li Wenzheng, Liu Junjun,Yao Shunli (2019). An Improved Dijkstra’s Algorithm for Shortest Path Planning on 2D Grid Maps.
- Bozyigit, A., Alankus, G., & Nasiboglu, E. (2017). Public transport route planning: Modified dijkstra’s algorithm.
- Kang, H. I., Lee, B., & Kim, K. (2008). Path Planning Algorithm Using the Particle Swarm Optimization and the Improved Dijkstra Algorithm.
- Economou, J. T., Kladis, G., Tsourdos, A., & White, B. A. (2007). UAV optimum energy assignment using Dijkstra’s Algorithm. 2007 European Control Conference (ECC).
- “Python Math: Distance between two points using latitude and longitude” [Online]. Available: https://www.w3resource.com/python-exercises/math/python-math-exercise-27.php?passed=passed
Index Terms
Keywords