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 and 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, Boston, 1997. doi: 10.1007/978-0-8176-4755-1.

[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-24. doi: 10.1137/0305001.

[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-196. doi: 10.1137/0323015.

[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-463. doi: 10.1007/BF00939877.

[5]

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

[6]

S. D. Conte and C. de Boor, Elementary Numerical Analysis: An Algorithmic Approach, Third Edition, McGraw-Hill, New York, 1981.

[7]

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

[8]

A. Friedman, Differential Games, American Mathematical Society, Rhode Island, 1974.

[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, Stanford University, California, 1998.

[10]

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

[11]

K. Horie, Collocation with Nonlinear Programming for Two-Sided Flight Path Optimization, Ph.D. Thesis, University of Illinois at Urbana-Champaign, Champaign, 2002.

[12]

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

[13]

R. Isaacs, Differential Games, John Wiley and Sons, New York, 1965.

[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, The University of Western Australia, 2002.

[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-53. doi: 10.1007/s10957-012-0006-9.

[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-177. doi: 10.1017/S1446181110000040.

[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-875. doi: 10.1016/j.amc.2013.08.092.

[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-291. doi: 10.1007/s10957-011-9904-5.

[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-309. doi: 10.3934/jimo.2014.10.275.

[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, Control, and Optimization, 2 (2012), 571-599. doi: 10.3934/naco.2012.2.571.

[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-2257. doi: 10.1016/j.automatica.2009.05.029.

[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.

[23]

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

[24]

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

[25]

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

[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-618. doi: 10.2514/2.4927.

[27]

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

[28]

J. Stoer and R. Bulirsch, Introduction to Numerical Analysis, Third Edition, Springer, New York, 2002. doi: 10.1007/978-0-387-21738-3.

[29]

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

[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-718. doi: 10.3934/jimo.2009.5.705.

show all references

References:
[1]

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

[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-24. doi: 10.1137/0305001.

[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-196. doi: 10.1137/0323015.

[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-463. doi: 10.1007/BF00939877.

[5]

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

[6]

S. D. Conte and C. de Boor, Elementary Numerical Analysis: An Algorithmic Approach, Third Edition, McGraw-Hill, New York, 1981.

[7]

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

[8]

A. Friedman, Differential Games, American Mathematical Society, Rhode Island, 1974.

[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, Stanford University, California, 1998.

[10]

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

[11]

K. Horie, Collocation with Nonlinear Programming for Two-Sided Flight Path Optimization, Ph.D. Thesis, University of Illinois at Urbana-Champaign, Champaign, 2002.

[12]

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

[13]

R. Isaacs, Differential Games, John Wiley and Sons, New York, 1965.

[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, The University of Western Australia, 2002.

[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-53. doi: 10.1007/s10957-012-0006-9.

[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-177. doi: 10.1017/S1446181110000040.

[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-875. doi: 10.1016/j.amc.2013.08.092.

[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-291. doi: 10.1007/s10957-011-9904-5.

[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-309. doi: 10.3934/jimo.2014.10.275.

[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, Control, and Optimization, 2 (2012), 571-599. doi: 10.3934/naco.2012.2.571.

[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-2257. doi: 10.1016/j.automatica.2009.05.029.

[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.

[23]

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

[24]

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

[25]

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

[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-618. doi: 10.2514/2.4927.

[27]

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

[28]

J. Stoer and R. Bulirsch, Introduction to Numerical Analysis, Third Edition, Springer, New York, 2002. doi: 10.1007/978-0-387-21738-3.

[29]

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

[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-718. doi: 10.3934/jimo.2009.5.705.

[1]

Abbas Ja'afaru Badakaya, Aminu Sulaiman Halliru, Jamilu Adamu. Game value for a pursuit-evasion differential game problem in a Hilbert space. Journal of Dynamics and Games, 2022, 9 (1) : 1-12. doi: 10.3934/jdg.2021019
[2]

Qi-shuai Wang, Pei Li, Ting Lei, Xiao-feng Liu, Guo-ping Cai. A Dimension-reduction method for the finite-horizon spacecraft pursuit-evasion game. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022028
[3]

Martino Bardi, Shigeaki Koike, Pierpaolo Soravia. Pursuit-evasion games with state constraints: dynamic programming and discrete-time approximations. Discrete and Continuous Dynamical Systems, 2000, 6 (2) : 361-380. doi: 10.3934/dcds.2000.6.361
[4]

John A. Morgan. Interception in differential pursuit/evasion games. Journal of Dynamics and Games, 2016, 3 (4) : 335-354. doi: 10.3934/jdg.2016018
[5]

Genglin Li, Youshan Tao, Michael Winkler. Large time behavior in a predator-prey system with indirect pursuit-evasion interaction. Discrete and Continuous Dynamical Systems - B, 2020, 25 (11) : 4383-4396. doi: 10.3934/dcdsb.2020102
[6]

Dayong Qi, Yuanyuan Ke. Large time behavior in a predator-prey system with pursuit-evasion interaction. Discrete and Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021240
[7]

Chao Liu, Bin Liu. Boundedness and asymptotic behavior in a predator-prey model with indirect pursuit-evasion interaction. Discrete and Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021255
[8]

Bingyan Liu, Xiongbing Ye, Xianzhou Dong, Lei Ni. Branching improved Deep Q Networks for solving pursuit-evasion strategy solution of spacecraft. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1223-1245. doi: 10.3934/jimo.2021016
[9]

Canghua Jiang, Cheng Jin, Ming Yu, Zongqi Xu. Direct optimal control for time-delay systems via a lifted multiple shooting algorithm. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021135
[10]

Nidhal Gammoudi, Hasnaa Zidani. A differential game control problem with state constraints. Mathematical Control and Related Fields, 2022  doi: 10.3934/mcrf.2022008
[11]

Qun Lin, Ryan Loxton, Kok Lay Teo. The control parameterization method for nonlinear optimal control: A survey. Journal of Industrial and Management Optimization, 2014, 10 (1) : 275-309. doi: 10.3934/jimo.2014.10.275
[12]

Li Jin, Hongying Huang. Differential equation method based on approximate augmented Lagrangian for nonlinear programming. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2267-2281. doi: 10.3934/jimo.2019053
[13]

Zhen Wu, Feng Zhang. Maximum principle for discrete-time stochastic optimal control problem and stochastic game. Mathematical Control and Related Fields, 2022, 12 (2) : 475-493. doi: 10.3934/mcrf.2021031
[14]

Marcus Wagner. A direct method for the solution of an optimal control problem arising from image registration. Numerical Algebra, Control and Optimization, 2012, 2 (3) : 487-510. doi: 10.3934/naco.2012.2.487
[15]

Vladimir Gaitsgory, Alex Parkinson, Ilya Shvartsman. Linear programming based optimality conditions and approximate solution of a deterministic infinite horizon discounted optimal control problem in discrete time. Discrete and Continuous Dynamical Systems - B, 2019, 24 (4) : 1743-1767. doi: 10.3934/dcdsb.2018235
[16]

Yu-Feng Sun, Zheng Zeng, Jie Song. Quasilinear iterative method for the boundary value problem of nonlinear fractional differential equation. Numerical Algebra, Control and Optimization, 2020, 10 (2) : 157-164. doi: 10.3934/naco.2019045
[17]

Gabriella Zecca. An optimal control problem for some nonlinear elliptic equations with unbounded coefficients. Discrete and Continuous Dynamical Systems - B, 2019, 24 (3) : 1393-1409. doi: 10.3934/dcdsb.2019021
[18]

Rein Luus. Optimal control of oscillatory systems by iterative dynamic programming. Journal of Industrial and Management Optimization, 2008, 4 (1) : 1-15. doi: 10.3934/jimo.2008.4.1
[19]

Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193
[20]

Yanqin Bai, Chuanhao Guo. Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems. Journal of Industrial and Management Optimization, 2014, 10 (2) : 543-556. doi: 10.3934/jimo.2014.10.543

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (114)
  • HTML views (0)
  • Cited by (9)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy