{'fraction_non_alphanumeric': 0.03651739381126273, 'fraction_numerical': 0.006957524505093215, 'mean_word_length': 4.369659442724458, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 23, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
One Apollonius Circle is Enough for Many Pursuit-Evasion Games

This paper investigates obstacle-free simple motion pursuit-evasion problems where the pursuer is faster and game termination is point capture. It is well known that the interior of the Apollonius Circle (AC) is the evader's dominance region, however, it was unclear whether the evader could reach outside the initial AC without being captured. We construct a pursuit strategy that guarantees the capture of an evader within an arbitrarily close neighborhood of the initial AC. The pursuer strategy is derived by reformulating the game into a nonlinear control problem, and the guarantee holds against any admissible evader strategy. Our result implies that the evader can freely select the capture location, but only inside the initial AC. Therefore, a class of problems, including those where the payoff is determined solely based on the location of capture, are now trivial.


Introduction
In his seminal work, Rufus Isaacs [1], among other things, formulated pursuit-evasion scenarios as differential games. In the decades since, applications of games of this type have grown to include missile defense [2], football tackling strategy, target/coastline guarding, and more [3]. Even in Isaacs' work, it was clear that particular circles, associated with Apollonius of Perga and known for some two millenia prior, were an important tool in solving these problems. An Apollonius Circle (AC) is defined as the set of points in a plane that have a specified ratio of distances to two fixed points, known as foci 1 . When two agents with simple motion (single-integrator kinematics) are able to freely move on a plane, an AC can be drawn at a moment in time with the two foci being the current location of the agents and the ratio of distances corresponding to the ratio of the two agents' maximum velocities. It is well-known that with a faster pursuer, the AC encloses a set of points ("evader dominance region") that the evader can safely reach before the pursuer can capture it.
Isaacs noticed the relevance of this result to a class of pursuit evasion games that involve targets. The evader wins a target defense game by reaching the target before being captured by the pursuer, whereas the pursuer wins the game by ensuring that capture occurs first [5]. Isaacs' initial result was concerning a convex target, but the target guarding problem has been extended to other variants with targets having various shapes, inspired by and modeling different practical scenarios. Other works were motivated by the similar problem of capturing an "escaping" agent, e.g., lion-man problem, the target surface enclosed the players [6].
In all of these games, if the AC intersects the target, then the evader is guaranteed to be able to reach the target without being captured by the pursuer. The evader can simply aim at a point on the target inside of the AC and move with maximum velocity. However, some subtlety exists in the converse: "can the pursuer ensure capture if the AC does not initially intersect the target?" The pursuer does not have a fixed point in space that it can reach in order to win; it must end up at the same location where the evader ends up -and the evader gets a choice in the matter! This subtlety was the motivation for many of the works published in this field, and specific differential games were formulated to treat each problem separately [7][8][9]. Even though the standard methods provide strong guarantees in the region of the state space in which the value function is differentiable, special treatments are often required along the singular surfaces. Even the dispersal surface (see 6.1 of [1]), which is considered to be relatively benign (in comparison with e.g., focal, equivocal, switching, and transition surfaces), has been demonstrated to yield some interesting behaviors. For example, in the two-pursuer one-evader game of minmax capture time with simple motion, faster pursuers, and point capture it was shown in [10] that the canonical pursuer strategy [1] results in chattering in the vicinity of the dispersal surface if the evader stands still. Ultimately, the evader cannot increase its capture time beyond the Value of the game in this attempt to exploit the singularity, however, its ability to induce chattering in the pursuers' headings is undesirable. Additionally, there is still the issue of what Isaacs referred to as a perpetuated dilemma in which even if the players happen to select the same equilibrium while on the dispersal surface, the state of the system may remain in a singular configuration. In the case of Isaacs' wall pursuit game, a resolution for the perpetuated dilemma has been proposed in [11] which simultaneously addresses the pursuers' chattering. For target guarding, however, the consequences of non-uniqueness may be more dire. As we will see in Section 1.2, this type of chattering in a pursuer's heading could lead to growth of the AC, even to the point where the evader can win.
We provide a pursuer control that ensures capture of an evader within an arbitrary close neighborhood of the initial AC. The proposed pursuit strategy provides a satisficing control to solve a broad class of pursuit-evasion games (such as target guarding, reach-avoid) studied in the literature, and is, in many cases, approximately equal to the traditional equilibrium strategies.
The first significance of the result provided in this paper is that the proposed controller solves a wide class of problems without any special treatment. The second significance of the presented work is that the proposed controller is a continuous state-feedback function. As we will see, many difficulties come from large changes in heading (i.e., 'chattering') that traditional methods may have near singular surfaces. Our control law is smoothly defined everywhere on the state-space, which prohibits the evader from exploiting any singularity.

Motivating Example 1: Pure pursuit allows the AC to bulge out
The statement is often made that capture of the evader within the AC (at initial time) is guaranteed without explicitly proposing a pursuit strategy which does so (see, e.g., [6,12]). This statement should be made more precisely: if the pursuer knows a specific trajectory that the evader is going to take or has access to the evader's control at each timestep, then the pursuer can guarantee capture within the original AC [13].
Worse, still, is when an equilibrium strategy associated with capture time is utilized in a game over capture location (e.g., implementing pure pursuit in the evader's win region of a circular escape game [12]). Against pure pursuit (pursuer always moves at maximum velocity directly toward the evader's current position), an evader's reachable set is a strict superset of the AC [14] -this is of utmost importance in games wherein capture location is pertinent (as shown in Fig 1).
x P x E Fig. 1. If the pursuer implements pure pursuit, the evader can reach the target (green) even though the AC (red) does not intersect; the black curve represents locus of pure pursuit capture points for constant evader heading.

Motivating Example 2: Two target problem leading to oscillation and evasion
Appendix A details a target-guarding problem with two simple linear target regions (depicted in Figure 2). A naive pursuer strategy could consider which target is more 'dangerous' and focus on defending that target. The expected behavior from traditional methods is shown in Figure 2(a), where the game proceeds in a stable fashion toward one of the two targets, and it appears as though neither agent ever has an incentive to choose any other strategy. Now, consider in Figure 2  a completely different admissible evader strategy (go straight up) than any of the strategies identified by traditional methods. The result (depicted in Figure 2(c)) is that the evader's strategy exploits a singular surface, causes the pursuer's control to chatter, and ultimately results in the evader winning the game.
Therefore, one must be careful when reasoning about equilibrium behaviors in the vicinity of singularities. In the case of this dispersal surface, it is tempting to believe the evader should only choose to aim towards the left or right goal. However, from this example, we see that it is imperative to consider the opponent's entire strategy space. The pursuer must, in general, employ a strategy which guarantees capture against any evader strategy (which the naive, bang-bang pursuer strategy does not).

Main Results
Define the state of the game at time t as x E (t), x P (t) ∈ R 2 , i.e., each agent's position in a fixed Cartesian frame. The agents control their instantaneous velocity: The game starts at time t 0 , and terminates when capture occurs: x P = x E . While the AC was originally constructed as a circle 2 [4], for notational simplification, we define it to be the closed disc 2 In three dimensional space it becomes a sphere and the presented analysis holds for 3D systems as well.
The traditional AC is the boundary of A(t), and may be denoted as ∂A(t).
We claim that there exists a (feedback) pursuer strategy which ensures capture arbitrarily close to A(t 0 ) regardless of the strategy of the attacker. To prove our claim, we construct a fixed disc C centered at We will show that A(t) will be contained within the interior of C (denoted C • ) for all t ≥ t 0 and that the distance between the pursuer and the attacker will go to zero in a finite time.
x At time t, let us denote the minimum and maximum distances between A(t) and ∂C by d min (t) and d max (t), respectively. Therefore, Showing that We use the notationx to denote a unit vector along the direction of the vector x. PROOF.
(i) We consider the Lyapunov-like function V (t) d max (t)d min (t) and will show that V (t) > 0 for all t. In particular, d min (t) > 0 for all t, which is necessary and sufficient to conclude that A(t) remains within C • for all time. To show this, we consider the time derivative of V as follows: where the inequality is obtained by noticing that the vector v E (t) has a maximum magnitude of ν and using the Cauchy-Schwarz inequality. Note that this step does not require the evader to choose any particular policy; it is simply a worst-case analysis from the perspective of the pursuer. Assuming for the moment that z P (t) > 0 for all t ≥ t 0 , we can choose the pursuer strategy v P = z P (t), which gives uṡ Therefore, as long as z P (t) > 0, the pursuer's policy is well-defined andV (t) ≥ 0. Hence, V (t) is nondecreasing. Next, we will prove that z P (t) > 0 for all t ≥ t 0 . We will proceed by contradiction. First, note that z P (t 0 ) = δ > 0 since y(t 0 ) = 0 and R C = R A (t 0 ) + δ. Now, suppose that τ > t 0 be the first time instance when z P (τ ) = 0. Therefore, from (7) The condition d min (τ ) ≤ 0 implies that there must have been a time in the interval [t 0 , τ ] when d min becomes zero and thus V becomes zero. This is not possible since V (t 0 ) = δ 2 andV has been positive for the entire interval [t 0 , τ ) due to the hypothesis that z P (t) > 0 for all t ∈ [t 0 , τ ). This leads to a contradiction, and hence, z P (t) cannot be zero for any time t ≥ t 0 . 2 Since V (t) = R 2 C implies capture, the theorem holds. 2 The bound on capture time in Theorem 1(ii) is a conservative bound, and its purpose is to show that the evader cannot delay the capture time indefinitely. The exact capture time, or a tighter bound thereof, can be obtained by considering an optimal control problem. Theorem 1(i)'s spatial bound of capture within C can also be made tighter.
Corollary 1 Although we inflate the initial AC radius by δ to construct the region C, it is guaranteed that capture will occur within a δ 1 neighborhood of the initial AC, where Define δ 1 to be the smallest possible d min (t f ), and the corollary follows. The pursuit strategy (6) guarantees that the distance between the pursuer and the evader at time t > t 0 is strictly smaller that their initial distance regardless of the evader's strategy.
PROOF. Without loss of generality, we assume that capture has not happened by time t. From the proof of Theorem 1, we notice that Given that y(t 0 ) = 0 and Theorem 1 ensuring that R A (t) < R C for all t, we obtain from the above inequality that R C − R A (t) > R C − R A (t 0 ), or equivalently, R A (t) < R A (t 0 ). Then, the Lemma is obtained by using the fact that R A (t) = γ r(t) for all t.
Remark 1 Since z P (t 0 ) > 0, the pursuer policy (6) is a continuous function of the state, is always well-defined, and is continuous with respect to time.
This vital property ensures that no singular surface exists, sidestepping any of the issues described in Appendix A and present in much of the prior literature.

Corollary 2 (Mobile Sensing Game)
In limitedinformation games, where the pursuer has a circular sensing distance ρ ≥ ||r(t 0 )||, it is guaranteed to capture the evader using the strategy outlined in Theorem 1 without losing sensing of the evader.
The proof follows directly from Lemma 1.

Remark 2
If the evader employs any speed below ν, then all the guarantees in this section hold.
At first, this may seem like a trivial observation, since choosing speeds below ν are explicitly in the admissible set. However, we will discuss implications of this along with other implications of the main results in the next section.

Implications
This section provides corollaries, in the context of Games of Final Location and Target Guarding problems, that immediately follow from our main result.
Definition 1 (Game of Final Location) Consider a continuous value field φ : R 2 → R defined over the planar environment. For the pursuer-winning scenario, we define the Game of Final Location as the Game of Degree with the terminal payoff given as where t f is the terminal time, and x E (t f ) denotes the location where capture occurs. In other words, the pursuer seeks to maximize φ(x E (t f )), while the evader seeks to minimize it.
Define the minimum payoff inside the initial AC as and X * arg min x∈A(t0) φ(x) as the set of corresponding locations.
Corollary 3 For any ε > 0, there is a set of strategies where the pursuer follows (6) and the evader moves directly to some x ∈ X * which is an ε-equilibrium strategy pair.
PROOF. First, recall that the evader is dominant for any point inside A(t 0 ). That is, without regard to the pursuer's strategy, the evader can set an open loop strategy to travel directly toward any point in A(t 0 ) at max speed, and it will reach the point before the pursuer can capture it. Particularly, the evader can reach any point in X * ⊂ A(t 0 ). Then, the evader can simply wait at such a point until capture. Therefore, φ(x E (t f )) ≤ φ * .
Conversely, Theorem 1 implies that, regardless of evader strategy, capture will occur within C • . Due to the continuity property of φ, for any ε > 0, there always exists a δ > 0 such that the pursuer's strategy enforces The following Corollary establishes the Value of the Game of Final Location by first deriving Upper and Lower Value functions and then showing that they can be made to be equal [9,15].

Corollary 4
The Value of the Game of Final Location is φ * .

PROOF. The Upper Value of the game is
following directly from the first inequality in the proof of Corollary 3. The Lower Value of the game is Note that while there is no single δ-strategy for the pursuer to guarantee that a particular payoff is φ * , the Value is defined by considering the supremum of all possible strategies, including the limit as δ → 0. Then, because V ≤ V by definition, the Value must be φ * . 2 The standard Game of Distance to Target is a special case of the Game of Final Location, where the field φ is given by the distance from a target set: In some works, a Game of Distance to Target is constructed only to find a barrier for a Target Guarding Problem. In others, the Game of Distance to Target is, itself, the topic of interest. In either case, the traditional approach can be quite complicated for general target sets (for an example of an intricate target set, see Figure 4). Corollary 4 solves the Game of Degree, and now we turn to the Game of Kind. PROOF. Necessity follows trivially from longstanding results that the initial AC forms the evader dominance region.
For sufficiency, let d * > 0 be the shortest distance between ∂A(t 0 ) and any point on the target set. There can be multiple points on the target set that achieve this shortest distance. Now we select δ = 0.5d * to inflate the initial AC and construct the circle C, within which the capture is guaranteed. Since C does not intersect with the target set, capture occurs outside of the target set, i.e., before evader reaches the target set. Note that the implementation of the strategy is completely decentralized, and there is no coordination required among the pursuers. In fact, each pursuer does not even need information about its fellow pursuers.
The exposition up to this point assumes that the pursuer has perfect knowledge about the evader's maximum speed ν. We can also consider scenarios where 3 For the purposes of this paper, ties go to the evader.
the pursuer has some uncertainty in the evader's maximum speed. Denote the evader's true maximum speed by ν true , the pursuer's estimate of ν true byν, and with slight abuse of notation, denote C o (ν) to be the circular region defined for a speed ratio of ν. It can be verified that C o (ν 1 ) ⊂ C o (ν 2 ) if ν 2 > ν 1 , and the next corollary follows trivially from Remark 2.
Corollary 7 (Uncertain Maximum Speed) Ifν ≥ ν true , the pursuer strategy (6) guarantees that the evader does not reach any point outside C o (ν).
The tighter the estimateν is, the smaller the guaranteed capture region C o (ν) will be. Therefore, while having a smaller value forν ensures capture within a smaller region, it also increases the risk ofν being smaller than ν true and consequently not capturing at all. On the other hand, a higher value ofν reduces the risk ofν being smaller than ν true but it also increases the guaranteed capture region. Thus, in context of the Game of Final Location, a natural trade-off between the risk of not capturing at all and the area of the guaranteed capture region (and thus, perhaps an increase in the final value) arises automatically through the pursuer's estimateν. Furthermore, this simple result only considers the case where the pursuer makes one estimate at the beginning of the game and commits to a strategy based on that estimate. How/when the pursuer should updateν (coupled with how the evader should structure his strategy to counter the pursuer's update law) remains an open question.
We finish with the Generalized Target Guarding version of Corollary 7. With a now familiar abuse of notation, let A(t; ν) denote the AC computed based on the positions at time t using a particular value of ν, whose true value may be unknown to the players.

