Gry różniczkowe

Gry różniczkowe – dział matematycznej teorii sterowania optymalnego, w którym rozpatruje się sterowanie w sytuacjach konfliktowych. Ma on także związek z teorią gier. Teoria powstała w latach 50. XX wieku.

Sformułowania problemów teorii gier różniczkowych

W teorii wyróżnia się dwa rodzaje gier:

• gra dwóch graczy,
• gra wielu graczy.

Podstawowe wyniki uzyskano dla gier różniczkowych dwóch graczy, a sama gra podporządkowana jest wtedy następującemu schematowi:

• dany jest pewien układ dynamiczny, w którym część sterujących działań podporządkowana jest graczowi I, a inna część graczowi II,
• zakłada się, że dla każdego z graczy wybór działań gwarantujących mu osiągnięcie założonego celu, przy dowolnym, nieznanym wcześniej sterowaniu przeciwnika, opiera się jedynie na informacji o bieżącym stanie układu.

W teorii gier różniczkowych rozpatruje się także problemy, w których zakłócenia działania układu traktuje się jako działania przeciwnika.

Zazwyczaj zakłada się, że ruch sterowanego układu jest podporządkowany równaniu różniczkowemu

$\dot{x}=f(t,x,u,v)$

gdzie $x$ jest wektorem fazowym układu, $u$ i $v$ – wektorami sterowania odpowiednio graczy I i II, a $t$ czasem. Określona jest klasa strategii $𝒰$ gracza I, a dla każdej strategii $U\in 𝒰$ określony jest wiązką ruchów $X(U),$ która jest generowana przez tę strategię oraz wszystkie możliwe strategie przeciwnika. Wiązka ta wychodzi z początkowego stanu powyższego układu.

Na ruchach $x(t),t⩾t_0$ układu zadany jest funkcjonał $\gamma (x(\cdot ))$ nazywany płacą gry, którego wartość gracz I stara się zminimalizować. Czasem funkcjonał $\gamma$ zależy także od realizacji $u(t),v(t),t⩾t_0$ sterowania obu graczy.

Biorąc pod uwagę także najbardziej niekorzystną realizację ruchu $x(\cdot )\in X(U),$ gdy wybór strategii jest pozostawiony graczowi II, jakość strategii $U\in 𝒰$ jest oceniana za pomocą wielkości:

${\kappa }_1(U)=\sup \{\gamma (x(\cdot )):x(\cdot )\in X(U)\}.$

Zadanie gracza I polega na określeniu strategii $U_0\in 𝒰,$ na której realizowane jest minimum funkcjonału ${\kappa }_1$ (jest to zadanie potęgi). Czasem rozpatruje się zadanie jakości, które polega na znalezieniu strategii $U_c\in 𝒰$ spełniającej nierówność:

${\kappa }_1(U_c)⩽c,$

gdzie $c$ jest daną liczbą.

W analogiczny sposób można sformułować zadanie gracza II. Jego strategia $V\in 𝒱$ jest oceniana przez wielkość:

${\kappa }_2(V)=\sup \{\gamma (x(\cdot )):x(\cdot )\in X(V)\}.$

Zadanie potęgi polega wtedy na znalezieniu strategii maksymalizującej wartość funkcjonału ${\kappa }_2,$ a zadanie jakości – na znalezieniu strategii $V_c\in 𝒱,$ dla której:

${\kappa }_2(V_c)⩾c.$

Jeśli w zadaniach graczy I i II klasy strategii $𝒰$ i $𝒱$ mają taką własność, że dla każdej pary uporządkowanej $(U,V)\in 𝒰\times 𝒱$ można określić choć jeden ruch

$x(\cdot )\in X(U)\cap X(V),$

generowany przez tę parę, to oba te zadania generują grę różniczkową na klasie strategii $𝒰\times 𝒱.$

Jeśli w grze różniczkowej spełniona jest równość

$\underset{U\in 𝒰}{\inf }\underset{x(\cdot )\in X(U)}{\sup }\gamma (x(\cdot ))=\underset{V\in 𝒱}{\sup }\underset{x(\cdot )\in X(V)}{\inf }\gamma (x(\cdot ))=c_0,$

to wielkość $c_0$ nazywa się ceną gry różniczkowej.

Przykład

Typowym przykładem gry różniczkowej jest zagadnienie pościgu-ucieczki. W tej grze

$x=(x_1,\dots ,x_{k+l})=(y_1,\dots ,y_k,z_1,\dots ,z_l),$

gdzie $y=(y_1,\dots ,y_k),z=(z_1,\dots ,z_l)$ są odpowiednio wektorami fazowymi ścigającego i uciekającego, a ich ruch opisywany jest równaniami

$\dot{y}=g(t,y,u),\dot{z}=h(t,z,v)$.

Najczęściej rozpatruje się przypadki, gdy wybór sterowania podlega ograniczeniom typu

$u\in P,v\in Q,$

gdzie $P,Q$ są pewnymi zbiorami zwartymi. Płacą w takiej grze jest czas spotkania, tzn.:

$\gamma (x(\cdot ))=T(x(\cdot ))=\inf \{t-t_0:||\{y(t){\}}_m-\{z(t){\}}_m\Vert ⩽\epsilon \},$

gdzie $\{y(t){\}}_m$ i $\{z(t){\}}_m$ są wektorami utworzonymi z pierwszych $m$ współrzędnych wektorów $y$ i $z.$ Zatem zbliżenie punktów $\{y(t){\}}_m$ i $\{z(t){\}}_m$ na odległość mniejszą od $\epsilon$ jest interpretowane jako spotkanie obiektów.

Linki zewnętrzne

• Gra szofer – morderca i jej modyfikacje (jęz. rosyjski),