An Introduction to Pursuit-evasion Differential Games

2020 American Control Conference
Denver, CO, USA, July 1-3, 2020
An Introduction to Pursuit-evasion Differential Games

Isaac E. Weintraub, Meir Pachter, and Eloy Garcia
Abstract— Pursuit and evasion conflicts represent challeng- differential games is the synthesis of saddle-point strategies
ing problems with important applications in aerospace and that provide guaranteed performance for each team regardless
robotics. In pursuit-evasion problems, synthesis of intelligent of the actual strategies implemented by the adversary.
actions must consider the adversary’s potential strategies.
Differential game theory provides an adequate framework to This paper serves as an introduction into the area of
analyze possible outcomes of the conflict without assuming two-team pursuit-evasion differential games with a focus on
particular behaviors by the opponent. This article presents multi-player problems, that is, games with three or more
an organized introduction of pursuit-evasion differential games players where team cooperation is implicitly required. An
with an overview of recent advances in the area. First, a outline of seminal work on the area of differential games
summary of the seminal work is outlined, highlighting impor-
tant contributions. Next, more recent results are described by which highlights important contributions and potential appli-
employing a classification based on the number of players: cations is given in Section II. This is followed by an overview
one-pursuer-one-evader, N-pursuers-one-evader, one-pursuer- of important contributions in the field using a suitable
M-evaders, and N-pursuer-M-evader games. In each scenario, categorization based on number of players in Section III.
a brief summary of the literature is presented. Finally, two Cooperation between agents of the same team is emphasized
representative pursuit-evasion differential games are studied in
detail: the two-cutters and fugitive ship differential game and both in theoretical and practical terms. From a theoretical
the active target defense differential game. These problems point of view, the saddle-point solution of a differential game
provide two important applications and, more importantly, with multiple players in one or both teams requires the
they give great insight into the realization of cooperation strictest level of cooperation. From a practical perspective,
between friendly agents in order to form a team and defeat cooperation improves team performance compared to the
the adversary.
individual efforts. The paper culminates with two represen-
I. I NTRODUCTION tative case studies in Sections IV and V which illustrate
Pursuit-evasion problems provide a general framework both the tools available to synthesize and verify optimal
that mathematically formalizes important applications in strategies and the important cooperation aspect within multi-
different areas such as surveillance, navigation, analysis of player differential games.
biological behaviors, and conflict and combat operations. II. S EMINAL W ORK
Pursuit-evasion sets up (in the simplest case) two players or
autonomous agents against each other; generalizations are The development of differential games started with the
typical in the sense of multiple players divided into two works of [3]–[8]. In these publications, Isaacs outlined
teams – the pursuer team against the evader team. The main the idea of posing problems in a dynamic game-theoretic
purpose is to provide strategies that enable an autonomous framework; he called this paradigm “Differential Games”.
agent to perform a set of actions against the opponent, for In his seminal treatise [3], Isaacs employed the principles of
instance, the pursuer aims at determining a strategy that will game theory, calculus of variations, and control theory, albeit
result in capture or interception of the evader. unknown to him, to solve problems involving a dynamic
It is common to approach pursuit-evasion problems by conflict between multiple agents/players, [3]. Isaacs used the
imposing certain assumptions on the behavior of the op- method of differential dynamic programming and introduced
ponent [1], [2]. However, many pursuit-evasion scenarios critical mathematical constructs such as dispersal, universal,
must address the presence of an intelligent adversary which and equivocal surfaces used to describe the optimal flow field
does not abide by a restricted set of actions. The desire in games and derive optimal saddle point strategies.
to design strategies that optimize a certain criterion against It is important to recognize some of the founders of
the worst possible actions of the opponent and that also static/dynamic games and optimal control including RAND
provide robustness with respect to all possible behaviors scientists such as Richard E. Bellman, Leonard D. Berkovitz,
of the same opponent, led to the emergence of differential David H. Blackwell, Melvin Dresher, Wendell H. Flemming,
game theory [3]. The central problem in pursuit-evasion and John F. Nash. Early contributions on dynamic games in
the former Soviet Union were published by N. Krasovskii,
I. Weintraub is with the Aerospace Systems Directorate, Air A. Melikyan, L. S. Pontryagin, and A. I. Subbotin [9].
Force Research Laboratory, Wright-Patterson AFB, OH 45433. Furthermore, at the first conference dedicated exclusively
isaac.weintraub.1@us.af.mil
M. Pachter is with the Department of Electrical Engineering, Air to dynamic games: “First International Conference on the
Force Institute of Technology, Wright-Patterson AFB, OH 45433. Theory and Applications of Differential Games” in Amherst,
meir.pachter@afit.edu MA, September 29-October 1, 1969, organized by Ho and
E. Garcia is with the Control Science Center of Excellence,
Air Force Research Laboratory, Wright-Patterson AFB, OH 45433. Leitmann. Isaacs, Berkovitz, Bernhardt, Blaquiere, Break-
eloy.garcia.2@us.af.mil well, Case, Friedman, Merz, Pontryagin, and Shubik were
978-1-5386-8266-1/$31.00 ©2020 AACC 1049
Authorized licensed use limited to: University of Wollongong. Downloaded on August 16,2020 at 14:08:54 UTC from IEEE Xplore. Restrictions apply.
among the invited speakers. Although Pontraygin was not to one another. These are minimax problems, that is, zero-
able to attend the meeting, these mathematicians and scien- sum-games, since an optimal solution for the performance
tists planted the seeds of the theory of optimal control and functional is one in which the strategy of one of the players
differential games. seeks to minimize the performance functional while the strat-
Of a large number of mathematicians and scientists which egy of the other player tries to maximize it. Constraints on
were involved in the development of differential games, the player’s come in the form of dynamics. These constraints
Rufus Isaacs, Richard Bellman, John Breakwell, and Lev can be linear or nonlinear. The classical problem of pursuit-
Pontryagin can be seen as principal contributors to the devel- evasion can be seen in an early work by Ho, Bryson, and
opment of the theory of differential games; Isaacs being the Baron [13]. In their work, a two-player differential game
father of Differential Games. His seminal work and his book was formulated in a Linear-Quadratic form to capture the
highlighted the possible use of differential games to solve basic pursuit-evasion conflict. Later, in the NASA technical
many problems, [3], [4]. Bellman, known for the method of report [14], differential models were employed in order to
dynamic programming, provided a tool whereby state feed- gauge the differences in performance between a manually
back optimal strategies could be directly obtained as opposed piloted vehicle and an optimally controlled one as provided
to methods based on necessary conditions as is the calculus in the earlier work, [13]. The experiment showed that the use
of variations, [10], [11]. Pontryagin, a Soviet mathematician, of differential games indeed provided useful information to
is recognized as developing his Maximum Principle (We’ll pilots, but a cautionary statement at the end of the technical
refer to it as Pontryagin’s Minimum Principle (PMP) for report stated that, ”...differential game problems will, in
the rest of this paper) for necessary conditions for optimal general, be more complicated theoretically than their optimal
control in the presence of hard constraints on control. Using control counterparts.” The NASA report concluded that the
methods derived by these four mathematicians, differential idea of solving differential games was thought to be useful
games were formulated and solved in many works to be as information provided to a pilot, but not yet accepted to
described throughout this paper. be a means of automatic control, a popular research topic
today.
III. OVERVIEW OF R ECENT R ESULTS IN In a dissertation by Satimov [15], the application of differ-
P URSUIT-E VASION ential games was envisioned for use in various fields such as
economics and military operations. Satimov also stated that
At the center of Differential Games lies the fundamental in the case of a single-player, differential games amount to
conflict of two parties known as “Pursuit-Evasion”. Pursuit- optimal control problems, and that different modifications of
evasion involves at least two agents or groups, labeled Isaacs’ method give the necessary and sufficient conditions
Pursuers and Evaders. The goal of a pursuer is to capture for optimality. The relationship between optimal control
evading agents, while the converse is the goal of an evader, and differential games is through the use of variational
to avoid being captured by a pursuer. This is a zero-sum game techniques, [3], [16]. If all but one of the player’s control
where the cost/payoff is the time-to-capture. Basic questions laws are given, the differential game reverts to a one-sided
arise, “What path should an evader or pursuer take to achieve optimal control problem.
their goal of avoiding or ensuring capture; and, under optimal
1) Homicidal Chauffeur Game: In his seminal text, Isaacs
play, by either pursuer or evader, is capture at all possible?”
proposed the famous “Homicidal Chauffeur” problem [3].
In this article, we begin by looking at this conflict and briefly
In this game, a hypothetical slow but highly maneuverable
discuss the current literature available describing strategies,
holonomic pedestrian is pitted against a driver of a mo-
methods, and applications. We invite the interested reader
tor vehicle which is faster but less maneuverable (a.k.a.
to read the great historical and literature surveys of Isaacs’
a Dubin’s Car). In this somewhat macabre scenario, the
work documented in [9], [12].
driver attempts to run over the pedestrian. The question
The idea of pursuit-evasion differential games is not to be solved is: Under what circumstances, and with what
limited to physical entities chasing after one another; Isaacs strategy, can the driver of the car guarantee that he can
defined kinematic equations which described the surfaces always catch the pedestrian or conversely, the pedestrian
upon which states were constrained. Using these differential guarantee that he can indefinitely elude the car, [3]. And, if
equations, one could propose problems in other research the pedestrian’s demise is guaranteed, what is the chauffeur’s
areas including but not limited to economics, sports, robotics, optimal strategy that will minimize the time-to-capture of
and air-combat. In this article, the focus is on differential the pedestrian, and what is the latter’s strategy to maximize
games of pursuit-evasion, but it is important to note that the his time? This simple game is a classical 1-pursuer-1-evader
applications of these mathematical tools are not limited to problem used to represent military applications for reasons
these simple, toy problems, a syllogism for more complex of acceptance and publication. Surveys have documented the
scenarios which may not be suitable for the public domain. history and notable work related to the “Homicidal Chauffeur
Differential Game,” [9], [17]–[19], going into detail and
A. One Pursuer, One Evader (1v1) expanding about the various aspects of this problem.
The premise of a differential game starts with the conflict A definitive work on the Homicidal Chauffeur Differen-
between two players who share a common performance tial Game is Merz’s Ph.D. thesis, [20]. Merz investigated
functional; the goals of the pursuer and evader are counter the Homicidal Chauffeur Differential Game in great detail
1050
describing two new singular lines known as: “switch enve- Kothari goes into detail of both games of kind and degree
lope” and “focal line.” These new lines further expand on with studies on differing agent’s speeds, capture radius and
Isaacs’ “barrier”, “universal”, and “equivocal” singular lines. maneuverability constraints, [27]. In their work, they develop
His work gives great detail and insight into the problem. the three-dimensional plots of the state space, highlighting
Breakwell and Merz helped motivate the complete solution the barrier and switching surfaces for the different scenarios.
of the Homicidal Chauffeur game at a conference in 1969, 3) Pursuit-Evasion in Constrained Environments: In an
[21]. Marchal also studied the Homicidal Chauffeur game effort to consider differential games in a more realistic
in great detail describing how using Pontryagin’s Minimum way, the introduction of boundaries and constraints on states
Principle could assist the interpretation of complex solutions, allows for finite spaces and regions to be included in
[17]. the game formulation. By imposing limitations on physical
2) The Two Cars Differential Game: A variation of the states, the pursuit-evasion differential game can be restricted
Homicidal Chauffeur Differential Game is the “Two Cars” to a bounded area or obstacles may be applied. A two
Differential Game where two players, each controlling a player differential pursuit-evasion game where an obstacle is
car with minimum turning radius, are engaged in a pursuit- added to delay the pursuer or to avoid capture entirely was
evasion game. In early work, Meier investigated the problem proposed by Fisac and Sastry [28]. Similarly, the reference
of Two Cars where both players had the same minimum [29] considered pursuit-evasion games in the presence of
turn radius, the pursuer was slower than the evader, and obstacles which inhibit the motion of the players. In their
the capture was defined by coming inside the range, l, of work, the use of polygons, line-segments, and asymmetric
the Evader, [22]. Another analysis of the Two-Car problem obstacles (an obstacle which effects one player differently
was performed by [23], [24]. In their papers, regions of than another) are developed. Fuchs and Khargonekar moti-
capture, escape, and barrier surfaces between those regions vated the use of escort regions through manipulation of the
were presented. Fig. 1 describes the geometry of the Two-Car performance functional, [30]. In [31] the pursuer and evader
Problem. Radius R1 and R2 describe the minimum turning are constrained to road networks and, in [32], a one-sided
radii of each player, u1 and u2 describe the curves associated constrained is imposed where the pursuer is not restricted to
with a max rate turn, and w1 & w2 describe each player’s a road network while the evader is.
velocity. 4) Pursuit-Evasion with Incomplete Information: In cases
where one or more agents do not have complete information
about the state of the game, these are problems called “Dif-
ferential Games of Incomplete Information.” In his seminal
work, [3] stated that the ability to pose problems which
restricted information to the individual players “...appears to
be the most vital area for future research.” Roxin and Tsokos,
introduced a stochastic approach as a means of modeling
partial information one agent might have relative to another,
[33]. Chernousko and Melikyan described a differential game
where incomplete information is provided to one of the
agents [34]. This idea was proposed in order to account for
information delay or gaps of information during game play.
Yavin proposed an incomplete information pursuit-evasion
differential game by restricting the pursuer’s information on
Fig. 1. The coordinate frames and turning radii used to describe the Two bearing and allowed the Evader to have perfect informa-
Cars Problem [23] Radius R1 and R2 describe the minimum turning radii tion in the engagement, [35]. Giovannangeli, Heymann and
of each player and u1 and u2 describe the curves associated with a max Rivlin tackled the problem of pursuit while avoiding convex
rate turn. w1 and w2 describe each player’s velocity.
obstacles by using Apollonius circles to provide paths in-
which the pursuer’s visibility of the evader is guaranteed
In [23] both agents have sector based regions of capture, throughout the engagement, [36]; the geometric concept of
typical of an aerial dogfight; but, in [24], the regions of Apollonius circle will be formally defined in Section IV-B.
capture were different, describing a heterogeneous model In [37], Hexner considered the problem where a parameter is
of on-board weapon systems. Similarly, in [25], Greenfield unavailable to only one player at the beginning of the game,
looked into the two-car problem, endowing the pursuer with and the other has a probability density function describing
a surveillance capability of range, l. The objective, to escape that parameter was described. Pachter and Yavin investigated
the surveillance region in minimum time. In an earlier work, the effects of noise on the Homicidal Chauffeur problem
Lewin investigated a similar differential game called the by introducing stochasics to the pursuit-evasion differential
“Surveillance-Evasion” Differential Game [26]. In the game, game dynamics, [38]. Battistini and Shima also employed
the evader strives to escape as soon as possible from the a stochastic model to overcome the limitations imposed by
pursuer’s detection circle, while the pursuer’s desire is the bearing-only measurements made by a pursuer, [39].
opposite. The authors of [40] studied a differential game with non-
A complete analysis performed by Bera, Makkapati, and linear stochastic equation where two players are subjected
1051
to noisy measurements. The paper [41] presented an N- and are numericaly determined.
pursuer-1-evader differential where the evader can observe
all the pursuers but the pursuers have limited observations B. N Pursuers, 1 Evader (Nv1)
of themselves and the evader. A pursuit-evasion game was The two-pursuer-1-evader problem had been well docu-
studied in [42] where a pursuer engages an evader using mented, [56]–[61]. Hagedorn and Breakwell investigated two
Unattended Ground Sensors (UGSs) that detect the evader’s pursuers engaging one evader which was required to pass
passage in a road network; when the pursuer arrives at an between the two pursuers, [56]. The game of degree was
instrumented node, the UGSs inform the pursuer if and when addressed in [57], [58] by employing the following payoff
the evader visited the node. functional: the distance between the object being pursued
5) Pursuit Evasion in Aerial Engagements: Applications and the pursuer closest to it, when a fixed-time engagement
of pursuit-evasion differential games relating to tactical air- terminates. The paper [59] considered the three-player game
to-air applications have been investigated. Shinar and Gut- in detail by briefly discussing the surfaces of the differential
man developed a closed form solution to a 3-Dimensional game when pursuers were both stronger, both weaker, and
missile-aircraft pursuit-evasion game, [43]. Shinar also in- one stronger-one-weaker than the evader. The authors of
vestigated a realistic pursuit-evasion engagement involving a [60] studied the case where faster pursuers cooperate to
missile engaged on an aircraft and air-to-air scenarios using capture a slower evader in minimum time. Hayoun and
variational methods, [44]. Considering naval applications, Shima restrict the pursuer’s controls to be bounded and their
Pachter and Milch framed their two-player engagement as a intercept times equal, [61]. Using two “strong” pursuers,
Homicidal Chauffeur Differential Game where dynamics of closed-form optimal controls are derived, and it is shown that
the ships are taken into account, [45]. Greenwood designed the addition of a second pursuer introduces a new singular
a realistic differential game in 3-dimensions by modeling zone to the game space in which the pursuers can guarantee
fighter aircraft, [46]. Greenwood used dynamics of two equal misses, regardless of the evaders actions.
fighter aircraft in space and even considered firing envelopes In the more general case, where there are N-pursuers
as part of this barrier analysis. In [47] a differential game and 1-evader, challenges with task allocation and strategy
is proposed which involves a pursuit-evasion engagement become more apparent. In order to aid the task allocation
between a missile and an aircraft. In the game formulation, between the N-pursuers, Huang and Bakolas employ the
a nonlinear miss-distance was used as a payoff functional. Voronoi diagram construct. It is used when capture of an
In [48] a pursuit-evasion game where the dynamics of the evader within a bounded domain is considered, [62], [63].
pursuer can be changed during the pursuit a finite number of In [64] sufficient conditions are presented for the existence
times was investigated. In [49], the evader has the ability to of an evasion strategy where simple motion kinemtics for
change their dynamics during the engagement a finite number the players is considered. The paper [65] considered a more
of times. Merz investigated the problem of pursuit or evasion general case of N-pursuers engaged against one evader.
selection if both agents were endowed with capture sets and Huang et al. employed a decentralized control scheme based
prior assignment had not been implemented, [50]. Related on the Voronoi partition of the game domain, where the
to dog-fights and aerial combat, Merz’s concern was with pursuers jointly shrink/minimize the area of the evader’s
role assignment in pursuit-evasion differential games and of Voronoi cell, [62]. Fig. 2 is a visualization of the individual
course the outcome. In more recent work [51], [52] the target pursuer cells from [63].
area defense differential game has been investigated and it
will be described in more detail in Section V.
6) Other 1V1 Works: Another example of posing the
pursuit-evasion problems using simple motion kinematics
in a differential game is in a work by Leitmann, [53]. In
this paper, a simple differential game between a pursuer
and evader was proposed, and variational techniques were
applied to determine outcomes of the game where terminal
miss distance was used as the payoff/cost functional.
In [54], Calise and Yu use simple motion kinematics
as well as expanded control energy to formulate a game
involving the pursuit-evasion of two aircraft at medium to
long range. Using a reduced-order model with control energy,
Calise and Yu are able to find trajectories similar to minimum
time intercept using only four states to model the encounter.
The “Lion and the Man” differental game discussed by
Quincampoix is a pursuit-evasion differential game where
the lion pursues a man, [55]. The lion and the man are free to
change their velocity direction instantaneously but are limited Fig. 2. A Voronoi Diagram [63] describing the task allocation in an N-
pursuer, 1-evader problem. Each color describes a cell from which a pursuer
to the intensity with which they do so. Since the lion is faster would capture an evader if starting in that cell. © 2010 IEEE
than the man, the regions of escape and capture are of interest
1052
The N-pursuer-1-evader problem was investigated in [66]
by focusing on guaranteed escape of the evader. The refer-
ence [67] considered identical non-holonomic players where
a computationally efficient algorithm to obtain approximate
solutions is proposed. Solutions to a multi pursuer single-
superior-evader pursuit-evasion differential game using fuzzy
logic methods were developed in [68], [69], where the
formation control mechanism guarantees that the pursuers
are distributed around the superior evader in order to avoid
collision between pursuers and guarantees that the capture
regions of each two adjacent pursuers are such that the
capture of the fast evader is guaranteed. VonMoll et. al. also
have considered multiple pursuers engaged on a single evader Fig. 3. Example of 1-pursuer-2-evader engagement and 1-pursuer-5-evader
[70]–[72]. By utilizing the Apollonius circles, they exploit engagement found in [78]. Since the pursuer is much more capable than the
evaders capture of all agents is guaranteed. © 2013 IEEE
the benefits of cooperation amongst the pursuers in order to
reduce the capture time of the evader.
C. 1 Pursuer, M Evaders (1vM) task allocation method to simulate the optimal engagements
The single pursuer against M-evaders differential game for “fixed sequence capture” and “free sequence capture” of
is a game where a pursuer tries to capture M-evaders in the pursuer is applied in that reference.
finite time. One challenge is to select the order in which the
pursuer accomplishes his task in minimum time. In, these D. N Pursuers, M Evaders (NvM)
problems the pursuer is faster, more maneuverable, or has The most general case of N-pursuers and M-evaders allows
other advantages over the evaders. for more complex engagements to be analyzed. Katz et. al
The case which involves two evaders and one pursuer has investigated a zero-sum differential game formulation for
received much attention, [73]–[76]. In [73] the case where a the control of military air operations using the method of
single pursuer engages two evaders was addressed. The goal characteristics, [81]. Although their examples were shown for
of this work was to investigate a differential game where the 1-Pursuer 1-Evader, their work has extensions to N-pursuer
pursuer tries to capture either of the evaders, minimizing n-Evader problems. Rusnak proposed a dynamic game called
its cost, and the evaders strive to escape the pursuer for “The Lady and the Body-Guards versus the Bandits”, [82].
as long as possible, increasing the payoff/functional of the The Bandits’ team objective is to capture the Lady while the
pursuer. Scott and Leonard investigated a scenario where Lady and her Body-Guards objective is to prevent it. The
two evaders employ coordinated strategies to evade a single Body-Guards are trying to intercept the Bandits prior to their
pursuer, but also to keep them close to each other, [74]. In arrival to the proximity of the Lady. The formulation and
[75], Breakwell and Hagedorn investigated the capture of solution of the game is presented. As described in Section
two evaders in succession by one pursuer in minimum time. V, this problem is a similar problem, but with more players
Pachter and Yavin proposed a differential game of pursuit- involved. A creative approach to handing the task allocation
evasion with one pursuer and two evaders, the motion of the of many agents was proposed by Bakolas and Tsiotras by
players being affected by noise, [76]. The stochastic game of employing the Voronoi diagram construct, [63]. Using the
degree is considered, where the pursuer strives to maximize Voronoi diagram, such that a pursuer residing inside a given
the probability of his winning the game, i.e., of capturing set of the partition can intercept a moving target faster than
at least one of the evaders. A 3-Dimensional pursuit-evasion any other pursuer outside the set. Another means of task
differential game consisting of a pursuer engaged against a allocation was proposed in [83] where Awheda and Schwartz
team consisting of two evaders was proposed in [77]. The proposed a fuzzy logic based decentralized control scheme
team of evaders consisted of a true evader and false decoy using the Apollonius circles construct. A formal analysis
evader; the evaders coordinate their actions to ensure the true of both optimal guidance and optimal assignments of N
evader escapes without capture. pursuers to M evaders, for N ≥ M , was undertaken in [84].
In a more general case of one pursuer engaged against Finally, the papers [85]–[87] address multiplayer differential
many evaders, the pursuer aims at capturing all evaders, games based on numerical solutions of Hamilton-Jacobi-
while the evaders coordinate their escape. Liu and Zhou in- Isaacs (HJI) equations.
vestigated a game involving a single-pursuer-multiple-evader
pursuit-evasion game where a superior pursuer attempts to IV. T WO C UTTERS AND F UGITIVE S HIP D IFFERENTIAL
minimize the total capture time of all the evaders, [78]. G AME
Fig. 3 shows the capture of M-evaders in succession from This section provides a detailed treatment of Isaacs’ clas-
[78]. In [79] the study of capture time for many pursuers sical problem of two cutters and fugitive ship differential
against one or more evaders is investigated. The authors of game where two faster pursuers cooperate to capture a
[80] formulate and solve a pursuit-evasion game in which slower evader in minimum time. The evader, knowing that
a single faster player chases several homogenous evaders; a is being pursued by two cooperative and fast pursuers,
1053
tries to maximize the capture time. Isaacs proposed the time without cooperation. This problem has important reper-
players’ optimal strategies in [3] and these strategies were cussions; although one pursuer is guaranteed to capture a
verified in [60] where the Value function was obtained and slower Evader in an open plane, there exist situations where
it was shown to be continuous, continuously differentiable, the Evader may win the game by reaching a certain subset
or C 1 , and the solution of the Hamilton-Jacobi-Isaacs (HJI) of the space or exiting the domain of the game. For instance,
Partial Differential Equation (PDE). This section extends consider an evading ship fleeing a pursuer and trying to exit
the presentation in [60] by offering a complete proof of the influence zone of the later. In this case the Pursuer would
the verification theorem pertaining to the two cutters and benefit from a second Pursuer and cooperation that strive
fugitive ship differential game, it also identifies the game’s to minimize the capture time preventing the Evader from
singular surface which is of dispersal type, and it illustrates reaching a safe haven.
the applicability of the solution of this differential game to The controls of E, P1 , and P2 are their respective in-
address interesting and more complex pursuit-evasion games stantaneous headings φ, ψ1 , and ψ2 . The states of E, P1 ,
with multiple pursuers and multiple evaders. and P2 are defined by their Cartesian coordinates in the
One of the fundamental concepts in differential games is realistic plane xE = (xE , yE ), xP 1 = (xP 1 , yP 1 ), and
the HJI PDE which provides a sufficient condition for the xP 2 = (xP 2 , yP 2 ), respectively. The complete state of the
existence of a Nash equilibrium. Regardless of how the Value game is defined by x := (xE , yE , xP 1 , yP 1 , xP 2 , yP 2 ) ∈ R6 .
function is obtained, the HJI equation can be used to verify The Evader’s control variable is his instantaneous heading
that such function indeed meets the optimality conditions. angle, uE = {φ}. P1 and P2 affect the state of the game
Moreover, since the gradient of the Value function takes the by choosing the instantaneous respective headings, ψ1 and
place of the co-states in the PMP, a direct solution of the ψ2 , so the Pursuers’ control variable is uP = {ψ1 , ψ2 }. The
HJI PDE can be used to synthesize the optimal strategies. In normalized dynamics in the realistic plane ẋ = f(x, uP , uE )
this section we use the former objective, that is, verification. are specified by the system of ordinary differential equations
In the following, we summarize the sufficient conditions for
ẋE = cos φ, ẏE = sin φ
a Nash equilibrium.
ẋP 1 = β1 cos ψ1 , ẏP 1 = β1 sin ψ1 (4)
Consider the following dynamics
ẋP 2 = β2 cos ψ2 , ẏP 2 = β2 sin ψ2
ẋ = f (t, x(t), u(t), v(t)) (1)
where β1 = vvPE1 > 1 and β2 = vvPE2 > 1 are
for t ∈ [0, tf ] and x(0) = x0 . The input variables u(t) the normalized speeds of the two Pursuers and they
and v(t) are the controls of each team, which are required are not necessarily equal. The initial state is x0 :=
to belong to an appropriate subspace. The performance (xE0 , yE0 , xP 10 , yP 10 , xP 20 , yP 20 ) = x(t0 ). We confine our
functional is attention to point capture, so the game terminates at time tf
Rt when the state of the system satisfies the terminal condition
J = q(x(tf )) + 0 f g(t, x(t), u(t), v(t))dt (2)
a) xP 1 = xE , yP 1 = yE , or
State feedback policies are considered, that is, u(t) = b) xP 2 = xE , yP 2 = yE , or (5)
µ(t, x(t)) and v(t) = ν(t, x(t)), for t ∈ [0, tf ]. c) both a) and b) apply.
Theorem 1: [88]. Assume that there exists a C 1 function
V (t, x(t)) that satisfies the HJI PDE The terminal time tf is defined as the time instant
when the state of the system satisfies any one of
− ∂V
∂t =
∂V
∂x · f(t, x, u∗ , v ∗ ) + g(t, x, u∗ , v ∗ ) (3) the conditions in (5), the terminal state being xf :=
(xEf , yEf , xP 1f , yP 1f , xP 2f , yP 2f ) = x(tf ). The Evader
with V (tf , x) = q(x). Then, the pair of strategies u∗ = strives to maximize the capture time while the Pursuers
µ∗ (t, x(t)) and v ∗ = ν ∗ (t, x(t)) is a saddle-point equilibrium cooperate to minimize the capture time, so the performance
in state feedback policies. functional is
Z tf
This result will be used to verify the solution of the two min max dt (6)
cutters and fugitive ship differential game in Section IV-C ψ1 ,ψ2 φ 0
but first we provide a formulation of the problem. subject to (4)-(5).
A. Problem Formulation B. Solution
Consider one Evader E and two Pursuers P1 and P2 with In this section we follow the procedure to derive regular
simple motion dynamics and constant speeds vE , vP 1 , and solutions of differential games [89], [90]. We introduce the
vP 2 , respectively; the players are holonomic. It is assumed co-states λ := (λxE , λyE , λxP 1 , λyP 1 , λxP 2 , λyP 2 ) ∈ R6 and
that the pursuers are faster than the evader. Through explicit the Hamiltonian of the differential game is formulated as
cooperation, the Pursuers aim at intercepting the Evader follows
in minimum time, while the Evader tries to maximize the
capture time. The advantage of having two cooperative H = 1 + λxE cos φ + λyE sin φ
Pursuers is that, depending on the initial positions of the + β1 λxP 1 cos ψ1 + β1 λyP 1 sin ψ1 (7)
players, the cooperative capture time is less than the capture + β2 λxP 2 cos ψ2 + β2 λyP 2 sin ψ2 .
1054
The optimal control inputs (in terms of the co-state variables) headings correspond to the cases where the Pursuer runs
are obtained from away from the Evader). Note that tf1 = 0 (respectively
tf2 =p0) only if r1 = 0 (respectively, r2 = 0), where
min max H ≡ 0 (8)
ψi ,ψ2 φ ri = (xE − xP i )2 + (yE − yP i )2 , for i = 1, 2. In such a
and they are given by case the Evader has been captured and the Game has ended.
Let us assume that condition a) in (5) is active, whereupon
cos φ∗ =√ λx
E , sin φ∗ = √ λy
E
(9) the optimal Evader strategy is obtained by solving
λ2 2
xE +λyE λ2 2
xE +λyE
maxφ tf1
(16)
cos ψ1∗ = − √ λx
P1 , sin ψ1∗ = − √ λy
P1 subject to eq. (12)
λ2 2
xP 1 +λyP 1 λ2 2
xP 1 +λyP 1
(10) which can be computed by solving for φ in

