American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Modelling and optimal control of blood glucose levels in the human body
  • JIMO Home
  • This Issue
  • Next Article
    Second order sufficient conditions for a class of bilevel programs with lower level second-order cone programming problem
October  2015, 11(4): 1127-1147. doi: 10.3934/jimo.2015.11.1127

Numerical solution of a pursuit-evasion differential game involving two spacecraft in low earth orbit

Songtao Sun 1, , Qiuhua Zhang 1, , Ryan Loxton 2, and  Bin Li 3,

1. 

Department of Astronautical Science and Mechanics, Harbin Institute of Technology, Harbin, China, China
2. 

Department of Mathematics and Statistics, Curtin University, Perth 6845
3. 

Department of Mathematics and Statistics, Curtin University, Perth, Australia

Received  November 2013 Revised  July 2014 Published  March 2015

This paper considers a spacecraft pursuit-evasion problem taking place in low earth orbit. The problem is formulated as a zero-sum differential game in which there are two players, a pursuing spacecraft that attempts to minimize a payoff, and an evading spacecraft that attempts to maximize the same payoff. We introduce two associated optimal control problems and show that a saddle point for the differential game exists if and only if the two optimal control problems have the same optimal value. Then, on the basis of this result, we propose two computational methods for determining a saddle point solution: a semi-direct control parameterization method (SDCP method), which is based on a piecewise-constant control approximation scheme, and a hybrid method, which combines the new SDCP method with the multiple shooting method. Simulation results show that the proposed SDCP and hybrid methods are superior to the semi-direct collocation nonlinear programming method (SDCNLP method), which is widely used to solve pursuit-evasion problems in the aerospace field.
Keywords: nonlinear programming, Pursuit-evasion problem, optimal control, multiple shooting method., differential game.
Mathematics Subject Classification: Primary: 91A25; Secondary: 49M37, 49N9.
Citation: Songtao Sun, Qiuhua Zhang, Ryan Loxton, Bin Li. Numerical solution of a pursuit-evasion differential game involving two spacecraft in low earth orbit. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1127-1147. doi: 10.3934/jimo.2015.11.1127
References:
[1]

M. Bardi, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations,, Birkhauser, (1997).  doi: 10.1007/978-0-8176-4755-1.  Google Scholar

[2]

L. D. Berkovitz, Necessary conditions for optimal strategies in a class of differential games and control problems,, SIAM Journal on Control and Optimization, 5 (1967), 1.  doi: 10.1137/0305001.  Google Scholar

[3]

L. D. Berkovitz, The existence of value and saddle point in games of fixed duration,, SIAM Journal on Control and Optimization, 23 (1985), 172.  doi: 10.1137/0323015.  Google Scholar

[4]

M. Breitner, H. Pesch and W. Grimm, Complex differential games of pursuit-evasion type with state constraints, part 2: Necessary conditions for optimal open-loop strategies,, Journal of Optimization Theory and Applications, 78 (1993), 443.  doi: 10.1007/BF00939877.  Google Scholar

[5]

W. H. Clohessy and R. S. Wiltshire, Terminal guidance system for satellite rendezvous,, Journal of the Aerospace Sciences, 11 (1960), 653.   Google Scholar

[6]

S. D. Conte and C. de Boor, Elementary Numerical Analysis: An Algorithmic Approach,, Third Edition, (1981).   Google Scholar

[7]

K. Deb, A fast and elitist multi-objective genetic algorithm: NSGA-II,, IEEE Transactions on Evolutionary Computation, 6 (2002), 182.   Google Scholar

[8]

A. Friedman, Differential Games,, American Mathematical Society, (1974).   Google Scholar

[9]

P. E. Gill, W. Murray, M. Saunders and M. H. Wright, User's Guide for NPSOL (Version 5.0): A Fortran Package for Nonlinear Programming,, Systems and Optimization Lab, (1998).   Google Scholar

[10]

A. L. Herman and B. A. Conway, Direct optimization using collocation based on high-order Gauss-Lobatto quadrature rules,, Journal of Guidance, 19 (1996), 592.  doi: 10.2514/3.21662.  Google Scholar

[11]

K. Horie, Collocation with Nonlinear Programming for Two-Sided Flight Path Optimization,, Ph.D. Thesis, (2002).   Google Scholar

[12]

K. Horie and B. A. Conway, Optimal fighter pursuit-evasion maneuvers found via two-sided optimization,, Journal of Guidance, 29 (2006), 105.  doi: 10.2514/1.3960.  Google Scholar

[13]