Corollary 8 (Critical Speed)
There exists a pursuer strategy to win the Generalized Target Guarding problem if and only if ν true < ν crit , where ν crit < 1 is the smallest ν such that min PROOF. For any ∆ > 0, the pursuer plays the game with the strategy from Theorem 1, assumingν = ν crit − ∆. Then δ = νcrit (1−νcrit) 2 −ν (1−ν) 2 r(t 0 ) > 0 guarantees a win for ν true ≤ ν crit −∆. Such δ always exists since we have δ → 0 with ∆ → 0. 2 This has implications for the Generalized Target Guarding Game with uncertainty in the speed ratio. Suppose the pursuer does not know the maximum speed of the evader. By playing the game assumingν, the pursuer can lose only when ν true > ν crit − ∆. Importantly, since the evader is guaranteed to win anyway when ν true > ν crit , only an infinitesimal parameter regime, ν true ∈ (ν crit − ∆, ν crit ] remains in question. Therefore, in contrast to the Game of Final Location, the pursuer can (and the authors believe, should) avoid worrying about actively estimating ν true for Generalized Target Guarding in favor of simply choosingν arbitrarily close to ν crit . The pursuer gains no advantage by performing such an estimate. Furthermore, by not using an estimator, it prevents any adversarial action based on exploiting the estimator.

