## Abstract

A qualitative account is given of a differential pursuit/evasion game. A criterion for the existence of an intercept solution is obtained using future cones that contain all attainable trajectories of target or interceptor originating from an initial position. A sufficient and necessary conditon that an opportunity to intercept always exists is that, after some initial time, the future cone of the target be contained within the future cone of the interceptor. The sufficient condition may be regarded as a kind of Nash equilibrium.

## 1. Introduction

In this note, we consider the differential game that describes the pursuit of a target with position *y*(*t*) at time *t*, by an interceptor whose position at time *t* is *x*(*t*). Both target and interceptor are assumed to manoeuvre freely and autonomously, subject to certain overall constraints. The evolution of *x* and *y* is given by
1.1
and
1.2
Here, *F* and *G* are assumed to be bounded analytical functions, and *u*=*u*(*t*) and *v*=*v*(*t*) are piecewise analytical controls. The histories of *x*, *y* and *v* are assumed to be known up to time *t*. If a control *u* can be found such that at a time *t*_{i} the interceptor has contrived to manoeuvre so that ∥*x*−*y*∥=0, an interception is deemed to have taken place, and the game terminates. This problem is a simplified version of the one posed by Pontryagin (1964).

This study addresses the conditions under which an interception can take place, rather than with conditions of optimality as to the time to interception, or payoff functionals. We seek conditions under which an interception is *guaranteed* to be possible. There is no assumption, for example, that an interception, if possible, will actually take place. We are more concerned with the existence of a solution to the game than with payoffs. However, in the present context, we may assume that only terminal payoffs are of interest, and that these need not sum to zero. In the terminology of Isaacs (1965), we regard this problem as a game of kind.

The principal tool used to study this problem is the relation between future cones, as defined in the next section, of target and interceptor. Constraints on the motion of either player enter the problem formulation through the topology of the future cones.

One may consider the results which have been proved below as a mathematical exercise confirming the commonplace observation in naval warfare that, in order to defeat an adversary in a surface engagement, it is sufficient and necessary to turn inside the adversary’s turning radius. Although the discussion will be couched in terms of trajectories in **R**^{3}, appropriate for aircraft, missiles, spacecraft or simple predator/prey interactions, the results clearly hold in **R**^{2}, as, for example, in the case of surface naval vessels, or in dimensions higher than three. The extension to more than two players is discussed in the sequel.

## 2. The future cone

We begin by defining the future cone of a manoeuvring player, and sketching some of its properties. Under the influence of propulsive forces, of its control *u*(*t*), and of external forces such as gravity or aerodynamic drag, the position *x*(*t*) of the interceptor will evolve as it manoeuvres. The evolution as given by equation (1.1) will be continuous, but need not always be differentiable, depending on the nature of *F* and of the control *u*(*t*). Identical remarks hold for *y*(*t*). For an effective interceptor, the control for *x* will depend upon the history of *y*, in general, and the motion of both interceptor and target may be quite involved. One may think of their trajectories as being representatives of generic Feynman paths in **R**^{3}. But, as a practical matter, both target and interceptor will respect certain physical limitations as to, say, maximum acceleration or total velocity change Δ*v*. In addition, the interaction between target and interceptor may be expected to take place during a finite engagement time interval, and to be confined within a finite engagement volume.

At some initial time , the interceptor will occupy a definite position . If we consider all possible histories for *x*(*t*) originating at , these will comprise a topological cone in **R**^{4} with vertex . We call this set the future cone of and denote the set of points subsequently accessible to the interceptor in the time interval (*t*_{1},*t*_{2}), with , by . Clearly, the future cone originating from a vertex at time the cone originating from any vertex at a time .

We may suppose that a freely manoeuvring player is able to move in any direction in **R**^{3} and that, if it can manoeuvre to a point *x*(*t*), it can likewise manoeuvre to points within any small neighbourhood of *x*(*t*). It will thus be convenient to regard the sets and as open for . (The extension to closed future cones will be discussed in §4.) The assumption that both target and interceptor can manoeuvre freely permits us to treat the future cone for each as a path-connected manifold for ; in particular, as path-connected for each value of *t*. The attainable trajectories intersecting each point in a space-like section of a future cone, i.e. the subset of the cone at any single value of *t*∈(*t*_{1},*t*_{2}), are nowhere tangent to the section, by virtue of the boundedness of *F*. For . We conclude that the future cones of both target and interceptor for admit a time-like foliation (Novikov 1967), and that their space-like sections are leaves of the foliation. Every attainable trajectory thus traverses leaves of the future cone in a positive sense as time increases. Given leaf , a leaf with is generated by exponentiating the action of the tangent space over each point corresponding to admissible values of Δ** v**. The ability of either target or interceptor to manoeuvre freely also implies that the tangent space over any point in is balanced