dtf1
= −c1 sin(φ − λ1 )
cos ψ2∗ = − √ λx
P2 , sin ψ2∗ = − √ λy
P2 . dφ
2 ∗ ∗
λ2 2
xP 2 +λyP 2 λ2 2
xP 2 +λyP 2 c1 cos(φ −λ1 ) sin(φ −λ1 )
− √ 2 2 ∗
=0 (17)
(11) c1 cos (φ −λ1 )+c1 r10
∗
⇒ sin(φ − λ1 ) = 0 ⇒ φ = λ1
Additionally, we can determine the co-state dynamics by
calculating λ̇ = − ∂H as expected (the heading φ = λ1 + π will minimize tf1 and
∂x . Hence, the co-state dynamics are:
λ̇xE = λ̇yE = λ̇xP 1 = λ̇yP 1 = λ̇xP 2 = λ̇yP 1 = 0; then, since E chooses its heading φ then it would choose the one
all co-states are constant and the optimal control inputs (9)- that maximizes tf1 ).
(11) are constant as well. Because the optimal headings are Similarly, if condition b) in (5) is active, then the optimal
constant then the players’ optimal trajectories are straight Evader strategy is φ∗ = λ2 , as expected. In cases a) or b) the
lines. Also, since the terminal condition is point capture (5) solution of the Two-Pursuer One-Evader Differential Game
we have the following: For case a) in (5): (2P1EDG) simplifies to the solution of the differential game
with one pursuer and one Evader where the Evader runs
xP 1f = xP 10 +β1 tf1 cos ψ1∗ = xE0 +tf1 cos φ∗ = xEf directly away from the pursuer.
(12)
yP 1f = yP 10 +β1 tf1 sin ψ1∗ = yE0 +tf1 sin φ∗ = yEf Since it is not evident at the beginning which condition, a),
where tf1 ≥ 0 can be written in terms of φ∗ as follows b), or c), is active, then the individual conditions a) and b) are
q checked first as follows: Consider φ = λ1 and obtain tf1 (λ1 )
tf1 = c1 cos(φ∗ − λ1 ) + c21 cos2 (φ∗ − λ1 ) + c1 r10 (13) using (13). Then, substitute φ = λ1 in (15) to compute
tf2 (λ1 ) and compare:
where
y −y
E0 P 10
if tf1 (λ1 ) ≤ tf2 (λ1 ) (18)
λ1 = arctan
xE0 − xP 10 then φ∗ = λ1 and there is nothing Pursuer 2 can do to
p
r10 = (xE0 − xP 10 )2 + (yE0 − yP 10 )2 decrease the capture time tf1 (φ∗ = λ1 ).
1 Also, consider φ = λ2 and obtain tf2 (λ2 ) using (15).
c1 = 2 r1 . Then, substitute φ = λ2 in (13) to compute tf1 (λ2 ) and
β1 − 1 0
compare:
For case b) in (5) we have:
if tf2 (λ2 ) ≤ tf1 (λ2 ) (19)
xP 20 + β2 tf2 cos ψ2∗ = xE0 + tf2 cos φ∗
(14)
yP 20 + β2 tf2 sin ψ2∗ = yE0 + tf2 sin φ∗ then φ∗ = λ2 and there is nothing Pursuer 1 can do to
where tf2 ≥ 0 can be written in terms of φ∗ as follows decrease the capture time tf2 (φ∗ = λ2 ).
q If neither, condition (18) nor condition (19), is satisfied, we
tf2 = c2 cos(φ∗ − λ2 ) + c22 cos2 (φ∗ − λ2 ) + c2 r20 (15) check if the interesting condition c) is active. In such a case
of simultaneous capture of E by P1 and P2 , both equations
where (12) and (14) need to hold for the same φ∗ and for the same
y −y
tf = tf1 = tf2 , where tf1 and tf2 are given by (13) and

