Families of Semipermeable Curves and Their Application to Some Complicated Variants of the Homicidal Chauffeur Problem

V.S.Patsko
Institute of Mathematics and Mechanics
Ekaterinburg, Russia

V.L.Turova
Zentrum Mathematik, Technische Universität München
Garching, Germany

Second International Conference on Game Theory and Management GTM2008

Graduate School of Management, St. Petersburg State University, and the International Society of Dynamic Games (Russian Chapter)

June 26-27, 2008, St. Petersburg



All slides in PDF (4422 Kb)




Families of Semipermeable Curves and Their Application to Some Complicated Variants of the Homicidal Chauffeur Problem





Time-limited reachable sets for the simplest (Dubins') car

Slide 1

This is the simplest model of the car's dynamics. It is called Dubins' car. Here xp, yp are the coordinates of the geometrical state, θ is the angle of velocity vector to the vertical axis, and u is the control.

Fix the origin as the initial point. Let the vector of the initial velocity is directed upwards along the vertical axis. Then the time-limited reachable sets (or reachable sets by given time) look like it is shown in the figure. The fronts of these sets propagate by going around two dark arcs.

Let us imagine a real function whose value at every point is the propagation time required for the front to reach the point. We call such a function as the value function. It is clear that the value function determines the optimal time of reaching the origin, the direction of the velocity vector at the origin being specified. The value function is discontinuous on the above mentioned arcs.





Isaacs' homicidal chauffeur game

Slide 2

Consider Isaacs' homicidal chauffeur game. Dynamics of player P is written to the left, dynamics of player E is to the right. The velocity of player E is bounded by a number ν.

Put the origin of the reference coordinate system at the current position of player P. Then the current state of player E is described by the system of the second order. Player P strives to bring the phase vector to a given target set as soon as possible. Player E has the opposite goal. In the classical setting, the target set is a circle centred at the origin.





Level sets and graph of the value function

Slide 3

This slide shows level sets and graph of the value function for the homicidal chauffeur game. The value function is discontinuous on two dark lines.





Example with shifted target set

Slide 4

Let us shift the centre of the target set. Consider again the discontinuity lines of the value function. We have two lines as it was before. The following question arises. Would it be possible to predict discontinuity lines of the value function without solving corresponding time-optimal game?





Semipermeable directions and semipermeable curves

Slide 5

The answer is "yes", and it is related to the investigation of families of smooth semipermeable curves in the plane. The smooth semipermeable curves are defined by the dynamic equations and constraints on the controls of the players only.

Consider minmax Hamiltonian function of the controlled system. Here, f is the right hand side vector of our system. Symbol z stands for a point in the plane x,y. The function lH(l, z) is positively homogeneous. Using this, we can consider unit vectors l only.

Choose a counterclockwise direction as a standard one for the boundary of the unit circle. For every point z find a unit vector l such that the Hamiltonian becomes zero. We consider the first type root from plus to minus and second type root from minus to plus. For the dynamics considered, it is proved that no more than two roots of each type can exist at every point.

Let l(1), 1(z) denote the first type root attained at u = 1. Respectively, l(1), 2(z) be the first type root atained at u = -1. Similarly, roots l(2), 1(z) and l(2), 2(z) of the second type are defined.

The existence of the root can be explained using the velocity vectograms of players P and E. Namely, a root exists, if and only if the vectograms are separated.

The unit vector of the system velocity corresponding to the extremal control for the first (second) type root is called the semipermeable direction of the first (second) type. The semipermeable direction of the first type is obtained by a clockwise rotation of the vector l through the anlgle π/2. For the second type semipermeable direction, a counterclockwise rotation takes place.

A smooth curve is called the first type semipermeable curve if the tangent vector at every point is the first type semipermeable direction. Similarly, the second type semipermeable curves are introduced.





Differential equations for semipermeable curves.
Domains of functions l(j),i

Slide 6

Based on these facts, we can compute the semipermeable curves as solutions of the ordinary differential equation shown in the upper part of this slide. Here, Π is the operator which rotates the vector by the angle π/2. We use a clockwise rotation for the case j=1 (the first type root) and counterclockwise rotation for the case j=2 (the second type root).

On the left, regions with different types of roots are shown. The domains of the first type roots are depicted on the right.





Families of semipermeable curves

Slide 7

Here, four families Λ(j),i; j = 1,2; i = 1,2 of semipermeable curves are presented. The arrows show the backward-in-time direction of motion with extremal controls. Any other families of smooth semipermeable curves for the classical homicidal chauffeur dynamics do not exist.





Discontinuity lines are semipermeable curves of families Λ(1),1, Λ(2),2

Slide 8

Let us go back to our two examples of level sets. For the left picture, the target set is a circle centred at the origin. For the right picture, the centre of the target set is shifted. Now, we can clearly see that the discontinuity lines are semipermeable curves. The right arcs in both pictures are from family Λ(1),1, the left arcs belong to family Λ(2),2. We can precisely determine where these arcs terminate. The termination occurs after their coming to the boundary of the domain of the corresponding family.





Acoustic game

Slide 9

P. Cardaliaguet, M. Quincampoix, and P. Saint-Pierre have considered a variant of the dynamics in which the radius of the circle constraint of player E depends on the distance σ of the current state to the origin of the reference system. The applied aspect is the follwing: the object E should not be very loud if the distance between him and player P becomes small. The dependence of the constraint on the distance σ is shown in the right lower picture.

The differential game with such dynamics was called the acoustic homicidal chauffeur game. Different target sets were considered, also in the form of a rectangle stretched along the horizontal axis





Regions with infinite values of the game

Slide 10

Here, the level sets and the graph of the value function are shown for one particular case. The values of the game are infinite outside the region filled out with the level sets. We can precisely detect to which family of semipermeable curves belong those curves that form the boundary of this region and touch the target set. But what about the hole inside? Would it be possible to describe it effectively without the computation of level sets?





Semipermeable curves in acoustic game

Slide 11

To describe the hole, one should study the families of semipermeable curves of the acoustic game very thoroughly. Let us show, for example, the semipermeable curves for the following parameters of the dynamics: ν*=0.8, s=0.9375. On the left, domains of the first and second type roots are shown. The family Λ(1), 1 of semipermeable curves is drawn on the right. In the case considered, the difference from the corresponding family for the classical dynamics is not big. The arrows show the forward direction of motion.





Semipermeable curves in acoustic game

Slide 12

Let now reinforce player E by taking a larger value of parameter ν*. In this case, the family Λ(1), 1 differs essentially from that one in the classical case. The picture to the left specifies the number of roots in different parts of the plane. In regions CU and CL , no roots exist.





Semipermeable curves and superiority sets of player E

Slide 13

In this way, we can give a description of the hole. The picture to the left shows those semipermeable curves which form the boundary of the hole. It consists of two first type and two second type semipermeable curves. These curves can be constructed precisely. On the contrary, when constructing level sets, the time near the boundary of the hole goes to infinity. This makes the description of the obtained limit problematical.





Reeds-Shepp's car as a pursuer

Slide 14

In the paper by J. A. Reeds and L. A. Shepp, a model time-optimal problem for a more agile car that can change his velocity vector instantaneously (by means of additional control w) was investigated. On the slide, a quote from this paper is given.

One can replace Dubins' car in the classical homicidal chauffeur game by Reeds-Shepp's car. Moreover, we can consider an intermediate case using a parameter a that specifies the lower bound on the linear velocity of player P. If a=1, the classical homicidal chauffer game is obtained. For a=-1, the homicidal chauffeur game with Reeds-Shepp's car arises.





Families of semipermeable curves in the classical homicidal chauffeur problem

Slide 15

For the classical variant of the homicidal chauffeur dynamics (which corresponds to a = 1), semipermeable curves are the involutes of the circle arcs being marked here with the thick lines. Here and on the next slides with the semipermeable curves, the arrows show the backward-in-time direction of motion.





Basis for families of semipermeable curves in reinforced homicidal chauffeur dynamics

Slide 16

For the more agile car, instead of two circumferences we deal with the arcs of four circumferences and with their involutes.





Families of semipermeable curves for reinforced homicidal chauffeur dynamics (a)

Slide 17

This slide corresponds to the case where a. The first and second type families generated by the arcs of two right circumferences are shown. We obtain three first type families and three second type families. Six symmetrical to them families are generated by the arcs of two left circumferences. All together, twelve families exist.





Families of semipermeable curves for reinforced homicidal chauffeur dynamics (a)

Slide 18

In the case a, the number of smooth semipermeable curves increases. Here, one can see the first type families generated as involutes by the arcs of two circumferences. In the case considered, sixteen families are obtained.





Level sets of the value function. Discontinuity lines

Slide 19

On this slide, results of the computation of level sets of the value function are presented for a = 0.25. On the right, an enlarge fragment of the computation is given. The left discontinuity line is a smooth junction of two semipermeable curves of the second type. Using the knowledge about the families, we can precisely determine where the left discontinuity line terminates. The right discontinuity line is symmetrical to the left one. It is composed of two semipermeable curves of the first type.





Level sets of the value function. Discontinuity lines

Slide 20

Here, the value of parameter a is less than . Using the information about the families of semipermeable curves, we can predict before the computation of level sets that four short curves emanating from the points c, d, e, f are discontinuity lines. The upper curves should terminate at the horizontal line y=0.3, the lower curves finish at the line y=-0.3.





Families of semipermeable curves for a > 0, ν = 0

Slide 21

To complete, let us demonstrate the simplest case where player E is immovable and the value of the parameter a is positive. In this case, we have four families of semipermeable curves. Every semipermeable curve is a semicircumference.





Related authors' works

Slide 22

Three related papers by the authors are presented.





V.S.Patsko
Institute of Mathematics and Mechanics
Ekaterinburg, Russia
patsko@imm.uran.ru

V.L.Turova
Zentrum Mathematik, Technische Universität München
Garching, Germany
turova@ma.tum.de