In this article, an algorithm for three-dimensional path generation and tracking for unmanned air vehicles in the presence of no-fly zones is proposed. The algorithm is based on a local optimization procedure aimed to find the shortest path between the waypoints in compliance with all path constraints. Vehicle structural and envelope limitations are accounted for by simple geometric constraints such as minimum curvature radius and flight path angle limitations, while no-fly zones are defined as cylindrical objects with infinite altitude. The algorithm is simple and it has a limited computational burden, at most quadratic with the number of zones to avoid. This makes the algorithm very suitable for real-time applications even in case of a high number of forbidden zones. Algorithm effectiveness has been demonstrated by means of numerical simulations in scenarios including the presence of no-fly zones not known before flight (for instance, in the case of sudden changes of weather conditions and/or detection of new fixed obstacles).
Gu DW, Postlethwaite I and Kim Y. A comprehensive study on flight path selection algorithms. In: Proceedings of the IEE seminar on target tracking: algorithms and applications, Birmingham, UK, 7–8 March 2006. New York: IEEE, pp.77–90.
3.
LaValleSM. Planning algorithms, Cambridge, MA: Cambridge University Press, 2006.
4.
ChosetHLynchKMHutchinsonS. Principles of robot motion: theory, algorithms, and implementations, Cambridge, MA: MIT Press, 2005.
5.
HwangYKAhujaN. A potential field approach to path planning. IEEE Trans Rob Autom1992; 8(1): 23–32.
6.
KavraluLESvestkaPLatombeJ. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans Rob Autom1996; 12(4): 566–580.
7.
Belghith K, Kabanza F, Hartman L, et al. Anytime dynamic path-planning with flexible probabilistic roadmaps. In: Proceedings of the 2006 IEEE international conference on robotics and automation, Orlando, FL, 15–19 May 2006. New York: IEEE, pp.2372–2377.
8.
Kothari M, Postlethwaite I and Gu D. Multi-UAV path planning in obstacle rich environments using rapidly-exploring random trees. In: Proceedings of the 48th IEEE conference on decision and control and 28th chinese control conference CDC/CCC 2009, Shanghai, China, 15–18 December 2009. New York: IEEE, pp.3069–3074.
9.
Amin JN, Boskovic JD and Mehra RK. A fast and efficient approach to path planning for unmanned vehicles. In: Proceedings of the AIAA guidance, navigation and control conference, Keystone, CO, 21–24 August 2006. Reston, VA: AIAA.
10.
Pettersson PO and Doherty P. Probabilistic roadmap based path planning for an autonomous unmanned aerial vehicle. In: Proceedings of the workshop on connecting planning and theory with practice, ICAPS 2004, Whistler, British Columbia, Canada, 3–7 June 2004.
11.
Omar R and Gu D-W. Visibility line based methods for UAV path planning. In: Proceedings of the ICROS-SICE international joint conference. ICROS-SICE 2009, Fukuoka, Japan, 18–21 August 2009. New York: IEEE, pp.3176–3181.
12.
Huang H and Chung S. Dynamic visibility graph for path planning. In: Proceedings of the IEEE/RSJ international conference on intelligent robots and systems, Sendai, Japan, vol. 3, 28 September – 2 October 2004. New York: IEEE, pp.2813–2818.
13.
Reif JH. Complexity of the mover’s problem and generalizations. In: Proceedings of the 20th IEEE symposium on the foundations of computer science, San Juan, Puerto Rico, 29–31 October 1979. New York: IEEE, pp.421–427.
14.
Corraro F. On-line trajectory planning algorithms for unmanned aerial vehicles. PhD Thesis, Un. Parthenope, 2011.
15.
AmbrosinoGAriolaMCiniglioU. Path generation and tracking in 3-D for UAVs. IEEE Trans Control Syst Technol2009; 17(4): 980–988.
16.
DubinsLE. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. Amer J Math1957; 79(3): 497–516.
17.
JorrisTRCobbRG. Multiple method 2-D trajectory optimization satisfying waypoints and no-fly zone constraints. AIAA J Guid Control Dyn2008; 31(3): 543–553.
18.
Jorris T. Common aero vehicle autonomous reentry trajectory optimization satisfying waypoint and no-fly zone constraints. AFIT/DS/ENY/07-04, PhD Thesis, Air Force Institute of Technology (AETC), Wright-Patterson AFB, OH, September 2007.
19.
TempoRBaiEWDabbeneF. Probabilistic robustness analysis: explicit bounds for the minimum number of samples. Syst Control Lett1997; 30: 237–242.
20.
Luongo S, Carbone C, Corraro F, et al. An optimal 3D analytical solution for collision avoidance between aircraft. In: Proceedings of the IEEE aerospace conference 2009, Big Sky, MT, USA, 7–14 March 2009. New York: IEEE, pp.1–9.
21.
Luongo S, Corraro F, Ciniglio U, et al. A novel 3D analytical algorithm for autonomous collision avoidance considering cylindrical safety bubble. In: Proceedings of the IEEE aerospace conference 2010, Big Sky, MT, USA, 6–13 March 2010. New York: IEEE, pp.1–13.
22.
EtkinB. Dynamics of atmospheric flight, New York, NY: Wiley, 1972.
23.
McCormickBW. Aerodynamics, aeronautics and flight mechanics, New York, NY: Wiley, 1994.
24.
Pettersen KY and Lefeber E. Way-point tracking control of ships. In: Proceedings of the 40th IEEE conference on decision control, Orlando, FL, 4–7 December 2001. New York: IEEE, pp.940–945.