E0 P 20
λ2 = arctan
xE0 − xP 20 (15), respectively. Additionally, for initial conditions such
p
r20 = (xE0 − xP 20 )2 + (yE0 − yP 20 )2 that c) is active, the capture time will be reduced compared
to the individual cases where the game only involves E and
1
c2 = 2 r2 . P1 or only E and P2 . Hence, the complete solution of the
β2 − 1 0 2P1EDG should define the optimal saddle point strategies of
Finally, for the most interesting case c) in (5), both (12) and every player and the outcome of the game in terms of which
(14) are simultaneously satisfied for the same heading φ∗ . pursuer will actually capture the Evader.
Because β1 > 1 (respectively β2 > 1) there exists In case c) in (5) the triple (φ, ψ1 , ψ2 ) which simultane-
a (unique) solution ψ1 (respectively ψ2 ) to equation (12) ously satisfies (12)-(15) with tf1 = tf2 can be obtained from
(respectively (14)) for any φ ∈ [0, 2π]. However, the opposite the intersection of two Apollonius circles. The first circle
is not true. There exists a range of heading values for ψ1 is based on r10 and the speed ratio β1 . The second circle
(respectively ψ2 ) such that no solution φ exists (these Pursuer is based on r20 and the speed ratio β2 . The center of the
1055
Apollonius circle between E and Pi , for i = 1, 2, is at a
distance ci = β 21−1 ri0 from E and its radius is ρi = β 2β−1
i
ri0 .
i i
The coordinates of the circle center are
ai = xE + ρi cos λi , bi = yE + ρi sin λi
and the equation of the circle is
(x − ai )2 + (y − bi )2 = ρ2i (20)
for i = 1, 2. From the two points of intersection of the
circles, the Evader chooses the point that maximizes the
capture time, as expected; this point is the intersection
point of the Apollonius circles (20) which is the farthest
away from the Evader’s position (xE , yE ). Let I : (xI , yI )
−yE
be the aimpoint and we have that φ∗s = arctan( xyII −x E
),
∗ y −y ∗ y −y
ψ1s = arctan( xI −xP ), and ψ2s = arctan( xI −xP 2 ) which
I P1 I P2
1
guarantee simultaneous interception by both Pursuers. In the
case of simultaneous capture we have that λm ≤ φ∗s ≤ λM , Fig. 4. Regions R1 , R2 , and Rs . The initial position of the Pursuers are
where λm = min {λ1 , λ2 } and λM = max {λ1 , λ2 }. P1 : (0, 3) and P2 : (0, −3) and the speed ratio parameters are β1 = 1.3
In this section we described a method that provides a and β2 = 1.25.
simple way to design a state feedback pursuit strategy for
the 2P1EDG and it is summarized as follows.
Proposition 1: Consider the Two-Pursuer One-Evader where
Differential Game (4)-(6) where β1 > 1 and β2 > 1. The
tfi (x)= β21−1 (xE −xPi ) cos φ∗ +(yE −yPi ) sin φ∗

solution of the differential game is:
i
φ∗ = λ1 , ψ1∗ = λ1 if tf1 (λ1 ) ≤ tf2 (λ1 ) + [(xE −xPi ) cos φ∗ + (yE −yPi ) sin φ∗ ]2 (23)
φ∗ = λ2 , ψ2∗ = λ2
1/2
if tf2 (λ2 ) ≤ tf1 (λ2 ) +(βi2 −1)[(xE −xPi )2 +(yE −yPi )2 ]
φ∗ = φ∗s , ψ1∗ = ψ1s
∗
, ψ2∗ = ψ2s
∗
otherwise
(21)
Fi (x)= (yE − yPi ) cos φ∗ − (xE − xPi ) sin φ∗

C. Verification
In this section we obtain the Value function and it is ver- × [(xE −xPi ) cos φ∗ + (yE − yPi ) sin φ∗ ]2 (24)
−1/2
ified that the Value function is continuous and continuously +(βi2 −1)[(xE −xPi )2 +(yE −yPi )2 ]
differentiable and that it also satisfies the Hamilton-Jacobi-
Isaacs (HJI) Partial Differential Equation (PDE). and βi > 1, for i = 1, 2, where φ∗ (x, β1 , β2 ) is obtained
Based on the different outcomes of the Differential Game, from the points of intersection of the two Apollonius circles.
the capture set, namely, the whole state space, is partitioned The optimal Evader heading φ∗ is only a function of the state
into three subsets. These three subsets are: x (the positions of the three players) and of the speed ratio
- R1 : where E is only captured by P1 . parameters β1 and β2 . Due to the complexity of an explicit
- R2 : where E is only captured by P2 . expression of φ∗ , the terms cos φ∗ and sin φ∗ remain in V (x).
- Rs : where E is simultaneously captured by P1 and P2 . The physical meaning of the Value function is the capture
In addition, for given speed ratio parameters β1 and β2 time under optimal play. The Value function takes different
the subsets can be characterized using the conditions in (18) forms depending on which region the Evader is located; in
and (19). The subset of states that result in (18) (respectively, any case, it should be a function of the state of the system.
(19)) holding with equality represent the boundary between In region R1 , it is only a function of the states of E and P1 .
regions R1 and Rs (respectively, regions R2 and Rs ). An In region R2 , it is only a function of the states of E and P2 .
example of these regions is shown in Fig. 4. Provided that Finally, in region Rs , V has to be correctly written in terms
every agent plays optimally, Fig. 4 represents the property of the states of E, P1 , and P2 .
that if E is initially located inside R1 , then the outcome of The last form of V (x) in (22), where x ∈ Rs , is a convex
the game is that E is captured only by P1 . If E is in R2 , it combination of the Value of the game, the capture time, using
is captured only by P2 and if E is in Rs , then it is captured the states of both Pursuers. When x ∈ Rs the condition for
simultaneously by both Pursuers. simultaneous capture is that tf1 (φ∗ ) = tf2 (φ∗ ). In such a
We wish to obtain a state feedback solution. At any time case, we define tf (φ∗ ) ≡ tf1 (φ∗ ) = tf2 (φ∗ ).
t, 0 < t < tf the state is x(t) = [xE (t), yE (t), xP1 (t), Dispersal surface. A dispersal surface D ∈ Rs exists if the
yP1 (t), xP2 (t), yP2 (t)]T . The Value function is given by two intersections of the Apollonius circles are located at the
 √ same distance from the Evader’s position; hence, two optimal
(xE −xP 1 )2 +(yE −yP 1 )2

 √
 β1 −1 ∀ x ∈ R1 strategies exist. This dispersal surface will be illustrated in
V (x) = (xE −xP 2 )2 +(yE −yP 2 )2
∀ x ∈ R2 (22) Section IV-D. Let us define R− s = Rs − D and define the
β2 −1
subset of the state space where regular solutions apply R =

 F1 (x)tf2 (x)−F2 (x)tf1 (x)

∀ x ∈ Rs
F1 (x)−F2 (x) R1 ∪ R2 ∪ R− s .
1056
∂V
Theorem 2: Consider the Two-Pursuer One-Evader Dif- We now evaluate the term ∂φ∗ as follows
ferential Game (4)-(6). The solution of the differential game
∂V −F2 ∂tf1 F1 ∂tf2
is given by Proposition 1. The corresponding Value function ∂φ∗ = F1 −F2 ∂φ∗ + F1 −F ∂φ∗
∂ −F2
2 ∂ F1

is given by (22). Then, the Value function (22) is continuous + tf1 ∂φ∗ F1 −F2 + tf2 ∂φ ∗ F1 −F2
and continuously differentiable over R and it satisfies the = F−F
∂tf1 F1 ∂tf2
∗ + F −F
2
1 −F2 ∂φ ∂φ∗
HJI equation for any x ∈ R. ∂ F1 −F2
1 2
+ tf ∂φ∗ F1 −F2
Proof. We start by analyzing the gradient of V (x) in regions ∂tf1 ∂tf2
R1 and R2 . In the case where x ∈ R1 we can write = F−F 2
1 −F2 ∂φ
∗ + F −F
1
F1
2 ∂φ∗
∂V
∂xE = β11−1 cos λ1 , ∂V 1
∂yE = β1 −1 sin λ1 where
∂tfi
= Fi · tfi . Therefore,
∂V ∂V ∂V ∂V (25) ∂φ∗
∂xP 1 = − ∂x E
, ∂yP 1 = − ∂yE
∂V −F1 F2 F1 F2 F1 F2 −F1 F2
∂φ∗ = F1 −F2 tf1 + F1 −F2 tf2 = F1 −F2 tf =0
where
xE −xP 1
cos λ1 =√ since tf = tf1 = tf2 . Hence the gradient of the Value
(xE −xP 1 )2 +(yE −yP 1 )2
yE −yP 1 function (26) can be simplified and be written as
sin λ1 = √ .
(xE −xP 1 )2 +(yE −yP 1 )2
∂V −F2 ∂tf1 F1 ∂tf2
∂x = F1 −F2 ∂x + F1 −F2 ∂x
(28)
1
Therefore, the Value function V (x) is C inside region R1 .
Similar expressions to (25) can be obtained when x ∈ R2 to for x = {xE , yE , xP1 , yP1 , xP2 , yP2 }. Note that Fi (x) can be
show that V (x) is C 1 inside region R2 . written in the following form
Now, the partial derivative of the Value function with (yE −yPi ) cos φ∗ −(xE −xPi ) sin φ∗
respect to each element of the state x when x ∈ Rs is Fi (x) = Qi
∗ (29)
= √ 2sin(λi −φ )
∂V −F2 ∂tf1 F1 ∂tf2 cos (λi −φ∗ )+βi2 −1
∂x = F1 −F2 ∂x + F1−F2 ∂x
∂
+ tf1 ∂x −F2 ∂ F1
F1 −F2 + tf2 ∂x F1 −F2
(26) for i = 1, 2. Since λm ≤ φ∗ ≤ λM , we have that F1 and F2
∂V dφ∗ have different sign and F1 − F2 6= 0. From (27) and (29) we
+ ∂φ ∗ · dx
conclude that the Value function is C 1 inside region Rs .
where tfi = tfi (x) and Fi = Fi (x) are given by (23) It is now critical to show that the Value function is C 1 on
and (24), respectively, for i = 1, 2. The functions tfi , Fi , the boundary of each subset. We consider only the boundary
φ∗ , and V depend only on the state x. The notation (x) is between R1 and Rs since the proof for the boundary be-
dropped hereafter in order to simplify the notation in (26) tween R2 and Rs follows in the same way. On the boundary
and in the remaining equations of this proof. In eq. (26) between R1 and Rs we have that φ∗ = λ1 because of (17).
the variable x denotes each element of the state x, that is, We also have from (29) that F1 (φ∗ = λ1 ) = 0. Thus, the
∂t
x = {xE , yE , xP1 , yP1 , xP2 , yP2 }. The specific forms of ∂xfi Value function evaluated in region Rs is given by
are given by −F2
V (x) = −F2 tf1 = tf1 .
Then, it is sufficient to show that tf1 as given in Rs which
h
∂tfi
∂xE = cos φ∗ + Q1i [(xE − xPi ) cos φ∗
1
βi2 −1
is denoted by tf1 s in (30) below, is equal to tf1 as given in
+ (yE − yPi ) sin φ∗ ] cos
iφ
∗
R1 (the subscript s is attached to tf1 to show where tf1 is
+ (βi2 − 1)(xE − xPi ) evaluated in Rs ). Consider (23) evaluated at φ∗ = λ1
h
∂tfi
= β 21−1 sin φ∗ + Q1i [(xE − xPi ) cos φ∗
h
∂yE i tf1 s = β 21−1 (xE − xP 1 ) cos λ1 + (yE − yP 1 ) sin λ1
+ (yE − yPi ) sin φ∗ ] sin
iφ
∗ 1
+ [(xE − xP 1 ) cos λ1 + (yE − yP 1 ) sin λ1 ]2 i
(27)
+ (βi2 − 1)(yE − yPi ) + (β12 − 1)[(xE − xP 1 )2 + (yE − yP 1 )2 ]
1/2
(
∂t
− ∂xfEi if i = j
hp
∂tfi
∂xPj = = β 21−1 (xE − xP 1 )2 + (yE − yP 1 )2
0 otherwise 1
( + (xE − xP 1 )2 + (yE − yP 1 )2
∂tfi
∂tfi − ∂yE if i = j + (β12 − 1)[(xE − xP 1 )2 + (yE − yP 1 )2 ]
1/2 i
=
∂yPj
0 otherwise √ 2 2
(β1 +1) (xE −xP 1 ) +(yE −yP 1 )
= β12 −1
for i, j = 1, 2 where Qi = [(xE − xPi ) cos φ∗ + (yE − √
(xE −xP 1 )2 +(yE −yP 1 )2
yPi ) sin φ∗ ]2 + (βi2 − 1)[(xE − xPi )2 + (yE − yPi )2 ]
1/2
. = β1 −1
Note that Qi > 0. = tf1 .
Let us first analyze the terms in the second line of eq. (30)
(26). Since tf = tf1 = tf2 we have that Thus, the Value function is continuous on the boundary
between regions R1 and Rs .

∂ −F2 ∂ F1 ∂ F1 −F2
tf1 ∂x + t f = tf
F1 −F2 2 ∂x F1 −F2 ∂x F1 −F2 Let us now consider ∂V ∂x on the same boundary. We want to
= tf · 0 show that (28) is equal to (25) on the boundary between these
= 0. two subsets, where the optimal Evader strategy is φ∗ = λ1 ,
1057
and for the relevant states x = {xE , yE , xP 1 , yP 1 }. Note that It is only left to show that the HJI equation is satisfied in
∂V ∂V ∂tf1 ∂tf1
∂xP 2 = ∂yP 2 = 0 since F1 = 0 and ∂xP 2 = ∂yP 2 = 0. Let
Region Rs . To accomplish this we use (27) and (28) to write
∂V
us consider first ∂x E
in (28) evaluated at φ∗ = λ1 ∂V
· f(x, u∗P , u∗E )
∂x
∂V
= −F2 ∂tf1 = ∂V
∂xEcos φ∗ + ∂y ∂V
E
sin φ∗
∂xE −F2 ∂x ∗
hE ∂V
+ β1 ∂xP 1 cos ψ1 + β1 ∂y ∂V
sin ψ1∗
= β 21−1 cos λ1 P1
√1 i + β2 ∂x∂V
P2
cos ψ2∗ + β2 ∂y ∂V
P 2
sin ψ2∗
2 +(y −y 2 2
+ (xE −xP 1 ) √ P 1 ) cos λ1 +(β1 −1)(xE −xP )
E

∂t ∂t
β1 (xE −xP 1 )2 +(yE −yP 1 )2 (31) = F−F 2 f 1
+ F1F−F 1 f 2
cos φ∗ (36)
1
h 2 −1) cos λ
cos λ1 +(β1
i 1 −F2 ∂xE 2 ∂xE
= cos λ + 1

∂tf1 ∂tf2
β12 −1 1 β1 + F−F 2
1 −F 2 ∂yE
+ F1
F1 −F2 ∂yE sin φ
∗
β1 +1
= cos λ1 ∂tf1 ∂tf1

β12 −1
1 + F−F −F
2
∂x β 1 cos ψ ∗
1 + ∂y β 1 sin ψ ∗
1
= β1 −1 cos λ1 1 2 P1 P1
∂tf2 ∂tf2
+ F1F−F1
∂xP 2 β 2 cos ψ ∗
2 + ∂yP 2 β 2 sin ψ ∗
2
∂V 2
which is equivalent to ∂x E
as given by (25). Following a
∂V ∂V ∂V subject to
similar approach we obtain that ∂y E
, ∂x P1
, and ∂y P1
are
also continuous on the boundary between regions R1 and cos φ∗ xE −xPi
Rs . Hence the Value function is C 1 on the boundary between cos ψi∗ = βi + βi tf
sin φ∗ yE −yPi (37)
regions R1 and Rs . sin ψi∗ = βi + βi tf
The same steps can be followed to show that the Value
function is C 1 also on the boundary between regions R2 for i = 1, 2. Note that (37) are the optimal Pursuers’
and Rs . Therefore, altogether, the Value function is C 1 for headings written in terms of the Evader’s optimal heading
x ∈ R. φ∗ , where the Evader aims at the intersection point of the
Finally, we show that the Value function satisfies the HJI two Apollonius circles. In other words, (37) are obtained
equation from eqs. (12) and (14).
Substituting (37) into (36) we obtain
∂V (x, t) ∂V (x, t)
= arg min max f (x, uP , uE ) + 1 ∂V
· f(x, u∗P ,u∗E )
∂t uP uE ∂x ∂x
∂tf1 ∂tf1
with uP = [ψ1 , ψ2 ] and uE R= φ. In this expression, the = 1
tf · F−F 2
1 −F2
(xP 1 −xE ) + ∂yE (yP 1 −yE ) (38)
t ∂xE
term 1 follows from the cost 0 f 1dt. Then, for the optimal 1 F1 ∂tf2 ∂tf2
+ tf · F1 −F2 ∂xE (xP 2 −xE ) + ∂yE (yP 2 −yE )
feedback strategy, we have ∂V ∂t
(x,t)
= 0 and V (x, t) = V (x);
therefore, and we also evaluate the terms

1 ∂tfi ∂t

∂V (x) − xE ) + ∂yfEi (yPi − yE )
0 = arg min max f (x, uP , uE ) + 1 . (32) tf ∂xE (xPi h
uP uE ∂x
= − tf (β12 −1) (xE − xPi ) cos φ∗ + (yE − yPi ) sin φ∗
If u∗P = u∗P (x) and u∗E = u∗E (x) are (feedback) optimal i
solutions, then we can check if V is the value function by + Q1i [(xE − xPi )2 cos2 φ∗
checking + 2(xE − xPi )(yE − yPi ) sin φ∗ cos φ∗

∂V (x)
+ (yE − yPi )2 sin2 φ∗
∗ ∗ i
0= f (x, uP , uE ) + 1 . (33) + (βi2 − 1)[(xE − xPi )2 + (yE − yPi )2 ]
∂x h
In Region 1 we have the following: φ∗ = ψ1∗ = λ1 and = − tf (β12 −1) (xE − xPi ) cos φ∗ + (yE − yPi ) sin φ∗
i
∂V
∂x· f(x, u∗P , u∗E ) + Q1i [(xE − xPi ) cos φ∗ + (yE − yPi ) sin φ∗ ]2
= cos φ∗ + ∂y
∂V ∂V
sin φ∗
i
∂xE
∗
E + (βi2 − 1)[(xE − xPi )2 + (yE − yPi )2 ]
∂V
+ β1 ∂xP 1 cos ψ1 + β1 ∂y ∂V
sin ψ1∗ h
= − tf (β12 −1) (xE − xPi ) cos φ∗ + (yE − yPi ) sin φ∗
P1
= (β −1)√(x −x 1 )2 +(y −y )2 (xE − xP 1 ) cos λ1 ii
1 E P1 E P1
+ (yE − yP 1 ) sin λ1 −β1 (xE − xP 1 ) cos λ1 + Qi
− β1 (yE − yP 1 ) sin λ1 (34)
= − t1f · tf
= (β −1)√(x −x1−β1)2 +(y −y )2 (xE − xP 1 ) cos λ1 = −1
1 E P1 E P1
+ (yE − yP 1 ) sin λ1 h i (39)
2 +(y −y 2
= √(x −x )−1 √(xE −xP 1 ) E P 1)
E
2
P 1 +(yE −yP 1 )
2 (xE −xP 1 )2 +(yE −yP 1 )2 for i = 1, 2. Substituting (39) into (38) we have
= −1.
∂V ∗ ∗ −F2 F1

Therefore, we have that ∂x · f(x, uP , uE ) = F1 −F2 − 1 + F1 −F2 − 1
= −1
1+ ∂V
∂x · f(x, u∗P , u∗E ) = 1 − 1 = 0 (35)
and we can write
that is, the HJI equation is satisfied by the candidate Value
function in Region R1 . The same equation follows in R2 . 1+ ∂V
∂x · f(x, u∗P , u∗E ) = 1 − 1 = 0 (40)
1058
which means that the HJI equation is satisfied by the Value 14
function in Region Rs .
12
Remark. The Value function (22) determines the capture I
time when using the normalized (by vE ) speeds. In the case 10
where vE 6= 1 the Value of the game is simply scaled 8
by 1/vE to obtain the real capture time. We work with 6
y
normalized speeds since the constant factor 1/vE does not
4
change the results in this paper.
2
In summary, a solution of the 2P1EDG was proposed
and the Value function was obtained. In this section we 0
P1 E P2
have verified that the Value function is continuous and -2
continuously differentiable over R. It was also shown that
-4
the candidate Value function satisfies the HJI equation for 0 5 10 15 20
x
any x ∈ R. All this together plus the uniqueness property
of the Value function verifies that the proposed solution and Fig. 5. Optimal Trajectories
the candidate Value function are in fact the solution of the
Two-Pursuer One-Evader Differential Game.
D. Dispersal Surface and Multi-Pursuer Multi-Evader Dif- subspace. The unlikely outcome where both teams choose
ferential Game the same strategy for all 0 ≤ t ≤ tf was referred by Isaacs
The existence of a dispersal surface was discussed in as the perpetual dilemma [3].
Section IV-C and the condition is given by the distance from We have shown that the time of capture of a fleeing Evader
the Evader’s position to each one of the two intersection can be reduced when two Pursuers work cooperatively as
of the Apollonius circles. We illustrate the game’s dispersal a team compared to the single Pursuer case. We can use
surface through an example. the state feedback solution of the 2P1EDG in order to
Consider the initial positions: E = (5, 0), P1 = (0, 0), approximate the solution for a Multi-Pursuer Multi-Evader
P2 = (24, −4). The players’ speeds are: vE = 1, vP1 = 1.25, Differential Game, where, in addition of taking advantage of
vP2 = 1.3125. Initially, there exist two sets of solutions the cooperative behavior by the Pursuers, it is also necessary
that satisfy the optimality conditions; the two intersection to assign teams of Pursuers to capture each Evader. The
points are at the same distance from the Evader’s position objective is to minimize the capture time of the last Evader
and the state of the game is located on the singular surface where each Pursuer has to be assigned to one and only
of dispersal type, that is, x ∈ D. In general, since there are one Evader. Let us consider an example with five Pursuers
more than one optimal solution and the each team does not and three Evaders where the speeds and initial positions of
know what strategy the opponent will implement, then two the five Pursuers are vP = {1.3, 1.18, 1.2, 1.05, 1.1} and
cases may occur: both teams choose the same solution or P = {(3, 9), (1, 5), (0, 0), (0.5, −3), (1.5, −7)}, respectively.
each team chooses a different solution. In the former case The initial positions and speeds of the three Evaders are
the state of the game stays on the dispersal surface and vE = {0.98, 0.85, 0.76} and E = {(8, 5), (10, 1), (7, −3)},
more than one solution is optimal. However, when teams respectively.
choose different solutions then the state of the game leaves In this example we consider assignments of teams 2−2−1.
the dispersal surface and transitions into a regular region of We do not consider cases where three Pursuers may be
the state space where only one optimal solution exists, hence, assigned to a single Evader. Under these conditions we obtain
no dilemma exists any longer. Typically, Pursuers pay an the combination of possible assignments shown in Table I,
infinitesimally small price for guessing incorrectly. where each numerical entry denotes the Value of the Game
In this example each team makes a choice at the beginning for the 2P1EDG combination Pi Pj El and the superscript
of the game and it happens that they selected opposite denotes which case is active under such combination, that
solutions, the Pursuers initially head south whereas the is, if the Evader will be captured only by Pi , only by
Evader heads North. Because the players did not choose Pj , or simultaneously by both Pursuers. A given Pursuer
the same strategy, the state of the game leaves the dispersal can be assigned to capture only one Evader which imposes
surface and it transitions into the regular subspace R. After constraints on the selection of assignments; if for instance,
measuring the Evader’s new position, the Pursuers recompute P1 is assigned to E1 , either alone or teaming up with P5 ,
the solution of the game; now it holds that x ∈ R− s ⊂ R.
then it cannot be assigned to E2 (or E3 ) and the best time
Fig. 5 shows the resulting trajectories. This problem illus- to capture E2 would be 28.46. Similarly, if P1 is assigned
trates a typical scenario in pursuit-evasion differential games either to E2 or E3 , then it cannot be used to capture E1 and
where the pursuers generally see a small cost increment by the best time to capture E1 would be 35.00.
incorrectly choosing between two or more strategies. This is The best assignment strategy is {P1 E1 }, {P2 P3 E2 },
inevitable in practice since the Evader will not announce its {P4 P5 E3 } corresponding to the capture times 20.01, 28.46,
strategy and the Pursuers will pay a price for the state of and 19.97, respectively. All Evaders have been captured at
the game to leave the dispersal surface and enter a regular 28.46 time units and no other combination can reduce this
1059
TABLE I
games of degree, when the target escapes, the range from
P OSSIBLE COMBINATIONS OF ASSIGNMENTS Pi , Pj , El FOR
the attacker to the target at the instant when the attacker
i, j = 1, ..., 5 AND l = 1, 2, 3. T HE SUPERSCRIPT DENOTES THE ACTIVE
is intercepted by the defender has been used. When the
CASE
target is captured by the Attacker, the distance between the
Pi , Pj - El 1 2 3 defender and attacker at the instant of capture of the Target
1,2 20.01(1) 23.62(1) 23.36(s) by the Attacker has been used as a performance metric.
1,3 20.01(1) 23.33(s) 17.31(3) These ranging metrics are popular because they quantify the
1,4 20.01(1) 23.62(1) 20.18(s) outcome of the engagement and are readily computed. Other
1,5 20.00(s) 22.92(s) 16.34(s)
metrics, such as time to capture, are also of interest.
2,3 35.00(2) 28.46(s) 17.31(3)
2,4 35.00(2) 29.84(2) 21.41(s) The two-players one target game of [93] is an early version
2,5 35.00(2) 29.68(s) 17.66(s) of target defense. In the paper, a two-player differential game
3,4 42.88(3) 28.71(3) 17.31(3) is played wherein one of the players wants the state of
3,5 42.88(3) 28.71(3) 16.75(s) the system to reach a target, while the other player wants
4,5 113.73(5) 46.69(5) 19.97(s) the state of the system to avoid this target. Introduced by
Boyell, the defense of a ship from an incoming torpedo using
a counter-weapon was described, [94], [95]. The authors
value. of [96], [97] proposed the defense of an active target by
launching a defensive missile. Rubinsky and Gutman pre-
V. ACTIVE TARGET D EFENSE D IFFERENTIAL G AMES sented an analysis of the end-game ATDDG scenario based
(ATDDG) on the Attacker-Target miss distance for a non-cooperative
A. Overview Target-Defender. The authors develop linearization-based
Target Defense Differential Games (TDDG) are recently Attacker maneuvers in order to evade the Defender and
introduced pursuit-evasion differential games with three continue pursuing the Target using the LQ paradigm, [98],
agents. A target (T ) is pursued by an agent called the attacker [99]. Defense of non-maneuverable aircraft was addressed in
(A). A third player, the Defender (D) pursues A in an effort [100], [101]. In [102], the limiting values of the three partic-
to defend T . The outcome of the three-player game is simple: ipants optimal strategies are studied as the quadratic weight
If D intercepts A before A captures T , then the Target is on the defending missiles acceleration command tends to
successfully defended; however, if A captures T before D zero. They show that in the limit, the intercepting missiles
can intercept A, then the defense is unsuccessful and A is and the targets optimal strategies are identical in form to
the winner. When the target is able to maneuver in the three- that obtained in the game without the defending missile.
player game, then T and D cooperate while playing against Ratnoo and Shima proposed a game theoretic analysis of
A and this scenario is known as the Active Target Defense the ATDDG problem using conventional guidance laws for
Differential Game (ATDDG). Fig. 6 describes the geometry both attacker and defender, [103], [104]. The cooperative
used to describe ATDDGs [91], [92]. strategies proposed by [105] allowed for a maneuverability
disadvantage of the Defender with respect to the Attacker and
Vt the results show that the optimal target maneuver is either
constant or arbitrary. The authors of [106] implemented a
φt Multiple Model Adaptive Estimator (MMAE) to identify
γt the guidance law and parameters of incoming missiles and
optimize defender strategies to minimize the control effort.
In [107] the three-agent game using zero-effort-miss (ZEM)
T
Va is investigated.
σa Rat The ATDDG has been addressed in great detail in [51],
Vd [52], [91], [92], [108]–[110]. The ATDDG was analyzed
φa γa λ in [51], [52] using simple motion kinematics. In order to
at
σd find the optimal strategy for the Defender to intercept the
γd R A Attacker, the geometric concept of the Apollonius circle is
λdada used. In this analysis, the authors are able to look at the
D critical Target/Attacker speed ratio to ensure target survival.
The authors of [108] considered the use of two defenders
Fig. 6. Defender-Attacker-Target Geometry describing the Active Target to better engage the attacker. The work in [110] investigated
Defense Differential Games where the Defender pursues the Attacker who the case where the Defender had a non-zero capture radius.
pursues the actively maneuvering Target, [91], [92].
While in previous work, information between all players was
shared, the work in [91], [109] was concerned with optimal
There exist a number of popular performance metrics evasion of the target assuming the defender’s and attacker’s
which are used when posing the ATDDG. In games of kind, control laws were proportional navigation and pure pursuit,
the interest lies with the outcome of the defense: does the respectively. Information was restricted to the Attacker and
Target succeed in evading the attacker or is captured? In Defender, and heading rate constraints were imposed on the
1060
Target. Finally, in [92], an Extended Kalman Filter was used In this paper the focus is on the Game of Degree when
to investigate the same engagement with sensor models. (43) applies. In such a case the cost functional is given by
1
B. Problem Formulation Jc (uA (t), uB (t), x̃0 ) := [(xAf − xTf )2 + (yAf − yTf )2 ]
2
The scenario of active target defense considers three play- (45)
ers: a Target (T ), an Attacker (A), and a Defender (D) which
have “simple motion” à la Isaacs. The game is played in the subject to the terminal condition (43).
Euclidean plane where the controls of T , A, and D are their The next two sections summarize the approach described
respective instantaneous headings φ, χ, and ψ and their states in [111] where a reduced state space is used to derive
are specified by their Cartesian coordinates xT = (xT , yT ), the optimal strategies of the escape game. Without loss of
xA = (xA , yA ), and xD = (xD , yD ). The players T , A generalization, it is assumed that xD = −xA , yA = 0,
and D have constant speeds denoted by VT , VA , and VD , yD = 0, and yT ≥ 0; the scenario is as shown in Fig.
respectively. The complete state of the TAD differential game 7. The selected reduced state space is a suitable choice of
is specified by x := (xT , yT , xA , yA , xD , yD ) ∈ R6 . The framework for this particular problem. Other choices such
game set is the entire space R6 . The initial time is denoted as a framework based on relative distances is common in
by t0 and the corresponding initial state of the system is other games. In general, the main purpose is to simplify the
x0 := (xT0 , yT0 , xA0 , yA0 , xD0 , yD0 ) = x(t0 ). The Target analysis by reducing the dimension of the system.
aircraft is slower than the Attacker missile, and thus the
speed ratio α = VT /VA < 1. We assume that the Attacker C. Game of Kind
and Defender have similar capabilities, so VA = VD . Without
The concept of Game of Kind is fundamental in differ-
loss of generality, the players’ speeds are normalized so that
ential games and, given the initial conditions and problem
VA = VD = 1 and VT = α.
parameters, its solution provides the answer to the question
The control input of the T /D team is the pair of instan- of which team wins the game.
taneous headings uT,D = {φ, ψ}. The Attacker’s control is
In the ATDDG and employing the reduced state space
his instantaneous heading angle, uA = {χ}. The dynamics
x = (xA , xT , yT ) we have that when xT < 0 the Target can
ẋ = f(x, uA , uT,D ) are specified by the system of ordinary
escape. When xT > 0 the state space is partitioned into two
differential equations
regions: Re and Rc . The region Re is the set of states such
ẋA = cos χ, xA (0) = xA0 that if the Target’s initial position (xT , yT ) and the coordinate
ẏA = sin χ, yA (0) = yA0 xA are such that (xA , xT , yT ) ∈ Re , then, the Target is
ẋD = cos ψ, xD (0) = xD0 guaranteed to escape the Attacker, provided the Target and
(41) the Defender team implement their optimal strategies φ∗ and
ẏD = sin ψ, yD (0) = yD0
ẋT = α cos φ, xT (0) = xT0 ψ ∗ . The Game of Degree, that is, the ATDDG, is played in
ẏT = α sin φ, yT (0) = yT0 Re . The region Rc specifies the states where under optimal
Attacker play, notwithstanding the presence of the Defender,
where the admissible controls are given by χ, φ, ψ ∈ [−π, π]. the Target cannot escape.
Both, the state and the controls, are unconstrained. The For a specified speed ratio 0 < α < 1, the equation
terminal condition is point capture, that is, the separation p p
between Target and Attacker becomes zero allowing the (xA + xT )2 + yT2 − (xA − xT )2 + yT2
α= (46)
Attacker to capture the Target and win the game. An alter- 2xA
native termination condition is when the separation between
Attacker and Defender is equal to zero; this case represents renders the boundary in the state space (xA , xT , yT ),
interception of the Attacker by the Defender and the T /D xT , xA > 0, where the active target defense game of degree
team wins. Hence, the termination set for the complete TAD is played out, and as such this boundary constitutes the
differential game is solution to the Game of Kind.
[ Proposition 2: [111]. For a given speed ratio 0 < α < 1
S := Se Sc (42) the region of win of the Attacker is
where Rc = {(xA , xT , yT )|xA > 0, xT > 0, yT ≥ 0,

yT2 x2
x2A + − T2 < 0}.
p
Se := x | (xA − xD )2 + (yA − yD )2 = 0 (43) 2
1−α α
represents interception of the Attacker by the Defender (and The manifold B in R3 which is the boundary of the set Re
the Target escapes) and for which the Target is guaranteed to escape is
p
Sc := x | (xA − xT )2 + (yA − yT )2 = 0 (44) B = {(xA , xT , yT )|xA > 0, xT > 0, yT ≥ 0,
represents the opposite outcome where the Attacker wins by yT2 x2
x2A + 2
− T2 = 0}.
capturing the Target. 1−α α
1061
and the region of win of the T & D team where the ATDDG
is played is
Re = {(xA , xT , yT )|xA ≥ 0, xT ≥ 0, yT ≥ 0,
yT2 x2T
x2A + − > 0} ∪ {(xA , xT , yT )|xA ≥ 0, xT ≤ 0}.
1−α2 α2
Thus, for a fixed xA > 0, the xA -cross section of B which
divides the reduced state space into the two regions Re and
Rc is the right branch of the hyperbola (where, xT > 0)
x2T yT2
2 − = 1. (47) Fig. 7. Optimal Headings of the Target, the Attacker, and the Defender
α 2 xA (1 − α2 )x2A
D. Game of Degree
In the following Theorem, the “two-sided” PMP is used in
order to synthesize the players’ optimal strategies. This prob- Additionally, the co-state dynamics are λ̇xA = λ̇yA = λ̇xD =
lem illustrates how the necessary conditions for optimality λ̇yD = λ̇xT = λ̇yT = 0. Hence, all co-states are constant
or PMP can be used to obtain the regular solution of this and we have that χ∗ ≡ constant, ψ ∗ ≡ constant, and φ∗ ≡
differential game where T and D cooperate to maximize the constant. In other words, the regular optimal trajectories are
terminal range while A aims at minimizing it. straight lines.
Theorem 3: Consider the ATDDG (41)-(45). The problem Concerning the solution of the attendant Two-Point
parameter is the speed ratio 0 ≤ α < 1 and the reduced Boundary Value Problem (TPBVP) on 0 ≤ t ≤ tf in R12 ,
state space, is (xA , xT , yT ) where, without loss of generality, we have 6 initial states specified by (41) and we need 6 more
xA > 0 and yT ≥ 0. In the part of the state space where conditions for the terminal time tf . In this respect, define the
the Target can escape, the optimal headings of the Attacker, augmented Mayer terminal value function Φa : R6 → R1
the Target, and the Defender are given by the state feedback Φa (xf ) := 12 [(xA (tf ) − xT (tf ))2 + (yA (tf ) − yT (tf ))2 ]
control laws +ν1 (xA (tf ) − xD (tf )) + ν2 (yA (tf ) − yD (tf ))
cos φ∗ = ± √ 2 xT 2
xT +(yT −y) where ν1 and ν2 are Lagrange multipliers. The PMP or Dy-
yT −y
sin φ∗ = ± √ for xT 6= 0. namic Programming yields the transversality/terminal condi-
x2T +(yT −y)2
(48) ∂
tions λ(tf ) = − ∂x
cos χ∗ = − √ 2 2 , sin χ∗ = √ 2y 2 .
x A Φa (xf ), that is,
xA +y xA +y
cos ψ ∗ = √ x2A 2 , sin ψ ∗ = √ 2y 2 . λxA = xT (tf ) − xA (tf ) − ν1 (52)
xA +y xA +y
λyA = yT (tf ) − yA (tf ) − ν2 (53)
where y is a real solution of the quartic equation
2 4
λxD = ν1 (54)
(1−α )y − 2(1−α2 )yTy 3 +
(49) λyD = ν2 (55)
(1−α )yT +x2A −α2 x2T y 2 −2x2A yT y+x2A yT2 = 0
2 2
λxT = xA (tf ) − xT (tf ) (56)
which is parameterized by the speed ratio 0 ≤ α < 1. The
quartic equation has two real solutions y1 and y2 and y1 ≤ λyT = yA (tf ) − yT (tf ) (57)
yT ≤ y2 . In eqs. (48) when xT ≤ 0 the solution y1 is At this point, we have that equations (52)-(57) together with
selected and when xT > 0 the solution y2 is used. Also, the terminal equations
when xT < 0, the sign in the Target heading in eq. (48) is
positive and, when xT > 0, the sign in the Target heading is xA = xD , yA = yD . (58)
negative. Finally, when xT = 0, the Target’s optimal heading,
φ∗ , is given by yield 8 conditions. Since we need only 6 conditions we
eliminate the introduced Lagrange multipliers ν1 and ν2 from
φ∗ = ϕ∗ + π/2 (50) equations (52)-(57) and we obtain
where λxA + λxD = xT (tf ) − xA (tf ) (59)
p
∗ x2A + (1 − α2 )yT2 λyA + λyD = yT (tf ) − yA (tf ) (60)
tan ϕ = . (51)
αyT
Proof. The optimal control inputs in terms of the co- Finally, the time tf is specified by the PMP requirement that
state variables are obtained from Isaacs’ Main Equation 1 the Hamiltonian H(x(t), λ(t), χ, ψ, φ)|tf ≡ 0.
minφ,ψ maxχ H = 0 and they are characterized by Because the optimal trajectories of A, D, and T are
λ A λ straight lines and VD = VA we have that
cos χ∗ = √λ2 x+λ2
, sin χ∗ = √λ2 yA
+λ2
xA yA xA yA
λxD λyD xA (tf ) = 0 (61)
cos ψ ∗ = − √λ2 2
, sin ψ ∗ = − √λ2 2
xD +λyD xD +λyD
λ T λyT
xD (tf ) = 0 (62)
cos φ∗ = − √λ2 x+λ 2
, sin φ∗ = − √λ2 +λ2 . yA (tf ) = yD (tf ) (63)
x yT T x T y T
1062
Let y := yA (tf ) = yD (tf ). Also, let xA = xA (t0 ), xT = The A and D optimal headings are
xT (t0 ), and yT = yT (t0 ) be the instantaneous positions at
some time t0 < tf . Hence, from equations (41) we obtain xA y
cos χ∗ = − p 2 , sin χ∗ = p 2 . (80)
the following xA + y 2 xA + y 2
xA y
xT (tf ) = xT + α · (tf − t0 ) cos φ, (64) cos ψ ∗ = p 2 , sin ψ ∗ = p 2 . (81)
xA + y 2 xA + y 2
yT (tf ) = yT + α · (tf − t0 ) sin φ, (65)
0 = xA + (tf − t0 ) cos χ, (66) Let us now use eqs. (10) and (81) to write the following
relationships
y = (tf − t0 ) sin χ, (67)
0 = −xA + (tf − t0 ) cos ψ, (68) − √λ 2
λxD
=√ xA
, − √λ2
λyD
=√ y
.
2 2
xD +λyD x2A +y 2 xD +λyD x2A +y 2
y = (tf − t0 ) sin ψ, (69)
(82)
In addition, equations (56)-(60) can be written as follows
Similarly, from eqs. (9) and (80) we obtain
λxT = −xT (tf ) (70)
λxA xA λyA y
λyT = y − yT (tf ) (71) √ = −√ , √ =√ .
λ2x +λ2y x2A +y 2 λ2x +λ2y x2A +y 2
A A A A
λxA + λxD = xT (tf ) (72) (83)
λyA + λyD = yT (tf ) − y (73)
We have four equations (59), (60), (82), and (83) in the four
Consider eq. (11) and eqs. (70) and (71). We calculate the unknowns λxA , λyA , λxD , and λyD . The solution is
following
1 xA
cos φ∗ = √
xT (tf ) λxA = [xT (tf ) − xA (tf ) − yT (tf ) − yA (tf ) ]
x2T (tf )+(y−yT (tf ))2 2 y
∗ yT (tf )−y (74) 1 y
sin φ = √ .

x2T (tf )+(y−yT (tf ))2 λyA = [yT (tf ) − yA (tf ) − xT (tf ) − xA (tf ) ]
2 xA
Hence, in light of eqs. (64) and (65), we have that the optimal 1 xA
λxD = [xT (tf ) − xA (tf ) + yT (tf ) − yA (tf ) ]
heading angle of T is φ∗ = ξ where the angle ξ is shown 2 y
in Fig. 7. The three points, T , Tf , and y are collinear and 1 y
λyD = [yT (tf ) − yA (tf ) + xT (tf ) − xA (tf ) ]
the optimal geometry is as shown in Fig. 7 where Tf = 2 xA
)). From the 4ADy in Fig. 7 we conclude
(xT (tf ), yT (tfp
that tf − t0 = x2A + y 2 . Without loss of generality, assume By substituting yA (tf ) = y and xA (tf ) = 0 we obtain
that t0 = 0, then
1 xA
q λxA = [xT (tf ) − yT (tf ) − y ] (84)
tf = x2A + y 2 . (75) 2 y
1 y
Thus, using Isaacs’ method, we are now able to reduce the λyA = [yT (tf ) − y − xT (tf )] (85)
2 xA
solution of the zero-sum differential game of degree to the 1 xA
optimization of a cost/payoff function of one variable. From λxD = [xT (tf ) + yT (tf ) − y ] (86)
2 y
(64)-(69), (74), and (75) we can write the cost (the terminal 1 y
distance between A and T ) as J(y; xA , xT , yT ) = T Tf ±T I, λyD = [yT (tf ) − y + xT (tf )] (87)
2 xA
where T Tf = αAI = αtf . Depending on which side of the
orthogonal bisector of the segment AD the Target is located which together with eqs. (70) and (71) specify the co-states
we have the two cases: in terms of the states at time tf . Now, eqs. (64), (65), (75),
For case a) where xT < 0 solve miny J1 where and (78) yield
√ 2 2 i
q q
J1 = α x2A + y 2 + (yT − y)2 + x2T . (76)
 h
x +y
 xT (tf ) = 1 + α √ 2 A
 xT
xT +(yT −y)2
For case b) where xT > 0 solve maxy J2 where a) h √ 2 2 i (88)
 yT (tf ) = 1 + α √ 2 xA +y
 (yT −y)+y
q q 2 xT +(yT −y)
J2 = α x2A + y 2 − (y − yT )2 + x2T . (77)
Similarly, eqs. (64), (65), (75), and (79) yield
Also, from eq. (74) we have that in case a)
 h √ 2 2 i
xT yT −y x +y
cos φ∗ = √ , sin φ∗ = √ (78)  xT (tf ) = 1 − α √ 2 A
 xT
x2T +(yT −y)2 x2T +(yT −y)2 xT +(y−yT )2
b) h √ 2 2
i (89)
and in case b)  yT (tf ) = 1 − α √ 2 xA +y
 (yT −y)+y
