Nonlinear Multiobjective Time-Dependent TF/TA Trajectory Planning Using a Network Flow–Based Algorithm
Publication: Journal of Aerospace Engineering
Volume 29, Issue 2
Abstract
This paper studies the problem of finding the optimum time-dependent trajectory for an unmanned aerial vehicle (UAV) or any aerial robot flying on a low-altitude terrain following/threat avoidance (TF/TA) mission. Using a grid-based discrete scheme, a modified minimum cost network flow (MCNF) algorithm over a large-scale network is proposed. Using the Digital Terrain Elevation Data (DTED) and discrete dynamic equations of motion, the four-dimensional (4D) trajectory (three spatial and one time dimensions) from a source to a destination is obtained exactly through minimization of a cost functional subject to the nonlinear dynamics and mission constraints of the UAV. Several objectives (including the arc length, fuel consumption, flight time, and risk of threat regions) may be assigned to each arc in the network. The algorithm uses scalarization, by which a multiobjective problem can be tackled by repeatedly solving a single-objective subproblem. An attempt is made to reduce the time order of the algorithm using innovative techniques to construct a polynomial-time algorithm. Moreover, owing to the increasing deviation of the inertial navigation system (INS) in terms of time, flying safely and avoding a collision with terrain at low altitudes is a significant problem in the trajectory design of this type of vehicle. An attempt is made to add this constraint to the algorithm to produce a practical and safe trajectory with no evident increase in the complexity and execution time. Numerical results are presented to verify the capability of the proposed approach to generate an admissible trajectory in the minimum possible time compared to previous approaches.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
The authors would like to thank members of Advanced Control Systems Laboratory of the University of Tehran for the fruitful discussion on the subject.
References
Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. (1993). Network flows: Theory, algorithms and applications, Prentice Hall, Englewood Cliffs, NJ.
Belker, T., Hammel, M., and Hertzberg, J. (2003). “Learning to optimize mobile robot navigation based on HTN plans.” Proc., IEEE Int. Conf. on Robotics and Automation (ICRA 2003), Vol. 3, IEEE, New York, 4136–4141.
Betts, J., and Huffman, W. P. (1993). “Path constrained trajectory optimization using sparse sequential quadratic programming.” J. Guidance Control Dyn., 16(1), 59–68.
Cormen, T., Leiserson, C., Rivest, R., and Stein, C. (1990). Introduction to algorithms, McGraw-Hill, New York.
Dalila, B. M., and Fontes, M. (2005). “Optimal trees for general nonlinear network flow problems: A dynamic programming approach.” Robotica, 23(5), 567–580.
Dever, C. (2004). “Parameterized maneuvers for autonomous vehicles.” Ph.D. thesis, Dept. of Mechanical Engineering, Massachusetts Institute of Technology, Cambridge, MA.
Doherty, P., Gustafsson, J., Karlsson, L., and Kvarnstrom, J. (1998). “Tal: Temporal action logics: Language specification and tutorial.” Electron. Trans. Artif. Intell., 2(4), 273–306.
Dreo, J., and Siarry, P. (2006). “An ant colony algorithm aimed at dynamic continuous optimization.” Appl. Math. Comput., 181(1), 457–467.
Engelbrecht, A. (2005). Fundamentals of computational swarm intelligence, Wiley, New York.
Enright, P. J., and Conway, B. A. (1993). “Discrete approximations to optimal trajectories using direct transcription and nonlinear programming.” J. Guidance Control Dyn., 14(4), 994–2002.
Erol, K., Hendler, J., and Nau, D. (1994). “HTN planning: Complexity and expressivity.” Proc., AAAI National Conf. on Artificial Intelligence, AAAI, Palo Alto, CA.
Fonseca, C., and Fleming, P. (1993). “Genetic algorithms for multiobjective optimization: Formulation, discussion, and generalization.” Proc., 5th Int. Conf. on Genetic Algorithms, ACM, New York.
Fujimura, K. (1996). “Path planning with multiple objectives.” IEEE Robot. Autom. Mag., 3(1), 33–38.
Goldberg, D. (1989). Genetic algorithms in search, optimization and machine learning, Addison-Wesley, Reading, MA.
Hall, R. (2007). “Path planning and autonomous navigation for use in computer generated forces.”, Swedish Defense Research Agency, Stockholm, Sweden.
Hart, P., Nilsson, P., and Raphael, B. (1968). “A formal basis for the heuristic determination of minimum cost paths.” IEEE Trans. Syst. Sci. Cybern., 4(2), 100–107.
Helgason, R. V., Kennington, J. L., and Lewis, K. R. (2001). “Cruise missile mission planning: A heuristic algorithm for automatic path generation.” J. Heuristics, 7(5), 473–494.
Henshaw, C. G., and Sanner, R. M. (2010). “Variational technique for spacecraft trajectory planning.” J. Aerosp. Eng., 147–156.
Hromkovic, J. (2004). Algorithms for hard problems, Springer, Berlin.
Kavraki, L. E., Svestka, P., Latombe, J. C., and Overmars, M. (1996). “Probabilistic roadmaps for path planning in high dimensional configuration spaces.” IEEE Trans. Robot. Autom., 12(4), 566–580.
Kirk, D. E. (1970). Optimal control theory: An introduction, Prentice Hall, Englewood Cliffs, NJ.
Konstantinos, I., Tsianos, I. A. S., Ucan, L., and Kavraki, E. (2007). “Sampling-based robot motion planning: Towards realistic applications.” Comput. Sci. Rev., 1(1), 2–11.
Krenzke, T. (2006). “Ant colony optimization for agile motion planning.” Master’s thesis, Dept. of Aerospace Engineering, Massachusetts Institute of Technology, Cambridge, MA.
Kuffner, J. J., and LaValle, S. M. (2000). “Rrt-connect: An efficient approach to single-query path planning.” Proc., IEEE Int. Conf. Robotics and Automation (ICRA '00), Vol. 2, IEEE, New York, 995–1001.
LaValle, S. M. (1998). “Rapidly-exploring random trees: A new tool for path planning.”, Dept. of Computer Science, Iowa State Univ., Ames, IA.
Lu, P. (1993). “Inverse dynamics approach to trajectory optimization for an aerospace plane.” J. Guidance Control Dyn., 16(4), 726–732.
Malaek, S., and Kosari, A. R. (2003). “A novel minimum time trajectory planning in terrain following flight.” Proc., IEEE Aerospace and Electrical System Conf., Vol. 8, IEEE, New York, 3755–3762.
Mali, A., and Lipen, Y. (2003). “MFSAT: A SAT solver using multi-flip local search.” Proc., 15th IEEE Int. Conf. Tools Artificial Intelligence, IEEE, New York, 84–93.
MATLAB [Computer software]. Natick, MA, MathWorks.
Marler, R., and Arora, J. (2004). “Survey of multi-objective optimization methods for engineering.” Struct. Multidisc Optim., 26(6), 369–395.
Miele, A. (1962). “Flight mechanics.” Theory of flight paths, Vol. I, Addison-Wesley, Reading, MA.
Pareto, V. (1906). Manuale di Economia Politica, Societ`a Editrice Libraria, Milan, Italy.
Rippel, E., Bargill, A., and Shimkin, N. (2004). “Fast graph-search algorithms for general aviation flight trajectory generation.” Technion—Israel Institute of Technology, Haifa, Israel.
Schouwenaars, T., Mettler, B., Feron, E., and How, J. (2009). “A new model for optimal tf/ta flight path design problem.” Aeronaut. J., 113(1143), 301–308.
Serafini, P. (1992). “Simulated annealing for multiobjective optimization problems.” Proc., 10th Int. Conf. on Multiple Criteria Decision Making, Vol. 1, Taipei, Taiwan, 87–96.
Sharma, T., Williams, P., Bill, C., and Eberhard, A. (2005). “Optimal three dimensional aircraft terrain following and collision avoidance.” ANZIAM J., 47, C695–C711.
Stewart, B. S., Chelsea, I., and White, C. (1991). “Multiobjective a*.” J. ACM, 38(4), 775–814.
Szczerba, R. (1996). “New cell decomposition techniques for planning optimal paths.” Ph.D. thesis, Univ. of Notre Dame, Notre Dame, IN.
Titterton, D., and Weston, J. (1997). “Strapdown inertial navigation technology.” Peter Peregrinus, London.
Twigg, S., Calise, A., and Johnson, E. (2006). “3d trajectory optimization for terrain following and terrain masking.” Proc., AIAA, Guidance, Navigation, and Control Conf. and Exhibit, AIAA, Keystone, CO, 21–24.
Vincent, T. L., and Grantham, W. J. (1999). Nonlinear and optimal control systems, Wiley, New York.
Wang, Y., and Chirikjian, G. S. (2000). “A new potential field method for robot path planning.” Proc., IEEE Int. Conf. on Robotics and Automation, Vol. 2, IEEE, New York, 977–982.
Xin, D., Hua-hua, C., and Wei-kang, G. (2004). “Neural network and genetic algorithm based global path planning in a static environment.” J. Zhejiang Univ. Sci., 6(6), 549–554.
Zardashti, R. (2015). “Optimal and constrained terrain following/threat avoidance guidance using nonlinear approach.” Ph.D. thesis, K.N. Toosi Univ. of Technology, Faculty of Aerospace Engineering, Tehran, Iran.
Zardashti, R., and Bagherian, M. (2009). “A new model for optimal TF/TA flight path design problem.” Aeronaut. J., 113(1143), 301–308.
Information & Authors
Information
Published In
Journal of Aerospace Engineering
Volume 29 • Issue 2 • March 2016
Copyright
© 2015 American Society of Civil Engineers.
History
Received: Sep 22, 2014
Accepted: May 29, 2015
Published online: Aug 11, 2015
Discussion open until: Jan 11, 2016
Published in print: Mar 1, 2016
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.