R. Isaacs, Differential Games,, John Wiley and Sons, (1965).   Google Scholar

[14]

L. S. Jennings, M. E. Fisher, K. L. Teo and C. J. Goh, MISER 3 Optimal Control Software: Theory and User Manual,, Department of Mathematics, (2002).   Google Scholar

[15]

C. Jiang, Q. Lin, C. Yu, K. L. Teo and G. R. Duan, An exact penalty method for free terminal time optimal control problem with continuous inequality constraints,, Journal of Optimization Theory and Applications, 154 (2012), 30.  doi: 10.1007/s10957-012-0006-9.  Google Scholar

[16]

B. Li, K. L. Teo, G. H. Zhao and G. R. Duan, An efficient computational approach to a class of minmax optimal control problems with applications,, ANZIAM Journal, 51 (2009), 162.  doi: 10.1017/S1446181110000040.  Google Scholar

[17]

B. Li, C. Xu, K. L. Teo and J. Chu, Time optimal Zermelo's navigation problem with moving and fixed obstacles,, Applied Mathematics and Computation, 224 (2013), 866.  doi: 10.1016/j.amc.2013.08.092.  Google Scholar

[18]

B. Li, C. J. Yu, K. L. Teo and G. R. Duan, An exact penalty function method for continuous inequality constrained optimal control problem,, Journal of Optimization Theory and Applications, 151 (2011), 260.  doi: 10.1007/s10957-011-9904-5.  Google Scholar

[19]

Q. Lin, R. Loxton and K. L. Teo, The control parameterization method for nonlinear optimal control: A survey,, Journal of Industrial and Management Optimization, 10 (2014), 275.  doi: 10.3934/jimo.2014.10.275.  Google Scholar

[20]

R. C. Loxton, Q. Lin, V. Rehbock and K. L. Teo, Control parameterization for optimal control problems with continuous inequality constraints: New convergence results,, Numerical Algebra, 2 (2012), 571.  doi: 10.3934/naco.2012.2.571.  Google Scholar

[21]

R. C. Loxton, K. L. Teo, V. Rehbock and K. F. C. Yiu, Optimal control problems with a continuous inequality constraint on the state and the control,, Automatica, 45 (2009), 2250.  doi: 10.1016/j.automatica.2009.05.029.  Google Scholar

[22]

H. J. Oberle and W. Grimm, BNDSCO: A Program for the Numerical Solution of Optimal Control Problems,, Inst. für Angewandte Math. der Univ. Hamburg, (2001).   Google Scholar

[23]

M. Pontani and B. A. Conway, Optimal interception of evasive missile warheads: Numerical solution of the differential game,, Journal of Guidance, 31 (2008), 1111.   Google Scholar

[24]

M. Pontani and B. A. Conway, Numerical solution of the three-dimensional orbital pursuit-evasion game,, Journal of Guidance, 32 (2009), 474.   Google Scholar

[25]

K. Schittkowski, NLPQL: A FORTRAN subroutine for solving constrained nonlinear programming problems,, Annals of Operations Research, 5 (1986), 485.  doi: 10.1007/BF02739235.  Google Scholar

[26]

T. Shima and J. Shinar, Time-varying linear pursuit-evasion game models with bounded controls,, Journal of Optimization Theory and Applications, 25 (2002), 607.  doi: 10.2514/2.4927.  Google Scholar

[27]

J. Shinar and T. Shima, Guidance law evaluation in highly nonlinear scenarios - comparison to linear analysis,, in Proceedings of the AIAA Guidance, (1999), 651.  doi: 10.2514/6.1999-4065.  Google Scholar

[28]

J. Stoer and R. Bulirsch, Introduction to Numerical Analysis,, Third Edition, (2002).  doi: 10.1007/978-0-387-21738-3.  Google Scholar

[29]

K. L. Teo, C. J. Goh and K. H. Wong, A Unified Computational Approach to Optimal Control Problems,, Longman Scientific and Technical, (1991).   Google Scholar

[30]

L. Y. Wang, W. H. Gui, K. L. Teo, R. Loxton and C. H. Yang, Time delayed optimal control problems with multiple characteristic time points: Computation and industrial applications,, Journal of Industrial and Management Optimization, 5 (2009), 705.  doi: 10.3934/jimo.2009.5.705.  Google Scholar

show all references

References:
[1]

M. Bardi, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations,, Birkhauser, (1997).  doi: 10.1007/978-0-8176-4755-1.  Google Scholar

[2]

