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^[1].

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

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

gdzie ${\displaystyle x}$ jest wektorem fazowym układu, ${\displaystyle u}$ i ${\displaystyle v}$ – wektorami sterowania odpowiednio graczy I i II, a ${\displaystyle t}$ czasem. Określona jest klasa strategii ${\displaystyle {\mathcal {U}}}$ gracza I, a dla każdej strategii ${\displaystyle U\in {\mathcal {U}}}$ określony jest wiązką ruchów ${\displaystyle 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 ${\displaystyle x(t),t\geqslant t_{0}}$ układu zadany jest funkcjonał ${\displaystyle \gamma (x(\cdot ))}$ nazywany płacą gry, którego wartość gracz I stara się zminimalizować. Czasem funkcjonał ${\displaystyle \gamma }$ zależy także od realizacji ${\displaystyle u(t),v(t),t\geqslant t_{0}}$ sterowania obu graczy^[2].

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

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

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

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

gdzie ${\displaystyle c}$ jest daną liczbą^[3].

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

${\displaystyle \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 ${\displaystyle \kappa _{2},}$ a zadanie jakości – na znalezieniu strategii ${\displaystyle V_{c}\in {\mathcal {V}},}$ dla której:

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

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

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

generowany przez tę parę, to oba te zadania generują grę różniczkową na klasie strategii ${\displaystyle {\mathcal {U}}\times {\mathcal {V}}.}$

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

${\displaystyle \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ść ${\displaystyle c_{0}}$ nazywa się ceną gry różniczkowej^[3].

Przykład

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

${\displaystyle x=(x_{1},\dots ,x_{k+l})=(y_{1},\dots ,y_{k},z_{1},\dots ,z_{l}),}$

gdzie ${\displaystyle 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

${\displaystyle {\dot {y}}=g(t,y,u),{\dot {z}}=h(t,z,v)}$^[3].

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

${\displaystyle u\in P,v\in Q,}$

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

${\displaystyle \gamma (x(\cdot ))=T(x(\cdot ))=\inf\{t-t_{0}:||\{y(t)\}_{m}-\{z(t)\}_{m}\|\leqslant \varepsilon \},}$

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

Przypisy

Linki zewnętrzne

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