追捕逃逸型微分對(duì)策問(wèn)題的識(shí)別域判別

張 霞， 高 巖， 夏尊銓

（1.大連理工大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，大連 116024；2.浙江財(cái)經(jīng)學(xué)院東方學(xué)院 信息分院，海寧 314408；3.上海理工大學(xué) 管理學(xué)院，上海 200093）

1 問(wèn)題的提出

微分對(duì)策理論是現(xiàn)代控制理論中的一個(gè)重要研究課題，也是對(duì)策論的一個(gè)重要分支.微分對(duì)策是指在局中人之間進(jìn)行對(duì)策活動(dòng)時(shí)要用到微分方程（組）來(lái)描述對(duì)策現(xiàn)象或規(guī)律的一種對(duì)策，是解決對(duì)抗與競(jìng)爭(zhēng)問(wèn)題的有力工具.微分對(duì)策理論的研究可追溯到20世紀(jì)40年代，當(dāng)時(shí)因軍事上的需要，由Isaacs帶領(lǐng)的團(tuán)隊(duì)研究了導(dǎo)彈對(duì)抗飛行器策略問(wèn)題，以此為開(kāi)端，微分對(duì)策的基本概念及理論相繼提出，最早的文獻(xiàn)見(jiàn)于Isaacs的《Differential Games》一書(shū)［1］.微分對(duì)策理論的進(jìn)一步發(fā)展來(lái)自?xún)蓚€(gè)方面：一是最優(yōu)控制理論；二是對(duì)策論.從最優(yōu)控制到微分對(duì)策可看作是從一方控制發(fā)展到雙方或多方控制；從對(duì)策論到微分對(duì)策，又可看作是從靜態(tài)的對(duì)策理論發(fā)展到動(dòng)態(tài)的對(duì)策理論.因此，微分對(duì)策理論的研究對(duì)控制領(lǐng)域和對(duì)策論中問(wèn)題的解決起著重要的作用［2］.而且隨著該理論的不斷發(fā)展，現(xiàn)在也被廣泛應(yīng)用到科學(xué)研究、工程技術(shù)、交通運(yùn)輸、航天航空、環(huán)境保護(hù)、經(jīng)濟(jì)管理和市場(chǎng)競(jìng)爭(zhēng)等許多方面［3－5］.

根據(jù)提法的不同，微分對(duì)策問(wèn)題有多種形式.本文將考慮單目標(biāo)兩人追捕逃逸型微分對(duì)策問(wèn)題（pursuit－evasion games），它是由Isaacs最早提出并命名的.描述如下：

考慮兩控制變量的微分動(dòng)力系統(tǒng)

其中，x∈Rn是狀態(tài)變量；u∈U，v∈V是控制變量；U，V?Rm，f（x，u，v）為Rm＋n到Rm上的利普希茨函數(shù).設(shè)Ω為Rn中開(kāi)子集，也稱(chēng)為目標(biāo).引入兩個(gè)局中人，第一個(gè)局中人為Ursula，控制變量為u，要使系統(tǒng)的狀態(tài)在有限時(shí)間內(nèi)到達(dá)目標(biāo)Ω；另一個(gè)局中人為Victor，控制變量為v，卻力爭(zhēng)使系統(tǒng)狀態(tài)永遠(yuǎn)避開(kāi)此目標(biāo)Ω，這就是單目標(biāo)兩人追捕逃逸型微分對(duì)策問(wèn)題.

Krasovskii及Subbotin研究了追捕逃逸型微分對(duì)策問(wèn)題的無(wú)優(yōu)先規(guī)則的位置策略［2，6］，并證明了選擇定理.即在任何初始點(diǎn)x0，或者Ursula贏(yíng)，或者Victor贏(yíng)，二者擇一.然而，在Caratheodory意義下系統(tǒng)（1）無(wú)解，為此他們推廣了解的定義，給出了近似微分對(duì)策.與位置策略的研究方法不同，文獻(xiàn)［7］使用了無(wú)預(yù)見(jiàn)性策略（nonanticipative stragies），故局中人都可以通過(guò)對(duì)方行動(dòng)的信息來(lái)決定自己的行動(dòng)，這在現(xiàn)實(shí)中有很多應(yīng)用事例.文獻(xiàn)［7］的另一個(gè)重要貢獻(xiàn)在于通過(guò)幾何方式去研究勝利域（victory domain，指無(wú)論對(duì)方如何行動(dòng)，局中人都能贏(yíng)的初始點(diǎn)的集合），據(jù)此可以繼續(xù)作勝利域的數(shù)值計(jì)算［8－9］.隨后又在文獻(xiàn)［10］中給出了具有狀態(tài)約束的追捕逃逸型問(wèn)題，并證明了微分對(duì)策值的存在性.近期作者又將這一理論推廣到混雜系統(tǒng)［11］.

