王震 袁勇 安波 李明楚 王飛躍

1.大連理工大學(xué)軟件學(xué)院 遼寧 大連 116620 2.南洋理工大學(xué)計(jì)算機(jī)工程學(xué)院 新加坡 639798 3.中國科學(xué)院自動(dòng)化研究所 北京100080 4.青島智能產(chǎn)業(yè)技術(shù)研究院山東青島266109

在現(xiàn)代社會(huì)中,保護(hù)各種關(guān)鍵公共基礎(chǔ)設(shè)施和目標(biāo)是各國安全機(jī)構(gòu)面臨的一項(xiàng)非常有挑戰(zhàn)性的任務(wù).比如,安全機(jī)構(gòu)需要保護(hù)公共交通網(wǎng)絡(luò)和乘客免受恐怖襲擊以及其他破壞活動(dòng);并且有責(zé)任阻止毒品、武器、錢財(cái)?shù)仍趪抑g非法流通;也同樣需要保護(hù)稀有動(dòng)物和自然資源等免遭非法狩獵、非法捕撈以及過度砍伐行為的破壞.隨著網(wǎng)絡(luò)社會(huì)的發(fā)展,安全機(jī)構(gòu)還需要及時(shí)發(fā)現(xiàn)和遏制網(wǎng)絡(luò)謠言,維護(hù)健康的網(wǎng)絡(luò)環(huán)境.最近幾年來,日益增長的國際恐怖主義威脅,加劇了安全機(jī)構(gòu)面臨的挑戰(zhàn).特別是公交、地鐵、火車和飛機(jī)等公共交通網(wǎng)絡(luò)每天承載數(shù)以百萬的乘客,使得它們成為恐怖分子的主要攻擊目標(biāo),這些年針對(duì)這些目標(biāo)的恐怖襲擊造成了巨大的人員傷亡和經(jīng)濟(jì)損失.比如,2001年9月11日恐怖分子劫持民航客機(jī)撞擊美國紐約世界貿(mào)易中心和華盛頓五角大樓的事件中,造成了2974人死亡并造成272億元直接經(jīng)濟(jì)損失.2004年發(fā)生在西班牙馬德里的火車連環(huán)爆炸案造成191人死亡,1755人受傷和預(yù)計(jì)2.12億歐元的經(jīng)濟(jì)損失.2005年發(fā)生在英國倫敦的地鐵和公交爆炸案,造成52人死亡,700余人受傷,并造成預(yù)計(jì)20億英鎊的經(jīng)濟(jì)損失,2014年3月1號(hào)發(fā)生在我國昆明的火車站暴力砍殺事件,造成了29人死亡,143人受傷.

面對(duì)這些恐怖襲擊和安全威脅,安全機(jī)構(gòu)可以采用的措施包括在入口處或者外圍路網(wǎng)設(shè)置安檢口進(jìn)行車輛檢查以及在系統(tǒng)中進(jìn)行警力的巡邏防控等.近年來,各國也都在安全資源方面大大增加了投入,但是這些資源畢竟是有限的,安全機(jī)構(gòu)不可能在任何時(shí)候都提供全面的安全保護(hù).而且,恐怖分子和罪犯可以通過提前觀察來發(fā)現(xiàn)安全機(jī)構(gòu)的保護(hù)措施中的固定模式和弱點(diǎn),并據(jù)此來選擇最優(yōu)的攻擊策略.比如,如果我們固定只是在周二和周四兩天對(duì)火車進(jìn)行安全檢查,同樣,在對(duì)機(jī)場(chǎng)進(jìn)行巡邏時(shí),我們固定上午9點(diǎn)在第一航站樓進(jìn)行巡邏,10點(diǎn)在第二航站樓,11點(diǎn)在第三航站樓,恐怖分子就可以輕易地觀察到并利用這些固定的模式,制定攻擊策略.所以,安全機(jī)構(gòu)需要通過隨機(jī)化調(diào)度安全資源來降低對(duì)手的偵查能力.但是安全機(jī)構(gòu)在進(jìn)行有效的隨機(jī)安全資源調(diào)度時(shí)面臨著非常多的困難.一個(gè)困難是如何給各種安全部門可以采取的行動(dòng)賦予不同的權(quán)重.一些保護(hù)目標(biāo)比其他目標(biāo)更脆弱,另外有些保護(hù)目標(biāo)因?yàn)槿藛T更密集或者具有特殊的政治意義而對(duì)恐怖分子來說更加吸引力,所以在制定安全資源的分配調(diào)度方案時(shí),需要把這些因素考慮進(jìn)去,而不能簡單地把所有保護(hù)目標(biāo)看作是等價(jià)的.而人類天生不擅長產(chǎn)生這種隨機(jī)的安全策略,無法產(chǎn)生真正的隨機(jī)行為.更為困難的是,在公共交通網(wǎng)絡(luò)和其他一些非常安全領(lǐng)域中,警力資源的調(diào)度問題規(guī)模驚人得大,即使不考慮隨機(jī)性的問題,人工調(diào)度也是一個(gè)非常昂貴和耗費(fèi)體力的工作.所以如何找出有限的安全資源的最優(yōu)配置方案,以獲取最佳的安全保護(hù)方案是安全領(lǐng)域資源分配中迫切需要解決的關(guān)鍵問題.

博弈論為研究有限安全資源的最優(yōu)部署策略提供了一個(gè)恰當(dāng)?shù)臄?shù)學(xué)模型.安全博弈論將安全部門和攻擊者(如恐怖分子)之間的博弈建模成Stackelberg博弈.盡管Stackelberg博弈模型是早在20世紀(jì)30年代提出來的[1],Wang Fei-Yue教授[2]在1990年就提出把Nash和Stackelberg策略引入到智能控制與優(yōu)化中,用于協(xié)調(diào)過程的監(jiān)控.但是Stackelberg博弈在安全部門領(lǐng)域中有限資源優(yōu)化調(diào)度中的應(yīng)用是在2006年Vincent Conitzer和Tuomas Sandolm發(fā)表了奠基性論文[3]后迅速發(fā)展起來的.該領(lǐng)域早期的主要研究者是南加利福尼亞大學(xué)Milind Tambe教授領(lǐng)導(dǎo)的TEAMCORE研究小組以及杜克大學(xué)Vicent Conitzer教授領(lǐng)導(dǎo)的研究小組,但是近些年越來越多的學(xué)者參與到這項(xiàng)研究中.相關(guān)的論文廣泛發(fā)表在人工智能領(lǐng)域的頂級(jí)會(huì)議IJCAI、AAAI和AAMAS上,安全博弈論的研究已經(jīng)成為當(dāng)前人工智能研究的熱點(diǎn)之一.

經(jīng)典的Stackelberg博弈模型通常有一個(gè)領(lǐng)導(dǎo)者和一個(gè)跟隨者.每一位參與者都有其可以執(zhí)行的行動(dòng)集合,即純策略集.混合策略允許參與者以某種概率選擇不同純策略,每位參與者的收益取決于所有參與者的純策略組合,參與者混合策略的收益是純策略收益的期望,領(lǐng)導(dǎo)者先行選擇策略,跟隨者觀察到領(lǐng)導(dǎo)者的策略,然后根據(jù)觀察結(jié)果做出最優(yōu)回應(yīng).在安全領(lǐng)域,安全部門必須利用有限的資源保護(hù)有可能被攻擊的目標(biāo),而攻擊者(如恐怖分子)能夠觀察到安全部門的策略.因此,安全博弈可以很好地抽象為Stackelberg博弈,其中攻擊者充當(dāng)追隨者的角色,安全部門充當(dāng)領(lǐng)導(dǎo)者的角色[3].安全部門的純策略表示為對(duì)哪幾個(gè)可能的攻擊目標(biāo)進(jìn)行巡邏或者設(shè)置安檢點(diǎn),比如,在機(jī)場(chǎng)的哪幾個(gè)入口設(shè)置安檢點(diǎn)或者在哪些航班上安排空中警察.而攻擊者的純策略可以表示為攻擊哪一個(gè)目標(biāo),比如,某一個(gè)特定的航班,我們可以根據(jù)一些專家意見和歷史數(shù)據(jù)確定攻擊者對(duì)每個(gè)可能的攻擊目標(biāo)實(shí)施攻擊成功對(duì)雙方帶來的收益值.我們也可以考慮收益值的不確定性,將模型擴(kuò)展成貝葉斯(Bayesian)Stackelberg博弈[4].對(duì)這些博弈模型進(jìn)行求解可以得到領(lǐng)導(dǎo)者的Stackelberg均衡策略,這個(gè)均衡策略通常是一個(gè)混合策略,即以某個(gè)概率分布選擇各種可能的行動(dòng)或資源分配,安全部門就可以利用這個(gè)策略來產(chǎn)生最佳的安全資源的調(diào)度方案.

近些年來,安全博弈論的研究取得了很大的進(jìn)展.研究者們不斷提出適應(yīng)于不同問題場(chǎng)景的Stackelberg博弈均衡策略求解算法.以這些算法為核心開發(fā)的很多實(shí)際應(yīng)用系統(tǒng)已經(jīng)被美國不同領(lǐng)域的安全機(jī)構(gòu)所使用.比如,ARMOR系統(tǒng)自2007年開始就被洛杉磯警方應(yīng)用在洛杉磯國際機(jī)場(chǎng),用于規(guī)劃機(jī)場(chǎng)檢查點(diǎn)的設(shè)置以及警犬的巡邏路線[5];IRIS系統(tǒng)自2009年起被美國聯(lián)邦空中警察署(FAMS)應(yīng)用在由美國始發(fā)的航班上,用于為這些航班進(jìn)行調(diào)度分配空中警察[6];PROTECT系統(tǒng)用于規(guī)劃美國海岸警衛(wèi)隊(duì)的巡邏路線,以幫助美國海岸警衛(wèi)隊(duì)在執(zhí)行保護(hù)港口、水路和海岸安全時(shí)提高效率,目前已經(jīng)在洛杉磯、波士頓和紐約的港口使用,并在被推廣到美國更多的港口[7];TRUSTS系統(tǒng)用于協(xié)助警方制定地鐵的巡邏日程以防止逃票、地鐵站內(nèi)的非法交易及恐怖襲擊等安全危機(jī),目前正在洛杉磯地鐵上進(jìn)行測(cè)試[8].這些成功的應(yīng)用為未來安全博弈論領(lǐng)域的應(yīng)用提供了廣泛的前景,當(dāng)然同時(shí)隨著問題規(guī)模的增加,以及考慮人的有限理性和在實(shí)際執(zhí)行中的不確定性等因素,也為求解算法的研究提出了巨大的挑戰(zhàn).

1 安全博弈論的基本概念

本節(jié)介紹安全博弈論涉及到的一些基本概念.首先介紹Stackelberg博弈的概念,其次是它的擴(kuò)展形式貝葉斯Stackelberg博弈,然后介紹強(qiáng)Stackelberg均衡的概念,最后給出安全博弈論的基本模型,以及最基本的模型求解算法.

1.1 Stackelberg博弈

經(jīng)典的Stackelberg博弈是由一個(gè)領(lǐng)導(dǎo)者和一個(gè)跟隨者構(gòu)成的雙人博弈[1].領(lǐng)導(dǎo)者首先確定自己的混合策略,跟隨者首先通過觀察得到領(lǐng)導(dǎo)者的策略,然后選擇能夠最大化其收益的策略進(jìn)行博弈.因?yàn)楸疚闹饕P(guān)注Stackelberg博弈在安全領(lǐng)域中的應(yīng)用,在這些領(lǐng)域中,領(lǐng)導(dǎo)者試圖保護(hù)一些目標(biāo)免受潛在的攻擊.所以,術(shù)語“保護(hù)者”和“領(lǐng)導(dǎo)者”,以及“攻擊者”和“跟隨者”分別可以互換使用.為了表達(dá)的簡單,我們也經(jīng)常把領(lǐng)導(dǎo)者(保護(hù)者)稱為“她”,而把跟隨者(攻擊者)稱為“他”.

在Stackelberg博弈中,領(lǐng)導(dǎo)者因?yàn)槭紫茸龀霾呗赃x擇,而可以獲得較多的利益,這經(jīng)常被稱為“先行者優(yōu)勢(shì)”.利用文獻(xiàn)[3]中給出的一個(gè)簡單的收益矩陣來解釋這種優(yōu)勢(shì),如圖1所示.

圖1 Stackelberg博弈收益矩陣舉例

領(lǐng)導(dǎo)者是行參與者,跟隨者是列參與者.這個(gè)博弈唯一的純策略納什均衡是領(lǐng)導(dǎo)者選擇a策略而跟隨者選擇c策略,這樣領(lǐng)導(dǎo)者得到的收益是2.但是實(shí)際上,對(duì)于領(lǐng)導(dǎo)者來說,b策略是嚴(yán)格占優(yōu)策略.所以,如果領(lǐng)導(dǎo)者可以先行確定自己選擇b策略,跟隨者為了使自己獲得更高的收益會(huì)選擇d策略,從而使得領(lǐng)導(dǎo)者得到3的收益.進(jìn)一步,如果領(lǐng)導(dǎo)者可以先行確定選擇a和b各為0.5的混合策略,跟隨者仍然會(huì)選擇d策略,從而可以使得領(lǐng)導(dǎo)者得到更高的3.5的期望收益1在這類博弈中,我們經(jīng)常假設(shè)當(dāng)對(duì)于跟隨者來說兩個(gè)純策略帶來的收益相同時(shí),他會(huì)選擇對(duì)領(lǐng)導(dǎo)者更有利的策略來打破僵局,否則,最優(yōu)策略的概念將無法很明確的定義,這個(gè)我們會(huì)在后面介紹強(qiáng)Stackelberg均衡時(shí),詳細(xì)介紹..下面,我們給出Stackelberg博弈更一般化的定義.領(lǐng)導(dǎo)者(保護(hù)者/安全部門)用Θ來表示,跟隨者(攻擊者)用Ψ來表示.每個(gè)參與者有一個(gè)純策略集,領(lǐng)導(dǎo)者的純策略集用,跟隨者的純策略集用來表示.混合策略是定義在參與者純策略集上的概率分布,x∈X表示領(lǐng)導(dǎo)者的混合策略,q∈Q表示跟隨者的混合策P略.這里,xi∈[0,1]表示領(lǐng)導(dǎo)者使用純策略θi∈Θ的概率P,類似的,qi∈[0,1]表示跟隨者使用純策略ψi∈Ψ的概率.我們用SΘ來表示領(lǐng)導(dǎo)者純策略的索引集,SΨ表示跟隨者純策略的索引集.所有可能的純策略組合下,領(lǐng)導(dǎo)者和跟隨者的收益分別定義為:

給定領(lǐng)導(dǎo)者的混合策略x∈X和跟隨者的混合策略q∈Q,可以將上面純策略的收益函數(shù)拓展到混合策略的形式,分別定義為:

1.2 貝葉斯Stackelberg博弈

Stackelberg博弈的每個(gè)參與者(領(lǐng)導(dǎo)者或者跟隨者)都可以拓展成有多種可能的類型,每種類型的收益值不同,這樣就成了貝葉斯Stackelberg博弈.在安全領(lǐng)域中,通常假設(shè)保護(hù)者(領(lǐng)導(dǎo)者)Θ的類型是確定的.而攻擊者(跟隨者)可能是多種類型中的一種,用γ∈Γ來表示.比如,安全部門面臨潛在的攻擊者可能是恐怖襲擊分子,也可能是毒品走私者.每種類型用一個(gè)不同的而且很可能是不相關(guān)的收益矩陣來表示.也就是說,面對(duì)不同類型的攻擊者時(shí),領(lǐng)導(dǎo)者和跟隨者的收益都是變化的.領(lǐng)導(dǎo)者不知道在某一確定的時(shí)刻他所面對(duì)的跟隨者是哪種類型的,但是,她知道各種類型的攻擊者出現(xiàn)的可能性.我們用pγ來表示一種特定的類型的跟隨者γ∈Γ出現(xiàn)的概率.跟隨者知道自己屬于哪種類型,所以他總是對(duì)領(lǐng)導(dǎo)者和他自己的收益具有完全信息.在這種情況下,領(lǐng)導(dǎo)者和跟隨者的純策略集還是不變的(分別是和),所以對(duì)于每種跟隨者的類型,所有可能的純策略組合下,領(lǐng)導(dǎo)者和跟隨者的收益定義為:

另外,每種跟隨者類型γ∈Γ的混合策略用qγ∈Q來表示.相應(yīng)地,對(duì)于給定的跟隨者類型γ∈Γ,領(lǐng)導(dǎo)者的混合策略x∈X和跟隨者的混合策略qγ∈Q,領(lǐng)導(dǎo)者和追隨者的期望收益分別定義為:

在這種形式化的模型中,領(lǐng)導(dǎo)者的目標(biāo)是在考慮到所有可能的跟隨者類型都會(huì)選擇最佳響應(yīng)的情況下,選擇一種能夠最大化她的期望收益的混合策略x∈X.這樣,每種跟隨者都選擇在對(duì)應(yīng)的收益矩陣下,對(duì)這個(gè)領(lǐng)導(dǎo)者的混合策略的最佳響應(yīng)策略.我們定義所有跟隨者類型的最佳響應(yīng)組合如下:

這樣,Stackelberg博弈中描述的“首先領(lǐng)導(dǎo)者承諾使用某一混合策略,然后每個(gè)跟隨者觀察這一策略,之后選擇最佳響應(yīng)”的場(chǎng)景可以很好地刻畫安全領(lǐng)域中安全部門所遇到的問題.安全部門需要首先部署好巡邏策略,對(duì)目標(biāo)進(jìn)行保護(hù).對(duì)手通過觀察監(jiān)視來知道安全部門的混合策略,然后選擇最大化自己期望收益的目標(biāo)進(jìn)行攻擊.攻擊者雖然知道安全部門的混合策略,但是他仍然不知道他將要實(shí)施攻擊的那一天,安全部門到底采用哪種巡邏方案.在Stackelberg博弈中,領(lǐng)導(dǎo)者是否能夠獲得先動(dòng)者優(yōu)勢(shì),有一個(gè)非常重要的因素是,是否允許采用混合策略.如果領(lǐng)導(dǎo)者只能采用純策略,那么先動(dòng)者可能得到更高的收益也可能得到更壞的收益.例如,在石頭剪刀布博弈中,先動(dòng)者不管承諾采用哪種純策略都肯定會(huì)失敗.但是如果先動(dòng)者可以選擇混合策略,那么先動(dòng)者得到的收益至少不會(huì)比同時(shí)行動(dòng)時(shí)差.Letchford等人[9],給出了不同類型的博弈下先動(dòng)者優(yōu)勢(shì)的詳細(xì)討論.

1.3 強(qiáng)Stackelberg均衡

博弈論中,最常見的解概念是Nash均衡.在這個(gè)均衡的策略組合下,任何一個(gè)參與者不能通過單方面改變策略來增加自己的收益[10].Stackelberg均衡是在Stackelberg博弈中Nash均衡概念的一種精煉.它是一種子博弈完美均衡.在這個(gè)均衡下,每個(gè)參與者在原博弈的每個(gè)子博弈中都會(huì)選擇最佳響應(yīng).這樣可以在均衡路徑中把只有在不可信威脅下存在的均衡策略組合消除.子博弈完美均衡是一種很自然的要求,但是當(dāng)多個(gè)策略對(duì)于跟隨者來說沒有區(qū)別時(shí),這個(gè)概念沒法保證有唯一解.為了得到唯一解,Leitmann[11]提出了兩種Stackelberg均衡的概念,之后被Breton等人[12]分別命名為“強(qiáng)Stackelberg均衡”和“弱Stackelberg均衡”.當(dāng)跟隨者在多個(gè)策略下收益相同時(shí),在強(qiáng)均衡的情況下,假設(shè)他總是選擇對(duì)領(lǐng)導(dǎo)者最有利的策略;而在弱均衡的情況下,假設(shè)他總是選擇對(duì)領(lǐng)導(dǎo)者最不利的策略.強(qiáng)Stackelberg均衡在所有Stackelberg博弈中都是存在的,而弱均衡不一定存在[12].Von Stengel和Zamir[13]指出領(lǐng)導(dǎo)者經(jīng)常能夠通過選擇無限接近于均衡解的策略使得跟隨者傾向于選擇對(duì)她有利的策略,從而達(dá)到她更想要的強(qiáng)均衡.所以在大多數(shù)安全博弈的文獻(xiàn)中,我們采用強(qiáng)Stackelberg均衡作為解的概念.下面給出強(qiáng)Stackelberg均衡的定義.

定義1.一個(gè)策略組合為強(qiáng)Stackelberg均衡,當(dāng)且僅當(dāng)它滿足以下條件:

1)領(lǐng)導(dǎo)者策略為最佳響應(yīng):

2)跟隨者策略為最佳響應(yīng):

3)當(dāng)跟隨者存在多個(gè)最佳響應(yīng)時(shí),跟隨者選擇對(duì)領(lǐng)導(dǎo)者有利的策略來打破僵局:

其中,Q?(x)是當(dāng)領(lǐng)導(dǎo)者的策略為x時(shí),跟隨者的最佳響應(yīng)集合.

1.4 Stackelberg安全博弈

本文,關(guān)注的是一類特殊的安全領(lǐng)域的貝葉斯Stackelberg博弈,我們稱之為安全博弈.為了能夠讓讀者更直觀地理解安全博弈論的模型和求解思路,首先簡單描述洛杉磯警方(LAWA)決定什么時(shí)候在哪條通往洛杉磯機(jī)場(chǎng)(LAX)的道路上設(shè)置車輛檢查站中遇到的安全問題場(chǎng)景,然后介紹將這個(gè)問題建模成貝葉斯Stackelberg博弈的方法.

在洛杉磯機(jī)場(chǎng),有特定數(shù)量的道路可以通往機(jī)場(chǎng).恐怖分子可能會(huì)駕駛帶有爆炸物品的汽車通過某一條道路進(jìn)入機(jī)場(chǎng),對(duì)機(jī)場(chǎng)實(shí)施恐怖襲擊.洛杉磯警方可以通過在這些道路上設(shè)置車輛檢查站來防止這種攻擊.但是他們遇到的問題是,一方面沒有足夠的警力資源同時(shí)在所有的道路上設(shè)置檢查站,另一方面因?yàn)槁每偷牧髁刻?如果對(duì)所有旅客都進(jìn)行篩查會(huì)花費(fèi)非常長的時(shí)間從而造成旅客的延誤.所以警方需要制定一個(gè)應(yīng)該什么時(shí)間和地點(diǎn)設(shè)置檢查點(diǎn)來檢查駛往機(jī)場(chǎng)的車輛的方案.洛杉磯警方要求在設(shè)計(jì)方案時(shí)要考慮到以下3個(gè)方面:1)潛在的襲擊者會(huì)觀察到警方的調(diào)度方案然后再確定他們的攻擊策略,這樣會(huì)使得確定性的調(diào)度方案非常容易被攻擊;2)警方對(duì)可能遇到的對(duì)手的信息是未知的或者不確定的;3)在隨機(jī)化的同時(shí),還要考慮不同的保護(hù)目標(biāo)可能帶來的成本和收益的差別.令T={t1,···,tn}為n個(gè)需要保護(hù)的目標(biāo)組成的集合(比如通往機(jī)場(chǎng)的道路的數(shù)量).保護(hù)者有可能用一些資源來保護(hù)這些目標(biāo)(比如,警方可以同時(shí)設(shè)置檢查點(diǎn)的個(gè)數(shù)),用R={r1,···,rm}來表示.假設(shè)警方有兩個(gè)資源(可以同時(shí)設(shè)置兩個(gè)車輛檢查站),則警方的純策略的集合為P={(t1,t2),(t1,t3),···,(tn?1,tn)}, 也就是在n個(gè)保護(hù)目標(biāo)中選出兩個(gè)的所有組合.假設(shè)可能面臨的攻擊者類型的數(shù)量為k.每一種攻擊者類型γ∈Γ可以選擇在n個(gè)目標(biāo)中選擇任何一個(gè)進(jìn)行攻擊,或者選擇根本不進(jìn)行攻擊,所以攻擊者的純策略集合為PΨ={t1,···,tn,none}.

當(dāng)目標(biāo)ti沒有被保護(hù)而受到類型為γ的攻擊者攻擊時(shí),保護(hù)者的收益用表示,攻擊者的收益用表示.類似地,當(dāng)該目標(biāo)被保護(hù)著而受到攻擊時(shí),保護(hù)者的收益用表示,攻擊者的收益用表示.在具體的安全領(lǐng)域問題中,這些收益值可以由領(lǐng)域?qū)＜襾斫o出.但是,通常這些收益值之間需要滿足和.也就是說,對(duì)于同一個(gè)目標(biāo)ti,對(duì)于任意一個(gè)攻擊者類型γ,當(dāng)該目標(biāo)沒有被保護(hù)時(shí),攻擊者進(jìn)行攻擊得到收益要比該目標(biāo)被保護(hù)時(shí)進(jìn)行攻擊得到的收益高,而對(duì)于保護(hù)者恰恰相反.這個(gè)性質(zhì)對(duì)于安全領(lǐng)域的問題通常是普遍適用的.這個(gè)要求類似于零和博弈的條件,但是比零和博弈的條件更寬松.Powell[14]給出了一些這種博弈通常不是零和博弈的原因.因?yàn)樵诎踩I(lǐng)域中,恐怖分子可能因?yàn)橐恍┨厥獾恼我蛩卣J(rèn)為某些特定的目標(biāo)特別重要,而這些目標(biāo)在警方眼里并不是特別重要;又比如,恐怖分子有時(shí)候可能認(rèn)為即使是一個(gè)失敗的攻擊也能給他帶來一定的收益,因?yàn)楣魩淼囊恍┕姷目只?另外恐怖分子可能在對(duì)特定的目標(biāo)進(jìn)行攻擊時(shí)需要有額外的花費(fèi),而這些目標(biāo)對(duì)警方來說可能并不是特別重要.圖2給出了對(duì)于一個(gè)目標(biāo)進(jìn)行攻擊時(shí)可能產(chǎn)生的4個(gè)收益值示例.當(dāng)警方在保護(hù)該目標(biāo)時(shí),攻擊者選擇攻擊該目標(biāo),警方得到的收益為5,而攻擊者得到的收益為?10;而如果警方?jīng)]有在保護(hù)該目標(biāo),而攻擊者選擇進(jìn)行攻擊,警方得到的收益為?20,而攻擊者得到的收益為30.

圖2 對(duì)一個(gè)目標(biāo)進(jìn)行攻擊的可能產(chǎn)生的收益值示例

有了以上這些定義,可以寫出每種攻擊者類型的標(biāo)準(zhǔn)型收益矩陣.圖3給出了一個(gè)具有兩個(gè)目標(biāo)、兩種攻擊者類型、一個(gè)保護(hù)資源的貝葉斯安全博弈的收益矩陣示例.

圖3 貝葉斯安全博弈收益矩陣示例

在圖3的表示方式中,每種攻擊者類型對(duì)應(yīng)一個(gè)收益矩陣,所以一共有k個(gè)收益矩陣,但是在最基本的貝葉斯Stackelberg博弈的求解算法(1.5中介紹的第一個(gè)算法MultiLPs)中,要求將這k個(gè)收益矩陣通過海薩尼轉(zhuǎn)換(Harsanyi transformation)變換成一個(gè)大的標(biāo)準(zhǔn)型博弈矩陣然后進(jìn)行求解.而這個(gè)變換產(chǎn)生的新的收益矩陣中,攻擊者的純策略數(shù)量是隨著攻擊者的類型指數(shù)級(jí)增長的.比如,如果在圖3的表示形式中,每個(gè)攻擊者的純策略數(shù)量為n+1,攻擊者的類型數(shù)量為k,而在經(jīng)過海薩尼轉(zhuǎn)換后得到的標(biāo)準(zhǔn)型博弈矩陣中,攻擊者的純策略數(shù)量為(n+1)k個(gè),這樣會(huì)使得問題的求解非常復(fù)雜,所以在安全博弈的問題中,通常直接使用1.3中的緊湊型的表示方式,然后直接針對(duì)這個(gè)緊湊型的表示方式來設(shè)計(jì)求解算法,這主要是利用了安全博弈問題中一個(gè)很重要的特點(diǎn),也就是不同攻擊者類型的收益矩陣之間是相互獨(dú)立的.

實(shí)際上,即使利用1.3中的表示方式,我們還會(huì)面臨另外一個(gè)問題,也就是在這個(gè)表示方式中,如果保護(hù)者的資源數(shù)量為m,而需要保?護(hù)的￠目標(biāo)數(shù)量為k,那么保護(hù)者的純策略的數(shù)量為≈nm,所以保護(hù)者的純策略數(shù)量是隨著資源的數(shù)量指數(shù)級(jí)增長的,這會(huì)使得每個(gè)矩陣行的數(shù)量會(huì)非常大.而實(shí)際上,我們可以給出一種更加緊湊的表示方式,使得矩陣行的數(shù)量為n.這是因?yàn)樵诎踩┺牡氖找婢仃囍?還有另外一個(gè)非常重要的特點(diǎn),也就是雙方的收益只與要被攻擊的目標(biāo)是否被保護(hù)者保護(hù)有關(guān),而與攻擊目標(biāo)以外的其他目標(biāo)是否被當(dāng)前保護(hù)者的純策略所保護(hù)無關(guān).比如,當(dāng)攻擊者選擇從第一條道路進(jìn)入機(jī)場(chǎng)實(shí)施攻擊時(shí),警方有沒有保護(hù)第二條或者第三條道路,不影響雙方得到的收益.下面利用這一特點(diǎn),給出一種更緊湊的安全博弈表示方式.

定義一個(gè)每個(gè)目標(biāo)被保護(hù)的概率向量C,其中每個(gè)目標(biāo)t被保護(hù)的概率為Pct.因?yàn)楸Ｗo(hù)者一共有m個(gè)資源,所以有約束m.然后t對(duì)于每種攻擊者類型γ定義一個(gè)每個(gè)目標(biāo)被攻擊的概率向量Aγ,我們P限定每個(gè)目標(biāo)t被攻擊的概率[0,1],并且[0,1].因?yàn)樵趶?qiáng)StaPckelberg均衡時(shí),攻擊者的最優(yōu)策略為純策略.而=0P意味著攻擊者選擇的純策略為不攻擊任何目標(biāo),=1 且=1意味著攻擊者選擇的純策略為攻擊目標(biāo)ti.當(dāng)一個(gè)目標(biāo)t被類型為γ的攻擊者攻擊時(shí),保護(hù)者的收益用式(10)中的(t,C)來表示.這樣,當(dāng)攻擊者的攻擊概率向量為Aγ時(shí),保護(hù)者的期望收益用式(11)中的(C,Aγ)來表示.類似地,我們也可以定義攻擊者的收益(t,C)和(C,Aγ).另外在式(12)中給出另外一個(gè)有用的定義攻擊集:在給定保護(hù)概率向量C下,所有能夠給攻擊類型為γ的攻擊者帶來最大期望收益的攻擊目標(biāo)集合.

在強(qiáng)Stackelberg均衡(SSE)時(shí),攻擊者在攻擊集中選擇最大化保護(hù)者期望收益的目標(biāo)進(jìn)行攻擊.我們用t?來表示這個(gè)最優(yōu)的目標(biāo).那么當(dāng)保護(hù)者面臨攻擊類型γ的概率為pγ時(shí),保護(hù)者的SSE期望收益為(C)=(t?,C)×pγ,而攻擊者的期望收益為(C)=(t?,C).

1.5 幾個(gè)基本的求解算法(Baseline Solvers)

本節(jié)介紹求解Stackelberg博弈的3個(gè)基本算法,它們分別是Conitzer和Sandholm于2006年提出的MultiLPs算法[3]、Paruchuri等人于2008年提出的DOBSS算法[4]和Kiekintveld等人于2009提出的ERASER算法[15].MultipleLPs是針對(duì)標(biāo)準(zhǔn)型的Stackelberg博弈求解的最基本多項(xiàng)式時(shí)間的算法,它也可以用來求解貝葉斯Stackelberg博弈,但是需要將收益矩陣通過海薩尼轉(zhuǎn)換變成標(biāo)準(zhǔn)型的,會(huì)使得求解時(shí)間隨著追隨者類型指數(shù)級(jí)增長.DOBSS算法是針對(duì)貝葉斯Stackelberg博弈提出的一個(gè)基本求解算法,它直接對(duì)圖3形式的收益矩陣進(jìn)行求解.ERASER算法是針對(duì)貝葉斯安全博弈提出的最基本的求解算法,它直接針對(duì)1.4節(jié)中提出的最緊湊形式的貝葉斯安全博弈進(jìn)行求解.

1.5.1 MultiLPs算法

本節(jié)介紹由Conitzer和Sandholm[3]提出的求解貝葉斯Stackelberg博弈中領(lǐng)導(dǎo)者最優(yōu)策略的基準(zhǔn)算法.這個(gè)算法利用強(qiáng)Stackelberg均衡的定義,將求解領(lǐng)導(dǎo)者最優(yōu)混合策略的問題建立成以下優(yōu)化問題:

其中,=haγ?i表示所有貝葉斯跟隨者的最優(yōu)純策略,也就是每種跟隨者類型對(duì)于領(lǐng)導(dǎo)者策略的最佳響應(yīng)純策略.x?是需要求解的領(lǐng)導(dǎo)者的最優(yōu)混合策略.式(13)等價(jià)于一個(gè)多線性規(guī)劃(LP)問題.思想是枚舉所有可能的跟隨者純策略組合aΨ=haγi,其中γ∈Γ,aγ∈P對(duì)于跟隨者的每一種純策略組合求解以下線性規(guī)劃問題得到當(dāng)aΨ為跟隨者的最佳響應(yīng)時(shí),領(lǐng)導(dǎo)者的最優(yōu)混合策略.

(2)游客出行方式更加靈活。三峽游輪旅游方式不再是主要出行方式，部分游客會(huì)趨向于選擇以更加靈活的方式在景區(qū)之間流動(dòng)。以自駕游大軍及背包客為代表的游客群體正在逐漸突破傳統(tǒng)三峽旅行方式，新的旅行方式以恩施州大峽谷景區(qū)為代表，該景區(qū)將逐步成為三峽地區(qū)新的旅游輻射中心。

其中,最優(yōu)一個(gè)約束保證aΨ是跟隨者的最佳響應(yīng).在所有的線性規(guī)劃中,有些線性規(guī)劃可能是無解的,但是總存在至少一個(gè)線性規(guī)劃有可行解.進(jìn)而,領(lǐng)導(dǎo)者的最佳混合策略x?就是在所有有可行解的LP中目標(biāo)函數(shù)值最大(也就是領(lǐng)導(dǎo)者的期望收益)的規(guī)劃所對(duì)應(yīng)的解.

1.5.2 DOBSS算法

DOBSS有效地將求解指數(shù)級(jí)的線性規(guī)劃問題減少成求解一個(gè)緊湊型的MILP問題,從而使得這個(gè)問題可以非常高效地利用運(yùn)籌學(xué)研究中提出的先進(jìn)的規(guī)劃問題求解技術(shù).DOBSS MILP的核心思想是用0～1向量aγ=[] 來表示跟隨者的純策略.其中,如果跟隨者類型γ的個(gè)體選擇第j個(gè)純策略則=1,否則為0.其中,U(x,j)表示當(dāng)領(lǐng)導(dǎo)者選擇混合策略x而跟隨者選擇他的第j個(gè)純策略時(shí)領(lǐng)導(dǎo)者的期望收益,而U(x,j)是相應(yīng)的跟隨者的期望收益.M是一個(gè)大常數(shù).

1.5.3 ERASER算法

ERASER算法的基本思想和DOBSS一樣,但是它直接對(duì)緊湊型的安全博弈進(jìn)行求解.這樣,它就可以避免枚舉指數(shù)級(jí)的保護(hù)者的純策略.ERASER的MILP如下所示:其中,保護(hù)者的策略用1.4節(jié)中定義的向量C來表示.和在DOBSS中一樣,攻擊者類型γ的策略為aγ.(C,t)和(C,t)分別表示當(dāng)保護(hù)者的策略向量為C,而攻擊者類型γ的個(gè)體選擇攻擊目標(biāo)t時(shí),保護(hù)者和攻擊者的期望收益.R表示保護(hù)者擁有的資源的數(shù)量,M是一個(gè)大常數(shù).

2 安全博弈論的實(shí)際應(yīng)用系統(tǒng)和新興的應(yīng)用方向

安全博弈論是一個(gè)以實(shí)際應(yīng)用為導(dǎo)向的研究領(lǐng)域.過去幾年,基于Stackelberg安全博弈框架設(shè)計(jì)的實(shí)際應(yīng)用系統(tǒng)已經(jīng)被美國不同領(lǐng)域的安全機(jī)構(gòu)所使用,并且嘗試應(yīng)用到其他更多安全領(lǐng)域中.這些具體的實(shí)際應(yīng)用場(chǎng)景為安全博弈論的研究提出了很多挑戰(zhàn),本節(jié)介紹安全博弈論的實(shí)際應(yīng)用系統(tǒng)和一些新興的應(yīng)用方向,為后文討論算法研究進(jìn)展和新的研究挑戰(zhàn)提供問題場(chǎng)景.

2.1 ARMOR-機(jī)場(chǎng)檢查站的設(shè)置及巡邏調(diào)度系統(tǒng)

洛杉磯國際機(jī)場(chǎng)(LAX)是美國最大的目的地機(jī)場(chǎng),每年的旅客流量在6000到7000萬左右,因此也成為美國西海岸主要的恐怖襲擊目標(biāo)之一,過去幾年已經(jīng)有多名密謀襲擊者被抓獲.洛杉磯警方采取不同的措施來保護(hù)機(jī)場(chǎng),包括設(shè)置車輛檢查站、警察部隊(duì)(和警犬)在航站樓巡邏,安全篩選和檢查乘客行李.

但是他們遇到的問題是,一方面沒有足夠的警力資源來全天候?qū)C(jī)場(chǎng)發(fā)生的每件事情進(jìn)行監(jiān)控,另一方面因?yàn)槁每偷牧髁刻?如果對(duì)所有旅客都進(jìn)行篩查會(huì)花費(fèi)非常長的時(shí)間從而造成旅客的延誤.所以洛杉磯警方必須要采取一些措施進(jìn)行抽檢.如果他們按照確定的計(jì)劃設(shè)置車輛檢查點(diǎn)以及警察部隊(duì)和警犬的巡邏,恐怖分子可以通過觀察輕易地知道警方的計(jì)劃,然后規(guī)避開檢查點(diǎn)和巡邏路線實(shí)施攻擊,使得警方的計(jì)劃失效,所以警方需要采用隨機(jī)化的策略.洛杉磯警方在制定隨機(jī)化的安保策略時(shí)主要需要解決以下兩個(gè)問題.第一個(gè)是考慮到有非常多的道路可以通往機(jī)場(chǎng),應(yīng)該什么時(shí)間在什么地點(diǎn)設(shè)置檢查點(diǎn)來檢查駛往機(jī)場(chǎng)的車輛.圖4(a)是在機(jī)場(chǎng)的一個(gè)入站口設(shè)置的車輛檢查點(diǎn)的例子.警察檢查經(jīng)過的車輛,當(dāng)發(fā)現(xiàn)可疑車輛時(shí),警方將對(duì)其進(jìn)行更加詳細(xì)的檢查.洛杉磯警方希望得到一個(gè)特定時(shí)間段的車輛檢查點(diǎn)隨機(jī)設(shè)置方案.比如,如果一共有3條路可以通往機(jī)場(chǎng),而同一時(shí)間段只能設(shè)置兩個(gè)車輛檢查點(diǎn),那么一個(gè)可能的設(shè)置方案是周一在入口1和入口2設(shè)置車輛檢查點(diǎn),周二在入口1和入口3設(shè)置檢查點(diǎn),等等.第二個(gè)問題是制定警犬在洛杉磯國際機(jī)場(chǎng)8個(gè)航站樓之間的巡邏路線.比如如果有3只警犬,一種可能的分配方案是第一天將警犬分別安排在1,3,6航站樓,第二天安排在2,4,6航站樓等.因?yàn)槁迳即墖H機(jī)場(chǎng)目前擁有的8個(gè)航站樓有不同的特性,如大小、載客量、客流量、國際與國內(nèi)航班數(shù)量.這些因素導(dǎo)致8個(gè)航站樓有不同的風(fēng)險(xiǎn)評(píng)估結(jié)果,所以安排巡邏方案的時(shí)候就要考慮到這些因素.圖4(b)是洛杉磯機(jī)場(chǎng)警犬巡邏的一個(gè)例子.

圖4 洛杉磯國際機(jī)場(chǎng)安全問題[16]

考慮到面臨的以上實(shí)際問題,洛杉磯警方要求在設(shè)計(jì)方案是要考慮到以下3個(gè)挑戰(zhàn):1)潛在的襲擊者會(huì)觀察到警方的調(diào)度方案,然后再確定他們的攻擊策略,這樣會(huì)使得確定性的調(diào)度方案非常容易被攻擊;2)警方對(duì)可能遇到的對(duì)手的信息是未知的或者不確定的;3)在隨機(jī)化的同時(shí),還要考慮不同的保護(hù)目標(biāo)可能帶來的成本和收益的差別.基于貝葉斯Stackelberg博弈論的ARMOR系統(tǒng)(Assistant for Randomized Monitoring over Routes)用于規(guī)劃洛杉磯國際機(jī)場(chǎng)檢查點(diǎn)的設(shè)置以及警犬的巡邏路線.以設(shè)置檢查點(diǎn)為例,假設(shè)洛杉磯國際機(jī)場(chǎng)有n條進(jìn)入機(jī)場(chǎng)的道路,警方在這n條道路上設(shè)置m(m

2.2 IRIS-空中警察調(diào)度系統(tǒng)

美國聯(lián)邦空中警察署(FAMS)負(fù)責(zé)將空中警察分配到始發(fā)地美國的航班上,以阻止?jié)撛诘墓?每架飛機(jī)具有不同的重要性,由于飛機(jī)上的乘客數(shù)量,地點(diǎn)和目的地城市的人口數(shù)量,來自不同國家的國際航班,還有其他一些特殊事件等原因,空中警察的分配問題比ARMOR系統(tǒng)更具挑戰(zhàn):他們每天需要將數(shù)量有限的空中警察分配給成千上萬的商業(yè)航班,空中警察的分配必須遵守各種類型的限制條件,如每一名空中警察需要飛回其基地,并滿足起飛、降落、休息等很多時(shí)間上的約束.找出滿足所有限制條件的,并考慮每架飛機(jī)的不同重要性的最優(yōu)隨機(jī)調(diào)度策略是一項(xiàng)非常困難的任務(wù).在此背景下,TEAMCORE研究小組開發(fā)了IRIS系統(tǒng)(Intelligent Randomization In Scheduling),并于2009年10月開始為所有國際航班的空中警察進(jìn)行調(diào)度[6].

在IRIS系統(tǒng)中,保護(hù)目標(biāo)為n個(gè)航班的集合,攻擊者可以從這n架航班中選擇任何一架進(jìn)行攻擊.FAMS可以將m

2.3 PROTECT-海岸警衛(wèi)隊(duì)巡邏系統(tǒng)

美國海岸警衛(wèi)隊(duì)(USCG)的任務(wù)包括維持海上安全、港口安全以及內(nèi)河航道的安全.由于恐怖主義和毒品走私的威脅,這些地方面臨的風(fēng)險(xiǎn)日益增加.美國海岸警衛(wèi)隊(duì)通過巡邏的方式來保護(hù)港口的基礎(chǔ)設(shè)施.然而,有限的安全資源使海岸警衛(wèi)隊(duì)無法隨時(shí)隨地保護(hù)所有重要設(shè)施,攻擊者便有了可乘之機(jī).為了協(xié)助美國海岸警衛(wèi)隊(duì)的資源分配,TEAMCORE研究小組設(shè)計(jì)了基于Stackelberg博弈模型的PROTECT系統(tǒng)(Port Resilience Operational/Tactical Enforcement to Combat Terrorism)[18?20].

開發(fā)PROTECT系統(tǒng)的目的是幫助美國海岸警衛(wèi)隊(duì)在執(zhí)行保護(hù)港口、水路、和海岸安全(合稱PWCS)時(shí)提高效率.對(duì)PWCS的巡邏著眼于保護(hù)重點(diǎn)設(shè)施,由于資源所限,任何設(shè)施都無法獲得全天候的保護(hù),因此對(duì)資源配置的優(yōu)化就變得至關(guān)重要.PROTECT系統(tǒng)同時(shí)考慮攻擊者的觀測(cè)能力和不同設(shè)施的價(jià)值,輸出美國海岸警衛(wèi)隊(duì)巡邏的日程表,包括什么時(shí)候開始巡邏,每次巡邏經(jīng)過哪些目標(biāo)區(qū)域,以及在每個(gè)目標(biāo)區(qū)域里執(zhí)行的巡邏活動(dòng).

和之前的系統(tǒng)相比,PROTECT系統(tǒng)有很多創(chuàng)新點(diǎn).首先,它不像以前的系統(tǒng)那樣假設(shè)攻擊者是完全理性的,而是基于行為經(jīng)濟(jì)學(xué)中的隨機(jī)最優(yōu)選擇(quantal response)理論對(duì)攻擊者的行為進(jìn)行建模;第二,為了提高效率,系統(tǒng)在尋找均衡和最優(yōu)解時(shí)采取了更加緊湊的方式來表示攻擊者的策略空間;第三,PROTECT系統(tǒng)通過真實(shí)的數(shù)據(jù)來評(píng)價(jià)其性能:1)比較人工產(chǎn)生的調(diào)度方案和PROTECT系統(tǒng)產(chǎn)生的調(diào)度方案在實(shí)際應(yīng)用中的效果;2)利用真人實(shí)戰(zhàn)演習(xí)對(duì)系統(tǒng)進(jìn)行攻擊,并分析結(jié)果數(shù)據(jù).PROTECT模型已經(jīng)部署在波士頓、紐約、洛杉磯的港口,并且可能被更多的美國港口采用[21?22].PROTECT系統(tǒng)除了用來保護(hù)港口外,還被用于紐約史泰登島的渡輪保護(hù).在這個(gè)問題中,需要利用救生船對(duì)目標(biāo)區(qū)域進(jìn)行巡邏來保護(hù)載有乘客的擺渡船.面臨的主要挑戰(zhàn)是被保護(hù)的目標(biāo)(擺渡船)是在連續(xù)的空間中不斷移動(dòng)的,而攻擊者可以選擇任何時(shí)刻進(jìn)行攻擊.這種移動(dòng)目標(biāo)的保護(hù)使得博弈模型變成連續(xù)策略集空間,帶來巨大的計(jì)算挑戰(zhàn).

2.4 TRUST-城市軌道交通系統(tǒng)安全系統(tǒng)

城市軌道交通系統(tǒng)面臨著多方面的安全挑戰(zhàn),包括防止逃票,阻止非法交易和打擊恐怖襲擊.特別地,在一些城市的軌道交通系統(tǒng)中(比如,洛杉磯的地鐵),乘客被要求自覺購票乘車,但是沒有采取強(qiáng)制措施.警方會(huì)在地鐵站中進(jìn)行巡邏,抽查行人的車票,如果遇到逃票的乘客將給予罰款.這樣一種信用乘車的方式可能會(huì)面臨由于嚴(yán)重逃票帶來的經(jīng)濟(jì)損失.以洛杉磯地鐵為例,它每天運(yùn)送約30萬乘客,每年逃票帶來的損失預(yù)計(jì)為560萬美元.洛杉磯警察局(LASD)雇傭一些工作人員在列車上或者站臺(tái)上檢票.由于巡邏檢票的工作人員數(shù)量較少,不可能覆蓋所有的列車和站臺(tái),因此洛杉磯警察局需要一些機(jī)制來設(shè)計(jì)檢票人員的巡邏路線.如果巡邏檢票的調(diào)度策略有比較固定的模式,那么逃票者可能會(huì)觀察到這個(gè)模式并且利用它來逃票.目前洛杉磯警察局依賴人工制定巡邏日程,但是由于人工制定的調(diào)度策略通常有固定模式,而且日程的制定需要考慮很多復(fù)雜的因素,比如列車運(yùn)行時(shí)間、發(fā)車間隔、日程長度等,因此制定調(diào)度策略的人工負(fù)擔(dān)很重.

TRUST系統(tǒng)將地鐵系統(tǒng)巡邏問題抽象成領(lǐng)導(dǎo)者-跟隨者的Stackelberg博弈.領(lǐng)導(dǎo)者(洛杉磯警察局)采用混合策略,跟隨者(可能逃票的乘客)觀察到這個(gè)策略并決定是否買票.由于運(yùn)輸系統(tǒng)的復(fù)雜性使得可能的巡邏策略數(shù)量呈指數(shù)級(jí)增長,這給計(jì)算最優(yōu)巡邏策略提出了很大挑戰(zhàn).為了解決此問題,TRUST使用了緊湊的表達(dá)方式,同時(shí)考慮到了時(shí)間和空間結(jié)構(gòu)[23].洛杉磯警察局目前正在洛杉磯地鐵上測(cè)試TRUST系統(tǒng),計(jì)劃根據(jù)系統(tǒng)產(chǎn)生的日程來安排巡邏,并檢測(cè)收入是否增長進(jìn)而確定逃票者是否減少.在對(duì)這個(gè)系統(tǒng)進(jìn)行測(cè)試的過程中,遇到的一個(gè)非常重要的挑戰(zhàn)是在實(shí)際使用中,由系統(tǒng)產(chǎn)生的巡邏方案經(jīng)常會(huì)被干擾打斷.這些干擾來自于,警察在巡邏過程中經(jīng)常被迷路的旅客要求幫助他找到要去的地方,有些時(shí)候,警察還會(huì)在巡邏過程中遇到其他一些突發(fā)事件需要處理.這要求系統(tǒng)能夠在遇到這種干擾之后動(dòng)態(tài)地產(chǎn)生新的巡邏方案.

另外一個(gè)挑戰(zhàn)來自于,在地鐵站等場(chǎng)所經(jīng)常發(fā)生偷盜,非法交易等犯罪事件.與策略式的恐怖襲擊不同,犯罪通常是機(jī)會(huì)性的,犯罪分子會(huì)在交通系統(tǒng)中隨機(jī)移動(dòng),發(fā)現(xiàn)合適的作案時(shí)機(jī)實(shí)施犯罪.所以如何有效地抑制這種犯罪是一個(gè)很有挑戰(zhàn)的任務(wù).這是一個(gè)數(shù)據(jù)密集的領(lǐng)域,可以采用數(shù)據(jù)挖掘工具分析以前犯罪案件的數(shù)據(jù),得出犯罪案件經(jīng)常發(fā)生的地點(diǎn)、犯罪行為的變化趨勢(shì)以及可能發(fā)生的犯罪類型.希望通過發(fā)掘犯罪活動(dòng)的時(shí)空模式,最優(yōu)地安排有限的安全資源.同時(shí),這會(huì)使得地鐵的巡邏成為一個(gè)多個(gè)目標(biāo)的優(yōu)化問題,這也是一個(gè)新的研究挑戰(zhàn).

2.5 GUARDS-全國范圍航空保護(hù)系統(tǒng)

美國運(yùn)輸安全管理局(US Transportation Security Administration(TSA))負(fù)責(zé)保護(hù)美國400多個(gè)機(jī)場(chǎng)的安全.這些機(jī)場(chǎng)每天需要服務(wù)28000架民航客機(jī)和總共大約87000架飛機(jī).為了保護(hù)如此龐大的交通網(wǎng)絡(luò),TSA雇傭了接近48000名交通安全人員.這些安全人員需要執(zhí)行各種各樣的安全措施來保護(hù)每個(gè)機(jī)場(chǎng)的安全.除了我們都知道的一些常見的安全措施,如行人安全檢查,TSA還需要用這些有限的人員來執(zhí)行其他上百種不同的安全保護(hù)措施來保護(hù)機(jī)場(chǎng)安全,這使得這個(gè)問題成為非常復(fù)雜的資源分配問題.另外,TSA不能產(chǎn)生一種最優(yōu)的保護(hù)策略直接應(yīng)用在所有的機(jī)場(chǎng)上,因?yàn)槊總€(gè)機(jī)場(chǎng)是不同的,需要有自己特定的保護(hù)策略,而同時(shí)TSA還需要在各個(gè)機(jī)場(chǎng)之間設(shè)定一個(gè)通用的標(biāo)準(zhǔn)來協(xié)調(diào)各機(jī)場(chǎng)之間的保護(hù)策略.

為了幫助TSA調(diào)度資源來更好地保護(hù)機(jī)場(chǎng),TEAMCORE團(tuán)隊(duì)開發(fā)了一個(gè)新的全國范圍航空保護(hù)的應(yīng)用系統(tǒng)GUARDS(Game-theoretic Unpredictable and Randomly Deployed Security).考慮到之前的應(yīng)用都是只用在一個(gè)位置,GUARDS系統(tǒng)主要面臨3個(gè)新的挑戰(zhàn):1)這個(gè)系統(tǒng)需要考慮到上百種不同的安全保護(hù)措施;2)需要考慮到多種潛在的威脅,這使得攻擊者的類型數(shù)大量增加;3)因?yàn)橛薪咏?00個(gè)終端用戶,所以不可能為每個(gè)機(jī)場(chǎng)設(shè)計(jì)一個(gè)系統(tǒng),需要上百個(gè)終端用戶設(shè)計(jì)用戶友好的系統(tǒng),可以讓用戶能夠很容易地輸入自己特有的信息,從而產(chǎn)生出適合各自機(jī)場(chǎng)特有的安全保護(hù)策略.GUARDS系統(tǒng)目前正在一個(gè)機(jī)密的機(jī)場(chǎng)接受評(píng)估和測(cè)試[24?25].

2.6 新興的應(yīng)用方向

除了上面提到的這些已經(jīng)成功應(yīng)用的系統(tǒng)之外,最近幾年還涌現(xiàn)出了一些新的應(yīng)用方向.

2.6.1 網(wǎng)絡(luò)領(lǐng)域的新興應(yīng)用方向

一個(gè)主要的領(lǐng)域是保護(hù)大規(guī)模的城市網(wǎng)絡(luò),如交通網(wǎng)絡(luò)、計(jì)算機(jī)網(wǎng)絡(luò)、電力網(wǎng)絡(luò)[26]和其他一些可以用網(wǎng)絡(luò)來建模的領(lǐng)域.比如,在2008年孟買恐怖襲擊之后,孟買警方開始在城市的道路上設(shè)置一些車輛檢查站.Tsai等人[27]將這一問題建模成城市道路網(wǎng)絡(luò)上孟買警方和攻擊者之間的安全博弈問題.在這個(gè)城市安全博弈中,保護(hù)者的純策略是將保護(hù)資源部署在網(wǎng)絡(luò)的一些邊上,比如,選擇城市網(wǎng)絡(luò)中的一些道路來布置車輛檢查點(diǎn).而攻擊者的純策略是選擇網(wǎng)絡(luò)上一條從源點(diǎn)到目標(biāo)點(diǎn)之間的路徑,比如從港口登陸點(diǎn)到城市中的一個(gè)重要建筑.保護(hù)者的策略集空間隨著可用的資源數(shù)量指數(shù)級(jí)增長,而攻擊者的策略集空間隨著網(wǎng)絡(luò)的規(guī)模指數(shù)級(jí)增長.為了解決這種大規(guī)模的問題,需要設(shè)計(jì)新的算法來為孟買城市網(wǎng)絡(luò)這種250多個(gè)點(diǎn)和600多條邊組成的城市道路網(wǎng)絡(luò)來生成隨機(jī)化的資源調(diào)度方案.

Stackelberg安全博弈模型同樣可以被應(yīng)用在一些參與者表現(xiàn)出“傳染”行為的對(duì)抗性領(lǐng)域.例如,營銷人員研究了以口相傳的廣告/病毒市場(chǎng),試圖理解為什么有些產(chǎn)品像病毒一樣傳播,有些卻不被注意[28].鎮(zhèn)壓叛亂是在武裝沖突中爭取當(dāng)?shù)仡I(lǐng)導(dǎo)者支持的斗爭,包括提供安保和給予醫(yī)藥支持等行為.電力網(wǎng)絡(luò)中保護(hù)者需要為一些電站設(shè)置冗余來防止由于恐怖襲擊或者天災(zāi)導(dǎo)致的級(jí)聯(lián)故障[26].就像以口相傳的廣告或者維和行為一樣,這些行為通過鄰里間傳播會(huì)產(chǎn)生巨大的社會(huì)影響.現(xiàn)實(shí)中可能存在多個(gè)參與方試圖通過某些策略影響同一個(gè)社會(huì)網(wǎng)絡(luò).例如一個(gè)參與者試圖傳播影響,另一個(gè)參與者通過傳播自己的影響來阻止第一個(gè)參與者影響的擴(kuò)張.這個(gè)“阻塞”問題描述了政府或維和者面臨的情形:通過每天/每周/每月為當(dāng)?shù)氐念I(lǐng)導(dǎo)者提供支持來阻止恐怖分子的激進(jìn)主義和武裝沖突的擴(kuò)張.安全博弈論可以分析這種大規(guī)模的網(wǎng)絡(luò)對(duì)抗中的資源分配策略.

安全博弈模型的方法同樣可以用于網(wǎng)絡(luò)安全的資源配置,比如包選擇或在大規(guī)模網(wǎng)絡(luò)中檢測(cè)可能的危險(xiǎn).隨著網(wǎng)絡(luò)攻擊的復(fù)雜程度以及預(yù)防網(wǎng)絡(luò)攻擊成本的持續(xù)上升,計(jì)算機(jī)系統(tǒng)和企業(yè)的計(jì)算機(jī)網(wǎng)絡(luò)面臨的壓力也逐年上升.許多新型檢測(cè)系統(tǒng)和監(jiān)管系統(tǒng)正在研發(fā)中,例如深度檢測(cè)包的方法或者周期性選擇網(wǎng)絡(luò)包的一個(gè)子集進(jìn)行探測(cè)分析方法等.攻擊/檢測(cè)問題可以被建模為一個(gè)兩方參與的博弈:攻擊者(闖入者)和防守者(檢測(cè)系統(tǒng)).攻擊者希望通過掃描網(wǎng)絡(luò)獲得網(wǎng)絡(luò)中重要機(jī)器的控制權(quán)(或者破壞這臺(tái)重要的機(jī)器),侵入到更加脆弱的系統(tǒng),獲得計(jì)算機(jī)網(wǎng)絡(luò)更多設(shè)備的操作權(quán).攻擊者的行為可以看作是通過一臺(tái)受控的機(jī)器(稱作源)向一個(gè)或多個(gè)脆弱的機(jī)器(稱作目標(biāo))發(fā)送惡意包.防守者的目標(biāo)是通過選擇一些包進(jìn)行檢測(cè),識(shí)別出攻擊者,從而阻止攻擊.然而,由于包檢測(cè)會(huì)造成網(wǎng)絡(luò)延遲,防守者需要決定何時(shí)何地去檢測(cè)網(wǎng)絡(luò)使得對(duì)惡意包的檢測(cè)成功率最高.計(jì)算設(shè)計(jì)的挑戰(zhàn)主要包括如何有效地計(jì)算出最優(yōu)的防御策略.

2.6.2 保護(hù)自然資源領(lǐng)域的新興應(yīng)用方向

另外一類新的應(yīng)用方向是防止與環(huán)境自然資源相關(guān)的犯罪行為.第一個(gè)這類應(yīng)用是保護(hù)森林資源免受亂砍亂伐[29].在這種場(chǎng)景中,巡邏者需要保護(hù)一大片連續(xù)的地域以防止不法分子的砍伐.可是往往由于巡邏警察的數(shù)量不足,導(dǎo)致需要精心巡邏策略:如何進(jìn)行巡邏分布、巡邏的時(shí)間和地點(diǎn)、如何使違法砍伐最少、如何對(duì)森林的保護(hù)最大化.這個(gè)問題可以建模成一個(gè)Stackelberg博弈問題,著眼于求解巡邏密度的分配.

另外一個(gè)這類應(yīng)用是保護(hù)瀕危物種[30].瀕危物種的偷獵使得很多物種已經(jīng)達(dá)到不可持續(xù)發(fā)展的數(shù)量.比如,全球老虎的數(shù)量已經(jīng)比1900年減少了95%,導(dǎo)致9種虎群中的3種已經(jīng)完全滅絕.這些偷獵行為的主要?jiǎng)訖C(jī)是老虎、大象和犀牛等物種有很多的經(jīng)濟(jì)利益.為了防止這種行為,各個(gè)國家都建立了野生動(dòng)物保護(hù)機(jī)構(gòu),但是相對(duì)于需要巡邏的區(qū)域來說,保護(hù)力量資源是遠(yuǎn)遠(yuǎn)不夠的.

另外一個(gè)這類應(yīng)用是保護(hù)海洋的漁類資源[31].海洋魚類是很多國家的重要食物來源.據(jù)世界自然基金會(huì)報(bào)告,過度捕撈導(dǎo)致英國、加拿大和其他近大西洋國家的鱈魚的數(shù)量已經(jīng)瀕臨危險(xiǎn).過去30年,全球鱈魚的數(shù)量已經(jīng)下降了70%,如果按照這個(gè)趨勢(shì)下去,15年之后鱈魚將在地球上滅絕.非法的,沒有申報(bào)的和不合乎條例的(illegal,unreported and unregulated fi shing(IUU))捕魚行為是海洋漁業(yè)資源可持續(xù)性的重要威脅.據(jù)美國國家海洋和大氣管理局(National Oceanic and Atmospheric Administration(NOAA))估計(jì),IUU捕魚行為每年可以制造1100～2600噸海產(chǎn)食品,在一些魚類的捕撈中,IUU捕撈能夠占到40%的份額.這背后的主要驅(qū)動(dòng)力是重大的經(jīng)濟(jì)利益和低風(fēng)險(xiǎn).任何國家都不可能保持全天候的保護(hù)海域來防止這種捕撈行為,所以如何有效地分配巡邏資源對(duì)美國海岸警衛(wèi)隊(duì)(US Coast Guard)等類似的機(jī)構(gòu)來說是個(gè)非常有挑戰(zhàn)性的問題.這個(gè)問題的主要挑戰(zhàn)在于,警方無法確切地知道魚群的位置,所以需要通過結(jié)合歷史數(shù)據(jù)和以往抓住非法捕魚者的記錄,結(jié)合機(jī)器學(xué)習(xí)的技術(shù)和博弈論的框架來設(shè)計(jì)新的算法.

除了以上兩個(gè)新興的應(yīng)用方向之外,最近針對(duì)大規(guī)模集體事件的恐怖襲擊也日益嚴(yán)重,比如2013年的波士頓馬拉松爆炸案.Yin等人[72]研究了馬拉松比賽這類集體事件中的安保資源分配問題.這一問題的主要挑戰(zhàn)在于,隨著比賽的進(jìn)行,賽段上不同位置的人數(shù)在發(fā)生變化,比如在比賽開始時(shí),大部分人是聚集在起點(diǎn)處的,而在比賽接近結(jié)束時(shí),更多的人位于終點(diǎn)處.所以在不同時(shí)間點(diǎn),賽段上的不同地點(diǎn)的收益是在不斷變化的,所以需要設(shè)計(jì)一種隨著時(shí)間連續(xù)變化的保護(hù)策略。

3 算法可擴(kuò)展性研究進(jìn)展

安全博弈論的應(yīng)用給研究提出了非常多的研究挑戰(zhàn),其中,最主要的挑戰(zhàn)來自于算法的可拓展性方面.DOBSS和ERASER等基本的博弈求解算法可以很好地解決機(jī)場(chǎng)車輛檢查點(diǎn)的布置問題,但是隨著安全部門安全策略和安全資源的數(shù)量和恐怖分子攻擊行為種類的增加,防御者和攻擊者的策略空間都可能會(huì)呈指數(shù)級(jí)增長,潛在的攻擊者的類型也會(huì)變得很多.這種大規(guī)模的問題場(chǎng)景甚至無法很好地在計(jì)算機(jī)中表示出來,更不要說利用現(xiàn)有的技術(shù)來進(jìn)行求解,所以如何設(shè)計(jì)更高效的博弈求解算法來應(yīng)對(duì)問題規(guī)模的增加成為一個(gè)主要的研究挑戰(zhàn).

在上文提到的各類應(yīng)用中,這類擴(kuò)展性問題已經(jīng)被提到.在空中警察調(diào)度的領(lǐng)域中,采用的調(diào)度方案需要將數(shù)量有限的空中警察分配給成千上萬的商業(yè)航班,并且滿足每一名空中警察需要飛回其基地的同時(shí)滿足起飛、降落、休息等很多時(shí)間上的約束.這使得防御者的策略空間非常龐大,不可能完全枚舉出來;在城市反恐的領(lǐng)域中,問題更加困難,保護(hù)者的策略集空間隨著可用的資源數(shù)量指數(shù)級(jí)增長,而攻擊者的策略集空間隨著網(wǎng)絡(luò)的規(guī)模指數(shù)級(jí)增長;而在全國范圍航空保護(hù)的領(lǐng)域中,保護(hù)者要面臨上百種潛在的攻擊威脅,使得攻擊者的類型數(shù)量增加;在PRPTECT系統(tǒng)保護(hù)移動(dòng)的渡輪和TRUSTS系統(tǒng)保護(hù)每輛地鐵的領(lǐng)域中,被保護(hù)的目標(biāo)(擺渡船)是在不斷移動(dòng)的,而攻擊者可以選擇任何時(shí)刻進(jìn)行攻擊.這種移動(dòng)目標(biāo)的保護(hù)使得博弈模型變成連續(xù)策略集空間,大大增加了問題的復(fù)雜性和求解難度.

本節(jié),我們介紹安全博弈論方向在解決大規(guī)模的實(shí)際安全領(lǐng)域問題中在模型和算法方面取得的進(jìn)展.具體的,我們主要介紹以下4個(gè)工作:1)ASPEN,它是Jain等人[17]為了解決空中警察調(diào)度領(lǐng)域中保護(hù)者策略集空間增大問題所提出的一個(gè)master-salve算法;2)RUGGED,是Jain等人[32]為了解決城市反恐領(lǐng)域中,保護(hù)者和攻擊者的策略集都是指數(shù)級(jí)的問題而提出的一個(gè)double-oracle算法;3)HBGS算法,是Jain等人[33]為了解決攻擊者類型增大而提出的一個(gè)層次化算法;4)Transition Graph,是Yin等人[8,23]為了解決保護(hù)移動(dòng)目標(biāo)的領(lǐng)域中,策略集同時(shí)受到時(shí)間和空間限制而提出的一種新的緊湊型的策略表示方法.

3.1 ASPEN算法

這一節(jié),我們主要介紹ASPEN算法,它主要是為了解決2.2節(jié)中FAMS在空中警察調(diào)度領(lǐng)域遇到的保護(hù)者策略集極其大的問題.它主要利用了在很多實(shí)際博弈論問題中一個(gè)很重要的特點(diǎn),也就是雖然問題的策略集非常大,但是最優(yōu)混合策略的支撐集很小,這就是說,在最后得到的最優(yōu)混合策略中,只有很少部分的純策略概率不為0,其他非常多的純策略的概率為0.ASPEN利用了這一特點(diǎn)使用策略生成(strategy generation)的方法,每次為保護(hù)者產(chǎn)生一個(gè)純策略,加入到優(yōu)化問題中,直到迭代收斂.

在這個(gè)安全博弈問題中,攻擊者可以選擇任意一架飛機(jī)進(jìn)行攻擊,而每一個(gè)空中警察可以被分配到一個(gè)可行的排班表上.每個(gè)排班表是由一組可以被放在一起保護(hù)的可行目標(biāo)組成,對(duì)于FAMS來說,一個(gè)排班表就是滿足起飛、降落、休息等很多時(shí)間上的約束的一次巡回飛行.一個(gè)聯(lián)合排班表需要把每個(gè)空警都安排在一個(gè)這樣的巡回飛行上,所以這樣的聯(lián)合排班表是有指數(shù)量級(jí)的.而保護(hù)者的一個(gè)純策略就是一個(gè)這樣的聯(lián)合排班表.因?yàn)閷?duì)于如此龐大的問題規(guī)模,無法做到遍歷保護(hù)者的純策略集,所以ASPEN算法對(duì)保護(hù)者使用了策略生成的方法.它將這個(gè)問題分解成了一個(gè)主(Master)問題和一個(gè)從(Slave)問題,然后反復(fù)對(duì)兩個(gè)問題進(jìn)行迭代求解,過程如算法1所示.

首先給保護(hù)者隨機(jī)生成非常少數(shù)量的純策略,然后求解由這些純策略和攻擊者的策略組成的主優(yōu)化問題,得到在這個(gè)主問題下,保護(hù)者的最優(yōu)策略,然后求解從問題,給保護(hù)者生成一條新的能夠在目前主問題的情況下最大限度增加保護(hù)者期望收益的純策略,將其加入到主問題,然后再求解新的主問題,如此反復(fù)進(jìn)行,直到無法為保護(hù)者找到新的純策略時(shí)結(jié)束.

我們可以用圖5的圖形化方式來更加形象地表示這個(gè)迭代過程.算法步驟2中的主問題對(duì)當(dāng)前已經(jīng)生成的純策略集進(jìn)行操作,圖中我們用矩陣P來表示這個(gè)策略集.矩陣P的每一列代表一條純策略,如果目標(biāo)可以被純策略保護(hù),則矩陣?yán)锩娴脑貫?,反之為0.算法步驟5中從問題的目標(biāo)產(chǎn)生一個(gè)最好的聯(lián)合排班表加入到矩陣P中.聯(lián)合排班表的好壞用它能夠?yàn)楸Ｗo(hù)者增加多少期望收益來衡量.一個(gè)最簡單的方式是枚舉所有可能的純策略來看哪一條是最好的,ASPEN算法中將其轉(zhuǎn)化為一個(gè)最小花費(fèi)網(wǎng)絡(luò)流問題從而可以高效地找到最優(yōu)的策略.ASPEN算法總是可以收斂到最優(yōu)的混合策略.

這種主從問題的思想在解決一個(gè)策略參與方的策略集非常大的問題中非常有效,Gan等人最最近發(fā)表的一篇論文[73]中利用類似的方法解決了保護(hù)資源具有外部性的情形下的安全博弈的求解問題.

3.2 RUGGED算法

在2.6.1節(jié)中給出的網(wǎng)絡(luò)領(lǐng)域的應(yīng)用方向中,保護(hù)者和攻擊者的純策略集都是指數(shù)集的.以大城市道路網(wǎng)絡(luò)中隨機(jī)車輛檢查點(diǎn)的設(shè)置的問題為例,如果是一個(gè)由20個(gè)節(jié)點(diǎn)和190條邊組成的完全圖,保護(hù)者的資源數(shù)量為5,則保護(hù)者的純策略數(shù)量約為200萬個(gè),而攻擊者的不含回路的可能攻擊路徑數(shù)量就有大約6618條.真實(shí)的網(wǎng)絡(luò)規(guī)模更大,比如在孟買的城市網(wǎng)絡(luò)中,就有250多個(gè)點(diǎn)和600多條邊,而安全部門通?？梢栽O(shè)置數(shù)十個(gè)檢查點(diǎn).本節(jié),介紹針對(duì)這一問題場(chǎng)景的RUGGEN算法[32].

圖5 ASPEN算法中的策略生成過程示意圖

RUGGED將這一問題建模成一個(gè)零和博弈問題.每個(gè)潛在的攻擊目標(biāo)都有一個(gè)收益值,如果保護(hù)者選擇設(shè)置檢查點(diǎn)的邊和攻擊者選擇的攻擊路徑有交集,則攻擊失敗,攻擊者的收益為0;如果雙方?jīng)]有交集,則攻擊成功,攻擊者得到攻擊目標(biāo)對(duì)應(yīng)的收益值.而保護(hù)者和攻擊者的收益之和為零.在這種零和博弈中,強(qiáng)Stackelberg均衡和Minimax均衡是等價(jià)的.每一方都沒法通過先動(dòng)得到任何優(yōu)勢(shì).求解Minimax均衡的問題可以轉(zhuǎn)化成線性規(guī)劃問題,在多項(xiàng)式時(shí)間內(nèi)求解.但是,因?yàn)樵谶@個(gè)問題中,個(gè)體的策略集是指數(shù)集的,使得標(biāo)準(zhǔn)的求解算法沒有辦法直接應(yīng)用過來.RUGGED利用了double-oracle的思想,對(duì)兩個(gè)參與者都使用類似于ASPEN中的策略生成的思想,從而避免枚舉兩個(gè)指數(shù)級(jí)的策略集空間.

RUGGED的算法流程如上所示.X是到目前為止得到的保護(hù)者的策略集,而A是攻擊者目前位置的策略集.CoreLP(X,A)求解由X和A組成的零和博弈得到雙方的最優(yōu)混合策略x和a.保護(hù)者模塊(Defender Oracle(DO))產(chǎn)生保護(hù)者對(duì)攻擊者目前的混合策略a的最佳響應(yīng)純策略(這個(gè)最佳響應(yīng)是從保護(hù)者所有的策略集中搜索的,而不局限于X中的策略).相似的,攻擊者模塊(Attacker Oracle(AO))產(chǎn)生攻擊者的最佳響應(yīng)攻擊路徑.這樣,該算法開始給博弈雙方都隨機(jī)產(chǎn)生很少數(shù)量的純策略,然后每次迭代給每個(gè)參與者最多增加一條最佳響應(yīng)策略.當(dāng)雙方都沒法找到最佳響應(yīng)策略時(shí),算法結(jié)束.同樣可以給出一個(gè)圖形化的示意圖來表示這個(gè)迭代過程,如圖6所示.McMahan等人[34]等人證明了這個(gè)算法對(duì)零和博弈的正確性.

RUGGED算法可以在10個(gè)小時(shí)左右的時(shí)間內(nèi)求解出由250個(gè)點(diǎn)和4個(gè)安保資源構(gòu)成的問題.這個(gè)算法還是沒法達(dá)到實(shí)際的問題規(guī)模,主要的計(jì)算復(fù)雜性在于每個(gè)oracle模塊求解最佳響應(yīng)的問題都是NP-hard問題.RUGGED算法中將這兩個(gè)問題都轉(zhuǎn)換成了混合整數(shù)線性規(guī)劃問題(MILP),但是求解的復(fù)雜性依然是很大的.在最近的一個(gè)工作中,Jain等人[35]在RUGGED算法的基礎(chǔ)上進(jìn)行了優(yōu)化,提出了一個(gè)新的算法SNARES.這個(gè)算法的改進(jìn)主要體現(xiàn)在兩方面:1)初始時(shí)不是隨機(jī)產(chǎn)生策略,而是利用一些貪婪算法產(chǎn)生一些更優(yōu)的純策略;2)在每個(gè)oracle模塊,不需要每次都求解最佳響應(yīng)問題,而是先用貪婪算法求解較佳問題嘗試找到一個(gè)比現(xiàn)在X和A中的策略更好的純策略,如果能找到就直接把這個(gè)策略返回,如果找不到再求解NP-hard的最佳響應(yīng)問題.這個(gè)算法大大提高了運(yùn)算速度,可以在合理的時(shí)間內(nèi)求解出為孟買的城市規(guī)模布置10～15個(gè)車輛檢查點(diǎn)的問題.Double-oracle的算法思想也被用到了其他網(wǎng)絡(luò)領(lǐng)域的安全問題中.如網(wǎng)絡(luò)傳播,電力網(wǎng)絡(luò)級(jí)聯(lián)故障,計(jì)算機(jī)網(wǎng)絡(luò).

圖6 RUGGED算法中的策略生成過程示意圖

3.3 HBGS算法

在安全博弈中,另外一個(gè)影響算法可拓展性的方面是攻擊者類型的數(shù)量.特別是在GUARDS系統(tǒng)面臨的安全場(chǎng)景中,可能面臨的安全威脅的種類非常大.而貝葉斯Stackelberg博弈的求解是一個(gè)NP-hard的問題,沒法找到O(types)級(jí)的多項(xiàng)式時(shí)間的求解算法.本節(jié)介紹Jain等人[33]提出的求解大規(guī)模的貝葉斯Stackelberg博弈的HBGS算法.該算法利用了層級(jí)化技術(shù)先將求解大的貝葉斯博弈的問題分解成求解層次化組織的更小的貝葉斯博弈,通過求解更小規(guī)模的博弈,來為求解大規(guī)模的博弈提供一些剪枝規(guī)則,使得大規(guī)模博弈的求解速度更快,從而更高效地解決問題.

求解貝葉斯Stackelberg博弈的最基本的算法是我們?cè)?.5.1中介紹的Multi LPs算法.這個(gè)算法的求解過程可以表示成圖7(a)[33]的形式.它是一個(gè)由兩種攻擊者類型和兩個(gè)純策略組成的貝葉斯Stackelberg博弈例子,所有可能的攻擊者策略組合方式被表示成了樹的形式.這個(gè)樹的所有葉子節(jié)點(diǎn)是所有可能的攻擊者策略組合,比如葉子[1,1]表示攻擊者類型γ1和γ2都選擇純策略a1.在基本的MultiLPs算法中,每個(gè)葉子節(jié)點(diǎn)是一個(gè)線性規(guī)劃問題.為了計(jì)算最優(yōu)的保護(hù)者混合策略,這個(gè)樹的所有葉子節(jié)點(diǎn)都要被評(píng)估到,使得我們需要求解指數(shù)級(jí)數(shù)量的線性規(guī)劃,導(dǎo)致了這個(gè)問題的NP-hard性.而實(shí)際上我們可以利用分支定界法(branchand-bound)的思想對(duì)這個(gè)樹進(jìn)行搜索,而如果我們能夠?yàn)榍蠼膺@個(gè)大規(guī)模問題的分支定界過程提供一些有效的上下界和剪枝規(guī)則,從而減少線性規(guī)劃的求解數(shù)量,就可以大大提高運(yùn)算速度,甚至能夠使得MultiLPs的運(yùn)算速度比DOBSS算法還要快.

HBGS算法正是基于這點(diǎn)考慮,在求解這個(gè)大規(guī)模問題之前,先進(jìn)行預(yù)處理.如圖7(b)[33]所示,先把大規(guī)模的貝葉斯Stackelberg博弈分解成層次化組織的多個(gè)更小規(guī)模的博弈.每個(gè)更小的博弈(圖7(b)中的子節(jié)點(diǎn))只考慮更少的攻擊者類型,這樣子節(jié)點(diǎn)的計(jì)算時(shí)間比父節(jié)點(diǎn)的博弈指數(shù)級(jí)減小.比如,在圖7(b)的例子中,父節(jié)點(diǎn)的貝葉斯Stackelberg博弈有4種攻擊者類型,層次化的表示方式將它分解成4個(gè)只有一種攻擊者類型的博弈作為子節(jié)點(diǎn).這樣,子節(jié)點(diǎn)博弈的求解結(jié)果可以用來為上層的父節(jié)點(diǎn)提供剪枝規(guī)則、限制上下界和刪除到一些顯然不可行的策略組合,從而使得父節(jié)點(diǎn)的大規(guī)模的問題求解速度更快.這種層次化的技術(shù)可以有效地提高分支定界法的效率,可以和其他算法如APSEN來結(jié)合使用,從而提高大規(guī)模問題的求解速度.

3.4 緊湊的策略表示方式

在利用緊湊的策略表示方式的思想方面,一類非常重要的進(jìn)展是當(dāng)被保護(hù)目標(biāo)是移動(dòng)個(gè)體時(shí),策略的緊湊表示方式.這種情況在地鐵系統(tǒng)中,防止乘客逃票的問題和內(nèi)河河道中客輪的保護(hù)問題中都會(huì)出現(xiàn).以地鐵系統(tǒng)的情況為例,警方可以通過在地鐵站或者在地鐵車上進(jìn)行抽查來防止乘客的逃票行為.在這個(gè)問題中,需要生成的巡邏時(shí)間表是由在地鐵站進(jìn)行查票和在某輛地鐵上進(jìn)行查票行動(dòng)組成的一個(gè)行動(dòng)序列.每個(gè)行動(dòng)需要指明一個(gè)巡邏隊(duì)在什么時(shí)間需要在什么地點(diǎn)進(jìn)行查票動(dòng)作.這使得可能的巡邏時(shí)間表數(shù)量是指數(shù)級(jí)的,而且受到地鐵在不同站點(diǎn)間移動(dòng)的空間和時(shí)間約束.

考慮由一條地鐵線路組成的交通系統(tǒng),有多輛車同時(shí)往返于這條線路上.這樣一個(gè)系統(tǒng)按照一個(gè)固定的時(shí)間安排來運(yùn)行,這個(gè)時(shí)間安排規(guī)定了在一天中,哪輛車在什么時(shí)間到達(dá)哪個(gè)站點(diǎn).所以,時(shí)間可以建模成連續(xù)的,只需要關(guān)注那些可能發(fā)生車輛到達(dá)/離開事件的時(shí)間點(diǎn).我們可以利用一個(gè)有向的轉(zhuǎn)移圖G=hV,Ei來表示地鐵線路一天的時(shí)間表,其中,一個(gè)節(jié)點(diǎn)由地鐵站s和時(shí)間點(diǎn)t的對(duì)組成.圖中的一條邊表示一個(gè)可能的行動(dòng).具體地說,節(jié)點(diǎn)hs,ti到節(jié)點(diǎn)hs0,t0i之間只有在滿足以下一個(gè)條件時(shí)才會(huì)有一條邊相連:1)S.是站點(diǎn)序列中地鐵站s的前一個(gè)或者后一個(gè)地鐵站,hs,ti和hs0,t0i是在某一輛地鐵的時(shí)間表上連續(xù)的兩個(gè)停車點(diǎn);2)s.=s,t

假設(shè)一共有λ個(gè)巡邏隊(duì),每個(gè)巡邏隊(duì)都可以被分配到一個(gè)不長于κ小時(shí)(比如κ=7)的巡邏任務(wù)上.每個(gè)巡邏隊(duì)都可以交互的進(jìn)行兩種巡邏行動(dòng):隨車檢查(巡邏隊(duì)在地鐵上對(duì)車上的乘客進(jìn)行檢查)和站點(diǎn)檢查(巡邏隊(duì)在站點(diǎn)上對(duì)進(jìn)入車站的旅客進(jìn)行檢查).一個(gè)巡邏純策略可以表示成圖G上的一個(gè)長度不大于κ的路徑,其中,一條邊e表示巡邏隊(duì)從邊的起點(diǎn)時(shí)刻點(diǎn)到邊的終點(diǎn)時(shí)刻點(diǎn)在一輛車上或者一個(gè)站點(diǎn)上進(jìn)行檢查.在圖8的例子中,如果κ=2而且λ=1,那么,圖中所有的長度為2的路徑都是有效的純策略,所以在這個(gè)博弈中,即使只有一個(gè)巡邏隊(duì),領(lǐng)導(dǎo)者的純策略數(shù)量也是指數(shù)級(jí)的.可以利用文獻(xiàn)[36]中類似的思想用轉(zhuǎn)移圖上每條邊的邊界覆蓋概率xe來緊湊地表示領(lǐng)導(dǎo)者的混合策略,也就是用每條邊上可能發(fā)生的檢查的期望數(shù)量.我們用表示V+?V轉(zhuǎn)移圖中所有可能的起始點(diǎn)的集合,用V??V表示所有可能的終止點(diǎn)的集合.為了表示的方便,可以給轉(zhuǎn)移圖增加一個(gè)指向所有V+中點(diǎn)的虛擬的起點(diǎn)v+和從所有V?中的點(diǎn)指向的一個(gè)虛擬的終點(diǎn)v?.由虛擬起點(diǎn)v+指出和指向虛擬終點(diǎn)v?的所有邊上的巡邏時(shí)間設(shè)置成0.這樣可以對(duì)轉(zhuǎn)移圖中的流量得到以下約束:

圖7 層次化求解貝葉斯Stackelberg博弈

圖8 轉(zhuǎn)移圖示例

第一個(gè)約束限制流入和流出轉(zhuǎn)移圖的總量為巡邏隊(duì)的總數(shù)λ,第二個(gè)約束限制了轉(zhuǎn)移圖上每個(gè)節(jié)點(diǎn)的流入量等于流出量,第三個(gè)約束限制了總共的巡邏時(shí)間為λ·κ,每條邊上的流量的理論上限為一個(gè)不大于λ的值α,也就是說每條邊上同時(shí)巡邏的警察的數(shù)量不可能超過λ.

但是在地鐵巡邏的問題中,僅僅定義每條邊上的邊界覆蓋概率xe并滿足上面幾個(gè)約束,可能會(huì)解出不可行或者沒法實(shí)際執(zhí)行的解.首先,它可能會(huì)導(dǎo)致解出的混合策略不滿足不大于κ的約束,因?yàn)榈?個(gè)約束只能約束所有巡邏隊(duì)的巡邏時(shí)間總和.比如圖9中給出的一個(gè)反例.

圖中邊v1→v2和邊v2→v3為兩個(gè)可行的巡邏動(dòng)作,每個(gè)動(dòng)作執(zhí)行時(shí)間為1h.巡邏必須從v1或者v3開始,但是可以在v1,v2和v3中的任意一個(gè)點(diǎn)結(jié)束,v+和v?是如上文所定義的虛擬起點(diǎn)和終點(diǎn).假設(shè)κ=1和λ=1.很容易可以檢驗(yàn)出來,這個(gè)例子滿足上面的3個(gè)約束.但是通過圖中給出的邊界覆蓋概率,我們能構(gòu)造出的唯一的混合策略是以50% 的可能性采取v+→v3→v?策略,另外50%的可能采取v+→v1→v2→v3→v?策略.這個(gè)混合策略顯然是不可行的,因?yàn)榈诙€(gè)策略的巡邏時(shí)間大于1h.這個(gè)問題出現(xiàn)的原因是在目前這種邊界概率的定義下,只能對(duì)平均的巡邏長度做約束,這樣就可能出現(xiàn)大于巡邏長度和小于巡邏長度的策略同時(shí)存在,而平均值滿足約束的情況.

其次,由滿足3個(gè)約束的邊界覆蓋概率構(gòu)造出來的混合策略可能會(huì)出現(xiàn)在不同車輛之間和隨車檢查與站點(diǎn)檢查之間頻繁交換很多次的巡邏策略,這樣的巡邏路線在實(shí)際中是不宜執(zhí)行的而且很容易出現(xiàn)錯(cuò)誤.巡邏策略中的換乘次數(shù)越多,巡警在執(zhí)行的過程中就需要記住越多的指令,這也會(huì)增加巡警因?yàn)殄e(cuò)過換乘導(dǎo)致策略無法執(zhí)行的可能性.比如,在圖8的例子中,hA,6PMi→hB,7PMi→hA,8PMi和hC,6PMi→hB,7PMi→hC,8PMi兩個(gè)巡邏策略每個(gè)需要一次換乘,而hA,6PMi→hB,7PMi→hC,8PMi和hC,6PMi→hB,7PMi→hA,8PMi兩個(gè)巡邏策略都不需要換乘.但是兩個(gè)策略對(duì)對(duì)應(yīng)的邊界覆蓋概率是一樣的,這時(shí)我們更希望得到第二對(duì)策略對(duì),因?yàn)樗菀讓?shí)施.

為了解決上述提到的兩個(gè)問題,Yin Zhenyu等人[23]在點(diǎn)上加入了邊的歷史信息,構(gòu)造了一種基于歷史副本的轉(zhuǎn)移圖(HDT graph)來避免出現(xiàn)上面兩種情況.首先為了避免出現(xiàn)第一種情況,HDT圖將圖G分解成多個(gè)子圖副本,每個(gè)子圖副本對(duì)應(yīng)不同的可能起始時(shí)間點(diǎn).對(duì)應(yīng)起始時(shí)間點(diǎn)t?的子圖副本,只保留滿足t?≤t≤t?+κ的節(jié)點(diǎn)v=hs,ti∈V.這樣在每個(gè)子圖中,可以保證路徑的長度不會(huì)大于κ.同時(shí)因?yàn)榭赡艿钠鹗紩r(shí)間點(diǎn)的數(shù)量是有限的,是原來的轉(zhuǎn)移圖G的線性拓展.圖10[33]展示了如何針對(duì)圖8中的例子構(gòu)造HDT圖.在這個(gè)例子中,κ=2并且有兩個(gè)起始時(shí)間點(diǎn)6PM和7PM.所以,HDT圖由原始轉(zhuǎn)移圖的兩個(gè)受限的副本組成.在每個(gè)節(jié)點(diǎn)中,括號(hào)中的時(shí)間的意思是對(duì)應(yīng)的起始時(shí)間點(diǎn).比如,原始圖中的hA,7PMi點(diǎn)在HDT圖中存在兩個(gè)副本hA,7PM,(6PM)i和hA,7PM,(7PM)i.當(dāng)起始點(diǎn)為6PM 時(shí),所有的可行巡邏方案只能在8PM 或者之前結(jié)束,所以在這左面的子圖副本中,我們不需要保留時(shí)間點(diǎn)為9PM的節(jié)點(diǎn).

圖9 邊界概率得到的不可行解的例子

圖10 考慮起始時(shí)間點(diǎn)的子圖副本示例

為了避免生成復(fù)雜的巡邏路徑,Yin等人[23]對(duì)HDT圖進(jìn)行了進(jìn)一步的拓展.主要思想是讓每個(gè)節(jié)點(diǎn)將在這一節(jié)點(diǎn)之前發(fā)生的上一個(gè)行動(dòng)記錄下來.也就是說,給每個(gè)點(diǎn)創(chuàng)建多個(gè)副本,每個(gè)副本表示從不同的邊指向這個(gè)點(diǎn).如果節(jié)點(diǎn)v是一個(gè)可能的起始點(diǎn),我們?cè)诹硗饨o它創(chuàng)建一個(gè)副本,代表在這個(gè)點(diǎn)之前沒有其他行動(dòng).如果v和v0之間有一條邊,我們?yōu)関點(diǎn)的所有副本和v0點(diǎn)的先驗(yàn)行動(dòng)為(v,v0)的副本之間構(gòu)造連邊.如果一條邊的兩個(gè)頂點(diǎn)保存的先驗(yàn)行動(dòng)的類型不一樣,我們稱這條邊為一個(gè)換乘邊.這樣在新的圖中,一個(gè)巡邏方案的換乘次數(shù)就是它包含的換乘邊的數(shù)量.為了優(yōu)先產(chǎn)生更簡單的巡邏方案,他們給每條換成邊定義了一個(gè)花費(fèi)β>0.這樣通過改變?chǔ)碌闹稻涂梢栽诮獾馁|(zhì)量和換乘次數(shù)之間進(jìn)行折中.圖11[23]展示了如何將圖10左圖陰影框中的子圖加入先驗(yàn)行動(dòng)信息.

圖11 考慮先驗(yàn)行動(dòng)的HDT圖示例

因?yàn)橹挥幸粭l邊指向hA,7PM,(6PM)i,所以我們只為這個(gè)點(diǎn)構(gòu)造一個(gè)副本,代表先驗(yàn)行動(dòng)為停留在A點(diǎn)進(jìn)行站點(diǎn)檢查.有3條邊指向節(jié)點(diǎn)hB,7PM,(6PM)i,所以我們?yōu)檫@個(gè)點(diǎn)構(gòu)造3個(gè)副本,分別表示先驗(yàn)行動(dòng)為乘坐一輛從A到B的車進(jìn)行隨車檢查,在B點(diǎn)進(jìn)行站點(diǎn)檢查和乘坐一輛從C到B的車進(jìn)行隨車檢查.我們同樣需要給每條由hB,7PM,(6PM)i點(diǎn)指出的邊構(gòu)造3個(gè)副本.比如hB,7PM,(6PM)i→hB,7PM,(6PM)i邊的3個(gè)副本,只有“Stay”到“Stay”的邊不是換乘邊.構(gòu)造了這樣的HDT圖后,我們就這個(gè)圖中每個(gè)邊上的邊界覆蓋概率來作為這個(gè)問題更有效的緊湊策略表達(dá)方式.

4 算法魯棒性研究進(jìn)展

除了可拓展性方面的挑戰(zhàn)以外,另外一個(gè)非常重要的挑戰(zhàn)來自于算法的魯棒性方面.傳統(tǒng)的博弈論通常假設(shè)參與者是完全理性的并且具有完美記憶能力的.但在現(xiàn)實(shí)中這些假設(shè)可能并不準(zhǔn)確.

因此,在計(jì)算防御者的資源分配策略時(shí),算法應(yīng)考慮各種不確定性,包括效用誤差、執(zhí)行誤差、觀測(cè)誤差以及能力的不確定性.另外,現(xiàn)實(shí)生活中的攻擊者常分布在基于社會(huì)、文化或有認(rèn)知偏見的聯(lián)盟中,因此如何借助社會(huì)科學(xué)和行為博弈論的思想(例如前景理論、隨機(jī)最優(yōu)選擇)來建立更符合實(shí)際的攻擊者行為模型也成為主要的研究挑戰(zhàn).

圖12 不確定性空間

4.1 收益不確定性

在實(shí)際應(yīng)用中,需要利用領(lǐng)域?qū)＜谊P(guān)于可用的保護(hù)資源、不同保護(hù)目標(biāo)的安全風(fēng)險(xiǎn)和脆弱性以及潛在的恐怖分子的喜好和能力等方面的知識(shí)來建模收益矩陣.保護(hù)者的均衡策略對(duì)收益矩陣非常敏感,但是領(lǐng)域?qū)＜覍?duì)這些信息把握有很大的不確定性,特別是恐怖分子相關(guān)的信息.比如,雖然我們可能知道一些目標(biāo)比另外一些目標(biāo)對(duì)恐怖分子來說更有吸引力,但是我們很難精確地知道恐怖分子在選擇攻擊目標(biāo)時(shí),如何評(píng)估人員傷亡、經(jīng)濟(jì)損失、媒體報(bào)道等因素給他們帶來的收益.這意味著我們可能無法給出在不同的攻擊情境下精確的收益值.

在傳統(tǒng)的安全博弈論工作中,通常利用貝葉斯博弈來對(duì)收益的不確定性進(jìn)行建模.假設(shè)存在有限多種攻擊者的類型,每種攻擊類型有對(duì)應(yīng)的出現(xiàn)概率和對(duì)應(yīng)的精確的收益矩陣.但是,在實(shí)際應(yīng)用中,這種方式有兩方面的不足.一是,這種有限貝葉斯Stackelberg博弈的均衡求解問題是NP-hard的.ARMOR系統(tǒng)中用的DOBSS算法只能求解到10種攻擊者類型和每種攻擊者只有5種攻擊行為的規(guī)模.目前在求解這一問題上最快的算法是3.3節(jié)中提到的HBGS算法,但是即使是這個(gè)算法,在攻擊者的可選攻擊行為只有5個(gè)的情況下,也無法達(dá)到大于50種攻擊類型的規(guī)模.在FAMS這種有上千種可能的攻擊行為的領(lǐng)域中,所有目前已知的算法都無法考慮很多種攻擊者類型.另外,利用有限貝葉斯Stackelberg博弈進(jìn)行建模,我們需要領(lǐng)域?qū)＜姨峁┟糠N攻擊者類型對(duì)應(yīng)的確切收益矩陣和確切的出現(xiàn)概率,這在很多實(shí)際場(chǎng)景中是無法得到的.針對(duì)這一問題,Kiekintveld等人[37]、Yin等人[38]和Nguyen等人[39]在這方面做了一系列研究進(jìn)展.

Kiekintveld等人[37]用連續(xù)的收益分布(比如高斯分布或者平均分布)來表示攻擊者的收益引入了一個(gè)無窮貝葉斯Stackelberg安全博弈.確切地說,這個(gè)模型假設(shè)可能的攻擊者類型是無窮多個(gè)的.假設(shè)其中某種攻擊者類型γ∈Γ被選擇的概率為Pb(γ),當(dāng)目標(biāo)ti被保護(hù)時(shí),攻擊者類型攻擊這一目標(biāo)得到的收益用Uti),目標(biāo)沒有被保護(hù)時(shí),攻擊者的收益用U(ti)來表示.因?yàn)榭赡艿墓粽哳愋蛿?shù)量是無限的,我們無法顯性地把所有的策略值表示出來.Kiekintveld等人[37]用可能的收益值的連續(xù)分布來代替:

這表示保護(hù)者對(duì)于攻擊者收益值的信念.比如,保護(hù)者認(rèn)為當(dāng)攻擊者攻擊一個(gè)被保護(hù)的目標(biāo)ti時(shí),他以(ti,c)的概率得到收益r.這種建模方式使得領(lǐng)域?qū)＜铱梢愿雍啽愕貋肀硎緦?duì)于攻擊者收益的不確定性.他們不需要給出確切的攻擊者類型數(shù)量、每種攻擊者出現(xiàn)的概率和對(duì)應(yīng)的確切收益值,只需要根據(jù)他們自己的信念或者不完全的情報(bào)信息給出攻擊者攻擊某一目標(biāo)時(shí)可能得到的收益分布即可.

然而因?yàn)楸旧碛邢薏┺牡那樾尉褪荖P-hard的,這個(gè)無窮貝葉斯博弈模型是無法得到精確解的,所以Kiekintveld等人[37]利用了數(shù)值解、蒙特卡洛采樣和近似優(yōu)化的思想為這一模型設(shè)計(jì)了多種近似求解算法.為了求解這個(gè)模型,我們需要求解出保護(hù)者的最優(yōu)覆蓋策略和每種攻擊者類型的最佳響應(yīng).這一問題可以分解成兩步,一是計(jì)算或者估計(jì)攻擊者的最佳響應(yīng)對(duì)保護(hù)者覆蓋策略的函數(shù);二是有了這個(gè)最佳響應(yīng)函數(shù)之后,搜索保護(hù)者的策略集空間來尋找保護(hù)者的最優(yōu)策略.為了近似地計(jì)算攻擊者的最佳響應(yīng)函數(shù),Kiekintveld等人[37]提出了兩種近似方法,分別是蒙特卡洛采樣方法和分段常量函數(shù)近似法.蒙特卡洛采樣方法的思想是,首先在攻擊者類型的分布函數(shù)中等可能性地采樣出有限數(shù)量的攻擊者類型,然后利用上面的兩個(gè)式子得到每種攻擊者類型對(duì)應(yīng)的收益值.然后利用改進(jìn)的貝葉斯ERASER算法來求解得到攻擊者的最佳響應(yīng)函數(shù),這種做法采樣的數(shù)量越多,得到的響應(yīng)函數(shù)越準(zhǔn)確,當(dāng)采樣數(shù)量趨近于無窮時(shí),可以得到精確的響應(yīng)函數(shù).分段常數(shù)函數(shù)近似法的思想是,首先假設(shè)攻擊者決定在一個(gè)攻擊目標(biāo)集合的子集中更傾向于攻擊哪個(gè)目標(biāo)時(shí),只考慮這個(gè)子集中的目標(biāo)被覆蓋的概率,不考慮其他目標(biāo)是否被覆蓋.比如,令D={1,2}?{1,2,3},則當(dāng)攻擊者評(píng)估攻擊目標(biāo)t1和攻擊目標(biāo)t2哪個(gè)更有利時(shí),只需要知道覆蓋概率c1和c2,而不需要知道目標(biāo)t3被保護(hù)的概率c3.這個(gè)假設(shè)看似是合理的,但是并不是一直是最優(yōu)的.利用這個(gè)假設(shè)可以迭代地增加考慮的攻擊目標(biāo)子集,得到攻擊者的最佳響應(yīng)函數(shù).給定了攻擊者的最佳響應(yīng)函數(shù)后,為了有效地搜索保護(hù)者的策略集空間來尋找保護(hù)者的最優(yōu)策略,Kiekintveld等人[37]提出了復(fù)制動(dòng)力學(xué)采樣和貪婪的蒙特卡洛搜索兩種近似方法.復(fù)制動(dòng)力學(xué)采樣是一種局部搜索算法,基于復(fù)制動(dòng)力學(xué)的思想.該算法首先有一個(gè)具有隨機(jī)覆蓋概率的初始種群,然后利用上文給出的攻擊者最佳響應(yīng)函數(shù)計(jì)算出這每個(gè)覆蓋概率下攻擊者和保護(hù)者的收益,利用這個(gè)收益來改變對(duì)應(yīng)的覆蓋概率,產(chǎn)生下一代個(gè)體的覆蓋概率.收益越大適應(yīng)度越大,覆蓋概率的改變?cè)叫?這樣經(jīng)過一段時(shí)間迭代后,得到較優(yōu)的覆蓋概率.貪婪的蒙特卡洛搜索的思想是從每個(gè)目標(biāo)的覆蓋概率都為0開始,每次給目標(biāo)增加一個(gè)小的增量的覆蓋概率.每個(gè)迭代步中,計(jì)算將這個(gè)小的增量增加到每個(gè)目標(biāo)上帶來的收益增量,然后選擇收益增量最大的目標(biāo),將這個(gè)小的增量增加在這個(gè)目標(biāo)上,算法直到所有的保護(hù)資源都已經(jīng)被分配完終止.實(shí)驗(yàn)結(jié)果表明即便使用這些近似求解算法,無窮貝葉斯模型比以往的有限貝葉斯模型在解的質(zhì)量和算法的可拓展性上都有很大的優(yōu)勢(shì).

Yin Zhenyu等人[38]進(jìn)一步提出了一個(gè)新的統(tǒng)一的HUNTER算法可以高效地求解有限貝葉斯Stackelberg安全博弈和無限貝葉斯Stackelberg安全博弈.該算法利用了多種人工智能和運(yùn)籌學(xué)的新技術(shù)來提升算法的效率:第一,它在搜索攻擊者的最佳響應(yīng)策略時(shí),使用最好優(yōu)先搜索(best- fi rst search)方法,這樣可以有效地減少搜索空間;第二,它通過首先求解一個(gè)線性規(guī)劃得到解的上界進(jìn)一步提升搜索的速度;第三,在求解線性規(guī)劃時(shí),利用了Benders分解技術(shù)進(jìn)一步提高求解效率;第四,作者發(fā)現(xiàn)在父節(jié)點(diǎn)中得到的Bender’s cuts可以在子節(jié)點(diǎn)中使用,進(jìn)一步提高了運(yùn)算速度;最后,HUNTER應(yīng)用了一種啟發(fā)式的分支規(guī)則進(jìn)一步提高算法效率.這個(gè)算法在求解離散型攻擊者類型和無限攻擊者類型的模型中都有很好的解的質(zhì)量和可拓展性.

考慮到在很多安全問題場(chǎng)景下,即使讓領(lǐng)域?qū)＜医o出攻擊者對(duì)每個(gè)攻擊目標(biāo)的確切收益分布也是不可能的,Kiekintveld等人[39]提出了一種新的更簡單的收益不確定性的建模方法.在這種基于區(qū)間的建模方法中,對(duì)于每個(gè)攻擊目標(biāo),都給出一個(gè)攻擊成功和不成功時(shí),攻擊者所能得到的最大和最小的可能收益.比如,我們可以用max和min表示目標(biāo)沒有被保護(hù)時(shí)的值,用Umax和Umin表示目標(biāo)被保護(hù)時(shí)的值.表1給出了一個(gè)由3個(gè)攻擊目標(biāo),1個(gè)保護(hù)資源的區(qū)間安全博弈收益矩陣示例.

這種建模方法的思想是,保護(hù)者只知道攻擊者的收益位于一個(gè)可能的區(qū)間以內(nèi),但是不知道確切的值.而且,保護(hù)者也不知道攻擊者的收益在這個(gè)區(qū)間內(nèi)的分布函數(shù),所以他們也沒法計(jì)算攻擊者的期望收益.在這個(gè)博弈中,強(qiáng)Stackelberg均衡的解概念就不適用了.Kiekintveld等人[39]利用了魯棒優(yōu)化中常用的最壞情況的解概念.也就是說,考慮攻擊者可能取定義的區(qū)間內(nèi)的所有收益值的組合,保護(hù)者的目標(biāo)是選擇一個(gè)最大化保護(hù)者最壞情況下的收益值的覆蓋向量C.給定覆蓋概率C,對(duì)于每一個(gè)目標(biāo),攻擊者有一個(gè)期望收益的范圍:

表1 區(qū)間安全博弈收益矩陣示例

所以在這個(gè)覆蓋概率下,攻擊者可以保證至少得到所有最小期望收益中的最大值,我們用R=maxtivmin(ti)來表示這個(gè)量.已知R值,則所有具有最大期望收益vmax(ti)≥R的目標(biāo)ti都有可能成為某種特定的攻擊者類型的最佳攻擊目標(biāo).我們可以定義一個(gè)潛在的攻擊目標(biāo)集Λ(C)={ti:vmax(ti)≥R}.另外,保護(hù)者對(duì)于每個(gè)攻擊目標(biāo)的期望收益為:di=ci·U(tti)+(1?ci)U(tti).所以,保護(hù)者的目標(biāo)是選擇一個(gè)覆蓋策略C,在這個(gè)策略下可以最大化保護(hù)者在潛在攻擊目標(biāo)中可能得到的最差收益:為了求解這一優(yōu)化問題,Kiekintveld等人[39]將這一問題轉(zhuǎn)化成一系列可行問題.首先,觀察到保護(hù)者的期望收益是隨著可用保護(hù)資源數(shù)量單調(diào)遞增的.保護(hù)者的可選覆蓋策略空間也是隨著保護(hù)資源數(shù)量單調(diào)遞增的.利用這一特點(diǎn),我們可以在保護(hù)者的期望收益空間內(nèi)進(jìn)行二分查找.在每一個(gè)迭代步中,已知保護(hù)者的資源數(shù)量,我們首先測(cè)試保護(hù)者取期望收益區(qū)間的中間值是否可行.如果不可行,最大收益一定小于中間值;如果可行,則最大收益一定大于等于中間值.利用這一方法,我們可以近似地得到保護(hù)者的最大收益.這是一個(gè)多項(xiàng)式時(shí)間的近似算法.

Nguyen等人[40]利用魯棒優(yōu)化中的極小化最大后悔值準(zhǔn)則針對(duì)基于區(qū)間的安全博弈模型提出了一種新的解的概念.首先我們定義并令I(lǐng)=則每一種可能的攻擊者類型對(duì)應(yīng)一個(gè)收益集合:

當(dāng)保護(hù)者的覆蓋概率為C時(shí),保護(hù)者在面對(duì)這種攻擊者類型時(shí)的期望收益為:

保護(hù)者在采用覆蓋概率C時(shí)的最大后悔值定義為:

這意味著,選擇這個(gè)覆蓋概率在最壞的情況下,可能少得到的收益.極小化最大后悔值準(zhǔn)則的意思就是要選擇最大后悔值最小的覆蓋概率:

在表1的例子中,如果按照最大化最差收益的準(zhǔn)則,則保護(hù)者的最佳策略為[1.0,0.0,0.0],把所有的資源分配在最脆弱的目標(biāo)1上,因?yàn)檫@個(gè)目標(biāo)的收益和損失值都是最小的,盡管保護(hù)目標(biāo)1得到的收益很小.在這種準(zhǔn)則下,最大的后悔值為11.而如果用極小化最大后悔值準(zhǔn)則,保護(hù)者的最優(yōu)策略為[0.34,0.44,0.22],在這種情況下,最大的后悔值為6.2.極小化最大后悔值最優(yōu)策略的求解問題可以表示成以下優(yōu)化問題:

在這個(gè)問題中,和都是連續(xù)的,所有約束的數(shù)量是無窮多的,另外這個(gè)問題是非凸的,所以非常難求解.Nguyen等人[40]利用了約束采樣和約束生成的方法來近似地求解這一問題.基本思想是先隨機(jī)采樣產(chǎn)生一個(gè)約束子集,然后不斷地給這個(gè)松弛的問題增加違背的約束直到收斂到最優(yōu)解.實(shí)驗(yàn)結(jié)果表明這種算法可以很快得到質(zhì)量很好的解.

4.2 執(zhí)行與觀察誤差

為了保證上述算法所得解的最優(yōu)性質(zhì),算法對(duì)于攻擊者的策略選取進(jìn)行了嚴(yán)格的假設(shè).它們認(rèn)為保護(hù)者能夠嚴(yán)格地執(zhí)行自己的策略,即便在執(zhí)行混合策略的情況下;同時(shí)假定攻擊者能夠完全觀察到保護(hù)者的執(zhí)行策略,并在此基礎(chǔ)上選取期望收益最高的目標(biāo)進(jìn)行攻擊.但是在現(xiàn)實(shí)世界中,這兩個(gè)假設(shè)很難得到滿足.保護(hù)者的執(zhí)行誤差和攻擊者的觀察誤差不可避免地存在,進(jìn)而影響了博弈雙方的收益,這削弱了上述算法的有效性.在考慮攻擊者無法完全得知保護(hù)者策略的情況下,GUARD[41]假定攻擊者觀察到的策略將會(huì)服從錨定理論.該理論認(rèn)為在沒有得到任何信息的時(shí)候,人們傾向于認(rèn)為可能發(fā)生的情況服從平均分布,并且一旦得到有用信息,人們將會(huì)在平均分布上進(jìn)行偏移.GUARD算法認(rèn)為在保護(hù)者采取策略時(shí),攻擊者觀察到的策略為=1/|X|·α+(1?α)P這樣攻擊者將會(huì)根據(jù)x0進(jìn)行決策,亦即0≤(al?∈XC)≤(1)M.雖然錨定理論是攻擊者的觀察偏見,但是可以看成一種觀察誤差.當(dāng)然也可以將錨定理論看做是由策略空間X到策略空間X0的映射,可以利用DOBSS求解x0,進(jìn)而求得保護(hù)者實(shí)際的執(zhí)行策略x.

在之后的工作中,研究者考慮了不同于錨定理論產(chǎn)生結(jié)果的觀察誤差,同時(shí)加入了保護(hù)者的執(zhí)行誤差.Yin等人[42]提出的RECON算法中,對(duì)于保護(hù)者的策略Cintend,其實(shí)際執(zhí)行策略y可以發(fā)生如下偏離:αi;而攻擊者所觀察到的并借以做出決策的策略Cobs也可以與實(shí)際執(zhí)行策略發(fā)生類似偏離:βi,而保護(hù)者只能最大化在誤差發(fā)生情況中的最差收益:其中在求解過程中,RECON通過引入Weakly Inducible目標(biāo)集S(Cint)將現(xiàn)有的雙層優(yōu)化問題變?yōu)閱螌觾?yōu)化問題.S(Cint)中目標(biāo)tj滿足:

相應(yīng)的規(guī)劃問題可以表述為:

其中,實(shí)驗(yàn)結(jié)果表明RECON相對(duì)于ERASER和COBRA具有更強(qiáng)的魯棒性,并且能為保護(hù)者帶來更高的收益.

RECON考慮的執(zhí)行誤差是靜態(tài)的,Jiang等人[43]考慮了動(dòng)態(tài)執(zhí)行誤差.不同于以上算法,時(shí)序成為影響執(zhí)行誤差的因素之一.這種誤差產(chǎn)生的原因是上述算法獲得的保護(hù)策略在執(zhí)行過程中由于突發(fā)事件和調(diào)度問題可能得到中斷,進(jìn)而無法得到有效實(shí)施,產(chǎn)生誤差.這在現(xiàn)實(shí)生活中是突出存在的,并造成了可觀的損失.Jiang等人[43]考慮一類具有動(dòng)態(tài)執(zhí)行誤差的貝葉斯Stackerberg博弈,其中保護(hù)者所擁有的總計(jì)R個(gè)巡邏單元i將會(huì)處在有限狀態(tài)空間S中的狀態(tài)si并執(zhí)行有限行為空間A中的行為ai.不同狀態(tài)之間的轉(zhuǎn)換服從馬爾科夫決策過程(MDP).Ti(si,ai,)為在當(dāng)前狀態(tài)si執(zhí)行的情況下,博弈轉(zhuǎn)化為 狀態(tài)的概率;Ri(si,ai,)是相應(yīng)轉(zhuǎn)換為保護(hù)者帶來的收益.這類收益是保護(hù)者在環(huán)境中獲得的收益,而非保護(hù)者與攻擊者發(fā)生博弈為保護(hù)者帶來P的收益.這樣攻擊者所能獲得的收益可以表示為γ∈ΓpγEt π[UΘ(t,π,aγ)],而攻擊者將會(huì)選擇攻擊期望收益最大的目標(biāo),即aγ∈Et π[UΨ(t,π,aγ)].在求解過程中,Jiang 等人[43]通過假設(shè)博弈具有可分離的收益并引入邊際轉(zhuǎn)換概率xi(si,ai,)以及邊際到達(dá)/執(zhí)行概率wi(si,ai),二者滿足如下約束:

這些約束條件解決了優(yōu)化過程的指數(shù)增長問題,并將優(yōu)化問題轉(zhuǎn)化為混合整數(shù)規(guī)劃問題,其優(yōu)化任務(wù)為:

求解結(jié)果是邊際概率,卻不能得到適用于馬爾科夫決策過程的策略.因此算法還需尋找能夠滿足最優(yōu)邊際概率的巡邏策略.

4.3 觀察能力的不確定性

在安全領(lǐng)域,研究者之所以選擇強(qiáng)Stackerberg均衡作為保護(hù)者的策略,便是基于攻擊者能夠?qū)ΡＷo(hù)者的策略進(jìn)行觀察,并在觀察之后選擇最優(yōu)響應(yīng),雖然在觀察過程中存在上述考慮的誤差.但是另外一種可能也會(huì)存在,就是攻擊者在執(zhí)行攻擊之前根本就無法得到保護(hù)者執(zhí)行策略的相關(guān)信息.這樣在完全理性的假設(shè)下,博弈結(jié)果將會(huì)是Nash均衡.在不同的博弈假設(shè)和收益矩陣的情況下,上述兩種均衡具有不同的性質(zhì),二者之間的聯(lián)系也有不同.Korzhyk等人[10]證明在安全博弈中,保護(hù)者的納什策略也是MINIMAX策略,而在滿足SSAS性質(zhì)的情況下,保護(hù)者的強(qiáng)Stackerberg策略也是納什策略.此外,在僅有一種保護(hù)資源的情況下,如果對(duì)于任何一個(gè)保護(hù)目標(biāo),(ti)6=E?,其中E?為MINIMAX策略攻擊者的收益值,那么保護(hù)者將會(huì)僅有一個(gè)強(qiáng)Stackerberg均衡策略.Korzhyk等人[44]考慮攻擊者具有pobs的概率可以完全觀察到攻擊者的策略,而有1?pobs的概率不能得知.保護(hù)者在不能得知攻擊者能否觀察到自己策略的情況下,將會(huì)通過最大化期望收益

來選擇最優(yōu)策略.由于攻擊者不能總是觀察到保護(hù)者的策略,這使得保護(hù)者的純策略仍然是一個(gè)分布,因此我們不再能夠?qū)懴滤屑儾呗?為了克服這個(gè)困難,設(shè)計(jì)算法在FIND-NE部分求解博弈的納什均衡策略,并以此作為保護(hù)者所選擇執(zhí)行的策略集元素加入D中,在現(xiàn)有策略集D的情況下,攻擊者將會(huì)采取納什均衡策略q,通過優(yōu)化保護(hù)者的期望收益,進(jìn)而求得保護(hù)者的最優(yōu)策略.相應(yīng)的算法流程如下:

在觀察能力的不確定性中,現(xiàn)有研究考慮的另一種情況是攻擊者只能夠觀察持續(xù)一段時(shí)間τ的攻擊者策略,然后設(shè)計(jì)自己的攻擊方案并執(zhí)行攻擊.這意味著觀察結(jié)果將會(huì)影響攻擊者的策略選取.An等人[45]假定攻擊者對(duì)于保護(hù)者執(zhí)行策略的先驗(yàn)概率服從狄利克雷分布,即:

在觀察到結(jié)果o后,利用貝葉斯規(guī)則可以求得后驗(yàn)分布:

則根據(jù)后驗(yàn)分布得到的邊際覆蓋概率為:

而攻擊者將會(huì)根據(jù)這樣的知識(shí)選擇最優(yōu)策略,此時(shí)攻擊者將會(huì)攻擊的目標(biāo)集為φ(o)=argmaxt∈T((t)+(1)(t)),因此保護(hù)者求解最優(yōu)策略的規(guī)劃問題成為如下形式P1形式:

對(duì)目標(biāo)函數(shù)取對(duì)數(shù)后使得其成為上凸的,成為P2形式:

在這種處理方法中,需要保護(hù)者事先得知攻擊者的觀察時(shí)間,而An等人[46]通過利用馬爾科夫決策過程模擬攻擊者的觀察行為放寬了這個(gè)假設(shè),相應(yīng)的博弈過程成為:1)保護(hù)者在得知攻擊者對(duì)于自己采用策略的先驗(yàn)分布的情況下選取混合策略x;2)攻擊者選擇進(jìn)行觀察或者進(jìn)行攻擊,若選擇進(jìn)行觀察,則根據(jù)現(xiàn)有觀察結(jié)果更新自己關(guān)于保護(hù)者策略的后驗(yàn)分布,如果選擇攻擊,則博弈結(jié)束.在求解過程中,作者證明在為每一個(gè)狀態(tài)o給定最優(yōu)值V(o)之后,利用BI-FS(Backward Induction with Forward Search)算法可以尋找到滿足攻擊者馬爾科夫決策過程的最優(yōu)解觀察圖O?.在此基礎(chǔ)上,求解保護(hù)者最優(yōu)策略的方法與之前方法類似.

在以往的研究中,攻擊者雖然能夠得知保護(hù)者的策略,因此,可以知道攻擊目標(biāo)被保護(hù)的概率,但是卻不能得知在攻擊發(fā)生的時(shí)候保護(hù)者采取的保護(hù)行為.在這個(gè)假設(shè)下,攻擊者可以通過隨機(jī)化自己的保護(hù)資源來提高自己的收益.但是這個(gè)假設(shè)在某種程度上并不直觀,因此,在相關(guān)文獻(xiàn)中放松了這個(gè)假設(shè),攻擊者雖然在不能得知在隨之而來的攻擊中保護(hù)者的保護(hù)行為,但是可以在觀察保護(hù)者現(xiàn)有保護(hù)行為的基礎(chǔ)上對(duì)其下一步保護(hù)行為進(jìn)行推測(cè).

Vorobeychik等人[47]證明對(duì)于任何滿足:UΘ(s,θ,ψ)=UΨ(s,θ,ψ) 且γΘ=γΨ的隨機(jī)Stackerberg博弈,都存在一個(gè)確定的分別由保護(hù)者和攻擊者馬爾科夫穩(wěn)態(tài)策略構(gòu)成的強(qiáng)Stackerberg均衡.這時(shí)的博弈發(fā)生在圖G上,不同的資源分布將會(huì)受到圖的拓?fù)浣Y(jié)構(gòu)的影響,而在資源分布調(diào)整的時(shí)候,保護(hù)者需要承擔(dān)一定的花費(fèi).但是這個(gè)結(jié)果并不能廣泛成立,正如Vorobeychik等人[48]、Letchford等人[49]陳述的,在一般的隨機(jī)Stackerberg博弈中,保護(hù)者的最優(yōu)策略并不是馬爾科夫穩(wěn)態(tài)策略.在這種情況下,Vorobeychik等人[48]考慮的博弈過程是z0對(duì)應(yīng)保護(hù)資源分配的起始狀態(tài),而保護(hù)者將會(huì)參考固定長度K的保護(hù)行為歷史來決定自己接下來的行為,其中被用來參考的歷史稱為不同的狀態(tài),記為s.而當(dāng)且僅當(dāng)保護(hù)者可以在狀態(tài)s的最后一個(gè)覆蓋向量轉(zhuǎn)變到z的情況下,Bsz=1.文章證明對(duì)于任意狀態(tài)s∈S,z0∈Z,只有在Gzz0具有完全匹配的時(shí)候,Bzz0=1.而一個(gè)保護(hù)者的策略給出在任何狀態(tài)s∈S下,保護(hù)者選擇可能出現(xiàn)的覆蓋向量的概率分布.在上述博弈過程中,假定攻擊者將會(huì)考慮h博弈步內(nèi)的期望收益:

而保護(hù)者的最終受益還需要考慮不同保護(hù)資源策略之間轉(zhuǎn)變的花費(fèi),

其中,

將上述限制條件結(jié)合在一起就成了需要求解的規(guī)劃問題.上述約束條件中,整數(shù)變量的組合以及連續(xù)變量πsz與其他變量的非上凸關(guān)聯(lián)為問題的求解增加了困難.為了克服這些困難,如果上述變量中至少有一個(gè)是二值變量,McCormick不等式提供了一種混合整數(shù)規(guī)劃的近似,降低了問題求解的復(fù)雜度.

4.4 人類行為建模

為確保算法結(jié)果的最優(yōu)性質(zhì),上述算法對(duì)博弈雙方的決策過程做出了很強(qiáng)的假設(shè).它們認(rèn)為博弈雙方是完全理性而且攻擊者會(huì)沒有誤差地觀察到守護(hù)者的策略,在守護(hù)者策略是混合策略的時(shí)候這樣的假設(shè)顯得更加重要.然而,這些假設(shè)很難在真實(shí)世界中得到執(zhí)行,尤其是博弈雙方均為人類的時(shí)候.攻擊者如何在已有知識(shí)的情況下進(jìn)行決策成為影響上述算法有效性的一個(gè)關(guān)鍵假設(shè).一般來說,應(yīng)用系統(tǒng)利用博弈論中的完全理性以及利益最大化假設(shè)進(jìn)行建模.雖然這是一個(gè)為研究者普遍接受的假設(shè),但是這將會(huì)使得保護(hù)策略在面對(duì)使用不同決策過程的襲擊者時(shí)表現(xiàn)很差,這些算法并不能利用人類決策過程中顯而易見的弱點(diǎn)為保護(hù)者獲得更好的收益.因此,完全理性等博弈論經(jīng)典假設(shè)在多主體領(lǐng)域應(yīng)用的有效和合理性受到質(zhì)疑,并且引起了研究者的注意[50].此方面的一個(gè)重要進(jìn)展是BRASS[51].BRASS假定攻擊者能夠?qū)ψ顑?yōu)策略進(jìn)行ε的偏離.這意味著攻擊者將在與最優(yōu)收益偏離ε的范圍內(nèi)隨機(jī)選取策略,這樣在給定多個(gè)ε?最優(yōu)策略的情況下,由于隨機(jī)性的存在,保護(hù)者只能優(yōu)化自己可能得到的最差收益.因此,優(yōu)化問題約束條件

使得當(dāng)=1時(shí),al?i∈X<ε,滿足了上面提到的ε偏離的要求.隨之加入規(guī)劃限制確保了算法解的有效性.這種思路不同于之前研究之處是,傳統(tǒng)方法假定攻擊者會(huì)選擇最大化保護(hù)者收益的策略.這項(xiàng)工作中表明BRASS相比DOBSS,能夠在面對(duì)智能攻擊者的時(shí)候取得更好的表現(xiàn).但是這樣工作中對(duì)于ε偏離產(chǎn)生的原因沒有進(jìn)行討論,相關(guān)的人類行為決策過程也沒有涉及.

這個(gè)問題在接下來的工作中得到回答.Yang等人[52]在行為經(jīng)濟(jì)學(xué)的前景理論和行為博弈論的隨機(jī)最優(yōu)化模型的基礎(chǔ)上分別提出了BRPT和BRQR算法,為算法中相關(guān)不同于經(jīng)典博弈論假設(shè)的改動(dòng)提供了清晰的決策過程.前景理論認(rèn)為人類在決策過程中將會(huì)最大化自己的期望,這里的期望被定義為π(pi)V(ci),其中pi為ci實(shí)際發(fā)生概率,權(quán)重函數(shù)π(pi)是決策者賦予ci的概率.一般情況下,πpi+π1?pi<1.V(ci)為ci能夠帶來的收益.前景理論表明人的決策具有損失厭惡,也就是說,人們過低預(yù)測(cè)收益發(fā)生的概率而過高預(yù)測(cè)損失的發(fā)生概率.

圖13 前景理論的經(jīng)驗(yàn)函數(shù)

隨機(jī)最優(yōu)化模型認(rèn)為人們并不嚴(yán)格最大化自己的收益,而是隨機(jī)性地進(jìn)行行為決策:當(dāng)誤差所帶來的懲罰降低的時(shí)候,人們選擇非最優(yōu)策略的概率增加.在其他人的策略給定的情況下,選取行為i的概率為:(x)=其中(x)是選取攻擊者行為t的期望收益.同時(shí),λ的取值決定了行為者p的理智程度:當(dāng)λ=0時(shí),行為者對(duì)收益不加考慮地選擇行為,當(dāng)λ→∞時(shí),隨機(jī)最優(yōu)化變?yōu)樽罴秧憫?yīng).

BRPT在假定攻擊者行為滿足前景理論的情況下給出最優(yōu)的保護(hù)策略.攻擊者攻擊目標(biāo)t而獲得的前景收益通過下式給出:π(xi)V()+π(1?xi)V().而攻擊者將會(huì)選擇前景收益最高的目標(biāo)進(jìn)行攻擊.這樣核心的規(guī)劃約束條件表示為:

為了克服非線性和非上凸函數(shù)π·為算法實(shí)現(xiàn)帶來的困難,BRPT采用了分段線性函數(shù)對(duì)其進(jìn)行近似,近似函數(shù)在圖14[52]展示.其中將π·分為了5部分線性函數(shù),這樣算法被改造成了一個(gè)混合整數(shù)線性規(guī)劃問題,提高了算法的運(yùn)算效率.

圖14 權(quán)重函數(shù)分段線性近似

在前景理論決策模型的基礎(chǔ)上,RPT模型通過引入攻擊者對(duì)執(zhí)行策略與最優(yōu)策略之間的ε偏離,融合了BRASS算法的優(yōu)勢(shì),使得算法更加貼近現(xiàn)實(shí)情況.

相應(yīng)地,BRQR假定攻擊者的決策模型滿足隨機(jī)最優(yōu)化,這樣優(yōu)化問題的目標(biāo)函數(shù)可以表示為:

這樣算法面臨著目標(biāo)函數(shù)的非線性和非上凸性質(zhì)帶來的求解困難.該算法通過多次選取起始點(diǎn)迭代使得其有更大的可能性收斂于全局最優(yōu)解,而在每次迭代中只尋找局部最優(yōu)解.

PASAQ通過利用二分搜索克服了BRQR算法收斂性的問題,提升了算法的運(yùn)算速度,并且充分考慮了保護(hù)資源分配中的相關(guān)限制條件,使得其成為PROTECT系統(tǒng)的核心算法[53].

這些算法需要對(duì)保護(hù)者的純策略進(jìn)行遍歷,在應(yīng)用情景更為大型的時(shí)候無法使用.BLADE算法利用切割平面法對(duì)PASAQ進(jìn)行了擴(kuò)展[54].

切割平面方法主要體現(xiàn)在Separation Oracle部分,它利用了最小化范式的方法能夠有效地對(duì)一個(gè)不合適的策略集進(jìn)行切割,這保證了每一次的切割都能夠使得剩余策略集最大程度地接近合適的策略集.另一方面為了驗(yàn)證Quantual Response在解釋人類行為建模的意義,SU-BRQR[55]引入了一類新的主觀效益函數(shù)它為所有決策者可知的信息賦予了相應(yīng)的權(quán)重,增加了模型的合理性,但在求解過程中并沒有太大改變.

不同于上述行為經(jīng)濟(jì)學(xué)建模思路,穩(wěn)健優(yōu)化方法在MATCH算法中得到了再一次的改進(jìn).與在BRASS中僅考慮攻擊者對(duì)于最優(yōu)策略的偏離,而保護(hù)者最優(yōu)化自己的收益不同,MATCH限制了保護(hù)者的最大損失[56].相應(yīng)的規(guī)劃算法表示為:

約束條件5是算法中最重要的條件,不等式左側(cè)UΨ(x,q)?UΨ(x,)計(jì)算攻擊者由于采用偏離的最優(yōu)策略而產(chǎn)生的損失,不等式右側(cè)γ?UΘ(,x)給出了保護(hù)者所承受的期望損失,其中β表示保護(hù)者所能承受的極限期望損失.這一約束條件將保護(hù)者由于攻擊者的策略偏移而得到的最大收益和改進(jìn)保護(hù)策略缺點(diǎn)之間進(jìn)行了平衡.MATCH算法具有3個(gè)優(yōu)勢(shì):1)它的運(yùn)算速度快于BRQR;2)它通過耦合攻擊者和保護(hù)者的表現(xiàn),為保護(hù)者帶來高于BRQR的收益;3)它避免了設(shè)計(jì)一種精確模型,增強(qiáng)了算法的普適性.

鑒于穩(wěn)健優(yōu)化和人類行為建模各有優(yōu)勢(shì),MonitonicMaximin結(jié)合了上述兩種建模方法[57].其總體思路是在原有Maximin算法中加入對(duì)于攻擊者選取的策略的限制,并假定攻擊者的策略滿足單調(diào)性,隨機(jī)最優(yōu)化成為這種條件下的特例.實(shí)驗(yàn)證明該算法的表現(xiàn)優(yōu)于上面提到的MATCH算法.

5 算法效能評(píng)估進(jìn)展

在上述算法提出和相應(yīng)的安全系統(tǒng)設(shè)計(jì)的同時(shí),對(duì)于算法和系統(tǒng)的評(píng)價(jià)機(jī)制的設(shè)計(jì)也進(jìn)入了研究者的考慮之中.計(jì)算機(jī)科學(xué)家在其具有豐富研究手段的算法運(yùn)行時(shí)間、算法復(fù)雜度、魯棒性及敏感性的方面給出了評(píng)價(jià)方法;但是由于多主體研究是理論結(jié)合實(shí)際問題的,因此,還要進(jìn)行更為細(xì)致和全面的考量,例如傳統(tǒng)的定量分析及領(lǐng)域?qū)＜乙庖娨彩侵档脜⒖嫉闹匾獦?biāo)準(zhǔn).Taylor等人[58?59]在對(duì)ARMOR系統(tǒng)進(jìn)行的評(píng)價(jià)中提出了多種評(píng)價(jià)機(jī)制選擇,其評(píng)價(jià)機(jī)制在以后的研究工作中得到了進(jìn)一步的創(chuàng)新和發(fā)展,形成了較為完善的評(píng)價(jià)機(jī)制.我們?cè)诖司C述如下.

5.1 算法博弈論的評(píng)價(jià)方法

利用博弈論視角來模擬安全問題是現(xiàn)有工作的基本假設(shè),也是最重要的假設(shè).博弈論給出了博弈雙方的博弈環(huán)境以及行為決策過程.算法博弈論利用計(jì)算機(jī)手段對(duì)博弈均衡進(jìn)行求解,現(xiàn)有的絕大多數(shù)工作將SSE作為目標(biāo)求解策略.因此,這類基本假設(shè)及算法求解中的表現(xiàn),成為計(jì)算機(jī)研究者評(píng)價(jià)過程中最為感興趣的一部分.

5.1.1 運(yùn)行時(shí)間與可擴(kuò)展性

有鑒于安全博弈問題的實(shí)用性背景,算法必須在相關(guān)部門可以承受的時(shí)間范圍之內(nèi)對(duì)問題進(jìn)行有效求解,而算法在問題尺度擴(kuò)大情況下的表現(xiàn)也得到了關(guān)注.

Pita等人[16]在改變貝葉斯Stackelberg博弈中對(duì)手種類的情況下,驗(yàn)證了DOBSS的表現(xiàn)要優(yōu)于ASAP和MultiLPs.Jain等人[60]在目標(biāo)數(shù)量、可用資源數(shù)量以及對(duì)手?jǐn)?shù)量3種不同的參數(shù)情況下表現(xiàn)了ERASER-C在運(yùn)行時(shí)間上少于DOBSS及MutiLPs.Pita等人[24?25]在不同領(lǐng)域數(shù)量、每一領(lǐng)域不同活動(dòng)種類及不同資源數(shù)量3個(gè)方面表明了GUARD采用的緊湊表示具有比DOBSS采用的全表示更好的擴(kuò)展性,關(guān)于二者所需內(nèi)存分析中也驗(yàn)證了這一點(diǎn)[18].Tsai等人[6]也在3種不同的FAMS數(shù)量上驗(yàn)證了IRIS在求解時(shí)間上的實(shí)用性.由上可以看出,分析運(yùn)行時(shí)間隨著不同博弈參數(shù)的變化成為分析算法表現(xiàn)的基本步驟.

圖15 DOBSS、ASAP和MultipLP運(yùn)行時(shí)間

5.1.2 策略表現(xiàn)分析

除了對(duì)于算法運(yùn)行時(shí)間的可行性的考慮,研究者還討論了算法求解出的SSE策略為保護(hù)者帶來的收益進(jìn)行了分析.

Pita等人[24?25]集中分析了GUARD 中使用的策略相對(duì)均勻隨機(jī)策略帶來的保護(hù)者收益上的提升,同樣Tsai等人[6]中對(duì)IRIS策略、權(quán)重和均勻隨機(jī)策略進(jìn)行了比較.Shieh等人[18?22]提供了使用λ=1.5的PASAQ算法能夠給出比DOBSS、均勻隨機(jī)策略(保護(hù)者或攻擊者)更高收益的實(shí)驗(yàn)證據(jù).以上的結(jié)果說明采用博弈論框架下的SSE均衡策略確實(shí)能夠?yàn)楸Ｗo(hù)者帶來收益上的提升,而這是安全系統(tǒng)應(yīng)用的目的.因此,策略表現(xiàn)的分析驗(yàn)證了上述研究的實(shí)用價(jià)值.

圖16 GUARD求解策略收益分析

5.1.3 魯棒性

由于混合策略只具有統(tǒng)計(jì)意義,在每一時(shí)刻保護(hù)者只能選擇一個(gè)純策略進(jìn)行實(shí)施.這種策略的實(shí)施過程不可避免地帶來了實(shí)施誤差,進(jìn)而可能影響博弈雙方的實(shí)際收益.因此,驗(yàn)證所得策略的魯棒性成為評(píng)價(jià)機(jī)制的一個(gè)選擇.

圖17 PROTECT系統(tǒng)在觀察噪聲下保護(hù)者的期望收益

Shieh等人[18?22]在博弈中加入了由于攻擊者觀察誤差、執(zhí)行誤差和收益誤差所引起的噪聲驗(yàn)證了使用λ=1.5的PASAQ算法能夠給出比DOBSS具有更高魯棒性的保護(hù)者策略.

5.2 數(shù)據(jù)建模模擬方法

除了考慮模型求解出的策略的性質(zhì)之外,研究者對(duì)于模型如何建立也考量,并且發(fā)展出通過已有數(shù)據(jù)建立博弈模型,評(píng)價(jià)相關(guān)算法優(yōu)劣的評(píng)價(jià)機(jī)制.Jain等人[60]利用來自LAX方面的真實(shí)數(shù)據(jù),建立了對(duì)于ARMOR獵犬問題進(jìn)行模擬的博弈模型.在評(píng)價(jià)中,筆者比較了不同情況下由ERASER-C產(chǎn)生的巡邏過程與均勻隨機(jī)巡邏過程的保護(hù)者的收益情況.

Yin等人[8,23]利用來自4條真實(shí)洛杉磯地鐵線路的數(shù)據(jù)集,根據(jù)列車時(shí)刻表建立了轉(zhuǎn)換網(wǎng)絡(luò),同時(shí)考慮了不同的時(shí)間上下地鐵人群分布變化以及列車運(yùn)行的真實(shí)情況,建立了仿真模型,進(jìn)行實(shí)驗(yàn)驗(yàn)證了TRUST系統(tǒng)在不同參數(shù)條件下的有效性.

相似地,Haskell等人[31]利用來自NOAA的海岸生態(tài)系統(tǒng)地圖中的漁業(yè)數(shù)據(jù),以及USCG漁船數(shù)據(jù),并將試驗(yàn)重點(diǎn)放在墨西哥灣的部分海域,通過將目標(biāo)海域離散化為網(wǎng)格建立了相關(guān)的博弈模型,并分別在考慮距離因素和不考慮距離因素的情況下,比較COmPASS與SUQR和MAXIMIN帶來的不同收益,肯定了COmPASS的更為優(yōu)良的表現(xiàn).Yang等人[30]利用了真實(shí)偷獵者的分布來模擬了野生動(dòng)物保護(hù)的實(shí)驗(yàn)過程,檢驗(yàn)了不同的學(xué)習(xí)策略在適應(yīng)性的資源分配原則下對(duì)于偷獵行為的打擊作用.真實(shí)數(shù)據(jù)的獲取和在博弈模型中的應(yīng)用,極大地將理論算法與實(shí)際問題結(jié)合起來,而避免了真實(shí)應(yīng)用中較為龐大的人力物力耗費(fèi),成為評(píng)價(jià)安全系統(tǒng)表現(xiàn)的常用手段.

圖18 TRUST真實(shí)數(shù)據(jù)建模結(jié)果

5.3 真實(shí)世界中的應(yīng)用

安全問題是真實(shí)世界中的問題,而現(xiàn)有工作中的模型都或多或少地進(jìn)行了簡化和適用性的假設(shè).檢驗(yàn)這些簡化和假設(shè)是否會(huì)影響模型有效性的最可靠的手段仍然在真實(shí)世界中進(jìn)行應(yīng)用.但鑒于真實(shí)應(yīng)用場(chǎng)景的復(fù)雜性,為了對(duì)相關(guān)影響因素進(jìn)行區(qū)別對(duì)待,研究者在實(shí)驗(yàn)室中進(jìn)行了真實(shí)的但是規(guī)模較小、情景較為簡單的實(shí)驗(yàn)應(yīng)用,取得了令人信服的評(píng)價(jià)結(jié)果.

5.3.1 實(shí)驗(yàn)室應(yīng)用表現(xiàn)

Pita等人[56,58]進(jìn)行了一個(gè)簡單的在線博弈“海盜和寶藏”實(shí)驗(yàn)來模擬真實(shí)的LAX出入口情況.

而這個(gè)實(shí)驗(yàn)的結(jié)果很好地驗(yàn)證了ARMOR能夠在對(duì)手是真人個(gè)體的時(shí)候取得較高的收益.同樣的手段也應(yīng)用在文獻(xiàn)[52,55]評(píng)價(jià)中.實(shí)驗(yàn)室應(yīng)用的評(píng)價(jià)手段能夠在較少的花費(fèi)情況下獲得相當(dāng)接近真實(shí)大型應(yīng)用場(chǎng)景的數(shù)據(jù).尤其是對(duì)于一些含有對(duì)人類行為建模的工作,這樣的實(shí)驗(yàn)數(shù)據(jù)能夠極大程度上驗(yàn)證并反映行為建模的有效性,取得可信的評(píng)價(jià)結(jié)果.

圖19 海盜與寶藏博弈界面

5.3.2 真實(shí)系統(tǒng)布置表現(xiàn)

真實(shí)安全系統(tǒng)的表現(xiàn)具有最有利的評(píng)價(jià)特征.在這些表現(xiàn)產(chǎn)生的數(shù)據(jù)中,出現(xiàn)在現(xiàn)有評(píng)價(jià)機(jī)制中的有:Yin等人[8,23]給出了LASD測(cè)試TRUST系統(tǒng)表現(xiàn)的大體結(jié)果.Pita等人[16]在LAX中布置了ARMOR對(duì)該系統(tǒng)的運(yùn)行特征及敏感性進(jìn)行了分析,同樣地,Jain等人[60]公布了ARMOR的采用前后的犯罪行為數(shù)據(jù),肯定了其對(duì)于預(yù)防犯罪的積極作用.

Shieh等人[18?22]披露部分波士頓港口在PROTECT系統(tǒng)應(yīng)用前后為USCG帶來的區(qū)域巡邏次數(shù)的變化.系統(tǒng)運(yùn)行的全部數(shù)據(jù)由于安全原因并未得到完全公開,但是從現(xiàn)有數(shù)據(jù)中可以分析,基于博弈論的安全系統(tǒng)的設(shè)計(jì)和布置為傳統(tǒng)安全問題的解決帶來了新的重要影響.

圖20 PROTECT系統(tǒng)布置前后情況對(duì)比

5.4 行業(yè)專家評(píng)價(jià)

5.4.1 領(lǐng)域?qū)＜以u(píng)價(jià)

雖然上述提到的不同評(píng)價(jià)能夠在不同的方面為安全系統(tǒng)提供定量分析,但是每一種手段都有著其自身的局限性,且很難對(duì)安全系統(tǒng)提供全面且中肯的評(píng)價(jià).在這種情況下,領(lǐng)域?qū)＜以u(píng)價(jià)就顯得極為重要.其所具有的相關(guān)專業(yè)知識(shí)以及在安全問題處理中的豐富經(jīng)驗(yàn)?zāi)軌蚩朔鲜龅娜秉c(diǎn).Jain等人[60]提到的領(lǐng)域內(nèi)專家的評(píng)價(jià)為:雖然ARMOR和IRIS系統(tǒng)并不能提供完全的安全性,但是它們可以幫助安全部門在現(xiàn)有資源的基礎(chǔ)上進(jìn)行最為有效的防御.

5.4.2 對(duì)手評(píng)價(jià)

除了領(lǐng)域內(nèi)專家的專業(yè)意見,最直接感受到安全系統(tǒng)的作用的應(yīng)當(dāng)是攻擊對(duì)手.因此,攻擊對(duì)手的評(píng)價(jià)顯得相當(dāng)重要.Shieh等人[18?22]提到:USCG為了能夠更好地了解攻擊對(duì)手對(duì)于潛在目標(biāo)的認(rèn)識(shí)創(chuàng)建了Adversatial Perspective Team.這個(gè)團(tuán)隊(duì)能夠從恐怖分子的角度對(duì)相應(yīng)的安全系統(tǒng)進(jìn)行評(píng)估,并且承認(rèn)了PROTECT系統(tǒng)為巡邏帶來的積極作用.

5.4.3 輿論評(píng)價(jià)

輿論評(píng)價(jià)是指社會(huì)相關(guān)媒體對(duì)于犯罪事件等社會(huì)不安定因素的評(píng)價(jià)和反映,從大眾的角度對(duì)相應(yīng)安全部門的行為進(jìn)行評(píng)價(jià).Shieh等人[18?22]提供了部分USCG船員對(duì)于PROTECT系統(tǒng)實(shí)施后的直觀評(píng)價(jià),肯定了該系統(tǒng)的作用,也表明了博弈論應(yīng)用于海洋安全領(lǐng)域問題的合理性.

6 新的研究挑戰(zhàn)

盡管現(xiàn)有的研究工作極大地提升了我們對(duì)于安全問題的防范能力,但是這些工作仍然是不完善的.仍然有新的應(yīng)用領(lǐng)域以及改進(jìn)方向?yàn)檠芯抗ぷ魈岢鎏魬?zhàn).這些挑戰(zhàn)多數(shù)來自于現(xiàn)有的有限計(jì)算能力,人類行為的不確定性以及現(xiàn)實(shí)場(chǎng)景中的特殊性質(zhì).

6.1 多目標(biāo)優(yōu)化

在現(xiàn)有的安全博弈論應(yīng)用中,防御者總是試圖最大化某個(gè)單一目標(biāo).然而,有些領(lǐng)域的防御者必須同時(shí)考慮多個(gè)目標(biāo).例如,洛杉磯警察局對(duì)地鐵系統(tǒng)的保護(hù)需要考慮逃票、普通犯罪以及恐怖襲擊等多種行為.從洛杉磯警察局的視角看,每種攻擊類型都有威脅(收入減少、財(cái)產(chǎn)被盜、生命威脅等).因?yàn)檫@些多元威脅的存在,通常沒有一種單一策略可以使所有攻擊類型的威脅最小化.由于針對(duì)某種特定攻擊的保護(hù)可能增加其他攻擊的威脅,因此,必須要做權(quán)衡和折衷.多目標(biāo)安全博弈可以用來應(yīng)對(duì)有多個(gè)相互矛盾的優(yōu)化目標(biāo)的安全博弈問題.在多目標(biāo)安全博弈中,不同攻擊類型的威脅用不同的博弈矩陣來表示,并且不需要對(duì)手攻擊類型的概率分布.與只有單個(gè)最優(yōu)解的單目標(biāo)貝葉斯安全博弈不同,多目標(biāo)安全博弈通常有一個(gè)帕累托邊界,它包含了求得的帕累托最優(yōu)解.通過將帕累托邊界展示給終端用戶,他們能夠更好地理解問題的結(jié)構(gòu)和不同安全目標(biāo)間的平衡.因此,終端用戶在選擇策略時(shí)能夠作出更明智的選擇.以上考慮的多目標(biāo)優(yōu)化任務(wù)局限于保護(hù)者角度,而攻擊者的多目標(biāo)優(yōu)化假設(shè)以及有限理性行為假設(shè)成為該方向的延續(xù)工作的相關(guān)主題得到了研究者的關(guān)注[61?62].

6.2 協(xié)同優(yōu)化

協(xié)同優(yōu)化,是指使用者(如空中警察署)和計(jì)算機(jī)協(xié)作制定的安全資源分配策略.在安全資源調(diào)度問題中通常存在很多限制條件.防御者通常受到資源數(shù)量的限制.另外,當(dāng)面臨一些特殊情況或者需要額外的知識(shí)時(shí),使用者可能需要對(duì)防御者的行為設(shè)置限制以影響結(jié)果.例如,在IRIS系統(tǒng)中,有時(shí)需要強(qiáng)制在某些航班上安排空中警察(例如當(dāng)政府官員需要乘飛機(jī)時(shí)).在現(xiàn)有的安全博弈論應(yīng)用中,通常只計(jì)算出符合所有限制條件的最優(yōu)解.但由于使用者的有限理性以及對(duì)限制條件影響資源調(diào)度結(jié)果性能的有限了解,用戶定義的限制條件可能會(huì)產(chǎn)生很差的資源分配方案,甚至導(dǎo)致不存在滿足所有限制條件的分配方案.如果放開一些限制條件,分配方案的性能就會(huì)得到很大提升.放開一些限制條件有無數(shù)種方法,而計(jì)算機(jī)軟件并不知道哪些限制條件可以放開,放開多少,以及放開限制條件對(duì)分配方案性能的影響.因此,需要用戶和計(jì)算機(jī)通過協(xié)同優(yōu)化來共同制定安全資源分配策略.協(xié)同優(yōu)化研究面臨的挑戰(zhàn):第一,安全博弈和限制條件的規(guī)模使得不能使用窮盡的搜索算法去測(cè)試所有的限制條件組合;第二,用戶并不完全了解放開限制條件可能引起的后果,這就需要用戶偏好發(fā)掘技術(shù)(preference elicitation)的支持;第三,在用戶和計(jì)算機(jī)之間關(guān)于控制權(quán)轉(zhuǎn)移的決策也很具有挑戰(zhàn)性;第四,很難評(píng)價(jià)協(xié)同優(yōu)化方法的性能;第五,給計(jì)算機(jī)設(shè)計(jì)一個(gè)能夠解釋限制如何影響資源分配方案性能的用戶接口也是一個(gè)有挑戰(zhàn)性的問題[63].

6.3 多部門協(xié)作

在很多情況下,對(duì)于一個(gè)安全任務(wù),需要多個(gè)安全部門布置多種安全資源才能達(dá)到目的.例如,位于紐約的美國海岸警衛(wèi)隊(duì)可能需要協(xié)調(diào)從屬于海岸警衛(wèi)隊(duì)的船只和直升機(jī)以及NYPD的船只巡邏.在這種情況下,海岸警衛(wèi)隊(duì)指揮部門可能僅僅擁有關(guān)于NYPD巡邏船只的不確切的信息,但是需要在協(xié)調(diào)海岸警衛(wèi)隊(duì)自身安全資源的同時(shí),也要與NYPD巡邏進(jìn)行協(xié)調(diào).這需要新的解的概念以及求解此類大型問題的有效算法.多部門協(xié)作問題并不限于上述例子,得到考慮的情景有不同安全部門的相同資源的布置,同一安全部門的不同資源的布置,不同安全部門的不同資源的布置[64],以及資源布置和巡邏過程中的聯(lián)合行動(dòng).聯(lián)合行動(dòng)意味著保護(hù)者的多種資源能夠以團(tuán)隊(duì)工作的形式對(duì)關(guān)鍵區(qū)域進(jìn)行巡邏.這能夠?qū)τ诠粽弋a(chǎn)生超出單一資源分別進(jìn)行巡邏的震懾效果.團(tuán)隊(duì)工作更能夠預(yù)防單一保護(hù)資源在策略執(zhí)行過程中出現(xiàn)的偏差以及特殊情況帶來的巡邏過程中斷,而這能使得攻擊者沒有可乘之機(jī)來獲得更高的收益.然而聯(lián)合行動(dòng)所獲得收益所具有的非線性以及問題的模塊化都為這個(gè)問題的求解帶來了特別的困難,這是在其他多部門協(xié)作場(chǎng)景中所不具有的[65?67].研究者利用了模塊化優(yōu)化以及分散馬爾科夫決策過程等適應(yīng)性模型和技術(shù)對(duì)這一困難進(jìn)行初步解決,而完全解決這類問題仍然需要更深入的工作.

6.4 犯罪行為建模

現(xiàn)有安全領(lǐng)域的相關(guān)工作絕大部分涉及對(duì)于博弈雙方?jīng)Q策過程的假設(shè).與經(jīng)典的理性人的假設(shè)不同,心理學(xué)以及行為經(jīng)濟(jì)學(xué)的研究進(jìn)展為我們提供了更為實(shí)際的模型,例如前景理論和量化反應(yīng)模型.大多數(shù)的這些模型具有不同于理性人假設(shè)的表現(xiàn),也使得優(yōu)化問題成為非上凸的進(jìn)而增加了求解為難度.如何探索出一個(gè)較為實(shí)際但是能夠克服優(yōu)化非上凸性質(zhì)的行為決策模型成為犯罪行為建模方面的一個(gè)考慮.同時(shí),這些模型中具有的關(guān)鍵參數(shù)將會(huì)很大程度上影響犯罪行為建模的合理性.但是我們很難甚至幾乎不可能預(yù)知這些參數(shù)值.研究者采取機(jī)器學(xué)習(xí)手段分別對(duì)于正常數(shù)據(jù)與異常數(shù)據(jù)進(jìn)行學(xué)習(xí),對(duì)這些參數(shù)進(jìn)行預(yù)測(cè),擬合出一個(gè)最佳的人類行為模型,提升了所建博弈模型的合理性[31,53].另外得到考慮的犯罪行為模型稱為機(jī)會(huì)性犯罪,它假設(shè)了大量潛在攻擊者隨著公共交通系統(tǒng)進(jìn)行轉(zhuǎn)站借以尋找合適的犯罪時(shí)機(jī),而巡邏人員在同樣的環(huán)境中對(duì)這樣的行為進(jìn)行檢查和抓捕,而攻擊者綜合考量每個(gè)攻擊目標(biāo)的吸引力,以及其沒有保護(hù)資源布置的情況進(jìn)行攻擊.這樣的模型結(jié)合了博弈論以及犯罪學(xué)的相關(guān)成果,為新型犯罪模型的提出提供了新的思路[68].

6.5 基于歷史數(shù)據(jù)的學(xué)習(xí)

研究工作早期應(yīng)用集中于反恐領(lǐng)域,而隨著研究范圍的擴(kuò)大,研究人員關(guān)注的安全問題也包括了日常發(fā)生的犯罪行為的預(yù)防,比如保護(hù)水產(chǎn)和海洋資源以及大規(guī)模鐵路系統(tǒng)的運(yùn)行等等.這些問題的一個(gè)關(guān)鍵特征是博弈雙方具有重復(fù)而且頻繁的交流,使得相關(guān)部門積累了豐富的數(shù)據(jù).這成為溝通博弈論領(lǐng)域與機(jī)器學(xué)習(xí)領(lǐng)域的一個(gè)契機(jī),亦即使得研究人員能夠在既往收集的數(shù)據(jù)中學(xué)習(xí)得到一個(gè)更能模擬保護(hù)者與環(huán)境以及對(duì)手之間結(jié)構(gòu)和關(guān)系以及收益情況的博弈模型[69].現(xiàn)有安全領(lǐng)域應(yīng)用的博弈收益矩陣多是在領(lǐng)域?qū)＜乙庖娨约皻v史數(shù)據(jù)的建議下確定的,但是在某些情況下,保護(hù)者很難確定攻擊者的收益,而且這些數(shù)值將會(huì)隨著時(shí)間發(fā)生變化,進(jìn)而影響到博弈結(jié)果[70].如何在盡可能少的博弈回合之下學(xué)習(xí)攻擊者的攻擊偏好,進(jìn)而為保護(hù)者設(shè)計(jì)更為有效的保護(hù)策略成為研究關(guān)注的話題.除此之外,對(duì)于動(dòng)態(tài)巡邏過程中可能出現(xiàn)的中斷情況,控制系統(tǒng)如何根據(jù)現(xiàn)有巡邏資源的時(shí)間和空間信息設(shè)計(jì)出新的有效的巡邏過程,修復(fù)中斷使得整個(gè)系統(tǒng)正常運(yùn)轉(zhuǎn)下去[71].這成為在數(shù)據(jù)中學(xué)習(xí)的一個(gè)重點(diǎn)關(guān)注場(chǎng)景.