智能體對手建模研究進(jìn)展

劉嬋娟，趙天昊，劉?？?，張 強(qiáng)

智能體對手建模研究進(jìn)展

劉嬋娟，趙天昊，劉?？?，張 強(qiáng)

(大連理工大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，遼寧 大連 116024)

智能體是人工智能領(lǐng)域的一個核心術(shù)語。近年來，智能體技術(shù)在自動無人駕駛、機(jī)器人系統(tǒng)、電子商務(wù)、傳感網(wǎng)絡(luò)、智能游戲等方面得到了廣泛研究與應(yīng)用。隨著系統(tǒng)復(fù)雜性的增加，關(guān)于智能體的研究重心由對單個智能體的研究轉(zhuǎn)變?yōu)橹悄荏w間交互的研究。多個智能體交互場景中，智能體對其他智能體決策行為的推理能力是非常重要的一個方面，通?？梢酝ㄟ^構(gòu)建參與交互的其他智能體的模型，即對手建模來實(shí)現(xiàn)。對手建模有助于對其他智能體的動作、目標(biāo)、信念等進(jìn)行推理、分析和預(yù)測，進(jìn)而實(shí)現(xiàn)決策優(yōu)化。為此，重點(diǎn)關(guān)注智能體對手建模研究，展開介紹關(guān)于智能體動作預(yù)測、偏好預(yù)測、信念預(yù)測、類型預(yù)測等方面的對手建模技術(shù)，對其中的優(yōu)缺點(diǎn)進(jìn)行討論和分析，并對手建模技術(shù)當(dāng)前面臨的一些開放問題進(jìn)行總結(jié)，探討未來可能的研究和發(fā)展方向。

決策智能；對手建模；博弈論；智能體系統(tǒng)；AlphaGo

在人工智能領(lǐng)域，智能體(agent)是一個物理的或抽象的實(shí)體，能夠通過感知器感知環(huán)境，對環(huán)境做出反應(yīng)并通過效應(yīng)器作用于環(huán)境。近年來，智能體技術(shù)在自動無人駕駛、機(jī)器人系統(tǒng)、電子商務(wù)、傳感網(wǎng)絡(luò)、智能游戲等方面得到了廣泛研究與應(yīng)用，成為備受關(guān)注的研究方向之一。智能體技術(shù)主要分為對單個智能體和智能體間交互的研究。隨著系統(tǒng)復(fù)雜性的增加，關(guān)于智能體的研究重點(diǎn)逐步由單個智能體轉(zhuǎn)變?yōu)橹悄荏w之間的交互。

智能體間的交互形式主要包括競爭和合作2種。博弈論是研究互動決策的理論[1-2]，為刻畫和分析多智能體相互之間競爭與合作決策提供了理論框架。由于現(xiàn)實(shí)博弈的狀態(tài)動作空間太大、博弈元素不完全可知等因素，智能體難以實(shí)現(xiàn)完全理性，且智能體策略往往會不斷學(xué)習(xí)變化。鑒于傳統(tǒng)博弈理論中理性假設(shè)較強(qiáng)以及在狀態(tài)轉(zhuǎn)換和策略動態(tài)演化方面的建模不足，又基于有限理性的演化博弈理論及強(qiáng)化學(xué)習(xí)方法得到廣泛研究與應(yīng)用[3]，為博弈決策的建模與求解提供了新的思路。

在智能體交互環(huán)境中，智能體的收益不僅取決于環(huán)境，同時也取決于其他智能體的動作[4]。因此對其他智能體的策略、信念等特征的推理，對于智能體的有效決策至關(guān)重要。同時，參與交互的智能體在進(jìn)行交互時往往會暴露出一些行為特征或策略偏向。如果一個智能體在進(jìn)行交互決策時，能夠通過對其他智能體的建模而對其特征加以利用，則可幫助該智能體做出更好地決策。這種對參與交互的其他智能體進(jìn)行建模的方法稱為對手建模[5]。經(jīng)典的對手建模是根據(jù)智能體的交互歷史建立一個對手模型[6]，將該模型看作一個函數(shù)，輸入智能體的交互歷史信息與數(shù)據(jù)，輸出其動作、偏好、目標(biāo)、計劃等的預(yù)測。

根據(jù)交互環(huán)境的不同，對手建?？梢苑譃楦偁帉κ趾秃献鲗ο螅y(tǒng)稱為對手[7]。象棋等對抗性博弈是對手建模研究的主要推動力之一。這類博弈的主要解決方案是基于“極大極小”原理(動態(tài)博弈中的極大極小方法如圖1所示，其中，EV為用啟發(fā)式評估函數(shù)計算得出的博弈樹葉節(jié)點(diǎn)的評估值；BV為由極大極小原理得到各個狀態(tài)的評估值；MAX為選擇其直接后繼子節(jié)點(diǎn)中價值最大的節(jié)點(diǎn)價值作為對該節(jié)點(diǎn)的評估值；MIN為選擇其直接后繼子節(jié)點(diǎn)中最小的價值)，即智能體針對最壞情況、萬無一失地對手優(yōu)化其決策。但通常情況下玩家對其對手并不是一無所知。與該玩家博弈交互過程中可以積累經(jīng)驗和知識，即具有不完美的對手信息。隨著完美信息博弈的研究不斷取得成功，不完美信息博弈逐漸成為研究的難點(diǎn)[8]。由于無法準(zhǔn)確獲取對手的全部信息，對手模型的研究成為不完美信息博弈中的一個核心方向，即在博弈過程中通過對手建模，盡可能地發(fā)現(xiàn)并利用對手策略中的弱點(diǎn)，從而獲得更大的收益。處在同一環(huán)境中的多個智能體，由于資源的有限性必然面臨資源競爭導(dǎo)致的利益沖突，因此每個智能體必須考慮其他智能體可能采取的行動及該行動對自己產(chǎn)生的影響。因此，如何在競爭環(huán)境中建立對手模型并不斷更新，進(jìn)而更好地了解和預(yù)測對手并正確制定自身對策使自己利益最大化，是智能體決策優(yōu)化的一個關(guān)鍵問題。