就具體應(yīng)用問(wèn)題來(lái)講，微分對(duì)策系統(tǒng)識(shí)別域（discriminating domain）的判別很重要，它直接關(guān)系到勝利域的表示以及微分對(duì)策問(wèn)題的解.然而，正如對(duì)一般的非線(xiàn)性控制系統(tǒng)可生存性判別的充要條件很難具體使用一樣［12］，目前關(guān)于微分對(duì)策問(wèn)題的識(shí)別域判別還沒(méi)有切實(shí)可行的判別準(zhǔn)則.為此，本文參照文獻(xiàn)［13］的方法，研究了一類(lèi)重要的控制系統(tǒng)即仿射非線(xiàn)性控制系統(tǒng)下的追捕逃逸型微分對(duì)策問(wèn)題，給出該問(wèn)題的系統(tǒng)識(shí)別域判別的方法，并結(jié)合凸可行問(wèn)題的算法給出該判別問(wèn)題的投影算法，最后給出這類(lèi)微分對(duì)策問(wèn)題的選擇定理.

2 識(shí)別域的判別方法

首先給出文中用到的幾個(gè)定義.

定義1K為Rn的閉子集，x∈K，若dK（x＋p）＝‖p‖，則稱(chēng)向量p∈Rn為K在x處的近似法向量，所有p的集合記為NPK（x）.

定義2 若任意x∈D，任意p∈NPD（x），則稱(chēng)D為f的識(shí)別域.Rn的閉子集K所包含的f的最大識(shí)別域稱(chēng)為f的識(shí)別核，記作Discf（K）.

定義3 若任意x∈D，任意p∈NPD（x），則稱(chēng)D為f的領(lǐng)導(dǎo)域（leadership domain）.Rn的閉子集K所包含的f的最大的領(lǐng)導(dǎo)域稱(chēng)為f的領(lǐng)導(dǎo)核，記作Leadf（K）.

下面討論識(shí)別域的判別問(wèn)題.考慮如下仿射非線(xiàn)性系統(tǒng)

其中，w（x）為Rn到Rn的利普希茨函數(shù)，g（x）和h（x）為Rn到Rm＋n的利普希茨函數(shù)，u∈U為一度量緊空間.v∈V＝｛v∈Rm｜ai（v）≤0，i＝1，2，…，r｝，ai（v）為Rm上的凸函數(shù).

定義區(qū)域

這里給定φj（x）為Rn上的連續(xù)可微函數(shù).定義指標(biāo)集

為方便問(wèn)題的研究，在此給出本文所用到的假設(shè)條件及已知命題.

假設(shè)1

a.f（x，u，v）｜Rn×U×V→Rn為連續(xù)函數(shù).

b.對(duì)任意u∈U，v∈V，f（·，u，v）為利普希茨連續(xù).

假設(shè)2［14］存在y0∈Rn，使得φj（x）Ty0＜0，j＝1，2，…，s.

假設(shè)3［14］cl（γ（x））＝Γ（x）成立，其中

這里cl為閉包.

命題1［14］若假設(shè)2及假設(shè)3成立，則TD（x）＝Γ（x）.其中

命題2［15］若假設(shè)1成立，則D為f的識(shí)別域的充要條件是：

任意x∈D，任意u∈U，f（x，u，V）∩TD（x）≠φ其中為空集.

下面給出判別系統(tǒng)（2）的識(shí)別域的充分必要條件.

定理1 在假設(shè)1～3成立的條件下，區(qū)域D為系統(tǒng)（2）中f的識(shí)別域當(dāng)且僅當(dāng)不等式組

是相容的.其中，v∈Rm為變量.

證明 由命題1知，區(qū)域D為f的識(shí)別域的充要條件是：

任意x∈D，任意u∈U，f（x，u，V）∩TD（x）≠φ.當(dāng)x屬于區(qū)域D的內(nèi)部時(shí)，TD（x）＝Rn，定理顯然成立.因此只需考慮邊界點(diǎn)的情況，即集合.此時(shí)由命題1知，

所以f（x，u，V）∩TD（x）≠φ等價(jià)于下面的不等式組有解

將y＝w（x）＋g（x）u＋h（x）v代入上面的第二個(gè)不等式，即得式（4a）和式（4b），證畢.

3 投影算法及選擇定理

下面給出判別系統(tǒng)（2）的識(shí)別域的算法.

因?yàn)槭剑?a）是關(guān)于變量v的線(xiàn)性不等式組，故可與式（4b）一起組成下面的凸不等式組

其中，v∈Rm為變量，q為式（4a）和式（4b）中全部不等式的個(gè)數(shù).

判別該凸不等式組的相容性又可視為凸可行問(wèn)題，令

則問(wèn)題轉(zhuǎn)化為尋找v∈Ψ.解決此問(wèn)題的一個(gè)強(qiáng)有力的方法是投影算法［16］，下面給出判別識(shí)別域的投影算法.

Step 2i＝0，0＜η≤1，取v0∈Rm.

Step3 若點(diǎn)列｛vi｝收斂，則停止，x∈D為f的識(shí)別域中的點(diǎn).否則轉(zhuǎn)至Step 4.

Step 4 計(jì)算σk∈?ak（vi）＝｛σk∈Rn｜z∈Rn，ak（z）≥ak（vi）＋［vi，z－vi］｝，

