Abstract
In the last years, the Flight Mechanics Research Group of Politecnico di Torino started a wide research activity, focused on exploration and implementation of path planning algorithms for commercial autopilots, typically adopted on unmanned vehicles. Different path planning approaches were implemented in a Matlab/Simulink based tool, generating waypoints sequences with four methods: geometric predefined trajectories, manual waypoints definition, automatic waypoints distribution (i.e. optimizing camera payload capabilities) and, finally, a comprehensive A*-based approach. The tool was also integrated with functions managing the maps used for planning. In this paper, two approaches to path planning in presence of orographic obstacles are detailed. The first algorithm is subdivided in three phases: the generation of a risk map associated with the ground orography, the transformation of the map in a digraph analyzed with the A* algorithm (to obtain the path with minimum risk/minimum distance) and finally the smoothing phase, to obtain a flyable waypoint sequence, realized with the Dubins curves. The structure of this method was defined and implemented, but its optimization is still in progress. The second algorithm is based on the same risk map, but optimizing polynomial curves with a genetic algorithm. This method produces a flyable waypoints sequence, minimizing a cost function reflecting path length and collision risk. An extension of this path solver, including aircraft performance constraints, was also considered. This method was tested on sample domains and its computational cost has still to be evaluated before the implementation in the tool.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
De Filippis, L., Guglieri, G., Quagliotti, F.: Flight Analysis and Design for Mini-UAVs. XX AIDAA Congress, Milano, Italy (2009)
Jun, M., D’R.: Path Planning for Unmanned Aerial Vehicles in Uncertain and Adversarial Environments, Models, Applications and Algorithms. Kluwer Academic Press (2002)
Kingston, D.K.: Implementation Issues of real-time trajectory generation on small UAVs. MS Dissertation, Brigham Young University, USA (2004)
Gu, D.W., Postlethwaite, I., Kim, Y.: A comprehensive study on flight path selection algorithms. IEE Seminar on Target Tracking: Algorithms and Applications. Birmingham, UK (2006)
Carroll, D.L.: Chemical laser modeling with genetic algorithms. AIAA J. 34(2), 338–346 (1996)
Guglieri, G., Quagliotti, F., Speciale, G.: Optimal trajectory tracking for an autonomous Uav. Autom. Control Aerosp. 1(1) (2008)
Bertuccelli, L.F., How, J.P.: Robust UAV search for environmentas with imprecise probability maps. IEEE Conference of Decision and Control. Seville, Spain (2005)
Pfeiffer, B., Batta, R., Klamroth, K., Nagi, R.: Path planning for UAVs in the presence of threat zones using probabilistic modelling. Handbook of Military Industrial Engineering. Taylor and Francis, USA (2008)
Erwig, M.: The graph Voronoi diagram with applications. Networks. 36(3) (2000)
Chandler, P.R., Rasmussen, S., Patcher, M.: UAV cooperative path planning. AIAA Guidance, Navigation and Control Conference. Denver (2000)
Bortoff, S.A.: Path planning for UAVs. Proc. of the American Control Conference. Chicago (2000)
Zabarankin, M., Uryasev, S., Pardalos, P.: Optimal risk path algorithm. Technical Report 2001-4, Department of Industrial and Systems Engineering. University of Florida, USA (2001)
Boissonnat, J.D., Cèrèzo, A., Leblond, J.: Shortest paths of bounded curvature in the plane. J. Intell. Robot. Syst. 11(1–2) (1994)
Reeds, J.A, Shepp, L.A.: Optimal path for a car that goes both forwards and backwards. Pac. J. Math. 145(2) (1990)
Sussmann, H.J., Tang, W.: Shortest Paths for the Reeds-Shepp Car: A Worked Out Example of the Use of Geometric Technique in Nonlinear Optimal Control, Report SYCON-91-10. Rutgers University (1991)
Ma, X., Castanon, D.A.: Receding horizon planning for dubins traveling salesman problems. IEEE Conference on Decision and Control. San Diego (2006)
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 (1957)
Capozzi, B.J.: Evolution-based Path planning and management for autonomous UAVs. Ph.D. Dissertation, University of Washington, USA (2001)
Nikolos, I.K., Tsourveloudis, N.C., Valavanis, K.P.: Evolutionary algorithm based 3-D path planner for UAV navigation. IEEE Trans. Syst. Man Cybern., Part B, Cybern. 33(6) (2003)
Chitsaz, H., LaValle, S.M.: Time-optimal paths for a dubins airplane. IEEE Conference on Decision and Control. New Orleans, USA (2007)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
De Filippis, L., Guglieri, G. & Quagliotti, F. A Minimum Risk Approach for Path Planning of UAVs. J Intell Robot Syst 61, 203–219 (2011). https://doi.org/10.1007/s10846-010-9493-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10846-010-9493-9