Dan Shen, Intelligent Fusion Technology, Inc; Khanh Pham, AFRL/RVSWS; Genshe Chen, Intelligent Fusion Technology, Inc.
Keywords: Pursuit-evasion game, space situational awareness, numerical solution, non-linear programming, multi-objective optimization, satellite interception, collision avoidance.
Abstract:
Pursuit-evasion (PE) games are mathematical tools to model the space situational awareness (SSA) problems, such as satellite interception, collision avoidance, and space sensor management. Early work in pursuit-evasion games took place before the wide availability of computers and software packages. Consequently, the application of PE game theory to useful problems has been limited, since all calculations had to be done analytically. It is well known that the solution of pursuit-evasion games with realistic dynamics must be found numerically. As is the case for optimal control problems, numerical solutions for PE games often fall into two categories, direct methods and indirect methods. The basic procedure for indirect methods is to take the system dynamics, form the Hamiltonian, derive the necessary conditions, and then solve the boundary value problem numerically using information about the states and costates at the boundaries. Conversely, in direct methods, the game problem is converted to a nonlinear programming problem and the solvers only need to know the system dynamics, control and state constraints, and the objective function, without the need for costate information.
Indirect methods are marked by their high accuracy and the production of a solution that satisfies the necessary conditions of optimality. In this paper, we developed enhanced indirect solutions by combing two-sided non-linear programming (NLP) and multi-objective optimization based initial solution guess for orbital PE games, where the pursuer minimizing the satellite interception time while the evader maximizing interception time for collision avoidance. The interception-avoidance (IA) PE game approach provides a worst-case solution, which is the robust lower-bound performance case.
In the proposed solution framework, the first step is to obtain a good initial value, which will be iteratively revised by an open source NLP solver, NLOPT. The better the initial value, the faster the numerical solution converges. In this paper, we develop a multi-objective optimization approach to approximately solve PE game problems and use the approximate solution as the initial value for NLOPT. In the literature, there are three categories of evolutionary solutions for multiple objective problems: dominance based algorithms, aggregation based algorithms, and indicator based algorithms. In this paper, we apply NSGA II (a dominance based algorithm) to generate an initial guess for our numerical game solution. The main reason is that NSGA II has been coded in SciLab, which is free and open source software for numerical computation providing a powerful computing environment for engineering and scientific applications.
As a user case, a two-satellite IA problem is modelled using a PE game and is simulated to demonstrate the effectiveness of the enhanced numerical PE game solution. Various multi-objective settings are tested and analyzed to obtain a good initial value. Then the settings of NLOPT to solve the PE game are presented and results are discussed. At the end, the conclusion is drawn and the future work is laid out too.
Date of Conference: September 11-14, 2018
Track: Poster