圖1 極大極小算法過程示例(在深度為3和分支因子為2的博弈樹中采用極大極小策略進(jìn)行決策)

除了傳統(tǒng)博弈論領(lǐng)域，在多智能體強(qiáng)化學(xué)習(xí)領(lǐng)域中對手建模也得到了一系列的研究[7]。多智能體強(qiáng)化學(xué)習(xí)考慮的是一群智能體彼此交互并與環(huán)境相互作用的決策場景，重點(diǎn)關(guān)注多智能體的協(xié)同問題。隨著多智能體系統(tǒng)的發(fā)展，其類型也越來越多，該決策的關(guān)鍵是基于彼此的了解及調(diào)整自己的策略。開放多智能體環(huán)境中，智能體會遇到之前未知的對手，那么可能需要將新的對手與老對手進(jìn)行對比，并用之前的成功策略作為該對手可能采用的策略，從而更好地協(xié)作。

對手建模在智能游戲、自動協(xié)商、足球機(jī)器人、人機(jī)交互等人工智能應(yīng)用場景中有著重要的應(yīng)用價值[7]。例如，自動駕駛汽車要保持在道路上安全穩(wěn)定運(yùn)行，不僅需要感知環(huán)境，還需要通過預(yù)測汽車和行人的行駛方向、運(yùn)動軌跡來更好地避免事故；在談判過程中，如果知道對方的底線，就能更快地達(dá)成理想的協(xié)議；游戲設(shè)計領(lǐng)域的一個重要挑戰(zhàn)是創(chuàng)建自適應(yīng)的可對玩家動作做出正確響應(yīng)的AI對手，要求其能夠首先識別玩家的策略?；诖罅康挠螒蚧胤?，AI對手能夠更好地預(yù)測對手的策略，提升自身的能力；在商業(yè)戰(zhàn)中，如果知道對手的商業(yè)策略，則能夠利用這些信息做出更有效地打擊對手的決策。

目前已有很多的智能體對手建模方法被提出。依據(jù)建模和預(yù)測的目標(biāo)，對手建模方法可分為對對手動作、對手類型、對手偏好及對手信念的建模等。不同方法各具優(yōu)缺點(diǎn)且適用于不同的情況?？傮w而言，理論和實(shí)踐證明通過合適的對手建模方法可實(shí)現(xiàn)對對手屬性的預(yù)測，能夠在各種交互場景中幫助智能體實(shí)現(xiàn)決策優(yōu)化。隨著智能交互場景的日益豐富與完善，對手建模技術(shù)也得到不斷地研究與發(fā)展，且面臨新的困難與挑戰(zhàn)。

本文基于對相關(guān)文獻(xiàn)的研究和總結(jié)，從對智能體的動作建模、偏好建模、信念建模、類型建模以及其他建模等幾個角度出發(fā)，對其主要的方法和技術(shù)進(jìn)行了詳細(xì)地闡述并對其優(yōu)勢及不足進(jìn)行了分析，最后就對手建模技術(shù)存在的難點(diǎn)和挑戰(zhàn)性問題進(jìn)行總結(jié)，并探討未來可能的研究和發(fā)展方向。

1 面向動作預(yù)測的對手建模研究

動作預(yù)測即通過重建對手的決策方法，顯式預(yù)測對手的未來動作，是對手建模中最常見的一種方法。其基本思路是首先建立一個初始的對手模型，可以初始化一個隨機(jī)模型或引用已知特定參數(shù)的一個對手模型作為初始模型；然后基于與對手的交互過程，不斷對模型參數(shù)進(jìn)行調(diào)整；最終擬合出與觀察結(jié)果相符的對手模型。面向動作預(yù)測的對手建模方法主要包括基于動作頻率和基于相似性推理2種。

1.1 基于動作頻率的對手動作預(yù)測

一次決策交互之后，根據(jù)其他智能體使用的動作相應(yīng)更新其計數(shù)。通過博弈實(shí)驗結(jié)果可以看出，采用基于對手動作頻率的聯(lián)合動作估值有助于通過較少的交互次數(shù)提升多智能體系統(tǒng)中智能體選擇最優(yōu)聯(lián)合動作的概率。

采用基于動作頻率的對手建模方法，需要解決的關(guān)鍵問題是了解在建模中使用哪些歷史元素。如果使用的歷史信息過少或有錯，就有可能做出錯誤或低可靠性的預(yù)測；如果使用歷史信息過多，就會導(dǎo)致學(xué)習(xí)過慢。為解決此問題，JENSEN等[12]提出使用歷史中個最近元素的可能子集來學(xué)習(xí)動作頻率的方法。為解決子集組合爆炸的問題，該方法采用條件熵進(jìn)行歷史信息的選擇。熵越高則不確定性越高，因此，最終選擇的是熵最低的歷史元素子集。

由此可見，基于動作頻率的對手動作預(yù)測方法主要是基于歷史交互信息對未來出現(xiàn)相同狀態(tài)時的對手動作進(jìn)行預(yù)測。通過此方法可以在決策開始時就建立一個相對理性的對手智能體，避免將一無所知的隨機(jī)對手模型作為初始模型。但該方法主要處理歷史出現(xiàn)過的狀態(tài)，難以預(yù)測沒有遇到過的未來狀態(tài)。

