0
| 本文作者： 楊曉凡 | 2017-11-16 21:56 |
雷鋒網(wǎng) AI 科技評論按：在2017年的微軟Malmo協(xié)作AI挑戰(zhàn)賽MCAC上，新加坡南洋理工大學(xué)助理教授安波帶領(lǐng)的團隊憑借他們的AI HogRider從來自26個國家的81支團隊中脫穎而出拿下冠軍。
安波是新加坡南洋理工大學(xué)計算機科學(xué)與工程學(xué)院南洋助理教授，于 2011 年在美國麻省大學(xué) Amherst 分校獲計算機科學(xué)博士學(xué)位。他的主要研究領(lǐng)域包括人工智能、多智能體系統(tǒng)、博弈論及優(yōu)化。有 60 余篇論文發(fā)表在人工智能領(lǐng)域的國際頂級會議 AAMAS、IJCAI、AAAI、ICAPS、KDD 以及著名學(xué)術(shù)期刊 JAAMAS、AIJ、IEEE Transactions，今年也在 IJCAI獲得了 IJCAI early career award并進行了現(xiàn)場演講。雷鋒網(wǎng) AI 科技評論之前也對安博士做過專訪，詳見 能玩德?lián)湟材鼙Ｕ蠂野踩?，南洋理工安波博士闡述算法博弈論的魅力何在？
近期，冠軍團隊也發(fā)出了一篇詳細的論文介紹了他們對協(xié)作AI的思考以及這次比賽的獲獎技巧（論文已經(jīng)被AAAI 2018錄用）。雷鋒網(wǎng) AI 科技評論把論文主要內(nèi)容介紹如下。
多個各自具有獨立興趣的智能體如何在復(fù)雜環(huán)境下協(xié)作完成更高級的任務(wù)一直是亟待解決的研究難點。 微軟的 Malmo 協(xié)作 AI 挑戰(zhàn)賽（MCAC）就是多智能體協(xié)作領(lǐng)域的一項重要比賽，鼓勵研究者們更多地研究協(xié)作AI、解決各種不同環(huán)境下的問題。
今年 MCAC 2017 中的挑戰(zhàn)問題是，如何在基于 Minecraft 的小游戲環(huán)境中讓兩個智能體合作，抓住一只小豬。
環(huán)境設(shè)置如圖所示，左側(cè)為第一人稱視角，右側(cè)為對應(yīng)的符號化的上帝視角。區(qū)域一共9x9大小，綠色格子代表可以走動的草地，橙色格子是不能穿過的圍欄或者柱子，兩個黑色的格子是出口；粉色的圈是小豬；藍色、紅色兩個箭頭就是要交替行動、合作抓住這只小豬的智能體；藍色智能體是比賽提供的，參賽選手要設(shè)計紅色智能體的策略，跟藍色智能體配合抓住小豬。
智能體的合法行為有三種，左轉(zhuǎn)、右轉(zhuǎn)以及前進。每局游戲中，藍色智能體有25%的幾率是一個隨機行動智能體，另外75%的幾率是一個沿著最短路徑追著小豬跑的專注行動智能體。小豬的移動是完全隨機的，并且智能體得到的信息也是有噪音的。
比賽的計分規(guī)則并不復(fù)雜，經(jīng)過一定局數(shù)的游戲（比如100局或500局）后，統(tǒng)計總分。智能體和圍欄/柱子一起把小豬完全圍住，兩個智能體就可以都得到25分，如上圖所示單個智能體把小豬堵在黑色格子或者兩個智能體共同夾擊小豬都可以，然后進入下一局；某一個智能體自己走到出口也會進入下一局，但這時只有先走到出口的智能體可以得到5分；比賽選手的智能體每一個行動都會扣掉1分。另外，一局中智能體一共達到25個行動，或者達到大約100秒的比賽時間后，也會進入下一局。
從計分規(guī)則可以看出，參賽選手的智能體必須用盡可能少的行動步數(shù)抓到小豬才能得到高分，這個過程中也最好和比賽提供的智能體有所配合（能在更多位置抓到小豬）。
在HogRider團隊看來，多智能體合作系統(tǒng)本來就是一大難題。其中一個重要因素是智能體之間的互動問題，在許多實際情境中，由于每個智能體都是利己的，所以它們不一定會選擇共同合作達到高回報，而可能選擇回報更穩(wěn)定的單獨行為（即便獲得的回報較少）。還有一個重要因素是不確定性，一種不確定性來自對環(huán)境和對其它智能體的有限的知識，這種不確定性還可以用概率模型應(yīng)對，但也有一種更麻煩的不確定性來自某些環(huán)境相關(guān)的因素，很難用建模的方式處理。
而在MCAC這樣需要形成系列決策的環(huán)境中更會放大這些困難。首先因為除了短期回報之外，還要考慮長期回報，所以在變化的環(huán)境中必須考慮當前的行動可能帶來的未來影響。另一個關(guān)鍵特性是有限的學(xué)習(xí)次數(shù)，Minecraft中的一輪動作通常要花好幾秒，要學(xué)到一個高效的策略也就很花時間。
所以團隊分成了下面幾步來應(yīng)對。
首先分析游戲環(huán)境，找到環(huán)境的關(guān)鍵難點和游戲規(guī)則沒有揭示的特性。
比如游戲規(guī)則并沒有給出小豬的行為模式，而它的行為模式顯然又很重要。在記錄了一萬步行動后，他們繪制出了小豬位置的分布圖，如下圖。
最中間的格子是小豬的初始位置，a、b、c三張圖分別對應(yīng)參賽選手的智能體剛做出行動的那一刻、做出行動1秒鐘后、以及做出行動3秒鐘后的位置。
從圖中他們發(fā)現(xiàn)：1，小豬和智能體的行動規(guī)則不一樣，智能體走一步的時候，小豬可以走好幾個格子，甚至還能轉(zhuǎn)彎；2，小豬往每個方向走的概率是相同的；3，參賽選手智能體兩個行動間的時間越久，小豬位置移動的概率就越高。
這給他們帶來一個有幫助的想法，如果小豬當前在一個抓不住的位置，那就可以等幾秒鐘，等待它走到能抓住的位置了再讓智能體行動。
對于比賽提供的藍色的智能體，如前文所述它有25%的概率是隨機的、75%的概率是專注的；同時團隊發(fā)現(xiàn)，觀察藍色智能體的行為也有25%左右的錯誤率。如果忽略了這種觀察帶來的不確定性就很麻煩。
這就引出了第二步，提出了一種新的智能體類型假說，用來處理這種類型的不確定性以及觀察動作的不確定性。
他們設(shè)計了一個智能體類型假說框架用于更新對藍色智能體的類型的判斷，他們建立的方法能抵抗觀察動作帶來的不確定性。其中用到了泛化貝葉斯方法，并用雙曲正切函數(shù)壓縮類型判斷的更新因子作為抵抗觀察錯誤的方法。
第三步，提出了一種新的Q-learning框架。
這是用來學(xué)習(xí)每一類型的智能體對應(yīng)的不同最優(yōu)合作策略。首先對“狀態(tài) - 行動”的對應(yīng)關(guān)系進行抽象提取，發(fā)現(xiàn)其實只有智能體、小豬和出口之間的空間對行動決策有影響，就顯著減小了原本巨大的行動空間。然后，相比于傳統(tǒng)Q-learning中的Q值先用隨機值初始化再花很多時間訓(xùn)練，HogRider團隊用了一個熱啟動的方法初始化，通過人類的推理過程形成決策樹。如下圖。訓(xùn)練時也分別為另一個智能體是隨機或?qū)Ｗ⒌那闆r訓(xùn)練出不同的Q-函數(shù)，集成在Q-learning框架中。
進一步地，他們還證明，當學(xué)習(xí)嘗試的次數(shù)有限時，一直在整個行動空間內(nèi)做隨機探索是非常低效的（“ε-貪婪”），有時候甚至?xí)恋K找到最優(yōu)策略，尤其是當找到的策略樹已經(jīng)不錯的時候。所以他們提出了一個“活躍的 ε-貪婪”方法，以（1 - ε）的概率選擇現(xiàn)有策略，以 ε 的概率嘗試新的策略；如果帶來的表現(xiàn)提升概率大于認為設(shè)定的50%，就更新策略。這樣在“執(zhí)行現(xiàn)有策略”和“尋找更好策略”之間比以往方法取得更好的平衡。
首先看比賽分數(shù)。得分最高的5支隊伍分數(shù)如圖，每局平均分數(shù)（越高越好）和變化幅度（分數(shù)波動/平均分數(shù)，越低越好）方面，HogRider分別領(lǐng)先第二名13%和21%。這表明HogRider在優(yōu)化程度和穩(wěn)定性方面都表現(xiàn)很好。
模型中選擇的一些具體方法也進行了單項驗證。比如第二步中更新對藍色智能體的判斷的方法，泛化貝葉斯+雙曲正切限幅的準確率和平均得分就比傳統(tǒng)貝葉斯方法高不少。
與專注的藍色智能體協(xié)作時，帶有熱啟動初始化的Q-Learning得分更高，學(xué)習(xí)曲線也收斂得更快
對于“活躍的 ε-貪婪”方法，通過學(xué)習(xí)曲線可以看到，淺藍色線代表的“ε-貪婪”方法果然出現(xiàn)了表現(xiàn)下降，“活躍的 ε-貪婪”方法則可以保證在訓(xùn)練過程中表現(xiàn)總是在進步的。驗證曲線更明顯地體現(xiàn)了“活躍的 ε-貪婪”方法的優(yōu)秀性。
HogRider團隊還邀請了一些在讀博士生嘗試這個游戲，結(jié)果HogRider模型的表現(xiàn)比人的表現(xiàn)還要好不少，平均分數(shù)和變化幅度分別領(lǐng)先28%和29%。
論文中HogRider團隊也分享了他們的經(jīng)驗教訓(xùn)，以供其它研究人員或者比賽團隊參考。
首先，在開頭的時候一定要深入了解要解決的問題。HogRider團隊在設(shè)計智能體類型的集成框架和新的Q-Learning方法前經(jīng)過了漫長的摸索，一開始他們選擇的不區(qū)分智能體類別的Q-Learning只有非常糟糕的表現(xiàn)，畢竟要解決的問題確實會出現(xiàn)不同的特點，也有非常多的不確定性。前沿的算法固然是解決問題的有力工具，但認真了解問題的基礎(chǔ)特征才能確保自己走的是正確的方向。并且，要解決面向應(yīng)用的問題，最終的方案往往是多種技術(shù)的結(jié)合體，而不能指望單獨用某一種復(fù)雜的方法就可以一次搞定。
其次，人類的直覺可以幫助把機器表現(xiàn)提升到新的高度。團隊成員們一開始打算用DQN而不是Q-Learning，它雖然有良好的Q函數(shù)表達能力，但參數(shù)化的Q函數(shù)無法初始化。有一些用了DQN的團隊也是表現(xiàn)很糟糕。這種時候，帶有人類的推理能力幫助的Q-Learning就展現(xiàn)出了巨大優(yōu)勢，這種初始化方式也可以用在更多背景知識可以幫助利用人類推理能力的地方。
最后，當發(fā)現(xiàn)新的隱含屬性后，模型和解決方案算法都應(yīng)當跟著持續(xù)地更新。在比賽過程中，算法幾乎編寫完畢的時候團隊才發(fā)現(xiàn)觀察另一個智能體的動作原來是有一定出錯的比例的，這時候他們沒有偷懶，向算法中的傳統(tǒng)貝葉斯方法中增加了兩項額外的適配，也對算法表現(xiàn)帶來了顯著的提升。
在對游戲結(jié)構(gòu)的細致探索之后，HogRider團隊結(jié)合了高效的智能體類型判斷方法，以及帶有熱啟動的新型Q-Learning（并運用了狀態(tài)-動作空間的抽象化和新的搜索策略），造就了HogRider的優(yōu)秀表現(xiàn)。
在MCAC后，未來更有挑戰(zhàn)的研究方向是兩個完全不知道對方特點的智能體如何協(xié)作，以及開發(fā)能夠泛化到不同環(huán)境中的算法，這種時候智能體需要把離線學(xué)習(xí)和在線學(xué)習(xí)相結(jié)合，以及融合更多強化學(xué)習(xí)的方法。這都需要研究者們繼續(xù)努力，也還有更多有趣的新發(fā)現(xiàn)在前方等著大家發(fā)現(xiàn)。
雷鋒網(wǎng) AI 科技評論編譯。
GitHub地址：https://github.com/Haishion/HogRider
雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
