Differential games of pursuit

. t

Indeed, let («*(•), «*(•)) be the e q u i l i b r i u m p o i n t i n the game Y =< *(«(•)>»(-))>•

T

h

e

P,E,

D

* ( « ( • ) , » * ( • ) ) > * ( « • ( • ) . » * ( • ) ) > ^{"•(•)."(-))

d-3.2)

for a l l «(•) G P.w(-) G £ . W e shall r e w r i t e (1.3.2) as K{u{-),v-{.))>K{u'{-)y{-)),

(1.3.3)

/f(u-(),«())<XK(-),«'(.)).

(1.3.4)

Integrating (1.3.3) w i t h respect t o an a r b i t r a r y measure v G E, a n d (1.3.4) w i t h respect t o an a r b i t r a r y measure, a G P we o b t a i n / K{u{-),v'{-))dp.

> j K(u'(-),v'(-))dp

= K(u-(-),v*(-)),

(1.3.5)

j K{u-{-)A-))dv

< j

= K(u'{),v'{-)).

(1.3.6)

K(u-(-),v-{-))d„

W e i n t e g r a t e (1.3.5) a n d (1.3.6) respectively w i t h measures

"„•{.),/*«•(.)•

T h e n , u s i n g (1.3.5) a n d (1.3.6), we find A i ( u , i v . ) ) > A/(« .(.,, i/ . ) > A/(^ .(.,,i/), (

u

v

( 0

u

(1.3.7)

i.e. the p o i n t A / ( / i ' ( . ) , i V ( - ) ) is the e q u i l i b r i u m point in the m i x e d strategies U

in the g a m e F , a n d A / ( ^ - ( ) . "-.(•)) =

^K(0,»*(-))-

For s i m p l i c i t y , we i n t r o d u c e the following n o t a t i o n :

M( . v) M h

=

M(u(),v).

T h e o r e m 3 For the pair p.", v* to be the equilibrium necessary

and sufficient

point in the game T , it is

that for all u(-) G P . t i ( - ) G E the following

inequality

holds. A / ( u ( - ) , f * ) > M{p-,v-)

> Mip-A-)).

(1.3.8)

Preliminaries

20

P r o o f : Sufficiency. L e t « £ P,u € E be a r b i t r a r y m i x e d strategies. W e integrate b o t h parts of the l e f t - h a n d inequality i n (1.3.8) w i t h respect to the measure p, and b o t h parts of the r i g h t - h a n d inequality i n (1.3.8) w i t h respect to the measure v. A s a result , we o b t a i n M(p,S)

= J

M(u(-),u')dfi>

> j M{ i\v')du M{pS,v')

(1.3.9)

= M{n\v-),

r

= j M{p',v')&t>

> j M{n',v(-))dv

>

= M(fi',v).

(1.3.10)

F r o m (1.3.9) and (1.3.10) we find out that the pair (/i*,c*) constitutes the e q u i l i b r i u m point i n m i x e d strategies. T h e necessity is evident, since if (1.3.2) is satisfied for all u £ P , v £ E, then i n p a r t i c u l a r , it also holds for a l l strategies / i ( - ) , !>„(•) prescribing p r o b a b i l i t y one to the elements u(-) € P , v{-) € E. • u

A s shown, the m i x e d strategies extend the players' strategy sets i n the original game and preserve the value of the game and the e q u i l i b r i u m point, if any. In most cases, the e q u i l i b r i u m point i n m i x e d strategies is found to be existent, while the e q u i l i b r i u m point may not exist. W e consider a special class of z e r o - s u m two-person games T where there is the e q u i l i b r i u m point i n m i x e d strategies. T h e o r e m 4 Let P e CompR (E G CompR ) be a compact set in Euclidean spaces of corresponding dimension, and the function K(tt(-}, v(-)) be continuous on Cartesian product P X E. Then in the game V • < P , E, /^(u(•),«(•)) > there is the equilibrium point in mixed strategies. k

1

For the proof this theorem y o u may refer to [8]. In some cases, using specific properties of the payoff f u n c t i o n , we may provide a more precise definition for structure of m i x e d o p t i m a l strategies i n the game V. Specially , this occurs i n the games w i t h convex and concave payoff f u n c t i o n . In w h a t follows we w i l l be dealing w i t h this type of games a n d , therefore, we w i l l consider t h e m i n details i n the following section.

1.4

Games with convex payoff function

A s s u m e t h a t the set E is compact i n R , n

i t " , the function K(u(-),v(-))

the set P is convex and compact i n

is continuous i n all its variables a n d convex i n

G a m e s w i t h convex payoff

function

21

«(•) for a l l o( ). S u c h game T = < P, E,K(u(-),v( w i t h convex payoff function (or convex game).

)) > w i l l be called the game

Let us consider a m i x e d extension of the game T over spaces of various p r o b a b i l i t y measures on P and E. Investigation of such type of games is of interest to us because the solution of the f a m i l y of p u r s u i t - e v a s i o n type games w i t h incomplete i n f o r m a t i o n reduces to t h e m . T h e s o l u t i o n has simple geometrical structure. In this section we w i l l define a general f o r m of o p t i m a l strategies and i n d i c a t e a m e t h o d of c o m p u t i n g the value of the game. W e hope t h a t the reader has some knowledge of fundamentals of the theory of convex sets a n d convex functions, therefore the relevant results of this theory are given w i t h o u t proof. Let I be a m i x e d strategy by which the point 2 is chosen w i t h p r o b a b i l i t y 1. T h e f o l l o w i n g theorem holds. t

T h e o r e m 5 The value of the game T is determined v = min max

by the

formula

Klu.v).

Player It has an optimal strategy of the form A j > Q J . At the same time, all pure strategies K(u,v) is achieved, are optimal for Player K(u, v) with each fixed v(-) is strictly convex for Player I is unique.

v = Y,i=i ^ i ^ w 1, I under which m i n max,, I . In addition, if the function in u(-), then the optimal strategy =

0

UBI

u

In T h e o r e m 5, I/Q is a p r o b a b i l i t y measure concentrated on not more t h a n the (n + 1) points i n the set £ , v , ( - ) Before t u r n i n g i m m e d i a t e l y to the proof of T h e o r e m 5, we shall prove some a u x i l i a r y l e m m a describing the properties of convex functions. Let B be a compact convex region i n the n - d i m e n s i o n a l space whose elements are denoted by y. T h e f u n c t i o n / is called linear if / ( £ X,y,) = £ A ; / ( i / ; ) with = 1 (the linear f u n c t i o n is not necessarily homogenous). T h e function f(y) — 1 denoted by u>, is linear. T h e linear functions form the (n - f 1) d i m e n t i o n a l linear space E. W e denote by F an element of the conjugate space E' . L e m m a 3 If F[w)

= 1, then there is such y that F{f)

= f(y)

for all f g

E.

P r o o f : It suffices to show t h a t 11 -I- 1 equations F(fi) = f(y) have a solution w i t h respect to y for n + 1 linearly independent elements / , 6 E. B u t w may be t a k e n as f\. T h e first equation then converts to identity. T h e other n equations are independent a n d have a s o l u t i o n , since y is an element of the n - d i m e n s i o n a l space. •

Preliminaries

22

L e m m a 4 The sei of all functions f, that are nonnegative on the set B, form a closed convex cone P C E with its vertex at zero, and the function u> is its interior point. Moreover, the region P(y) = {f(y) : f(y) € P}, for which P(y) > 0. coincides with B. (We denote by P(y) a collection of all f{y) for f € P, and by f{B) a collection of all f(y) for y G B). P r o o f : F i r s t show t h a t P is a closed convex cone. L e t f f € P , a > 0, 0 > O.Then f = af +0f also belongs to P , since f(y) = a / , ( y ) + Pf [y) > 0 for all y € B. T h a t the P is closed is evident. If / = 0, then f € Pit

1

3

1

2

W e now show that the region, for w h i c h P(y) > 0, coincides w i t h E. L e t y & B. T h e n y may be separated from B by a h y p e r p l a n e , i.e. it is possible to indicate such / € E that f(y) < c < f{B). Consequently, the function f — cw belongs to P and is negative i n j / . Suppose w is not the interior point of P. T h e n there is a sequence / „ —» u>, / n € P- For each y„ 6 B there is y £ B such t h a t f {Vn) < 0. Since B is compact region , then there exists a subsequens y converging to y € B and such that / n , ( u „ ) < 0. T h e n , f(ya) < 0, as well. In this case , however, I i m _ o o /n (!/o) < 0the same t i m e , l i m f (y) = 1 for a l l t/'s on B, i.e. w is the interior point of the set P. • n

n

ni

0

t

nt

t

A

t

n - D O

n

L e m m a 5 Let Q be a compact convex sei from E not intersecting there arc such y 6 B and S > 0 that Q(y) < —6.

P.

Then

P r o o f : Let F € E' a n d shares P and Q, i.e. F(f)>b>F(g)

(1.4.1)

for a l l / € P and q £ Q. F r o m this it i m m e d i a t e l y follows that F(f) > 0 for all / € P Indeed, assume that the case is the contrary. L e t fi be such that F(h) < 0. T h e n Xf, £ P for any A > 0 and we have F(Xfj) = XF(f ) < 0. Since A cannot be chosen a r b i t r a r i l y large, this contradicts (1.4.1). T h u s , P{f) > 0 a n d , a d d i t i o n a l l y , there is 6 ^ 0 satisfying (1.4.1), since 0 6 P, a n d P(0) = 0, and the sets P and Q are convex, closed and do n ot intersect. F r o m (1.4.1) we o b t a i n t

F(f)>0>

F(q)-b.

(1.4.2)

Setting ( — 6) = 6 > 0, we derive the inequality P(Q)

+ 6
(6>0).

(1.4.3)

Since w is an interior point of P, then F{u>) > 0 holds. W e may choose F i n such a manner t h a t F(w) = 1. B y L e m m a 3, we find the point y satisfying the inequality Q(y) + 5 < 0 < P(y). In accordance w i t h the preceding l e m m a , y € B. T h i s completes the proof of L e m m a 5. •

G a m e s w i t h convex payoff

23

function

L e m m a 6 If the function s u p f (B) is positive for the family {f } of linear functions, then for the properly chosen A, > 0, E S S Aj = 1 and a ; , i = I,... ,n,n + 1, the function f = E S r i A / is a member of P, i.e. f{B) > 0. a

a

a

;

0 j

P r o o f : If / „ ( ; / ) > 0 for t h e fixed a a n d y, then there is a n open set c o n t a i n i n g y where there is a strict inequality. Consequently, by H e i n e - B o r e l theorem on covers, we m a y find such finite subset {f } t h a t m a X j { / ( j / } } > 0 for each yeB. 0)

0>

D e n o t e by Q a convex h u l l of the s u b f a m i l y {f ,}- Because of L e m m a 5 , the sets P a n d Q intersect. Since Q is b o u n d e d , a n d P is not b o u n d e d , then a b o u n d a r y point of t h e set Q lies i n P T h i s point belongs to a space of dimension not exceeding n , therefore it m a y be represented as a convex linear c o m b i n a t i o n of not more t h a n n + 1 functions / „ . T h i s proves the l e m m a . • a

T h e o r e m 6 Let {ip } be a family of continuous convex functions defined on the compact convex n-dimensional set B. The function sup

0 there are such indices a ; and such A : , that for all y G B. a

a

a

0

7i+l

1=1

when A,- > 0 and £ £ £ A, = 1. Proof:

Suppose t h a t for a l l j 6 B , satisfying the condition of T h e o r e m 5,

the following i n e q u a l i t y holds 6 > i n f sup

T h e set y € B, for w h i c h

k

0

T o prove the second p a r t of the theorem, we w i l l consider a f a m i l y {f } s

of

all linear functions satisfying the c o n d i t i o n (1.4.4)

[Va-ff>KB)>0

for a c e r t a i n a. A n y y - t a n g e n t plane satisfies this c o n d i t i o n , so that f a m i l y a

f

B

contains a l l planes tangent to ip„. Consequently, for a l l y's sup fp{y) = supy {y) a

> c.

Preliminaries

24 Consider for a fixed 6 > 0 the f a m i l y Fp = lb-(c

-8)w].

Since sup,, f 13(B) > c, we have sn [fp-(c-6)w](B)>S>0. 0 P

W e shall apply L e m m a 6 to the f a m i l y Fp and choose p\,..., /3 , A i , . . . , A Let be the functions corresponding to f f r o m (1.4.4). T h e n n+t

n + 1

.

0i

n+l

n+l

i=l

i=1

for all y G B, which was stated i n the theorem. W e now prove T h e o r e m 5. Consequently, the function tp(u) = sup K(u, v) achieves a m i n i m u m value at some point u 6 B, and for every t > 0 we may choose {A;} and {v\}. T h u s , v

0

n+l

for a l l u € P , where A|, «J take values from compact sets, i.e. X\ > 0 and Jl"=i A ' — 1. Therefore, as * —1 0, for every i we may choose the l i m i t points \9 ?'i = l , . . . , n + 1, satisfying the conditions A? > 0 a n d E " ^ A? = 1, }

1

v

£a^(»,^J^

(1-4-5)

for a l l u £ P . T h e inequality (1.4.5) implies t h a t if Player II adopts a m i x e d finite strategy v*(-) = A°/,,°, then his payoff is at least f(u ). A t the same t i m e , if Player I adopts a pure strategy u , then w i t h any v P l a y e r IPs payoff equals 0

0

K(u ,v) 0

< sup K(u ,v) 0

=

ip(u ). 0

T h u s , i ^ ( U ) is the value of the game, and {7^, v'} a pair of o p t i m a l strategies. Let us now assume t h a t K is a s t r i c t l y convex w i t h respect to u for any u , and show that the o p t i m a l strategy for Player I here is unique. A l s o , for P l a y e r II we choose a fixed o p t i m a l strategy of the form YJlH A?f„j, define P as a set of such points u that 0

1+1 i £A°A>,v°) < («o) + -, v

* = 1,2,,..,

G a m e s with convex payoff function and

25

denote by p a p r o b a b i l i t y measure related to any o p t i m a l strategy for

P l a y e r I . It is r e a d i l y seen t h a t u(P

= 0 for any v.

— P) v

B u t it follows

from the s t r i c t convexity t h a t the intersection [") P* consists of a unique p o i n t . Consequently, the m i x e d o p t i m a l strategy /,„, is unique. T h i s completes proof of the t h e o r e m .

the •

T h e result of this section will be i l l u s t r a t e d by referring to examples. Example Si = S

2

8. L e t us consider a special case given i n E x a m p l e 1 from 1. L e t

— S a n d the set S be a closed circle on the plane, w i t h O as its center

and R as r a d i u s . T h e payoff function K(u,v) respect to x for fixed y. x

2

£ S,j£

= p{x y),x t

S,is s t r i c t l y convex w i t h

Indeed, let y — (y\,y )

£ £, x

2

=

1

(xj,x ) £ 2

S,

= ( x j , x\) € S . If s i ^ x , then for a l l 0 < A < 1 2

p{ ,Xx y

+ (1 - \)x )

+ (1 - X)p( x ).

< \pfax )

2

%

1

(1.4.6)

2

yi

In fact, { A y i + (1 -

- [A3} + (1 - \)x }} 2

{A( ,i-xj)4-(l-A)( !

= A (yi-xl) + 2

! f

=

2

i-3?)} =

0-4.7)

2


2

2

2

/

+2A(l-A)(j/ -xi)( /i-xJ). 1

!

Similarly {Ay

2

+ (1 - A ) y - [Xx\ + (1 - A ) z ] } 2

= A %

2

- x

2

)

2

+ (l-A) (

2

2

y

2

-x ) + 2

+2A(1 - A)(j, - x\)(y -

(1.4.8)

2

x\).

2

2

=

2

A t the same t i m e ,

+ ( l - ^(yr-xir

+ iyi-xl) }

= A l(y -x\f 2

+ (y -xl) ]

1

2

!

2

+ (i

+2A(1 - A ) ^ ( y , - x i ) ( y i - x\f 2

+(yi- x i m - x ^ +

+

2

2

+(l-A) [( /i-x ) 2

=

2 2

-x ) ]+

/ 2

+ (y

(1.4.9)

2

2

-

- x ) (y l 2

2

^ - x ^ - x

2

2

2

)

2

x ) + 2

2

] .

A d d i n g u p (1.4.7) a n d (1.4.8) a n d c o m p a r i n g w i t h (1.4.7) we have t h a t i t suffices to prove the i n e q u a l i t y (

y i

-x\)(

y i

-x

2

x

)

+

(y ^x )(y -x )< 2

l 2

2

2

2

Preliminaries

26

< vKfi

-

x\) (y* 2

4) +to2

4) {y* 2

4T+

( - > L4

i0

B y squaring (1.4.10), we get [2(yi -

- x )(y 2

< im - A)\y* - 4)

2

- x\)(y - x\)] <

2

2

+ (to - 4 ) f > - * d a

(!•*•")

a

or, w h i c h is the same, Kift - 4)(y2 - A) - (V2 - 4)(ifi - «SSP > o

(i-4.i2)

However, (1.4.12) is always satisfied i f x ^ x ^ j / . T h u s , we have completed the proof for the convexity of the function p(x, y) i n t, w i t h each y being fixed. B y the c o n d i t i o n , the set S (circle) is also convex. Therefore, we can directly apply T h e o r e m 1, from w h i c h i t follows t h a t the value of the game 1

2

v ~ m i n max/>(x, y).

(1.4.13)

T h e example i n 2 suggests that v = m i n max p(x, y) = R

(1.4.14)

In this case, the point x 6 S, on which the m i n i m u m of expression m a x s p(x,y) is achieved, is unique a n d coincides w i t h t h e center of the circle 5 (i.e., w i t h the point O (see 2)). B y T h e o r e m 5, this point precisely is the o p t i m a l strategy for Player I (minimizer) i n the given case. T h e o r e m 1 states that Player II (maximizer) has a m i x e d o p t i m a l strategy prescribing a positive probability to not more three points i n t h e set S. However, because of the symmetry of the set S, by using the o p t i m a l strategy, the player chooses w i t h probability ( 4 , |) any two d i a m e t r i c a l l y opposite points on the b o u n d a r y o f S. Denote such a strategy for Player II by f " = i I + ^I . T o prove the o p t i m a l i t y of v' i t suffices to establish t h a t for all x , y £ S, s &

yl

y2

}

M{I y) 0t


< M(x,S).

(1.4.15)

Here M is the expectation of the payoff (see 3), I is a pure strategy for P l a y e r I designed to choose a center of the circle S, and j/], y are a r b i t r a r y d i a m e t r i c a l l y opposite points on the b o u n d a r y of the circle 5 , M(7o, v') = \R + ^R = R. Since R is the value of the game, and I an o p t i m a l strategy for P l a y e r I , then the l e f t - h a n d side of (1.4.15) is apparent. N o w , let x be an a r b i t r a r y point from S (Fig.8). T h e n 0

2

0

G a i n e s with convex payoff

function

27

Fig.

M{x,v-)

= -p{x, ) yi

+

8.

-p(x,y )

l

> -2R = R. l

2

T h i s completes the proof of the inequality (1.4.15). Example 9. C o n s i d e r the generalization of the preceding example to the case where the set S is a closed convex set on the plane. In other aspects this game coincides w i t h the one f r o m E x a m p l e 1, Since a l l conditions of T h e o r e m 1 are satisfied, the value of the game v = min max res yes

0(2,

y)

(1.4.16)

and P l a y e r I has an o p t i m a l pure strategy. W e a t t e m p t now to define the q u a n t i t y v and o p t i m a l strategies for the Players I a n d II. W e construct a m i n i m u m sphere Co(R) containing the set 5. L e t 0 be a center of this sphere, and R its radius. W e will show t h a t v = R. Indeed, m a x s p(x, y) > R holds for each x € S, since if x w o u l d be such t h a t m a x „ p(xi,y) = R = R-5,(t) > 0), then there w o u l d be the sphere C (R^) w i t h its center at the point xj and R' as its r a d i u s , containing S. Since R} > R, then the above a s s u m p t i o n contradicts the m i n i m a l i t y of the sphere Co(R). A t the same t i m e , there are points y on which m i n m a x , p(x, y) = p(0,y) is achieved. These are the tangent points of the b o u n d a r y of the sphere Co{R) and of the b o u n d a r y of the set S. T h u s , x

v e

e S

1

XI

i e S

e s

v = m i n m a x ^(a:, y) = R. N o w let /o be P l a y e r I ' s strategy prescribing p r o b a b i l i t y 1 to the choice of the center 0 of the sphere C (R) 0

(evidently, 0 € S).

E m p l o y i n g T h e o r e m 1,

Preliminaries

28

we have that the o p t i m a l strategy for P l a y e r II prescribes positive p r o b a b i l i t y to not more t h a n three points of the set S. It is readily seen t h a t these points must be the tangent points for the sphere C {R) and the b o u n d a r y of the set S. T o define probabilities, under w h i c h the m a x i m i z i n g player chooses the tangent points for the sphere Co(R) and the b o u n d a r y of the set S, we will consider two cases. Case 1. T h e r e exists two tangent points for S and C (R} such that their j o i n i n g chord is a diameter of the circle CQ(R)Case 8. T h e two points given above not exist. Suppose we have a simple Case 1. Denoted by Ai, A d i a m e t r i c a l l y opposite tangent points for Co(R) and S. T h e o p t i m a l strategy for the m a x i m i z e r is the choice of points A\ and A w i t h equal probabilities Denote this strategy for P l a y e r II by ji'. It suffices to show t h a t for all A G S 0

0

2

2

T h e latter is proved as i n (1.4.15). In case 2, there are necessarily such three tangent points A A ,A that the center O of the circle C [R) belongs to a convex hull of these points. W e choose a coordinate system, i n such a way t h a t the center O of the circle CQ(R) is its o r i g i n . In this system, let ( z i . J h ) , (x ,y ), (x , y ) be coordinates for the points A,,A ,Az. T h e n there exist such A , > 6 , £ ? = j A,- = l , i = 1,2,3 that E f - i A^ar; — 0, £ j L ] A;t/, — 0, since any point of the convex p o l y h e d r o n is representable as a convex linear c o m b i n a t i o n of its vertices. lt

2

3

Q

2

2

3

3

2

W e show t h a t one of the points b y v'. C o n s i d e r based on (1.4.5),

a m i x e d o p t i m a l strategy for the m a x i m i z e r is the choice of Ay, A ,A$ with probabilities A i , A A . Denote this strategy the function E(l ,v*) for A e S. It suffices to show t h a t , for a l l A G S. 2

2 l

3

A

E{I ^)>E{l ,u') A

0

= R.

However, the function

•=1

where x, y are coordinates of the point A G S, is s t r i c t l y convex w i t h respect to x,y and is continuously d i f f e r e n t i a t e w i t h respect to x,y, therefore it has a unique point of m i n i m u m that is determined from the c o n d i t i o n

G a m e s with convex payoff

function

29

Fig. 9.

T h i s yields

3 = 0, - * « ) » + ( » - * ) *

0)

-0.

i t j ^ ( x - x , ) + (y 2

y i

y

It can be r e a d i l y seen t h a t the point x = 0,y = 0 is a solution to equations (*), since, s u b s t i t u t i n g x = 0, y = 0 in (*), we o b t a i n A

3

E

T-

3

= E

j ^

r

=

3

Thus, /

0

is a p o i n t of m i n i m u m of the function R=

e"), i.e. for a l l .4 g S

E{h,v-)<E{l ,v-). A

w h i c h was to be shown ( F i g . 9 ) . C o n s i d e r a generalization of the preceding game. L e t P l a y e r I choose not one p o i n t x 6 S, but m points i ' ' , . . . , x ' ' € 5 . F o r m a l l y , the game proceeds as follows. T h e convex compact set S is given on the plane. P l a y e r II chooses 1

m

Preliminaries

30

a point y € S, a n d P l a y e r I a system of m points x ' , . . . , x > € S. Choices are m a d e simultaneously a n d independently of one another. P l a y e r I P s payoff is assumed t o be ] )

1 ^ f ) -

m

E M

1

,m

i

- ! /

,

i

)

+ {4

2

, 1

-^) ] 2

=

here x = ( x ' ' , . . . , x^ '). Player I ' s payoff is equal t o — K. 1

m

In this game a set of strategies for the m i n i m i z i n g player P = [S] is convex and closed as Cartesian product of closed convex sets. T h e function K{x,y) is strictly convex, i n x w i t h every fixed y. Indeed, t h e function w(u) — u is strictly convex. m

2

If t h e function w(u) is s t r i c t l y convex , then t h e function w(u + c) is also strictly convex w i t h any fixed c. If the function t O j f i i ! ) , u ; ( i i 2 ) , • - •, w (u ) are convex, then the function $ ( u i , . . . , u ) = C-ti)j(uj) is also convex. T h u s , we may a p p l y T h e o r e m 1 on the structure of o p t i m a l strategies for players, according to w h i c h the o p t i m a l strategy for Player I is pure, and the m i x e d strategy of Player II concentrates measure at no more t h a n three points of the set S. T h e value of the game is equal t o 2

n

n

n

1 min max — V*a{*'"*,»). *(.) «<«,(€« yes m

v=

W e compute the quantity v a n d find an o p t i m a l pure strategy for P l a y e r I . Denote by S i ( x ' ' ' , . . . , z ' ' } a geometric locus of points y on the plane for which jjj £ jB*(«w, y) = £ = const. W e show that this set is a sphere w i t h its center at the point x = ( i j , z ) , where m

2

2

1

m

x, = ^ £ x ! » , m

1

=

I , 2 ,

; = i

its radius being

(1.4.17) Indeed

Games with convex payoff

11

function

[{*F) - ^ V . +

- 2x[% + y + yj] = ?,

2

2

-T [-2x^y -2x[ y l

i)

l

+ yUy } 2

2

2

=

13

m

m 13

+ 2 m

( i i - yi)

+ (x

2

- y)

2

2

(xi - y , ) . + ( i - y 2 ) 2

2

=

2

a

=

Expression (1.4.17) a n d x, correspond to sample variance and sample means of the quantities x\'\ hence the expression

m a y be represented as •

2 m

Preliminaries

32 E v i d e n t l y , there must be

W i t h the fixed center x , a m a x i m a l radius is o b t a i n e d f r o m the c o n d i t i o n of m i n i m u m for a sample variance, i.e. n n n l f ^ ' - x . f ,

under c o n d i t i o n ^ Y?j=\ x ^ ' = x , , i =

(1.4-18)

1,2.

T h e m i n i m u m i n (1.4.18) is achieved w i t h x - ' = i ; . i.e. to o b t a i n a m a x i m a l r a d i u s , it is necessary to concentrate a l l points X ; at the point £ ; {at the center of the sphere). 3

C o n s i d e r a m i n i m a l sphere containing the set S. L e t XQ = ( x j , x ° ) , R° be a center and radius of this sphere. T h e n , w i t h x,- = x°, x ' ' = x ° , i = 1,2, j = 1 , . . . , m , P = (R ) , the sphere S / ( x , . . . ,a:< )) also coincides w i t h the m i n i m a l sphere containing the set S. Therefore, for any point y € S J

0

( 1 )

2

1

m

*"

- E ^ V ' ,=i

1

, i / ) ^ *

0

)

3

^

(1.4.19)

2

m

(here all x ' ' = x , j = 1 , . . . , m). E v i d e n t l y , there are no points a J $ such that the inequality (1.4.19) is satisfied for a l l y £ S w i t h t < I (since 5 / is the m i n i m a l sphere containing S). J

0

1

T h u s , the o p t i m a l strategy for P l a y e r I is the choice of m i d e n t i c a l points ( i ° ) t ' ) = x°, i = 1 , . . . , m , that belong to S and are centers of the m i n i m a l spheres containing the set S (the point x° being u n i q u e ) , and the o p t i m a l strategies for P l a y e r II prescribe positive probabilities to not more than three tangent points 7/1,3/2,1/3 for the m i n i m a l sphere, c o n t a i n i n g the set S, a n d this set. T h e value of the game is equal to the radius of m i n i m a l sphere c o n t a i n i n g the set 5 .

1.5

One class of games with complete information

Let us consider a class of multistage games w i t h complete which are a c c o r d i n g a generalizations of E x a m p l e 2 from 1. T h e game w i l l take place in the E u c l i d e a n n - d i m e n s i o n a l space R". W e denote P l a y e r I 's position by x g R" a n d t

O n e class of games with complete

33

information

P l a y e r I P s p o s i t i o n by y e RV-. F o r each x € R" y 6 fl" we determine, respectively, the sets U , % w h i c h are assumed to be compact sets of E u c l i d e a n spaces RP • t

x

T h e game starts f r o m positions x , yo- A t the i n i t i a l time instant the Player I and II m a k e a choice of points x , G U „ a n d X i G V . In this case, P l a y e r I P s choice is c o m m u n i c a t e d to P l a y e r I before he chooses points X i G U (i.e. P l a y e r II leads). A t t h e points x\,y\ , the Player I a n d II choose x G V and y G V , a n d P l a y e r I P s choice is communicated to P l a y e r I before he chooses t h e p o i n t x G U , etc. I n position Xk-i,yk-i the players choose x G U ,y G V , a n d P l a y e r I P s choice is communicated to Player I before he chooses the point x G Ukk-> ' ^-he process terminates at the A^-th step by choosing i j v G U _,, yN £ ^ V N - I ^ P o s i n g t o state x ^ , J/JV. T h e families of sets U ,V ,x G R ,y G R are assumed to b e continuous in Hausdorff m e t r i c w i t h respect t o x,y. T h i s means that for any e > 0 there w i l l be such S > 0 t h a t for ||x — x„|| < 6 \\y — y \\ < 6. 0

x

vo

xts

2

2

Zl

V1

X1

2

k

Xki

k

yk

i

k

a n <

XN

x

n

y

n

0

(iy«

D (U ), (U ) D U x

x

t

xa

Here U ,(V ) is t h e e-neighbourhood of the set U(V). W e shall n o t p r o v i d e t h e proof for the following L e m m a , since it is well known in analysis. c

t

L e m m a 7 Let f(x',y') U

x

the

X V. v

be a continuous

If the families

{U },{V } x

y

function

on the Cartesian

are Hausdorff

continuous

product

in X , J / ,

then

functionals F (x,y)

= max m i n

F (x,y)

= min m a x / ( x ' , j / )

l

2

are continuous

v'&J,

in x,y.

f{x',y%

y'£V

r

Let x = ( x , . . . ,xji/) M i d y = (t/o, - • •, VN) be trajectories for the Player I and II realized d u r i n g the game, P l a y e r I P s payoff is the q u a n t i t y 0

max J(x ,y ,k) x

k

k

= F{x,y),

(1.5.1)

where f(x,y,k) is a continuous function of x,y. P l a y e r P s payoff is equal t o — F ( z e r o - s u m t w o - p e r s o n game). A s s u m e t h a t the game is a perfect i n f o r m a t i o n game, i.e. at each t i m e instant (at each step) the players know positions x ,y a n d t i m e instant k. A d d i t i o n a l l y , P l a y e r II choice of y +i is k n o w n to P l a y e r I. k

k

k

Preliminaries

34

Player f's strategies are all possible functions u(x,y,t) such t h a t u(x ,y k

Player IPs strategies are a l l possible functions v(x,y,t)

U. Ik

x

v( k,Vki

k) € V

y i

,k)€

k+l

such t h a t

. These strategies w i l l be called pure strategies (as d i s t i n -

guished from mixed strategies). Suppose the Players I and I I adopt pure strategies u(x,y,t),v(x,y,t).

In

the s i t u a t i o n ( « ( • ) , « ( • ) ) the play proceeds as follows. A t the first step, Player I I passes from the state y

0

to X\ = U(x ,yi,0) choice). x

2

to the state yi = v[x ,yo,0),

A t the second step, the players pass to the states y

2

= u{x\,y-i,

1) = v[x-j v(xi,yt,

1), 1), etc.

t

and I I pass from the states x -\ y ~ k

x

k

and Player I from

o

= u(x -,,y ,kk

x

0

= U(ZQ,v(zj,y>,0),0), (since Player I knows Player IPs

o

1

k

to the states y

l

k

l}

k

= v(xk-i,

k

1) = u{x - v(x - ,yk-uk

k

= v(jti jft, 1), (

A t the i - t h step, the Players I y -i,

k — 1),

k

- l ) , f c - 1 ) , etc.

t

T h u s , each s i t u a t i o n ( « ( • ) , » ( • ) ) uniquely defines the pair of trajectories of the Players I and I I x = (x .... 0>

payoff K(*>(•),*(*)1

— F(i,

x^)

and y = (y ,...,

y^),

0

a n d hence w i t h the

y) determined from t h e f o r m u l a (1.5.1).

T h e games depend on t w o parameters, namely, i n i t i a l positions d u r a t i o n A ' , hence i t is denoted by r(xo,yo,N). each game r(x ,

j/o. N) may be conveniently placed i n t o the family of games

0

r(x,y,T)

and

Xo,yo

T o continue our studies,

that are dependent on parameters

x,y,T.

T h e following theorem, which is a generalization of Zermello theorem for the finite games w i t h complete i n f o r m a t i o n , is v a l i d . T h e o r e m 7 In the game

V{XQ, ya, N)

there is an equilibrium

point

iti pure

strategies. P r o o f : T h e proof w i l l be carried o u t by the i n d u c t i o n m e t h o d w i t h respect r

to the number of steps i n the game A . W i t h N = 0 the theorem is evident. Assume that the theorem holds for a l l N < k and prove its v a l i d i t y for N L e t N < k. Consider the family of the games T{x,y,N)(N

< k).

k.

I n this

game, let u" (-,0>*£„(•, t) be o p t i m a l strategies for the Players I a n d I I , and y

the value of the game r(x,y,N).

v(x,y,N)

T h e function F[x,y,k)

is defined

as follows: F(x,y,k)

= max mir, { m a x [f(x\

y\ 0 ) , V ( x ' , y', k — 1)]} =

= m a x [ / ( z , y , 0 } , m a x rnin V(x\ =

y\ k - 1)] =

(1.5.2)

ms.x\f(x,y,0) V(x,y,k-\)] >

Strategies («*)* , (w*)*^ are defined by the rule y

k

(u-)

= / " r v ( - - 0 , at t> 0, x- e U , y' 6 %, z

'

\

i V(x',y' k~\) >

= mm .Vlx; \k-\)), z