1.2 基于相似性推理的對手動作預(yù)測

動作頻率的建模方式只能預(yù)測在歷史中曾經(jīng)出現(xiàn)的狀態(tài)，而對于未來未知狀態(tài)沒有很好的泛化能力?；谕评淼姆椒梢越鉀Q這個問題，其基本思路是首先將歷史狀態(tài)歸結(jié)為不同的情形，記錄這些情形以及智能體遇到該情形時所采取的動作。然后，構(gòu)造相似性函數(shù)來評估不同情形的相似程度。最后，當(dāng)遇到新的情形時，依據(jù)相似函數(shù)判定最相近的情況[13-15]并預(yù)測相應(yīng)的可能動作。

基于相似性推理方法的關(guān)鍵問題就在于相似度函數(shù)的設(shè)計。通常，決策情形(或案例)包含多個屬性的向量表示，而相似度函數(shù)定義為向量之間的某種差異運(yùn)算，且需要根據(jù)被建模智能體的特征進(jìn)行自動優(yōu)化。STEFFENS[16]將相似度函數(shù)定義為2個給定決策情形的屬性差異的線性加權(quán)，可以一個足球游戲為例，即

上述2種對手動作預(yù)測方法的共同點(diǎn)均是基于觀測到的歷史信息，由此可能帶來的一個問題是指數(shù)級的空間復(fù)雜度。例如，假設(shè)使用的歷史信息或情形的個數(shù)為，每個歷史信息或情形的動作或值的個數(shù)為，則需要存儲的數(shù)據(jù)規(guī)模為a。因此需要尋求其他的表示方法，例如有限自動機(jī)DFA[18]、決策樹[19]、人工神經(jīng)網(wǎng)絡(luò)[20]等方式。文獻(xiàn)[4]將多智能體強(qiáng)化學(xué)習(xí)問題重新表述為貝葉斯推理，推導(dǎo)出最大熵目標(biāo)的多智能體版本，并通過最大熵目標(biāo)學(xué)習(xí)對手的最優(yōu)策略，為合作博弈中的對手建模提供了新的思路。DAVIES等[21]在多智能體強(qiáng)化學(xué)習(xí)算法-多智能體深度確定性策略梯(multi-agent deep deterministic policy gradient，MADDPG) (圖2)中引入雙向LSTM網(wǎng)絡(luò)，存儲并通過學(xué)習(xí)更新對手表示來模擬對手的學(xué)習(xí)過程，作者以Keep-Away游戲為例說明對手建模表現(xiàn)出更好的效果。

圖2 多智能體強(qiáng)化學(xué)習(xí)MADDPG算法框架

2 面向偏好預(yù)測的對手建模研究

對手的偏好建模是通過對對手策略的根本原因的建模實(shí)現(xiàn)對策略的預(yù)測與分析，主要包括對手意圖、收益函數(shù)、目標(biāo)計劃等方面。

2.1 基于意圖識別的偏好預(yù)測

基于行為意圖的對手建模方法對算法實(shí)時性的要求較高，即需要在實(shí)時交互的過程中，基于已做出的部分動作信息和歷史相同態(tài)勢下的決策，快速判斷其正在采取的行動的真實(shí)意圖，這一點(diǎn)對于一些場景(如人機(jī)交互中機(jī)器人對于人的意圖識別)等非常重要。

2.2 基于收益函數(shù)重構(gòu)的偏好預(yù)測

基于收益函數(shù)重構(gòu)對智能體的偏好進(jìn)行預(yù)測的方法往往需要基于對手是理性的假設(shè)，并且需要對對手模型的部分信息(如收益函數(shù)的影響因素)有一定了解，同時借助大量的歷史信息才能學(xué)到更準(zhǔn)確的參數(shù)。

2.3 基于計劃識別的偏好預(yù)測

計劃識別是根據(jù)所觀察的對手動作確定對手的最終目標(biāo)及其實(shí)現(xiàn)該目標(biāo)的計劃[23]。目標(biāo)對象的描述通常采用基于層次表示法的“計劃庫”形式[24]，從頂層的最終目標(biāo)子任務(wù)到最終不可分解的動作，逐層分解和細(xì)化。計劃庫中除了計劃分解關(guān)系，還包含各個步驟之間的時序等依賴關(guān)系以及步驟的先決環(huán)境條件信息。計劃庫的表示形式可以使用有向無環(huán)圖?；谟媱潕煲约耙唤M觀察到的歷史動作，計劃識別的方法可以生成滿足計劃庫規(guī)則的可能計劃。將對手的規(guī)劃問題視為馬爾可夫決策過程，通過求解最優(yōu)隨機(jī)策略實(shí)現(xiàn)對手行為序列的預(yù)測。

基于計劃識別的偏好預(yù)測方法，可以預(yù)知相對較長的一段交互中對手的策略，因此更適用于長期或持續(xù)決策場景。例如，智能個性化推薦系統(tǒng)可以基于對用戶歷史目標(biāo)和計劃的分析，為其推薦所需要的信息[25]；一個智能的入侵檢測系統(tǒng)可通過檢測攻擊者的目標(biāo)和計劃，持續(xù)地采取相應(yīng)的防御措施[26]。但是該方法需要有設(shè)計良好的計劃庫，使其能夠準(zhǔn)確表達(dá)各種可能的計劃，甚至非常復(fù)雜的計劃。

3 面向信念建模的對手建模研究

