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 ${\mathcal {U}}$ gracza I, a dla każdej strategii $U\in {\mathcal {U}}$ 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\geqslant 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\geqslant 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 {\mathcal {U}}$ 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 {\mathcal {U}},$ 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 {\mathcal {U}}$ spełniającej nierówność:

$\kappa _{1}(U_{c})\leqslant c,$

gdzie $c$ jest daną liczbą.

W analogiczny sposób można sformułować zadanie gracza II. Jego strategia $V\in {\mathcal {V}}$ 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 {\mathcal {V}},$ dla której:

$\kappa _{2}(V_{c})\geqslant c.$

Jeśli w zadaniach graczy I i II klasy strategii ${\mathcal {U}}$ i ${\mathcal {V}}$ mają taką własność, że dla każdej pary uporządkowanej $(U,V)\in {\mathcal {U}}\times {\mathcal {V}}$ 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 ${\mathcal {U}}\times {\mathcal {V}}.$

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

$\inf _{U\in {\mathcal {U}}}\,\,\sup _{x(\cdot )\in X(U)}\gamma (x(\cdot ))=\sup _{V\in {\mathcal {V}}}\,\,\inf _{x(\cdot )\in X(V)}\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}\|\leqslant \varepsilon \},$

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 $\varepsilon$ jest interpretowane jako spotkanie obiektów.

Linki zewnętrzne

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