^{1}and thus any leaf to its future will be the union of convex neighbourhoods. As bounded subsets of

**R**

^{4}, the sets and have compact closure. Let and consider an open covering of that includes . Compactness of thus implies that is covered by a finite union of convex neighbourhoods.

The foregoing remarks serve to justify the assumptions we shall make regarding the future cones of target and interceptor. It will be assumed that the subset of either cone lying to the future of its vertex is a manifold possessing a time-like foliation, whose leaves are locally convex and which possesses a finite convex cover. In particular, there is no assumption that the future cone of either target or interceptor, or their leaves, is necessarily convex as a whole.

## 3. Conditions for interception

### (a) Guaranteed interception

The existence and character of optimal solutions to equations (1.1) and (1.2) leading to interception has been well studied since Pontryagin (1964); vide Pontryagin (1971, 1974, 1981). These studies emphasized minimization of time-to-capture for the pursuer and maximization of that time for the evader. There is also a large body of literature devoted to the study of the related Homicidal Chauffeur and Two Cars games introduced by Isaacs (1965); e.g. Brooks (2008), Miloh *et al.* (1993), Miloh (1982), Getz & Pachter (1981), Shinar & Gutman (1980) and Cockayne (1967). The studies cited variously treat games of degree or of kind, but all impose restrictions on the form of the game to facilitate its detailed analysis, such as limitation to a linear game, or to fixed velocity ratios for the players, or to piecewise constant radii of curvature.

Our concern here is with the general form of equations (1.1) and (1.2), but is restricted to the more limited goal of finding a qualitative description of conditions under which we may be confident that the interceptor can force an interception, optimally or no, subject to the assumptions given above. A winning pure strategy of the interceptor is to choose an attainable trajectory that will lead to interception of the target. (A mixed strategy would choose among multiple trajectories with this property.) This choice amounts to a mapping from the set of all trajectories available to the interceptor to its desired *actual* trajectory. For present purposes, a *guaranteed intercept* will be said to exist when an interception solution always exists, no matter how the target manoeuvres within its future cone. For the remainder of this note, ‘intercept’ is to be understood as ‘guaranteed intercept’ even when not so explicitly identified.

The development in this section relies upon a fixed-point theorem for correspondances owing to Tian (1991). For completeness, we restate theorem 3 of Tian (1991).

### Theorem 3.1.

*Let X be a non-empty subset of a locally convex separated topological vector space E. Suppose that* *is an upper semicontinuous correspondance with non-empty closed convex values. Then, the necessary and sufficient condition for the existence of a fixed point x***∈F(x***) is that there exists a non-empty compact convex subset* *such that*
3.1

### (b) Interception at a specified time: a condition on leaves

We begin by proving

### Lemma 3.2.

*A sufficient and necessary condition for the existence of a guaranteed intercept is that at the time of intercept* *t*_{i},
3.2
*for* .

### Proof.

The necessary condition is elementary. Suppose a guaranteed intercept exists at time *t*_{i}. Then, every point *y* in must coincide with some point *x* in in order that ∥*x*−*y*∥=0 for at least one pair of values of *x* and *y*. If equation (3.2) is false, then there would be some portion of that lay outside the attainable set of interceptor positions at that time. Thus, there would be a subset of for which ∥*x*−*y*∥>0, .

The sufficient condition follows from theorem 3 of Tian (1991). Assume that equation (3.2) holds. Then, is a non-empty subset of the locally separated convex vector space **R**^{3}, and its intersection with is non-empty. Suppose that, of all the possible trajectories , the actual trajectory of the target is *y**(*t*). The mapping from into given by *F*(*x*)={*y**(*t*_{i})} is closed and convex, . For a sequence *x*_{n} tending to any , *F*(*x*_{n})={*y**(*t*_{i})}=*F*(*x*(*t*_{i})). The mapping *F* is thus upper semicontinuous. The point *y**(*t*_{i})∈*N*_{y*(ti)} of , where *N*_{y*(ti)} is one of the convex sets that comprise the finite open cover of . Therefore, The requirements of theorem 3 of Tian (1991) are thus satisfied. Combining the consequent fixed point *x**(*t*_{i}) for *F* with the tautological fixed point resulting from the target’s ability to manoeuvre freely, we may write
3.3
■