除了環(huán)境因素，其他自主智能體的“心智狀態(tài)”也會影響智能體的決策。智能體對于當(dāng)前的環(huán)境以及其他智能體持有自己的信念，與此同時，其他智能體對環(huán)境也持有自己的信念，這樣的信念層層嵌套就形成了無限的遞歸信念推理。信念建模就是通過“模擬”其他智能體的推理過程來預(yù)測其行為策略。

3.1 定量信念建模

信念建模首先在博弈論中的不完全信息博弈中得到研究[8,27]。為解決信念推理的無限遞歸問題，文獻(xiàn)[5]將信念嵌套終止于一個固定的遞歸深度，從而實(shí)現(xiàn)信念的近似模擬。在遞歸底部的預(yù)測被傳遞到上層以選擇該層的最佳操作，然后再傳遞到更高層，依此類推，直到智能體可以在遞歸開始時做出選擇。通常假設(shè)每個智能體自認(rèn)比其他智能體擁有更深的信念，且假設(shè)其他智能體是理性的，即將根據(jù)自己的信念選擇最優(yōu)的行動。GALLEGO等[28]將-層的信念建模方法用在多智能體強(qiáng)化學(xué)習(xí)中，基于模型平均算法來更新對手信念中最有可能的模型。BAKER等[29]利用貝葉斯對手信念來構(gòu)建對手模型，并在撲克游戲中展示出貝葉斯對手模型的有效性。

3.2 定性信念建模

在形式邏輯領(lǐng)域，研究學(xué)者們對智能體的信念建立了定性的描述與推理方法。通常用處理不確定性的信念算子“B”來表示智能體相信。信念算子與知識算子“K”都屬于認(rèn)知邏輯算子。與定量信念類似，定性信念的研究涉及單層的信念，以及多層的信念嵌套[30]；同時還要考慮信念是否動態(tài)變化[31]?；谛拍钸壿嫹椒ǎ梢越柚Ｐ蜋z測技術(shù)實(shí)現(xiàn)多智能體互動環(huán)境下的策略推理與自動驗證[32]。

面向信念建模的方法充分體現(xiàn)了智能體之間的相互建模，智能體在對對手預(yù)測的同時也將對手對于該智能體的預(yù)測考慮在內(nèi)。然而由于這種層層嵌套的遞歸推理或計算，導(dǎo)致計算代價非常大，且在遞歸的交互推理中往往需要加入一些理性假設(shè)，因此建模準(zhǔn)確性的保證也是一個難點(diǎn)。

4 面向類型建模的對手建模

4.1 基于模型選擇的類型建模

上述對手建模方法都需要基于對手的交互信息從零開始學(xué)起。顯然，該方式構(gòu)建模型的速度比較慢。基于類型的建模是假設(shè)建模對象屬于已知的幾種類型之一，因而可以直接重用先前的模型。

每一個類模型可以對智能體的完整參數(shù)進(jìn)行描述，以交互歷史作為輸入，以被建模對象的動作概率分布作為輸出。對于當(dāng)前的交互，在已有模型中找出最為相似的模型即可。類模型的參數(shù)可以由領(lǐng)域內(nèi)的專家指定或根據(jù)任務(wù)領(lǐng)域合理假設(shè)[33]，也可以通過已有的交互學(xué)習(xí)信息或歷史數(shù)據(jù)生成[19]。羅鍵和武鶴[34]利用交互式動態(tài)影響圖(interactive dynamic influence diagrams，I-DID)對未知對手進(jìn)行建模。交互式動態(tài)影響圖以圖形形式表達(dá)多智能體交互決策過程并在復(fù)雜的交互中對其他智能體的動作行為進(jìn)行預(yù)測。圖3為包含2個智能體(位于層的主觀智能體和位于-1層的智能體)的交互式動態(tài)影響圖。其中的節(jié)點(diǎn)包括：①決策節(jié)點(diǎn)，表示智能體的決策行為A；②隨機(jī)節(jié)點(diǎn)，包括客觀存在的環(huán)境狀態(tài)以及智能體的觀察函數(shù)O，智能體動作的概率分布A；③值節(jié)點(diǎn)R為智能體的值函數(shù)；④模型節(jié)點(diǎn)m,l-1為-1層的智能體所有可能存在的模型，即由上層智能體描述的下層智能體的所有模型，，其中為該模型的信度，為智能體的框架(包括決策節(jié)點(diǎn)、觀察節(jié)點(diǎn)和值節(jié)點(diǎn))。除此之外，還有策略鏈，用隨機(jī)節(jié)點(diǎn)A與模型節(jié)點(diǎn)之間的虛線表示，代表模型的解即智能體的策略。一個層的交互式動態(tài)影響圖的求解是采用自底向上的方法，即求解智能體的第層的I-DID，需要先解出所有低一層即-1層的智能體的模型m,-1。該工作將對手的候選模型保存在模型節(jié)點(diǎn)并隨時間更新其信度，通過智能體觀察到的動作及的觀察，基于最大效用理論，在模型空間中使用“觀察-動作”序列逐步排除候選模型，最終判定對手的真實(shí)模型。該方法大大提高了建模的速度，但需要基于智能體都是理性的假設(shè)。

圖3 l層上的交互式動態(tài)影響圖示例

4.2 基于特征分類的類型建模

