Call for Paper - January 2024 Edition
IJCA solicits original research papers for the January 2024 Edition. Last date of manuscript submission is December 20, 2023. Read More

Multi-UAV Path Planning using Modified Dijkstra's Algorithm

Print
PDF
 
Download Full Text
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 and Farhan Kapadia. Multi-UAV Path Planning using Modified Dijkstra's Algorithm. International Journal of Computer Applications 175(28):26-33, October 2020. BibTeX

@article{10.5120/ijca2020920816,
	author = {Dhruv Karve and Farhan Kapadia},
	title = {Multi-UAV Path Planning using Modified Dijkstra's Algorithm},
	journal = {International Journal of Computer Applications},
	issue_date = {October 2020},
	volume = {175},
	number = {28},
	month = {Oct},
	year = {2020},
	issn = {0975-8887},
	pages = {26-33},
	numpages = {8},
	url = {http://www.ijcaonline.org/archives/volume175/number28/31629-2020920816},
	doi = {10.5120/ijca2020920816},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, USA}
}

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

  1. Eman Alsafi and Soha S. Zaghloul (2017). Drone Route Planning for Military Image Acquisition Using Parallel Simulated Annealing.
  2. “Wing - X, the Moonshot Factory” [Online]. Available: https://x.company/projects/wing/
  3. “Amazon.com: Prime Air” [Online]. Available: https://www.amazon.com/Amazon-Prime-Air/b?ie=UTF8&node=8037720011
  4. Sahingoz, O. K. (2013). Generation of Bezier Curve-Based Flyable Trajectories for Multi-UAV Systems with Parallel Genetic Algorithm. Journal of Intelligent & Robotic Systems.
  5. 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).
  6. 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.
  7. 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.
  8. Gjorshevski, H., Trivodaliev, K., Kosovic, I. N., Kalajdziski, S., & Stojkoska, B. R. (2018). Dynamic Programming Approach for Drone Routes Planning.
  9. Sahana, S. K., & Jain, A. (2014). High Performance Ant Colony Optimizer (HPACO) for Travelling Salesman Problem (TSP).
  10. 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).
  11. Fan, D., & Shi, P. (2010). Improvement of Dijkstra’s algorithm and its application in route planning.
  12. Li Wenzheng, Liu Junjun,Yao Shunli (2019). An Improved Dijkstra’s Algorithm for Shortest Path Planning on 2D Grid Maps.
  13. Bozyigit, A., Alankus, G., & Nasiboglu, E. (2017). Public transport route planning: Modified dijkstra’s algorithm.
  14. Kang, H. I., Lee, B., & Kim, K. (2008). Path Planning Algorithm Using the Particle Swarm Optimization and the Improved Dijkstra Algorithm.
  15. Economou, J. T., Kladis, G., Tsourdos, A., & White, B. A. (2007). UAV optimum energy assignment using Dijkstra’s Algorithm. 2007 European Control Conference (ECC).
  16. “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

Keywords

Path Planning, Multi-UAVs, Dijkstra’s Algorithm, Drone Routing, Multi-objective Optimization, Charging Stations.