### (c) General interception condition

We next extend the lemma to the corresponding assertion for the entire cone . The conditions for existence of a guaranteed intercept are given by

### Theorem 3.3.

*Let* *. Then, a sufficient and necessary condition for the existence of a guaranteed intercept at* *is that*
3.4

### Proof.

The sufficient condition follows the reasoning used in the lemma, applied to the sets and in the locally convex separated topological vector space **R**^{4}. The mapping now is into the target trajectory , which (as before) is closed, convex and upper semicontinuous. To show existence, choose a time . By previous remarks, a convex neighbourhood belonging to a finite open cover of exists for which for some and . Then, theorem 3 of Tian (1991) gives existence of a fixed point for such that
3.5

The necessary condition is obtained by transfinite induction (Kelley 1955). Let and take *t*_{i}−*t* as an ordinal. We prove the result for and extend to the full set at the end.

We begin by showing that the necessary condition holds at late times. Suppose that a guaranteed intercept exists at time *t*_{i} for *t*_{γ},*t*_{i} within any neighbourhood of *t*_{1}. As ,
3.6
By lemma 3.2, it follows that
3.7

Next, suppose that at least one guaranteed intercept opportunity exists for time *t*_{i} between *t*_{γ} and *t*_{1}. By the inductive hypothesis,
3.8
We wish to examine the prospects at an earlier time *t*_{β}. Consider the sets and
3.9
and similarly for . If a guaranteed intercept is to be possible ∀*t*∈(*t*_{β},*t*_{γ}), at no time *t* in (*t*_{β},*t*_{γ}) can it be that
3.10
by lemma 3.1. Letting , we have equation (3.4). ■

## 4. Discussion

The sufficient conditions (3.3) and (3.5) have been posed in the form of a Nash equillibrium (Nash 1950). One may paraphrase the outcome as follows: the target can navigate to any point in its future cone but, no matter how the target moves, so long as the future cone of the target lies within that for the interceptor, the interceptor can always manoeuvre to the target’s position.

Were a convex set, the sufficient condition for the theorem would follow immediately from the Kakutani (1941) fixed-point theorem applied to . This assumption is stronger than might be desired, but we may suppose the interceptor can choose to manoeuvre within a convex future cone during an engagement, if that is to its advantage. This observation amounts to regarding the choice of future cone as part of specifying a strategy for the interceptor.

Nothing in the method of proof given in §2 requires the future cone of either player to be open to the future of its vertex. One may regard a closed future cone of (say) the interceptor as the closure of a suitably chosen non-closed cone of the kind described in §2.^{2} Provided that the boundaries of consist of trajectories with the properties described in §2, they satisfy a transversality condition with respect to the leaves of the cones. The closed future cones thus admit a time-like foliation. Finally, a closed future cone so defined is a finite union of closed convex sets. Both necessary and sufficient conditions for the theorem are therefore satisfied if
4.1
where the actual future cone of either player may be taken to be the indicated closure. Note, however, that by the Tietze–Nakajima theorem, a locally convex cone that is closed is necessarily convex.

Extension of these results to dimensionalities other than three poses no difficulties. As in Nash (1950), the extension to an *n*-player game is likewise straightforward. However, the interpretation of the results differs for the notable case of a single interceptor manoeuvring to intercept one genuine target amidst a number of indistinguishable decoys. Recall that the game terminates when an interception occurs; that is, we do not assume that an interceptor can engage multiple targets in succession. In this case, a guaranteed intercept will certainly exist, but it might lead to the interception of a worthless decoy. Only if the number of interceptors equals or exceeds the number of targets real and bogus, can one say with confidence that the conditions on the future cones of targets and interceptors obtained in this note guarantee the existence of interception opportunities for all actual targets.

## Footnotes

↵1 The tangent space

*T*over a point is balanced if*x*∈*T*implies*t**x*∈*T*, where |*t*|≤1.↵2 A closed future cone is equivalent to the

*attainable set*introduced by Varaiya (1967) and Roxin (1969) in a different context.- Received October 16, 2009.
- Accepted November 19, 2009.

- © 2009 The Royal Society