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