Control Strategies in Multi-Player Pursuit and EvasionGame∗Jung Soon Jang†and Claire J. Tomlin‡Department of Aeronautics and AstronauticsStanford University, Stanford, CA 94305-4035This paper presents a new methodology for solving multi-player pursuit and evasiongames. The proposed control strategies are derived from direct differentiation of chosenvalue (or level set) functions, instead of solving the associated Hamilton Jacobi Isaacs (HJI)equations. The corresponding strategies offer a simple form of the control laws that can beimplemented on real-time control systems for autonomous vehicles. In order to guaranteea minimum separation distance between players, a new method to compute a reachable set,which only requires a set of ordinary differential equations, is developed. We also exploredifferent value functions which lead to different performance measures for some players. Weillustrate our approach on a three player pursuit and evasion game and present simulationresults.I. IntroductionCoordination and control of multiple agents have received great attention over the last few years.1–5Applications abound: formation flying, conflict resolution, optimum task allocation, and air-trafficcontrol, just to name a few.Differential game theories have been studied for obtaining optimal solutions of such problems. Also,advances in numerical methods for partial differential equations (PDEs) have opened an alternative routeto study these problems by numerically solving the associated Hamilton-Jocobi equations. Examples haveincluded various two-player games6–8and the associated conflict resolution problem9and multi-player games(more than two).10–12Control strategies presented in the above studies used the knowledge of the exact orapproximate solutions of associated HJ equations or of (assumed) opposing intents of some players, in orderto devise the corresponding control laws for the players.While these approaches are mathematically elegant and powerful (a way of capturing the behavior ofentire groups of trajectories at once), they suffer from the curse of dimensionality. This not only limits theirapplicability to low-dimensional problems, but also results in failure of real-time implementation (because ofcomputational complexity and storage). Alternatively, to mitigate these shortcomings, over-approximationschemes have been studied by Mitchell and Tomlin,13Stipanovi´c, Hwang, Tomlin,14and others,15–17andthese approximations may be used for fast computations of control laws. Stipanovi´c, Shankaran, and Tom-lin18also presented strategies for multi-player game derived from an approximate Hamilton Jacobi Isaacs(HJI) equation by minimizing or maximizing the growth of chosen level-set functions.In this paper, we present a solution methodology for multi-player (multi-pursuer) pursuit and evasiongame. Control strategies for the players are derived from certain value functions, rather than computingcontrol strategies from the solution of associated HJ equations. The elegance of this metho d is in that itprovides analytical expressions for the (non-optimal) strategies, accommodates nonlinear dynamics easily,and can b e extended to include more players and/or different value (or objective) functions. The simplifiedform of the strategies also offers practical implementation for real-time systems.∗This study is supported by the DoD Multidisciplinary University Research Initiative (MURI) program administered by theOffice of Naval Research under Grant N00014-02-1-0720.†Research Associate, Department of Aeronautics and Astronautics, AIAA member, [email protected]‡Associate Professor in Department of Aeronautics and Astronautics, and Courtesy Associate Professor in Department ofElectrical Engineering, Director of Hybrid Systems Lab., AIAA member, [email protected] of 10American Institute of Aeronautics and AstronauticsAIAA Guidance, Navigation, and Control Conference and Exhibit15-18 August 2005, San Francisco, CaliforniaAIAA 2005-6239Copyright © 2005 by the American Institute of Aeronautics and Astronautics, Inc. All rights reserved.Figure 1. Relative coordinate system: origin is located at the center of the evader, and is oriented so thatevader has 0 degree heading angle with respect to the horizontal axis.This paper is organized as follows. Section II defines the problem discussed in this paper. Section IIIderives control strategies for players using chosen value functions and computes the corresponding reachableset incorporated into the devised control strategies. Section IV presents simulation results and Section Vpresents a control strategy for the pursuers derived from a different value function. Finally, Section VIconcludes this pap er.II. Problem StatementThis section defines some notions for pursuit-evasion game between n identical players. The game isassumed to be of non-zero sum variety. Consider a planar n player game where aircraft dynamics are givenin the following relative coordinates (see Figure 1):˙xi=ddtx1ix2ix3i=−v + v cos x3i+ ux2iv sin x3i− ux1idi− u= f (xi, u, di) (1)where (x1i, x2i) and x3irespectively represent a relative position and a relative heading angle of the ithpursuer with respect the evader, v is the speed of the aircraft, and diand u are the control input of the ithpursuer and the evader respectively. Magnitudes of the control input belong to the following norm boundedsetsu ∈ {a ∈ R | kak ≤ µ} , di∈ {b ∈ R | kbk ≤ ν} (2)where µ and ν are positive constants.Instead of formulating the problem as the corresponding minmax optimization (the pursuer wants tominimize the distance with the evader and the evader wants to maximize it), where the solution is associatedwith the corresponding HJI equations, the objective of the game is to 1) find control strategies satisfyingthe following constraint:(u∗→˙Je> 0d∗i→˙Jpi< 0(3)subject to kuk ≤ µ, kdik ≤ ν2 of 10American Institute of Aeronautics and Astronauticswhere Je=Pni=1Jpiand Jpi= x12i+ x22iare value functions associated with the evader and individualpursuers respectively. This implies that the pursuer wants to keep decreasing its distance from the evaderand the evader wants to increase the sum of distances with all pursuers. However, the proposed evader’scontrol strategy does not necessarily guarantee that the evader can avoid capture by any pursuer since theevader’s constraint (˙Je> 0) can be easily satisfied: for