2 xT +(y−yT )
xT y−yT
cos φ∗ = − √ , sin φ∗ = √ (79)
x2T +(y−yT )2 x2T +(y−yT )2 Inserting eqs. (88) and (89) into eqs. (70), (71), and (84)-(87)
1063
allows us to express the co-states in terms of y (or tf ): games such as the “Homicidal Chauffeur” Differential Game
h √ 2 2 i and “Two-Cars” Differential Game were briefly discussed.
x +y
√
λxT = − 1 ± α 2 A xT Games involving N-pursuers-1-evader, 1-pursuer-M-evaders,
xT +(yT −y)2
h √ 2 2 i and N-pursuer-M-evaders were addressed. In games with
x +y
λyT = − 1 ± α √ 2 A (yT − y) multiple players, cooperation between members of the same
xT +(yT −y)2
√ team was emphasized. Not only cooperation improves team
x2 +y 2
h i
λxA = 12 1 ± α √ 2 A (xA + xT − xA yyT ) performance but it was shown that cooperative behaviors are
xT +(yT −y)2
√ 2 2 i (90)
h
x +y xT necessary to synthesize saddle-point equilibrium strategies.
λyA = 21 1 ± α √ 2 A [y T − (1 + )y]
xT +(yT −y)2
√ 2 2 i
xA Two pursuit-evasion problems involving multiple players
were presented and they were formulated as differential
h
x +y
λxD = 21 1 ± α √ 2 A (xT − xA + xA yyT )
xT +(yT −y)2 games. The solutions provided in this paper highlighted the
h √ 2 2 i
x +y cooperative aspect and the methods available by applying
λyD = 21 1 ± α √ 2 A 2
[yT − (1 − xxA
T
)y]
xT +(yT −y) differential game theory.
We now used the condition on the Hamiltonian at the
R EFERENCES
terminal time in conjunction with eqs. (78)-(81) for the
optimal controls and eq. (90) for the co-states. Doing so we [1] J. Sprinkle, J. M. Eklund, H. J. Kim, and S. Sastry, “Encoding aerial
pursuit/evasion games with fixed wing aircraft into a nonlinear model
obtain the following predictive tracking controller,” in 43rd IEEE Conference on Decision
− 21 (xA + xT − xA yyT ) √ xA and Control, 2004, pp. 2609–2614.
x2A +y 2 [2] M. G. Earl and R. DAndrea, “A decomposition approach to multi-
+ 21 [yT − (1 + xxA T
)y] √ 2y 2 vehicle cooperative control,” Robotics and Autonomous Systems,
xA +y vol. 55, no. 4, pp. 276–291, 2007.
+ 21 (xT − xA + xA yyT ) √ x2A 2 [3] R. Isaacs, Differential Games. John Wiley and Sons, 1965.
xA +y [4] ——, “Games of Pursuit,” RAND Corporation, Santa Monica, CA,
+ 21 [yT − (1 − xxA T
)y] √ 2y 2 Tech. Rep., 1951.
xA +y [5] ——, “Differential Games I: Introduction,” RAND Corporation,
+√ 2 α 2
[x2T + (yT − y)2 ] =0 Santa Monica, CA, Tech. Rep., 1954. [Online]. Available:
xT +(yT −y) https://www.rand.org/pubs/research memoranda/RM1391.html
⇒ −x2A + x2A yyT + yT y − y 2 [6] ——, “Differential Games II: The Definition and Formulation,”
√ 2 2 RAND Corporation, Santa Monica, CA, Tech. Rep., 1954. [Online].
xA +y
+α √ [x2 + (yT − y)2 ] = 0 Available: https://www.rand.org/pubs/research memoranda/RM1399.
x2T +(yT −y)2 T html
⇒ (x2A + y 2 − x2A yyT − yT y)2 [7] ——, “Differential Games III: The Basic Principles of the Solution
= α2 (x2A + y 2 )[x2T + (yT − y)2 ] Process,” RAND Corporation, Santa Monica, CA, Tech. Rep., 1954.
[Online]. Available: https://www.rand.org/pubs/research memoranda/
⇒ (1 − yyT )2 (x2A + y 2 ) = α2 [x2T + (yT − y)2 ] RM1411.html
[8] ——, “Differential Games IV: Mainly Examples,” RAND
Finally, grouping terms in y we obtain (49), that is, the Corporation, Santa Monica, CA, Tech. Rep., 1955. [Online].
optimal aimpoint on the orthogonal bisector of AD specified Available: https://www.rand.org/pubs/research memoranda/RM1486.
by y ∗ is a real solution of the quartic equation (49). html
[9] M. H. Breitner, “The genesis of differential games in light of Isaacs’
For the derivation of the Target strategy when xT = 0, contributions,” Journal of Optimization Theory and Applications, vol.
please refer to [111]. 124, no. 3, pp. 523–559, 2005.
The verification of the saddle-point strategies of the [10] R. Bellman, Dynamic Programming. Princeton, NJ: Princeton
University Press, 1957.
ATTDG in the escape region was recently provided in [11] A. Lew, “Richard Bellman’s Contributions to Computer Science,”
[112]. Preliminary results and a candidate solution for the Journal of Mathematical Analysis and Applications, vol. 119, no.
ATDDG in the capture region have been presented in [113]; 1-2, pp. 90–96, 1986.
[12] P. Bernhard, “Isaacs , Breakwell , and their sons,” no. 1927, Chateau
verification of these strategies is a topic of current research. Vaalsbroek, Maastricht, NL, 1998, pp. 1–16.
[13] Y. C. Ho, A. E. Bryson, and S. Baron, “Differential games and
VI. C ONCLUDING R EMARKS optimal pursuit-evasion strategies,” IEEE Transactions on Automatic
Pursuit-evasion differential games, initially introduced by Control, vol. 10, no. 4, pp. 385–389, 1965.
[14] S. Baron, “Differential Games and Manual Control,” National
Rufus Isaacs, have been studied in great detail over the Aeronautics and Space Administration, Washington, DC, Tech.
past half-century. Since its inception, many ideas and tech- Rep., 1966. [Online]. Available: https://ntrs.nasa.gov/search.jsp?R=
niques have been developed to gain a better understanding 19660028126
[15] N. Satimov, “Problems of Pursuit and Evasion in Differential Games,”
of pursuit-evasion differential games. In his seminal work, Ph.D. dissertation, Tashkent State University, 1981.
Isaacs motivated and described the idea of posing problems [16] I. M. Gelfand and S. V. Fomin, Calculus of Variations. New York,
in a game-theoretic framework; the dynamics are mathemat- NY: Dover Publications, Inc, 2000.
[17] C. Marchal, “Analytical Study of a Case of the Homicidal Chauffeur
ically described by differential equations so he called this Game Problem,” in Optimization Techniques IFIP Technical Confer-
approach “Differential Games”. Using differential games, ence. Springer, Berlin, 1975, pp. 472–481.
problems of pursuit-evasion have been properly described [18] V. S. Patsko and V. L. Turova, “Homicidal Chauffeur Game: History
and Modern Studies,” in Advances in Dynamic Games. Annals
and solved. The contributions of Rufus Isaacs, Richard Bell- of the International Society of Dynamic Games, M. Breton and
man, John Breakwell and his students, and Lev S. Pontryagin K. Szajowski, Eds. Ekaterinburg, Russia: Birkhäuser Boston, 2009,
were highlighted in this paper. A description of different pp. 3–43.
[19] M. Falcone, “Numerical Methods for Differential Games based on
categories of pursuit-evasion differential games and signif- Partial Differential Equations,” International Game Theory Review,
icant contributions were provided with examples. Classic vol. 8, no. 2, pp. 231–272, 2006.
1064
[20] Anthony W. Merz, “The Homicidal Chauffeur - A Differential Symposium on Adaptive Processes, vol. 17. San Diego, CA: IEEE,
Game,” Guidance and Control Laboratory, Wright-Patterson AFB, 1978, pp. 960–965.
OH, Tech. Rep., 1971. [Online]. Available: http://www.dtic.mil/dtic/ [44] J. Shinar, “Solution Techniques for Realistic Pursuit Evasion Games,”
tr/fulltext/u2/885270.pdf Technion - Isreal Institute of Technology, Haifa, Israel, Tech. Rep.,
[21] J. V. Breakwell and A. W. Merz, “Toward a Complete Solution of the 1980.
Homicidal Chauffeur Game,” in Proceedings of the first international [45] M. Pachter and T. Milch, “The ’Homicidal Chauffeur’ model in naval
conference on the theory and applications of differential games, pursuit-evasion,” in Guidance, Navigation and Control Conference.
Amherst, MA, 1969, pp. III 1 – III 5. AIAA, 1987.
[22] L. I. Meier, “A New Technique for Solving Pursuit-Evasion Differ- [46] N. Greenwood, “A differential game in three dimensions: The aerial
ential Games,” IEEE Transactions on Automatic Control, vol. AC-14, dogfight scenario,” Dynamics and Control, vol. 2, no. 2, pp. 161–200,
no. 4, pp. 352–359, 1969. 1992.
[23] W. M. Getz and M. Pachter, “Two-Target Pursuit-Evasion Differential [47] F. Imado and T. Kuroda, “A Method to Solve Missile-Aircraft Pursuit
Games in the Plane,” Journal of Optimization Theory and Applica- -Evasion Differential Games,” in 16th Triennial World Congress.
tions, vol. 34, no. 3, pp. 383–403, 1981. Prague, Czech Republic: IFAC, 2005, pp. 176–181.
[24] ——, “Capturability in a two-target game of two cars,” Journal of [48] J. Shinar, V. Y. Glizer, and V. Turetsky, “A Pursuit-Evasion Game
Guidance and Control, vol. 4, no. 1, pp. 15–21, 1981. with Hybrid Pursuer Dynamics,” in Proceedings of the European
[25] I. Greenfeld, “A differential game of surveillance evasion of two Control Conference, no. July 2-5, Kos, Greece, 2007, pp. 1306–1313.
identical cars,” Journal of Optimization Theory and Applications, [49] ——, “A Pursuit-Evasion Game with Hybrid Evader Dynamics,” in
vol. 52, no. 1, pp. 53–79, 1987. European Journal of Control, no. August 23-26. EUCA, 2009, pp.
[26] J. Lewin and J. V. Breakwell, “The Surveillance-Evasion Game of 121–126.
Degree,” Journal of Optimization Theory and Applications, vol. 16, [50] A. W. Merz, “To Pursue or to Evade - That is the Question,”
no. 3-4, pp. 339–353, 1975. Guidance, vol. 8, no. 2, pp. 161–166, 1984.
[27] R. Bera, V. R. Makkapati, and M. Kothari, “A Comprehensive [51] M. Pachter, E. Garcia, and D. W. Casbeer, “Active target defense dif-
Differential Game Theoretic Solution to a Game of Two Cars,” ferential game,” in Fifty-second Annual Allerton Conference, Allerton
Journal of Optimization Theory and Applications, vol. 174, no. 3, House, UIUC, Illinois, USA, 2014, pp. 46–53.
pp. 818–836, 2017. [52] E. Garcia, D. W. Casbeer, and M. Pachter, “Active Target defense
[28] J. F. Fisac and S. S. Sastry, “The pursuit-evasion-defense differential differential game with a fast Defender,” in American Control Con-
game in dynamic constrained environments,” in Proceedings of the ference, Chicago, IL, 2015, pp. 3752–3757.
IEEE Conference on Decision and Control, vol. 54, no. Dec 15-18, [53] G. Leitmann, “A simple differential game,” Journal of Optimization
2015, pp. 4549–4556. Theory and Applications, vol. 2, no. 4, pp. 220–225, 1968.
[29] D. W. Oyler, “Contributions to Pursuit Evasion Thesis.pdf,” Ph.D.
[54] A. J. Calise and X.-M. Yu, “An Analysis of a Four State Model for
dissertation, University of Michigan, 2016.
Pursuit-Evasion Games,” in Conference on Decision and Control. Ft.
[30] Z. E. Fuchs and P. P. Khargonekar, “Generalized engage or retreat
Lauderdale, FL: IEEE, 1985, pp. 1119–1121.
differential game with escort regions,” IEEE Transactions on Auto-
[55] M. Quincampoix, “Differential Games,” in Computational Com-
matic Control, vol. 62, no. 2, pp. 668–681, 2017.
plexity: Theory, Techniques, and Applications, R. A. Meyers, Ed.
[31] S. Sundaram, K. Kalyanam, and D. W. Casbeer, “Pursuit on a
Springer New York, 2012, vol. 69, pp. 854–861.
graph under partial information from sensors,” in Proceedings of the
American Control Conference, 2017, pp. 4279–4284. [56] P. Hagedorn and J. V. Breakwell, “A differential game with two
pursuers and one evader,” Journal of Optimization Theory and
[32] K. Kalyanam, D. W. Casbeer, and M. Pachter, “Pursuit on a graph
Applications, vol. 18, no. 1, pp. 15–29, 1976.
using partial information,” Proceedings of the American Control
Conference, vol. 2015-July, pp. 4269–4275, 2015. [57] A. G. Pashkov and S. D. Terekhov, “A differential game of approach
[33] E. Roxin and C. P. Tsokos, “On the Definition of a Stochasic with two pursuers and one evader,” Journal of Optimization Theory
Differential Game,” Mathematical Systems Theory, vol. 4, no. 1, pp. and Applications, vol. 55, no. 2, pp. 303–311, 1987.
60–64, 1969. [58] A. Y. Levchenkov and A. G. Pashkov, “Differential game of optimal
[34] F. L. Chernousko and A. A. Melikyan, “Some Differential Games approach of two inertial pursuers to a noninertial evader,” Journal of
with Incomplete Information,” in Optimization Techniques IFIP Tech- Optimization Theory and Applications, vol. 65, no. 3, pp. 501–518,
nical Conference, vol. 27. Springer, Berlin, 1974, pp. 445–450. 1990.
[35] Y. Yavin, “A Pursuit-Evasion Differential Game with Noisy Mea- [59] S. A. Ganebny, S. S. Kumkov, S. Le Ménec, and V. S. Patsko,
surements of the Evader’s Bearing from the Pursuer,” Journal of “Numerical Study of Two-on-One Pursuit-Evasion Game,” in Pro-
Optimization Th, vol. 51, no. 1, pp. 161–177, 1986. ceedings of the 18th World Congress, vol. 44, no. 1. Milano, Italy:
[36] C. Giovannangeli, M. Heymann, and E. Rivlin, “Pursuit-Evasion International Federation of Automatic Control, 2011, pp. 9326–9333.
Games in Presence of Obstacles in Unknown Environments : towards [60] E. Garcia, Z. Fuchs, D. Milutinovic, D. W. Casbeer, and M. Pachter,
an optimal pursuit strategy,” in Cutting Edge Robotics, V. Kordic, Ed., “A geometric approach for the cooperative two-pursuer one-evader
2010, no. 2006, pp. 47–81. differential game,” IFAC-PapersOnline, vol. 50, no. 1, pp. 15 209–
[37] G. Hexner, “A Differential Game of Incomplete Information,” Jour- 15 214, 2017.
nal of Optimization Theory and Applications, vol. 28, no. 2, pp. [61] S. Y. Hayoun and T. Shima, “A Two-on-One Linear PursuitEvasion
213–231, 1979. Game with Bounded Controls,” Journal of Optimization Theory and
[38] M. Pachter and Y. Yavin, “A Stochasic Homicidal Chauffeur Pursuit- Applications, vol. 174, no. 3, pp. 837–857, 2017.
Evasion Differential Game,” Journal of Optimization Theory and [62] H. Huang, W. Zhang, J. Ding, D. M. Stipanović, and C. J. Tomlin,
Applications, vol. 34, no. 3, pp. 405–424, 1981. “Guaranteed decentralized pursuit-evasion in the plane with multiple
[39] S. Battistini and T. Shima, “Differential Games Missile Guid- pursuers,” in Proceedings of the IEEE Conference on Decision and
ance with Bearings-Only Measurements,” IEEE Transactions on Control. Orlando, FL: IEEE, 2011, pp. 4835–4840.
Aerospace and Electronic Systems, vol. 50, no. 4, pp. 2906–2915, [63] E. Bakolas and P. Tsiotras, “Optimal Pursuit of Moving Targets Using
2013. Dynamic Voronoi Diagrams,” in IEEE Conference on Decision and
[40] O. Basimanebotlhe and X. Xue, “Stochastic Optimal Control to a Control. Atlanta, GA: IEEE, 2010, pp. 7431–7436.
Nonlinear Differential Game,” Advances in Difference Equations, vol. [64] P. Borowko and W. Rzymowski, “Avoidance of Many Pursuers in
266, no. 1, 2014. the Simple Motion Case,” Journal of Mathematical Analysis and
[41] W. Lin, Z. Qu, and M. A. Simaan, “Nash strategies for pursuit- Applications, vol. 111, no. 2, pp. 535–546, 1985.
evasion differential games involving limited observations,” IEEE [65] W. Chodun and L. D. Berkovitz, “Differential Games of Evasion with
Transactions on Aerospace and Electronic Systems, vol. 51, no. 2, Many Pursuers,” Journal of Mathematical Analysis and Applications,
pp. 1347–1356, 2015. vol. 142, no. 2, pp. 370–389, 1989.
[42] K. Kalyanam, D. W. Casbeer, and M. Pachter, “Pursuit of a Moving [66] G. I. Ibragimov, M. Salimi, and M. Amini, “Evasion from Many Pur-
Target with Bounded Speed on a Directed Acyclic Graph Under suers in Simple Motion Differential Game with Integral Constraints,”
Partial Information,” IMA Journal of Mathematical Control and European Journal of Operational Research, vol. 218, no. 2, pp. 505–
Information, pp. 1–16, 2016. 511, 2012.
[43] J. Shinar and S. Gutman, “Recent advances in optimal pursuit and [67] M. Kothari, J. G. Manathara, and I. Postlethwaite, “Cooperative
evasion,” in Conference on Decision and Control including the 17th Multiple Pursuers against a Single Evader,” Journal of Intelligent
1065
and Robotic Systems: Theory and Applications, vol. 86, no. 3-4, pp. [91] I. E. Weintraub, E. Garcia, D. W. Casbeer, and M. Pachter, “An
551–567, 2017. Optimal Aircraft Defense Strategy for the Active Target Defense
[68] M. D. Awheda and H. M. Schwartz, “Decentralized Learning in Scenario,” in AIAA Guidance, Navigation, and Control Conference.
Pursuit-Evasion Differential Games with Multi-Pursuer and Single- Grapevine, TX: American Institute of Aeronautics and Astronautics,
Superior Evader,” in Systems Conference (SysCon), 2016 Annual 2017, p. 10.
IEEE. Orlando, FL: IEEE, 2016, p. 8. [92] I. E. Weintraub, E. Garcia, and M. Pachter, “An Optimal-Stochastic
[69] A. A. Al-Talabi, “Multi-Player Pursuit-Evasion Differential Game Aircraft Defense Strategy for the Active Target Defense Scenario,” in
with Equal Speed,” in International Automatic Control Conference. AIAA Guidance, Navigation, and Control Conference. Kissimmee,
Pingtung, Taiwan: IEEE, 2017, pp. 1–6. FL: AIAA, 2018.
[70] A. Von Moll, D. Casbeer, E. Garcia, D. Milutinović, and M. Pachter, [93] P. Cardaliaguett, “A Differential Game with Two Players and One
“The Multi-pursuer Single-Evader Game,” Journal of Intelligent & Target,” SIAM Journal on Control and Optimization, vol. 34, no. 4,
Robotic Systems, vol. 96, no. 2, pp. 193–207, 2019. pp. 1441–1460, 1996.
[71] A. Von Moll, D. W. Casbeer, E. Garcia, and D. Milutinovic, “Pursuit- [94] R. L. Boyell, “Defending a Moving Target Against Missile or
evasion of an Evader by Multiple Pursuers,” in International Confer- Torpedo Attack,” IEEE Transactions on Aerospace and Electronic
ence on Unmanned Aircraft Systems, (ICUAS). Dallas, TX: IEEE, Systems, vol. AES-12, no. 4, pp. 522–526, 1976.
2018, pp. 133–142. [95] ——, “Counterweapon Aiming for Defense of a Moving Target,”
[72] M. Pachter, A. Von Moll, E. Garcia, D. W. Casbeer, and D. Miluti- IEEE Transactions on Aerospace and Electronic Systems, vol. AES-
novic, “Singular Trajectories in the Two Pursuer One Evader Dif- 16, no. 3, pp. 402–408, 1979.
ferential Game,” in International Conference on Unmanned Aircraft [96] T. Yamasaki and S. N. Balakrishnan, “Triangle Intercept Guidance for
Systems (ICUAS). Atlanta, GA: IEEE, 2019, pp. 1153–1160. Aerial Defense,” in Guidance, Navigation, and Control Conference.
[73] Z. E. Fuchs, P. P. Khargonekar, and J. Evers, “Cooperative de- Toronto, Ontario, Canada: AIAA, 2010, p. 22.
fense within a single-pursuer, two-evader pursuit evasion differential [97] T. Yamasaki, S. N. Balakrishnan, and H. Takano, “Modified Com-
game,” in IEEE Conference on Decision and Control. Atlanta, GA: mand to Line-of-Sight Intercept Guidance for Aircraft Defense,”
IEEE, 2010, pp. 3091–3097. Journal of Guidance, Control, and Dynamics, vol. 36, no. 3, pp.
[74] W. Scott and N. E. Leonard, “Pursuit, Herding and Evasion: A Three- 901–905, 2013.
Agent Model of Caribou Predation,” in IEEE American Control [98] S. Rubinsky and S. Gutman, “Three Body Guaranteed Pursuit and
Conference, no. 1. Washington, DC: IEEE, 2013, pp. 2978–2983. Evasion,” in AIAA Guidance, Navigation, and Control Conference.
[75] J. V. Breakwell and P. Hagedorn, “Point Capture of Two Evaders Minneapolis, MN: AIAA, 2012, p. 24.
in Succession,” Journal of Optimization Theory and Applications, [99] ——, “Three-Player Pursuit and Evasion Conflict,” Journal of Guid-
vol. 27, no. 1, pp. 89–97, 1979. ance, Control, and Dynamics, vol. 37, no. 1, pp. 98–110, 2014.
[76] M. Pachter and Y. Yavin, “One Pursuer and Two Evaders on the [100] R. H. Venkatesan and N. K. Sinha, “A New Guidance Law for the
Line: A Stochasic Pursuit-Evasion Diffferential Game,” Journal of Defense Missile of Nonmaneuverable Aircraft,” IEEE Transactions
Optimization Theory and Applications, vol. 39, no. 4, pp. 513–539, on Control Systems Technology, vol. 23, no. 6, pp. 2424–2431, 2015.
1983. [101] I. E. Weintraub, E. Garcia, and M. Pachter, “A Kinematic Rejoin
[77] T. G. Abramyants, E. P. Maslov, and V. P. Yakhno, “Evasion from Method for Active Defense of Non-Maneuverable Aircraft,” Proceed-
Detection in Three-Dimensional Space,” Journal of Computer and ings of the American Control Conference, pp. 6533–6538, 2018.
Systems Sciences International, vol. 46, no. 5, pp. 675–680, 2007. [102] I. Rusnak, H. Weiss, and G. Hexner, “Guidance Laws in TargetMis-
[78] S.-Y. Liu, Z. Zhou, C. Tomlin, and K. Hedrick, “Evasion as a team sileDefender Scenario with an Aggressive Defender,” in 18th World
against a faster pursuer,” in American Control Conference, 2013, pp. Congress. Milano, Italy: International Federation of Automatic
5368–5373. Control, 2011, pp. 9349–9354.
[79] I. A. Alias, R. Noorsuria, R. Ramli, G. Ibragimov, and A. Narzullaev, [103] A. Ratnoo and T. Shima, “Line-of-Sight Interceptor Guidance
“Simple Motion Pursuit Differential Game of Many Pursuers and One for Defending an Aircraft,” Journal of Guidance, Control, and
Evader on Convex Compact Set,” International Journal of Pure and Dynamics, vol. 34, no. 2, pp. 522–532, 2011. [Online]. Available:
Applied Mathematics, vol. 102, no. 4, pp. 733–745, 2015. https://arc-aiaa-org.wrs.idm.oclc.org/doi/pdf/10.2514/1.50572
[80] D. Wang and Z. Peng, “Pursuit-evasion games of multi-players with [104] ——, “Guidance Strategies Against Defended Aerial Targets,” Jour-
a single faster player,” in Chinese Control Conference, CCC, vol. nal of Guidance, Control, and Dynamics, vol. 35, no. 4, pp. 1059–
July 27-29, Chengdu, China, 2016, pp. 2583–2588. 1068, 2012.
[81] I. N. Katz, H. Mukai, H. Schättler, M. Zhang, and M. Xu, “Solution [105] T. Shima, “Optimal Cooperative Pursuit and Evasion Strategies
of a differential game formulation of military air operations by Against a Homing Missile,” Journal of Guidance, Control, and
the method of characteristics,” Journal of Optimization Theory and Dynamics, vol. 34, no. 2, pp. 414–425, 2011.
Applications, vol. 125, no. 1, pp. 113–135, 2005. [106] V. Shaferman and T. Shima, “Cooperative Multiple Model Adaptive
[82] I. Rusnak, “The Lady, The Bandits and the Body Guards - A Guidance for an Aircraft Defending Missile,” Journal of Guidance,
Two Team Dynamic Game,” International Federation of Automatic Control, and Dynamics, vol. 33, no. 6, p. 25, 2010.
Control, vol. 38, no. 1, pp. 441–446, 2005. [107] Q. Sun, Z. Chen, N. Qi, and H. Lin, “Pursuit and evasion conflict
[83] M. D. Awheda and H. M. Schwartz, “A Decentralized Fuzzy Learn- for three players based on differential game theory,” in Control And
ing Algorithm for Pursuit-Evasion Differential Games with Superior Decision Conference (CCDC), 2017 29th Chinese. Chongqing,
Evaders,” Journal of Intelligent and Robotic Systems: Theory and China: IEEE, 2017, pp. 4527–4531.
Applications, vol. 83, no. 1, pp. 35–53, 2016. [108] D. W. Casbeer, E. Garcia, and M. Pachter, “The Target Differential
[84] E. Garcia, D. W. Casbeer, A. Von Moll, and M. Pachter, “Mul- Game with Two Defenders,” Journal of Intelligent and Robotic
tiple pursuer multiple evader differential games,” arXiv preprint Systems, vol. 89, pp. 87–106, 2018.
arXiv:1911.03806, 2019. [109] E. Garcia, D. W. Casbeer, and M. Pachter, “Active target defense
[85] K. Margellos and J. Lygeros, “Hamilton–jacobi formulation for using first order missile models,” Automatica, vol. 78, pp. 139–143,
reach–avoid differential games,” IEEE Transactions on Automatic 2017.
Control, vol. 56, no. 8, pp. 1849–1861, 2011. [110] E. Garcia, D. W. Casbeer, Z. E. Fuchs, and M. Pachter, “Cooper-
[86] M. Chen, Z. Zhou, and C. J. Tomlin, “Multiplayer Reach-Avoid ative Missile Guidance for Active Defense of Air Vehicles,” IEEE
Games via Pairwise Outcomes,” IEEE Transactions on Automatic Transactions on Aerospace and Electronic Systems, vol. 54, no. 2,
Control, vol. 62, no. 3, pp. 1451–1457, 2017. pp. 706–721, 2018.
[87] Z. Zhou, J. Ding, H. Huang, R. Takei, and C. Tomlin, “Efficient path [111] M. Pachter, E. Garcia, and D. W. Casbeer, “Toward a solution of
planning algorithms in reach-avoid problems,” Automatica, vol. 89, the active target defense differential game,” Dynamic Games and
pp. 28–36, 2018. Applications, vol. 9, no. 1, pp. 165–216, 2019.
[88] J. Hespanha, Noncooperative game theory: An introduction for en- [112] E. Garcia, D. W. Casbeer, and M. Pachter, “Design and Analysis
gineers and computer scientists. Princeton University Press, 2017. of State-Feedback Optimal Strategies for the Differential Game of
[89] T. Basar and G. J. Olsder, Dynamic Noncooperative Game Theory,. Active Defense,” IEEE Transactions on Automatic Control, vol. 64,
Society for Industrial and Applied Mathematics, 1998. no. 2, pp. 553–568, 2019.
[90] J. Lewin, Differential Games: theory and methods for solving game [113] E. Garcia, D. W. Casbeer, and M. Pachter, “Optimal target capture
problems with singular surfaces. Springer-Verlag London Limited, strategies in the target-attacker-defender differential game,” in Amer-
1994. ican Control Conference, 2018, pp. 68–73.
1066

An Introduction to Pursuit-evasion Differential Games

Uploaded by

Copyright:

Available Formats

An Introduction to Pursuit-evasion Differential Games

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

An Introduction to Pursuit-evasion Differential Games

Uploaded by

Copyright:

Available Formats

2020 American Control Conference

Denver, CO, USA, July 1-3, 2020

An Introduction to Pursuit-evasion Differential Games

978-1-5386-8266-1/$31.00 ©2020 AACC 1049

(10) which can be computed by solving for φ in

where vE 6= 1 the Value of the game is simply scaled 8

by 1/vE to obtain the real capture time. We work with 6

where Rc = {(xA , xT , yT )|xA > 0, xT > 0, yT ≥ 0,

You might also like