除了建立預(yù)選類模型之外，也可以通過特征分類來預(yù)測對手的行為風(fēng)格，例如是“攻擊型”還是“防守型”[35]，以揭示對手在何時會采取相應(yīng)的動作。該方法將有限的特征標(biāo)簽中的一種分配給對手，因此是典型的分類問題。在策略游戲領(lǐng)域，該方法得到了廣泛地應(yīng)用。WEBER和MATEAS[36]提出預(yù)測星際爭霸游戲中玩家策略的方法。在網(wǎng)絡(luò)中收集大量玩家的游戲回放，再將游戲回放轉(zhuǎn)換為游戲動作日志，每個玩家的行動都被編碼成一個單一的特征向量，并使用基于專家游戲玩法分析的規(guī)則標(biāo)記出特定的策略。將策略預(yù)測問題表示成分類問題，利用這些數(shù)據(jù)，使用一些經(jīng)典的分類及回歸算法如C4.5算法，k-NN等機(jī)器學(xué)習(xí)算法檢測對手的策略并估計對手執(zhí)行動作的時間。SYNNAEVE和BESSIèRE[37]利用收集到的相同回放數(shù)據(jù)，基于期望最大化和k-means算法，提出了將星際爭霸玩家的開放策略從有限的策略集中分類的方法。文獻(xiàn)[35]提出特定的分類器來預(yù)測玩家在游戲Spring中的游戲風(fēng)格。DAVIDSON等[38]使用深度神經(jīng)網(wǎng)絡(luò)表達(dá)對手模型，通過只對專家進(jìn)行特征選擇，減輕了特征選擇的計算負(fù)擔(dān)并在德州撲克游戲中應(yīng)用該方法取得了較好的分類效果。

因此，基于類型的對手建模通過分類模型的建立，很好地避免了對對手從零學(xué)起的問題。然而，該方法的有效性依賴于分類模型的準(zhǔn)確性和完整性，錯誤的或覆蓋面不足的類型空間會直接導(dǎo)致錯誤的預(yù)測。

5 其他建模方式

對手建模方法大多都采用顯示建模的方式，即建立一個顯示的對手模型(如決策樹、神經(jīng)網(wǎng)絡(luò)、貝葉斯網(wǎng)絡(luò))等來預(yù)測對手策略。同時，對手建模較多的是從主智能體的角度對交互中的其他智能體進(jìn)行建模，因此，對個體智能體的建模是一個主流模式。

5.1 隱式建模方法

圖4 基于DQN的隱式對手建模網(wǎng)絡(luò)

吳天棟和石英[42]基于貝葉斯統(tǒng)計方法提出策略自擴(kuò)展算法，改進(jìn)了顯式建模的效率；同時基于對手博弈行為在不同信息集中的關(guān)聯(lián)性提出了子策略發(fā)現(xiàn)算法，提高了隱式模型的準(zhǔn)確率。

相對于顯示建模，隱式建模的優(yōu)點(diǎn)在于合并了建模與規(guī)劃這2個過程，可以更自然地利用二者之間的協(xié)同作用。但顯式建模更易于直接觀察建模結(jié)果，并且通過模型與規(guī)劃的解耦，對手模型可以由不同的規(guī)劃算法使用。

5.2 群體建模方法

上述的模型大都是預(yù)測單個智能體的行為，而在多智能體的環(huán)境中，智能體之間可能具有顯著的相關(guān)性，對每個智能體單獨(dú)建模則將由于無法捕捉到這樣的關(guān)聯(lián)特征而使預(yù)測效果大打折扣。聯(lián)盟博弈中，聯(lián)盟內(nèi)部的智能體盡力地使聯(lián)盟的總體收益最大化，不同聯(lián)盟之間也應(yīng)該將其他聯(lián)盟中的成員作為一個整體來進(jìn)行對手建模。FOERSTER等[43]在深度強(qiáng)化學(xué)習(xí)中使智能體在更新自己策略的同時，考慮到他人的學(xué)習(xí)過程，即基于其他智能體的行動來預(yù)測其參數(shù)。將所有參與交互的其他智能體建模視為其對手，主體不是根據(jù)當(dāng)前的環(huán)境參數(shù)優(yōu)化策略，而是考慮到下一步對手更新策略之后的環(huán)境，并依此環(huán)境來更新策略。實(shí)驗表明該方法在重復(fù)囚徒困境和投幣游戲中都取得了很好的效果。AUMANN[44]提出了推廣的納什均衡概念且定義為個體行為的聯(lián)合分布。將智能體分組，通過利用群體中的額外結(jié)構(gòu)(如團(tuán)隊內(nèi)成員角色信息、通信協(xié)議[45-46]等)對群體進(jìn)行建模往往更加高效和準(zhǔn)確[29]。

相對于個體對手建模，群體建模方式可以刻畫群組內(nèi)部成員間的策略依賴，因此在以群體形式?jīng)Q策的場景中有望取得更好的預(yù)測效果。同時由于不需要單獨(dú)考慮每個對手和主智能體的決策交互，能一定程度上提高建模的效率。但由于群組內(nèi)部具有各種相互依賴的關(guān)系，群體模型相對于個體模型而言往往更加復(fù)雜。

6 未來發(fā)展方向

對手建模理論及方法的研究已經(jīng)取得了長足的進(jìn)展。然而面對復(fù)雜開放環(huán)境，智能體需應(yīng)對動態(tài)不確定性變化并自適應(yīng)地做出相應(yīng)調(diào)整，這也對對手建模提出了更高的要求。

6.1 部分可觀測條件下的對手建模