Conclusion and Limitations
In this work, we provide a sufficient strategy for the pursuer which guarantees that a slower evader will be captured within a neighborhood arbitrarily close to the Apollonius circle constructed at the beginning of the game. In contrast to existing strategies in the literature, our strategy eliminates the nuances of considering particular problem geometries separately and their resultant singular surfaces.
The results of this paper do not apply to cases where the agents have more complex dynamics (higher order, nonholonomic, state spaces with other geometries), in games with a non-zero capture radius, or where obstacles are present. This is because the AC no longer accurately captures the dominance region. Furthermore, when the evader is faster than the pursuer, i.e., ν > 1, it is easy to see that capture cannot be enforced with only one pursuer. Multiple pursuers will have to cooperate to guarantee capture. Finally, other games, such as the Game of Capture Time, still require further treatment.
Similar to [16], consider an example where there are two parallel vertical target regions (instead of circular target regions), as shown in Figure A.1. A typical differential game formulation may discover equilibrium strategies where both agents head directly to the point on the AC that is closest to one of the two targets (i.e., Question What happens on the singular surface?
We will discuss three different possible answers.

Answer A Both agents choose an instantaneous mixed strategy.
This is the natural first answer, especially considering the subgame perfect nature of the nonsingular strategies. Both agents pick either I 1 or I 2 , say with 50% probability for the first instant. Immediately thereafter, either d 1 < d 2 or d 1 > d 2 , and the agents' equilibrium control actions for the remainder of the game are well-defined; this is true whether the agents choose the same aim point or not.
However, there is a problem with this reasoning. In a Nash equilibrium, no player has anything to gain by changing only their own strategy. We will show by contradiction that Answer A is not actually a Nash equilibrium.
We can view the pursuer's strategy (head directly to I 1 or I 2 , choosing an IMS between these options on the singular surface) as a bang-bang type strategy. That is, there are only two possible actions he may choose to take. The question then is: holding the pursuer's strategy constant, is there anything else the evader may prefer to do? Indeed, there is. Consider what happens if the evader chooses to move directly up. The pursuer's strategy will chatter back and forth across the singular surface, and the system will remain at/near the singularity.
This behavior is similar to that of [10], but can be much more dangerous. Consider the distance between the two agents r = r . The time derivative of this distance iṡ In this vertical arrangement on the singular surface, if the evader heads straight up,r ≈v E . If the pursuer heads toward I 2 , for example (shown in Figure A.1b), Notice thatṙ becomes positive when ν is sufficiently large (>≈ 0.786). In this case, the result of the pursuer control chattering is that the distance between the agents will always increase (at least until the AC grows to intersect a target region, at which point, there exists an evader strategy to win). A video of a discretized simulation of this behavior can be viewed at https: //youtu.be/7J_8l_Uy6f8.
This result is similar to that in Section 4 of [17], and as in that paper, a full treatment of this scenario requires solutions to differential equations with discontinuous right-hand sides (i.e. in the sense of Filippov [18]) due to the fast switching behavior of the pursuer. That said, supposing that the policy does result in a continuous solution, we have seen that the evader can benefit from choosing a different strategy (go straight up instead of toward I 1 or I 2 ), and so Answer A cannot be a Nash equilibrium.
Answer B The pursuer heads straight toward the evader.
The analysis for this answer likely follows closer to [10], and it resembles adding a form of 'deadzone' into the pursuer's policy. We assume that the pursuer commits to heading straight toward the evader for some finite time T once the state is on or sufficiently close to the singular surface. This commitment may allow the pursuer to alleviate the concern of Answer A at the cost of some penalty in the reward function for the period of time that the pursuer is heading straight toward the evader (J can be decreasing during this time). T may need to be calibrated according to ν.
Further, unlike [10], a full analysis of this answer would require us to (after specifying the pursuer's committed strategy) determine what the best evader counterstrategy is. Should the evader simply harvest the small reward gain and then proceed to a critical point? Can it instead stay near enough to the singular surface to occasionally (and advantageously) trigger the pursuer's deadzone? These questions would require significant effort, likely repeated for a plethora of different geometries, and it is clear why this paper's main result is to be preferred.

Answer C A viscosity solution.
There has been great historical effort in describing viscosity solutions to differential games on singular surfaces and connecting them to dynamic programming problems, such that they can be estimated using numerical methods [19]. However, these methods are still difficult in practice for many problems of interest [20], and even if solved, generally only provide numerical results. The authors believe that these difficulties are easily overcome for many problems by using the result of this paper instead.