In this thesis, we propose a direct numerical method for quantitative pursuit-evasion games with control variable constraints. The method is a gradient-based one specialized for a class of pursuit-evasion games, for which the payoff of the game is the capture time. The proposed method adopts direct approach that transform the game problem into parameter optimization problem using discretization of control inputs of the players. Linear approximation of final position changes due to small perturbation of control input and final time transforms the pursuit-evasion game problem into a set of parameter optimization problems. The solution of these optimization problems is obtained by an iterative optimization algorithm developed in this thesis. The proposed algorithm is composed of two procedures, update and correction. Derivation of the update and correction algorithms is described in detail.
The optimal solution for an example of two-dimensional pursuit-evasion games is calculated to demonstrate the performance of the algorithm. Two evader models, constant-speed evader and realistic evader, are used to investigate the characteristics of the saddle-point trajectory. The solution calculated by the proposed method is also compared with the solution obtained by the indirect approach and analytic approach , which explicitly uses the necessary conditions. Comparison shows that the proposed method accurately computes the optimal capture time and provides a good approximation of the optimal solution. A capture set of the pursuer for the example calculated by the proposed algorithm is presented. The proposed method is extended to the three-dimensional pursuit-evasion problem. The merit of the proposed gradient method is that it is computationally efficient and applicable to realistic pursuit-evasion games with complicated missile/target dynamics.
In addition to the gradient-based direct method, numerical procedure based on pre-computed optimal trajectories is proposed. In this procedure, minimum-time trajectories of the pursuer and the evader are calculated for various end points. Contour map of iso-final time curves is constructed from transformation of these pre-computed optimal trajectories. Saddle-point solution of the pursuit-evasion games is obtained from the contour map by searching a final point that satisfies the saddle-point inequality. The behavior of the gradient-based method is analyzed on the contour map of iso-final time curves. This analysis shows that the solution of the gradient-based method is converged to the saddle-point solution.
본 논문에서는 정량적 추적-회피 게임에 대한 직접적 수치해석 기법을 제안한다. 제안된 방법은 구배 정보를 이용하며, 성능지수가 요격시간인 추적-회피 게임 문제에 적용할 수 있다. 제안된 방법은 직접적 접근방법을 사용한다. 이 방법에서는 제어입력의 이산화를 통하여 최적제어문제를 파라미터 최적화 문제로 변환한다. 추적자와 회피자의 최종위치 변화를 제어입력과 요격시간의 미소섭동과 민감도 함수의 선형 합으로 근사화하며, 이러한 과정을 통하여 추적-회피 게임 문제는 파라미터 최적화 문제들로 변환된다. 이러한 문제들의 해는 본 논문에서 제시한 반복적 최적화 알고리즘을 통하여 계산된다. 제안된 알고리즘은 갱신과정과 수정과정으로 구성되며, 각 과정의 알고리듬 유도방법을 본문에서 자세하게 다루었다.
제안된 알고리즘을 2차원 추적-회피 게임 예제에 적용하여 최적 해를 계산하였다. 이 예제에서는 등속 회피자 모형과 실제적 회피자 모형에 대하여 안장점 해를 계산하고 그 특성을 분석하였다. 또한 계산된 수치 해를 검증하기 위하여 간접적 방법과 해석적 방법에 의해 계산된 해와 비교하였다. 이러한 비교에서 제안된 방법이 요격시간을 정확히 계산할 수 있음을 확인하였다. 그리고 추적자에 대한 요격집합을 제안한 기법을 이용하여 계산하였다. 또한 제안된 방법을 3차원 추적-회피 게임 문제에 확장하였다. 제안된 방법은 수치적으로 효과적이며, 실제적인 복잡한 추적-회피 게임에 적용가능이 용이하다.
구배-기반 방법에 부가하여, 본 논문에서는 미리 계산된 최적 궤적을 사용하는 수치기법을 제안한다. 이 수치방법에서는 먼저 추적자와 회피자의 최소시간 궤적을 다수의 최종점에 대하여 계산한다. 이렇게 미리 계산된 최적 궤적을 초기요격조건에 맞게 변환한 뒤, 이 변환 결과로부터 등-요격시간선도를 구성한다. 추적-회피 게임의 안장점 해는 등-요격시간선도에서 안장점 부등식을 만족하는 탐색하여 결정한다. 구배-기반 방법의 거동을 등-요격시간선도를 이용하여 분석하였다. 이러한 분석으로부터 구배-기반의 해가 안장점으로 수렴됨을 알 수 있다.
