Comparing fuel-optimal and shortest paths with obstacle avoidance
Abstract
This paper presents a comparison of fuel-optimal and shortest paths of an unmanned combat aerial vehicle (UCAV) with obstacle avoidance. A nonlinear constrained optimization algorithm is applied to obtain the optimal paths. An initial value problem (IVP) and an inverse-dynamics approach are used separately to determine optimal paths for various scenarios and in order to reduce computation time. While inputs of the optimization algorithm are discrete control variables in the IVP method, discrete state variables are used as inputs in the inverse-dynamics method. The minimized path segments of the geometrical model provide an initial estimation of the heading angle for the aircraft flight mechanics model. The number of variables used by the optimization algorithm has a direct effect upon the optimal accuracy; however, the computation time is inversely proportional to the number of the variables. Simulation results demonstrate that the proposed IVP method effectively converges to optimal solutions.
Keyword : fuel-optimal path, shortest path, geometric approach, initial value problem, inverse dynamics, fmincon, obstacle avoidance
How to Cite
Cihan, I. H. (2022). Comparing fuel-optimal and shortest paths with obstacle avoidance. Aviation, 26(2), 79–88. https://doi.org/10.3846/aviation.2022.16878
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
Albert, A., Leira, F. S., & Imsland, L. S. (2017). UAV path planning using MILP with experiments. Modelling Identification and Control Journal, 38(1), 21–32. https://doi.org/10.4173/mic.2017.1.3
Ardema, M. D., & Asuncion, B. C. (2009). Flight path optimization at constant altitude. In Variational analysis and aerospace engineering. Springer. https://doi.org/10.1007/978-0-387-95857-6_2
Bai, M., Yang, W., Song, D., Kosuda, M., Szabo, S., Lipovsky, P., & Kasaei, A. (2020). Research on energy management of hybrid unmanned aerial vehicles to improve energy-saving and emission reduction performance. International Journal of Environmental Research and Public Health, 17(8), 2917. https://doi.org/10.3390/ijerph17082917
Bortoff, S. A. (2000, June 28–30). Path planning for UAVs. In Proceedings of the 2000 American Control Conference (IEEE Cat. No. CH36334) (Vol. 1, pp. 364–368). Chicago, IL, USA. https://doi.org/10.1109/ACC.2000.878915
Brandt, S. A., Bertin, J. J., Stiles, R. J., & Whitford, R. (2004). Introduction to aeronautics: A design perspective. American Institute of Aeronautics and Astronautics. https://doi.org/10.2514/4.862007
Cafieri, S., & Durand, N. (2014). Aircraft deconfliction with speed regulation: New models from mixed-integer optimization. Journal of Global Optimization, 58(4), 613–629. https://doi.org/10.1007/s10898-013-0070-1
Call, B. R. (2006). Obstacle avoidance for unmanned air vehicles [Master thesis, Brigham Young University]. Provo, UT, USA. https://scholarsarchive.byu.edu/cgi/viewcontent.cgi?article=1791&context=etd
Chen, J., Li, M., Yuan, Z., & Gu, Q. (2020, June 12–14). An improved A* algorithm for UAV path planning problems. In 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference (ITNEC) (Vol. 1, pp. 958–962). https://doi.org/10.1109/ITNEC48623.2020.9084806
Cihan, I. H. (2016). Optimal path planning of an unmanned combat aerial vehicle with obstacle avoidance [Master thesis, University of Missouri]. Columbia, MO, USA.
Dobrokhodov, V. N., Walton, C., Kaminer, I. I., & Jones, K. D. (2020). Energy-optimal guidance of hybrid ultra-long endurance UAV. IFAC-PapersOnLine, 53(2), 15639–15646. https://doi.org/10.1016/j.ifacol.2020.12.2500
Fan, Y., Yang, L., Li, Q., Nong, C., Zheng, Z., & Xue, F. (2020, June 12–14). Cost index-based cruise flight trajectory optimization. In 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference (ITNEC) (Vol. 1, pp. 103–110). IEEE. https://doi.org/10.1109/ITNEC48623.2020.9085146
Ferguson, D., & Stentz, A. (2006, October 9–15). Anytime RRTs. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (pp. 5369–5375). Beijing, China. https://doi.org/10.1109/IROS.2006.282100
Force, U. T. (2011). Unmanned aircraft system airspace integration plan. Department of Defense.
Geiger, B., Horn, J., DeLullo, A., Niessner, A., & Long, L. (2006, August 21–24). Optimal path planning of UAVs using direct collocation with nonlinear programming. In AIAA Guidance, Navigation, and Control Conference and Exhibit. Keystone, CO, USA. American Institute of Aeronautics and Astronautics. https://doi.org/10.2514/6.2006-6199
Hanscom, A. F. B., & Bedford, M. A. (2013). Unmanned aircraft system (UAS) Service Demand 2015–2035. Literature review & projections of future usage. Research and Innovative Technology Administration US Department of Transportation, Washington, DC, USA.
Jensen, L., Tran, H., & Hansman, J. R. (2015, June 23–26). Cruise fuel reduction potential from altitude and speed optimization in global airline operations. In 11th USA/Europe Air Traffic Management Research and Development Seminar (ATM2015) (pp. 497–506). Lisbon, Portugal.
Kleder, M. (2008). Shortest path with obstacle avoidance (ver 1.3). https://www.mathworks.com/matlabcentral/fileexchange/8625-shortest-path-with-obstacle-avoidance-ver-1-3
Liu, H., Chen, S., Shen, L, & Chen, J. (2012). Tactical trajectory planning for stealth unmanned aerial vehicle to win the radar game. Defence Science Journal, 62(6), 375–381. https://doi.org/10.14429/dsj.62.2686
Macharet, D. G., Neto, A. A., & Campos, M. F. M. (2010, October 23–28). Feasible UAV path planning using genetic algorithms and Bézier curves. In Proceedings of the 20th Brazilian Symposium on Artificial Intelligence (pp. 223–232). São Bernardo do Campo, Brazil. https://doi.org/10.1007/978-3-642-16138-4_23
Mohan, K., Patterson, M., & Rao, A. (2012, August 13–16). Optimal trajectory and control generation for landing of multiple aircraft in the presence of obstacles. In AIAA Guidance, Navigation, and Control Conference (pp. 1–16). Minneapolis, MN, USA. American Institute of Aeronautics and Astronautics. https://doi.org/10.2514/6.2012-4826
Richards, A., & How, J. P. (2002, May 8–10). Aircraft trajectory planning with collision avoidance using mixed integer linear programming. In Proceedings of the 2002 American Control Conference (IEEE Cat. No. CH37301) (pp. 1936–1941). Anchorage, AK, USA. IEEE. https://doi.org/10.1109/ACC.2002.1023918
Sadraey, M, & Müller, D. (2009). Drag force and drag coefficient. In Aircraft performance analysis. VDM Verlag Dr. Müller.
Schouwenaars, T., De Moor, B., Feron, E., & How, J. (2001, September 4–7). Mixed integer programming for multi-vehicle path planning. In Proceedings of the 2001 European Control Conference (pp. 2603–2608). Porto, Portugal. IEEE. https://doi.org/10.23919/ECC.2001.7076321
Shima, T., Rasmussen, S. J., & Sparks, A. G. (2005, March 19–22). UAV cooperative multiple task assignments using genetic algorithms. In Proceedings of the American Control Conference (pp. 8–10). Portland, OR, USA. https://doi.org/10.1109/ACC.2005.1470429
Sonmez, A., Kocyigit, E., & Kugu, E. (2015, June 9–12). Optimal path planning for UAVs using genetic algorithm. In Proceedings of the International Conference on Unmanned Aircraft Systems (ICUAS) (pp. 50–55). Denver, CO, USA. https://doi.org/10.1109/ICUAS.2015.7152274
Tian, Y., Wan, L., Ye, B., & Xing, D. (2019). Cruise flight performance optimization for minimizing green direct operating cost. Sustainability, 11(14), 3899. https://doi.org/10.3390/su11143899
Tsai, Y. J., Lee, C. S., Lin, C. L., & Huang, C. H. (2015). Development of flight path planning for multirotor aerial vehicles. Aerospace, 2(2), 171–188. https://doi.org/10.3390/aerospace2020171
Turgut, E. T., Cavcar, M., Usanmaz, O., Canarslanlar, A. O., Dogeroglu, T., Armutlu, K., & Yay, O. D. (2014). Fuel flow analysis for the cruise phase of commercial aircraft on domestic routes. Aerospace Science and Technology, 37, 1–9. https://doi.org/10.1016/j.ast.2014.04.012
Véras, L. G., Medeiros, F. L., & Guimaraes, L. N. (2019). Rapidly exploring Random Tree* with a sampling method based on Sukharev grids and convex vertices of safety hulls of obstacles. International Journal of Advanced Robotic Systems, 16(1). https://doi.org/10.1177/1729881419825941
Wang, Y., & Chen, W. (2014, July 28). Path planning and obstacle avoidance of unmanned aerial vehicle based on improved genetic algorithms. In Proceedings of the 33rd Chinese Control Conference (pp. 8612–8616). Nanjing, China. https://doi.org/10.1109/ChiCC.2014.6896446
Zammit, C., & Van Kampen, E. J. V. (2018, January 8–12). Comparison between A* and RRT algorithms for UAV path planning. In AIAA Guidance, Navigation, and Control Conference (pp. 1846–1869). Kissimmee, FL, USA. https://doi.org/10.2514/6.2018-1846
Zhang, L., Zhou, Z., & Zhang, F. M. (2014). Mixed integer linear programming for UAV trajectory planning problem. In Applied Mechanics and Materials, 541, 1473–1477. https://doi.org/10.4028/www.scientific.net/AMM.541-542.1473
Ardema, M. D., & Asuncion, B. C. (2009). Flight path optimization at constant altitude. In Variational analysis and aerospace engineering. Springer. https://doi.org/10.1007/978-0-387-95857-6_2
Bai, M., Yang, W., Song, D., Kosuda, M., Szabo, S., Lipovsky, P., & Kasaei, A. (2020). Research on energy management of hybrid unmanned aerial vehicles to improve energy-saving and emission reduction performance. International Journal of Environmental Research and Public Health, 17(8), 2917. https://doi.org/10.3390/ijerph17082917
Bortoff, S. A. (2000, June 28–30). Path planning for UAVs. In Proceedings of the 2000 American Control Conference (IEEE Cat. No. CH36334) (Vol. 1, pp. 364–368). Chicago, IL, USA. https://doi.org/10.1109/ACC.2000.878915
Brandt, S. A., Bertin, J. J., Stiles, R. J., & Whitford, R. (2004). Introduction to aeronautics: A design perspective. American Institute of Aeronautics and Astronautics. https://doi.org/10.2514/4.862007
Cafieri, S., & Durand, N. (2014). Aircraft deconfliction with speed regulation: New models from mixed-integer optimization. Journal of Global Optimization, 58(4), 613–629. https://doi.org/10.1007/s10898-013-0070-1
Call, B. R. (2006). Obstacle avoidance for unmanned air vehicles [Master thesis, Brigham Young University]. Provo, UT, USA. https://scholarsarchive.byu.edu/cgi/viewcontent.cgi?article=1791&context=etd
Chen, J., Li, M., Yuan, Z., & Gu, Q. (2020, June 12–14). An improved A* algorithm for UAV path planning problems. In 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference (ITNEC) (Vol. 1, pp. 958–962). https://doi.org/10.1109/ITNEC48623.2020.9084806
Cihan, I. H. (2016). Optimal path planning of an unmanned combat aerial vehicle with obstacle avoidance [Master thesis, University of Missouri]. Columbia, MO, USA.
Dobrokhodov, V. N., Walton, C., Kaminer, I. I., & Jones, K. D. (2020). Energy-optimal guidance of hybrid ultra-long endurance UAV. IFAC-PapersOnLine, 53(2), 15639–15646. https://doi.org/10.1016/j.ifacol.2020.12.2500
Fan, Y., Yang, L., Li, Q., Nong, C., Zheng, Z., & Xue, F. (2020, June 12–14). Cost index-based cruise flight trajectory optimization. In 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference (ITNEC) (Vol. 1, pp. 103–110). IEEE. https://doi.org/10.1109/ITNEC48623.2020.9085146
Ferguson, D., & Stentz, A. (2006, October 9–15). Anytime RRTs. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (pp. 5369–5375). Beijing, China. https://doi.org/10.1109/IROS.2006.282100
Force, U. T. (2011). Unmanned aircraft system airspace integration plan. Department of Defense.
Geiger, B., Horn, J., DeLullo, A., Niessner, A., & Long, L. (2006, August 21–24). Optimal path planning of UAVs using direct collocation with nonlinear programming. In AIAA Guidance, Navigation, and Control Conference and Exhibit. Keystone, CO, USA. American Institute of Aeronautics and Astronautics. https://doi.org/10.2514/6.2006-6199
Hanscom, A. F. B., & Bedford, M. A. (2013). Unmanned aircraft system (UAS) Service Demand 2015–2035. Literature review & projections of future usage. Research and Innovative Technology Administration US Department of Transportation, Washington, DC, USA.
Jensen, L., Tran, H., & Hansman, J. R. (2015, June 23–26). Cruise fuel reduction potential from altitude and speed optimization in global airline operations. In 11th USA/Europe Air Traffic Management Research and Development Seminar (ATM2015) (pp. 497–506). Lisbon, Portugal.
Kleder, M. (2008). Shortest path with obstacle avoidance (ver 1.3). https://www.mathworks.com/matlabcentral/fileexchange/8625-shortest-path-with-obstacle-avoidance-ver-1-3
Liu, H., Chen, S., Shen, L, & Chen, J. (2012). Tactical trajectory planning for stealth unmanned aerial vehicle to win the radar game. Defence Science Journal, 62(6), 375–381. https://doi.org/10.14429/dsj.62.2686
Macharet, D. G., Neto, A. A., & Campos, M. F. M. (2010, October 23–28). Feasible UAV path planning using genetic algorithms and Bézier curves. In Proceedings of the 20th Brazilian Symposium on Artificial Intelligence (pp. 223–232). São Bernardo do Campo, Brazil. https://doi.org/10.1007/978-3-642-16138-4_23
Mohan, K., Patterson, M., & Rao, A. (2012, August 13–16). Optimal trajectory and control generation for landing of multiple aircraft in the presence of obstacles. In AIAA Guidance, Navigation, and Control Conference (pp. 1–16). Minneapolis, MN, USA. American Institute of Aeronautics and Astronautics. https://doi.org/10.2514/6.2012-4826
Richards, A., & How, J. P. (2002, May 8–10). Aircraft trajectory planning with collision avoidance using mixed integer linear programming. In Proceedings of the 2002 American Control Conference (IEEE Cat. No. CH37301) (pp. 1936–1941). Anchorage, AK, USA. IEEE. https://doi.org/10.1109/ACC.2002.1023918
Sadraey, M, & Müller, D. (2009). Drag force and drag coefficient. In Aircraft performance analysis. VDM Verlag Dr. Müller.
Schouwenaars, T., De Moor, B., Feron, E., & How, J. (2001, September 4–7). Mixed integer programming for multi-vehicle path planning. In Proceedings of the 2001 European Control Conference (pp. 2603–2608). Porto, Portugal. IEEE. https://doi.org/10.23919/ECC.2001.7076321
Shima, T., Rasmussen, S. J., & Sparks, A. G. (2005, March 19–22). UAV cooperative multiple task assignments using genetic algorithms. In Proceedings of the American Control Conference (pp. 8–10). Portland, OR, USA. https://doi.org/10.1109/ACC.2005.1470429
Sonmez, A., Kocyigit, E., & Kugu, E. (2015, June 9–12). Optimal path planning for UAVs using genetic algorithm. In Proceedings of the International Conference on Unmanned Aircraft Systems (ICUAS) (pp. 50–55). Denver, CO, USA. https://doi.org/10.1109/ICUAS.2015.7152274
Tian, Y., Wan, L., Ye, B., & Xing, D. (2019). Cruise flight performance optimization for minimizing green direct operating cost. Sustainability, 11(14), 3899. https://doi.org/10.3390/su11143899
Tsai, Y. J., Lee, C. S., Lin, C. L., & Huang, C. H. (2015). Development of flight path planning for multirotor aerial vehicles. Aerospace, 2(2), 171–188. https://doi.org/10.3390/aerospace2020171
Turgut, E. T., Cavcar, M., Usanmaz, O., Canarslanlar, A. O., Dogeroglu, T., Armutlu, K., & Yay, O. D. (2014). Fuel flow analysis for the cruise phase of commercial aircraft on domestic routes. Aerospace Science and Technology, 37, 1–9. https://doi.org/10.1016/j.ast.2014.04.012
Véras, L. G., Medeiros, F. L., & Guimaraes, L. N. (2019). Rapidly exploring Random Tree* with a sampling method based on Sukharev grids and convex vertices of safety hulls of obstacles. International Journal of Advanced Robotic Systems, 16(1). https://doi.org/10.1177/1729881419825941
Wang, Y., & Chen, W. (2014, July 28). Path planning and obstacle avoidance of unmanned aerial vehicle based on improved genetic algorithms. In Proceedings of the 33rd Chinese Control Conference (pp. 8612–8616). Nanjing, China. https://doi.org/10.1109/ChiCC.2014.6896446
Zammit, C., & Van Kampen, E. J. V. (2018, January 8–12). Comparison between A* and RRT algorithms for UAV path planning. In AIAA Guidance, Navigation, and Control Conference (pp. 1846–1869). Kissimmee, FL, USA. https://doi.org/10.2514/6.2018-1846
Zhang, L., Zhou, Z., & Zhang, F. M. (2014). Mixed integer linear programming for UAV trajectory planning problem. In Applied Mechanics and Materials, 541, 1473–1477. https://doi.org/10.4028/www.scientific.net/AMM.541-542.1473