目前的研究往往假設(shè)能夠獲取完整的環(huán)境和對手信息。然而，許多領(lǐng)域應(yīng)用場景具有環(huán)境部分可觀測的特性，智能體的交互性與自適應(yīng)性更為環(huán)境增加了不確定性。智能體只能獲取關(guān)于環(huán)境或其他智能體不完整或不確定的觀察，這種部分可觀測的特性使對手建模變得愈發(fā)困難：一方面建?？赡苊媾R信息錯誤或遺漏的問題；另一方面，對手的行為模式與其持有信息之間的對應(yīng)關(guān)系不能明確。目前，在擴(kuò)展式博弈領(lǐng)域，已經(jīng)提出一些符號和概率方法來解決這一問題[47]。如何實(shí)現(xiàn)更廣泛的智能交互場景中部分可觀測條件下的對手建模是一個亟待解決的問題。

6.2 對手動態(tài)策略的建模

現(xiàn)有的建模方法中，多數(shù)方法都假設(shè)智能體在交互過程中的策略是固定的。但在自適應(yīng)系統(tǒng)中，智能體也在不斷學(xué)習(xí)與動態(tài)適應(yīng)調(diào)整中，因此這種假設(shè)是不現(xiàn)實(shí)的，對手模型的構(gòu)建需要根據(jù)對手的實(shí)時策略做出適應(yīng)性變化。但對手策略可能變化的情況過多，使得動態(tài)建模變得非常困難。當(dāng)前已經(jīng)有一些方法針對這一問題提出了相應(yīng)的解決方案，從而在不同程度上實(shí)現(xiàn)了動態(tài)的對手建模。例如，文獻(xiàn)[48]規(guī)定動作必須在極限內(nèi)收斂，文獻(xiàn)[41]要求在多種固定策略中周期性選擇。然而，要真正處理變化的對手策略，構(gòu)建能夠動態(tài)預(yù)測對手行為的智能體仍然是面臨的一個困難。

6.3 開放多智能體系統(tǒng)中的對手建模

目前，對于多智能體場景下智能體的建模均存在系統(tǒng)環(huán)境封閉的假設(shè)，即在整個交互的過程中，系統(tǒng)中的智能體數(shù)目是不變的。而在一些開放的多智能體系統(tǒng)中[49]，智能體可能隨時進(jìn)入或離開系統(tǒng)而不通知其他智能體，這種特性在網(wǎng)絡(luò)環(huán)境當(dāng)中是經(jīng)常出現(xiàn)的[50]。當(dāng)下，已經(jīng)有一些針對開放多智能體系統(tǒng)的研究，但是為此類系統(tǒng)開發(fā)高效的對手建模方法，例如開放環(huán)境下合作智能體間信任與信譽(yù)模型的建立[51]，仍然是一個挑戰(zhàn)。

6.4 可遷移的對手建模方法

基于特定的決策場景和特定的對手信息建立對手模型是比較直接的思路。然而某一場景下表現(xiàn)良好的方法換到其他場景或其他對手時則難以有效應(yīng)用。足夠智能的智能體應(yīng)具備面對未知環(huán)境和對手做出自適應(yīng)調(diào)整的能力。目前的對手建模大都是針對特定決策過程下的特定對手，不具有一般性。具有一定通用性的對手建模方法具有很大的研究吸引力，同時也帶來更大的挑戰(zhàn)。遷移學(xué)習(xí)可以通過重用過去的經(jīng)驗來改進(jìn)新場景和未知對手的學(xué)習(xí)過程[19]，可能是研究此類問題的解決方案之一。

7 總 結(jié)

本文主要針對當(dāng)前存在的智能體對手建模技術(shù)進(jìn)行了歸納和總結(jié)，詳細(xì)闡述了對手建模的不同類型。另外，本文還列舉了各種建模方法中的典型算法，分析了各類技術(shù)的優(yōu)缺點(diǎn)及技術(shù)特點(diǎn)。最后對對手建模技術(shù)研究中存在的難點(diǎn)問題及未來發(fā)展方向進(jìn)行了探討。

[1] SILVER D, HUANG A, MADDISON C J, et al. Mastering the game of go with deep neural networks and tree search[J]. Nature, 2016, 529(7587): 484-489.

[2] Osborne M J, Rubinstein A. A course in game theory[M]. Cambridge: MIT Press, 1994: 1-368.

[3] Lowe R, Wu Y I, Tamar A, et al. Multi-agent actor-critic for mixed cooperative-competitive environments[C]//The 31st International Conference on Neural Information Processing Systems. Cambridge: MIT Press, 2017: 6382-6393.

[4] Tian Z, Wen Y, Gong Z, et al. A regularized opponent model with maximum entropy objective[C]//The 28th International Joint Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2019: 602-608.

[5] Carmel D, Markovitch S. Learning models of opponent’s strategy game playing[C]//Proceedings of the AAAI Fall Symposium on Games: Learning and Planning. Palo Alto: AAAI Press, 1993: 140-147.

[6] LOCKETT A J, CHEN C L, MIIKKULAINEN R. Evolving explicit opponent models in game playing[C]//Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation - GECCO’07. New York: ACM Press, 2007: 2106-2113.

[7] He H, Boyd-Graber J, Kwok K, et al. Opponent modeling in deep reinforcement learning[C]//The 33rd International Conference on Machine Learning. New York: ACM Press, 2016: 1804-1813.

[8] Harsanyi J C. Games with incomplete information played by “Bayesian”[J]. Management Science, 1967, 14(3): 159-182.

[9] Brown G. Iterative solution of games by fictitious play[M]. New York: John Wiley & Sons, 1951: 374-376.

[10] Fudenberg D, Levine D K. The theory of learning in games[M]. Cambridge: MIT Press, 1998: 1-292.

[11] Claus C. The dynamics of reinforcement learning in cooperative multiagent systems[C]//The 15th National/10th Conference on Artificial Intelligence/Innovative Applications of Artificial Intelligence. Palo Alto: AAAI Press, 1998: 746-752.