L. D. Berkovitz, Necessary conditions for optimal strategies in a class of differential games and control problems,, SIAM Journal on Control and Optimization, 5 (1967), 1.  doi: 10.1137/0305001.  Google Scholar

[3]

L. D. Berkovitz, The existence of value and saddle point in games of fixed duration,, SIAM Journal on Control and Optimization, 23 (1985), 172.  doi: 10.1137/0323015.  Google Scholar

[4]

M. Breitner, H. Pesch and W. Grimm, Complex differential games of pursuit-evasion type with state constraints, part 2: Necessary conditions for optimal open-loop strategies,, Journal of Optimization Theory and Applications, 78 (1993), 443.  doi: 10.1007/BF00939877.  Google Scholar

[5]

W. H. Clohessy and R. S. Wiltshire, Terminal guidance system for satellite rendezvous,, Journal of the Aerospace Sciences, 11 (1960), 653.   Google Scholar

[6]

S. D. Conte and C. de Boor, Elementary Numerical Analysis: An Algorithmic Approach,, Third Edition, (1981).   Google Scholar

[7]

K. Deb, A fast and elitist multi-objective genetic algorithm: NSGA-II,, IEEE Transactions on Evolutionary Computation, 6 (2002), 182.   Google Scholar

[8]

A. Friedman, Differential Games,, American Mathematical Society, (1974).   Google Scholar

[9]

P. E. Gill, W. Murray, M. Saunders and M. H. Wright, User's Guide for NPSOL (Version 5.0): A Fortran Package for Nonlinear Programming,, Systems and Optimization Lab, (1998).   Google Scholar

[10]

A. L. Herman and B. A. Conway, Direct optimization using collocation based on high-order Gauss-Lobatto quadrature rules,, Journal of Guidance, 19 (1996), 592.  doi: 10.2514/3.21662.  Google Scholar

[11]

K. Horie, Collocation with Nonlinear Programming for Two-Sided Flight Path Optimization,, Ph.D. Thesis, (2002).   Google Scholar

[12]

K. Horie and B. A. Conway, Optimal fighter pursuit-evasion maneuvers found via two-sided optimization,, Journal of Guidance, 29 (2006), 105.  doi: 10.2514/1.3960.  Google Scholar

[13]

R. Isaacs, Differential Games,, John Wiley and Sons, (1965).   Google Scholar

[14]

L. S. Jennings, M. E. Fisher, K. L. Teo and C. J. Goh, MISER 3 Optimal Control Software: Theory and User Manual,, Department of Mathematics, (2002).   Google Scholar

[15]

C. Jiang, Q. Lin, C. Yu, K. L. Teo and G. R. Duan, An exact penalty method for free terminal time optimal control problem with continuous inequality constraints,, Journal of Optimization Theory and Applications, 154 (2012), 30.  doi: 10.1007/s10957-012-0006-9.  Google Scholar

[16]

B. Li, K. L. Teo, G. H. Zhao and G. R. Duan, An efficient computational approach to a class of minmax optimal control problems with applications,, ANZIAM Journal, 51 (2009), 162.  doi: 10.1017/S1446181110000040.  Google Scholar

[17]

B. Li, C. Xu, K. L. Teo and J. Chu, Time optimal Zermelo's navigation problem with moving and fixed obstacles,, Applied Mathematics and Computation, 224 (2013), 866.  doi: 10.1016/j.amc.2013.08.092.  Google Scholar

[18]

B. Li, C. J. Yu, K. L. Teo and G. R. Duan, An exact penalty function method for continuous inequality constrained optimal control problem,, Journal of Optimization Theory and Applications, 151 (2011), 260.  doi: 10.1007/s10957-011-9904-5.  Google Scholar

[19]

Q. Lin, R. Loxton and K. L. Teo, The control parameterization method for nonlinear optimal control: A survey,, Journal of Industrial and Management Optimization, 10 (2014), 275.  doi: 10.3934/jimo.2014.10.275.  Google Scholar

[20]

R. C. Loxton, Q. Lin, V. Rehbock and K. L. Teo, Control parameterization for optimal control problems with continuous inequality constraints: New convergence results,, Numerical Algebra, 2 (2012), 571.  doi: 10.3934/naco.2012.2.571.  Google Scholar

[21]

R. C. Loxton, K. L. Teo, V. Rehbock and K. F. C. Yiu, Optimal control problems with a continuous inequality constraint on the state and the control,, Automatica, 45 (2009), 2250.  doi: 10.1016/j.automatica.2009.05.029.  Google Scholar

[22]

