人工智能已經(jīng)在圍棋、圖像識(shí)別和語音識(shí)別等領(lǐng)域?qū)崿F(xiàn)了超越人類專家的水平失息，但今天看來譬淳，智能化的機(jī)器還離我們很遠(yuǎn)档址。要想實(shí)現(xiàn)通用智能，AI 智能體必須學(xué)習(xí)如何在共享環(huán)境中與「他人」進(jìn)行互動(dòng)：這就是多智能體強(qiáng)化學(xué)習(xí)面臨的挑戰(zhàn)邻梆。
本文將通過地圖尋寶問題為例守伸，向你簡(jiǎn)要介紹多智能體系統(tǒng)實(shí)施時(shí)的困難程度及其原因。
「研究人工智能三十五年來的主要經(jīng)驗(yàn)是：困難的問題是易解的浦妄，簡(jiǎn)單的問題是難解的尼摹。」Pinker (1994)剂娄，《The Language Instinct》
我之前覺得編寫一個(gè)軟件智能體來收集圖上的寶藏是件簡(jiǎn)單的小事蠢涝。但是我完全錯(cuò)了。編寫出不愚蠢行動(dòng)的智能體實(shí)際上非常困難阅懦。
明確定義的多智能體設(shè)置
「智能體是指任何通過傳感器感知環(huán)境和二、通過效應(yīng)器作用于環(huán)境的事物《ィ」Stuart Russell&Peter Norvig惯吕，《Artificial Intelligence: A Modern Approach》
使用 GraphStream 庫(kù)模擬多智能體系統(tǒng)收集寶藏。
這是一個(gè)簡(jiǎn)單的多智能體問題怕午。讓 n 個(gè)智能體在完全連接的圖上移動(dòng)并收集寶藏废登。智能體的行動(dòng)、感知和溝通受到限制诗轻，它們只能觀察并移動(dòng)到與它們直接相連的節(jié)點(diǎn)钳宪，只能與足夠接近的智能體進(jìn)行通信。
有三種智能體：探險(xiǎn)者扳炬、收集者和無限背包（Infinite-backpack）智能體。探險(xiǎn)者注定要探索地圖搔体，因?yàn)樗鼈儾辉试S收集寶藏恨樟。收集者才可以收集，但它們不能攜帶太多疚俱，并且必須將它們收集的寶藏分發(fā)給無限背包智能體劝术。
智能體的感知有限，但可以記住過去的觀察結(jié)果呆奕。每個(gè)智能體都有自己的世界表征形式养晋、自己的圖（真實(shí)圖的子圖）。智能體的子圖是它們?cè)L問過的所有節(jié)點(diǎn)的記憶梁钾，以及它們?cè)?jīng)見過或走過的邊绳泉。它們必須將此圖傳達(dá)給其他智能體，以便它們都可以共享來自所有子圖的修復(fù)姆泻。
JADE（Java Agent DEvelopement Framework）將用于實(shí)現(xiàn)所謂的「行為」（教程地址：http://jade.tilab.com/doc/tutorials/JADEProgramming-Tutorial-for-beginners.pdf零酪、https://gitlab.com/herpsonc/startJade）冒嫡。在這個(gè)多智能體系統(tǒng)框架中，行為是智能體將要執(zhí)行的一組指令四苇。在每一輪中孝凌，每個(gè)智能體都按順序執(zhí)行每個(gè)行為。
你的目標(biāo)：實(shí)現(xiàn)智能體的行為月腋，使之在一定時(shí)間內(nèi)收集盡可能多的寶藏钠至。
看起來很簡(jiǎn)單，是吧侄非？
（注意：該項(xiàng)目是《多智能體系統(tǒng)簡(jiǎn)介》（ANDROIDE 的一門課程）的一部分奖恰。靈感來自于生存恐怖游戲 Hunt The Wumpus，在該項(xiàng)目的完整版本中寨躁，智能體需要處理四處游蕩的穆碎、可怕的 Wumpus）。
重要的行為
想象兩個(gè)智能體在長(zhǎng)廊中朝相反方向移動(dòng)职恳。圖的每個(gè)節(jié)點(diǎn)上只能有一個(gè)智能體所禀，所以它們必須協(xié)調(diào)行為以避免阻礙別人》徘眨考慮到這種情況色徘，我們必須實(shí)施一個(gè)特定的協(xié)議。
模擬中智能體的沖突：MyExplorerAgent2 擋住了其他兩個(gè)智能體操禀。
協(xié)調(diào)
智能體的感知有限褂策，并且有不同的能力。因此颓屑，合作是必不可少的斤寂。發(fā)生沖突時(shí)，必須應(yīng)用解除該情況的協(xié)議揪惦。它們必須分享自己的子圖遍搞，看看誰更接近高度連接的節(jié)點(diǎn)，并就誰來移動(dòng)達(dá)成一致器腋。
探險(xiǎn)者智能體必須同意誰來探索未知圖形的哪個(gè)部分溪猿，以優(yōu)化它們的移動(dòng)并防止沖突。
信息交換
在多智能體設(shè)置中交換信息以便讓每個(gè)智能體都能獲取全局知識(shí)的過程被稱為 gossip problem纫塌。
例如诊县，假設(shè)集合 {1,2, … ,n} 中的每個(gè)智能體都知道一部分信息，稱為一個(gè)秘密措左。然后依痊，一個(gè)非常簡(jiǎn)單的協(xié)議是讓智能體 1 呼叫 2、3媳荒、......抗悍、n驹饺，并了解它們的秘密。當(dāng) 1 知道所有的秘密時(shí)缴渊，它會(huì)呼叫給 2赏壹、......、n衔沼，告訴它們這些秘密蝌借，這樣每個(gè)智能體都知道所有的秘密了≈敢希總共有 n-1+n-1=2n-2 次呼叫菩佑。實(shí)際上，最佳解決方案需要 2n-4 次呼叫凝化，這與我們的簡(jiǎn)單算法非常接近稍坯。
然而，在我們的問題中搓劫，直到所有節(jié)點(diǎn)都被探索時(shí)才能知曉完整信息瞧哟，這使得算法稍微復(fù)雜一些，因?yàn)榭偟闹R(shí)是動(dòng)態(tài)的（智能體探索的圖越多枪向，它們的知識(shí)總量越多）勤揩。
這時(shí)就出現(xiàn)了優(yōu)化妥協(xié)（optimization compromise）。為了讓全部智能體知道所有秘密秘蛔，這 n 個(gè)智能體之間必須交換消息的最佳數(shù)量是多少陨亡？更多信息意味著更好的全局知識(shí)和更好的協(xié)調(diào)。然而深员，由于有數(shù)千個(gè)智能體和數(shù)百萬個(gè)節(jié)點(diǎn)负蠕，每毫秒發(fā)送數(shù)千條消息的成本遠(yuǎn)遠(yuǎn)無法忽略，成為一個(gè)計(jì)算負(fù)擔(dān)辨液。
異步通信
智能體之間的通信是異步的虐急。由于智能體的執(zhí)行是分布式的，所以沒有全局時(shí)鐘來同步智能體的動(dòng)作滔迈。此外，在交換信息時(shí)被辑，每個(gè)智能體都有一個(gè)郵箱燎悍，其中包含來自其他智能體的郵件，所以通信可能會(huì)延遲盼理。在延遲期間谈山，一個(gè)智能體可能會(huì)移動(dòng)很遠(yuǎn)，并且永遠(yuǎn)不會(huì)回復(fù)原始信息宏怔。
聯(lián)盟形成
聯(lián)盟形成示例（圖源：https://www.slideshare.net/SurSamtani/coalition-formation-and-price-of-anarchy-in-cournot-oligopolies）
某些目標(biāo)不能單獨(dú)實(shí)現(xiàn)（比如抬起重物）奏路。因此畴椰，智能體可能會(huì)同意組成一組智能體，稱為聯(lián)盟（coalition）鸽粉，來實(shí)現(xiàn)共同目標(biāo)斜脂。
有了具備三種不同必要技能（探索、收集和積累）的智能體触机，一個(gè)至少包括三個(gè)智能體的聯(lián)盟才會(huì)形成帚戳。因此，必須實(shí)施創(chuàng)建和更新聯(lián)盟的協(xié)議儡首∑危可以使用 Shapley 值（由智能體聯(lián)盟創(chuàng)造的剩余額）來確定哪些聯(lián)盟是最有價(jià)值的。
即使是在簡(jiǎn)單的問題設(shè)置中蔬胯，有幾個(gè)障礙出現(xiàn)得非扯怨快，算法的復(fù)雜性似乎是無法克服的氛濒。當(dāng)嘗試構(gòu)建行為類似人類的 AI 算法時(shí)产场，這是一個(gè)反復(fù)出現(xiàn)的現(xiàn)象。
讓 AI 執(zhí)行簡(jiǎn)單的行為是困難的
「要讓計(jì)算機(jī)如成人般地做智力測(cè)試或下棋是相對(duì)容易的泼橘，但是要讓它們有如一歲小孩般的感知和行動(dòng)能力卻是相當(dāng)困難甚至是不可能的涝动。」Moravec（1988）炬灭，《Mind Children》
如果我們用人類替代智能體醋粟，我相信他們很快就會(huì)明白如何在這個(gè)游戲中取勝，他們會(huì)傳達(dá)他們?cè)趫D中所看到的信息重归，并形成聯(lián)盟來收集最多的寶藏米愿。然而，對(duì)智能體實(shí)施嚴(yán)格的行為準(zhǔn)則卻是非常困難的鼻吮。
莫拉維克悖論：
對(duì)人類來說容易的事對(duì)機(jī)器來說卻難以置信地困難育苟。
說到下象棋，AI 表現(xiàn)出了超人類的水平椎木。但是對(duì)于基本的人類行為违柏，例如行走或協(xié)調(diào)行動(dòng)來探索地圖，人工智能算法卻出奇地困難香椎。
國(guó)際象棋大師加里·卡斯帕羅夫曾在《Deep Thinking》中寫道：任何足夠先進(jìn)的算法都不難在同時(shí)進(jìn)行的比賽中擊敗 20 名頂級(jí)棋手漱竖。但是沒有 AI（機(jī)器人）可以在擁擠的酒吧中四處走動(dòng)和自行移動(dòng)棋子。
來源：https://www.youtube.com/watch?v=adFd0f7K46w
機(jī)器學(xué)習(xí)在非常特定的情況下工作
但是你可能會(huì)問為什么我們不使用最新的機(jī)器學(xué)習(xí)（ML）算法來解決我們的問題呢畜伐？......ML-only 算法只能被用于特定的任務(wù)馍惹。
是的，強(qiáng)化學(xué)習(xí)（RL）算法非常流行，可以解決超難的問題万矾，例如在 Atari 游戲或圍棋中展現(xiàn)出超人類的水平悼吱。但是這些游戲都是具備小數(shù)據(jù)輸入的全可視性游戲，這與我們的尋寶問題并不相同良狈，因?yàn)榈貓D在開始時(shí)并不完全可見后添。
（圖注）來源：http://deep%20reinforcement%20learning%20doesn%27t%20work%20yet/（Feb. 2018）
但是，OpenAI 不是在多智能體系統(tǒng)上们颜，用機(jī)器學(xué)習(xí)算法在 Dota 2 的 5 vs 5 中戰(zhàn)勝了人類嗎吕朵？你可能會(huì)問。
是的窥突，當(dāng)在 Dota 2 1 vs 1 中戰(zhàn)勝世界冠軍時(shí)努溃，OpenAI 展現(xiàn)了令人印象深刻的結(jié)果。但是這主要是因?yàn)樗鼈儚?qiáng)大的計(jì)算能力阻问，并不是人工智能的突破梧税。
它們的目標(biāo)是利用一個(gè)包含 580 萬場(chǎng)比賽的數(shù)據(jù)集在 5 vs 5 比賽中獲勝。所以称近，它們似乎正在使用完全機(jī)器學(xué)習(xí)方法（從人類游戲中學(xué)習(xí)）研究多智能體問題第队，并且似乎缺少多智能體系統(tǒng)的自上而下方法。
智能體不會(huì)推斷和概括刨秆。純機(jī)器學(xué)習(xí)可用于單個(gè)智能體或完全可觀察的系統(tǒng)凳谦，但是多智能體系統(tǒng)不是一個(gè)完全已知的世界，必須采用一個(gè)更普遍的方法衡未。
我們不知道如何實(shí)現(xiàn)可擴(kuò)展行為
在只有兩個(gè)智能體在走廊上朝相反方向走的時(shí)候尸执，我們遇到了一個(gè)問題。實(shí)施協(xié)議來處理這一特定問題是可能的缓醋。
但是如果是 100 個(gè)智能體在具備 400 個(gè)節(jié)點(diǎn)的地圖上呢如失？
少數(shù)智能體的硬編碼功能與多智能體系統(tǒng)的可擴(kuò)展和可泛化實(shí)現(xiàn)之間存在差距。
需要做什么
經(jīng)過研究送粱，必須開發(fā)特定的多智能體協(xié)議來解決這類問題褪贵。沒有先驗(yàn)知識(shí)的學(xué)習(xí)不會(huì)教授智能體如何溝通，因?yàn)樗阉骺臻g太大抗俄。純數(shù)據(jù)驅(qū)動(dòng)的方法不會(huì)帶來任何結(jié)果脆丁。
結(jié)論
實(shí)現(xiàn)一個(gè)解決尋寶問題的算法比看起來要困難得多。構(gòu)思能夠解決簡(jiǎn)單問題的多智能體系統(tǒng)絕非易事动雹。機(jī)器學(xué)習(xí)算法在過去十年中取得了巨大成果偎快，但僅憑機(jī)器學(xué)習(xí)無法解決所有的人工智能問題。
原文鏈接：https://hackernoon.com/why-coding-multi-agent-systems-is-hard-2064e93e29bb