[12] JENSEN S, BOLEY D, GINI M, et al. Rapid on-line temporal sequence prediction by an adaptive agent[C]//Proceedings of the 4th International Joint Conference on Autonomous Agents and Multiagent Systems-AAMAS’05. New York: ACM Press, 2005: 67-73.

[13] ALBRECHT S V, RAMAMOORTHY S. A game-theoretic model and best-response learning method for ad hoc coordination in multiagent systems[EB/OL]. [2021-06-18]. https://arxiv.org/abs/1506.01170.

[14] HSIEH J L, SUN C T. Building a player strategy model by analyzing replays of real-time strategy games[C]//2008 IEEE International Joint Conference on Neural Networks (IEEE World Congress on Computational Intelligence). New York: IEEE Press, 2008: 3106-3111.

[15] Borck H, Karneeb J, Alford R, et al. Case-based behavior recognition in beyond visual range air combat[C]//The 28th International Florida Artificial Intelligence Research Society Conference. Palo Alto: AAAI Press, 2015: 379-384.

[16] Steffens T. Adapting similarity measures to agent types in opponent modelling[C]//AAMAS’04 Workshop on Modeling Other Agents from Observations. Heidelberg: Springer, 2004: 125-128.

[17] DENZINGER J, HAMDAN J. Improving modeling of other agents using tentative stereotypes and compactification of observations[C]//Proceedings of IEEE/WIC/ACM International Conference on Intelligent Agent Technology. New York: IEEE Press, 2004: 106-112.

[18] CARMEL D, MARKOVITCH S. Model-based learning of interaction strategies in multi-agent systems[J]. Journal of Experimental & Theoretical Artificial Intelligence, 1998, 10(3): 309-332.

[19] Barrett S, Stone P, Kraus S, et al. Teamwork with limited knowledge of teammates[C]//Proceedings of the 27th AAAI Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2013:102-108.

[20] SILVER D, HUANG A, MADDISON C J, et al. Mastering the game of Go with deep neural networks and tree search[J]. Nature, 2016, 529(7587): 484-489.

[21] DAVIES I, TIAN Z, WANG J. Learning to model opponent learning (student abstract)[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2020, 34(10): 13771-13772.

[22] 薛方正, 方帥, 徐心和. 多機(jī)器人對抗系統(tǒng)仿真中的對手建模[J]. 系統(tǒng)仿真學(xué)報, 2005, 17(9): 2138-2141.

XUE F Z, FANG S, XU X H. Opponent modeling in adversarial multi-robot system simulation[J]. Acta Simulata Systematica Sinica, 2005, 17(9): 2138-2141 (in Chinese).

[23] CARBERRY S. Techniques for plan recognition[J]. User Modeling and User-Adapted Interaction, 2001, 11(1-2): 31-48.

[24] Oh J, F Meneguzzi, Sycara K P, et al. An agent architecture for prognostic reasoning assistance[C]//The 22nd International Joint Conference on Artificial Intelligence, Palo Alto: AAAI Press, 2011: 2513-2518.

[25] MCTEAR M F. User modelling for adaptive computer systems: a survey of recent developments[J]. Artificial Intelligence Review, 1993, 7(3-4): 157-184.

[26] GEIB C W, GOLDMAN R P. Plan recognition in intrusion detection systems[C]//Proceedings DARPA Information Survivability Conference and Exposition II. DISCEX'01. New York: IEEE Press, 2001: 46-55.

[27] HARSANYI J C. Bargaining in ignorance of the opponent’s utility function[J]. Journal of Conflict Resolution, 1962, 6(1): 29-38.

[28] GALLEGO V, NAVEIRO R, INSUA D R, et al. Opponent aware reinforcement learning[EB/OL]. [2021-04-18]. www. researchgate.net/publication/335276661_Opponent_Aware_Reinforcement_Learning.

[29] BAKER R J S, COWLING P I, RANDALL T W G, et al. Can opponent models aid poker player evolution?[C]//2008 IEEE Symposium On Computational Intelligence and Games. New York: IEEE Press, 2008: 23-30.

[30] VAN DITMARSCH H, VAN DER HOEK W, KOOI B. Dynamic epistemic logic[M]. Heidelberg: Springer, 2008: 1-282.

[31] MARQUIS P, SCHWIND N. Lost in translation: Language independence in propositional logic - application to belief change[J]. Artificial Intelligence, 2014, 206: 1-24.

[32] VAN BENTHEM J, VAN EIJCK J, GATTINGER M, et al. Symbolic model checking for Dynamic Epistemic Logic—S5 and beyond[J]. Journal of Logic and Computation, 2018, 28(2): 367-402.

[33] ALBRECHT S V, CRANDALL J W, RAMAMOORTHY S. An empirical study on the practical impact of prior beliefs over policy types[C]//Proceedings of the 29th AAAI Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2015: 1988-1994.

[34] 羅鍵, 武鶴. 基于交互式動態(tài)影響圖的對手建模[J]. 控制與決策, 2016, 31(4): 635-639.

LUO J, WU H. Opponent modeling based on interactive dynamic influence diagram[J]. Control and Decision, 2016, 31(4): 635-639 (in Chinese).

[35] Schadd F, Bakkes S, Spronck P. Opponent modeling in real-time strategy games[EB/OL]. [2021-04-18]. www. researchgate.net/publication/335276661_Opponent_Aware_Reinforcement_Learning.

[36] WEBER B G, MATEAS M. A data mining approach to strategy prediction[C]//2009 IEEE Symposium on Computational Intelligence and Games. New York: IEEE Press, 2009: 140-147.

[37] SYNNAEVE G, BESSIèRE P. A Bayesian model for opening prediction in RTS games with application to StarCraft[C]// 2011 IEEE Conference on Computational Intelligence and Game. New York: IEEE Press, 2011: 281-288.

[38] DAVIDSON a, bILLINGS d, SCHAEFFER J, et al, Improved opponent modeling in poker[C]//Proceedings of the 2000 International Conference on Artificial Intelligence (ICAI 2000), Palo Alto: AAAI Press, 2000: 493-499.

[39] CRANDALL J W. Towards minimizing disappointment in repeated games[J]. Journal of Artificial Intelligence Research, 2014, 49: 111-142.

[40] Bard N, Johanson M, Burch N, et al. Online implicit agent modelling[C]//2013 International Conference on Autonomous Agents and Multiagent Systems. New York: ACM Press, 2013: 255-262.

[41] HERNANDEZ-LEAL P, ZHAN Y S, TAYLOR M E, et al. Efficiently detecting switches against non-stationary opponents[J]. Autonomous Agents and Multi-Agent Systems, 2017, 31(4): 767-789.

[42] 吳天棟, 石英. 不完美信息博弈中對手模型的研究[J]. 河南科技大學(xué)學(xué)報: 自然科學(xué)版, 2019, 40(1): 54-59, 7.

WU T D, SHI Y. Research on opponent modeling in imperfect information games[J]. Journal of Henan University of Science and Technology: Natural Science, 2019, 40(1): 54-59, 7 (in Chinese).

[43] FOERSTER J N, CHEN R Y, AL-SHEDIVAT M, et al. Learning with opponent-learning awareness[C]//AAMAS’18: Proceedings of the 17th International Conference on Autonomous Agents and Multi-Agent Systems. New York: ACM Press, 2018: 122-130.

[44] AUMANN R J. Subjectivity and correlation in randomized strategies[J]. Journal of Mathematical Economics, 1974, 1(1): 67-96.

[45] STONE P, VELOSO M. Task decomposition, dynamic role assignment, and low-bandwidth communication for real-time strategic teamwork[J]. Artificial Intelligence, 1999, 110(2): 241-273.

[46] TAMBE M. Towards flexible teamwork[J]. Journal of Artificial Intelligence Research, 1997, 7: 83-124.

[47] PANELLA A, GMYTRASIEWICZ P. Interactive POMDPs with finite-state models of other agents[J]. Autonomous Agents and Multi-Agent Systems, 2017, 31(4): 861-904.

[48] CONITZER V, SANDHOLM T. AWESOME: a general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents[J]. Machine Learning, 2007, 67(1-2): 23-43.

[49] PINYOL I, SABATER-MIR J. Computational trust and reputation models for open multi-agent systems: a review[J]. Artificial Intelligence Review, 2013, 40(1): 1-25.

[50] VARMA V S, MOR?RESCU I C, NE?I? D. Open multi-agent systems with discrete states and stochastic interactions[J]. IEEE Control Systems Letters, 2018, 2(3): 375-380.

[51] HUYNH T D, JENNINGS N R, SHADBOLT N R. An integrated trust and reputation model for open multi-agent systems[J]. Autonomous Agents and Multi-Agent Systems, 2006, 13(2): 119-154.

Research progress of opponent modeling for agent

LIU Chan-juan, ZHAO Tian-hao, LIU Rui-kang, ZHANG Qiang

(School of Computer Science and Technology, Dalian University of Technology, Dalian Liaoning 116024, China)

Agent is a core term in the field of artificial intelligence. In recent years, agent technology has been widely studied and applied in such fields as autonomous driving, robot system, e-commerce, sensor network, and intelligent games. With the increase of system complexity, the research focus on agent technology has been shifted from single agent to interactions between agents. In scenarios with multiple interactive agents, an important direction is to reason out other agents’ decisions and behaviors, which can be realized through the modeling of other agents involved in the interaction, that is, opponent modeling. Opponent modeling is conducive to reasoning, analyzing, and predicting other agents’ actions, targets, and beliefs, thus optimizing one’s decision-making. This paper mainly focused on the research on opponent modeling of agents, and introduced the opponent modeling technology in agent action prediction, preference prediction, belief prediction, and type prediction. In addition, their advantages and disadvantages were discussed, some current open problems were summarized, and the possible future research directions were presented.

decision intelligence; opponent modeling; game theory; agent systems; AlphaGo

TP 391

10.11996/JG.j.2095-302X.2021050703

A

2095-302X(2021)05-0703-09

2021-04-01；

2021-05-21

1 April，2021；

21 May，2021

中國科協(xié)青年人才托舉工程(2018QNRC001)；國家自然科學(xué)基金項目(61702075，31370778，61425002，61772100，61751203)

Young Elite Scientists Sponsorship Program by CAST (2018QNRC001); National Natural Science Foundation of China (61702075, 31370778, 61425002, 61772100, 61751203)

劉嬋娟(1986-)，女，河北邯鄲人，副教授，博士。主要研究方向為智能決策與智能計算。E-mail：chanjuanliu@dlut.edu.cn

LIU Chan-juan (1986-), female, associate professor, Ph.D. Her main research interests cover intelligent decision and intelligent computing. E-mail：chanjuanliu@dlut.edu.cn

張 強(qiáng)(1971–)，男，陜西西安人，教授，博士。主要研究方向為圖形圖像處理、智能計算等。E-mail：qzhangdl@163.com

ZHANG Qiang (1971-), male, professor, Ph.D. His main research interests cover graphic image processing, intelligent computing, etc. E-mail：qzhangdl@163.com