H. J. Oberle and W. Grimm, BNDSCO: A Program for the Numerical Solution of Optimal Control Problems,, Inst. für Angewandte Math. der Univ. Hamburg, (2001).   Google Scholar

[23]

M. Pontani and B. A. Conway, Optimal interception of evasive missile warheads: Numerical solution of the differential game,, Journal of Guidance, 31 (2008), 1111.   Google Scholar

[24]

M. Pontani and B. A. Conway, Numerical solution of the three-dimensional orbital pursuit-evasion game,, Journal of Guidance, 32 (2009), 474.   Google Scholar

[25]

K. Schittkowski, NLPQL: A FORTRAN subroutine for solving constrained nonlinear programming problems,, Annals of Operations Research, 5 (1986), 485.  doi: 10.1007/BF02739235.  Google Scholar

[26]

T. Shima and J. Shinar, Time-varying linear pursuit-evasion game models with bounded controls,, Journal of Optimization Theory and Applications, 25 (2002), 607.  doi: 10.2514/2.4927.  Google Scholar

[27]

J. Shinar and T. Shima, Guidance law evaluation in highly nonlinear scenarios - comparison to linear analysis,, in Proceedings of the AIAA Guidance, (1999), 651.  doi: 10.2514/6.1999-4065.  Google Scholar

[28]

J. Stoer and R. Bulirsch, Introduction to Numerical Analysis,, Third Edition, (2002).  doi: 10.1007/978-0-387-21738-3.  Google Scholar

[29]

K. L. Teo, C. J. Goh and K. H. Wong, A Unified Computational Approach to Optimal Control Problems,, Longman Scientific and Technical, (1991).   Google Scholar

[30]

L. Y. Wang, W. H. Gui, K. L. Teo, R. Loxton and C. H. Yang, Time delayed optimal control problems with multiple characteristic time points: Computation and industrial applications,, Journal of Industrial and Management Optimization, 5 (2009), 705.  doi: 10.3934/jimo.2009.5.705.  Google Scholar

[1]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[2]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[3]

Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437
[4]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017
[5]

Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027
[6]

Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183
[7]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056
[8]

Shanjian Tang, Fu Zhang. Path-dependent optimal stochastic control and viscosity solution of associated Bellman equations. Discrete & Continuous Dynamical Systems - A, 2015, 35 (11) : 5521-5553. doi: 10.3934/dcds.2015.35.5521
[9]

David Cantala, Juan Sebastián Pereyra. Endogenous budget constraints in the assignment game. Journal of Dynamics & Games, 2015, 2 (3&4) : 207-225. doi: 10.3934/jdg.2015002
[10]

Yuncherl Choi, Taeyoung Ha, Jongmin Han, Sewoong Kim, Doo Seok Lee. Turing instability and dynamic phase transition for the Brusselator model with multiple critical eigenvalues. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021035
[11]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[12]

Yves Dumont, Frederic Chiroleu. Vector control for the Chikungunya disease. Mathematical Biosciences & Engineering, 2010, 7 (2) : 313-345. doi: 10.3934/mbe.2010.7.313
[13]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[14]

Jaume Llibre, Luci Any Roberto. On the periodic solutions of a class of Duffing differential equations. Discrete & Continuous Dynamical Systems - A, 2013, 33 (1) : 277-282. doi: 10.3934/dcds.2013.33.277
[15]

Y. Latushkin, B. Layton. The optimal gap condition for invariant manifolds. Discrete & Continuous Dynamical Systems - A, 1999, 5 (2) : 233-268. doi: 10.3934/dcds.1999.5.233
[16]

Yanqin Fang, Jihui Zhang. Multiplicity of solutions for the nonlinear Schrödinger-Maxwell system. Communications on Pure & Applied Analysis, 2011, 10 (4) : 1267-1279. doi: 10.3934/cpaa.2011.10.1267
[17]

Olena Naboka. On synchronization of oscillations of two coupled Berger plates with nonlinear interior damping. Communications on Pure & Applied Analysis, 2009, 8 (6) : 1933-1956. doi: 10.3934/cpaa.2009.8.1933
[18]

Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463
[19]

Martin Bohner, Sabrina Streipert. Optimal harvesting policy for the Beverton--Holt model. Mathematical Biosciences & Engineering, 2016, 13 (4) : 673-695. doi: 10.3934/mbe.2016014
[20]

Xingchun Wang, Yongjin Wang. Variance-optimal hedging for target volatility options. Journal of Industrial & Management Optimization, 2014, 10 (1) : 207-218. doi: 10.3934/jimo.2014.10.207

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (56)
  • HTML views (0)
  • Cited by (7)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences