高巍,羅俊仁,袁唯淋,張萬鵬
面向對手建模的意圖識別方法綜述
高巍1,2,羅俊仁1,袁唯淋1,張萬鵬1
(1. 國防科技大學智能科學學院,湖南 長沙 410073;2. 96843部隊,甘肅 蘭州 730102)
首先介紹了對手建模的幾種不同的類型,引出行為建模中的意圖識別問題;隨后針對意圖識別的過程、分類、主要研究方法、研究展望以及實際應用進行了歸納分析,總結并討論了相關領域取得的最新研究成果;最后指出意圖識別目前存在的不足以及未來的發展方向。
對手建模;意圖識別;目標識別;計劃識別;目標識別設計;計劃識別設計
基于行為觀測序列推斷智能體的目標是近幾年來人工智能和心理學研究者都感興趣的問題。眾多行為建模方法中,人工智能領域關于行為識別與設計得到了廣泛關注。計劃行動與意圖識別(PAIR,plan, activity, and intent recognition)[1]作為一種基于經典識別范式得到了廣泛研究。
目標識別被廣泛應用于人機交互[2]、智能體建模[3]、目標推理[4]、重要基礎設施保護[5]等。一些新的研究包括將意圖識別應用于多智能體行為識別[6]、決策過程中控制意圖的分享與隱藏[7],之間的關系可分為:不可知識別(agnostic/keyhole recognition),其中執行者對觀察者的識別過程不可知;對抗識別,執行者在給定約束下試圖欺騙識別者;有意識別,執行者有意通過隱式通信的方式將自己的行為告知識別者。這些與可解釋性規劃[8]、隱私保護規劃密切相關[7,9],其中任務執行者可根據相關情景主動披露或隱秘混淆其真實目標。
對手建模是在對抗環境下,考慮如何對除自己以外其他參與者進行行為建模,這是一種典型的行為預測技術[10-11]。當前對手建模(OM,opponent modeling)[12]的主要方法有以下幾種(如圖1所示)。
(1)策略重構(policy reconstruction)[13],假設模型有固定的結構,可根據被觀察智能體行為,預測行為概率;可以學習滿足模型結構的任意模型,交互過程中模型持續更新,但這種方式比較復雜,既耗時又耗空間,可細分為條件行為概率模型[14]、案例推理模型[15]、緊致模型表示[16]和效用重構模型[17]。
(2)類型推理(type reasoning)[18-20],假設智能體有多種類型,可根據被觀察智能體行為分析模型的相對可能性,預測行為概率,其中“類型”可以是“黑盒”,如果真實類型存在可快速匹配,但類型空間出錯時,行為預測可能出錯,信念空間不足以分辨類型的真假。
(3)行為分類(action classification)[21],根據不同信息源信息,選擇模型結構,運用機器學習的方法擬合模型參數,預測智能體的類別,可預測模型的多種屬性,許多機器學習方法可能使用,但需要大量數據,模型需要提前計算,實時交互更新很難。
(4)行為識別(action recognition)[1],算法使用層次化規劃庫或域理論(domain theory),預測智能體的目標和可能行為,豐富的規劃庫有助于識別復雜行為,但規劃庫可能不完備,許多識別方法沒有考慮觀察者的存在。
(5)遞歸推理(recursive reasoning)[22-23],遞歸持續推理其他智能體的可能模型,預測其可能行為,可用于分析其他智能體的高層次信念,但遞歸層次難以分析,理性假設太強。
(6)圖模型(graph model)[24-25],使用各種圖模型表示智能體決策過程與偏好,預測智能體的可能行為,圖形化表示有助于計算效率的提高,但對于序列決策過程擴展性不強。
(7)群組建模(group modeling)[26-27],通過分析一群智能體的行動、目標和規劃,預測多智能體的聯合屬性,可抓住一群智能體行為的關聯關系,但智能體之間的不相關性,使群組建模很困難。
(8)集群建模(swarm modeling)[28],通過分析生物群體的行為特征對集群行為模型進行建模。
除以上介紹以外,隱式建模(implicit modeling)[29]、假設檢驗[30]和安全最佳反應[31]也常用于智能體行為建模。

圖1 對手建模分類
Figure 1 Classifications of opponent modeling
當前這類行為建模方法廣泛應用于游戲AI中[32-33]。智能體行為建模面臨的一些問題主要有建模方法的組合、部分可觀情況下的策略重構、安全有效的模型探索、決策因素的有效發覺、算法的高效實現、時變行為的建模、持續行為的建模、開放域多智能體建模、自主模型補全及修正等。
當前研究智能體意圖的兩大模型主要是BDI(信念、愿望和意圖)模型[29]和COI(能力、機會和意圖)模型[5]。意圖識別問題的三大研究要素為環境(或問題域)、識別者(或識別系統)以及被識別者。傳統的行為識別方法通常將被識別者和識別者分別設定為行為執行者與觀察者。
如圖2所示,意圖識別可以看作一個以觀測信息為輸入,在領域知識支撐下圍繞假說空間的推理與計算,以符合觀測的假說(包括目標與計劃)及其概率分布為輸出的過程。
根據環境(或問題域)的類型,可以分為確定性識別和隨機性識別。根據執行者和觀察者之間的競合關系,可以分為:不可知識別,其中執行者不知道觀察者的識別過程;有意識別,執行者有意通過隱式通信的方式將自己的行為告知識別者;對抗識別,執行者在給定約束下試圖欺騙識別者[1,5]。
意圖識別作為“計劃行動意圖識別”的子問題,與計劃識別、行動識別[34]和目標識別緊密相關。“計劃行動意圖識別”有許多共同之處,為了充分發揮不同類型識別方法的作用,Freedman等[35]提出“計劃行動意圖識別”的統一框架。根據研究問題的層次劃分,當前的研究大多把行動識別看作底層識別,把計劃識別看作包括連續行動和目標的識別,把目標識別僅看作識別行動目標。其實,當智能體的行動與具體特定目標關聯時,意圖識別即目標識別。當智能體處于確定性環境(或問題域)時,其選擇的行動是依經典規劃理論得出與特定目標關聯的計劃,包含為了達到目標而執行全部行動和行動間的關系,意圖識別即計劃識別。當智能體處于隨機性環境(或問題域)時,其選擇的行動是依序貫決策理論或博弈理論得出與特定目標相關聯的行動,意圖識別即目標識別。本文主要研究目標識別與計劃識別。

圖2 意圖識別行為建模框架
Figure 2 Intention recognition behavior modeling framework
本文研究假定執行意圖識別過程中,觀察者充當識別者。行動識別主要識別底層行為,計劃識別主要識別行為的中上層,目標識別主要識別行為的最終目標。
當前意圖識別主要有以下三大范式。
(1)基于規劃理論的識別范式。這是一種典型的符號式確定性意圖識別方法,其中可以用分層任務網絡(HTN,hierarchical task network)、命題語法、與或樹的方式來構建執行者的計劃庫或直接使用域理論來表征執行者的行為。基于規劃的計劃識別方法(PRAP)[36-37]是一種利用逆向推理識別意圖的方法,其相應變體如基于規劃的目標識別(GRAP)[38]、基于規劃的模型識別(MRAP)[39]均是基于域理論來進行行為識別的。這類方法大多依賴于計劃庫或域理論生成被觀察到的智能體為實現其目標的計劃假設空間[1]。此類方法在計算上是有效的,但需要豐富的領域知識,并對觀察到的智能體的偏好做出強有力的假設。
(2)基于效用理論的識別范式[5,38,40]。其中,基于部分可觀馬爾可夫決策過程(POMDP)的識別方法[38],建立了不確定條件下的序貫決策模型,為隨機環境意圖識別提供了方法;而基于博弈理論的識別方法[5,40],使用一種生成式方法[41],為對抗博弈場景下意圖識別與應對規劃提供了新的模型與求解方法。
(3)基于學習理論的識別范式。其中,策略識別方法[42-43]、逆強化學習[44-46]和正則化強化學習[47-48]方法均可用于學習行為模型、基于代價的深度學習方法[49-52],可用于預測后續行動。
3.3.1 基于代價的目標識別
目標識別是識別目標驅動智能體行動策略的一種主要方法,這種方法主要著眼于智能體的目標域相關問題,相較于計劃識別中注重過程信息,目標域問題將過程隨機化,重點關注目標的狀態,當前關于目標域攻防對抗問題的相關研究已經取得相當多的成果。
目標識別作為“計劃行動意圖識別”的子問題,廣泛應用于環境部分可觀的決策問題,其中觀察者需要構造執行者的決策行動模型,基于不完全觀測序列識別執行者的行動目標。
目標識別通過觀察智能體的行為來確定其意圖的問題,涉及對最終或“最高層次”目標感興趣的配對問題,而不是必須在實現計劃或次級目標的過程中進行談判的計劃或次級目標[53]。
如圖3所示,識別者對所感知的智能體行為進行分析,確定智能體的目標。智能體以初始狀態(標記為“開始”)進入場景,并執行指向預先確定目標的一系列操作(在這種情況下,由圖中標有“目標”的下部方框表示),根據感知到的觀察序列(不一定完整或準確)分析智能體的目標。此任務與計劃識別緊密相關,但又不同于計劃識別,后者旨在確定智能體要遵循的完整計劃以實現其目標。
根據時效性要求可劃分為離線目標識別和在線目標識別(如表1所示)。在離線目標識別的觀測序列中,雖然本身可能會有很多噪聲或者是不完整的,但觀測序列會提前顯示出來。相反,在在線目標識別中,觀測值是逐步顯示的,而必須在每一次額外的觀察之后做出假設,且不知道哪一次觀察是最后一次觀察。當前,離線目標識別研究比較多[54],近些年也出現了一些在線目標識別相關方法[55-57]。

圖3 目標識別過程
Figure 3 Target recognition process

表1 目標識別模型屬性
當前基于代價的目標識別模型主要有:R&G (Ramirez and Geffner)模型[36],可用于與任務規劃相關的經典離線目標識別方法;M&S(Masters and Sardina)模型[58],可用于連續和離散空間與路徑規劃相關的離線目標識別方法;V&K (Vered and Kaminka)模型[55],可用于連續和離散空間與運行規劃相關的在線目標識別方法。
R&G方法:Ramirez和Geffner介紹了第一個基于計劃的目標識別(R&G)方法。給定理論和觀測序列,R&G引入了一種考慮觀測序列的修正理論。




事實證明,使用M&S方法可以顯著縮短計算時間,同時具有與R&G方法相似的性能。

3.3.2 基于計劃度量的目標識別
在規劃理論中,landmark是指在每一個有效的計劃中,為了從最初的狀態達到一個特定的目標,必須在某一點上都是正確的事實[60]。
Vered 和 Kaminka 進行了一系列關于連續域上的在線識別工作[55-57],考慮與路線規劃以外的運動規劃類型有關的目標識別,如繪圖分析。同時,將目標識別描述為“目標鏡像”(即人類對觀察的移情反應)[55],即人類在觀察到的情況下想象自己,并假定被觀察的人有興趣發現最符合人類推理的“啟發式”(即概率分布)。在關注在線目標識別的機制時,Vered 和 Kaminka通過重復使用“路徑前綴”(即到目前為止觀察到的路徑)的計算代價來節省時間,而不是重復計算其全部代價,進而提出了兩種新的機制,以幫助減少計算代價[56]。在在線目標識別中,對觀測數據進行增量處理,在收到新的觀測結果后,該系統首先檢查對手是否在接近“最有可能”的目標。如果是,則跳過重新計算;如果不是,系統將檢查自上一次觀測以來對手的行為軌跡(即運動角度)。如果對手以大于某個給定閾值的角度偏離了一個目標,則該目標將從候選集中剪枝,進行未來概率計算。Vered 和Kaminka將目標鏡像與landmark的使用結合起來[57],為離散域和連續域提供在線解決方案,通過每個目標的“landmark完成”與“總landmark”的比率來生成概率分布。
3.3.3 計劃識別
計劃識別是許多領域中普遍存在的任務,包括自然語言、多智能體系統和輔助認知[61-63]。


其中,選取的行動序列滿足由動作組成的觀察序列。例如,動作序列π={,,,,,}滿足觀察序列1= {,,}和2= {,,},但不是3= {,,}。這可以借助將中的觀察索引映射為中的動作索引的函數來形式化。
3.4.1 目標識別設計
目標識別設計(GRD, goal recognition design)由Keren、Gal和Karpa在2014年提出[60],其目的是通過離線執行目標識別任務來降低在線目標識別任務的復雜性,修改智能體操作的底層環境。目標識別設計的目的是找到最小的一組底層環境的修改,迫使智能體盡早揭示其目標。這個問題本身與許多相同的目標識別應用程序相關,因為通常可以很容易修改底層環境。
通常情況下,目標識別設計問題有兩個組成部分:目標識別效果的度量;可能對環境造成的設計變化的模型。
目前,目標識別設計模型主要包括確定性的目標識別設計與隨機性的目標識別設計,表2總結了現有目標識別設計模型的概括、度量和可能的設計。
(1)確定性目標識別設計
目標識別設計主要分析如何更好地改造執行者所處的環境,使執行者的目標更早暴露出來,其中最壞情況顯著性(WCD,worst case distinctiveness)作為衡量目標模糊性度量,用來指導離線的環境重設計,它是指智能體在目標被揭示之前可以執行的最大動作數。

表2 現有目標識別設計模型屬性
最初,Keren在2014年提出的目標識別設計問題是在以下3個假設下進行的:
①系統中的智能體行為將是最優的(即智能體將沿著最短的路徑移動到其目標);
②智能體是確定性的;
③環境是完全可觀的(即智能體的狀態和行為都是可觀的)。
進一步,Keren等于2015年將GRD問題擴展到行動部分可觀測[67]、Agent行動非最優[66]等情況,從而對GRD問題領域進行了豐富和拓展。
限制智能體可以執行的一組可用操作是改進模型的一種可行性方法。為了保持用戶的舒適度,改進的模型保留所有目標的原始解決方案成本。另外,希望在最大限度地減少WCD的同時減少引入的更改并遵守可能指定的任何設計約束。
此外,針對現有 GRD 問題的求解過于依賴經典規劃,Son等[65]在2016 年提出基于答案集編程(ASP,answer set programming)描述性框架的求解方法,實驗證明基于ASP的GRD問題求解不僅具有良好的擴展性,而且在效率上較傳統方法能夠達到3個數量級的升躍。
然而,許多實際應用程序必須考慮各種形式的不確定性。特別是目標識別系統通常會由于缺少合適的傳感器、傳感器覆蓋范圍不足、傳感器故障、測量結果不準確等而導致可觀察性降低。在完全可觀察的設置中,只有在以下情況下才會妨礙目標識別:智能體的行為可能符合多個目標,當可觀察性不完整時,即使智能體的行為是特定于目標的,智能體的目標也可能無法識別。
Keren等在2016年將WCD的概念擴展到部分可觀的環境[67],其基礎是欺騙性智能體能夠控制哪些行為“發出”觀測結果。在這種假設下,智能體可能保持一條模糊的路徑,以獲得更大的距離。同樣,距離是使用最優(或“有界最優”)路徑從初始狀態計算的。這一策略本質上是一種蓄意欺騙,其特點是“隱私保護”。
(2)隨機性目標識別設計
在現實世界中處處存在著隨機性和局限性,這導致智能體無法控制其行動的結果,同時,觀察者受到傳感器數量和質量的限制。
Wayllaced等在初始的GRD基礎上,提出了隨機目標識別設計(S-GRD)[71],同時,提出了名為“預期情況顯著性”(ECD,expected-case distinctiveness)的新指標[72],即根據所有目標成為真正目標的可能性來衡量可能的目標。
該框架還擴展了以下假設:智能體行為不再可觀察,智能體狀態只是部分可觀察到的。這種放松是以實際應用為動力的。諸如智能體導航之類的操作,智能體操作是不可觀察的,但其狀態(當前位置)可以是(至少部分)觀察到的。智能體狀態的部分可觀測性是由于傳感器分辨率低(如GPS),可能導致幾個附近的狀態彼此無法區分。最后,將一種新類型的傳感器精化看作改進某些狀態可觀的可能設計[73],同時在此基礎上,進行對傳感器精化、搜索空間的剪枝和對部分可觀的S-GRD的ECD度量的推廣。
S-GRD算法使用增強MDP和Ⅵ類算法,通過從增強初始狀態到任何增強目標的最大期望成本來計算WCD。


Ⅵ的局限性在于,即使某些狀態的預期成本已經收斂,它也會在每次迭代中更新每個狀態。拓撲值迭代(TVI)[75]通過僅在一個強連接圖(SCC)中重復更新狀態直到其值收斂,然后在另一個SCC中更新狀態來解決此限制。由于SCC形成有向無環圖,SCC中的狀態僅影響其之前的狀態。因此,通過以相反的拓撲排序順序選擇SCC,不再需要考慮狀態在先前迭代中已經收斂的SCC。
3.4.2 計劃識別設計
目標識別設計是以一種易于識別智能體目標的方式設計領域的問題。而計劃識別設計(PRD,plan recognition design)是一種可以更快地識別智能體計劃的設計域問題。該問題由Mirsky等在2017正式提出[76],計劃識別設計問題是將原GRD問題推廣到降維區域,使用層次計劃(GRD-PL),該問題是利用計劃庫設計領域的任務,以便于快速識別智能體的計劃。GRD可以幫助更快地解釋智能體試圖實現的目標,而PRD則有助于更快地理解智能體如何實現其目標。在GRD范式的基礎上,這兩個新問題(GRD-PL和PRD)都可以采用最壞情況顯著性(WCD)進行量化。
帶有計劃庫的目標識別設計(GRD-PL):Ramirez和Geffner[77]提供了一種將計劃庫(表示為AND-OR樹)編譯為STRIPS表示的方法。從理論上講,可以通過解決STRIPS空間中的相應GRD問題來解決GRD-PL問題。但是采用該方法得到的STRIPS表示的復雜度可能比較高。因此,將GRD問題擴展到使用計劃庫進行域的表示作為一種新的方法來解決這類問題。即使WCD計算適應于關于層次計劃的推理以及如何在不限制智能體實現其可能目標的情況下,以最小化其WCD的方式更改給定域。在這種情況下,WCD是使用搜索樹來計算的,該樹在顯示其計劃之前找到智能體可以執行的最長操作序列。
計劃識別設計:計劃識別設計是一種可以更快地識別智能體的計劃的設計域問題。在GRD問題中,該設計試圖將所需的觀察次數最小化,直到對智能體的目標不存在任何含糊之處;而PRD則試圖將觀察的數量降到最低,直到對智能體的完整計劃沒有任何含糊之處。Mirsky等[78]定義了一個新的度量,即最壞的方案區分(WCPD)。
WCPD的定義為:在最壞的情況下,能得到智能體的計劃的觀察數量。形式上,對于每兩個計劃1,2,它們的WCPD計算公式為

運行示例中計劃庫的WCPD為1,因為在觀察運行之后,對于智能體的計劃仍然存在模糊。請注意,一個額外的觀察(如踢)將明確地識別該智能體的計劃。而計劃識別設計問題就是解決計劃庫的WCPD最小化的問題。
GRD、PRD與GRD-PL之間的比較如表3所示。
近年來,針對不完美域模型(imperfect domain model)的目標識別方法[79-80]、針對新應用場景的主動目標識別[81]、連續空間的目標識別[58]、非理性智能體的目標識別[59]相繼提出。除了上文中指出的問題和局限性外,在未來研究中,需要探索多種途徑來擴展在不完美離散域模型上的目標識別工作。目前可以從以下兩個設想出發進行探索:①使用一個傳播的RPG來解釋不完美域模型,如文獻[82]采用信息來構建規劃啟發式,用于對不完美域模型進行規劃;②文獻[83]開發了一種基于規劃痕跡的不完美域模型細化方法,采用基于信息的規劃痕跡和推斷信息的方法獲取不完美域模型。
在實際應用中,意圖識別不是最終目的。觀察者的最終目的是在識別行動者真實意圖的前提下,對行動者進行協作或者阻礙。對抗條件下,觀察者可以采用更為實用的攔截措施來干擾執行者的欺騙行為,控制目標識別過程。除了干擾對方的欺騙性規劃過程,對抗雙方也能夠試圖控制目標識別的過程,使規劃具備可解釋性(混淆性、欺騙性、含糊性、隱私性和安全性)以達到干擾對方的意圖識別過程或者防止隱私泄露的目的。
對抗環境下的競合關系是意圖模糊與欺騙的重要因素。同時,對手的欺騙性行為對意圖識別過程的影響是未來開展意圖識別的首要需求。從反制的角度,意圖識別方法研究自然而然地引入了被識別者的欺騙性路徑規劃問題。目前,針對被識別者的欺騙路徑規劃問題,考慮其主動欺騙行為對識別效果、遲滯識別時機等方面的影響。同時,欺騙概念可以從路徑規劃領域延伸到一般的經典任務規劃問題,如采用概率意圖識別算法評估欺騙量級,并提出一個新的優化模型,在資源約束下最大化被識別者的規劃欺騙性。因此,對抗環境下的意圖識別與被識別者的欺騙性任務規劃方法研究對無人作戰、軍事指揮與控制具有一定價值,也是對現有對手建模與欺騙行為建模的重要補充。

表3 GRD、PRD、GRD-PL之間的比較
目前,一種新型的自動方法可以用來對抗RTS中的對手策略[84],它結合了目標識別功能以推斷對手的目標;landmark的計算以識別可用于阻止對手達成目標的子目標;傳統的自動計劃以生成阻礙對手達成目標的計劃。解決人工智能應用于RTS游戲的主要挑戰之一的技術:從無到有綜合計劃反對對手戰略。為了在實時環境中正常工作,當前的研究主要在已知域無關反規劃算法的基礎上進行了兩項修改:①使用代價估計而不是在目標識別中進行計劃計算;②選擇任何地方的對手可以被阻擋,而不是推理最好的停止在哪里阻止它。
隨著人類感知研究的新興領域興起,意圖識別開始與另一個新興領域——可解釋性人工智能重疊[85]。2017年,DARPA發起“可解釋人工智能”項目研究,以此探索可以使自主系統對其行為進行更好解析的技術。當前,可解釋性人工智能與合法人工智能、負責任人工智能、隱私保護人工智能是可信任人工智能的主要內容。針對規劃決策領域可解釋性研究,主要關注可解釋規劃、可解釋性決策算法。對抗環境下,智能體的行為模型具備多模態屬性,可解釋行為(模型也得到了廣泛關注。文獻[86]對具有人類意圖的智能體和人在回路中的智能體的可說明行為進行了歸納總結。考慮合作情景時,智能體的目標和規劃必須同時具備明確性、透明性、解釋性和預測性[87]。考慮對抗情景時,智能體的目標和規劃必須具備混淆性、含糊性、隱私性和安全性。近年來,為實現多模態的規劃決策方法,控制信息披露和隱藏的規劃方法、控制目標混淆或明確的規劃方法和控制意圖分享與隱藏的決策方法相繼被提出。一些新的研究包括將意圖識別應用于多智能體行為識別中[6]、決策過程中控制意圖的分享與隱藏[7]。這些與可解釋性規劃[8]、隱私保護規劃密切相關[7,9],其中任務執行者可根據相關情景主動披露或隱秘混淆其真實目標。
在復雜的戰場環境中,智能體之間通常采用協同的方式實現共同的目標,即聯合意圖。考慮到一個智能體的行為對與其協同作戰的智能體產生的影響,針對多智能體的聯合意圖識別比單個智能體的意圖復雜和困難更加符合實際的作戰需求。多智能體意圖識別的重點和難點是基于統一的建模框架來描述智能體的協同行為。如果識別者具備領域背景和識別對象行為習慣的相關知識,那么通常可使用顯示建模的方式,即采用一個復雜的有向圖模型對各要素間的依賴關系進行詳細建模。
多智能體計劃識別(MAPR)[83,88-89]是計劃、活動和意圖識別(PAIR)研究主題的一個子集[1],MAPR研究的重點是觀察單個智能體的行為,并從這些行為中推斷哪些團隊中的智能體進行了工作,以及團隊的目的[90]。目前大多數MAPR解決方案是識別特定領域的活動,依賴于將觀測結果與人類生成的庫相匹配,并且預先分析完整結構的同步痕跡。
CADET系統是一個集中在旅級地面行動的戰斗規劃系統,其中重要一環就是對抗推理和對抗規劃。DARPA從2004年開始籌建實時對抗情報和決策(RAID,real-time adversarial intelligence and decision-making)計劃[91],關注如何將敵人在軍事行動中的對抗行為納入規劃考慮范疇。
RAID系統面臨許多問題,紅藍雙方的行動有很強的相互依賴關系,一方對另一方的資產和行動知識不可避免地受到限制。觀察和觀察的解釋都有一定限度的誤差和錯誤。除了局部的、延遲的甚至是錯誤的觀察外,對于戰場的知識也會受到有目的性的、持續的、攻擊性的、智能的隱藏和欺騙。由于文化上、條令條例上和心理上的影響,作戰規劃時往往僅僅考慮最危險(通常是敵方理論上最優的)的作戰行動序列。然而實際最可能發生的作戰行動序列很大限度上會受到人為因素的影響,甚至可能與理論上的最危險策略不同。以城市戰斗為例,復雜的城市地理環境使戰斗呈現高密度同時有碎片化的威脅和機遇[91];地形由于人的參與也是動態變化的;同時戰場上的非戰斗人員必須明確納入考慮范圍,并最小化其附加損害。除了火力和機動需要考慮之外,其他的如情報收集、后勤等都與火力機動緊密耦合,這些都充滿著對抗性和不確定性。
即時戰略(RTS,real-time strategy)游戲是一種對復雜戰場環境模擬的仿真手段,在仿真過程中,己方人員指示己方實體通過獲取資源、構造結構,來摧毀對手的建筑從而贏得比賽。RTS 游戲是對作戰仿真的簡化,因此,可以作為即時對抗規劃、不確定條件下的決策支持等方法的試驗床。由于龐大的狀態空間、動態的對抗環境,以及對決策時效性的高度要求,RTS 游戲的研究使 AI 研究人員面臨極大的挑戰。尤其是在對指揮員智能體建模時,需要考慮到全局信息。在廣泛的研究范圍中,作為實時對抗性規劃和不確定性決策的基本問題,人工智能規劃已經成為一個至關重要的研究領域。
RTS游戲由于存在許多具有挑戰性的子問題,如目標推理、策略構建、學習等,已被廣泛用于AI研究。應用于RTS游戲的AI的主要挑戰之一是自主開發、綜合考慮對手觀察結果的計劃。該任務可以看作對策問題。
對抗規劃劃分為對抗推理和對抗計劃兩個相互影響的部分,來表示在一個對抗環境下,一方通過計算求解對手的決定性狀態、意圖和行為并盡全力反制敵方的行動和計劃的動態規劃過程。這個領域的子問題包括信念和意圖識別、對手策略預測、規劃識別、欺騙計劃發現、欺騙計劃和計劃生成等。從工程角度來講,對抗計劃的研究覆蓋了廣泛的實際問題領域,除了即時戰略游戲這類娛樂性策略游戲之外,還可以應用在軍事計劃和指揮、軍事和外交情報獲取、反恐和國土安全、信息安全、仿真和訓練系統、實用機器人等領域。
目前,規劃算法應用于機器人、航空航天和工業工程等領域,其目的是找到困難問題的優化解決方案。這些問題可能涉及數千個參數和相互作用,不可能通過手工獲得一個解決方案。例如,考慮一個包含數千臺具有大量數據的服務器的分布式計算基礎設施,規劃器將被用來安排數據遷移、啟動新的實例、處理數據、以最有效的方式分配資源。通常,目標是在所有服務器上有一個相當分布的工作負載。顯然,找到最優的計劃(即成本最低的計劃)并不是一件容易的事情。
規劃器是確定性的,意味著可以產生相同的輸入(目標、初始狀態等)。對手可以從這些輸入? 輸出對進行學習,進而得到行為模型。這樣對手可以在給定輸入時,以高概率預測出輸出計劃中的關鍵動作。當計劃人員針對分布式計算調度問題執行任務時,對手可以推斷出計劃的哪一步至關重要。即如果避免了那一步,資源或計算位置將產生最大的負面影響。這意味著對手可以識別出最感興趣的服務器或攻擊的鏈接,并且采取了相應的措施。
如今,通常智能體在某處想要使用計劃系統找到自己的位置和自己的路線是一件很容易的事(應用GPS)。路徑規劃器用于找到從兩個(或多個)點導航的最佳方法,其根據每個路徑片段的代價(即速度限制、路程等)輸出一組方向。考慮在大規模使用計劃系統而沒有經過人工驗證的情況下應用的所有問題(機場、數據中心、生產線等)。確定計劃算法可能使用的關鍵目標,可以提供發動攻擊的手段,從而增加所需的資源(時間、計算能力、能源等)或阻止規劃器找到任何合理的計劃。
當前,許多智能系統使用固定通信輸入或預設響應中至少一個與其他系統進行交互,從而導致僵化的交互體驗以及為系統開發各種場景的大量努力。固定輸入限制了用戶的自然行為,從而限制了溝通,并且預設響應會阻止系統適應當前情況,除非專門實施。相反,閉環交互專注于動態響應,這些動態響應基于對用戶感知活動的解釋來說明用戶當前正在執行的操作。采用閉環交互的智能體還可以監視其交互,以確保用戶按預期進行響應。通過演示實現了一個輔助交互式智能體,該智能體集成了計劃、計劃識別和意圖識別,以預測用戶要完成的任務并自主決定響應這些預測要采取的措施。
當交互式體驗開始時,輔助智能體將沒有用戶模型。這也意味著智能體不知道用戶想要做什么,必須通過觀察才能做出明智的決定。用戶將在模擬環境中玩回合制游戲,可以自由地從一組完成標準中進行選擇,成功滿足其中任何一個條件都將贏得比賽。用戶將在第一個回合中采取行動,這為智能體提供一些有關它們打算完成哪些事件的信息。當智能體收到足夠的信息來決定如何做出響應,則智能體將在第二輪行動。由于演示的模擬游戲設置,用戶輸入則為簡單的離散按鈕按下和鼠標點擊,不需要任何原始傳感器數據。因此,這種實現只是將活動識別作為從輸入到游戲相應動作的映射來執行。計劃和意圖識別組件收到這些操作后,通過觀察概率識別計劃(R&G方法)[37]進行識別,該算法運行生成規劃器來模擬用戶解決各種問題。
本文對對手建模進行了簡要的介紹,并針對行為建模中的目標識別、計劃識別、目標識別設計、計劃識別設計共4方面現有的研究方法進行了詳細的總結與分析;同時,給出在不完美域模型、對抗規劃、意圖識別控制與可解釋人工智能、多智能體意圖識別等方面在意圖識別領域的研究展望;針對軍事輔助決策、即時戰略游戲、對抗規劃、人機協同的典型應用分析,指出了這一研究工作的實際意義。
盡管Keren等在最新的綜述中總結了當前目標識別設計方面的主要工作[92],現有的研究工作極大地提升了目標識別的速度與正確率,但這些工作仍然是不完善的,仍然有新的應用領域以及改進方向為研究工作提出挑戰。這些挑戰多數來自現有的有限計算能力、人類行為的不確定性以及現實場景中的特殊性質。
[1] SUKTHANKAR G. Plan, activity, and intent recognition: theory and practice[R]. 2014.
[2] CHAKRABORTI T, KAMBHAMPATI S, SCHEUTZ M, et al. AI challenges in human-robot cognitive teaming[J]. arXiv preprint arXiv:1707.04775, 2017.
[3] ALBRECHT S V, STONE P. Autonomous agents modelling other agents: a comprehensive survey and open problems[J]. Artificial Intelligence, 2018, 258: 66-95.
[4] HEINZE C. Modelling intention recognition for intelligent agent systems[R]. 2004.
[5] LE GUILLARME N. A game-theoretic planning framework for intentional threat assessment[D]. Thèse de doctorat: Université de Caen, 2016.
[6] BIGELOW D. Intent recognition in multi-agent domains[M]. University of Nevada, Reno, 2013.
[7] STROUSE D J, KLEIMAN-WEINER M, TENENBAUM J, et al. Learning to share and hide intentions using information regularization[C]//Advances in Neural Information Processing Systems. 2018: 10249-10259.
[8] CHAKRABORTI T, KULKARNI A, SREEDHARAN S, et al. Explicability legibility predictability transparency privacy security the emerging landscape of interpretable agent behavior[C]//Proceedings of the International Conference on Automated Planning and Scheduling. 2019: 86-96.
[9] KEREN S, GAL A, KARPAS E. Privacy preserving plans in partially observable environments[C]//IJCAI. 2016: 3170-3176.
[10] WRIGHT J R. Modeling human behavior in strategic settings[D]. Columbia: University of British Columbia, 2016.
[11] PLONSKY O, APEL R, ERT E, et al. Predicting human decisions with behavioral theories and machine learning[J]. arXiv preprint arXiv:1904.06866, 2019.
[12] BORGHETTI B J . Opponent modeling in interesting adversarial environments[M]. Minnesota: University of Minnesota, 2008.
[13] BROWNE C B, POWLEY E, WHITEHOUSE D, et al. A survey of monte carlo tree search methods[J]. IEEE Transactions on Computational Intelligence and AI in Games, 2012, 4(1): 1-43.
[14] CHAKRABORTY D, STONE P. Multiagent learning in the presence of memory-bounded agents[J]. Autonomous Agents and Multi-Agent Systems, 2014, 28(2): 182-213.
[15] KOLODNER J. Case-based reasoning[M]. Morgan Kaufmann, 2014.
[16] CARMEL D, MARKOVITCH S. Learning models of intelligent agents[C]//AAAI/IAAI. 1996: 62-67.
[17] BAARSLAG T, HENDRIKX M J C, HINDRIKS K V, et al. Learning about the opponent in automated bilateral negotiation: a comprehensive survey of opponent modeling techniques[J]. Autonomous Agents and Multi-Agent Systems, 2016, 30(5): 849-898.
[18] BARRETT S, STONE P, KRAUS S, ET al. Teamwork with limited knowledge of teammates[C]//Twenty-Seventh AAAI Conference on Artificial Intelligence. 2013.
[19] ALBRECHT S V, CRANDALL J W, RAMAMOORTHY S. An empirical study on the practical impact of prior beliefs over policy types[C]//Twenty-Ninth AAAI Conference on Artificial Intelligence. 2015.
[20] ALBRECHT S V, RAMAMOORTHY S. On convergence and optimality of best-response learning with policy types in multiagent systems[J]. arXiv preprint arXiv:1907.06995, 2019.
[21] SCHADD F, BAKKES S, SPRONCK P. Opponent modeling in real-time strategy games[C]//GAMEON. 2007: 61-70.
[22] WEN Y, YANG Y, LU R, et al. Multi-agent generalized recursive reasoning[J]. arXiv preprint arXiv:1901.09216, 2019.
[23] WEN Y, YANG Y, LUO R, et al. Probabilistic recursive reasoning for multi-agent reinforcement learning[J]. arXiv preprint arXiv:1901.09207, 2019.
[24] DOSHI P, ZENG Y, CHEN Q. Graphical models for interactive POMDPs: representations and solutions[J]. Autonomous Agents and Multi-Agent Systems, 2009, 18(3): 376.
[25] TORKAMAN A, SAFABAKHSH R. Robust opponent modeling in real-time strategy games using bayesian networks[J]. Journal of AI and Data Mining, 2019, 7(1): 149-159.
[26] MAO W, GRATCH J, LI X. Probabilistic plan inference for group behavior prediction[J]. IEEE Intelligent Systems, 2012, 27(4): 27-36.
[27] HAUSKNECHT M, MUPPARAJU P, SUBRAMANIAN S, et al. Half field offense: an environment for multiagent learning and ad hoc teamwork[C]//AAMAS Adaptive Learning Agents (ALA) Workshop. 2016.
[28] ?O?I? A. Learning models of behavior from demonstration and through interaction[D]. Technische Universit?t, 2018.
[29] HERNANDEZ-LEAL P, ZHAN Y, TAYLOR M E, et al. Efficiently detecting switches against non-stationary opponents[J]. Autonomous Agents and Multi-Agent Systems, 2017, 31(4): 767-789.
[30] ALBRECHT S V, RAMAMOORTHY S. Are you doing what i think you are doing? criticising uncertain agent models[J]. arXiv preprint arXiv:1907.01912, 2019.
[31] WANG Z, BOULARIAS A, MüLLING K, et al. Balancing safety and exploitability in opponent modeling[C]//Twenty-Fifth AAAI Conference on Artificial Intelligence. 2011.
[32] STANESCU A M. Outcome prediction and hierarchical models in real-time strategy games[R]. 2019.
[33] MOURAD M, AREF M, ABD-ELAZIZ M. Opponent models pre-processing in real-time strategy games[J]. International Journal of Intelligent Computing and Information Sciences, 2016, 16(3): 37-45.
[34] SUKTHANKAR G R. Activity recognition for agent teams[R]. 2007.
[35] FREEDMAN R G, ZILBERSTEIN S. A unifying perspective of plan, activity, and intent recognition[C]//Proceedings of the AAAI Workshops: Plan, Activity, Internet Recognition. 2019: 1-8.
[36] RAMíREZ M, GEFFNER H. Plan recognition as planning[C]//Twenty-First International Joint Conference on Artificial Intelligence. 2009.
[37] SOHRABI S, RIABOV A V, UDREA O. Plan recognition as planning revisited[C]//IJCAI. 2016: 3258-3264.
[38] PEREIRA R F, OREN N, MENEGUZZI F. Landmark-based approaches for goal recognition as planning[J]. arXiv preprint arXiv:1904.11739, 2019.
[39] AINETO D, JIMéNEZ S, ONAINDIA E, et al. Model recognition as planning[C]//Proceedings of the International Conference on Automated Planning and Scheduling. 2019: 13-21.
[40] ANG S, CHAN H, JIANG A X, et al. Game-theoretic goal recognition models with applications to security domains[C]//International Conference on Decision and Game Theory for Security. 2017: 256-272.
[41] LE GUILLARME N, MOUADDIB A I, LEROUVREUR X, et al. A generative game-theoretic framework for adversarial plan recognition[C]//JFPDA 2015. 2015.
[42] LI J, REN T, SU H, et al. Learn a robust policy in adversarial games via playing with an expert opponent[C]//Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems. 2019: 2096-2098.
[43] ?O?I? A. Learning models of behavior from demonstration and through interaction[D]. Technische Universit?t, 2018.
[44] ZIEBART B D. Modeling purposeful adaptive behavior with the principle of maximum causal entropy[D]. Figshare, 2010.
[45] TASTAN B. Learning human motion models[C]//Eighth Artificial Intelligence and Interactive Digital Entertainment Conference. 2012.
[46] GAURAV S, ZIEBART B. Discriminatively learning inverse optimal control models for predicting human intentions[C]//Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems. 2019: 1368-1376.
[47] LI X, YANG W, ZHANG Z. A unified framework for regularized reinforcement learning[J]. arXiv preprint arXiv:1903.00725, 2019.
[48] TIAN Z, WEN Y, GONG Z, et al. A regularized opponent model with maximum entropy objective[J]. arXiv preprint arXiv:1905.08087, 2019.
[49] MAYNARD M, DUHAMEL T, KABANZA F. Cost-based goal recognition meets deep learning[J]. arXiv preprint arXiv:1911.10074, 2019.
[50] WOOKHEE M, YOUNG E H, ROWE J. Deep learning-based goal recognition in open-ended digital games[C]//Tenth AAAI Conference on Artificial Intelligence & Interactive Digital Entertainment. 2014.
[51] DUHAMEL T, MAYNARD M, KABANZA F. A transfer learning method for goal recognition exploiting cross-domain spatial fea-tures[J]. arXiv preprint arXiv:1911.10134, 2019.
[52] THIBAULT D, MAYNARD M, KABANZA F. Imagination-augmented deep learning for goal recognition[J]. arXiv preprint arXiv:2003.09529v1, 2020.
[53] BLAYLOCK N, ALLEN J. Fast hierarchical goal schema recognition[C]//Proceedings of the National Conference on Artificial Intelligence. 2006: 796.
[54] VERED M, KAMINKA G A. Heuristic online goal recognition in continuous domains[C]//International Joint Conference on Artificial Intelligence. 2017: 4447-4454.
[55] VERED M, KAMINKA G A, BIHAM S. Online goal recognition through mirroring: Humans and agents[C]//The Fourth Annual Conference on Advances in Cognitive Systems. 2016.
[56] VERED M, KAMINKA G A. Online recognition of navigation goals through goal mirroring[C]//Proceedings of the 16th Conference on Autonomous Agents and Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems. 2017: 1748-1750.
[57] VERED M, PEREIRA R F, MAGNAGUAGNO M C, et al. Towards online goal recognition combining goal mirroring and landmarks[C]//AAMAS. 2018: 2112-2114.
[58] MASTERS P, SARDINA S. Cost-based goal recognition for the path-planning domain[C]//IJCAI. 2018: 5329-5333.
[59] MASTERS P, SARDINA S. Goal recognition for rational and irrational agents[C]//Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems. International Foundation for Autonomous Agents and Multiagent Systems. 2019: 440-448.
[60] HOFFMANN J, PORTEOUS J, SEBASTIA L. Ordered landmarks in planning[J]. Journal of Artificial Intelligence Research, 2004, 22: 215-278.
[61] SCHMIDT C. SRIDHARAN N, GOODSON J. The plan recognition problem: an intersection of psychology and artificial intelligence[J]. Artificial Intelligence, 1978, 11: 45-83.
[62] COHEN P R, PERRAULT C R, ALLEN J F. Beyond question answering[M]//Strategies for Natural Language Processing. Lawrence Erlbaum Associates, 1981.
[63] PENTNEY W, POPESCU A, WANG S, KAUTZ H, et al. Sensor-based understanding of daily life via large-scale use of common sense[C]//Proceedings of AAAI. 2006.
[64] KEREN S, GAL A, KARPAS E. Goal recognition design[C]// Twenty-Fourth International Conference on Automated Planning and Scheduling. 2014.
[65] SON T C, SABUNCU O, Schulz-Hanke C, et al. Solving goal recognition design using ASP[C]//Thirtieth AAAI Conference on Artificial Intelligence. 2016.
[66] KEREN S, GAL A, KARPAS E, et al. Goal recognition design for non-optimal agents[C]//National Conference on Artificial Intelligence. 2015: 3298-3304.
[67] KEREN S, GAL A, KARPAS E. Goal recognition design with non-observable actions[C]//Thirtieth AAAI Conference on Artificial Intelligence. 2016.
[68] KEREN S, GAL A, KARPAS E. Strong stubborn sets for efficient goal recognition design[C]//Twenty-Eighth International Conference on Automated Planning and Scheduling. 2018.
[69] SARAH K, AVIGDOR G, EREZ K. Goal recognition design in deterministic environments[J]. Journal of Artificial Intelligence Research, 2019, 65: 209-269.
[70] KEREN S, PINEDAL, GAL A, et al. Equi-reward utility maximizing design in stochastic environments[C]//Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence. 2017: 4353-4360.
[71] WAYLLACE C, HOU P, YEOH W, et al. Goal recognition design with stochastic agent action outcomes[C]//IJCAI. 2016.
[72] WAYLLACE C, HOU P, YEOH W. New Metrics and Algorithms for Stochastic Goal Recognition Design Problems[C]//IJCAI. 2017: 4455-4462.
[73] WAYLLACE C, KEREN S, YEOH W, et al. Accounting for partial observability in stochastic goal recognition design: messing with the marauder’s map[C]//Proceedings of the 10th Workshop on Heuristics and Search for Domain-Independent Planning (HSDIP), Delft, The Netherlands. 2018: 33-41.
[74] RICHARD B. Dynamic Programming[M]. Princeton University Press, 1957.
[75] ROBERT T. Depth-first search and linear graph algorithms[J]. SIAM Journal on Computing, 1972, 1(2): 146-160.
[76] MIRSKY R, STERN R, GAL Y, et al. Plan recognition design[C]//Workshops at the Thirty First AAAI Conference on Artificial Intelligence. 2017.
[77] RAMIREZ M, GEFFNER H. Heuristics for planning, plan recognition and parsing[J]. arXiv preprint arXiv:1605.05807, 2016.
[78] MIRSKY R. Goal and plan recognition design for plan libraries[J]. ACM Transactions on Intelligent Systems and Technology (TIST), 2019, 10(2): 14.
[79] PEREIRA R F, PEREIRA A G, MENEGUZZI F. Landmark-enhanced heuristics for goal recognition in incomplete domain models[C]//Proceedings of the International Conference on Automated Planning and Scheduling. 2019: 329-337.
[80] PEREIRA R F. Goal recognition over imperfect domain models[J]. arXiv preprint arXiv:2005.05712, 2020.
[81] AMATO C, BAISERO A. Active goal recognition[J]. arXiv preprint arXiv:1909.11173, 2019.
[82] ZHANG T. Solving large scale linear prediction problems using stochastic gradient descent algorithms[C]//Proceedings of the International Conference on Machine Learning (ICML). 2004. 919-926.
[83] ZHUO H H. Recognizing multi-agent plans when action models and team plans are both incomplete[J]//ACM Transactions on Intelligent Systems and Technology, 2019, 10(3): 1-24.
[84] POZANCO A, MARTIN Y E, FERNANDEZ S, et al. Counterplanning using Goal Recognition and Landmarks[C]//International Joint Conference on Artificial Intelligence. 2018: 4808-4814.
[85] GADEPALLY V, GOODWIN J, KEPNER J, et al. AI enabling technologies: a survey[J]. arXiv preprint arXiv:1905.03592, 2019.
[86] CHAKRABORTI T, KULKARNI A, SREEDHARAN S, et al. Explicability legibility predictability transparency privacy security the emerging landscape of interpretable agent behavior[C]//Proceedings of the International Conference on Automated Planning and Scheduling. 2019: 86-96.
[87] SREEDHARAN S, KAMBHAMPATI S. Balancing explicability and explanation in human-aware planning[C]//2017 AAAI Fall Symposium Series. 2017.
[88] BANERJEE B, KRAEMER L, LYLE J, et al. Multi-agent plan recognition: formalization and algorithms[C]//National Conference on Artificial Intelligence, 2010: 1059-1064.
[89] ZHUO H H. Multiagent plan recognition from partially observed team traces[J]. Plan, Activity, and Intent Recognition, 2014: 227-249.
[90] ARGENTA C, DOYLE J. Multi-agent plan recognition as planning (MAPRAP)[C]//International Conference on Agents and Artificial Intelligence. 2016: 141-14
[91] ALEXANDER K, WILLIAM M. McEneaney. Adversarial reasoning: computational approaches to reading the opponent's mind[R]. 2006.
[92] KEREN S, Gal A, KARPAS E. Goal recognition design-survey[C]//Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence (IJCAI-PRICAI-20). 2020.
Survey of intention recognition for opponent modeling
GAO Wei1,2, LUO Junren1, YUAN Weilin1, ZHANG Wanpeng1
1. College of Intelligence Science and Technology,National University of Defense and Technology, Changsha 410073, China 2. The army of 96843, Lanzhou 730102, China
Several different methods of opponent modeling were introduced, leading to the problem of intention recognition in behavior modeling. Then, the process, classification, main methods, research prospects and practical applications of intention recognition were analyzed inductively, the latest research in related fields were summarized. Finally, some shortcomings of the current intention recognition and design methods were pointed out and some new insights for the future research were presented.
opponent modeling, intention recognition, goal recognition, plan recognition, goal recognition design, plan recognition design
TP18
A
10.11959/j.issn.2096?109x.2021052
2020?07?10;
2020?09?25
張萬鵬,wpzhang@nudt.edu.cn
國家自然科學基金(61702528,61806212,U1734208)
The National Natural Science Foundation of China (61702528, 61806212, U1734208)
高巍, 羅俊仁, 袁唯淋, 等. 面向對手建模的意圖識別方法綜述[J]. 網絡與信息安全學報, 2021, 7(4): 86-100.
GAO W, LUO J R, YUAN W L, et al. Survey of intention recognition for opponent modeling[J]. Chinese Journal of Network and Information Security, 2021, 7(4): 86-100.
高巍(1996? ),女,遼寧開原人,國防科技大學碩士生,主要研究方向為對手建模、任務規劃、意圖識別、彈道規劃。

羅俊仁(1989? ),男,湖北大冶人,國防科技大學博士生,主要研究方向為智能體建模、對抗團隊博弈、多智能體強化學習。
袁唯淋(1994? ),男,云南曲靖人,國防科技大學博士生,主要研究方向為安全博弈、對手建模、強化學習、多智能體系統。

張萬鵬(1981? ),男,四川邛崍人,國防科技大學副研究員,主要研究方向為智能決策、任務規劃、自動化和控制、人機協同。