Abstract
This paper presents a risk-aware path planning strategy for Unmanned Aerial Vehicles in urban environments. The aim is to compute an effective path that minimizes the risk to the population, thus enforcing safety of flight operations over inhabited areas. To quantify the risk, the proposed approach uses a risk-map that associates discretized locations of the space with a suitable risk-cost. Path planning is performed in two phases: first, a tentative path is computed off-line on the basis on the information related to static risk factors; then, using a dynamic risk-map, an on-line path planning adjusts and adapts the off-line path to dynamically arising conditions. Off-line path planning is performed using riskA*, an ad-hoc variant of the A* algorithm, which aims at minimizing the risk. While off-line path planning has no stringent time constraints for its execution, this is not the case for the on-line phase, where a fast response constitutes a critical design parameter. We propose a novel algorithm called Borderland, which uses the check and repair approach to rapidly identify and adjust only the portion of path involved by the inception of relevant dynamical changes in the risk factor. After the path planning, a smoothing process is performed using Dubins curves. Simulation results confirm the suitability of the proposed approach.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Buniyamin, N., Wan Ngah, W., Sariff, N., Mohamad, Z.: A simple local path planning algorithm for autonomous mobile robots. Int. J. Syst. Appl. Eng. Dev. 5(2), 151–159 (2011)
Cai, G., Dias, J., Seneviratne, L.: A survey of small-scale unmanned aerial vehicles: recent advances and future development trends. Unmanned Sys. 2(02), 175–199 (2014)
Clothier, R.A., Walker, R.A., Fulton, N., Campbell, D.A.: A casualty risk analysis for Unmanned Aerial System (UAS) operations over inhabited areas. In: AIAC12, Twelfth Australian International Aerospace Congress, 2nd Australasian Unmanned Air Vehicles Conference, pp. 1–15 (2007)
Dalamagkidis, K., Valavanis, K., Piegl, L.A.: On integrating unmanned aircraft systems into the national airspace system: issues, challenges, operational restrictions, certification, and recommendations, vol. 54. Springer Science & Business Media (2011)
De Filippis, L., Guglieri, G., Quagliotti, F.: A minimum risk approach for path planning of UAVs. J. Intell. Robot. Syst. 61(1), 203–219 (2011)
De Filippis, L., Guglieri, G., Quagliotti, F.: Path planning strategies for UAVs in 3d environments. J. Intell. Robot. Syst. 65(1), 247–264 (2012)
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1(1), 269–271 (1959)
Dubins, L.E.: On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. Am. J. Math. 79(3), 497–516 (1957)
Ferguson, D., Kalra, N., Stentz, A.: Replanning with RRTs. In: Proceedings 2006 IEEE International Conference on Robotics and Automation, 2006. ICRA 2006, pp 1243–1248 (2006)
Feyzabadi, S., Carpin, S.: Risk-aware path planning using hirerachical constrained markov decision processes. In: 2014 IEEE International Conference on Automation Science and Engineering (CASE), pp. 297–303. IEEE (2014)
Goerzen, C., Kong, Z., Mettler, B.: A survey of motion planning algorithms from the perspective of autonomous UAV guidance. In: Selected Papers from the 2nd International Symposium on UAVs, Reno, Nevada, USA June 8–10, 2009, pp. 65–100. Springer (2009)
Guglieri, G., Lombardi, A., Ristorto, G.: Operation oriented path planning strategies for RPAS. Am. J. Sci. Tech. 2(6), 1–8 (2015)
Guglieri, G., Ristorto, G.: Safety assessment for light remotely piloted aircraft systems. In: INAIR 2016 - International Conference on Air Transport, vol. 1, pp. 1–7 (2016)
Hansen, K.D., la Cour-Harbo, A.: Waypoint planning with Dubins curves using genetic algorithms. In: Control Conference (ECC), 2016 European, pp. 2240–2246. IEEE (2016)
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)
Islam, F., Narayanan, V., Likhachev, M.: Dynamic multi-heuristic A. In: 2015 IEEE International Conference on Robotics and Automation (ICRA), pp. 2376–2382. IEEE (2015)
Islam, F., Narayanan, V., Likhachev, M.: A*-connect: bounded suboptimal bidirectional heuristic search. In: 2016 IEEE International Conference On Robotics and Automation (ICRA), pp. 2752–2758. IEEE (2016)
Jensen, O.B.: Drone city-power, design and aerial mobility in the age of smart cities. Geol. Helv. 71(2), 67 (2016)
Karakaya, S., Ocak, H., Küçükyildiz, G.: A bug-based local path planning method for static and dynamic environments. In: International Symposium on Innovative Technologies in Engineering and Science, pp 846–855. Valencia, Spain (2015)
Karaman, S., Frazzoli, E.: Incremental sampling-based algorithms for optimal motion planning. Robot Sci. Syst. VI 104(2), 1–20 (2010)
Karaman, S., Frazzoli, E.: Optimal kinodynamic motion planning using incremental sampling-based methods. In: 2010 49th IEEE Conference on Decision and Control (CDC), pp. 7681–7687. IEEE (2010)
Kavraki, L.E., Svestka, P., Latombe, J.C., Overmars, M.H.: Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robot. Autom. 12(4), 566–580 (1996)
la Cour-Harbo, A.: Mass threshold for ‘harmless’ drones. Int. J. Micro Air Veh. 9(2), 77–92 (2017)
la Cour-Harbo, A.: Quantifying ground impact fatality rate for small unmanned aircraft. J. Intell. Robot. Syst. 1–18. https://doi.org/10.1007/s10846-018-0853-1 (2018)
LaValle, S.M.: Rapidly-exploring random trees: a new tool for path planning (1998). TR 98-11, Computer Science Dept., Iowa State University
LaValle, S.M.: Planning algorithms. Cambridge University Press, Cambridge (2006)
Likhachev, M., Gordon, G.J., Thrun, S.: Ara*: anytime A* with provable bounds on sub-optimality. In: Advances in Neural Information Processing Systems, pp. 767–774 (2004)
Lin, Y., Saripalli, S.: Path planning using 3D Dubins curve for unmanned aerial vehicles. In: 2014 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 296–304. IEEE (2014)
Lin, Y., Saripalli, S.: Sampling-based path planning for UAV collision avoidance. IEEE Trans. Intell. Transp. Syst. 18(11), 3179–3192 (2017)
Lumelsky, V.J., Stepanov, A.A.: Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape. Algorithmica 2(1–4), 403–430 (1987)
Mohammed, F., Idries, A., Mohamed, N., Al-Jaroodi, J., Jawhar, I.: Uavs for smart cities: opportunities and challenges. In: 2014 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 267–273. IEEE (2014)
Murphy, R.: Introduction to AI Robotics. MIT Press, Cambridge (2000)
Pereira, A.A., Binney, J., Hollinger, G.A., Sukhatme, G.S.: Risk-aware path planning for autonomous underwater vehicles using predictive ocean models. J. Field Rob. 30(5), 741–762 (2013)
Primatesta, S., Capello, E., Antonini, R., Gaspardone, M., Guglieri, G., Rizzo, A.: A cloud-based framework for risk-aware intelligent navigation in urban environments. In: 2017 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 447–455. IEEE (2017)
Quigley, M., Conley, K., Gerkey, B., Faust, J., Foote, T., Leibs, J., Wheeler, R., Ng, A.Y.: Ros: an open-source robot operating system. In: ICRA Workshop on Open Source Software, vol. 3, p. 5 (2009)
Rathbun, D., Kragelund, S., Pongpunwattana, A., Capozzi, B.: An evolution based path planning algorithm for autonomous motion of a UAV through uncertain environments. In: The 21st Digital Avionics Systems Conference, 2002. Proceedings, vol. 2, pp. 8D2–8D2. IEEE (2002)
Rudnick-Cohen, E., Herrmann, J.W., Azarm, S.: Risk-based path planning optimization methods for unmanned aerial vehicles over inhabited areas. J. Comput. Inf. Sci. Eng. 16(2), 21004–21010 (2016)
Savkin, A.V., Huang, H.: The problem of minimum risk path planning for flying robots in dangerous environments. In: 2016 35th Chinese Control Conference (CCC), pp. 5404–5408. IEEE (2016)
Silva Arantes, J.D., Silva Arantes, M.D., Motta Toledo, C.F., Júnior, O.T., Williams, B.C.: Heuristic and genetic algorithm approaches for UAV path planning under critical situation. Int. J. Artif. Intell. Tools 26(01), 1760008 (2017)
Stentz, A.: Optimal and efficient path planning for unknown and dynamic environments. Tech. rep., DTIC Document (1993)
Sujit, P., Saripalli, S., Sousa, J.B.: Unmanned aerial vehicle path following: a survey and analysis of algorithms for fixed-wing unmanned aerial vehicles. IEEE Control. Syst. 34(1), 42–59 (2014)
Weiß, B., Naderhirn, M., del Re, L.: Global real-time path planning for UAVs in uncertain environment. In: Computer Aided Control System Design, 2006 IEEE International Conference on Control Applications, 2006 IEEE International Symposium on Intelligent Control, 2006 IEEE, pp. 2725–2730. IEEE (2006)
Wen, N., Su, X., Ma, P., Zhao, L., Zhang, Y.: Online UAV path planning in uncertain and hostile environments. Int. J. Mach. Learn. Cybern. 8(2), 469–487 (2017)
Wzorek, M., Doherty, P.: Reconfigurable path planning for an autonomous unmanned aerial vehicle. In: International Conference on Hybrid Information Technology, 2006. ICHIT’06, vol. 2, pp. 242–249. IEEE (2006)
Yang, L., Qi, J., Xiao, J., Yong, X.: A literature review of UAV 3D path planning. In: 2014 11th World Congress on Intelligent Control and Automation (WCICA), pp. 2376–2381. IEEE (2014)
Zhang, B., Mao, Z., Liu, W., Liu, J.: Geometric reinforcement learning for path planning of UAVs. J. Intell. Robot. Syst. 77(2), 391–409 (2015)
Acknowledgments
This work was supported by a fellowship from TIM, by the Siebel Energy Institute, and by Compagnia di San Paolo.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Primatesta, S., Guglieri, G. & Rizzo, A. A Risk-Aware Path Planning Strategy for UAVs in Urban Environments. J Intell Robot Syst 95, 629–643 (2019). https://doi.org/10.1007/s10846-018-0924-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10846-018-0924-3