Θi＝｛y∈Rn｜ak（vi）＋〈σk，y－vi〉≤0，k＝1，2，

Step 5 選擇ωi｜η≤ωi≤2－η，計(jì)算vi＋1＝vi＋ωi（yi－vi）.

Step 6i＝i＋1，轉(zhuǎn)至Step 3.

定理2（收斂性） 在下列條件成立的情況下，算法收斂，即｛vi｝→v∈Ψ.

a.ai（v）≤0，i＝1，2，…，r為凸連續(xù)函數(shù)；

b.Ψ≠φ；

c.對(duì)任意v，?ai（v）是有界的，i＝1，2，…，r.

最后回到兩人追捕逃逸型微分對(duì)策問(wèn)題，給出在仿射非線(xiàn)性系統(tǒng)下的選擇定理.

定理3 設(shè)f滿(mǎn)足假設(shè)1，令Ο＝Rn＼Ω，則Victor的勝利域?yàn)镈iscf（Ο），Ursula的勝利域?yàn)棣蹹iscf（Ο）.

證明 參照文獻(xiàn)［7］的選擇定理可以得到Victor的勝利域?yàn)镈iscf（Ο），Ursula的勝利域?yàn)棣躄eadf（Ο）.又因?yàn)閒（x，u，v）＝w（x）＋g（x）u＋h（x）v，故

即Isaacs條件滿(mǎn)足，所以L(fǎng)eadf（Ο）＝Discf（Ο），故結(jié)論成立，證畢.

由此可見(jiàn)，在這種特殊情況下，局中兩人的勝利域瓜分了目標(biāo)集的補(bǔ)集.而且該微分對(duì)策問(wèn)題與無(wú)優(yōu)先規(guī)則的位置策略相同，故只要知道系統(tǒng)的初始狀態(tài)，就能確定兩人的對(duì)策結(jié)局.

4 結(jié) 論

本文基于非光滑分析及生存理論得出了一類(lèi)仿射非線(xiàn)性微分對(duì)策問(wèn)題在不等式約束區(qū)域上系統(tǒng)識(shí)別域的判別方法，該方法可具體實(shí)現(xiàn)；并給出了算法，以及兩人追捕逃逸型微分對(duì)策問(wèn)題的選擇定理.雖然微分對(duì)策理論的研究及應(yīng)用有了極大的發(fā)展，但在追捕逃逸型微分對(duì)策模型的建立和求解以及不確定型微分對(duì)策等方面的研究尚不充分，這可作為進(jìn)一步研究的課題.

［1］Isaacs R.Differential games［M］.New York：Wiley，1965.

［2］Krasovskii N N，Subbotin A I.Game theoretical control problems ［M ］. New York： Spring－Verlag，1988.

［3］Getz W M，Pachter M.Two－target pursuit－evasion differential games in the plane［J］.JOTA，1981，34 （3）：383－403.

［4］Zhu Q Y，Tembine H，Basar T.Hybrid risk－sensitive mean－field stochastic differential games with application to molecular biology［C］／／2011 50th IEEE Conference on Digital Object Identifier.Orlando，2011：4491－4497.

［5］Steffen J，Georges Z.Developments in differential game theory and numerical methods：economic and management applications［J］.Computational Management Science，2007，4（2）：159－181.

［6］Krasovskii N N，Subbotin A I.Universal optimal strategies in positional differential games ［J］.Differential Equat，1984，19（11）：1377－1382.

［7］Cardallaguet P.Differential game with two players and one target［J］.SIAM J Control and Optimization，1996，34（4）：1441－1460.

［8］Quincampoix M，Saint－pierre P.An algorithm for viability kernels in Holderian case：approximation by discrete viability kernels［J］.Journal of Math System，Estim and Control，1995，5（1）：115－118.

［9］Cardallaguet P，Quincampoix M，Saint－pierre P.Some algorithms for differential games with two－players and one target［J］.Mathematical Modeling and Numerical Analysis，1994，28（4）：441－461.

［10］Cardallaguet P，Quincampoix M，Saint－pierre P.Pursuit differential games with state constraints［J］.SIAM J Control and Optimization，2002，39（5）：1615－1632.

［11］Gao Y，Lygeros J， Quincampoix M. On the reachability problem for uncertain hybrid systems［J］.IEEE Transactions on Automatic Control，2007，52（9）：1572－1586.

［12］高巖.一類(lèi)非線(xiàn)性控制系統(tǒng)可生存性判別［J］.信息與控制，2005，34（4）：510－512.

［13］高巖.仿射非線(xiàn)性控制系統(tǒng)生存性的判別［J］.控制理論與應(yīng)用，2009，26（6）：654－656.

［14］Demyanov V F， Rubinov A M. Constructive nonsmooth analysis［M］.Berne：Peterlang，1995.

［15］Aubin J P.Viability theory［M］.Boston：Birkh?user，1992.

［16］Garcia－palomares U M.A superlinearly convergence projection algorithm for solving the convex inequality problem［J］.Operations Research Letter，1998，22（2／3）：97－103.