y

t

:

=0

>

O n e class of games with complete

i « ^ u < j - |

S

35

information

)

a

t

t

=

0

W e w i l l show that F ( x , y , f c ) is the value of the game r ( * , y , i ) , aud *) a""! ( * ) l ( " ) o p t i m a l strategies for the players I and II i n this game. B y definition, the payoff K i n the situation (w")'jL('i*)»(*")£*(*,'*) is equal to F(x,y,k). w

v

, f

a r e

N o w let one of the players, say Player II, depart from the strategy (i>")£,„{-,( J, choosing a strategy ( u ) * ( - , t ) instead of i t . T h e n , from (1.5.2) we o b t a i n ' v

> m a x \f(x,y,0),

F(x,y,k)

m i n V(x\y,k-

1)"| .

(1.5.3)

Generally, j / does not coincide here w i t h y from (1.5.2), since the strategy (»)«(•. 0

d i f f e r s

f

r

o

m

t h e

strategy

(»•)*,(.,*),

Let m i n ^ y , ^ ( a ; , j / , i — 1) is achieved at the point x = x(y). game r ( i , j / , f c — 1). L e t K(u,v) be the payoff f u n c t i o n , and o p t i m a l strategies for the P l a y e r I and II i n this game. T h e n V ( i , y , f c - 1) = K&ftti?)

C o n s i d e r the S f c ' the

(1-5.4)

>

for any strategy v * ^ of P l a y e r II i n the (k — l ) - s t a g e game. 1

In (1.5.4), let u j ^ ' be a restriction of the strategy u £ ( - , i ) on a position set i n the game r(x,y,k — 1). T h e n , using (1.5.3), (1.5.4), we may w r i t e the following c h a i n of inequalities: iV

>K({*X„,(v-)* )>

F(x,y,k)

tf

>max[/(x,y,0),K(i,!7,^l)]> >max[/(x,y,0),^ut^Ol =

(1.5.5)

=

*(("'}*,,(<«)•

T h e inequality (1.5.5) is satisfied for a l l strategies (!>)*„. S i m i l a r l y , it may be shown that for a l l ( « ) £ „ F(x,y,k)

=

K((v-)i, ,(vX,)< v

<*(«,.(»*)ijis satisfied. T h u s , F(x,y,k)

is the value of the game r ( x , y , f c ) .

ti-s-6) T h i s proves

T h e o r e m 1. ' U s i n g L e m m a 7 a n d i n d u c t i o n m e t h o d , the continuity of the function V[x,y,k) may be readily proved.

in

x,y

Preliminaries

36

C o r o l l a r y 1. T h e value of the game T ( x , y, k) is a solution of the f u n c t i o n a l equation V(x,y,k) = max[/(x,y,0),max

m i n V(x',y',k-l)]

(1.5.7)

w i t h the i n i t i a l c o n d i t i o n V(x,y,0) = /(x,u,0). N o w consider the game f ( x , y , N) differing f r o m the g a m e r ( x , y , N) in that here P l a y e r 1 is acting as the leader. T h u s , in the game r(x ,y N) at each step k Player II knows, apart from states xt,yk d time k, the state Xfc+i G U choosen by Player I at the instant k. A t each step k P l a y e r I knows Xk,Vk,k only. As in T h e o r e m 1, we may show t h a t the value of the game f { x , J/Q, A ' ) exists and the value function of the game V ( x o , y , N) satisfies the functional equation. 0

0

0

0

0

0t

a r |

tt

0

0

V(x,y,Jfc) = m a x [ / ( x , y , 0 ) , m a x

m i n K f V . y ' , * - 1)]

(1.5.8)

under the i n i t i a l condition V(x,y,0) — /(x,j/,0). C o r o l l a r y 2. Consider the games T'(x , y , N) and t(x ,y ,N) differing from the games r(x ,y , N) and f ( x , j / , N) only i n the form of the payoff function. Assume that i n these games the payoff of P l a y e r II equals the distance between h i m and Player I at the last step of game, i.e. p(x^,y^). T h e proof of T h e o r e m 1 and C o r o l l a r y 1 then holds if instead of f u n c t i o n a l equations (1.5.7), (1.5.8) we consider equations 0

0

0

0

0

0

K ' ( x , y, k) = m a x m i n V ' ( x ' , y\k-\) under the initial c o n d i t i o n V'(x, y,Q) = p{x,y) V'(x,y,k)

0

0

(1.5.7')

and

= n u n max V'(x k iyi

-

I)

(1.5.8')

under the i n i t i a l c o n d i t i o n V'(x,y,0) = p(x,y). Indeed, the above equations are derived directly from (1.5.7), (1.5.8), if we set f(x,y,k) = 0 for k < W and f(x,y,N) = p{x,y). Example 10. Consider a discrete game of pursuit in w h i c h the sets U are the circles w i t h a as a radius and their center at the point x , and the sets V are the circles w i t h 0 as a. radius and their center at the point y(a > 0). T h i s corresponds to the game of pursuit in which P l a y e r II (the evader) moves on the plane at a speed of not more than 0, and Player I (the pursuer) at a speed of not more than o . T h e pursuer's speed exceeds that of the evader , and Player I is second i n t u r n to play. Such type game is the discrete game of " s i m p l e p u r s u i t " w i t h d i s c r i m i n a t i o n for the evader. T h e g a m e d u r a t i o n is N x

y

One class of games with complete

37

information

steps, and P l a y e r 1 Ps payoff equals a distance between the players at the final step. T h i s payoff is a special case of the payoff defined as the m a x i m u m value of some f u n c t i o n along a realized trajectory of the game. Indeed, if /(x^, y , k) — 0 is set for a l l k < N,f{xN,yfj,N) = p(x^, t/w), then the payoff F(x,y) i n the game is defined as k

F(x,y)

=

max f(x y ,k). N

k>

k

W e shall find the value of game and o p t i m a l strategies for the players by solving the equation (1.5.7). Since f{x ,y ,k) = 0 w i t h k < N, we get the equation V(x,y,k) = max m i n V(x\y',k~ 1) (1.5.9) k

k

w i t h the i n i t i a l c o n d i t i o n V(x, y, 0) = p{x, y). Hence we have = m a x m i n p(x',y') y'ev,,x'eLii

V(x,y,l)

Since U a n d V are the circles w i t h centers at x and y, and a and 0 as r a d i i , then if U D V , the function V(x,y, 1) = 0,if, however, U C V then m a x . y ^ m i n ^ e ^ p(x',y') = p(x,y) + 0-a = p(x,y)-(a~0) (see analysis of E x a m p l e 1 i n 2). W e have x

y

x

v

y

x

.. J O, ( >y
V

ii U

i

X

DV , or itV

%$x

Xl

y

v

e

(p(x,y)-(a-0)
y

w

(1.5.10) or, which is the same, V(x,y,\)

= max[0, p(x,y)

0)].

- (a -

Let p(x', y') be a continuous function defined on U X V and c a real number. x

y

Then max m i n [f(x',y')

+ c] = c + max m m

f{x',y').

Using the i n d u c t i o n by a number of steps k, we prove that the following f o r m u l a holds: or, w h i c h is the same, ...

.

V (x, y,K)

v

f0, — y

i{p(x,y)-k(a-0)
j _

k

,

Q

_ ^

i n

t h e

O

pp

0 S

i

t e

c a s e

,

( •• I

otherwise, V{x, y, k) = max[0,/>(x, y) - k{a -

0)].

L e t (1.5.11) be satisfied for k < m. W e prove that it holds for k = m. L e t us employ the (1.5.9). T h i s yields V(x,y,m)

= m a x m i n V(x\y',m

-

1)

Preliminaries

38 or

V(x,y,m)

= max min

0,

if

p{x',y') — (m — \ )(a — 0),

i n t h e opposite case.

Consider the function $(x',y')

j,') - ( m - 1 ) ( « - ^) < 0,

= max[0, p(x', y') -(m

- 1 ) ( « - 0)] for x' £

max m i n {max[0,p(z',i/') - ( m - l ) ( a - /?)]} = = max[0,max rpAn[p(x',y')

~ (m - l){a-

0)}] =

= m a x [ 0 , / > ( * , » ) - ( a - / 9 ) - ( m - l ) ( a - £)] = = max[0, p{x, y) - m(a - 0)}. However, = max nun *(x',J/').

V{x,y,m) i.e. V(x,y,m)

= p(x,y)

- m(a - 0),

which was to be proved. If V(x, y, m) = p(x, y) — m(a — 0), i.e px, y — m(a — 0) > 0, then by using the o p t i m a l strategy, Player II chooses, at each t i m e instance, the intersection point m for the line of centers x,y a n d the b o u n d a r y of V w h i c h is farthest from x. Similarly, by the o p t i m a l strategy, at each time instant Player I chooses from the set U the point which is nearest to the point chosen by P l a y e r II. Moreover, if Player IPs action is o p t i m a l (i.e., he chooses M), then Player I chooses the point m' on the interval xM w h i c h belongs to U a n d is nearest to M. A s . a result, if b o t h players act o p t i m a l l y , the sequences of the chosen points x o , x i , . . . ,xpi, y , y ..., y lie on the same line passing through x ,y (Fig.10). If V(x,y m) = 0, then the o p t i m a l strategy for P l a y e r II is a r b i trary. However, Player I 's strategy is t h e same as i n the previous case u n t i l the players first pass to the states for which m a x y g v , minx-gi/t p(x\y') = 0. B e g i n n i n g w i t h this state, Player I repeats Player I P s choice. y

T

x

0

1}

N

0

a

t

1.6

Simultaneous games of pursuit with n o n convex payoff functions

In this section a solution is given to some simultaneous games of pursuit i n which the payoff function and the strategy sets for players are n o n - c o n v e x . T h e

Simultaneous

games of p u r s u i t with non-convex

payoff

functions

39

Fig. U . results o b t a i n e d i n 4 are not applicable to such games, therefore a solution for b o t h players belongs to the class of m i x e d strategies. T h e existence of solution in this class follows f r o m T h e o r e m 3. Example 11 {simultaneous game of p u r s u i t i n a ring). T h i s game is a special case of the game f r o m E x a m p l e 1 where the sets S\ — S3 = S and S a ring. T h e r a d i i of outer and inner circles of the ring S are denoted respectively by R and r ( F i g . l l ) . W e w i l l show t h a t the o p t i m a l strategies for the Players I and II are a choice of the points w i t h u n i f o r m d i s t r b u t i o n on the inner (for P l a y e r I) and the outer (for P l a y e r II) circles of the r i n g S. Denote these strategies by fi* (for P l a y e r I) a n d V* (for P l a y e r II). F o r the above strategies the mean value of the payoff (distance) is equal to M O * ' , p*) -

= —

yjR? + r

[**£"

j' 2

2K JO

JR? V

+

V

2

-

3

- 2Rr cos{<^ - ip)dipdj> =

2 R r cos fd£ = * ( r , R),

Preliminaries

40

where y a n d ip are vectorial (polar) angles of pure strategies for the Players I a n d I I , respectively. If P l a y e r II chooses t h e point y w i t h polar coordinates tp,ip then the expected distance (Player I plays the strategy ft*) equals M(p\y)

= *{r,<£) = ^

fj

y/r + p 2

2

- 2pr cos £df.

It is readily seen that for r < p < R the function
Now consider the s i t u a t i o n (x,v~)

i n w h i c h x € S.

2

T h e n t h e expected

distance equals M{x,u-)

= $(p,R)=

^-

+ P ~2Rp cos {dt;.

JR

2

2

B y a p p l y i n g the L e i b n i t z rule, one may see that M

=

, « M

0

dp

>

(

, , < , <

t

op

1

F r o m this i t follows that $(/), R) increases monotonically i n p, hence $ ( r , R) < 4>(p, R) and we have M{x,v')>M{p.',v-)>M{p.\y) for a l l x,y G S . W e have thus proved the o p t i m a l i t y of strategies (see Theorem 3). T h u s , the value of the game is equal to the integral: M{p\v-)=~

r Zir Jo

JR

2

+ r * - 2Rr cos ^

= * { r , R).

If S is the circle w i t h he radius R (r — R), then the value of t h e game equals ^R. Example 12. Consider a simultaneous z e r o - s u m game of p u r s u i t between the detail of pursuers P = {Pi,P } ( P l a y e r I) a n d the evader E ( P l a y e r II). Player P = {Pi,P } chooses a point x — (x ,x ), x 6 S, x £ S, a n d Player E, w h o does not know Player P's choice (simultaneously w i t h h i m ) , chooses the point y S S. Player E's payoff is set to be equal m i n ^ i ^ p{xi, y). T h u s , Player E aims to m a x i m i z e the distance between himself and D e t a i l P ( m a x i m i z a t i o n of a m i n i m u m distance to one of the detail partners). P l a y e r 2

2

t

2

x

2

P pursues the opposite object. W e shall provide a solution for b o t h players. Case A. T h e set S is the interval c — [—1,+lJ. W e show t h a t mixed o p t i m a l strategies are: for Player P the choice of points ( — 1 , 1 / 3 ) , ( — 1 / 3 , 1 )

S i m u i t a n e o u s games of pursuit

with non-convex

41

payoff functions

w i t h equal p r o b a b i l i t i e s , and for Player E the choice of points - 1 , 0 , 1 w i t h equal probabilities. T h e value of the game is equal to 1/3.

also

T h e m i x e d strategies are denote by p," and v~, respectively. Let Player E play the strategy c", and P l a y e r P chooses an a r b i t r a r y pure strategy x = ( i i . z j ) . W e may always assume t h a t xi < x j . T h e s i t u a t i o n (x,e*) corresponds to the payoff A f ( * , 0 = \(i + *,) + ^(1 - x ) + i m i n d x . U x , ! ) .

(1.6.1)

a

E v i d e n t l y , if xi < x

2

< 0, then

• i// M 2 + x, - 2 x mm M(x,e ) = mm

2

1 = -

(1.6.2)

is achieved w i t h xi = — 1 , x = 0. If 0 < xi < x j , then 2

- XMt -\ • 2 + 2x - x min M ( x , v ) = mm * l|A | t

a

1 = 3

(1.6.3)

is achieved w i t h X] = 0, X j = 1. C o n s i d e r the case X i < 0 < x . C l e a r l y , 2

min(x, v*\ sa minx, ^ min Y* a

r j

2J

L

= 5 = |

with - x i > x with - x i < x

2

2

and is achived w i t h xi = - 1 , and is achived w i t h x = 1.

n 6 4)

2

In p a r t i c u l a r , w i t h x i = - 1 , x = 1/3 and w i t h xi = - 1 / 3 , x = 1 the payoff of P l a y e r E equals 1/3. T h u s , E q . ( 1 . 6 . 1 ) - E q . ( 1 . 6 . 4 ) are satisfied for any pure strategy x = ( x x ) . Player E receives the payoff M(x,i/') > 1/3. N o w let P l a y e r P play the strategy u * , and Player E an a r b i t r a r y pure strategy j £ c 2

2

1 (

2

A s s u m e t h a t y > 0. C o n s i d e r two possibbties: 0 < y < 1/3 and 1/3 < y < 1. In the first case P l a y e r E receives the payoff

*-

K 5 - ' H ( i

in the second

+

0 4

. M(p.;y)

= ^ - y )

+ 2 { y - i )

( I 6

'

5 )

. =

y

< '> L6

6

In view of the s y m m e t r y for y < 0, the payoff of P l a y e r E turns out to be 1/3. C o n s e q u e n t l y , p l a y i n g any pure strategy, P l a y e r E cannot a payoff below 1/3.

Preliminaries

42

F r o m (1.6.5) and (1.6.6) we may conclude t h a t M(p',v") = 1/3. Case B. S is a circle w i t h radius r, its center being at the o r i g i n of coordinates. In what follows, we denote by D (S ) a circle circumference of the circle w i t h radius r, its center being at the o r i g i n of coordinates. r

T

Consider the function $(r,/>) = r

+ p - i r r o , 0 < r, p < R.

2

2

L e m m a 8 The function ®{r,p). (as a function of the variable r) is strictly convex and achieves the absolute minimum at a unique point r = 2R/x. 0

P r o o f : W e have "

f

c

d

.

^

i

.

.

,

*

(

1

, „

Consequently, the function $ ( r , p) r 6 [OR], is s t r i c t l y convex, and the derivat

tive Or

=

2

r - —

1.6.8

IT

is strictly monotone. E v i d e n t l y , the function (1.6.8) vanishes at a unique point r = 2R/ir, Because of the strict convexity of the function $(r ,R) (1.6.7), the point r is a unique point of absolute m i n i m u m . T h i s proves the lemma. 0

0

0

L e m m a 9 The function 4>(r, p) is strictly maximum at the point p — R.

convex in p and achieved

absolute

0

P r o o f : Because of the s y m m e t r i c entry of variables r and p into the function $(r,p),

the strict convexity of §{r,p)

follows from L e m m a 8.

W e have $ ( r , R) - * ( r , 0 ) = r + R - -r R it 0

2 0

0

2

- r

2

0

=

_ * _ i » a _ » ^ _ „ » , . We have thus proved the l e m m a completely.

•

Remark. L e m m a s 8 a n d 9 suggest that the point ( r , R) is the saddle point of the function $(r,p). Indeed, * ( r , p ) < * ( r , R) < * ( r , P ) . 0

0

0

T h e o r e m 8 Mixed optimal strategies are: for Player P the choice of Xi with uniform destribution on S , x = —x , for Player E the choice of y with uniform destribution on S . The value of the game is equal to $>(r , R). ra

2

2

t

0

S i m u l t a n e o u s games of pursuit

with non-convex

Fig.

payoff

functions

43

12.

P r o o f : D e n o t e the stated strategies by

ii*,i>".

Let P l a y e r E adopt the strategy u", and Player P an a r b i t r a r y pure strategy x = x,- = ( r i c o s y > i , r i s i n ^ , ) , i = 1,2.

(&iy%);

C o n s i d e r the case x = x%. Denote by r a number n — r , and by

2

2

f - ) = ^ - ! "[R 2ir Jo

M(x,

2

= R + r 2

+ r

2

> R + r

2

2

2

- 2Rr cos(0 - tfi)]dip =

2

- ^-Rr = * ( r , R).

(1.6.9)

Consequently, when a d o p t i n g a pure strategy x = ( x j , x ) , X i — x , Player £ receives the payoff A / ( x , f " ) > $(r, R) > $(r , R) (see L e m m a 8). In what follows, we assume t h a t x\ ^ x . 2

2

0

2

O n the p l a n e R , we introduce a polar system of coordinates. As the origin of coordinates, we take the point O, and as the polar axis the ray starting from the point 0 n o r m a l to the chord AB the set of the points of the circle D that are equidistant f r o m x\ a n d x (Fig.12). 2

r

2

For s i m p l i c i t y of notations, we propose that w i t h respect to a new system of coordinates, the point Xj has the same coordinates (r,- cos tpi,rjSin tpj) i = 1,2. P l a y e r E ' s payoff is equal to l

Mix,

e*) = ^ - / ' " m i n ^ 2TT JO

= ~ LlT

f

'

[R J - 0

2

2

+ r - 2 f l r , cos(i& - y 2

+ r\ - 2Rr

2

COS(T>

-

{

W

=

Preliminaries

44

Let = -[{R +

f i M

4)0-2Rr

2

f (v>) = - P

+ r ) ( i r - /?) + 2 f l r , sin^cos
2

a

sin 0 cos p],

2

3

TT

0<
- 0.

T h e stationary points of functions F i a n d f a are, respectively, 0 a n d JT, for 0 < 0 < TT/2 a n d F/(y>) = 2Rr

sin^sin

2

f^(v») = -2Rrj

sin / ? s i n tp,

0 a n d JT are the points of absolute m i n i m u m of the functions Wj (
< 0 for tp e ( - 1 , 0 ) , F , ' ( y ) > 0 for

G (0, T ) a n d

S i m i l a r l y , F&ip) < 0 for

^(^)>0for^G(7r,27T-^)).

Consequently, M(x,v')

= F( ) l

1 —

> F,(0) + I5£r) =

- F( )

Vl

2

V2

/ (R + r | - 2 f l r cos <^)d0+ 2

+—

/

2

(i? +r + 2^1003^)^ 2

(1.6.10)

2

i.e. using the strategy x i = (-r 0), x = ( r 0 ) P l a y e r P receives a larger payoff than using the strategy x,- = (r; cos i^>,, r,- s i n ^>). u

2

2 l

N o w let X i a n d x lie o n the diameter of the circle D , the distance between t h e m being 2 r , a n d the chord A B (for t h i s case) forms t h e central angle 2 a . Assume that x = (Rcosa — r,Q), x = (Rcosct + r , 0 ) . P l a y e r £ ' s payoff is equal t o 2

r

x

2

*(<*,r) = — £TT

\ +

*"h f

J

Rcosa

- r) + R s i n 2

1

2

yj]dyj+

—a

r2r-a

2^ J

1 ! ~ o~ /

I" \(R cos yj-

[{Rwsi>-Rcosa+

r) + R sin ip}dyj = 2

2

2

a

[K ~ ZRws'KRcosa 2

c

'i R2

2Rcos

^(

Rcosa

-) r

+ r) + (Rcosa

+(

+

-)w

ficosa

r

2

r) }dyj+ 2

=

Simultaneous

games of pursuit = ^{[R + [R

2

with non-convex

+ (Rcos a + r) ]a 2

- 2 f t s i n a(Rcos

a +

+ ( f l c o s a - r) ](7r - a) + 2Rsma(Rcos 2

2

45

payoff functions r)+

a -

r)}.

W e show that the f u n c t i o n r) for a fixed r w i t h respect to a a achieves m i n i m u m when a = x / 2 . P e r f o r m i n g elementary c o m p u t a t i o n s , we obtain 3* 2 T T — = - f l s i n a\(n — 2a)r — x f t c o s a l , da IT " ' ' therefore for sufficiently small a j°' < 0, because s i n a > 0, r(w - 2a) x/E COS a < 0 (in the l i m i t i n g case r x - x i i = x ( r - R) < 0, r < R). A t the same t i m e , 2*fcZ3£l = -R • 0 = 0. 3 l t

r >

2

W i t h each f i x e d r , the f u n c t i o n ^ j " ' ^ has no zeros i n a exept for a = x / 2 . Suppose the opposite is true. L e t Q i € ( 0 , x / 2 ) be a zero of the function —j?^. T h e n , for a = en, the function G(a) = (x — 2a)r — uRcosa also equals to zero. T h u s , ( ? ( « , ) = G ( x / 2 ) = 0. E v i d e n t l y , G ( a ) , as the difference of a linear f u n c t i o n (x — 2 o ) r a n d the function irftcosa, has no zeros: G(a) > 0 for a (E ( t * i , x / 2 ) . W e compute its dervatives: G'{a) = - 2 r + x f l s i n a ,

= xtfcoso > 0

G"(a)

i.e. the f u n c t i o n G ( a ) is convex. Since G(a)

> 0, a € ( c t i , x / 2 ) , this contra-

dicts the above inequality. T h u s , the f u n c t i o n *j£' ^ < 0 for a € ( o i , x / 2 ) and d

3 l t ,

^ ' ^ 2

r

=

r

0- Consequently, the function *(or, r ) w i t h respect to c* achieves

absolute m i n i m u m for a = x / 2 : *(o,r) > *(x/2,r). T h i s means that i n this case the payoff of P l a y e r E = * ( a , r ) > * ( x / 2 , r ) > {r,R) > * ( r „ , f l ) .

M(x,v-)

(1.6.11)

Based on (1.6.9)—(1.6.11), it turns out that for any pure strategy x = ( a : j , i ) Player E has the payoff M{x,v-) > *(r ,ft). (1.6.12) 2

0

Suppose P l a y e r P adopts the strategy p", a n d Player E an a r b i t r a r y pure strategy y — (p cos i>, p sin t/>). T h e n P l a y e r £ obtains the payoff A/(u*,!/) = - L f 2 x Jo = _L 2 x Jo

m

\ (p a

min[p

+ rl-2pr cos(i!-
2

2

a

+ r 2

2pr c o s £ , p 0

2

+ rl + 2pr cos(i>-
2

0

+ r + 2 ? r cos£)d£ = a

0

*(r ,/)), 0

=

Preliminaries a n d , because of L e m m a 9, M(x,v*)

(1-6-13)

= <S>(r ,p)<$(r ,R), 0

a

Inequalities (1.6.12) and (1.6.13) i m p l y t h a t a and v are mixed o p t i m a l strategies respectively for the Player P a n d E, and $ ( r , R) ' the value of the game. T h i s proves theorem completely. • 0

s

Example 13. Consider a generalization of the previous game i n this case where p u r s u i t is carried out by a pursuer detail i n v o l v i n g m p a r t i c i p a n t s . N o w , suppose that a simultaneous z e r o - s u m game between the pursuer d e t a i l P = {P, P } (Player I) a n d the evader E ( P l a y e r II) is given. P l a y e r P = { P i , . . . , P } chooses the point x = (x ...,x ), r , E S, i = 1 , . . . , m and Player E, without any knowledge of Player P ' s choice (simultaneously with h i m ) , chooses the point y £ S. T h e payoff of P l a y e r E is assumed to be equal min, , p{xi,y). m

lt

m

6 {

m

m ]

T h u s , as in the previous case, Player E aims to m a x i m i z e the distance between himself and the detail ( m a x i m i z a t i o n of a m i n i m u m distance from one of the partners of the detail P ) . P l a y e r P pursues the opposite object. W e shall give a solution for the case where the set 5 coincides with the interval [—1,+1]. A t present, the solution of the game in the general case is unknown. T h e o r e m 9 The mixed optimal strategy for Player E is the choice of the points 2m - 3

2 m - 2i - 1

' " 2 m - 1'"''

2m - 1

1

1

1

2m-V''''~2^n~^'2m~^\'''''

'

with probabilities 1 / 2 m . The optimal strategy for Player able choice of two sets of m points 2m - 5 '

1

2m - 1 " " '

2m -

2m-3

3

1

2m - 1 *

2m-3

V 2m - 1 ' " ' " ' 2m -

3

2 m - 1"'"

P is the the

2m - 5

2m - 1 ' " " ' 2m -

The value of the game is equal to l/(2m

— 1).

P r o o f : Introduce the following n o t a t i o n : - \ ~

2 m

~ ' + 2m - 1 4

3

'

2 m - 4 ( i - 1) + 1" 2m - 1

1'

V

equiprob-

Simult. L.J- . J j.-. games of pursuit

with non-convex

payoff

functions

47

\2m - 4 i + 1 2 m - 4 t + 31 '

2m-l

2m -

W e show that M(F\y) < I / { 2 m - l ) for a l l y £ [ - 1 , 1 ] , where F is a strategy of P l a y e r P. Indeed, for y £ £ 2 m - 4i: + 3

M(F-,y)= -mv l

+ imio

2m - 1

2 m - 4i + 1

- V

2 m - 1

+

-y

2m - 1

A similar equality is derived for y € W e now prove t h e i n e q u a h t y x ;G")

>

m

1 2m - 1

where G' is a strategy of Player E. We restrict ourselves to the cases when the points Xi are l y i n g o n the interval (in the remaining cases the proof is s i m i l a r ) : 1. n €ti,i= 2. n £ii,

1,2,...,m; 1 , 2 , . . . , * - l,fc + l , . . . , m , x e e „

i=

k?p.

k

In the first case, 2m - 4i + 1

<

2m - 1

2m - 4i + 3

<

-

X

-

i

2 m - 1

M{x xi,...,x ;G') u

_1_ ' ™ / 2 m - 4 j + 3 2m

=

m

\

A

/

1

2m-4i + l\

2 m - l -'V+gfo-

g(

'

2 m - l J

=

2m- 1

T h e second case means that t w o points Xi fall on one of the intervals a n d we have * * ( « , , . . . , * , ;
2m

_

/2m-4j+3

£

l~2m^l

'2m - 4p + 3 + mninn (I -— ; — 2 m - ] + n ui n (x

=

^ X j

J

+

j

£ . ( '

2 m - 4 j + 3^

f J

-

2m. - 4p 4p + 3 3

\ + 2m = 1 *J 2 _4p + l 2m-4p+r ,xt 2- m - 1: — ) + 2 m - 1 x

T

m

p

m -1 22m

2m-4£+_3 2 m - 1

i

+

2 m - Ak + 1 2 m - 1

>

J

+

48

Preliminaries 1 -

/

2m

4

2 m \2m - 1 ~ 2 m - 1

4

n _

1

2m - 1 / ~ 2m -

+

T h e latter inequalities show the o p t i m a l i t y of strategies F',

1" G* and prove the

theorem.

•

Example 14- T w o players - the p u r s u i n g detail P = { P i , . . . , P } and the evading detail E = {Ei,... ,E„] - choose the systems of points x = m

(pi,-.-: • ,x ), x; £ [ - 1 , 1 ] , i = 1 , . . . , m , and y = ( » i y ), & e [ - 1 , 1 ] , j = 1 , . . . , n , respectively. T h e choice is made simultaneously and independently, i.e., i n m a k i n g his choice, P has no information about the choice of E a n d vice versa. Player E's payoff is assumed to equal m

m

-(max min I i i

— u,-J + m a x m i n i »

\xi

—

yA).

T h e game is z e r o - s u m . W e w i l l prove the following simple theorem. T h e o r e m 10 The optimal strategy for each partner of ike detail P , € P, i = 1 , 2 , . . . , m , is the choice of the point {0} with probability 1 (strategy F*), and the optimal strategy for the detail E = {£,-,..., E} - is the choice of the points — 1, + J with equal probabilities and subsequent concentration of the entire detail E tkere in (strategy G'). The value of the game equals 1. n

P r o o f : Suppose Player E chooses a strategy G', and P l a y e r P an arbitrary pure strategy x = (x ,...,x ). For the purposes of defmiteness, assume that x\ < x < ... < x . T h e n l

2

m

m

= - ( m i n | - 1 - Xi\ + m a x | - 1 - xA

M{x,G")

+ - ^ m i n |1 - x;\ + m a x |1 T ( | l + a : i | + |1

Xi\j

+

+

+ |1 - n | + |1 - x | ) m

= 1.

Suppose now Player P choses the strategy F * , and P l a y e r E the a r b i t r a r y pure strategy y = ( t / , , . . . , y ), j / , < y < ... < y . T h e n n

M{F\y)

2

n

= ^ m a x l ^ l + m i n l j / j l ^ < 1.

T h u s , the strategies P " , G " are a c t u a l l y o p t i m a l , and the value of the game is equal to 1. B

Chapter 2 Definition of differential game of pursuit and existence theorem of equilibrium points 2.1

Nonformal description

Differential games of p u r s u i t are a n extension of the multistage games of p u r suit discussed i n C h . 1, to the case where the number of steps i n the game becomes infinite (continuum) a n d the players have an o p p o r t u n i t y to make decisions continuously. Therefore, such formulation n a t u r a l l y suggests that the players' trajectories represent solution of the system of differential equations, the r i g h t - h a n d sides o f which depend on the parameters under the players' control. L e t x e R , y G R", u G U C R , v G V C fi*. f(x,u),g(y v) be the nd i m e n s i o n a l vector functions given on R X U, R™ x V respectively. C o n s i d e r two systems of o r d i n a r y differential equations n

1

t

n

*-/(*,»),

(2-1.1)

y=g(y,v)

(2.1.2)

w i t h t h e i n i t i a l conditions x ,y . P l a y e r P[E) starts the m o t i o n from the point (position) x ,y and moves i n the phase space R", choosing at each instant a value of the parameter u G U, (u G V) i n accordance w i t h his objectives a n d i n f o r m a t i o n accessible i n each current state. 0

0

0

0

T h e most r e a d i l y describable is the complete information case. In the differential g a m e this means t h a t t h e phase states x(t),y(t) are k n o w n to the players at each time instant ( when t h e parameters u G U,v G V. are chosen. S o m e t i m e s , at each current instant (, one of the players, say, Player P •19

Definition o f differential

50

game of

pursuit

requires a d d i t i o n a l i n f o r m a t i o n about the value of the parameter v £ V chosen by Player E at the same instant. In such a s i t u a t i o n , P l a y e r E is said to be d i s c r i m i n a t e d , and the game itself is called the game w i t h d i s c r i m i n a t i o n for Player E. T h i s definition of complete information suggests an analogy w i t h the multistage games of pursuit w i t h complete i n f o r m a t i o n from C h . 1. T h e parameters tt £ U,v £ V are called the controls for £ , respectively. Let the motions x ( ( ) , j / ( t ) , 0 ( 0 ) = x ,y(0) T h e trajectory x{t) (y(t)) is called the motion trajectory of T h e Players' objectives i n the game are determined w i t h the that is dependent on the realized trajectories x(f) (y(t)). game is assumed to have a prescribed d u r a t i o n T. o

the P l a y e r P and = y ) be realized. the P l a y e r P (E). help of the payoff, In some cases the 0

L e t x(T),y(T) be phase states for the Players P and E at m o m e n t of the t e r m i n a t i o n of the game T. T h e payoff of P l a y e r E is then assumed to be equal M{x(T),y(T)), where M{x,y) is a continuous function given on W x R , In a special case, when n

M(x(T),y(T))

(2.1.3)

= p(x(T), y(T))

where p(x(T),y(T)) = \jT."=\{ i{ ) ~ 3 / - ( ) ) the E u c l i d e a n distance between the points x(T),y{T), the game describes the process of p u r s u i t , in which Player E is a i m i n g to recede from P l a y e r P by the game termination instant for a m a x i m u m distance. In a l l cases, the game is assumed to be zeros u m , i.e. the payoff of Player P is equal to — M(x(T),y{T}). If condition (2.1.3) is satisfied, then Player P is a i m i n g to ensure a m a x i m u m approach to Player E by the game t e r m i n a t i o n instant T. x

r

T

!

i s

T h e payoff thus defined depends only o n the finite position of the players and the player, say Player P , scores the results he has obtained by the game termination instant T. Therefore, quite reasonable is the p r o b l e m formulation where Player E ' s payoff is defined as the m i n i m u m distance between the players existing i n the process of the game ^ K K ' M O )

(2.i-4)

Sometimes a l i m i t a t i o n on the game d u r a t i o n is not essential, and the game proceeds u n t i l the Players P a n d E arrive at a p a r t i c u l a r result. Let the m - d i m e n s i o n a l surface S be given in R tn = min{(t : (x(t),y{t))

2n

and called t e r m i n a l . Set

€ S]

i.e. i n ' the first instant for the point x(t),y(t) to fall on S. If for a l l the ( > 0 the point x(t),y(t) & S then t is assumed to be equal +oo. W i t h the s

u

N on formal

description

51

trajectories of x(t), y(t) r e a l i z e d , the payoff of P l a y e r E is assumed to be equal tn ( P l a y e r P ' s payoff is e q u a l to - ( „ ) . If S is a sphere w i t h r a d i u s £ > 0.

X > , 1=1

- y,)

2

= t.

then we are dealing w i t h the p r o b l e m of p u r s u i t , i n which P l a y e r P is a i m i n g to ensure the fastest approach to Player E for a distance £ > 0. If £ = 0, then by the c a p t u r e is meant a coincidence of phase coordinates for the Players P and E. P l a y e r E seeks to delay the capture instant. Such type of games of pursuit are called the response games of p u r s u i t (or the t i m e o p t i m a l games of p u r s u i t ) . A t t i m e s , it is essential to define the set of i n i t i a l states for the Players P and E, f r o m w h i c h Player P can ensure the capture of P l a y e r E for a distance i? (£ - c a p t u r e ) a n d the set of i n i t i a l states, from which Player E can ensure t h a t such a c a p t u r e does not take place for the distance £ (^-capture) i n a finite t i m e . T h e first set is called the capture zone ( C , Z ) , and the second the escape zone (E, Z). E v i d e n t l y , these zones do not meet. However, of i m p o r t a n c e is the question whether the closure of the u n i o n for the capture and escape zones covers the entire phase space. A l t h o u g h this issue will be addressed i n w h a t follows, we now note that for adequate description of the process it suffices to define the payoff as follows. Suppose there is i n 1? co (see (2.1.4)). T h e n the Payoff of Player E is assumed to be — 1 . If, however, i n = oo then his payoff is assumed to be +1 (Player P ' s payoff is assumed to be equal Player E's payoff w i t h opposite sign). T h e games of p u r s u i t w i t h such a payoff are called the p u r s u i t - t y p e games of degree. P h a s e constraints. If we require a d d i t i o n a l l y that d u r i n g the game the point {x,y) w o u l d not leave a set S € fl , then we have the phase-constrained differential game of p u r s u i t . A special case of such a game is the " L i f e - l i n e " game. 2n

T h e " l i f e - l i n e " game is the z e r o - s u m two-person game of k i n d , i n which the payoff of P l a y e r E is assumed to be + 1 , i f he succeeds i n reaching the b o u n d a r y of the set S ( " l i f e - l i n e " ) before he has been c a p t u r e d by Player P . T h u s , the a i m of P l a y e r E is to reach the b o u n d a r y of the set S prior to his rendezvous w i t h P l a y e r P (i.e. before he has been approached by P l a y e r P for a distance £,£ > 0). T h e a i m of P l a y e r P, however, is to approach Player E for the distance £ w h i l e the latter is i n the set S. It is assumed that P l a y e r P cannot a b a n d o n the set S. Example I (simple m o t i o n ) . T h e game takes place on the plane. T h e motion of the Players P and E is described by a system of differential equations

Definition

52

x x

2

t

«j

+

2

<

a

2

+ t> <0\a>0

2

pursuit

«*t,

$1 =

J/i=^,u

game of

= Uj,

2

u-2 u

—

of differential

(2.1.5)

2

Physically, the i m p l i c a t i o n of equations (2.1.5) is t h a t the P l a y e r P and E are m o v i n g i n the plane at l i m i t e d velocities, the m a x i m u m velocities a and 0 being constant in value, and the velocity of P l a y e r E does not exceed that of P l a y e r P. B y choosing at each t i m e instant a control u = (ui,u ) constrained by + u j < a (the set U ), the player can change the velocity direction ( the direction of the velocity vector). Similarly, by choosing at each t i m e instant a control v = (vi,v ) constrained by v + v\ < 0 (the set V ) , P l a y e r E can also change the velocity direction at each time instant. E v i d e n t l y , if a > 0, then the capture zone {CZ) coincides w i t h the entire space, i.e. P l a y e r P can always ensure the capture of Player E for any distance £. T o this end, it suffices to choose the motion at the m a x i m u m velocity a and to direct the velocity vector at each time instant ( towards the pursued point y(t), i.e. to carry out pursuit along the pursuit line. 2

2

2

2

2

If a < 0 then the set (EZ) coincides w i t h the entire space of the game less the points (x,y), for which p(x,y) < £ Indeed, if at the i n i t i a l instant Po(xa>yo) > £, then Player E can always ensure capture avoidance by receding from Player P along the straight line j o i n i n g the s t a r t i n g p o s i t i o n x , i / o and the m a x i m u m velocity 0. }

0

A remarkable fact established here, will be encountered on w h a t follows. To form the control ensuring capture avoidance for P l a y e r £ , it suffices to know only the i n i t i a l states, while i n the case a > 0, to form the control ensuring capture of a player E, Player P needs information o n his own and the opponent's state at each current t i m e instant. Example 2. T h e Players P and E are the m a t e r i a l points w i t h unit masses m o v i n g on the plane under the action of the m o d u l u s - c o n s t r a i n e d and the frictional forces. T h e motion equations are of the f o r m x x x

3

= Ui - k x , P

3

x

4

t

= z ,

2

= i

3

= u 2

4

, kx, P

V\ = !/3, h

=

yn,

4

u + u\ < 2

a, 2

(2.1.6)

G a m e of pursuit

in normal

form

53

h = v - k y ,v\ x

E

3

+ vl <0 , 2

V« = «a — *E2/4

where ( x i , ^ ) , ( 3 / 1 , 3 / 2 ) are geometric coordinates, and (x , i ) , (t/ , y ) .... are, respectively, the moments of the points P a n d E,k and fcg the friction coefficients, or a n d 0 the m a x i m u m forces applicable to the m a t e r i a l points P and E. T h e m o t i o n starts f r o m the states ar,-(0) = x°,3/,{0) = 3 / ? , i = 1 , 2 , 3 , 4 Here, by the state is meant the m o m e n t u m and coordinate space of the Players P and E rather t h a n their geometric position. T h e sets I / , V are the spheres 3

4

3

4

p

U = [u= ( t n . u a j i u j + uj <<* }, 2

V = {v = (v ,v ):v 1

2

2

+ vt<0*}

T h e i m p l i c a t i o n here is that the Players P and E may choose the direction of a p p l i e d forces at each time i n s t a n t . However, the m a x i m u m values of these forces are restricted by the constants a and 0. In this f o r m u l a t i o n , as shown below, the c o n d i t i o n a > 0 (power superiority) is inadequate for P l a y e r P to complete the game.

2.2

Game of pursuit in normal form

In 1 we d i d not provide the m e t h o d of choosing the controls u G U, v £ V by the Players P a n d E d u r i n g the game according to the i n c o m i n g i n f o r m a t i o n . In other words, we gave no definition for the concept of strategy i n the differential game. T h i s concept may be defined by employing different approaches. W e focus only o n the i n t u i t i v e l y evident game - theoretical properties to be possessed by the concept. A s noted i n C h . I , the strategy must describe the player's behavior i n a l l i n f o r m a t i o n states, i n w h i c h he may be d u r i n g the game. In the game w i t h the prescribed d u r a t i o n T, the information state of each player is determined by the phase vectors of the states x(t),y(t) at the current instant 1 and by the t i m e i f r o m the start of the game. Therefore, it would be n a t u r a l t o consider the strategy of P l a y e r P(E) as a function u(x, y, t)(v(x, y, t)) w i t h values i n the control set U (V). T h a t is how the strategy is defined i n [1]. Such type strategies are called synthesizing. However, this m e t h o d of defining a strategy suffers f r o m some grave disadvantages. Indeed, let the Players P a n d E choose the strategies afar, y, t), v(x, y, t). T h e n t o determine the players' motion strategy a n d , consequently, the payoff ( w h i c h is t r a j e c t o r y - d e p e n d e n t ) , we s u b s t i t u t e functions u{x, y, t), v(x, y, (), instead of control parameters u, v, into (2.1.1), (2.1.2), and integrate t h e m

Definition o f differential

54

on the time interval [0,7'] under the i n i t i a l conditions x y 0i

0

game of

pursuit

T h u s we get the

following system of o r d i n a r y differential equations: x y =

f(x,u{x,y,t)),

(2.2.1)

9(y,v(x,y,t)).

For the existence and uniqueness of a solution to the system (2.2.1) it is essential that some conditions be imposed on the functions f{x,u),g(y,v) and the strategies u{x, y, t), v(x, y, t). T h e first group of conditions (for f(x, u ) , 9{Vi")) places no l i m i t a t i o n s on the strategical capabilities of players, refers to the p r o b l e m statement a n d are justified by the physical nature of the process involved. T h e case is different w i t h the constraints on the class of functions (strategies) u ( x , y, (), i>(x, y, t). S u c h constraints for the players' capabilities are inconsistent w i t h the notions (adopted in the game theory) above the players' freedom to choose a behavior, a n d , i n some cases, lead to s u b s t a n t i a l impoverishment of the strategy sets. For example, if we restrict ourselves only to the continuous functions. u ( x , y,t),v{x,y,t), then the problems are encountered where there are no solutions i n the class of continuous functions. T h e assumption of a wider strategic spaces makes it impossible to ensure the existence of a unique solution to the system (2.2.1) on the interval [0,T]. A t times, to overcome this difficulty, one considers the sets of strategies u(x, y, t), u ( x , y,t), for which the system (2.2.1) has a unique solution that is capable of continuation on the interval [0, T). A s i d e from the n on const m e t iven ess of definition for the strategy sets, such on approach is not adequately s u b s t a n t i a t e d , since the set of a l l strategy points u(x y,t),v(x,y,t), for which the system (2.2.1) has a unique s o l u t i o n , proves to be nonrectangular. T h e latter circumstance, as shown below, leads to transformation of the e q u i l i b r i u m point concept m a k i n g it game—theoretically meaningless. l

A n o t h e r approach, proposed by N . N . K r a s o v s k y [10,12], enables the players to make on ambiguous choice of controls i n each i n f o r m a t i o n state. In this monograph we choose piecewise o p e n - l o o p strategies as strategies in the differential game. T h e piecewise o p e n - l o o p strategy u(-) for Player P is composed of a pair {<7,a}, where a is some p a r t i t i o n i n g 0 = t' < t\ < . . . < t* < . . . o f the time interval [0,oo] by the points t' w i t h o u t finite points of a c c u m u l a t i o n ; a is the m a p p i n g which places each point y' and phase states x(t' ),y(t' ) in correspondence w i t h a measurable o p e n - l o o p control u(t) for t e [t' , t' ) (a measurable function u(t)). Similarly, the piecewise o p e n - l o o p strategy v(-) for Player E is composed of a p a i r {T,0}, where T is some p a r t i t i o n i n g 0 to < t" < ... < t% < ... of the t i m e interval [0, oo) by the points t' ' w i t h o u t finite points of a c c u m u l a t i o n ; 0 is the m a p p i n g w h i c h places each point t" and positions x{t" ),y{t" ) in correspondence w i t h a measurable o p e n - l o o p control 0

n

k

k

k

t

k

k+l

k

k

k

k

G a m e of pursuit

in norma.!

form

55

v(t) on the interval [j&tjHa.) ( a measurable function D e n o t e the set of a l l piecewise o p e n - l o o p strategies for P l a y e r P by and set of a l l possible piecewise o p e n - l o o p strategies for P l a y e r E by E.

P, Let

be a pair of measurable o p e n - l o o p controls for the Players P a n d E

u{t),v(t)

(measurable function) w i t h values i n the set of controls U, V C o n s i d e r a system of o r d i n a r y differential equations

on the time interval [0,oo] w i t h the i n i t i a l conditions x(0)

= i o , !/(0) = yo-

C o n d i t i o n A . W i t h any pair of measurable o p e n - l o o p controls u((),

it(t)

and any i n i t i a l conditions x , i / , the system of differential equations (2.2.2) 0

has a u n i q u e s o l u t i o n x(t),

y(t)

0

(x(0) = x , t/(0) = y ),

t

0

0

which can be continued

on the t i m e interval t £ [0,oo). L e t x ,y 0

be a pair of i n i t i a l conditions for equations (2.2.2). T h e system

0

where u(-)

$ = {xo>yo\u(-),v(-)},

£ P,v(-}

€ E is called the s i t u a t i o n i n the

differential game. U s i n g C o n d i t i o n A , it can r e a d i l y be shown that to each s i t u a t i o n S { x o , y o ; u ( - ) , u(')}

uniquely corresponds a pair of trajectories x(t),

that x(0) = x ,y(0)

y(t)

=

such

= j / and

o

0

v = s{y Indeed, let u{-) —

{ C T , Q } , V{-)

—

(2.2.3)

(*).«(•))•

{T,0}.

Moreover, let 0 = r < ( i < . . . u

<

< . . . be a p a r t i t i o n i n g of the interval [0, co) which is a union of p a r t i t i o n i n g s u , r . T h e s o l u t i o n of system (2.2.3) is constructed as follows. O n each interval 't+i),

= 0 , 1 , . . . , the images of the mappings a,@

o p e n - l o o p controls u ( i ) , v(t),

are the measurable

hence, by C o n d i t i o n A , the system of equations x = /(x(i),u(i)), y =

has a u n i q u e s o l u t i o n x(t),

y(t),

9(y{t)Xt))

such that x(0)

= x y((i) 0t

= y , on the interval 0

[ t , i i ) . T a k i n g x ( i i ) , j / ( t i ) as i n i t i a l conditions, on the interval [ti,t ) 2

0

we con-

struct a s o l u t i o n to (2.2.4) by reusing the m e a s u r a b i l i t y of controls

u(t),v(t)

as the m a p p i n g images a,0

Obtain-

ing x{t ), y(t ) 2

on the interval [tk,tk+i),

we continue the process w i t h the result t h a t we find a u n i q u e

2

solution x(t),y(t),

so that x(0)

= x ,y{0)

c o r r e s p o n d i n g to { x , y \ u{-),v(-)} 0

(the evader

k = 0,1,....

E).

Q

o

= y0

A n y t r a j e c t o r y x(t)

(y(i))

is called the trajectory of the pursuer P

Definition o f di/ferentiai g a m e of"pursuit

56

In what follows, we consider the games w i t h the four types of payoff functions. T e r m i n a l payoff.

G i v e n are: a number T > 0 and the f u n c t i o n

continuous on {x,y}.

T h e payoff i n the s i t u a t i o n S =

{x ,

M(x,y)

y ; u(-), v(-)}

0

0

is

defined as follows: tf(*o,yo;

«(•),»()) =

M{x{T),y{T)),

where x{T) = x(t)\ y(T) = y(t)\ = {here x(t),y{t) are the trajectories of Players P and E corresponding to the s i t u a t i o n S). W e are dealing with the p r o b l e m of p u r s u i t when the function M(x,y) is the E u c l i d e a n distance between the points x and y. l=Tl

t

T

M a x i m u m r e s u l t . Let M(x y) be a continuous real f u n c t i o n . In the situation S = {x , y ; «(•), « ( • ) } , the payoff of P l a y e r E is assumed to be min < 0 is a given number. If M(x,y) = p{x,y), then the game describes the process of pursuit. t

0

0

0

(

I n t e g r a l p a y o f f . Some m - d i m e n s i o n a l m a n i f o l d S and a continuous function M(x,y) > 0 are given i n R x i f * . A s s u m e that i n the s i t u a t i o n S = {x ,y ;u(-),v(-)} In is the first instant at which the trajectory x(t),y(t) falls on S. T h e n K(x ,y ;u(-), *>(•)) A f ( l ( i ) , y(f))d< (if t = 00, then n

0

0

l

0

0

n

K = oo), where x{t),y(t) are the trajectories, respectively, for the Players P and E corresponding to the s i t u a t i o n S. In the case M = \,K = ( n , we face the p r o b l e m of p u r s u i t . Q u a l i t a t i v e p a y o f f . T h e payoff function K may take one of the three values + 1 , 0 , - 1 depending on a position of i ( i n ) i n ft" X R . After defining the strategy set for the Players P and E and the payoff f u n c t i o n , we can define the differential game of p u r s u i t as the game in normal form. In C h . 1, by the n o r m a l form is meant the triple (X, V , K), where {X, Y) are the spaces of pairs of all possible strategies i n the game, K is the payoff function defined on X x Y. In the case involved, the payoff f u n c t i o n is defined not only on the set of pairs of a l l possible strategies i n the game but also on the set of all pairs of the i n i t i a l position x ,y . Therefore, to each p a i r (x ,yo) G R corresponds its own game in n o r m a l form i.e. we actually define a f a m i l y of games i n n o r m a l form which depend on the parameters x ,y £ R x R. B y the normal form of the differential game V{x ,yo) given on the space of strategy pairs P x E is meant the expression n

0

0

n

a

0

n

0

n

0

r ( x , a / o ) = (xo,yo\ P,E, 0

where K{x y ;u{-),v(-)) methods given above. 0l

Q

K[x ,y ;u( 0

0

),v(-)))

is the payoff function defined by any one of the four

G a m e of pursuit

in normal

form

57

If the payoff f u n c t i o n K i n the game T is t e r m i n a l , then the relevant game I" is c a l l e d the game w i t h t e r m i n a l payoff. If the function K is defined i n the second way, then the g a m e is called the game for achievement of the m a x i m u m result. If the f u n c t i o n K i n the game T has the integral form, then the relevant game T is called the integral payoff game. W h e n the payoff function i n the game T is q u a l i t a t i v e , the relevant game T is called the q u a l i t a t i v e game (the game of k i n d ) ' . N a t u r a l l y , o p t i m a l strategies cannot exist i n the class of piecewise o p e n loop strategies (in view of the open structure of the class). However, we can show t h a t , i n a sufficiently large number of cases, for any e > 0 there is the e - e q u i l i b r i u m p o i n t (see 2, C h . 1). R e c a l l the definition for the e - e q u i l i b r i u m p o i n t . Let an e > 0 be given. T h e s i t u a t i o n S* = {x , y ; «*(•), «*(•)} is called the e - e q u i l i b r i u m point i n the game r f x o . p o ) if for a l l u(-) £ P,v{-) £ E the inequality holds. 0

0

(2-2.5)

K(x ,yo;<(')X-))-t0

T h e strategies u*(-), «*(•) defined in (2.2.5), are called the e-optima! strategies for the Players P a n d E. T h e following l e m m a is a rephrased version of the l e m m a i n C h . I for differential games. L e m m a 1 Suppose

that in the game r{xo,t/o) f

or

every e > 0 there exist a

limit l i m f f ( i o , » ; « , * ( • ) . <(•))• A s s u m e that for any i n i t i a l conditions x ,y 0

0

from the region X C R

x

n

R",

any e > 0 there is the e - e q u i l i b r i u m point. W e offer the following definition. D e f e n i t i o n 1. T h e f u n c t i o n V(x,

y) defined at each point x ,y 0

0

€ R? x R"

as lug. K{x ,y ; 0

0

<(•)»<(•))

is called the value of the g a m e T{x , 0

y) 0

= V(*o>*>)>

from the i n i t i a l conditions x , y 0

T h e existence of the e q u i l i b r i u m point in the game V(x ,y ) 0

0

£

X.

for any e > 0

0

is equivalent to the fulfillment of the equality sup i n f K(x y ;u(-),v(-)) v(-)e£ "<-> 0l

6P

0

=

i n f gup «( )6f

K(x ,y ;u(-),v(-)). 0

0

'Such type games are treated in some detail in Ch. 5 which deals with the "Life line" games where the function K is specified.

of differentia/ g a m e of

Definition

58

pursuit

If i n the game T(x ,yo) for any e > 0 there are e - o p t i m a l strategies for the Players P and E, then the game V(x ,y ) is said to have a solution. D e f i n i t i o n 2. Let u " ( ) , u " ( - ) be a pair of strategies such t h a t 0

0

XfcttWfc),«*(•))

0

> K"(*°,ift>;«*(-).»'(-)) >

tf(*o,ito;«'(-),«(-))

( - - ) 2

2

7

for all u(-) e P and u(-) 6 £ . T h e situation ( x , J/oi«*(•), f*(-)) is then called the e q u i l i b r i u m point i n the game T(x , yo)T h e strategies u*(-) € P and v'(-) G £ f r o m (2.2.7) are called o p t i m a l strategies for the Players P and E. T h e existence of the e q u i l i b r i u m point i n the game P ( z o , yo) is equivalent to the fulfillment of the equality 0

tl

max

m i n K(x ,

yol ».(•)•>"(•)) =

0

#q„

m

, * ^ ( ^ c i t o ; «(')>"('))• a

Evidently, if there is an e q u i l i b r i u m point, then for any e > 0 it is also the e - e q u i l i b r i u m point, i.e.

the function V{x ,y ) 0

0

here j u s t coincides with

K(x y ; « ' ( • ) , "*(•)) (see 2, C h . 1). Consider the synthesizing strategies. D e f i n i t i o n 3. T h e situation u'(x,y,t),v'(x,y,t) is called the e q u i l i b r i u m point i n the game i n synthesizing strategies if the inequality holds. Oi

0

#(x ,!/o;"(x,!f,*),v'{x,y,t)) 0

> Jf(^,(fe;t^(^ff,i),r(ai,sv^) >

> >

(2-2.8)

K(x ,y ;u'(x,y,t),v(x,y,t)). 0

0

Note that the e q u i l i b r i u m point i n the o r d i n a r y sense i n the class of functions u(x, y, (), v(x, tf, i ) is not possible because of the nonrectangularity of the situation space (the spaces of admissible pairs u(x, y, t), v(x,y,t), for w h i c h the system (2.2.1) has a unique solution). In fact, the s i t u a t i o n u*(x,y,t), v'(x,y,t) is the e q u i l i b r i u m point i n the game P i n the class of functions u(x,y,t), v{x, y, t), if the inequality (2.2.8) holds for all situations (u{x, y, (), v'(x, y, i ) ) , and (u'(x, y, £), v(x, y, t)), for which there is a unique solution of the system (2.2.1) from the initial states x ,y on [0,oo). 0

0

T h e strategies u"(x, y, t), v'(x, t/, () are called the o p t i m a l strategies for the Players P and E. T h e function V(x , y ) = K(x ,y ;u'(x,y,t),v"(x,y,t)) is called the value function of the game. 0

0

a

a

A d i s t i n c t i o n is made between the concepts of e q u i l i b r i u m point i n the piecewise o p e n - l o o p and the synthesizing strategies. In the synthesizing strategies, we cannot require the inequality (2.2.7) to be satisfied for a l l strategies

E x i s t e n c e of the e-equilibrium

point in differential

games

59

(u'(x, y,t),v(x, y, ()), since for some ti, v the pairs (u", v), (u, v') cannot be a d missible (in an a p p r o p r i a t e s i t u a t i o n the equation system (2.2.1) may have, generally, no s o l u t i o n , or may have no unique solution). Such type of games were s t u d i e d i n the theory of games over the finite strategy sets and were called games w i t h p r o h i b i t e d S i t u a t i o n s (see [3]). In w h a t follows, we consider the classes of piecewise o p e n - l o o p strategies unless otherwise specified.

Existence of the e—equilibrium point in differential games with prescribed duration

2.3

In this section we w i l l prove the existence of the e - e q u i l i b r i u m point i n the differential games of p u r s u i t w i t h prescribed d u r a t i o n i n the class of piecewise o p e n - l o o p strategies described i n 2. C o n s i d e r i n w h a t follows the case where P l a y e r E's payoff is a distance p(x(T), y(T)) at the last instant T oi the game. Start w i t h the game w i t h t e r m i n a l payoff. Let the d y n a m i c s of the game be given by the following differential equations: for F x = p(x,u),

(2.3.1)

for£

(2.3.2)

y = g{y,v).

Here x, y £ R , U € U, v £ V, where U, V are respectively the compact sets of E u c l i d e a n spaces R a n d R ,t € [0,oo) (see [16, 17, 23, 48, 5 2 - 5 6 , 63-65]). D e f i n i t i o n 4. Denote by P{x ,t ,t) the set of all points x £ R", for which there is a measurable o p e n - l o o p control u(t) transferring the point x to the point x on the t i m e interval \t ,t] (here the phase point is assumed to be in the p o s i t i o n x at the instant (). T h e set P(x ,to,t) is the reachability set for P l a y e r P. L i k e w i s e , the reachability set E(y ,t ,t) is defined for Player E. n

k

e

0

0

0

0

0

0

0

A s s u m e t h a t the functions f,gare such that the reachability sets P(x ,t ,t), E{yo,t ,t) for the Players P and E, respectively, satisfy the following conditions: 0

0

0

1. P(x ,t ,t) 0

is determined for any x

0

0

£ R", t ,t 0

£ [0,oo] (t

0

< t) a n d is a

compact set of the space R " ; 2. the f u n c t i o n P{x ,t ,t) is continuous in a l l of its arguments i n Hausdorf m e t r i c , i.e. for any e > 0, x„ £ R , t £ [O.oo) ( ( < t) there is such S > 0 t h a t \t - *ol < S, \t - t'\ < 6, p(x ,x' ) < 6, then p'{ P[x , t , (), P(x', t' > *')) < - R e c a l l that the Hausdorf m e t r i c p* i n the 0

0

n

0

0

0

0

0

0

e

0

Definition

till

of differential

game of

pursuit

space of compact subsets R is given as follows : p'(A, B) = m a x ( / ( 4 , B), p'(B,A)). T h e same is for E(y ,to,t). Here p'(A, B) = max p(a, B), where p is s t a n d a r d metric i n R". n

J

0

a€A

T h e existence theorem w i l l be proved for the game of p u r s u i t w i t h prescribed duration r(x ,y ,T), where i , y € R are respectively t h e i n i t i a l positions of the Players P and £ , and T is the d u r a t i o n of the game which proceeds as follows. T h e Players P and E at the t i m e instant t = 0 start m o v i n g from the positions x<,,yo in compliance with the chosen piecewise o p e n - l o o p strategy. T h e games terminates at the time instant / = T, a n d P l a y e r E receives from Player P the payoff equal to p(x(T),y(T)}. (see 1, C h . 2). 0

0

n

a

0

a

A t each time instant ( 6 [0,T] of the game r(x , y , T), each player knows the time instant t, his o w n p o s i t i o n , a n d the opponent's p o s i t i o n . Denote by P(x ,t ,t) {E(y ,t ,t)). a set of the trajectories o f system (2.3.1), (2.3.2) emanating from the point x (ya) and defined on the interval [t ,t]. 0

0

0

0

0

0

0

0

Let 6 = S„ = £ a n d introduce the games r f ( x o , yo-, T), i = 1 , 2 , 3 , that are a u x i l i a r y w i t h respect to the game r ( x , j/o, T ) . 0

T h e game r j ( x , y , T) proceeds as follows. A t the first step, Player E, being i n the position y , chooses a trajectory v% f r o m the set E(yo,Q,&), and Player P, being in the position XQ and having knowledge of P l a y e r E ' s choice at this step, i n t u r n chooses a trajectory u{ from the set P(j/o, 0,5). A t the k-th step (k = 2 , . . . , 2"), Player E knows the position of P l a y e r P - t h e point x _j a n d o w n position - the point y _j a n d chooses trajectory v from the set £ ( ( £ _ , , ( £ - 1)5,fc5), P l a y e r P knows a d d i t i o n a l l y Player E ' s choice at this step and chooses a trajectory u\ from the set P[t _j, (fc — 1)6, kS). T h e game terminates at the 2 " - t h step a n d P l a y e r E receives from Player P the payoff equal to p(x(T), y(T)). 0

0

0

6 k

6

s k

t

k

T h e game r (x y T) differs from the game T{{x ,y ,T). in t h a t , as the fc-th step (k = 1 , . . . , 2 " ) , P l a y e r P chooses a trajectory u£ from the set P(ti-i'{k ~ i)S,k8) a n d knows the position x _ and at this instant; here Player E makes his choice w i t h the a d d i t i o n a l knowledge of the choice made by Player P at this step. 6 2

0:

0:

a

k

0

l

T h e game V (x , y , T) differs from the game T {x , yo, T) in t h a t , at the 2 " th step, Player P chooses a trajectory U „ from the set ^ ( x ^ . , , ( 2 - 1)6,2"S), whereupon P l a y e r E receives the payoff that is equal to p(x(T), y(T — 6)). 5

3

0

6 2

0

2

n

T o be noted is that the games r*(x ,y ,T) the games from E x a m p l e 2, C h . 1. 0

0

6

0

i = 1,2 are a special cases of

In fact, as a f a m i l y of sets U , x 6 R , i t suffices to take U(x) = P(x, 0,6], and as a f a m i l y o f sets V - V(y) = E(y,0,6) i.e. the f a m i l y of reachability sets from the initial states x and y in the time 6 — ^. n

t

s

Denote the values of the games r ,{x ,y ,T) s

0

0

by y « / r f ( i , j / T } 0

0 l

E x i s t e n c e of the e-equilibrium

point in differential

L e m m a 2 Let {A(r)}, {B(s)} ously dependent on parameters functions

61

be the family of compact sets in R" continur,s G R in the Hausdorf metric. Then the n

F{r,s)

max

=

mm

min

G(r,s)=

f(x,y),

y£B{t)

z£A{t)

max

f.(x,y),

are continuous on the product R X R if f(x,y) (this lemma is similar to Lemma 7, Ch. I). n

Proof:

games

n

is continuous

L e t us prove the l e m m a for the function F(r, s).

provided for the f u n c t i o n T h e f u n c t i o n g(x)

n

x

R"

A s i m i l a r proof is

G(r,s).

— m i n ^ s j , ) f(x,y)

is the envelope of the

function f a m i l y and is continuous on the set A{r). given.

on R

B y the c o n t i n u i t y of the function g(x)

continuous

Let a number e > 0 be

on the space R" there is such

e > 0 t h a t if the point x' belonging to the set A(r)AA(r') ,

with a particular

2

r' is such t h a t there is such point x" G A(r)f]A(r') then the i n e q u a l i t y \g(x") — g{x')\ < t is v a l i d .

< S t h a t p(x",x')

< S,

T h e definition of Haysdorf

metric suggests t h a t , to satisfy this c o n d i t i o n , it is sufficient that the inequality < 6 be satisfied, because of the continuity of the family of sets

p*(A{r)A(r')) A(r),

by the p a r a m e t e r r i n the Haysdorff m e t r i c for any 6 > 0 it is possible to

select such Tj t h a t for p{r', r) < 17 the inequality p{ A{r),

A{r')) < 3

£ is satisfied.

Consequently, by any c > 0 it is possible to find such i) > 0 t h a t for r ' , r such that p(r',r)

< n the following inequality holds I max

m i n fix.y),—

max

min

f{x,y),\<e

T h e c o n t i n u i t y of the f u n c t i o n F i n s G S is proved in much the same way.

L e m m a 3 In the games r f ( a : , t/ , T ) , z = 1 , 2 , 3 , there exists the 0

in x , y 0

0

G R, n

and T, and for

0

i = 2

3

AAB

ValTf (x , y , T})

0

ValFi{x ,y ,T) Proof:

0

every x , yo, T < oo, the functions

points for

0

0

every n > 0 the following < VaIV*(x ,y ,T),T 0

0

0

are

inequality

equilibrium continuous holds (2.3.3)

= 2"6.

T h e existence of the e q u i l i b r i u m point i n the games r f ( x , ! / o , T } ) , 0

1,2,3 =

follows f r o m T h e o r e m

7, C h . 1, and its corollaries.

(A\B)\J{B\A)

T o be compared with the equations (1.5.7'),(1.5.8').

T o prove

62

Definition

of differential

game of

the inequality (2.3.3), we w r i t e the functional equations for the ValTt{xo,y ,T)),i

=

0

functions

l,2: Valri(x ,yo,T)

=

0

max

min

ValTi(v{{S),vi(S),T

) ! n

u

n

I

min

2

2a

2

=

0

max

p(u. (T),v „(T)),

1

Vair {x ,yo,T) 6

(2.3.4)

- 6))

max min f. " eB(s^_,.r-s,T) r) 5 eP( *„_ ,r-J.r) ,T-S,T)

-

pursuit

Vair (u\{6), s

(2.3.5)

v[{6), T - 6),

2

Va/r*(x ,j ,?') = 0

min

( a

max

p(vL(T) iLlT)), t

T h e inequality (2.3.3) is obtained by a p p l y i n g sequentially the inequalities (1.2.4) to the functional equations (2.3.4) and (2.3.5). T h e continuity of the functions ValT*(x , y , T ) , i = 1,2,3 is proved by applying sequentially L e m m a 2 to the functional equations (2.3.4), (2.3.5). (The sets B, P in (2.3.4), (2.3.5) may be replaced by suitable reachability sets which enables utilization of L e m m a 2.) • 0

0

L e m m a 4 F o r any integer n > 0, ffte following Vair{"(x , 0

Vairi(x , 0

inequalities

hold:

Jto, T) < Vairl""

( x , J/6, T),

i/

(x ,

0 ]

T) > ValT " S

2

+l

0

y ,T) 0

0

P r o o f : W e show the validity of the first inequality. T h e second inequality is proved in the same manner. Suppose that P l a y e r E receives a guaranteed payoff ValT\ {x , y T) by choosing on o p t i m a l strategy in the game P [ " ( i , y , T). L e t us restrict the class of admissible strategies for P l a y e r E in the game f{" (x ,yo,T) to the class of strategies in the game r\"(x y T). It can be readily seen that here he ensures for himself the payoff equal to V a i r f " ( x o , !/o, T ) , t h i s proves the validity of the required inequality. pj n

0

0

¥1

0l

0l

0

(l

0l

Existence

of the e-equilibrium

T h e o r e m 1 For any x ,y 0

point in differential

< oo the next limiting

€ R",T

0

63

games

Hm V a / P h x c y c T ) - J i m

equality

holds:

Vair "{x ,y ,T) B 2

0

0

P r o o f : C o n s i d e r t h e games T (x ,y ,T), ri"(x ,y ,T). T o each pair of strategies u(-),u(-) i n t h e game T "(x y ,T) corresponds a pair of strategies u'(-),v'(-) i n the game ri"{x ,yo, T) which are t r u n c a t i o n s of the pair u(-),u( ) at t h e last step (u(-) = u'(-)). Denote the payoff function in the games r "(x ,y ,T) r * " ( x , y , T ) by K {u(-),v(-)) ^ d K (u'(-), «'(•)) respectively. T h e i n e q u a l i t y £ a 2

0

0

2

0

0t

0

0

0

s

2

0

0

0

2

0

3

is satisfied. T h i s means t h a t the inequality V lT^(x ,y ,T) a

0

<

0

+

max

ValTi'(x ,y ,T)+ 0

max

0

(2.3.6)

p(y,y')-

y6E{yo,Q,7W) v'€£{v,r-(„,T)

r >

*

is also satisfied. W r i t e (2.3.6) for the games w i t h other i n i t i a l d a t a : ^r* (x ,i^» r)
0

)

max

0

max

p(y,y')-

veElvJ-.O.T-S) !V'€E(v.T-Sn.T) Be the c o n s t r u c t i o n of the set E{y ", 0, T — 6 ), 6

the inclusion

n

E ( j , f » , 0 , T - 5 ) C £ ( y o , 0 , K ) (yf- e

£(y ,0,*,)).

n

o

is valid a n d , because of the c o n t i n u i t y of the function p{x, y) a n d the compactness of the sets i n v o l v e d , the inequality V a / r * " ( x , y J " , T ) < Vair "(x , £

0

+ is satisfied.

3

yt",T)+

0

max max p{y,y')ye£(vo,0.T)y'6E(y.r-«„.T)

(2.3.7)

T h e definition of the games r t " ( x , y , 7 ' ) , ^ " ( x c y o , ? ' ) implies 0

0

the e q u a l i t y Vairi"

(x , y 0

0 l

T) =

max

Vair f(x , s

in view of t h e c o n t i n u i t y of the function E(y,0,T)

0

y ",T). s s

(2.3.8)

and initial condition

£ ( y , 0 , 0 ) = 0, the a d d e n d in (2.3.7) tends to zero as n -> oo.

Denote it by

( , ( n ) . F r o m (2.3.7), (2.3.8) we get Vairi"(x , 0

yo, T) > Vair "(x 6

2

0l

J/f™, 7") - e,(n).

(2.3.9)

64

Definition

Because of the continuity of VvT^($a yo,T), s

0

> V a l l f (z ,

0

0

f f o

game of

pursuit

(2.3.9) implies the inequality

t

Vair "(x ,y ,T)

of differentia!

, . r ) - e^n) + e {n), 2

(2.3.10)

where 62(71) —* 0 as n —> co. W h e n m a k i n g a passage i n (2.3.10) to the limit as n —* 0 0 , which is possible by L e m m a 4 a n d the theorem on the bounded monotone sequence, we have l i m Vair "(x , T} s

n—.oo

> E m Vair '{x ,y T). g

0 y(h

*

1

I


(2.3.11)

1h

n—too

F r o m L e m m a 3 follows the opposite inequality. Consequently, b o t h limits in (2.3.11) coincide. T h e statement of T h e o r e m 1 has been proved on the a s s u m p t i o n that the sequence p a r t i t i o n i n g the interval [0,T] er = {i a

= Q
0

1

<...

= T},n=


N

1,...,

satisfies the condition tj+t — tj = ^, j — 0 , 1 , . . . , 2" — 1. It can r e a d i l y be seen that the statement of T h e o r e m 1 holds for any sequence a„ of p a r t i t i o n i n g the interval [0, T] such that 7

K )

= max((

j + 1

- tj)

n

=f

0.

(2.3.12)

Consider any such two sequences of p a r t i t i o n i n g the interval [0,T], and {o^}. T h e following l e m m a holds.

{a } • n

Lemma 5 J i m Vair\">(x ,y ,T) 0

where x ,y £ 0

0l

R, n

0

= Jim

Vair^(x ,y T), 0

0!

T < 00.

P r o o f : W e give the proof by c o n t r a d i c t i o n . A s s u m e that the statement of the l e m m a is not true, and assume that the following inequality will be a satisfied J i m Vair^xo^T)

> J i m ValT\" (x , y , 0

T).

0

T h e n the natural numbers n\,m.\ may be found such that the following i n equality will be satisfied Vair° -'(x ,y ,T) 2

0

0

> Vairl-'(x , ,T) 0 yo

> ValV,^ >

(x ,y ,T) 0

0

>

Vair?{xo,y*,T).

Existence

of the e-equilibrium

point in differential

65

games

Denote by b p a r t i t i o n i n g of the interval [0, 7"] by the points belonging to both the p a r t i t i o n i n g o ,

and o .

m

T h e following inequality is satisfied for a

nt

Vair (x ,y ,T) s

2

0

< ValT'S'ixoyVtoT)

0

< VaWl (^jfy T) m

<

t

<

Vair°(x ,y ,T), 0

0

whence ValTUxo,yo,T))

<

Vair°(x ,y ,T). 0

0

T h i s contradicts (2.3.3) f r o m L e m m a 3. Consequently, our assumption is false and the statement of L e m m a 5 is proved.

•

T h e o r e m 2 For all x , t / , T < oo in the game T(x ,y ,T) 0

a

0

point for any e > 0.

equilibrium

ValT(x ,y ,T) 0

=

0

\imValT^(x ,y ,T), 0

0

of the interval [0,T] (to he

where {o~ } is any decreasing sequence of partitions n

compared with Theorem

there is the e -

a

Moreover,

7, Ch. 1).

P r o o f : L e t e > 0 be a n a r b i t r a r y given number. W e show t h a t such strategies ti (-) a n d v,{-) w i l l be found for the players P a n d E respectively that for a l l strategies u(-) 6 P,«(•) € E the following inequalities are satisfied: t

K(x ,y ,u (-),v(-)) 0

0

- e < K(x ,y ,u {-),v (-))

t

0

0

c

< K{x ,y ,u(-),v,(-)) 0

<

c

+ e.

0

Because of T h e o r e m 1, there exist such p a r t i t i o n t r (
u

that Vatr "(x ,y ,T) a 2

0

-

0

lirn^ ValV' "{x ,y T)

< e,

- Vair^ixo^o^)

< e.

2

Urn ValT'Six^y^T)

0

a>

n—oo

Let «'(•) = « . < ) ,

where a ,0l l u

are o p t i m a l strategies for the players P a n d E in the game

T j " ' {x , y , T) a n d T' (x , 0

«'(•) =

vl

0

y , T), respectively. In this case, based on the choice

0

0

of maps QJ, and 0' , P l a y e r P ensures the payoff at least ( - l i m _ u

y ,T) 0

n

o 0

VaW\ (x , rn

0

+ e)"and P l a y e r E the payoff l i m ^ „ V a / r " ( i o , ! / o , 7 ' ) - e . Consequently n

i

u'(-), »«(•) are t h e e - o p t i m a l strategies for t h e players P a n d E, respectively. T h e function ValT{x ,y ,T) 0

0

= \im

Vair^{x ,y ,T) 0

a

Definition of differential

66

game of

pursuit

is the value f u n c t i o n of the game r(z>o>lfd> T)

•

C o r o l l a r y . In the proof of the existence theorem, we d i d not use the specific form of the payoff p(x(T),y(T)). It was i m p o r t a n t only the continuous dependence of the payoff from the realized trajectories. Therefore, T h e o r e m 1 holds also if instead of p(x(T), y(T)) any continuous f u n c t i o n a l o f trajectories x(t), y{t) is considered. In p a r t i c u l a r , such a f u n c t i o n a l m a y be equal too nihio
2.4

Existence of e—equilibrium points in optimal time differential pursuit games

O p t i m a l time differential p u r s u i t games constitute a special case of differential games w i t h integral payoff, as defined i n 2, C h . 1. T h e classes of strategies P and E are the same as i n the game of prescribed d u r a t i o n . T h e set S={(x y):

p(x,y)Q}.

}

is given i n R

n

x

R. n

Let x(t),y(t) be trajectories for the players P a n d E i n the s i t u a t i o n (u("),u{*)) from the i n i t i a l states x ,y . Denote 0

t {x ,y ;u[ a

0

0

i

(if such that (x((),t/(()) sumed to be +oo).

0

),t>(-)) = min{f : (x{t),y(t))

eS

does not exist, then

€ S}

(n(*o»Sol «(•)»«(•))

is as-

In the differential o p t i m a l time p u r s u i t game, Players E's payoff is assumed to be K(x ,y ;u(-),v(-)) 0

0

= t„{x y ; 0t

0

u(-),«(•))•

Player P's payoff is equal too —K. T h e game depends on the initial states x ,y , 0

0

hence it is denoted by l\x ,y }. 0

0

F r o m the definition o f the payoff function it follows that i n the game r { x , t / ) Player B aims to m a x i m i z e the time of a p p r o a c h i n g P l a y e r P on a given distance t > 0. O n the other h a n d , P l a y e r P seeks to m i n i m i z e this time. 0

0

T h e o p t i m a l time pursuit game r ( i , y ) is related directly to the prescribed duration pursuit game for achievement of the m a x i m u m result. L e t r ( i , y , T) be the game of p u r s u i t w i t h prescribed d u r a t i o n T for achievement of the 0

0

0

0

E x i s t e n c e of e - e q u i i i b r i u m

67

points

m a x i m u m result ( P l a y e r E's payoff is equal to min <,<7- p(x{t), y{t))). 0

As

shown i n 3 of this chapter, for such type of games for every t > 0 i n the class of piecewise o p e n - l o o p strategies there is an e - e q u i l i b r i u m point. Let V{x , yo, T) be the value of such a game, a n d V(x , y ) the value of the game T{x ,yo)0

Q

0

a

L e m m a 6 With the fixed x ,yo the Junction cally in T on the time interval [0,oo).

V(x ,y ,T)

0

0

decreases

0

monotoni-

P r o o f : L e t T\ > T% > 0. Denote by vf' {•) an e - o p t i m a l strategy for Player E in the game T(xo, yo, For Player E, this strategy ensures t h a t the distance between h i m a n d P l a y e r P on the interval [0, Tj] is at least max[0, V(x ,y ,7i) — e] Consequently, it also ensures the distance between t h e m max[0, V(x ,y ,Ti)— e] on the interval [0,T ], where T < T , . Hence 0

0

3

0

0

2

V ( x o , yo, r . ) > max[0, V(x , a

y , Tj) - e] 0

(2.4.1)

(the strategy uf'(*), which is e - o p t i m a l i n the game T(x ,y ,Ti), is not necessarily e - o p t i m a l in the game P ( x , yo, Since e m a y be chosen a r b i t r a r i l y , then the statement of the l e m m a follows from (2.4.1). C o n s i d e r the e q u a t i o n 0

0

0

V(x ,yo,T) 0

= e

(2.4.2)

w i t h respect to T . T h r e e cases are possible here: 1. the (2.4.2) has no root; 2. i t has o n l y one root; 3. it has more t h a n one root. In case 3, it follows f r o m the m o n o t o n i c i t y a n d continuity of the function V(x„,y , T) i n T t h a t the (2.4.2) has the whole segment of roots, i.e. the function V(x ,y ,T ), as the f u n c t i o n of T, has a constancy interval (Fig.13). 0

a

0

i

Let us consider each case separately. In case 1 it is possible t h a t : a)

K(xo,y ,7

b)

infr> V(x ,!/o,?")>£;

0

0

1

)<^forallT>0;

D

c) inf >o V{x , T

,

0

y , T) = I. 0

Definition

68

of differentia!

game of

pursuit

F i g . 13

ID case l a , we have

V O o ^ o . r ) = p{x ,y ) 0

i.e.

tn{xo,ya;ii(-)> '(')) = 0 for a l l u(-),u(-).

T{x , 0

yo) is equal to V(x

<£

0

1

T h e n the value of the game

y ) = 0. In case l b

0l

0

Jnf Vfa, ,T)

= $mV(x

Vo

T)

> i.

0%Vot

For every (sufficiently large) T > 0, Player E has the strategy u(-, T), which ensures the avoidance of ( - c a p t u r e on the interval [0, T]. Player P has no strategy which ensures the ( - c a p t u r e of Player E i n finite t i m e . Indeed, if such a strategy existed a n d ensured a p a r t i c u l a r capture t i m e V(x ,yo), then it would be better than the o p t i m a l strategy for Player P in the game T(xo, yo\ V(xo> J/o))i since, by assumption the value of this game V(x ,yo] V(xo,yo)) > £• A t the same time, it cannot be stated that Player E has a strategy w h i c h ensures the avoidance of ( - c a p t u r e for any time. T h e p r o b l e m of finding the i n i t i a l states, in which such a strategy exists, reduces to a solution of the game of k i n d for Player E. T h u s , for £ < l i m - . « , V(xo,yo,T) it m a y be s t a t e d t h a t the value of the game, if any, is larger than any fixed T , i.e. it is equal to +oo. Consider case l c together w i t h case 3. 0

0

T

Consider case 2. Let T be a unique root of ( 2 . 4 . 2 ) . T h e m o n o t o n i c i t y and c o n t i n u i t y of the function V ( i , j / , r ) in T i m p l y the existence of such S > 0 that for a l l T > T > T - 6 0

0

0

V(x ,y ,T) 0

and for a l l T + S > T > 0

0

0

0

> V{x ,y ,To) 0

(2.4.3)

0

T. 0

V(x ,!/o,T)< 0

V(xo,y ,T ) 0

0

(2.4.4)

E x i s t e n c e of (-equilibrium

points

69

C o n s i d e r the game of p u r s u i t r(x ,y ,T) (T + 6 > T > T ). It has the e - e q u i l i b r i u m p o i n t i n the class of piecewise o p e n - l o o p strategies for any e > 0. T h i s means t h a t there exists the strategy u ( / ) for Player P which guarantees h i m a p p r o a c h i n g P l a y e r £ o n a distance V(x ,y T) -f t . F r o m (2.4.4) i t follows that e! > 0 may be chosen i n such a way that ti < V(x , y , To) V ( z o , y o , T) = £-V{x , ya, T). C h o o s i n g e] in this way, we see t h a t the strategy u,[(-) for P l a y e r P guarantees h i m approaching P l a y e r E o n the distance 0

0

0

0

t l

0

0t

1

0

0

0

V(x ,

V(x , y , T) + V{x , y , T) = / .

yo, T) + ej< i-

0

a

0

0

(2.4.5)

0

F r o m (2.4.5) i t follows that the strategy «,,(•) ensures the ( - c a p t u r e of P l a y e r E i n the t i m e not exceeding T + S. Here £[ is found by S and can be defined for any 6 > 0. E v i d e n t l y , by adopting the e - o p t i m a l strategy v (-) i n the game T(x , Vo, T) (T > T > T - S) where e is chosen f r o m the condition e < V(x , y , T) - V(x , y , T ) = V{x , y , T) - t, Player E can ensure t h a t in the t i m e T P l a y e r P w i l l not approach h i m o n a distance 0

C]

2

0

0

2

0

0

0

0

V(x , 0

0

0

0

0

V(x , y , T) - V(x , y , T) + I = t,

y , T)-t > 0

2

2

0

a

0

0

i.e. i n the t i m e T ( T - e < T < T ) P l a y e r E c a n make the f - c a p t u r e impossible. T h i s means t h a t i n the o p t i m a l time p u r s u i t game r ( a : , y ) t h e r e is the e - e q u i l i b r i u m point i n piecewise o p e n - l o o p strategies for any e > 0, with the value of the game being equal to To{xo,yo)- Here T is a unique root of the E q u a t i o n (2.4.2). Q

0

0

0

0

In case 3, denote the m i n i m u m root of (2.4.2) by To- G e n e r a l l y , we cannot c l a i m t h a t the value of the game ValY{x , yo) = T . Indeed, f r o m V(x , y ,T ) = £ i t o n l y follows that i n the game T(x ,y ,T ) for any e > 0, there is the strategy u {-) for P l a y e r P which guarantees h i m the e + £-capture of P l a y e r E i n the t i m e T . T h e existence of more than one roots of (2.4.2) implies (the m o n o t o n i c i t y of V(x , y , T)) the existence of the interval of constancy in T p n j T i j of the f u n c t i o n V(x ,y ,T) Therefore, an increase i n the d u r a t i o n of the game T{xo,yo, 3") ° n 5, where 6 < T — T , does not involve a decrease in the guaranteed approach to P l a y e r E, i.e. for all T £ [To, Ti\- player P can only ensure an approach t o Player £ on a distance ( + e (for any e > 0), and we have no reason t o say t h a t for a p a r t i c u l a r T £ [To, T i ] the value of e turns out to be zero. E v i d e n t l y , if the e q u i l i b r i u m point (instead of the e - e q u i l i b r i u m ) 0

a

0

0

0

0

0

0

c

a

0

0

0

t

0

existed i n the game r ( x , y a , T ) , then the value of the game r ( x , y o ) would correspond e x a c t l y t o T . 0

0

0

0

W e m o d i f y the concept of the e q u i l i b r i u m point in the game r ( x , y o ) Henceforth i n this section i t is more convenient t o employ the notation r ( x , yo, $ instead of T(x , y ) w i t h the i m p l i c a t i o n that i n the game T(x , y , £) the play terminates when the players have approached one another o n a distance £. L e t t' (xo,yo', (-)> i )) be the necessary t i m e u n t i l the players a p proach one another on the distance ( i n the s i t u a t i o n ("(•}> v(-)). • 0

0

0

n

u

0

v

a

0

Definition

70

of differential

game of

D e f i n i t i o n 5. For t > 0 5 > 0 the pair of strategies uf(-), v (-)

pursuit

is said to

s

constitute the e, 6 - e q u i l i b r i u m s i t u a t i o n i n the game F(:to,;/o,£) 4 it constitutes the ( - e q u i l i b r i u m point i n the game T{x ,

y , £ + 5), i-e. if

0

+ e > (

t (x ,yo-M-)M(-)) l +s n

0

0

n

+ i

Oa,!/o;uf(-),^(-)) > (2.4.6)

>CVo,!/o;fifM,^))-*

for a l l u(-) e P , «(•) e £ . D e f i n i t i o n 6. Suppose there is a sequence {& }, &k —* 0 such that i n all games T(XQ, I/Q, £ + S ) for any e > 0 there is the e - e q u i l i b r i u m p o i n t . T h e n the limit k

k

\imV(x y J 0l

(2.4.7)

+ °k) = V(x ,y ,e)

0

0

0

is called value of the game r(x ,y ,(). Note that the definition does not depend on the choice of a sequence S since the function V(x , yo,£) decreases monotonically i n £. D e f i n i t i o n 7. W e say t h a t the game r(x ,y ,£) has the value i n the generalized sense, if there is a sequence {8 }, S —t 0, such t h a t for any e > 0 and 5* £ {6k} i n the game r[x ,yo,£) there exist e q u i l i b r i u m s i t u a t i o n . F r o m (2.4.6) and (2.4.7) it follows that if the game has the value i n the ordinary sense, then its value V'(x ,y ,£) (in a generalized sense) exists and equals 0

0

k

0

0

k

a

k

0

0

lim

0

t *(x ,y ,u v (-)) e +s n

0

0

6

c>

(2.4.8)

= V'(x ,y ,£)

s

0

0

{«*)-<> N e x t , from the definition of the value of the game T(x , y , £) (in a generalized sense) it follows that if i n the game T(x ,y ,£) for any e > 0 there is the ee q u i l i b r i u m point i n the o r d i n a r y sense (i.e. a solution i n the o r d i n a r y sense), then it is exactly the solution, and V(x ,y ,£) = V'{x ,ya,£) (it suffices to take a sequence {S }, 6 = 0,for all k). 0

k

0

0

0

0

0

0

k

T h e o r e m 3 Suppose there exist the least finite root of the (2.4.2), T Then there is the value (in the generalized sense) of the optimal pursuit r(x ,y ,£), 0

0

0

P r o o f : T h e monotonicity and continuity of the function V{x ,y ,T) 0

k

0

y, T)

0

Q

^ O o . y o . T o ) = £ a n d the function V(x ,y ,T ) k

oo.

in T i m -

0

plies the existence of such sequence T - » T from the left, t h a t V(x , points T .

<

= To-

and V'(X ,y ,£) 0

0

time game of

Q

0

k

-t

is s t r i c t l y m o n o t o n e at the

k

Let 4 =

(2.4.9)

V(x ,y ,T )-£>0 o

o

k

T h e strict monotonicity of the function V(x ,y T) at the points T suggests that the equation V{x , y , T) = t + 5 has a unique root T . T h i s means that 0

0

0

k

0l

k

k

Alternative

71

for any S £ {S } i n the game T{x , y , £ + e) there is the e - e q u i l i b r i u m point for any e > 0 (see case 2). T h i s , however, means that i n the game T(x , yo, £) there is a s o l u t i o n i n a generalized sense and k

0

0

0

l i m V{x ,y ,£ 0

+ S) = limT* = T =

0

k

V'{xo,yo,£}

0

T h i s proves the theorem.

•

N o w consider case l c . W e have i n f V(x ,y T) = £. Let T - » oo. T h e n limt-.eo V{x ,yo,T ) = f . T h e m o n o t o n i c i t y and continuity of V(x ,yo,T) in T suggests that a sequence T may be chosen i n such a way that the function V(x y ,T) is s t r i c t l y m o n o t o n e at the points T . T h e n , as i n the proof of T h e o r e m 3, we m a y show t h a t there exists such a sequence {b~ } that T

0

0

0>

k

k

0

k

0y

0

k

k

l i m V(x ,yoJ 0

+ 6 ) = l i m T = T = oo k

k—.co

k

0

it—.oo

T h u s , i n this case a generalized solution also exists, and a generalized value of the game V(xo, J/o,^) equals infinity.

2.5

Alternative

In many cases it is preferable to find out weather player P can guarantee the ( - c a p t u r e f r o m the given i n i t i a l positions x,y i n a fixed time T. A n d if not we have to determine whether P l a y e r E can guarantee the avoidance of ( - c a p t u r e in the prescribed t i m e T. Let V(x,y, T) be the value of the game w i t h prescribed d u r a t i o n T from the i n i t i a l states x, y £ R", the payoff being min <[
1.

V{x,y,T)>£;

2.

V(x,y T)<£. :

Let us consider case 1. It follows from the definition of the function V(x,y,T) t h a t for any e > 0 there is such a strategy «"(•) for Player E that K(x,y;u(-),v:(-))>V(x,y,T)-e. holds for a l l strategies u(-). B y choosing a sufficiently small e, we may ensure that K(x,y;u(

)y<-))>

V( ,y,T)-e>£ x

for a l l strategies tz(-) of player P. T h e form of the payoff function K

suggests

that b y a d o p t i n g the strategy v'(-), P l a y e r E can ensure t h a t the inequality

Definition

72

of differential

game of

pursuit

min £be satisfied independent of P l a y e r P ' s actions, i.e. i n case 1 Player E ensures the avoidance of ^ - c a p t u r e on the t i m e interval [0, T] independent of Player P ' s actions. 0

Consider case 2. Let T be a m i n i m a l root of the equation (T < T) V(x,y,t) = £ w i t h the fixed x,y (if p(x,y) < I, then T is assumed to be 0). T h e definition of V(x,y,T ) then implies that i n the game T(x,y,T ) for any t > 0 Player P has the strategy u'(-) which ensures t h a t the inequality 0

0

0

0

0

ff(x,y;«;(•),»(•))<

V(x,y,T )

+ e =

0

£+e

is satisfied for a l l strategies v(-) of P l a y e r E. T h e form of the payoff function K suggests t h a t , by adopting the strategy u\{-), Player P c a n ensure that the inequality min 0 P l a y e r P can ensure the £-f-^-capture of Player E i n the time T, whatever the action of the latter may be. 0

0

W e have actually proved the following theorem (about a l t e r n a t i v e ) . T h e o r e m 4 For any x,y,E alternatives holds.

ft"

and T > 0 at least one of the following

1. From the initial states x, y Player E can ensure the avoidance during the time T independent

of Player

P's

of

two

(-capture

actions.

2. For every e > 0 Player P can ensure the £ + e-capture of Player E from the initial states x, y in the time T independent of Player E's actions. For each fixed T > 0 the entire space R* x ft" is divided into three nonintersecting regions: the region A = {x,y : V(x,y,T) < £}, called the capture zone, the region B = {x,y : V(x,y,T) > £} naturally called the escape zone, and the region C = {x,y : V(x,y,T) — £}, the neutral outcome zone. 1

Let x,y

G A. B y definition of A , for any £ > 0 P l a y e r P has such strategy

u*(-) that K(x,y;u- (-),v:(-))
+ e

c

for a l l strategies u(-) of Player E. B y properly choosing of e > 0, it is possible to ensure that *(*.*;«;(•),»;(•)><

V{x,y,T}

+

e<£

is satisfied. T h e l a t t e r means that the strategy «*(•) of P l a y e r P guarantees h i m the ( - c a p t u r e of P l a y e r E from the i n i t i a l states x,y in the t i m e T. A s a result, we get the following improvement of T h e o r e m 4.

Differentia!

games with dependent

motions

T h e o r e m 5 For any fixed T > 0 the entire space is divided into three tersecting regions A, B, C possessing the following properties :

nonin-

1. for any x y £ A , Player P has the strategy uj(-) which ensures the t-capture of Player B on the interval [0,T] independent of the tatter's actions; t

8. for any x,y £ B Player P has the strategy v'(-) which ensures the avoidance of ^-capture independent of Player P 's actions; 3. for any z , y £ C and t > 0, Player P has the strategy u*(-) which ensures the (. + t-capture of Player E independent of the latter's actions. T h e e x p l i c i t i m p l i c a t i o n of T h e o r e m 5 is t h a t if x, y £ A, then P l a y e r P can always ensure t h a t the trajectory x(t),y(t) emanating from the i n i t i a l states x,y does not leave the set / H J C d u r i n g the time T. Similarly, if x,y £ ft, then P l a y e r E can always ensure that the trajectory x(t),y(t) e m a n a t i n g from the i n i t i a l states x,y does not leave the set B\JC d u r i n g the t i m e T.

2.6

Differential games with dependent tions

mo-

So far we have discussed the differential games where the players' motions were described by (2.1.1), (2.1.2). A special feature of such games is that the control and phase states of the opponent d i d not affect e x p l i c i t l y players m o t i o n , since the variables y,v d i d not appear i n the r i g h t - h a n d side of (2.1.2), and the variables x,u d i d not appear i n the r i g h t - h a n d side of (2.1.2). In this, and in the following sections of the present chapter, we study the games, where the m o t i o n equations are of a general f o r m , w h i c h does not enable us to interpret them as differential games of p u r s u i t . In general, the theorems on the existence of a s o l u t i o n in the class of piecewise o p e n - l o o p strategies, t h a t are similar to theorems f r o m 3-5 of the present chapter, do not h o l d for this case. Let z £ ft", u £ U C CompR , v £ V C CompR*, f(z u,v) be the w - d i m e n s i o n a l vector f u n c t i o n given on R X U X V. Consider the system k

t

n

z' = f{z,u,v)

(2.6.1)

w i t h the i n i t i a l c o n d i t i o n z(0) = z . T h e n z moves i n the phase space ft" under the a c t i o n of the controls chosen at each instant respectively by the players P and E i n accordance w i t h their objectives and the information accessible i n each state of the game. T h e players' objectives i n the game are determined 0

Definition

74

of differential

gome of

pursuit

w i t h the help of the payoff that is dependent on the realized t r a j e c t o r y

z(t).

T h e game is assumed to be w i t h prescribed d u r a t i o n T. L e t M[z ,z{t)} Q

be a continuous f u n c t i o n a l of t h e t r a j e c t o r y z(t) realized

d u r i n g the game. A s s u m e that P l a y e r E's payoff is M[z , z ( t ) ] , a n d P l a y e r P ' s 0

p a y o f f - A f [20, «{*)]• A s before, such type of differential games are called the games w i t h prescribed d u r a t i o n . Sometimes the r e s t r i c t i o n on the d u r a t i o n of the game is of n o i m p o r t a n c e , a n d the game proceeds u n t i l the players P and E achieve some p a r t i c u l a r result. Let the m - d i m e n s i o n a l surface S called the t e r m i n a l surface, be given in R. n

Set t

n

= m i n { i : z(f) £ £ } , i.e. i n is the first i n s t a n t at w h i c h the point

z(t) penetrates S. If for a l l i > 0 the p o i n t z(t) g S, then tn is assumed to be equal +00. P l a y e r E's payoff is assumed to be equal i n (Player P ' s payoff being — i n ) .

A s before, such type of differential games are called the o p t i m a l

t i m e games. In m a n y cases i t is essential to define a set of i n i t i a l states from which Player P can ensure that the point 2 falls on S independent of P l a y e r E's action, a n d , conversely, i t is essential to define a set of i n i t i a l states, from which P l a y e r E can ensure the avoidance of a rendezvous w i t h the set S. Such type of differential games w i l l be called t h e differential games of k i n d . A s before (see 2), we choose the classes of piecewise o p e n - l o o p strategies. For the existence of the unique solution of system (2.6.1), w h i c h m a y be continued on the interval [0,oo) under any i n i t i a l conditions ZQ £ R"and

any

situation (u('),!>(•)) i n piecewise o p e n - l o o p strategies we impose on the r i g h t h a n d sides of equations (2.6.1) the condition that is s i m i l a r to C o n d i t i o n A from 2 of this chapter. C o n d i t i o n B . T h e system of o r d i n a r y differential equations 2 = f{z,u(t),v{t))

w i t h any pair of measurable o p e n - l o o p controls u{t),v(t)

any i n i t i a l condition z

0

the time interval [0, 00).

and

has a unique solution z ( i ) which c a n be extended to A s in 2, C h . 2, by e m p l o y i n g C o n d i t i o n B , we can

construct for any i n i t i a l conditions the solution of system i = f(z, u(t),

v(t)),

which can be extended to the interval [0,oo). Moreover, we may define the payoff function K(z ,n(),v(-)), 0

whose f o r m depends of the f o r m of t h e game.

In contrast to the case of independent motions, i n the differential games w i t h dependent motions the e - e q u i l i b r i u m points for any e > 0 i n the class of piecewise o p e n - l o o p strategies m a y not exist. T h i s m a y be i l l u s t r a t e d by referring to the following simple example. Example 3. T h e game has a prescribed d u r a t i o n T > 0, i £ R>, u £ [0,1], v £ [0,1], 2 = (u - v)\ 2(0) = 2 (z > 0), M ( 2 , 2 ( i ) ) = z{T). 0

0

0

A s s u m e that the ( - e q u i l i b r i u m point in the class of piecewise o p e n - l o o p strategies exists for all e > 0, a n d let {(«;(•)>"«(•))} be a f a m i l y of the e-equi-

Differentia/ g a m e s with dependent

motions

75

l i b r i u m p o i n t s for various € > 0, a n d V be tbe value of the game. T h e n + « > V > K(z ;u:(-),v(-))

Rfa«(•).<{-))

- t

0

(2.6.2)

for a l l u(-),w(-)Since there always exists the strategy u ( - ) , coincident w i t h v'( ) (u,(-) = ""(•))> by choosing the strategy u ( ) against the strategy v'(-) P l a y e r P can ensure t h a t the velocity of m o t i o n of the point z w i l l be zero, which leads to the payoff K{z ; B , ( ' ) » » * ( ' ) ) = o in the s i t u a t i o n (ti ( ), t>*(-)) Since the payoff K(z ;u{ ),v(-)) for any u(-),t>(') cannot be less t h a n z , a n d the inequality Zo + « > V m u s t h o l d for a l l e > 0, then V = z a n d for a l l e > 0 a n d v( ) the following i n e q u a l i t y is to be satisfied (

t

z

a

(

(

0

u

0

«;(•), » ( • ) ) - « .

(2.6.3)

Now let «;(•) = {o-',o'} be the e - o p t i m a l strategy for P l a y e r P. W e construct the strategy u(-) = { T , £ } , r = a' for P l a y e r £ . For any t , z{t ), the m a p p i n g k

0' associates the state t ,z(tk), k

time interval

[ifc,ifc+i): 1 0

where u'(()

K

w i t h the following o p e n - l o o p control on the

for a i l ( for which i / ( i ) < i , for a l l t for which u'(f) > |,

is the o p e n - l o o p control d i c t a t e d by the strategy u'(t)

interval [ d t . t i + i ) f r o m the state (*, z(t ). k

on the

T h e n , i n the s i t u a t i o n (u^('),ii(-))

the velocity of the p o i n t z is J or m o r e , a n d the payoff K{za\ u*(-),ii(-)) in this s i t u a t i o n is equal to K(z ;u'(-),v(-))

^ for any ( - o p t i m a l strategy

> z+

0

0

adopted by P l a y e r PIf e = £ , then (see (2.6.3)) T zo > K(z ; 0

u j (•).»(•)) ~ 8 "

T =

T

T -

8"

T +

Z o

=

" 8

+

2

° -

T h e o b t a i n e d c o n t r a d i c t i o n means t h a t , i n the case i n v o l v e d , the e - e q u i l i b r i u m point exists not for all t > 0, a n d we cannot talk about a solution of the game in the class of piecewise o p e n - l o o p strategies. T h e f u n d a m e n t a l results for the games w i t h dependent motions were obt a i n e d by N . N . K r a s o v s k y [12] a n d his followers, who extended the classes of strategies to i n c l u d e m i x e d strategies and provide the proof of the existence of a s o l u t i o n i n this extended classes. Since the above mentioned are discussed i n d e t a i l in [12], we just dwell here on the differential games w i t h dependent motions a n d d i s c r i m i n a t i o n of one of the players where we can prove the existence of the ( - e q u i l i b r i u m points for any e > 0 i n the class of piecewise o p e n - l o o p strategies.

Definition o f differentia.! game of pursuit

76

Denote by T{z , T) the t e r m i n a l payoff game of prescribed d u r a t i o n T from the i n i t i a l state z - Introduce the upper a n d lower games w i t h d i s c r i m i n a t i o n . a

0

Let V~(z,T) be the lower game w i t h d i s c r i m i n a t i o n for P l a y e r E. L e t (j, T be the p a r t i t i o n s of the interval [0, T\ dictated by the piecewise open-loop strategies u(-), v(-) for the players P and E i n the game r(z ,T), and w - a\Jr be a u n i o n of these partitions. In the game P ( z , T), at each point t € w Player P knows t a n d z(t ), and Player E knows t ,z(t ). A s s u m e t h a t i n t h e game r ~ ( z ( , , T ) Player P knows the p a r t i t i o n w a n d , at the instants t € u>, knows t , z((fe) and a control v{t) of P l a y e r E on the t i m e interval [(*, t +i]. Changes in the information state n a t u r a l l y involve changes i n the strategy definition of Player P. 0

k

k

k

k

k

k

k

k

T h e strategy of Player P is defined i n the game F~(z , T) as follows. L e t "( ) = { ,0} be a strategy of Player E i n the game F ( z , T ) (the strategy classes of Player E in the games r ( z , T ) a n d r ~ ( z , T ) coincide). T h e n , by the strategy u{-) for Player P i n the game F " ( z , r ) is meant a pair {a,a], where a is a m a p , which places each point z[i ) and control for P l a y e r E on the corresponding interval, i n correspondence w i t h a measurable open-loop control u{t),i e [ifc,ifc+i)0

T

0

0

0

0

k

Denote the strategy classes of the players i n the game r ~ ( z o , T ) by P~ = {u(-)} a n d £ = { » ( - ) } • Let P ( z , r ) be the upper game w i t h d i s c r i m i n a t i o n of P l a y e r P . L e t
+

+

k

k

k

0

+

Jr

+

+

k

k

k

+

Denote the strategy classes for the players i n the game r ( z , T ) by P = {u(-)} a n d E = {v(-)}. W e show that i n the games r ( z , T ) a n d r~(z ,T) for the strategy classes under considering there on the ( - e q u i l i b r i u m point ( >0). +

+

£

+

0

0

0

Differential

games with dependent

motions

77

In order to prove the existence of ( - e q u i l i b r i u m points i n the games T {z ,T) and r-(z ,T), we w i l l construct the a p p r o x i m a t i n g sequence of games rf(z ,T) and Tj{z ,T) w i t h discrete t i m e as shown i n this chapter for the games w i t h independent m o t i o n s . +

0

0

0

0

T h e game Tj(z ,T) differs from the game r~(z ,T) only by the strategy sets for the players. L e t 6= {t } be a fixed p a r t i t i o n of the t i m e interval [0,T\. T h e set of strategies E i n the game rj(z T) is a subset of strategies E in the game r { z o , T ) a n d is defined as follows: 0

0

k

6

0t

_

E

e

= {(r,0):r

= 6,

(T,0)GE},

i.e. this is the set of a l l such pairs ( r , 0) for which the p a r t i t i o n r is the same. Likewise, the set of strategies Pf i n the game Vj(z ,T) is a subset of strategies P~ i n the game T~{z ,T) and is defined as follows: 0

0

P - = {(6',0):6'

=

e

S (6',a)£P-), l

i.e. this is the set of all such pairs (S',o) for which the partition S' = S is the same. S i m i l a r l y , by fixing the p a r t i t i o n s of the time interval [0, T] for all strategies of the players P a n d E, it is possible to construct a discrete a p p r o x i m a t i o n r + f z o . ^ . o f the game T (z ,T) G e n e r a l i z a t i o n of L e m m a s 2 and 3 to the case of games r J ( z , T ) , Vj(z ,T) is elementary a n d we get the l e m m a that follows. +

0

0

0

L e m m a 7 In the games r^{zo,T) and rj(z ,T) there are equilibrium points in the classes of strategies P ~ , Es and Ps, E$ respectively. The values of those games V ( z , T ) and Vf(z ,T) are continuous functions ofz,T. (The reachability sets of system (2.6.1) are assumed to be compact for any z G W , T > 0 and continuously dependent on Zo,T). a

s

s

+

0

0

0

Suppose the p a r t i t i o n 6' contains one break point more than the p a r t i t i o n S, and the other break points (* coincide w i t h the break points of the partition 6. C o n s i d e r the games Tg,{z ,T) and Vj{z ,T). L e t t < ('< t by definition, at the point z{t ) i n the game rj,(z ,T) P l a y e r P receives from P l a y e r E a smaller amount of i n f o r m a t i o n that i n the game r^",(z ,T) (in the first case he knows v(t) for t G [(*,*'). a n d i n the second v(t) for ( G [ ( * , t * i ) ) . P l a y e r E, however, receives at the instant t' the i n f o r m a t i o n about the state z(t') that is a d d i t i o n a l as against the one in the game r ^ ( z , r ) . T h i s means that P l a y e r P ' s p o s i t i o n i n the game Tj(z ,T) becomes worse as against the one in the game rj(z ,T), w h i c h leads to the inequality Vf(z ,Y) > ^"(zo.T). T h e same i n e q u a l i t y follows from such explicit reasoning as Es- D E . Restrict Q

k

a

k

k+l

0

0

+

0

0

0

0

s

Definition

78

of differential

game of

pursuit

Player £ i n the game Tj.(z, T) to the class of strategies Es i n the game T h e n , i n the game rj.(z,T), he can always ensure the payoff equal to from w h i c h we get the inequality

Vj(z,T) Vf(z,T),

V 7(z T)>V -(z ,T). t

0l

s

(2.6.4)

0

S i m i l a r l y , we may get the inequality V t(z ,T)
+

0

(2,6.5)

0

Let 6i C 02 C - -. C fi C be a decreasing sequence of partitions of the interval [ O T ] . Since the t e r m i n a l payoff M[z , z{T}\ is bounded on the reachability set of the system (2.6.1) from the i n i t i a l state z i n the time T , then the sequences V ~(z ,T) and V *(z ,T) are bounded monotone sequences of continuous functions. Let \5\ = m a x ; tk\ be a break r a n k . n

0

0

s

0

St

0

—

( t e

L e m m a 8 There exist the

limits

V+(z ,T)

=

0

V(z T)=

s

\im

th

that are independent

l i m V +{zo,T), is* I—o Vf {z ,T) k

Q

s

sequence {fit}-

of the choice of a partition

T h e existence of the limits V , V~ for each fixed decreasing sequence {fit}, fifc+i D Sk, \$k\ —* 0 follows from the monotonicity and boundlessness of se¬ quences { V + } , {V ~}. W e show that for all uniformly decreasing sequences {fi*} a n d {fij,} of the interval partitions the following relationship holds +

s

00

J i m V -(z ,T)= f

00

l]mV 7(z ,T)

0

s

0

Denote l i n w V£ = V-{{6 )) and l i m ^ V$ = V-({6' }) Set L = sup V ({fifc}) (here supremum is taken w i t h respect to a set of all uniformly decreasing breaks). It is fairly easy to see that L < oo, since a l l V~({S }) are bounded by the number supM(z , z ) , z e C (z ). Here M(z) is the terminal payoff t h a t is a continuous function, and C (z ) is the reachability set of system (2.6.1). Let an a r b i t r a r y n > 0 be given. B y the definition of L, there is such a p a r t i t i o n that k

k

4|[

k

T

0

T

0

u

Vf{2o,T)>L-$. Let m be a number of interior points of the p a r t i t i o n fi. Because of the continuity of the reachability set C ( z ) (in the Hausdorff metric) and the continuity T

0

Differential

games with dependent

motions

79

of the payoff M for any n a t u r a l number m a n d any e > 0, there is such 6(e) > 0 t h a t , i f i n the p a r t i t i o n 6'^ - *J_.,J < 5(e) for a l l i , then for any p a r t i t i o n 6" c o n t a i n i n g m interior p o i n t s the following inequality is satisfied V- „{z ,T) U6

- V 7(z ,T)

0

6

W e choose 5' i n such a way t h a t | i ; l?r M o r e o v e r , Vf^j „(e ,T) s

u s

<e.

0

< |(|). T h e n

« ( s . , ^ - y r ( o , T ) < e = |. J

Z

> L — |, whence we have t h a t

A

V,7
>£-,,.

0

T h e latter inequality shows that for any decreasing sequence of p a r t i t i o n s of the interval [0,T] l i m Y%fa,f)

= L.

T h i s e x a c t l y proves the first p a r t of the statement i n L e m m a 8. Its second part is proved i n m u c h the same way. T h e o r e m 6 In the games r {z ,T) +

e-equilibrium r (z ,T) +

+

and r-{z T),

for any e > 0 there are

0

0

respectively.

QL

0

and T~(zo,T)

0

points and V ( z , T), V~(z , T) are the values of the games

P r o o f : L e t us prove the statement of the theorem for the game T~(z , T). T h e 0

proof for the g a m e T (z ,T) +

is made i n m u c h the same way. F i x an a r b i t r a r y

0

e > 0 u s i n g L e m m a 8, we m a y find such a p a r t i t i o n 5 that (2.6.6)

V-(z ,T)-Vf(z ,T)<e. 0

0

Let &t,Vs(-) be o p t i m a l strategies for the players P a n d E in the game

TJ{ZQ,T).

W e construct the following strategy for the P l a y e r P in the game

r~(z ,T). 0

Let «(•) = ( r , / 3 ) be a strategy for P l a y e r E, then by ii*( ) = (fi,a) is meant the strategy for P l a y e r P which places his every i n f o r m a t i o n state a t the time instants tk € S\JT i n correspondence w i t h the same o p e n - l o o p control u(t) for * € [h,tk+i)

as the strategy u y , that is o p t i m a l i n the game rj^j (z(t ),T f

T

T

tk), f r o m the i n i t i a l state zfjfcj, d u r a t i o n T — t W e show t h a t t h e strategy u'(-), r~(z , T).

k

-

K

w i t h the p a r t i t i o n 8(Jr.

is o p t i m a l for P l a y e r P in the game

E v i d e n t l y , as follows from (2.6.6), for any e > 0 by a d o p t i n g the

0

strategy v , t h a t is o p t i m a l i n the game Tj(z ,T), 6

0

payoff at least V~{z ,T) 0

P l a y e r E can ensure the

- e. W e show t h a t , by p l a y i n g the strategy

P l a y e r P guarantees the payoff for P l a y e r E not exceeding V~(ZQ,

u'(-),

T) = L.

Definition

so

of differential

game of

pursuit

Suppose the opposite is true. Let t?(-) = {T', 0} be a strategy for P l a y e r E , under w h i c h the payoff i n the s i t u a t i o n (u*(-)i »(•)) is L+c> crete game r j y , ( z , T ) w i t h the p a r t i t i o n 6\JT'. T

L. C o n s i d e r a dis-

In the s i t u a t i o n (u'(-), !>(•)),

0

the game r ~ ( z o , T ) is realized as a discrete game w i t h the p a r t i t i o n 6(Jr'.

In

a d d i t i o n , as follows from the definition of the strategy u'(-), P l a y e r P chooses the same controls u(t)

for ( € [(*,t*+i) ^ ^

n

pl y

e

a

o p t i m a l l y i n the game

s

T j y , ( z , T),i.e. he ensures that P l a y e r £ ' s payoff w i l l not exceed V j . ( z , 7 * ) f

5

0

T

0

F r o m (2.6.4), however, we have V -(z ,T) 5

0

< V-^Xz^T)


=

V~(z ,T). 0

T h e latter inequality means t h a t Player P can ensure t h a t P l a y e r E's will not exceed L. T h i s proves the theorem.

2.7

payoff •

Alternative for games with dependent motions and discrimination

Consider the games w i t h dependent motions f r o m 6. Let a compact set 5 be given i n R". In some cases we have to find out whether a player can ensure that a trajectory z(t) penetrates the terminal set S i n a fixed time T from the i n i t i a l position z € R . If this is not possible, then we have to find out whether Player E can ensure the avoidance of the point z ( i ) falling on the set S d u r i n g time T. n

0

T h e reasoning given i n the previous section point out the way of solving this problem for the upper F ( z , T ) and the lower r ~ ( z , T ) games with discrimination. +

0

0

T h e o r e m 6 can be readily generalized to the case when the payoff of Player £ is a continuous function of the realized trajectory: i n p a r t i c u l a r , it can be generalized to the case when it is of the form o

min ?(z(t),S),

(2.7.1)

r

where z(t) is a realized trajectory, p a distance to the set S. T h i s section does not provide appropriate proofs since they are exactly as i n 6. Now, let r ( z o , T ) and r ( z J") be the upper and lower games w i t h disc r i m i n a t i o n and payoff (2.7.1), K " ( z , T ) and V ( z , T ) being the corresponding values of the games. W e shall study the game r ( z , T ) i n some detail. T h e game P ( z o , T ) is studied in m u c h the same w a y T h e following two cases (two alternatives) are possible: _

+

0 l

0

+

0

_

+

1-

V-(z ,T)>0, o

0

A l t e r n a t i v e for games w i t h dependent motions and d i s c r i m i n a t i o n 2. V-{z ,T)

81

= 0.

o

C o n s i d e r case 1. Let K{z ; u(-), «{•)) be the payoff function in the game under study. It follows from the definition of V~(zT) that for any e > 0 there is such a strategy v'(-) for P l a y e r E t h a t for a l l strategies u(-) 0

B y choosing a sufficiently s m a l l e, we may ensure that K(z u(-),v;(-))>V-(z T)-e>Q o]

0>

for all strategies u(-) of P l a y e r P . T h e form of the function K suggests that, by a d o p t i n g the strategy «"(•), Player E can ensure t h a t the inequality

m i n p(z(t), S) > 0 will be satisfied independent of P l a y e r P's actions, i.e. in case 1 Player E ensures the avoidance of the point z failing on the set S d u r i n g the time interval [0, T] independent of Player P ' s actions. Consider case 2. L e t To be the m i n i m a l root of the equation (T < T ) V~(z ,t) = 0. T h e definition of V~(z ,t) then suggests t h a t , in the game r(zo,To) for any e > 0 P l a y e r P has the strategy u'(-) which ensures that the inequality 0

0

0

K(z ;u:(-},v(-))
+ e = e

0

is satisfied for all strategies v(-) of Player E. F r o m the form of the function K it follows t h a t , by a d o p t i n g the strategy u'(-). P l a y e r P can ensure t h a t the inequality m i n p(z(t),S)

< e

is satisfied independent of P l a y e r E's actions. W h e n the strategy u"(-) is extended to cover the interval [0, T], we see t h a t , in case 2, for any € > 0 P l a y e r P can guarantee the entry into the ( - n e i g h b o r h o o d of the set S in the time T independent of Player E's actions. W e proved the following theorem (about alternative). T h e o r e m 7 In the game T~(z,T), holds (z € R

n

and T >

at least one of the following

alternatives

0).

I. Player E can guarantee the avoidance of the entry into the terminal set S from the initial state during the time T independent of Player P's actions.

82

Definition of differential

g a m e of

pursuit

2. For e > 0, Player P can guarantee the entry into the (-neighborhood of the terminal set S from the initial state z during the time T independent of Player E's actions. A similar theorem also holds for the game r ( z , T) M o r e general a n d finer theorems (for the game F ( z , T) were proved by N . N . K r a s o v s k y [12]. T h e corresponding constructions u t i l i z e wide classes of m i x e d strategies. T h e remaining chapters of the book are not dealing w i t h dependent motions. +

Chapter 3 Class of pursuit—evasion games with optimal open—loop strategy for evader 3.1

Discrete game with terminal payoff and discrimination for player E

T h e game Ts(x ,y , 0

T), that w i l l be discussed in this section, differs from the

0

game Ti{x ,y ,T) 0

defined i n 2, C h . 2, i n the strategy sets P , E for players.

0

Let 8 =

(0 = t

0

< i

t

of the time i n t e r v a l [0,T].

< ... < t

< t„ = T}

< ...

k

be a fixed p a r t i t i o n

T h e strategy set i n the game Ts(xo,yo,T)

is a

subset of the strategy set E i n the game V(xo, yo, T ) and is defined as follows : E

s

= {{T,@)

: T = 8,(T,0)

G E],

i.e. this is a set of a l l the pairs (T,3)

g E

for w h i c h the p a r t i t i o n T = 8 is the same. T h e strategy space for P l a y e r P is composed of pairs {6, a } ,

where 6 is

the p a r t i t i o n of [0,7"] fixed throughout the game (and coinciding with the p a r t i t i o n of the same i n t e r v a l for Player E), a n d a is the map which places an admissible o p e n - l o o p control u(t) on the interval [t*,ifcfi) in correspondence w i t h each p o i n t t

k

€ 8, the p o s i t i o n x(t ), y(t ), k

k

and the o p e n - l o o p control

u(£),fe[r*,r* ). + 1

T h e strategy spaces for the P l a y e r P and E i n the game T$(x , yo, T) 0

denoted b y P , s

E, 6

are

respectively.

T h e c o n s t r u c t i o n of strategies for Player P suggests that the i n f o r m a t i o n on x(t ), k

a n d the P l a y e r E's c o n t r o l v(t)

y(t ) k

each i n s t a n t t . k

k

E is the first to choose u(t) for t G [t ,t ) k

P.

for ( € [(*,ij=+i) is supplied at

T h i s m a y be understood as follows. A t the instant t

T h e n P l a y e r P chooses u(f) for ( G [t ,t i). k

83

Player

and reports his choice to P l a y e r

k+l

k+

In this case P l a y e r P is

CJass of pursuit-evasion

8-1

games with optimal

open-loop

strategy

i n a privileged p o s i t i o n , the game is called the game w i t h d i s c r i m i n a t i o n for Player E . N o t e that d i s c r i m i n a t i o n for P l a y e r E is not assumed i n the game r(*o,yo,r). Denote the strategies i n the game r {x ,y ,T) by u {-)>M )- Evidently, all the constructions i n v o l v i n g the derivation of a unique s o l u t i o n of the system x = f(x,us()),il = g{y, "*(•))> w i t h the i n i t i a l conditions and situation ( U ( - ) , J J S ( - ) ) , are made just as i n 2, C h . 2. Recall that Player E ' s payoff i n the game w i t h t e r m i n a l payoff is defined as p(x(T),y{T}), where p, is the E u c l i d e a n distance between the players' position x(T),y(T) as the game terminates (see 2, C h . 2). Denote by Cf{x ) and C^(y ) the reachability sets for the P l a y e r P and E from the initial states x ,yo at the time instant T and p{xo,y ) = m a x , r . m i n , 7 - ( ) / » ( ? ' , n ' ) - U s i n g the designations f r o m 3, C h . 2, we have s

0

0

s

S

0

0

0

£

6 C

0

n

e c

( 3

o l

1

I 0

P(x , a

0, T) = C {x ), T P

E(y ,0,

0

T) =

0

C {y ). T B

a

Let p {x ,y ) = p(£,n) (p is achieved at the points £ £ Cp{x ), tj £ Cg(jf ))> where o ( f , J ? ) is the E u c l i d e a n distance between the points £,n. Any trajectory x (t) (0 < t < T) j o i n i n g ( x ' ( 0 ) = x ,x'(T) = j ) points x and £ is called the conditionally o p t i m a l trajectory for P l a y e r P and any trajectory y'(t) (0 < t < T ) j o i n i n g (y*(0) = yo, y*(T) = if) points y a n d n is called the conditionally o p t i m a l trajectory for Player E. T

0

0

T

0

0

m

0

0

Q

T h e point M is called the center of pursuit in the game Ts(x ,yo,T) 0

PT=

m a x

n

,

if

A

. ™ ,/»(?'. »?') = /({> 0

(/) is achieved at the points £ € Cp{x ), M £ C / j ( y ) ) . T h e center of pursuit may be not unique. T o every center of pursuit M correspond points £ £ Cp(x ) from (3.1.1). 0

0

0

Let x"(() be the c o n d i t i o n a l l y o p t i m a l trajectory for Player P , leading to f, and y'(t) the conditionally o p t i m a l trajectory for P l a y e r E , leading to M. W e say that the trajectories x'(t),y*(t) correspond to one another. Consider an a u x i l i a r y game r' (x,y,T) w h i c h is the same as the game F6(x,y,T) except that here Player E remains at the point y when t £ [ 0 , 0 ] , i.e. Player E ' s motion takes place w i t h the delay a. T h e m o t i o n equations and the payoff of the players are same as i n the game Fs(x, y, T). Let M', x"(t),y"(t) be the center of pursuit and the relevant conditionally o p t i m a l trajectories i n the game T' (x,y T). W e say t h a t i n the game Ts(x,y,T) there is an invariant center of p u r s u i t if the following conditions are Sg

5a

t

satisfied. ' i n [10, Cl(y ) 0

and

12]

the quantity pr(zo,ya) CJ,(x ). a

is called the " h y p o t h e t i c m i s m a t c h " between the sets

Discrete g a m e w i t h t e r m i n a l payoff a n d d i s c r i m i n a t i o n for piayer E

85

1. T h e center of p u r s u i t is the same i n all of the games V {x*{t),y'(t),T-t) f r o m the i n i t i a l states x " ( t ) , y'(t) w i t h the d u r a t i o n T-t, where x"(t), y*(t) are an a r b i t r a r y p a i r of the relevant c o n d i t i o n a l l y o p t i m a l trajectories i n the game r (x , y , T). s

6

0

0

2. F i x t, x ' ( r ) , !/*((), a n d let x"(t + a) (0 < a < T - t, x"(t + a)\ = x"{t)) be a c o n d i t i o n a l l y o p t i m a l trajectory for Player P in the game r ' s i ( x " ( i ) , i / , r - f), where y G C|;(j/*(t)). C o n s i d e r the current games " V c - t y C + <*),V,T - t - a) for 0 < a < S and fixed (, y G C {y-(t)). L e t M'{a) be a center of p u r s u i t i n the game r ' _ ( i ' * ( ( + a),y, T —t~ a) for 0 < a < 6, y e C (y'(t)). W e require the point M'(a) not depend on a for a i l 0 < a < S (occupies the same position). a=0

,

s

( (

E

0

s E

Prove the following l e m m a . L e m m a 1 Let x"(t),y"{t)

be a pair of relevant conditionally

ries in the game Tg(x, y, T), exist the solution the recurrent

x'(t ),x'(ti},...,

k

t

a

min

=

lk

on the conditionally

Proof:

x'(t ),x'[t ).

D

optimal

being invariant. a

trajecto-

Then there

= T, (x'(t ) 0

= x) 0

of

equations

PT- {Ah),y'(tk)) laying

the center of pursuit

(3.1.2)

jT- (x,y-{t )), ll+l

k+1

optimal trajectory x'(t)

i.e. x'(tk)

=

x'{tk).

F r o m the invariance c o n d i t i o n for the center of p u r s u i t M p(( M)

= p ^(x-(t),y'(t)),

1

T

0

A l o n g the relevant c o n d i t i o n a l l y o p t i m a l trajectories x'{t),y'(t)

for all ft £

we have

{toy-,in)

^, (x*(t ) ,-(r ))=^1

i

l i

t

( t +

A t the same t i m e , for a l l x G C (x'{t )) s

P

T

is satisfied.

k

k

<

k

+

(3.1.3)

1

the inequality

k

p -t {x~(t ),y-(t ))

,(x*(^ i),y*(iH ))-

fr_ (*,|f(**+i))fMl

Indeed,

pT-t^'i^^'ih))

=

max min p{x ) « £ $ * ( * * ( ' * ) ) >y

T

min

p{x',M),

=

Class of pursuit-evasion

v€C

T E

min However, since x g C p *

games with optimal

'*+»(*•('*+.»«*€^

,>(x,JW),

(x G

W

open-loop

strategy

M

G ^ V t M ) ) -

''(x"^)),

+1

C^" '(x)CC?-"(^(^)). +

then T h e latter inequality, together w i t h E q . (3.1.3), proves the l e m m a .

•

D e f i n i t i o n 1. T h e set of points {x',y',T'} such t h a t V £ [ 0 , T ] , x' £ Cp~ '(x), y' £ C%~ \y) is called the singular surface i n the game Ts(x,y,T) if i n the games P,;(x', y', J " ) there is no invariant center of p u r s u i t . T h e singular surface is called dispersal if Player E's choice of the control v(t),t € [t ,t ) on the singular surface defines uniquely the invariant center of pursuit M w i t h respect to the reachability sets C p " ' ^ ^ ) ) a n d CE~' {y{t ),v). Here Cl~ *(y{t ),v) is a subset of the set C£~'*(t/((*)), where i n P l a y e r E may arrive at the instant T from the states y(t ), w i t h the fixed s t a r t i n g interval of control v(t),t £ [ f , t , r ) . T h i s set coincides w i t h C ^ ' * ' (y(t )), where y{t i) is a point wherein Player E arrives from the state y(t ), when using the control v(t),t £ [tfc,(fc+i)' T

T

k

1

l

k

k+1

k

k

k

-

fc+1

4

k+

k+1

k

T h e o r e m 1 Suppose that in the game rs(x , yo, T) there is an invariant center of pursuit pVfxo.J/o) > 0- Then there exists an equilibrium point, the conditionally optimal trajectories are optimal, and the value of the game is equal to Va(x ,y ,T) = pr(xo,J/o)' Moreover, the optimal strategies for the Players P and E are of the form vj(-) = (£,/?*), where the map /?* associates each point x(t ),y(t ),t with the control v'(t), t £ [t ,t ) which defines the motion of the point E on the conditionally optimal trajectory y'(t) in the game r (x(,, J / Q , T) aiming to the invariant center of pursuit (i.e.,the piecewise openloop strategy r j ( ( ) is time function); u j ( ' ) — (6, a"), where a' places each point ?(**))** control v(t),t £ [ i , i ) of Player E in correspondence with the control u(f), ( £ [t , t + 1) transfering the point x from the state x(t ) to the state x ( t t i ) such that 0

0

0

k

k

k

k

k+l

s

a

n

d

t

k

t + 1

k

k

+

^r-

l i + 1

(x(i* ),!,(« + 1

f c + 1

))

=

min

^ T

l l + 1

Here y{t ) is the point wherein Player E arrives v(t), t £ [<j(,tfe+i) at the time instant t . k+1

k

( x , y(t )). k+1

when choosing

(3.1.4) the control

Discrete g a m e w i t h termi/iaJ payoff a n d d i s c r i m i n a t i o n for p/ayer E

87

P r o o f : W e show t h a t ^ ( * o , ! » ; « ; ( • ) . "!(•)) =

fr(xo,yo)-

(3.1-5)

Let y*(f) b e the c o n d i t i o n a l l y o p t i m a l strategy for P l a y e r £ directed towards the invariant center of pursuit M whose existence is assumed i n the theorem (y*(0) = yo, y*(T) = M). In the s i t u a t i o n {x ,y \v.'{-),v-{-)) the trajectory x'(t) for P l a y e r P at the t i m e instant t ,k - 0 , 1 , . . . . n passes through the points x'(t ) obtained as a solution of the recurrent equation ( L e m m a 1): 0

a

k

k

fr- {x'(t ),y-(t )) tt

k

min J T ^ V ,

=

k

/(**,))•

(3-1.6)

For any solution of this system, however, we have M*0>»>) = P T - , ( x ' ( i i ) , ! / * ( i i ) ) = . . . (

--• =

fr-^Wfrffc))

p(x*
= . . . = f>(x'(r),M) = ff(*o,»;u*(.),v*())

= cons(.

(3.1.7)

We have thus proved the equality (3.1.5). Show t h a t K{x ,y ;u ( a

0

),v}(-))

s

> p (x ,y ) T

Q

0

> K(x ,y ;u- (-),v {-)). 0

0

s

s

(3.1.8)

for a l l «((•) G P and u (-) G E . F i r s t prove the v a l i d i t y of the l e f t - h a n d inequality. Let u<( ) be a strategy for P l a y e r P, a n d x(T) the point wherein he appears when the game ends i n the s i t u a t i o n ( « ( ( - ) ' " £ ( ' ) ) - Since (

s

(

PT{xa,yo)=

max

nun o(£,A/),

t h e n , for any p o i n t £ ' 6 Cf{x ), the inequality P T - ( X Q , yo) < ptf', M) is satisfied. In p a r t i c u l a r , p r ( x , j ( o ) < p(x{T),M), a n d since the strategy uj(-) transfers yo to the point M, then /»(x{T'),A/) = K(x ,y ; us{-),v' (-)), a n d this proves the v a l i d i t y of the l e f t - h a n d inequality (3.1.8). W e now prove the v a l i d i t y of the r i g h t - h a n d inequality (3.1.8). In the game r$(2o,!/o,T), h t i m e instant (* the pursuer P has complete information on the trajectory of P l a y e r E for ( G [<*,(*+))• p a r t i c u l a r , this means that at each t i m e i n s t a n t t he knows the point y(t +i) which is reached by £ in the time - t . N o w assume that P l a y e r £ deviates his conditionally o p t i m a l trajectory (control v"(t)) d u r i n g the time t +t - h choosing on t h e interval [tk,h+\) t h e control v{t) different from v'(t). 0

0

Q

a

t

0

s

e a c

I n

k

k

k

k

88

CJass of pursuit-evasion

games with optimal

open-loop

strategy

Since Player E has held the control u*(t) up to the i n s t a n t r * , then from the definition of the strategy uj(-) for Player E a n d f r o m the invariance of the point M we have h{x»,yo) L e t D ~'"{y{t )) E

=

PT-t (x'(h)>y'(tk))t

be a subset of the reachability set C%~ (y*{t )) tk

k

E, which is o b t a i n e d from C]f {y{t )} ik

at the instant i +i, E passes through the point y(t +i). k

= ^r-*i(M*{iA),V*(ifc)) >

0

>

max

min

Consider the a u x i l i a r y game T' (x*(t ), SiS

point y — y[t +i)

for Player

Then

k

PT(x ,yo)

k

under the a d d i t i o n a l requirement that,

k

k

(3.1.9)

p(^,n).

y, T — t ) k

where E remains at the

d u r i n g the t i m e 6.

k

Let x'*(() be a conditionally o p t i m a l trajectory for P l a y e r P i n the game I V ( x - ( i * ) , V,T - i ) .

Let r _ (x"(t iiS

s

y = y(t ), k

k

d u r i n g the time t

y = y(h+i)

a

- h - a) for 0 < a < 6,

+ a),y,T

k

be the game, where P l a y e r E remains at the point

z'(tk) = x'(t )

-{t

k+1

k

+ a) = S - a, a n d pT-t - {x'*{h k

a

+

a) y) l

be a m a x i m i n distance between reachability sets c o m p u t e d in this game. T h e n PT-,Ax"(t ),y)

= &_,,,(**(**). I f ( ' H i ) )

min

< p _ (x'(t ),y'(t )).

k

max

T

tt

k

k

= (3.1.10)

F r o m the existence of the invariant center of pursuit i n the game Ts(x , 0

ya,T)

(see condition 2) it follows t h a t , for all 0 < a < 6, the center of p u r s u i t i n the games rs,s- (x"(t a

- t — a) is the same, therefore for a l l 0 < a

+ a),y,T

k

k

PT-n + ){^ k

a

k

+ a),y(t ))

-

k

<6.

const.

Hence, i n p a r t i c u l a r , w i t h a = 0 and a — 6 we get

However, PT-t (x"{tk i),y) t+l

+

=

max

min

/>({,*) =

since, in this case, P l a y e r E remains at the point y{t ) 6-6 = 0. A s a result, we get (see E q . (3.1.10)) k+1

PT-t^,{x-(t ),y) k+l

< p ^{x-(t ),y~(t )), T

k

k

d u r i n g the time

(3.1.11)

Discrete g a m e w i t h terminal

payoff and discrimination

i.e. there is such p o i n t x"(t ) quently,

€ C (x'(t ))

k+1

P

k

for player

89

E

that (3.1.11) is satisfied. Conse-

where x is chosen by the strategy u'(-) from the condition m i n i.e. i n t h e s i t u a t i o n (ii'('),i> (-)) we have

pr-t (x,y{t +i))i k

k

c

Pr-tH,

= fa(xo, yo)

< pT-tfc(**C
if, p l a y i n g the strategy vs(),

P l a y e r E continues to select the controls, which

do not coincide w i t h v*(t), then fa{x ,y ) 0

0

> pr-<

= pT-t (x'(t ) -(t )) k

>

k iy

k

fr-tw(x(t ,y t )) M

{

>...>

k+2

= p{x{T) y(T)) :

=

t + 1

(x(t

f c +

,),!/((

po(x(T),y(T))

t + 1

)) >

=

K(x ,y u- (.)M-))0

0]

s

T h i s is e x a c t l y w h a t proves the v a l i d i t y of the r i g h t h a n d inequality (3.1.8). We have thus proved the theorem.

•

T h e o r e m 1 has a l o c a l character and holds i n the regions of x , y , T, where 0

a

the invariance conditions for the point M are satisfied, i.e. i n the space region bounded b y the singular surface. N o t e that PT[X<3, yo) = 0 holds for C g ( y o ) C C?(x„)._ Let T > 0 b e the first time instant when pr(xo,yo)

= 0 and the condition

a? > 0 i n T h e o r e m 1 is violated explicitly. ( C o m p a r e this w i t h the first instant of absorption). T h e following theorem is readily obtained from the c o n t i n u i t y of the function PT{XO,VO) T h e o r e m 2 Suppose 6 ),S 2

2

T.

m

there is such Si > 0 that in the games TS(XQ,

< 6\, the conditions

2

the value of the game r (x ,y ,f) s

P can approach

Player

0

j/ol T —

of Theorem 1 are satisfied (for all 5 < S ). 0

Then

t

is zero, i.e. for any e > 0 at time T

Player

E for a distance not exceeding t.

P r o o f : T h e p r o o f of T h e o r e m 2 follows f r o m the fact t h a t , by adopting i n the game r (x ,y ;f) s

B

the o p t i m a l strategy u * ( ) in the game Ts(x , y \T -

0

0

0

P l a y e r P c a n approach P l a y e r E at instant f - S on a distance P T S ^ X Q , 2

and from the Hausdorff c o n t i n u i t y of the reachability sets Cp{x),C^(y), point T = 0. Corollary.

6 ), 2

j/), 0

at the •

If T > T, then the players P a n d E may be i n the states

of passive e x p e c t a t i o n , i.e.they make a r b i t r a r y moves along some trajectories u p to t h e t i m e i n s t a n t T = T, where f

x(t),y[t)

equation p (x(r),y(r)) T

is the m i n i m u m root of the

= 0. For £ € [r,T], the players start the p u r s u i t i n t h e

game r ( s ( r ) , y(r); T - T), ensuring a zero value of the game in accordance A

Class of pursuit-evasion

90

games with optimal

open-loop

strategy

w i t h T h e o r e m 2 (provided t h a t the conditions of this theorem are satisfied in the game r,(x(r),y(r),f)). Consider a global solution of the games. W e restrict ourselves to the games of pursuit where a l l singular surfaces are dispersal. T h e theorems 1, 2 make it possible to construct the solution " i n s m a l l " , i.e. w i t h the a d d i t i o n a l assumption that the players' trajectories do not intersect singular surfaces. For the global solution one chould be able to construct an o p t i m a l control on singular surfaces. In the general case, the nonincrease of Pr{x, y) is to be proved a d d i t i o n a l l y when Player P adopts the strategy u'(-) (the principle of m i n p ) , to the point m o v i n g on the singular surface (see the examples 4, 5, 7, C h . 4). In the case of the dispersal surface, the solution is comparatively simple, since Player E's choice of the control v(t) for ( 6 ['k,(it+i) on a singular surface (which becomes known to the opponent immediately) defines uniquely the center of pursuit M from the states x(tt,),y(t),) for the sets C j ~ ' * ( a : ( ( t ) ) , C g ' * ( ! / ( 4 ) ) . T h e o p t i m a l control is intended for a i m i n g at the point M. T h u s , the theorems 1, 2 also give a global solution to the games of pursuit where all singular surfaces are dispersal. _

3.2

Continuous game without discrimination

U s i n g the continuity of the function ^r(*o,I/o) in T,x ,y d i s c r i m i n a t i o n requirement. 0

we can discard the

0

W e define the invariant center of pursuit for the continuous game without d i s c r i m i n a t i o n r(x,y,T). T h e pursuit center M is called invariant if there is such 5 > 0 that for all 0 < 5 < 5 it is invariant i n the discrete games r $ ( x , j / , T) w i t h d i s c r i m i n a t i o n for Player E. T h e o r e m 3 Suppose in the game T[x ,yo,T) there is an invariant center of pursuit. Then the function p (x , yo) i» the value of the game without discrimination (i.e. the game of pursuit where Player P's choice is based only on the information about the state of the system at the time instant t). 0

T

0

P r o o f : For the given e > 0, we choose such 6 > 0 t h a t 0

\h{xo,yo)-fa(x',y')\ for all x', y' belonging to C {x ), 6 P

0

< |

(3.2.1)

Cgftfe), and for all 8' < 8 . N e x t . l e t 5, be such 0

that for a l l x e C^{x ) a n d a l l 6' < 5, the diameter of the set D{C (x)) < | and 8 = min{S ,S } Player P is prescribed the strategy u,( ), under which, on the time interval [0,5] he moves a r b i t r a r y to a point x(5) e C {x ). Let 0

0

6

P

}

p

0

Continuous game without discrimination

ill

x(6),y(6) be the states realized by the instant S. F r o m the state x' = x{S), y(6) he plays an o p t i m a l strategy in the game w i t h d i s c r i m i n a t i o n T {x', y , T) s

0

(this is possible, since at each step Player P knows the move made by his opponent). T h e value of the game r (x',y T) is equal to PT(x',y ), but in the game V$ P l a y e r P cannot make a final move (having played the strategy «*(•)), since he has lost one (opening ) move by choosing a n a r b i t r a r y m o t i o n to the point x' from the point x i n the t i m e 6. Therefore, he can guarantee an approach to P l a y e r E by the instant T only on a distance px(x', yo) + 5 (since the diameter of the reachability set C (x) for one step does not exceed 6 for all x £ C p ( x ) ) . Because of E q . (3.2.1) the strategy u ( ' ) ensures that Player P will aproach P l a y e r E by the time instant T on a distance PT{XQ, yo) + e. Since Player E c a n always p r o v i d e for himself the payoff PT(XQ, yo), then u,(-) is the ( - o p t i m a l strategy for P l a y e r P. T h i s completes the proof of the theorem. • 6

0t

0

0

P

0

(

Instead of the lower game of p u r s u i t , where Player E is d i s c r i m i n a t e d , we may consider the u p p e r game of pursuit w i t h d i s c r i m i n a t i o n of Player P. A l l previous results are valid i f instead of the q u a n t i t y max

pr( o,yo)= x

m i n />(£,?)

we consider the q u a n t i t y min min p{(,n). (6Cj(i ) neclbn)

p{xo,yo)=

0

In this case, the definition of the upper center of pursuit and its invariance may be also i n t r o d u c e d . W h e n the center of pursuit is invariant the upper center of p u r s u i t is not (this was to be expected, otherwise the quantities p,p would be e q u a l , w h i c h is far from r e a l i t y ) . Moreover, we know no case of the invariance of the u p p e r center of the pursuit other than i n the game of " s i m p l e p u r s u i t " o n the sphere. A t the same t i m e , the invariance of the center of p u r s u i t is observed i n a large class of problems (see [28, 30, 32]). T h e latter consideration also provides support for the i n t u i t i v e l y evident n o n - s i m m e t r y of the players' status i n the games of pursuit. T h e a b o v e - m e n t i o n e d constructions may also be generalized to the case where the sets Cj,(x ) a n d C%{y ) are not necessarily closed. M o r e o v e r , the e - o p t i m a l i t y m a y be shown for the strategies given above, where under the quantities PT{x,y),Pr{x,y) are meant the quantities 0

a

pr{x,y)

P(x,y)

=

=

sup

inf

inf

p{?,n),

sup

p{(,v),

92

Class of pursuit-evasion

games with optimal

open-loop

strategy

a n d under center of p u r s u i t a n d the upper center of p u r s u i t are meant the points i n the e-neighbourhoods

of the points M

Cl(y )

closures of the sets Cf{x ),

0

0

a n d M'

belonging to the

and d e l i v e r i n g m a x m i n a n d m i n m a x in

the preceding equalities.

3.3

Arbitrary terminal payoff functions and phase constrains

W e now t u r n to the p u r s u i t - t y p e games of p r e s c r i b e d d u r a t i o n

T{x ,y ,T) 0

0

where the t e r m i n a l payoff is denned as K(x ,yoM-),v())

=

a

where M(x,y)

M(x(T),y(T))

is an a r b i t r a r y continuous function given on R

n

X RJ . 1

T h e lower game w i t h d i s c r i m i n a t i o n Ts(x , y , T) is defined as i n 2, C h . 2, 0

except t h a t M{x(t),

0

is meant everywhere i n s t e a d of

y(t))

T h e function Mr(x,y)

p(x(T),y(T)).

is the analog of the function p(x,y)

a n d is defined

as follows: Mr(x,y)

— max

min

M(£,n).

C o n d i t i o n a l l y o p t i m a l trajectories are defined as in 1 (for simplicity, the sets C (y) E

and Cp(x)

are assumed to be c o m p a c t ) .

T h e point H is called the center of the game V${x , y , T) if MT(x ,y ) 0

M{£, H).

(Here

0

0

0

=

H are the points at which m a x m i n of the function M ( £ , TJ)

is achieved). B y analogy w i t h 1, we introduce the a u x i l i a r y game T' (x,y,T)

where

So

Player E remains at the p o i n t y d u r i n g the time a. T h e center of the auxiliary game is determined as i n the game r ( x , y, T) except that the reachabiliy sets, by which m a x m i n is t a k e n , are computed for the a u x i l i a r y game. A s i n 1, the notion of the invariant center of the game is i n t r o d u c e d w i t h the help of the a u x i l i a r y game. T h e o r e m 1 is fully applicable to the case of the function MJ{XQ,

yo).

T h e o r e m 4 Assume that in the game Ts(x , yo, T) there is an invariant center of the game and A Z ; r ( : r , y ) > 0. Then there is an equilibrium point, conditionally optimal trajectories are optimal, the value of the game V(x ,y ,T) = MT[XO,yo), and optimal strategies for the players P and E are constructed in much the same way as in Theorem 1. 0

0

0

0

0

T h e proof for T h e o r e m 4 fully coincides w i t h the one for T h e o r e m 1, in 3. T h e n o t i o n of the singular surface is j u s t as i n 1. T o generalize T h e o r e m 3 to the games w i t h o u t d i s c r i m i n a t i o n , we utilize the continuity of functions Mr{x,y)

i n all of the arguments.

A r b i t r a r y terminal

payoff functions

and phase

constrains

93

T h e o r e m 5 A s s u m e that in the game r{xo,yo,T) (without discrimination) there is an invariant center of the game. Then the function Mj{x,y) is the value of the game without discrimination. Proof:

A s i n T h e o r e m 3, we consider the a p p r o x i m a t i o n game r (x s

with descrimination.

y , T)

0:

0

Here the c o n t i n u i t y of the function Mj{x,y)

is used

instead of the c o n t i n u i t y of the function p(x , y ). 0

•

0

T h e o r e m 5 is a p p l i c a b l e t o z e r o - s u m games of pursuit w i t h prescribed d u ration between the pursuer team a c t i n g as one player P = { P i , . . . , P } a n d m

the evader E. Suppose the m o t i o n equations for the team partners P j , i = l , . . . , m , and Player E are of the f o r m i«

=

u), « 6 0 ® , J $ € R , i = l , . . . , m , n

!/ =
Sjg

,...,

0

min,'/3{i'''(T),J/(T')),

where x ' ( i ) , y(t), i = l,...,m-

yo, (*)> u

=

are trajectories of the

team members P ; a n d P l a y e r £ f r o m the i n i t i a l states x' , yo, i ~ 1 , . . . ,m, in a

the s i t u a t i o n («(•),«(•)).

In order to have an o p p o r t u n i t y to apply T h e o r e m 5,

we a d d to the m o t i o n equations for Player E, n x (m — 1) equations of the from Vi = ° . j = !»••••>.** X ( w i t h a r b i t r a r y i n i t i a l conditions. new extended vector y = (y,y,,... i

m

- )> ]

B y the state vector of Player E is meant a of dimension n X m . T h e vectors

,y ( -i)) n

m

a n d y are of the same d i m e n s i o n . W e rewrite the payoff i n the equivalent

form: K(x '\...,xo \yoM-)A-)) 0

=

m

= m\n

M(x(T),y(T))==

p(x^{T)MT)).

Here b y t h e distance is meant t h e distance between the vectors x y{T)

( , ,

{ T ) and

(but n o t y(T)) i n the space R . Since the function M(x, y) is continuous, n

we can a p p l y T h e o r e m 5. L e t a closed convex set S be given i n R". Consider the pursuit game w i t h prescribed d u r a t i o n a n d w i t h the a d d i t i o n a l constraint under which the players P and E are n o t allowed t o leave the set S d u r i n g the game. M o t i o n equations are o f the f o r m E q . ( 2 . 1 . 1 ) , Eq.(2.1.2), the i n i t i a l conditions being ( x , y ) G S. 0

0

T h e payoff is defined as a distance between the players at t h e time instant T when the p l a y ends. D e n o t e such a g a m e by

r'^(xo,yo,T).

94

Class of pursuit-evasion

games with optimal

open-loop

strategy

T o s u m m a r i z e the previous results, we have to introduce the n o t i o n of a d missible o p e n - l o o p controls a n d admissible strategies. T h e o p e n - l o o p control u(t) for 0 < ( < T is called admissible in the game ^l ' (x ,1/o>3 ) ' f under this control the trajectory x(t) corresponding to the : 1

0

^,

given o p e n - l o o p control belongs to 5 (XQ £ S).

T h e admissible open-loop

control for Player E is determined i n much the same way. B y the reachability set Cf(x ,S) 0

for Player P i n the game

T^(x y T) Ol

0t

is meant a set of points at which Player P can arrive at t h e t i m e instant T from the point x

0

£ S be e m p l o y i n g every admissible o p e n - l o o p control. T h e

reachability set Cg(y ,S)

from Player E is defined i n m u c h the same way.

0

T h e piecewise o p e n - l o o p strategy ti(-) is called admissible if i n any situation u(-) £ E the trajectory x(t), x(0) = x

o

£ S , 0 < t < T

belongs

to S. A n admissible piecewise o p e n - l o o p strategy for P l a y e r E is defined in much the same way. T h e set of a l l admissible piecewise o p e n - l o o p strategies for the players P and E will be denoted respectively by P

s

and E .

B y the e q u i l i b r i u m point

s

and the value of the game are meant those i n the class of admissible piecewise o p e n - l o o p strategies. It follows from the construction of the sets P P, s

v(-) £ E

s

and x £

S,y £

0

0

and E

s

s

that for any u(-) £

S the trajectories x(t),y(t),

0 < t < T, belong

to S. B y analogy w i t h pr{x , yo), we define P T ( X , y , S) as 0

PT{x ,yo,S) 0

0

=

sup

0

inf

p(f,n).

A l t h o u g h this does not play a role i n what follows, we assume that the sets @E{yQ>S),

Cp~{xo,S)

are compact a n d the function PT(X<3, y , S) is continu0

ous i n Xo, yo, T (in the phase-con strained games this c o n d i t i o n m a y not be fullfilled). T h e n it is possible to define a center of pursuit a n d relevant conditionally o p t i m a l trajectories x"((), In general, not a l l of the c o n d i t i o n a l l y o p t i m a l trajectories correspond to admissible controls, we agree to consider, w i t h o u t special s t i p u l a t i o n s , only admissable c o n d i t i o n a l l y o p t i m a l trajectories x'(t),

t/*(t) i.e. such t h a t x'(t) €

S, y'{t) £ S for 0 < i < T. F r o m the definition of the sets Cf(x ,

S), C f ( j / o , S )

0

it follows that such trajectories necessarily exist. A s in 2, we define the discrete game r (x ,ya,T) s

Player E.

0

w i t h d i s c r i m i n a t i o n of

In this game, we find the strategy u"(-) of P l a y e r P from the

formula (3.1.4) by replacing therein the set C {x(t )) s

P

k

B y c o n s t r u c t i o n , t h e strategy u*(-) is admissible. invariant center of pursuit. Here by x'(t),

by C {x(t ), P

k

S).

A s i n 2, we define an

y*(i) is meant a n admissible pair of

relevant c o n d i t i o n a l l y o p t i m a l trajectories. Theorems 1, 2, 5 h o l d fully for the

time p u r s u i t games

Optimal

95

case of phase constraints i f by the reachability sets are everywhere meant the sets Cp(x, S), C (y, 5 ) b o t h in definition of pr{x, y) and in the formulation of an o p t i m a l strategy for P l a y e r P . E

3.4

Optimal time pursuit games

In this section, we w i l l consider the games o f p u r s u i t where the payoff function equals t h e t i m e - t o - c a p t u r e . F o r the purposes of defininiteness, we assume that the t e r m i n a l m a n i f o l d S is the sphere p(x,y) = (,£ > 0, the function M(x,y) = +1 (see i n 2 , C h . 2) [28]. Let us assume that the sets C' {x) and C (y) continuous i n the point t = 0 uniformly w i t h respect to x and y. Suppose the following q u a n t i t y has a m e a n i n g P

®{*,y,£)

E

= max min

t (x,y-,\i(t),v(t)), n

where t (x,y; u((), w(t)) is the t i m e of advancing the distance t between t h e players P and E m o v i n g from the i n i t i a l points x, y under measurable o p e n loop controls u{t) a n d v(t), respectively. A l s o , assume the function Q(x,y, () continuous i n a l l of its arguments. Kelendzheridze was t h e first to introduce this function [9]. n

D e f i n i t i o n 2 . L e t ( u ( i ) , 8 ( f ) ) , f £ [0, oo) be a pair of o p e n - l o o p controls, under w h i c h Q(x, y, () is achieved, and y*(f), x'(t) be a corresponding pair of trajectories defined b y sistem (2.1.1), (2.1.2) under o p e n - l o o p controls u(t), v(t) and i n i t i a l c o n d i t i o n s x * ( 0 ) = x, y * (0) = y. T h i s p a i r o f trajectories w i l l be referred t o as a pair o f conditionally o p t i m a l trajectories. In what follows, r' (x,y) is the game of pursuit which differs from the game T ( i , y) only in t h a t here Player E remains in the initial state y d u r i n g the time S. L e t x' (t) be a c o n d i t i o n a l l y o p t i m a l trajectory for Player P in this game. 6

T h e o r e m 6 Suppose the following t. inf t )&(x',y,l)

conditions

are satisfied

is achieved with y fixed for any x.

fl(iC i(x

2. 0 ( x * ( i ) , !/*(*), 0 + * "

c o n s i

>

0

^

(

^ *n»

w

h

e

r

e

t

n

=

I n i n

<{'

:

P(*'(t) y*(t))
3. There is such I that for all S < § in the game F {x, y) with any fixed t, s

V 6 0 {y'(t)) E

for all 0 < a < 6 we have B(x"(t

+ a),y,()

+ a = const,

Class of pursuit-evasion

games with optimal

where x'*(t) = x"(t) (here Q{x"(t + o),y,i) T' . (x"(t

+ },yJ)}

5 a

is computed for the game

Then for any I > 0, e > 0 in the game T{x,y)

there is the

exist such pair of strategies u'(-),

t-equilibrium

i.e. for any e > 0 there

point and the value of the game is equal to Q(x,y,£), that

- e < tU*>vi
>y

strategy

[28].

a

e(x ,e)

open-loop

^

+ «.

4{*,j/i«(•).<(•)) + * > ^ f * * » ; « * ( • ) » « * ( • ] ) > t' (z,yX(-)M-))

(--) 3

4

J

- % (3.4-2)

n

for all possible strategies t i ( - ) and v(-) of the players P and E. Before passing t o the proof of the theorem, we prove some auxiliary statements. A s i n 2 of this chapter, we introduce the discrete games rs{x,y,t) with discrimination of Player E. M o t i o n equations for the players are the same, and a p a r t i t i o n of the interval [0,oo) is fixed, i.e. the p a r t i t i o n by the set of points {tfcl^o that tk+i — t — S for any k. P l a y e r E is said to be discriminated, i.e. at the time instant t Player P has, apart f r o m information on the time, his own and opponent's position at a given t i m e , information on the control v(t) for t £ |*fc,t*+l)- T h u s , at the instant t P l a y e r P has information o n the opponent's position at the instant t +\. Let u*(-), vs{-} be strategies for the players P and E respectively i n the game rs(x,y,£). s

u

c

n

k

k

k

k

L e m m a 2 Under conditions of Theorem 6, in the game Vjfe, y, () for S <S there is an equilibrium point in pure strategies and Q(x,y,£) is the value of the game, i.e. there exist a pair of strategies uj(-), uj(-) such that for any strategies uj(-) and Uj( ) of players P and E in the game Yi{x,y,V) there is t' (x,y,u (-),vl(-))>t (x,y,u}(.),v (-)) n

6

n

=

6

(3.4.3)

= Q(x y ?)>t (x,y;u (-),v (-)). l

>

n

l

s

P r o o f : Let v{t;x(t ),y(t )), u(t;x(t ),y(t )), t £ \t ,oo), be a pair of o p e n loop controls o n which Q(x(t ), y(t ),i) is achieved. Let us define the strategies uj(-) and v' (-). T h e strategy « ; ( - ) for Player E in the game V (x,y,() associates the state (t ,x(t },y(t )) w i t h the admissible o p e n - l o o p control v{t,x(t ),y{t )) for ( £ [ < , i ) . T h e strategy uj(-) for Player P i n the game Vs{x,y,() associates the state (t ,x{t ),y(t )), with the admissible o p e n - l o o p control v.(t;x(t ),y(t +i)), t £ [tk,t ) transferring the point x(t ) to such point x(t ) £ C (x(t )) such that k

k

k

k

k

k

k

s

s

k

k

k

k

fc

k

fc+J

k

k

k

k+1

Q(x(tk+i)Mh )J) +l

P

=

k

k

k+l

k+l

k

m i n e(x\y(t i),e), k+

(3.4.4)

O p t i m a / t i m e p u r s u i t games

97

if the ( - c a p t u r e f r o m the points x(t ),

off.*) is impossible i n the time 6. O t h e r -

k

wise P l a y e r P chooses the admissible o p e n - l o o p control u(() which allows the ( - c a p t u r e to be realized in the m i n i m u m time. W e w i l l show t h a t the s i t u a t i o n («((•)• f((').) is the e q u i l i b r i u m point. A s s u m e t h a t in the s i t u a t i o n ( « " ( • ) , u * ( ) ) for n < k the equality holds Q(x(t ),y{t ),e) where x(t ),

= 6(x,y,(),

n

(3.4.5)

is the position of the players P a n d E at the instant ( „ i n

y(t )

n

+ t

n

n

n

the s i t u a t i o n ( u j ( - ) , » ( ( • ) ) , establish that Eq.(3.4.5) holds for n = k + 1. Let v(t;x(t ) (t(:)), k

t G [ffc,oo) be a p a i r of o p e n - l o o p

u(t;x{t ),y{t )),

iy

k

k

controls on which Q{x(t ),y{t ),() k

is achieved, a n d x'(t,x(t )),

k

y'{t,y{t )),

k

k

t G [t <x>) be a corresponding p a i r of trajectories defined by the system (2.1.1), kl

(2.1.2) u n d e r the i n i t i a l conditions x'(t ,x(t ))

=

y'(tk,y{t ))

= y(tk)

k

k

k

x[t ), k

and the o p e n - l o o p controls v(t;x{t ),y(t }), k

time r = ( - t

a n d denote x'(t,x(t ))

k

k

Introduce the

u(t;x(t ),y(t )).

k

k

k

= x(r,x(t )),

«"((,y{t ))

k

=

k

y(T,y(t )). k

F r o m Eq.(3.4.4) we have 9 W ( * , ) , ! / ( f i , y ( t * ) ) , ( ) < Q(x(6,x(t )),y(6,y(t )),g). k

+

(3.4.6)

k

T h e second condition of T h e o r e m 6 implies e(x(6 x(t )),y(6,y{t ))J) 1

k

k

k

B y the a s s u m p t i o n , the c o n d i t i o n (3.4.5) is satisfied. t r o d u c i n g the n o t a t i o n y(S,y(t )) k

(3.4.7)

+ 6 = e(x(t ),y(t ),e).

k

fr°

= y(t -n), k

m

Consequently, by i n -

(3-4.6) a n d E q . (3.4.7) we

get e(x(t ),y(t ),i) k+l

+ t

k+l

(3.4.8)

<6(x,y,e).

k+1

A t the same t i m e , let x' be an a r b i t r a r y point of the set C £ ( x ( ( t ) ) , a n d u ' ( i ) , i 6 [t , t +i) be an a d m i s s i b l e o p e n - l o o p control transferring the point x(t ) k

k

k

to

the point x'. N e x t , let u ( i ) , t G [U+1,00) be such admissible o p e n - l o o p control that t (x\y(t )Mt)Mi,x(h)Mt>-))) n

=

k+l

= mint {x\y(t i),u(t) v(t,x{t ),y(t ))) "(') n

< maxmm v(()

k+

1

t (x',y(t )Mt)Mt}) n

k+1

k

<

k

= eK3/(*

t + ]

},().

(3.4.9)

»(<)

Let D be a set of measurable o p e n - l o o p controls u ( t ) , ( 6 coincident w i t h the f u n c t i o n u'(t) on the interval [t t +i)kt

k

[(4,00)

t h a t are

Denote by ti(i)

98

Class of pursuit-evasion

games with optimal

the function defined on the interval [t ,oo) k

strategy

that is coincident w i t h u'(f) on the

k

interval [t ,tk+i)

open-loop

a n d w i t h 5(() o n [ ( * i , o o ) . T h e n +

» ( < * ) . * ( * ) , * K ' , *(**). *(**))) = =

min

t {x{t ),y(t )Mi)Ai,x(h),y(tk))) n

k

k

Next *&(*(ifc),y(*fc),fi(t,«(**),|f(*t)) ii(* a{*fc),|f(**))) = )

= min

1

t^{x(U)Mtk)Mt)Mt,x{tk),y{tk)))

{here m i n is taken for a l l possible measurable o p e n - l o o p controls). However, D is a subset of the set of all measurable o p e n - l o o p controls. Consequently,

^(*(*t)^(**),»(*,*(*k).»(*fc)),«(*.*(**).»('*))) =

© ( * ( * * ) . <

T h e latter inequality (3.4.10) follows f r o m (3.4.9). T h u s ,

+ e(x\ (t ),e).

Q(x(t )Mh),e)<6

y

k

k+l

T h e inequality {3.4.11) holds for any point x' g C (x(t )), P

k

(3.4.11) specifically, for

x ( ( t + i ) . F r o m (3.4.11), (3.4.8), a n d from the a s s u m p t i o n (3.4.5) we have

Q(x,y,l)

= e{s(tHi)»V(*Hi),0 + '*+!•

So (3.4.5) also holds for n = 6 + 1 . For n - 0 , Eq.(3.4.5) is obviously satisfied. W e have thus proved (3.4.5). L e t N be such that Q(x,y,i)

= N6 + 6', where 6' < 6. Since NS = t , from N

(3.4.5) we have 0(x,yj) here Q(x{t ),y(t )J) N

= e(x(t ),y{t ),£) N

N

+ t, N

(3.4.12)

= 6' < 6.

N

F r o m the states x(f-w), y(i/>/), h a v i n g i n f o r m a t i o n on Player Es control for the time 6 ahead and a d o p t i n g the strategy u j ( - ) , P l a y e r P m a y finish the pursuit in the time Q(x{t ),y(t ),£) N

= 6' < 8. T h u s the hole t i m e of pursuit

N

in the situation (l*J(')i"*(")) from the i n i t i a l states x, y along t h e trajectories ! / " ( ' ) ' equal to s

i'niw,

«*(•). V|(-)) = t

N

+ S- = NS + 6' = Q{x,y, f).

(3.4.13)

Let us prove the validity of the r i g h t - h a n d side of t h e inequality (2.4.3). W e first show that in the s i t u a t i o n ( « # ( • ) » J ( 0 ) the following inequality holds V

9(x(M,y(M,<)>©(3((m),y{W*) + ^

(3.4.14)

O p t i m a / t i m e p u r s u i t games

99

where x(t ), y(t ), x(t ], y(t ) are positions of the players P and E at the time instant t and t i n the s i t u a t i o n (wf(').fj{-)), k

k

k+l

k

k+l

k+l

©(xfifej, y(tk)J)

= m a x m i n *£,(*(**), !/(**)>«('), » ( * ) ) =

- m i n t n ^ ) ^ ^ ) , ^ ) , ^ ! , ^ ) , ^ ^ ) ) ) .

(3.4.15)

Let i i ( i ) i £ ) be an o p e n - l o o p control transferring the point x(t ) to the point x{t ). T h e o p e n — l o o p control transferring the point y(t ) to the point y(t ) is the control v(t;x{i ),y(t ), t £ \t ,t ). Let D be a set of o p e n - l o o p controls defined for t E [t*,oo) and coincident w i t h w(f.) for £ € [ t t , t i i ) . C o n s i d e r the q u a n t i t y k

k+1

k

k+l

k

k

k

k+i

+

Evidently, <jfe>

» ( ' * ) ' «<'>. < 5

^

t ;

< S f etajftiw),^^)^).

(3.4.16)

The set D is a subset of the set of a l l measurable o p e n - l o o p controls. C o n sequently, f r o m (3.4.15) and (3.4.16) it is possible to derive the inequality (3.4.14). L e t tij(-) be a strategy of Player P under which, i n the s i t u a t i o n («((• ))"?(•))> he makes r times a choice that is different from the choice of u j ( - ) . In this notation uj(-) = u°( ). A s s u m e t h a t for n < r the inequality * n ( w K 0 X ( 0 )

>9 ( W ) -

(3.4.17)

is satisfied. P r o v e t h a t (3.4.17) also holds for n = r + 1. N o w , suppose t h a t i n the game Ts(x,y, £} Player P adopts the strategy u j ( ' ) , a n d P l a y e r E the strategy v^(-). L e t t be the time instant at which the choice of u £ ( - ) does not coincide w i t h the choice of uj(-) for the first time. W e introduce the t i m e r = t — t i and consider the game r $ ( x ( t i i ) , y(t +i),£), where x(t ), y(t i) are positions of the players P and E respectively at the instant t i n the s i t u a t i o n ( u £ ( ' ) , u ; ( - ) ) . In this game, Player E adopts the strategy uj(-) P l a y e r P the strategy under w h i c h , i n the s i t u a t i o n ("£(')< l ( ' ) ) i he makes a choice r times different than the choice of u j ( - ) , i.e. the strategy l(')- B y a s s u m p t i o n . + 1

k

+1

k+

k+}

k

+

kJt

+ l

k+l

u

u

t„(x(tk uy(h i)y (-)M) +

+

s

>

eHM-?(W4

(3-4.18)

and since ( h ( ^ y . ^ ( ) . ^ ( 0 ) =^»+in(^('Hi),!/(^ i);^(-).'';(-)), 1

+

(3-4.19)

100

Class of pursuit-evasion

games with optimal

open-loop

strategy

then, by e m p l o y i n g (3.4.14), we obtain

T h e choices by the players P a n d E i n the game T {x,y,t), however, has been coincident w i t h their choices in the s i t u a t i o n (t£(•),tlj(-J) u p t o the instant f*. Consequently (3.4.15) holds for n < k. T h e n , from (3.4.20) we find s

(3.4.21)

tnlx^v'sU.u^W^Q^y,?)

T h u s , (3.4.10) also holds for n = r + 1 , and since this holds obviously for n = 0, then i t also holds for a l l n < N i.e. for any Player P ' s strategy i n the game Fj(a;,3/,£) we have the inequality. t (*iy>M-),v;(-))

> &(x,yJ)

n

fe^sB^H)

=

(3-4.22)

Now prove the validity of the r i g h t - h a n d side of the inequality (3.4.3). First establish the following inequality: 0(^),yfc),O>H0(% ,),y(Wi).a +

where x(t ), y(t ), x(t^i), y{t +i) are the points at w h i c h the players P and E arrive i n the s i t u a t i o n (ttj(-),v$(-)) a t the instants t , (t+iL e t v(i), t € [t ,t + 1) be an o p e n - l o o p control transferring the point y(tk) t o the point j/((fc i), a n d u(t), t £ b e an o p e n - l o o p control transferring the point x(t ) to the point i ( r ) . L e t D be a set of measurable o p e n - l o o p controls that are coincident w i t h the control v(t) o n the interval ), where tk is the time instant when P l a y e r E's choice i n t h e situation (ttj(-), »;(•)) is firstly noncoincident w i t h his choice in the s i t u a t i o n (uj(-),t)J(-)) Then k

k

k

k

k

k

+

k

f c + 1

&(x,y,e) = t + e(x{t ),y(t ),e) k

k

k

> ™ . m i n t (x(t ),y{t ); n

k

u(t),v(t))

k

u(i)eD u(i) (3.4.23) Consider an a u x i l i a r y game V (x{t ), y ) , where P l a y e r E remains at the point y = y{t ) d u r i n g the time b\. Let x'*(t) be a c o n d i t i o n a l l y o p t i m a l trajectory for Player P i n t h e game U( (M>f)< 's,B- (Atk + <*),y) for 0 < a < 6, y = y{t ), x''{t) = x(i ) be the game where Player E remains at the point y = y(t i) d u r i n g the time t i - (t + a) = 6 - a. L e t Q'[x"(t + a), y, () b e the m a x i m i n time prior to the ( - c a p t u r e computed i n this game. T h e n 6Si

k

k+x

r

x

a

D

dT

a

k+1

k

k+

k+

k

k

9 V « * ) , y , 0 = e>'(r ),y('* »),*) = t

= tnm.nnnt {x(t ),y(i ),u(t)Mt)) n

v(tj€D u(<)

k

k

+

< Q{x(t ),y(t )J). k

k

(3.4.24)

O p t i m a ) t i m e p u r s u i t games

101

It follows f r o m c o n d i t i o n 3 of T h e o r e m 6 t h a t for all 0 < a < 6 0 ' O ' " ( ( + a), V{tk+i),t)

(3.4.25)

+ a = const.

t

Hence, i n p a r t i c u l a r , for all a = 0 and a = 6 we get = 6y%*i^i(&wM) +

&(x"{t ) y(t ),£) k t

k+l

(3-4-26)

S

However »[*) «(0 = e(x"(^

+ 1

), (( ! /

t + 1

)/)

(3.4.27)

since i n this case P l a y e r E remains at the point y(t ) time 5 = 0. A s a result, we have k+i

Q(x (tk)Mh)J)>Q(x"(tk )Mh i),e) H

+i

(3.4.28)

+ 6

+

Consequently, there exists such x " ( t i ) € C (x(t )) satisfied. T h e n the following inequality holds P

t +

> ©

©(**(**),V(W)

unmoved d u r i n g the

f

t

k+l

/

)

for which (3.4.28) is

+ 6

(3.4.29)

where x is selected under the strategy u'( ) from the m i n condition of the function © ( z , j / ( t

l + 1

) , f ) o n the set Cp{x(t ))

i.e.in the situation (uj(-),««(•))

k

e ( * , s , / ) = e(*(r ),!,(t ),() + t > e ( x ( ( t

t

t

t + 1

),j,(i

t + 1

),^) +

(3.4.30)

T h e further prove is i n much the same way as the vahdity of the l e f t - h a n d side of the i n e q u a l i t y Eq.(3.4.3). • W e now t u r n t o the proof o f T h e o r e m 6. P r o o f : B y hypothesis, the function 6(x,y,£) is continuous i n a l l of its arguments. Consequently, for any t > 0 we find such 6 > 0. t h a t as soon p({x,y,£),(x',y\£'))<6,

(3.4.31)

\Q(x,yJ)-Q(x\y',e')\< -.

(3.4.32)

e

T h e a s s u m p t i o n a b o u t the continuity of C (x), Cp(y) i n t = 0 uniformly w i t h respect t o x, y suggests t h a t by 8 i t is possible t o find such 8 > 0 that for any x' € Cp(x), y' G Cp(y), t = £ - 5, (3.4.31) holds. P

x

N e x t , byfi it is possible to find such a > 0, a > 0 t h a t for any x' EE C x

5

V €

3

l P

(x),

Cp(y) {x,x')<5

P

u

p{y,y')<6,.

(3.4.33)

Class of pursuit-evasion

102

games with optimal

open-loop

strategy

Introduce the notation S = min

<7i,
2

(3.4.34)

2l

Consider the strategy u'{-} for Player P that is an ordered pair (o-,a), where o* is a p a r t i t i o n of the interval [0, oo) by the points w i t h the step equal to S < S and ct is a m a p which associates the state f , x(to), y(to) w i t h an a r b i t r a r y admissible o p e n - l o o p control u ( i ) , t € [ i o , ' i ) CO = 0, x(t ) — x , y(t ) = yo), l then coincides w i t h the map a ' w h i c h associates the state (t*,jr{ii),!/(**)), k > 1, w i t h an admissible o p e n - l o o p control u(t), t € [tk,tk+t) transferring the point x(t ) to such point x = x(t +i) that 3

0

0

2

0

a

0

n

(

t

k

min

0(x(tk^)Mh),n=

(3.4.35)

Q(x',y(tk),i'),

where £' = I — St. T h e n , the map Q is an o p t i m a l strategy for P l a y e r P in the game rs (x(6 ) y,£'). Moreover, assume t h a t Player E's strategy «"{•), under which a p a r t i t i o n of the time interval [0, 0 0 ) is chosen w i t h an a r b i t r a r y step 6 and a m a p coincides w i t h the o p t i m a l strategy for P l a y e r E in the game T^yJ). From the o p t i m a l i t y of the strategy v'(-) i n the game Ts (x,y,£'). for any strategy u(-) of Player P follows 3

3 }

a

3

(3-4.36)

®(x,yJ)
For u(-) = u-(-) (3.4.36) takes the form &{x,yj) T h e fact that u'(-)

< &*,»,«;(•),<(•))•

(3-4.37)

is an o p t i m a l strategy in the game T {x(6 },y,£'} S3

3

e ( * ( « ) , y , 0 > £ ( * * , « * ( . ) . « ( • ) ) - 63,

implies (3.4.38)

3

where t' (x,y,u'(-),v{-)) = r is the approaching time for the points x(t), y(t — 0 3 ) on a distance t' from the initial positions as x and y i n the situation l s3

Next rt»(T),if(T))

< /»(*(T),jf(T - S )) + p ( „ ( r - <5 ),y(r)). 3

3

However, S < S a n d , based on the choice of S we get z

2

2

O p t i m a / t i m e pursuit games

103

Thus, (x(T),y(r))


P

(3.4.39)

+ 6, =t.

implies

F r o m (3.4.32) we have (3.4.41)

Q(x(6 ) y,e')
F r o m (3.4.41), (3.4.38) a n d (3.4.40), a n d t a k i n g i n account t h a t S < |, we obtain 2

®(*,yj)

- 6

> t (x,y,<(-)X-)) n

(3.4.42)

T h e i n e q u a l i t y (3.4.42) holds for any Player E's strategy i n the game r(x,y,().

S u b s t i t u t i n g u(-) = v'(-) i n (3.4.42) we get *<>,,,,<(•),!,;(.))

(3.4.43)

- < < Q(x,y,e).

Using (3.4.43), (3.4.37), (3.4.36) a n d (3.4.42), we find - e < 0(x,y,e}

< t (x,y,u;(-U;(-))

< 9 ( x , y, I) + e < t h O ,

«(•)> < ( - ) ) + e,

t (x,y,u:(-)M-)) n

<

u

(3-4.44)

T h u s , the s i t u a t i o n (u*(-)i " « ( " ) ) ' the ( - e q u i l i b r i u m p o i n t in the game a n d Q(x,y,£) is the value of the game. s

r(x ,£), • >y

R e m a r k . W e may a b a t i d o m the a s s u m p t i o n a b o u t the existence of m a x m i n t {x, y, u(t),v(t)) e

n

and

min

Q{x\y i) t

i n t r o d u c i n g the quantities 0 ( z , j/,f) = supinf f n ( x , j / , u ( i ) , T ; ( i ) ) , "(0 sup

0(x',y,().

In this case, the t h e o r e m s i m i l a r to T h e o r e m 6 is also v a l i d . Because of c u m bersome n o t a t i o n s , i t s precise f o r m u l a t i o n a n d proof are o m i t t e d here.

104

Class o f p u r s u i t - e v a s i o n games with optima.! open-loop

3.5

strategy

Necessary and sufficient conditions for existance of optimal open—loop strategy for player E

I D this section, we restrict ourselves to the p u r s u i t games of prescribed durat i o n , although all of its results are extended to cover the o p t i m a l time pursuit games. Let r ( x , i / o , ' ) he a discrete game of pursuit w i t h the (6 = — t ) with prescribed d u r a t i o n T and w i t h d i s c r i m i n a t i o n of P l a y e r E from the initial states x , y T h e n the following theorem holds 4

k

0

0

0

Theorem 7 = Va^^^1>o,^/o,7 ),

PT( O,VO) y £ R

if and only if for all x , 0

0

s

0

and T = 6k, k = 1 , 2 , . . .

=

h(xo,yc) ( ValT (x ,y ,T)

n

max

min

6

(3.5.2)

p -s{x,y) T

is the value of the game V (x ,

a

(3.5.1)

,

X

0

y ,T)). 0

T h e proof of the theorem is prefaced w i t h the following l e m m a . L e m m a 3 For any x ,

y

0

0

£ R" and T > 5, the following

pT(xo,yo)

<

max min »6C-£(iro)»<€C£(*«)

P r o o f : B y the definition of the function pT(x,y), max

=

max

V€C' M

l6

E

For a l l ( £ C (x ) for any x £ C {x ), 5

s

P

0

P

0

min

PTS(X,V)

min max c f , ( x ) sec%-%) 0

inequality

prslx.y) we have =

min p(x, 5). secj-'w

we have the inclusion Cjr\x) y £ Cj- (j/)

C C£(x ). 0

Consequently,

S

min

p(x,y)>

min

p(ar,y).

p(x,jj) >

max

min

T h e n for any a: £ C ( x ) P

max

0

min

is satisfied

p(i,fi).

Existance

of optimal

open-loop

strategy

105

for player E

Thus max >

min

max

Pr~s(x,y)

max

v6C*(s„)

5 e C

min

>

p(x,y)

=

f-' )i6Cj(x )^ ( v

0

T h i s completes the proof of the l e m m a .

•

W e now prove the theorem. Proof:

Suppose the (3.5.1) is satisfied but the (3.5.2) not. T h e n ,

Necessity.

by the previous l e m m a , there exist such x , pTo{zo,yo)<

max

Denote x°(t)

mm

0

0

0

(3.5.3)

pr _i{x,y). 0

VEC7J.{ )i£C*(i )

— x(t\x , u ° ( ' ) ) , where u°(-) 0

0

n

0

w

the game rs{x ,yo,T ).

T = Sk , k > 1 t h a t

y £ R,

0

0

is an o p t i m a l strategy of Player P in

E v i d e n t l y , there is such point j* £ C {y )

0

E

mm

p -i(x,y-) To

max

=

min

for which

Q

(3.5.4)

p - {x,y). Ta

6

Let u ° ( - ) , 5°(-) be o p t i m a l strategies i n the game ri(x°(S),y',T

— 6).

We

focus on the following strategy ti(-) for Player E; at the instant t = 0 he chooses the function v £ i ( [ 0 , 5], V ) such that the motion generated by this function transfers P l a y e r E from the state y

0

y* = y(S;y ,v) 0

to the state y' in the time equal to 6, i.e.

a n d s t a r t i n g f r o m the instant ( = 5 Player E plays the strategy

«"(•).

'

Denote by fi (-) a restriction of the strategy u°(-) to the interval [6, To]. 0

F r o m (3.5.1), (3.5.3), (3.5.4) we find « i ( * o , l t o ) > K(u\hu°(

)>^y^T )

= K-(fi (.),5°():*»(*).»'.ro-*) 0

>

min

fa-i{x,y')

=

max

=

0

min

>

p -s(xo{6),y') To

pT„(x ,y ) 0

0

>

> p { o,yo)Tc

x

T h e c o n t r a d i c t i o n o b t a i n e d proves the necessity of the c o n d i t i o n (3.5.2). Sufficiency.

N o t e t h a t c o n d i t i o n (3.5.3) is an equation for the value func-

tion of the discrete finitestep game r (xQ,y , e

T h e o r e m 2, C h . 2). T h e f u n c t i o n h( >y) x

a

T) (see T h e o r e m 7, C h . 1, a n d

satisfies the Eq.(3.5.2); hence it is

the value of the game T$[x, y, T ) , T h i s proves the theorem.

•

Class of pursuit-evasion

106

L e m m a 4 / / an optimal function

games with optimal

open-loop

strategy (i.e.

of the time only) for Player

is necesary and sufficient

strategy

the strategy which

E is to exist in the game T(x ,

=

p (x ,y ). T

T h e proof follows from the definition of T h e game r(x ,y ,T)

0

0

pr{x ,y ). 0

0

is a p p r o x i m a t e d by the discrete games r ( x , y ,

0

s

T h e o r e m 8 If for any x ,

e R,

y

0

T >.0 in the game T(za,yo,

n

0

0

0

E

that for

£ R", y £ R", T > S 0

=

pT(xo,yo P r o o f : Sufficiency.

T).

0

T) Player

is to have an optimal open-loop strategy, it is necessary and sufficient and any x

it

that 0

anyS>0

is the

yo, T),

0

ValT(xo,y ,T)

0

open-loop

max

min

PT-S{ ,

(3.5.5)

y)

x

W e show t h a t the c o n d i t i o n (3.5.5) implies the equality W < * Q . t t o ) = Vair{x ,y ,T) 0

(3.5.6)

0

E v i d e n t l y , P l a y e r E has an o p e n - l o o p strategy w h i c h ensures the payoff the least pr( o,yo)

since for any e >

x

payoff K(u(-),

v*(t); x ,y ,T) 0

0 a n d any strategy u(-) where v'(t)

> p (xo,yo),

0

T

of P l a y e r P the

is o p e n - l o o p control

transferring P l a y e r E from the state yo to the state y'

£ C (yo)

(y'

E

is the

center of p u r s u i t ) such that min

p(x,y')

=

max

mm

p{x, y) = p {x , T

y)

0

0

Prove that for any € > 0 P l a y e r P has a strategy which ensures that he will loose not more than pr{ o,

yo) + £• F i x e > 0. Consider the following strategy

x

u (-) for P l a y e r P : P l a y e r P chooses & > 0 and an a r b i t r a r y o p e n - l o o p control fi

U i ( t ) , t € [0,5) a n d , s t a r t i n g from the instant 6, he pursues the point y(t — 6} in the game F j ( x ( f i ) , y , T — 6) where y(t) is P l a y e r E ' s m o t i o n . 0

Because of the continuous dependence of the sets Cp(x ),

Cg()/o) on x ,

0

0

yo,

T, we have that there is S > 0 such that \PT-s,( ( i)^ya) x s

~

fa( o,yo)\

and there is S > 0 such that for all y £ C g 2

p{y,y')

< j - Set S = m i n { 5 i , 5 } . 0

2

game P j ( a : ( 5 ) , ( / , T — S ) 0

0

a

x

- 8

<

|,

" (jfo) a n d y' £ C (y)

the distance

E

Since the strategy u "(-) is o p t i m a l i n the s

(see T h e o r e m 7), then it ensures, i n this g a m e , an ap-

0

proach to P l a y e r E (y(t—S )) on a distance not more t h a n prs, 0

yo}- T h i s

( (Sj), x

implies an approach to P l a y e r E on a distance not more than px-6„(x(S ), 0

J/o) +

E x i s t a n c e of optimal

open-loop

strategy

E

for player

107

\, since it follows f r o m the choice of b~ that i n a t i m e S he cannot cover a distance more t h a n g. However, \pT-s (x(6 ),y ) - P T ( * O , ! / O ) | < §• T h e r e fore, P l a y e r P ensures an approach to P l a y e r £ on a distance not more t h a n PT(ZO, VO) + «• T h i s completes the proof of the sufficiency. 0

0

0

0

0

Necessity. A s s u m e t h a t P l a y e r E has an o p t i m a l o p e n - l o o p strategy. A l s o , suppose t h a t 6 > 0 a n d there are x , y £ R a n d T such t h a t 0

PT (X ,3/O)< 0

0

n

0

0

max

0

min

(3.5.7)

PT -s (x,y) B

0

Because of l e m m a 3 inequality of opposite sign is not possible. T h e n P l a y e r E has the strategy v'(-): at the instant t ~ 0 he chooses the o p e n - l o o p control u ( i ) , ( G [0,fi ] t r a n s f e r r i n g y o

min 'f&?

0

PT -h[ 'y') x

a

(x ) 0

to y " , where y' is such t h a t ™

= y

min

a x

hi-h(*ty),

6C7j (vol z£C>* (x ) 0

and from the i n s t a n t f = 5 he plays the o p t i m a l o p e n - l o o p strategy v'{t) i n the game r(x,y",T — S ), where x is the state in which P l a y e r P appears at the instant t — S . Hence for any strategy u(-) G P 0

0

0

=

*(»(•), »*(-); =

K(u(-),v'(t);x(6 ;x M-))y,T -6 )> 0

> where u(-)

min

he-toi ^*) 1

0

0

0

(3.5.8)

> PT<,(xo,yo),

is a r e s t r i c t i o n of the strategy u(-)

to the interval [t5 ,T ]. 0

0

By

L e m m a 4, the i n e q u a l i t y contradicts the o p t i m a l i t y of o p e n - l o o p strategy. T h i s completes the proof of the theorem.

•

B y e m p l o y i n g T h e o r e m 7, we derive a p a r t i a l differential equation for the value f u n c t i o n of the game.

T h e conditions of T h e o r e m 3 are assumed to be

satisfied for the g a m e P ( x , y , T ) . T h e n the function pj(x,y) game T(x,y,T)

w i t h d u r a t i o n T from the i n i t i a l conditions

A s s u m e that i n some region of the space R pr(x,

n

is the value of the x,y.

x R" x [0,oo) the function

y) has continuous p a r t i a l derivatives in all its variables. Since pr(x,

y) is

independent of £ , n then Eq.(3.5.5) may be r e w r i t t e n as max Let £ G C (y), 6 E

n G C {x). p

m i n [pr(x,y)

- & • - < ( { , » ) ) ] = 0.

T h e n there is the p a i r of controls u(f), v(t)

(3.5.9) which

transfers the p o i n t s y a n d x, respectively, to the states F a n d n i n the t i m e 8. Let x(t),

y(t)

be relevant trajectories. In this case ( = f f{x{t),u{t))dt Jo

+ X,

108

Class of pursuit-evasion

•/=

games will} optimal

f 9(y(i)At))dt Jo

open-loop

strategy

(3-5.10)

+ y.

D i v i d i n g b o t h sides of the Eq.(3.5.9) by S > 0, u s i n g Eq.(3.5.10) a n d letting S —> 0, we o b t a i n dp

under the i n i t i a l condition

3p

f

.

=

pr{x,y)\T~o

= 0,

(3.5.11;

p{ ,y)x

A s s u m e that we have somehow succeeded i n defining u, v, w h i c h gives max and m i n i n Eq.(3.5.12), as functions of x,y,T

and J | ,

i.e.

S u b s t i t u t i n g the (3.5.13) i n Eq.(3.5.12), we get

provided that K, x

T h u s , to define pr(x,

V: )\T=O T

= p(x,

(3.5.15)

y)

y), we have the C a u c h y p r o b l e m for the p a r t i a l differential

equation of the first order Eq.(3.5.14) w i t h the initial c o n d i t i o n (3.5.15). The Eq.(3.5.14) has been derived independently by various authors (see [ l , 33, 65]) and is called the Isaacs equation. A s s u m e that p a r t i a l derivatives of the second order of the function p exist then solution to the C a u c h y problem for Eq.(3.5.14) can be o b t a i n e d by the m e t h o d of characteristics that are of the form

dpx,

A

dfi(x,u{x,y,p )) x

dx - j r = 3i {y>v{x,y,p )),

»= l,...,n,

y

D

.

3

P»,

y

%(j/,u(3r,y,^)),

dt

£

%

(3.5.16)

E x i s t a n c e of optimal

open-loop

strategy for player E

109

Here dxj/dt, dp /dt, dy jdt, dp Jdt are the time derivatives along the o p t i m a ! trajectory. T h e derivation of Eq.(3.5.16) may be found i n [1], where the equations of characteristics are shown to determine o p t i m a l traectories for players. T h e i n i t i a l conditions for integration of equations i n (3.5.16) are obtained from (3.5.15). Xj

3

y

For the o p t i m a l t i m e p u r s u i t game the equation (3.5.15) takes the form

(3.5.17)

under the i n i t i a l c o n d i t i o n © ( s , y , O U * . » ) = ' = 0.

(3.5.18)

Here, as i n the previous case, the continuous p a r t i a l derivatives of the first order of the function Q(x,y,l) i n x, y are assumed to exist. A s s u m i n g t h a t it is possible to define u , ti, w h i c h carry over max and m i n in Eq.(3.5.6) as functions of x, y, i.e.

we rewrite equation (3.5.17) i n the form

provided t h a t e ( * . y . 0 U * , v > = ' = °-

(3-5-20)

T h e d e r i v a t i o n of equation (3.5.17) is o m i t t e d here, since it is similar to the derivation of equation (3.5.14) for the p u r s u i t game w i t h prescribed d u r a t i o n . B o t h C a u c h y p r o b l e m s (3.5.14), (3.5.15) and (3.5.17), (3.5.18) are nonlinear w i t h respect to p a r t i a l derivatives, since their solution poses serious problems. T h e differentiability of functions p a n d 0 presents a very fine a n d c o m p l i cated p r o b l e m . N . N . K r a s o v s k y has shown the differentiability of function p in the s o - c a l l e d regular case [10].

Class of p u r s u i t - e v a s i o n games w i t h optima] o p e n - i o o p strategy

110

3.6

Iterative methods for solution of differential game of pursuit

Let r ( x , y , T ) be a discrete form of the differential game F(x,y,T)

of dura-

s

tion T > 0 t e r m i n a l payoff M(x(T),y(T))

w i t h a fixed step of t i m e - i n t e r v a l

p a r t i t i o n 8, Player E being d i s c r i m i n a t e d for the t i m e 5 > 0 ahead. by Vs(x,y,T)

the value of the game r * ( x , y, T} . 2

\)mV {x T) 6

=

iyi

Denote

Then

V(x,y,T)

and o p t i m a l strtegies in the game r ; ( x , y , T ) w i t h sufficiently s m a l l 5 can be effectively employed to construct E - e q u i l i b r i u m points i n the game

Ts{x,y,T).

W e now expound the m e t h o d . Z e r o — o r d e r a p p r o x i m a t i o n . A s a zero-order a p p r o x i m a t i o n of the value function of the game Vg(x, y, T), we take the function max

V °(x,y,T)= 6

where Cp(x),

m i n A/(£,r>),

(3.6.1)

are the reachability sets for the players P and E from the

C [y) E

initial states x, y £ / J

7 1

by the time instant T.

T h e choice of the function V$[x, y, T) as an i n i t i a l a p p r o x i m a t i o n is justified by the fact that i n a sufficient broad class of games (a " r e g u l a r case") it proves to be the value of the game T(x, y, T) (see in 2, 5 i n this chapter). T h e following a p p r o x i m a t i o n is constructed by this Tule V (x,y,T) s

l

V?(x,y,T)=

=

max

min

V ° ( £ , n , T — 6),

max m i n V ({, ft T - 6), nec£( ) «
(3.6.2)

x t

v

V?{x,V,T)=

max

min

Vt^tn^

- S)

w i t h T > 5 and V ( x , y, T ) = V ? ( * , v , T ) , k = 1, 2 , . . . , w i t h T < S. e

fc

A s we may see f r o m the formulas (3.6.2), the operation m a x m i n is taken w i t h respect to the reachability sets C (y), C {x) for the time 8, i.e. for one step of the discrete game T(x,y T). E

P

l

T h e o r e m 9 The sequence of function ing. ' T h e terminal payoff

on fl" x R"

is

equal

{Vg (%,$,$}) is monotone

to M(x(T), y(T))

where

M(r, y) is

a

nondecreas-

function continuous

Iterative

methods

for solution

of differential

P r o o f : W e first prove the i n e q u a l i t y

game of

a n d V °(x,y,T),

J s

For a l l ( e C (x) there is C ? ~ ' ( 0 C - (r,), £ € C {x)

min

C Cj{x).

P

T 6 E

s

max

mm

111

3

B y the definition of the functions V (x,y,T)

— max

pursuit

we have

Mff.n) Consequently, for any r) €

P

min

Hence we have t h a t for any £ € max

min

> .min

M{i,T))

/W(f,if)

C {x) P

M ( £ , n) >

max

min JW(f,n).

Therefore, i n p a r t i c u l a r , max

mm >

max

min min

M(f,n)

>

Af(xi,Tj).

Thi V,'fx,y,r) =

> =

max

max.min

max

min

max m i n Jtf(£,rj) = nec%(yi cecj(x)

if,T-«)>

Mif.fi) V°(x,y,T),

i.e. A s s u m e that for I < k the following inequality holds

V?{x,y,T)>Vr\*,V,T).

(3.6.3)

T h e proof of this inequality is given here only for the purposes of completeness, since it reproduces the one for Lemma 3. 3

112

Class of pursuit-evasion

games with optimal

open-loop

strategy

W e prove that V/* (*,J,T')> tf(*,l..T). 1

(3.6.4)

1

B y definition, V {x,y,T)

max

=

k+1 s

V (x,y,T)

max

=

k

min min

V}fa* T-S), t

ltf-»(fc*r-S).

(3.6.5)

F r o m (3.6.3), and using (3.6.5), we obtain the required inequality (3.6.4). We have thus proved that the statement of the theorem holds at each point (x, y, T) in the case T > 6. In the case T < 5, however, the statement of the theorem is obviously seen. T h i s complete the proof of theorem. • T h e o r e m 10 The sequence {V (x,y,T)}

converges in a finite number of steps

k

N, with the estimate N < [ j j + 1, where the brackets stand for the greatest integer. P r o o f : Let N < [ j ] 4- 1. Show that (3.6.6)

V "(*,V,T)-Vi'+ {z,y,T). l

l

T h e expression (3.6.6) is obtained from the construction of the sequence {V (x,y,T)}. k

Indeed,

= max

max

min

min

max

Vjtf"-

... - (N - 1 )8).

,n ~\T

1

N

Similarly, we get =

V *'(x,y,T) s

N

max

min

max

min

max

- IN

V?(f, -\y -\T N

...

N

-1)6).

However, T - (N - 1)6 = a < 6, therefore

Vi{f-\t, ~\T-{N-l)6) N

= V (( -\r, -\T 2 s

N

N

- (N - 1)5) =

= V?(£ -\y - ,a), W

v

1

whence follows (3.6.6). T h e coincidence of members of the sequence E q . (3.6.2) for k > N is obtained from Eq.(3.6.6) by i n d u c t i o n . T h i s proves the theorem. •

Iterative

methods

for solution

of differential

game of

pursuit

T h e o r e m 11 The limit of the sequence {V {x,y,T)} of the game T (x,y,T). s

coincides

K

113 with the value

e

P r o o f : B a s i c a l l y , T h e o r e m 11 is the corollary of T h e o r e m 10. Indeed, let V (x,y,T)

=

s

l i m V {x,y,T). s

(3.6.7)

k

Since the convergence takes place i n a finite number of steps not exceeding +

then i n the recurrent E q . ( 3 . 6 . 2 ) it is possible to convert to the

limit as k —t oo. T h e l i m i t i n g function V {x,y,T)

satisfies the equation

6

V {x,y,T)

max

=

s

min

V {(,jj,T

(3.6.8)

- 6)

6

under the i n i t i a l c o n d i t i o n Vs(x y,T)

\
t

0

=

max

min

Af(f,n),

which is a sufficient c o n d i t i o n for the function V$(x, y,T) the game

to be the value of

T{x,y,T).

W i t h knowledge of the function Vs(x,y,T),

a n d using the E q . ( 3 . 6 . 8 ) , we can

construct o p t i m a l piecewise o p e n - l o o p strategies i n the game Fs(x,y, T).

The

E - o p t i m a l strategies i n the basic game T{x, y, T) are constructed w i t h the help of strategies t h a t are o p t i m a l i n the game Fs[x,y,T)

(see 2, 5 in this chapter).

A s is clear f r o m ( 3 . 6 . 2 ) , the coincidence of two successive a p p r o x i m a t i o n at the steps k a n d k + 1 means that the corresponding a p p r o x i m a t i o n is the value of the game Fs(x,y,T), coincide w i t h the k-th

since in this case all subsequent a p p r o x i m a t i o n s

a p p r o x i m a t i o n . Such a coincidence is a c r i t e r i o n for

termination of c o m p u t a t i o n s . W e have every reason to say that i n the broad class of problems the convergence occurs faster t h a n i n the time mentioned in T h e o r e m 11.In p a r t i c u l a r , the c o m p u t a t i o n i n the " r e g u l a r case" terminates at the first step after the f u n c t i o n V / ( x , i / , T) has been computed (at the same time, this provides a " r e g u l a r i t y " c r i t e r i o n ) . W e w i l l m o d i f y the above m e t h o d of successive a p p r o x i m a t i o n s . A s an i n i t i a l a p p r o x i m a t i o n , we take the f u n c t i o n V^{x, y, T) — where V °(x y,T) s

y, T ) ,

is defined by ( 3 . 6 . 1 ) . T h e following a p p r o x i m a t i o n is con-

t

structed by the rule V, (x,y,T) k+,

=

max

max

for T > 5, where N = f , a n d V \x,y,T) k+

min

V ? ( { , 17, T - i6)

= V °(x,y,T) s

for T < S.

(3.6.9)

114

Class of pursuit-evasion

games with optimal

open-loop

strategy

T h e statements of the theorems 9-11 holds for the sequence of functions {V (x,y,T)), as well as for sequence of functions {V (x,y,T)}. These statements for the sequence of functions {V (x,y,T)} are proved in m u c h the same way as similar reasonings for the sequence of functions {V (x,y,T)}. The functional equation for the value function of the game Ts{x, y, T) in the region { ( i , u , T ) | T > 5} is of the form k f

k

t

k

k s

= max

V(x,y,T)

max

min

V(£,n,T

(3.6.10)

- iS),

where N = j, and the i n i t i a l condition remains the same,i.e. V(x,y,T)\

=

T
max

min

M((,,n)

W e prove the equivalence of Eq.(3.6.8) and Eq.(3.6.10). T h e o r e m 12 Eq.(3.6.8)

and Eq.(3.6.l0) T

are

with the initial

min

V(x,y,T)\ < = s

•

min

condition (3.6.11)

M((,n)

equivalent.

P r o o f : Suppose the function V {x,y,T] satisfies E q . (3.6.8) and initial condition (3.6.11). W e show that it satisfies E q . (3.6.10) i n the region {(x, y, T)\T > 6

Indeed, since V (x,y,T)

satisfies (3.6.8), then the relationships

s

max

V (x,y,T)= s

= >

max

min

max max *ec> {y) nec M E

=

...>

E

max

max

holds in the region {(x,y,T)\T Vi{x,y,T)=

min

max

min

V ((,n,T

- 6) =

6

Vdl, rj,T - 26) >

min m i n Vs(L n, T — 26) = (ec {*) £ec<<£) p

min

min > 6}. max

VSILTI.T-%$)

V (£,n,T-iS) t

£

...

>

...

Since the equality min

V(£, n, T -

6),

Iterative

methods

for solution

of differential

game

115

of pursuit

is satisfied for i = 1, then the equality V&(x,y,T)

= max

max

min

V(f,n,

T -

8),

where N = j , holds, w h i c h proves the required statement. Now let the function V {x,y,T) i n the region {(x,y,T)\T > 6} satisfy E q . (3.6.10) a n d i n i t i a l c o n d i t i o n (3.6.11). W e show that it also satisfies Eq.(3.6.8). Suppose the opposite is true. T h e n from (3.6.10) we find s

max

Vi{x,y,T)> In the region {{x,y,T)\T

min

>

max

=

max

(3.6.12)

V {(,rj, T - 8). s

However,

> 8}. max

— max

min

min

max max

V (f ,r>,T - 8) = 6

max

min

K (£, fj.T - (i + 1)6) >

min

min

Vs(l, ij, T — (i + 1 )8) =

max max max min m i n Vs(£, V. T — (i + 1)5) = •eli^-il^c^fiec^Wfg^Wf-ecjfif) ' v

=

max

max

min

V [(.n.T s

- i5) = VAx.y,

T),

since, by (3.6.12), the rigorous inequality holds for ! = 1. A s a result, we get a contradiction which completes the proof of the theorem. • C o n s i d e r now the o p t i m a l time pursuit game T(x,y). As is seen from 4, C h . 2, the existence of the (, u - e q u i l i b r i u m points in the game T (x, y) for any e > 0, 8 > 0 is connected w i t h the solution of the game F(x, y,T) w i t h prescribed d u r a t i o n T , w i t h the payoff equal to w = min <,<7 p(x(t), y(t)). In the game T{x,y, T) w i t h perscribed d u p a t i o n , by the solution is c o m m o n l y meant the ( - e q u i l i b r i u m point. For any e > 0,the existence of the ( - e q u i l i b r i u m point and the existence of the game value for the games with perscribed d u r a t i o n is proved under sufficiently general assumptions in 3, C h . 2. l

0

Let V(x,y,T) be the value of such a game. F i x the i n i t i a l state x, y £ R" and consider the function w(t) where w(t) C h . 2).

V(x,yJ)

is a continuous non-increasing function w i t h t £ [0,oo) (see 4,

L e t Vs{x,y,T)

be the game w i t h prescribed d u r a t i o n T w i t h the

payoff w a n d the value V (x,y,T), 6

time 8 > 0.

=

where Player E is d i s c r i m i n a t e d for the

116

Class of pursuit-evasion

games with optimal

open-loop

strategy

Based on 3, C h . 2, w (t) s

=

V (x,y,t)
hmV {x ,t) 6

=

>y

V(x,y,t).

0—*(j

Denote by r|(ar, y) (see 4 i n this chapter) the o p t i m a l time game up to the ( - c a p t u r e instant, where the evader is d i s c r i m i n a t e d for the time S ahead. Assume that the values of the games T'(x,y), and T'(x,y) exist are finite and are equal, respectively to V and V'{x,y). T h e n the following theorem holds. e

s

T h e o r e m 1 3 lims-.o V '(x,y)

= V {x,y)

Proof:

at each point {x,y)

e t

s

A s is evident from T h e o r e m 3, C h . 2, V'(x,y)

e R

n

X R*.

and V£(x,y)

are the

m i n i m u m roots of equations V(x, ,T) for fixed

(3.6.13)

= £, V
V

>Vi

x,y iv(T)

= V(x,y,T)

> V (x,y,T) s

= w (T) s

(3.6.14)

(3.6.14) and the functions w(T), u>s(T) are m o n o t o n i c a l l y nonincreasing. Since V (x,y) and V'(x,y) are the m i n i m u m roots of (3.6.13), then there are such a > 0, £*[ > 0 that on the intervals [ V ( z , y ) - a,V (x,y)], [V/(x,y) Oti,V (x,y)] the functions w(T) and u)j(T) are s t r i c t l y descreasing. T h e n we have l i m w (T) = wlT). t

e

s

e

Therefore, for any a > 0 there are such Si > 0 an T € [V{x, that w (r) > w(V (x,y)) = t,

y) - a, V (x, e

y)]

l

h

and since w (V (x,y}) < w(V'(x,y)) = t, then the m i n i m u m root of equation u>s,{T) - ( belongs to the interval [V(x,y) - a, V'(x, y)\. Consequently, V \{x,y) also belongs to this interval. Since a may be chosen a r b i t r a r y small, and the sequence {V${x,y)} is monotonically non decreasing i n S, then 6l

e

s

\imV '(x,y)

=

6

V'(x,y).

T h i s completes the proof of the theorem.

•

T h e o r e m 13 suggests that the sequence {V (x,y)} imation of V'(x,y). s

e

can be used for approx-

F i x a p a r t i c u l a r S > 0. T h e c o m p u t a t i o n of V'{x, y) is a sufficiently tedious operation, since it involves the solution of discrete Isaacs e q u a t i o n . W e suggest the recurrent procedure of finding V '(x,y) s

Iterative

methods

for solution

of differential

117

game of pursuit

Let l ( x , y ; u ( i ) , ! > ( ( ) ) be the f u n c t i o n a l , that is defined for any admissable o p e n - l o o p control tt(t) a n d v(t) a n d is equal to the t i m e to the ( - c a p t u r e instant, f r o m t h e i n i t i a l states x, y (E R", if t h e ( - c a p t u r e occurs when the controls u(t) a n d v(t) are used, otherwise i t equals oo. N e x t , let n

Q\x,y)

=

u inU (x,y u(t)At)Y

S

?

n

>

As a z e r o - o r d e r a p p r o x i m a t i o n , we take

Vl (x,y) =

Q (x y). i

0

l

T h e choice of zero-order a p p r o x i m a t i o n is justified by the fact that in some cases this provides the value of the game (see 4 i n this chapter). T h e second a p p r o x i m a t i o n is constructed by the rule V£(x,I,)=

sup

inf V&(£,n) + *

(3.6.15)

for ( z , y ) £ L a n d V / , ( i , y ) = V / ( x , ! / ) for (x,y) 6 L , where L = {{x,y) € 0

0

0

0

R"xR"\V (x,y)<6}. f sp

A s i n the proof of a s i m i l a r statement i n 5 of this chapter (see L e m m a 3), we m a y show t h a t for any states x y and for any £ and 5 G (0,Q'(x,y)), the following i n e q u a l i t y holds t

t

sup

e'(x,y)<

i n f 0 ' ( £ , >?) + *-

Hence T h e a p p r o x i m a t i o n k + 1 is constructed by the rule VUtfrv)

=

S

U

jsf, Mk(i>*)+*

P

(-- ) 3

6

16

for (x y) 6 L a n d Vl {x,y) = Vl {x,y) for (*,$,) G L , where = {(x,y) R" X R \V' {x,y) < (k + 1)6}. T h e construction of the sequence { 6.ki V {x,y). E v i d e n t l y , the sequence {Vlk(x, y)} y

v

x

e

k

k+1

n

k

k

k

4 1

l 6 ik

for (x,y) e Li converges i n not more than i steps, and the i - t h a p p r o x i m a t i o n coincides w i t h the value of the game T\(x,y). Indeed, i n the passage i n Eq.(3.6.14) to the l i m i t as k -* oo at the point (x,y) e Li (the latter is possible because of the convergence of the process i n a finite n u m b e r of steps), we get V (x,y)= t s

sup

i n f VM,T})

+ §

(3.6-17)

118

Class of pursuit-evasion

here for (x, y) £ L

games with optima!

open-loop

strategy

0

V (x,y) l e

=

Q (x,y) t

However, Eq.(3.6.17) w i t h a suitable i n i t i a l condition on the set L provides a sufficient c o n d i t i o n for Vg(x y) to be the value of the game (x,y). T h u s , the following theorem holds. 0

t

T h e o r e m 14 Let (x,y) 6 Li and k be the first step at which V ' (x,y) V£ (x,y). Then for alli> k s k+1

=

k

Vli(x,y)=Vl (x,y) k

=

V<(x,y),

where V$ (x, y) is the value of the game. K n o w i n g V£{x,y) a n d using Eq.(3.6.17), we may find the e , 5 - o p t i m a l strategies for the players P a n d E, as it has been done i n 4 of this chapter.

Chapter 4 Examples of differential games of pursuit 4.1

Games with prescribed duration without phase constraints

T h i s chapter studies differential games o f p u r s u i t whose solution is based on the results presented i n C h . 3. Example

1. L e t the reachability sets for t h e Player P and E be such that max

m i n MU,n)

=

min

m a x MU.y)

(4-1-1)

Let (\ Hhe an a r b i t r a r y pair of points at which m a x m i n is achieved in (4.1.1). T h e n by T h e o r e m 1, C h . 1. m i n m a x is also achieved i n the same points. In the latter case, the point // satisfies the first c o n d i t i o n of invariance. Indeed, for all 0 < t < T t h e p o i n t , f belongs to the set Cp~'{x'(t)), a n d the point H belongs to t h e set Cg~*(y'(t)). Moreover, from T h e o r e m 1, C h . 1, for all V G C E O ) . f G Cp{z) we have t

t

Since for ( € [0,T] C%~*(y*{t)) C C £ ( j / ) , £ ? " * ( * " { * ) ) P ( ) > then the above inequality also holds for a l l n g C £ ( j / * ( t ) ) , i G (#"*(**(*)). B y a p p l y i n g again T h e o r e m 1, C b . 1, we o b t a i n c

C

X

-(

max

min

M((, n) =

min

max

M{£, n) = M(A, / / ) .

T h e l a t t e r relationship shows t h a t the first c o n d i t i o n for invariance o f the point / / is satisfied. 119

E x a m p l e s of differential

120

games of

pursuit

W h e n the (4.1.1) is satisfied, the differential multistage game r(x,y,T) converts to a simultaneous single-stage game and it follows from (4.1.1) that such a game has an e q u i l i b r i u m point i n pure strategies. In this case, the optimal strategy for Player P is the choice of the point and the one for Player E is the choice of the point H. F r o m this it follows that i n the corresponding differential game (under condition (4.1.1)) the o p t i m a l strategies for the players employ only the i n f o r m a t i o n on the players' positions at the i n i t i a l instant of the game and on the game duration T. T h e continuous " t r a c k i n g " of the opponent is unwarranted. Example 2. ( simple p u r s u i t ) . T h e pursuit occurs over the entire Euclidean space. M o t i o n equations are of the form

where a: = T h e set x. T h e set T h e payoff

n , n , ^ u - < 1,

Xi = aui,

i = 1,..

Vi^fiVi,

i = l,...,n,

£ « ? < 1 ,

const, 0 = const, a > 0. Cj,(x) is a sphere with the radius aT a n d its center at the point C (y) is a sphere w i t h the radius 0T and its center at the point y. function is defined as follows: E

H(x(T),y(T))

= p(x(T),y(T))

=

£(«i(T)-jB(r))'.

Geometrically, the invariance of the center of pursuit ( the center of the game ) is straightforward, and T h e o r e m 3, C h . 3, is applicable here. Indeed (see the E x a m p l e 1 from 2, C h . 1), p (x,y) T

= p(x,y)-( -0)T a

{p(x y)> t

0),

T h e quantity p (x,y) is achieved at the points Mi,M (see F i g . 5 - 7 , C h . 1), where M is the intersection point for the line of the centers xy(OOi), that is farthest from x(O), and the point M is the point of the set C^(xi) (Si), that is nearest to the point M. T h e conditionally o p t i m a l trajectories for the Players P and E are the straight line segments xMi, (OMi) and yM (O M). T h e first condition of invariance follows from the fact that for any 0 < ( < T the point M(t), t h a t is the center of pursuit w i t h respect to the states x'(t),y'(t),T - t remains on the center line xy(OO ), i.e. it coincides w i t h M. T

x

x

W e now assume that at some instant 0 < t < T P l a y e r E deviates from the conditionally o p t i m a l trajeciory d u r i n g the time 6, and makes a transition to the point y' e C (y'(t)). T h e n the center of pursuit w i t h respect to the E

Games with prescribed sets C p " ' ( V ( t ) )

without phase

duration

a n d C%~ ~ (y'), i

i.e.

s

6iS

trajectory x"(t)

121

the center of p u r s u i t M' i n the game

— t), is on the center l i n e x'(t),

V' (x'(t),y',T

constraints

y'. T h e c o n d i t i o n a l l y o p t i m a l

for P l a y e r P i n this game is a straight line segment of lenght

a(T - t) focussed on

M'.

C o n s i d e r the games V {x"{t since the trajectory x"(t)

- t - a) for 0 < a < 8. In these

+ a),y',T

Bi
games, the center of p u r s u i t M'(a)

is on the center line x"(t

+ a),

y', and

is focussed on M' — i W ' ( o ) , then for all 0 < o; < 8

it coincides w i t h M' = A / ' ( 0 ) — M ' ( a ) , 0 < a < 8. W e have thus proved the second c o n d i t i o n of invariance. Consequently, the value of the game p (x,y)

=

T

p(x,y)-(a-0)T.

T h e o p t i m a l strategy for P l a y e r E is o p e n - l o o p and provides an o p e n - l o o p trnsition to the center of p u r s u i t M.

U s i n g the e - o p t i m a l strategy for Player

P at each instant of t i m e is m i n i m i z i n g the function p w i t h respect to the realized state of the game. the realized point y.

G e o m e t r i c a l l y , this involves the m o t i o n towards

In p a r t i c u l a r , when the e q u i l i b r i u m point is concerned,

this leads to the m o t i o n along the c o n d i t i o n a l l y o p t i m a l straight trajectory focussed on the point M (see E x a m p l e 10, C h 2). If R\ = \xM\\ < \xM\ — R

2

= \xM\ — \yM\, then based on E x a m p l e from

Chapter 1 (see 2, case 2) max

min

ptt.y)

=

min

max

pU.n)

—

prix^y)

the c o n d i t i o n of E x a m p l e 1 are satisfied. Now write formally the Isaacs equation for the " s i m p l e p u r s u i t " game.

It

is of the form dp —

-X = max )

w i t h the i n i t i a l c o n d i t i o n PT(x,y}W=o

dp

X

— K + m m )

= \f(*i - j n )

3

dp -—w,-

+ (*2-jra) a

In (4.1.2), m a x and m i n are achieved for

ui(x,y,p ) s

-

a,dx J

Am

3

.M. U2(x,y,p ) x

(4.1.2)

3«

(4.1.3)

Examples

122

of differential

0

games of

pursuit

+ © ' dy2

and (4.1.2) takes the form dp

dp

+

dxi

i t

dp\\fd£

-0

dyy)

\dy

(4.1.4)

2

w i t h the initial condition

W e now check the continuous differentiability of the f u n c t i o n

dp

X,- - j/i

dp 5

f-

px{x,y):

Xi - J/; y(x,-i„)' +

(4.1.6) (x -y ) a

It follows from (4.1.6) that function px(x,y]

2

s

has continuous derivatives

everywhere except of the surface \/(x,-yi)

2

+ (x -y ) 2

2

2

= 0.

(4.1.7)

T h e surface (4.1.7) corresponds to the case Pr{x,y) — 0, since i n this case x = y a n d Cp{x) D C g ( y ) (/J < a ) . T h u s , the function 07(1,1/) turns out to be a solution to the C a u c h y p r o b l e m for (4.1.4) i n the space region which does not contain the surface the (4.1.7), the latter b e i n g singular for the Isaacs (4.1.4). Note that this singularity has been overcome i n the procedure developed in C h . 3 (theorem 2,3). Example 3. ( d y n a m i c game of p u r s u i t w i t h frictional forces). T h e pursuit takes place over the entire plane. M o t i o n equations are of the f o r m =Pi,

|"| < 1,

Games w i t h

prescribed

duration

without

h pi =

=

aiii

-

ij =

M

i,

s

phase

constraints

1.

<

kppi,

1,2.

i =

p%i -

123

k Si, E

Here q a n d r are respectively geometrical coordinates of the Players P and E , s (p) is a m o m e n t u m of P l a y e r £ ( P ) , a n d k , k are some constants interpreted as friction coefficients. T h e payoff function is defined as follows: P

H(q(T) r(T))

E

= p(q(nr(T))

>

= T'=>

F i r s t consider the case & ^ 0, k the circle w i t h the radius p

R (T) P

E

^ 0. T h e set C j ( t f ) (in the space 9) is

= a k

P

and its center at the point 1 -

q = q+

e-^

p-

T

where q, p are the s t a r t i n g position and i n i t i a l m o m e n t u m for Player P set C (r) (in the space ) is the circle w i t h the radius

The

E

and its center at the point r = r +

s

1 - e**r :

k

E

where r, s are the s t a r t i n g position and i n i t i a l m o m e n t u m for Player E . L e t us make the f o l l o w i n g a s s u m p t i o n :

*>** i >h

(4 L8)

T h e q u a n t i t y PT( ) ' equal to the distance p(M',M) between the point M (the center of p u r s u i t ) , l y i n g on the center line and being farthest from the center of the circle Cp(q), a n d the point M' being nearest to the point M i n the circle Cp(q), and is c o m p u t e d from the f o r m u l a r

s

p (q,r) T

= p(0,0')

+

R

E

- R

P

-

E x a m p l e s of differential

124

Fig.

do not coincide w i t h the

C {r) E

1 _ -i
, _

e

-

pursuit

14.

( i n this example, the centers of circles Cp{q), points q, p), whence we have that

fa(
games of

e

-* T B

=

I ct

e-tpT + k T-\ P

e-^

a

+ kT

T

E

j3—

- 1

t-

2

Let ''*(*) he c o n d i t i o n a l l y o p t i m a ! trajectories. T h e n , to satisfy the first condition of invariance, it is sufficient that along the c o n d i t i o n a l l y optimal trajectories R (T-t)>

(4.1.9)

R (T-t)

P

E

for all 0 < t < T, where Rp(T — t) and R (T — f) are respectively the radius of the circles Cp~'{q {t)) and C | " ' ( r * ( i ) ) (note t h a t the c o n d i t i o n (4.1.8) is also satisfied for the simple p u r s u i t , since in this case Rp(T - t) = o(T -1), R (T — t) = f3[T — (), a > j3). Indeed, suppose there are such instants (i and t that E

-

E

2

Rp(T

- t)

> R {T

-

U),

Rp(T

- t ) < R (T

-

t ).

}

E

2

E

2

T h e n the s i t u a t i o n shown i n Fig.14 becomes possible. Here the center of pursuit has " j u m p e d " from the point A / ( l ) to the d i a m e t r i c a l l y opposite point M(ti). T h e inequality (4.1.9) excludes such a possibility. W e now obtain a sufficient condition for the coefficients a , j3, k , k for w h i c h (4.1.9) takes place. Denote T — t = r. t

P

E

d u r a t i o n without phase constraints

Games with prescribed Let us c o m p u t e

125

R' ,R' : P

E

1 - e = « —

*,
~ ,

k

1 R (r)

= (lL^

B

p-*E

_

k

P

T

,

E

R' {0) = Q, R' (0) = 0. P

E

W e find second derivatives: = ae~ '\

R" {T)

=

R> (T)

k

P

e

fir**.

Moreover, «WT)| _ = O , R" {r)\ T

E

0

T=a

=

p.

F r o m (4.1.8) we o b t a i n R» {0)

>

P

R (0). E

Consequently, i n some neighbourhood of zero flJ(T)

and since Rp(Q)

— R'EW

R" {T),

>

E

= 0, then i n the same neighbourhood R (r)>R! (T). F

Hence R (0)

= 0 a n d for s m a l l T we get

= Rp{0)

E

E

Rp(r)

E v i d e n t l y , if a &P( ) t

>

$ a n d fcp <

R B { T )f°

>

a>0and k

P

> k

E

r

a l l r > 0. (£

>

R {T). E

then c o n d i t i o n (4.1.8) is satisfied, a n d

k, E

Therefore, of interest is proof of (4.1.9) for

> JL).

We w i l l show t h a t i n this case there is always Rpir)

>

(4.1.10)

R! (T). E

Indeed, suppose the opposite is true. T h e n there is such instant r

^(r ) 1

But £

< £

From k

E

= i . (L - e - ^ ' )

- ^

(1 - e - V )

= Bfo ) 1

(see c o n d i t i o n (4.1.8)). < kp follows k r E

l

<

k

P

T

L

,

or e * ' < c £ T

\ whence

kFT

l

that

(4.1.11)

Examples

126

of differential

games of

pursuit

B u t this contradicts (4.1.11), i.e. (4.1.10) holds for a l l r > 0. S i n c e i n the neighbourhood of zero Rp{r)

>

then (4.1.10) implies Rp{r)

RE{T),

>

RE{T)

for all r > 0. W e have thus proved (4.1.9) under condition (4.1.8) for a l l r > 0. T h e second c o n d i t i o n of invariance is satisfied and proved as i n E x a m p l e 2. W e now construct the equation w i t h p a r t i a l derivatives of the first order (see (3.5.12)) for the game involved. It is of the form

-£(&+&]-£(&»+gM + dp

*

+/J m a x >

dp

dp

.

*

—t>i + Q m m >

dp

-5— m

(4.1.12)

W i t h the initial condition t

(4.1.13)

Controls u , 5 from (3.5.13), on which m i n a n d m a x are achieved i n (4.1.12), are determined by the formulas -2L a*.

Ui =

V;

3s,

=

:,

i = 1,2.

S u b s t i t u t i n g S,, 0; into (4.1.12), we o b t a i n the C a u c h y p r o b l e m for equatiurn w i t h partial derivatives of the first order

9 T ~ t

W '

—o

+

~ £

dr~. J S,

3tV

,

+

1

d ? * *

I

"

1

+ 0

EI*

(4.1.14)

£1

w i t h the i n i t i a l condition

M<MO =

£(«

~ r,)

a

(4.1.15)

Games w i t h p r e s c r i b e d d u r a t i o n without phase constraints

127

Introduce the n o t a t i o n s _ s

_

^ = A »

P

-

_ -

d

3 5 ? - * . ' = 1.2.

Characteristics of (4.1.14) are o p t i m a l trajectories in the game of pursuit [lj. Equations of C h a r a c t e r i s t i c s are of the form (see (3.5.18)) * = P i . Pi =

/., ^

a

. r* = s,-,

yfPl +

p

£,=0.

= -p

Sl

T I

-

£

k p,.,

PT = 0,

E

i=

l,2,

W h e n solving the equation (4.1.14) w i t h the i n i t i a l condition (4.1.15) by the method of characteristics, we o b t a i n the previously derived expression »

fa(
/

e

-kpT

_ i

e

-k T

_

E

|*

= &

t

-krT

e

-

r

+

i

k

+

p

T

-

P

i

~ P

S

-k T

l

e

-[«-—M *

s

+

*|

i

^

k T-\\ E

~

J -

T h e function p f r o m (4.1.16) has continuous partial derivatives over the entire region of space except the points l y i n g on the surface

£ ( , _ „ + „ _

\

S

i

_ _ )

=„,

(

4

,,7)

where the p a r t i a l derivatives p „ p , i — 1,2 are not defined. T h e surface (4.1.2) corresponds to the i n i t i a l states, for w h i c h the distance p(0,0'} between the centers of reachability circles is zero, since the expression on the left side of (4.1.12) is e x a c t l y the distance between the centers of reachability circles. T h u s , the function p proves to be a solution to the Cauchy problem for the equation (4.1.14) w i t h the i n i t i a l condition (4.1.15) i n the space region free from s i n g u l a r i t i e s , at these points Cp(q) D C (r) and pr{q,r) = 0. W h e n the condition R ( T ) > R [T) (a > 0, £ > £ ) is satisfied, the results of C h a p t e r 1 (see the T h e o r e m 2, 3) makes it possible to overcome this singularity [27] j u s t as i n E x a m p l e 1. p

ti

T

E

P

E

Examples

128 Consider the case k

F

T h e set Cf(q)

of differential

games of

= ICE = 0 ( the absence of friction) [35] i n some detail.

is a circle with the radius Rp(T)

= or— a n d its center at the

point q = q + pT, where q, p are the s t a r t i n g position a n d i n i t i a l for P l a y e r P . R (T) E

pursuit

T h e set C (r)

momentum

(in the space q, r) is a circle w i t h the radius

E

= 0%£ and its center at the point p m r + sT,

s t a r t i n g position and i n i t i a l m o m e n t u m for P l a y e r E. converts to the inequality a ^ 3

> 0—-,

where r, s are the

T h e c o n d i t i o n (4.1.9)

and the existence c o n d i t i o n for the

invariant center of pursuit (4.1.9) converts to the inequality a > 0

(4.1.18)

P h y s i c a l l y , this means that the m a x i m u m force applied by Player P exceeds the force applied by Player E. W h e n (4.1.18) is satisfied, the value of the game is equal to

PT(q,r).

tt is

determined from the f o r m u l a

Mq,

- r,- 4 T{

r) = A

-

Pi

- (a - 0)~.

(4.1.19)

T h e equation w i t h partial derivatives of the first order for the f u n c t i o n

PT{q,^)

is derived from (4.1.14) by s u b s t i t u t i n g kp — fcg = 0 Example

3a.

T h e pursuit occurs over the entire plane.

M o t i o n equations

are of the form 4i =

Pi,

p\ = aui - kppi,

|u| < 1,

i =

1,2

Vi = 0v

M S I ,

i =

1,2,

U

Here q and y are respectively the geometrical positions of the players P and E, and p is Player P ' s m o m e n t u m . T h u s , i n the case at h a n d , Player E moves in accordance w i t h the " s i m p l e m o t i o n " , and Player P representing a material point of unit mass, m o v i n g under the action of the friction force and the force a. Player £ ' s payoff is defined as a distance between the players' geometrical locations when the play terminates:

H(q(T),y(T))

F i r s t consider the case k the radius

= p(q(T),y(T))

P

=

£(*(?) -

^ 0. T h e set Cf(q)(\n e-

kpT

+

»,(D) . a

the space q) is a circle with k T-1 P

Games w i t h p r e s c r i b e d d u r a t i o n without phase

constraints

129

and its center at the p o i n t 1 -

e*'

T

where q, p are the s t a r t i n g position and i n i t i a l m o m e n t u m for Player P . T h e set C [y) is a circle w i t h the radius RE(T) = ST and its center at the point y. A s before, the q u a n t i t y p {q,y) is computed by the f o r m u l a E

T

h{
= p(q,y) + R E - R P , 1 -

e"*'- ' + k T 1

- a

- 1

P

t~ " k

T

„

+0T.

A s shown in the previous example, to satisfy the invariance conditions for the center of p u r s u i t M it is sufficient that along the c o n d i t i o n a l l y o p t i m a l trajectories q'(t), y'{t)

the inequality R (T

- t) > R {T

P

is satisfied for a l l 0 < ( < T, where R (T

- i ) , P l ( T - () are the radius of

P

reachability circles Cp~'(q*(t)), by

(4.1.20)

- t)

E

E

C | " ' ( y - ( t ) ) - In what follows, T - t is denoted

T.

We find the c o n d i t i o n (4.1.20) to be satisfied for the case under study. Compute R ' and R ' : P

B

R'p(r) Since fi > 0 and R' (0} E

=

8. Since R (0) P

this n e i g h b o u r h o o d .

l

~ ^

k

P

\

R' (T)=0. e

= 0, there is such neighbourhood of zero that

P

R' {T)

= a

=

R (0) E

= 0, then R {r)

<

P

R {T), E

T ?

flp(r)

<

0 for r from

T h u s , the sufficient condition of invariance (4.1.20) is

violated. A t the same t i m e , under some i n i t i a l conditions the center of pursuit is found to be invariant. L e t us deduce these conditions. C o n s i d e r the difference -kpT

y(T)

= R P ( T )- Jfc(r) = o

+ kr -r^p P

- 1

Br.

Show t h a t f>{r) goes to zero at a unique point which is a monotonicity point of the function v ( r ) . C o m p u t e
Examples

130 Since


>

of differential

games of pursuit

0, then i^'(r) increases monotonically. However, ^'(0) = —ft <

0. L e t 3 < I-. T h e n there is such r that ^'( o) = 0, or s

T

0

1 . 1 — In — g • k 1 - P-kp

TO =

(4.1.21)

P

For t > r the function 0, i.e. the function
0

is strictly increasing. Since y>'(0) < 0, i^(0) < 0 for 0 < T < r , then ^ ( r ) < 0 0

and y>(r) goes to zero for some f

> r . In the same t i m e

0

0

OL

l i m
0

= +oo,

Suppose the following condition is satisfied (4.1.22) T h e n the point M is invariant.

In fact, the invariance of the point M may

be violated (see Fig.14) only if d u r i n g the m o t i o n a long c o n d i t i o n a l l y optimal trajectories the point M, that is d i a m e t r i c a l l y opposite t o the point M , i n the set Cg{y) is more removed from Cp(q) than the point M ( o r i t is at the same distance from Cp(q) as the point M). G e o m e t r i c a l l y , i t is evident t h a t under condition (4.1.22) this is not possible. W h e n the c o n d i t i o n (4.1.22) is satisfied, for all T we have (4.1.23)

RE{r)-R (r)