Abstract
This paper investigates the offline path planning problem of unmanned aerial vehicles (UAVs) for surveillance mission in complex urban environments. A new idea by coupling the differential evolution (DE) with A* algorithm is suggested to address the problem in large urban areas with narrow street and infrastructure of built environment. The proposed method consists of two phase: the first phase adopts DE to divide the straight line between source and destination into several smaller regions, while the second one utilizes A* for each region to find a collision-free and shortest path in parallel. In order to assess the efficiency of the suggested algorithm, a real-world scenario is examined. Evaluations exhibited promising results with proper accuracy and minimum computational time.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
(Atsushi Sakai et al. https://github.com/AtsushiSakai/PythonRobotics).
References
Alajlan, M., Koubâa, A., Châari, I., Bennaceur, H., Ammar, A.: Global path planning for mobile robots in large-scale grid environments using genetic algorithms. In: 2013 International Conference on Individual and Collective Behaviors in Robotics (ICBR), pp. 1–8. IEEE (2013)
Bauso, D., Giarré, L., Pesenti, R.: Multiple UAV cooperative path planning via neuro-dynamic programming. In: 2004 43rd IEEE Conference on Decision and Control (CDC) (IEEE Cat. No. 04CH37601), vol. 1, pp. 1087–1092. IEEE (2004)
Brintaki, A.N., Nikolos, I.K.: Coordinated UAV path planning using differential evolution. Oper. Res. 5(3), 487–502 (2005)
Canny, J.: The Complexity of Robot Motion Planning. MIT Press, Cambridge (1988)
Cekmez, U., Ozsiginan, M., Sahingoz, O.K.: A UAV path planning with parallel ACO algorithm on CUDA platform. In: 2014 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 347–354. IEEE (2014)
Chen, Y., Luo, G., Mei, Y., Yu, J., Su, X.: UAV path planning using artificial potential field method updated by optimal control theory. In. J. Syst. Sci. 47(6), 1407–1420 (2016)
Choi, Y., Choi, Y., Briceno, S., Mavris, D.N.: Energy-constrained multi-UAV coverage path planning for an aerial imagery mission using column generation. J. Intell. Robot. Syst. 97(1), 125–139 (2019). https://doi.org/10.1007/s10846-019-01010-4
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische mathematik 1(1), 269–271 (1959)
Gammell, J.D., Srinivasa, S.S., Barfoot, T.D.: Informed RRT*: optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic. In: 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2997–3004. IEEE (2014)
Ghambari, S., Lepagnot, J., Jourdan, L., Idoumghar, L.: A comparative study of meta-heuristic algorithms for solving UAV path planning. In: 2018 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 174–181, November 2018. https://doi.org/10.1109/SSCI.2018.8628807
Goerzen, C., Kong, Z., Mettler, B.: A survey of motion planning algorithms from the perspective of autonomous UAV guidance. J. Intell. Robot. Syst. 57(1–4), 65 (2010)
Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100–107 (1968)
Kavraki, L., Svestka, P., Overmars, M.H.: Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robot. Autom. 12, 566–580 (1994)
LaValle, S.M., Kuffner Jr., J.J.: Randomized kinodynamic planning. Int. J. Robot. Res. 20(5), 378–400 (2001)
Li, J., Sun, X.: A route planning’s method for unmanned aerial vehicles based on improved a-star algorithm. Acta Armamentarii 7, 788–792 (2008)
López-Ibánez, M., Dubois-Lacoste, J., Stützle, T., Birattari, M.: The irace package, iterated race for automatic algorithm configuration. Technical report, TR/IRIDIA/2011-004, IRIDIA, Université Libre de Bruxelles (2011)
Ji, X.-T., Xie, H.-B., Zhou, L., Jia, S.-D.: Flight path planning based on an improved genetic algorithm. In: 2013 Third International Conference on Intelligent System Design and Engineering Applications, pp. 775–778. IEEE (2013)
Yang, P., Tang, K., Lozano, J.A., Cao, X.: Path planning for single unmanned aerial vehicle by separately evolving waypoints. IEEE Trans. Robot. 31(5), 1130–1146 (2015)
Zhang, X., Duan, H.: An improved constrained differential evolution algorithm for unmanned aerial vehicle global route planning. Appl. Soft Comput. 26, 270–284 (2015)
Zhang, X., Chen, J., Xin, B., Fang, H.: Online path planning for UAV using an improved differential evolution algorithm. IFAC Proc. Volumes 44(1), 6349–6354 (2011)
Zhao, Y., Zheng, Z., Liu, Y.: Survey on computational-intelligence-based UAV path planning. Knowl.-Based Syst. 158, 54–64 (2018)
Zhu, Y., et al.: Target-driven visual navigation in indoor scenes using deep reinforcement learning. In: 2017 IEEE International Conference on Robotics and Automation (ICRA), pp. 3357–3364. IEEE (2017)
Acknowledgment
This work is part of a project funded by the French Agence Nationale de la Recherche under grant number ANR-16-SEBM-0004.
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Ghambari, S., Idoumghar, L., Jourdan, L., Lepagnot, J. (2020). A Hybrid Evolutionary Algorithm for Offline UAV Path Planning. In: Idoumghar, L., Legrand, P., Liefooghe, A., Lutton, E., Monmarché, N., Schoenauer, M. (eds) Artificial Evolution. EA 2019. Lecture Notes in Computer Science(), vol 12052. Springer, Cham. https://doi.org/10.1007/978-3-030-45715-0_16
Download citation
DOI: https://doi.org/10.1007/978-3-030-45715-0_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-45714-3
Online ISBN: 978-3-030-45715-0
eBook Packages: Computer ScienceComputer Science (R0)