善于單挑卻難以協(xié)作，構(gòu)建多智能體AI系統(tǒng)為何如此之難？

人工智能已經(jīng)在、和等領(lǐng)域達到或超越了人類專家的水平，但今天看來，智能化的機器還離我們很遠(yuǎn)。要想實現(xiàn)通用智能，AI 智能體必須學(xué)習(xí)如何在共享環(huán)境中與「他人」進行互動：這就是多智能體強化學(xué)習(xí)面臨的挑戰(zhàn)。

本文將通過地圖尋寶問題為例，向你簡要介紹多智能體系統(tǒng)實施時的困難程度及其原因。

「研究人工智能三十五年來的主要經(jīng)驗是：困難的問題是易解的，簡單的問題是難解的。」Pinker (1994)，《The Language Instinct》

我之前覺得編寫一個軟件智能體來收集圖上的寶藏是件簡單的小事。但是我完全錯了。編寫出不愚蠢行動的智能體實際上非常困難。

明確定義的多智能體設(shè)置

「智能體是指任何通過傳感器感知環(huán)境、通過效應(yīng)器作用于環(huán)境的事物。」Stuart Russell&Peter Norvig，《Artificial Intelligence: A Modern Approach》

使用 GraphStream 庫模擬多智能體系統(tǒng)收集寶藏。

這是一個簡單的多智能體問題。讓 n 個智能體在完全連接的圖上移動并收集寶藏。智能體的行動、感知和溝通受到限制，它們只能觀察并移動到與它們直接相連的節(jié)點，只能與足夠接近的智能體進行通信。

有三種智能體：探險者、收集者和無限背包(Infinite-backpack)智能體。探險者注定要探索地圖，因為它們不允許收集寶藏。收集者才可以收集，但它們不能攜帶太多，并且必須將它們收集的寶藏分發(fā)給無限背包智能體。

智能體的感知有限，但可以記住過去的觀察結(jié)果。每個智能體都有自己的世界表征形式、自己的圖(真實圖的子圖)。智能體的子圖是它們訪問過的所有節(jié)點的記憶，以及它們曾經(jīng)見過或走過的邊。它們必須將此圖傳達給其他智能體，以便它們都可以共享來自所有子圖的修復(fù)。

JADE(Java Agent DEvelopement Framework)將用于實現(xiàn)所謂的「行為」(教程地址：http://jade.tilab.com/doc/tutorials/JADEProgramming-Tutorial-for-beginners.pdf、https://gitlab.com/herpsonc/startJade)。在這個多智能體系統(tǒng)框架中，行為是智能體將要執(zhí)行的一組指令。在每一輪中，每個智能體都按順序執(zhí)行每個行為。

你的目標(biāo)：實現(xiàn)智能體的行為，使之在一定時間內(nèi)收集盡可能多的寶藏。

看起來很簡單，是吧?

(注意：該項目是《多智能體系統(tǒng)簡介》(ANDROIDE 的一門課程)的一部分。靈感來自于生存恐怖游戲 Hunt The Wumpus，在該項目的完整版本中，智能體需要處理四處游蕩的、可怕的 Wumpus)。

重要的行為

想象兩個智能體在長廊中朝相反方向移動。圖的每個節(jié)點上只能有一個智能體，所以它們必須協(xié)調(diào)行為以避免阻礙別人?？紤]到這種情況，我們必須實施一個特定的協(xié)議。

模擬中智能體的沖突：MyExplorerAgent2 擋住了其他兩個智能體。

協(xié)調(diào)

智能體的感知有限，并且有不同的能力。因此，合作是必不可少的。發(fā)生沖突時，必須應(yīng)用解除該情況的協(xié)議。它們必須分享自己的子圖，看看誰更接近高度連接的節(jié)點，并就誰來移動達成一致。

探險者智能體必須同意誰來探索未知圖形的哪個部分，以優(yōu)化它們的移動并防止沖突。

信息交換

在多智能體設(shè)置中交換信息以便讓每個智能體都能獲取全局知識的過程被稱為 gossip problem。

例如，假設(shè)集合 {1,2, … ,n} 中的每個智能體都知道一部分信息，稱為一個秘密。然后，一個非常簡單的協(xié)議是讓智能體 1 呼叫 2、3、......、n，并了解它們的秘密。當(dāng) 1 知道所有的秘密時，它會呼叫給 2、......、n，告訴它們這些秘密，這樣每個智能體都知道所有的秘密了。總共有 n-1+n-1=2n-2 次呼叫。實際上，最佳解決方案需要 2n-4 次呼叫，這與我們的簡單算法非常接近。

然而，在我們的問題中，直到所有節(jié)點都被探索時才能知曉完整信息，這使得算法稍微復(fù)雜一些，因為總的知識是動態(tài)的(智能體探索的圖越多，它們的知識總量越多)。

這時就出現(xiàn)了優(yōu)化妥協(xié)(optimization compromise)。為了讓全部智能體知道所有秘密，這 n 個智能體之間必須交換消息的最佳數(shù)量是多少?更多信息意味著更好的全局知識和更好的協(xié)調(diào)。然而，由于有數(shù)千個智能體和數(shù)百萬個節(jié)點，每毫秒發(fā)送數(shù)千條消息的成本遠(yuǎn)遠(yuǎn)無法忽略，成為一個計算負(fù)擔(dān)。

異步通信

智能體之間的通信是異步的。由于智能體的執(zhí)行是分布式的，所以沒有全局時鐘來同步智能體的動作。此外，在交換信息時，每個智能體都有一個郵箱，其中包含來自其他智能體的郵件，所以通信可能會延遲。在延遲期間，一個智能體可能會移動很遠(yuǎn)，并且永遠(yuǎn)不會回復(fù)原始信息。

聯(lián)盟形成

某些目標(biāo)不能單獨實現(xiàn)(比如抬起重物)。因此，智能體可能會同意組成一組智能體，稱為聯(lián)盟(coalition)，來實現(xiàn)共同目標(biāo)。

有了具備三種不同必要技能(探索、收集和積累)的智能體，一個至少包括三個智能體的聯(lián)盟才會形成。因此，必須實施創(chuàng)建和更新聯(lián)盟的協(xié)議?？梢允褂?Shapley 值(由智能體聯(lián)盟創(chuàng)造的剩余額)來確定哪些聯(lián)盟是最有價值的。

即使是在簡單的問題設(shè)置中，有幾個障礙出現(xiàn)得非常快，算法的復(fù)雜性似乎是無法克服的。當(dāng)嘗試構(gòu)建行為類似人類的 AI 算法時，這是一個反復(fù)出現(xiàn)的現(xiàn)象。

讓 AI 執(zhí)行簡單的行為是困難的

「要讓計算機如成人般地做智力測試或下棋是相對容易的，但是要讓它們有如一歲小孩般的感知和行動能力卻是相當(dāng)困難甚至是不可能的?！筂oravec(1988)，《Mind Children》

如果我們用人類替代智能體，我相信他們很快就會明白如何在這個游戲中取勝，他們會傳達他們在圖中所看到的信息，并形成聯(lián)盟來收集最多的寶藏。然而，對智能體實施嚴(yán)格的行為準(zhǔn)則卻是非常困難的。

莫拉維克悖論：

對人類來說容易的事對機器來說卻難以置信地困難。

說到下象棋，AI 表現(xiàn)出了超人類的水平。但是對于基本的人類行為，例如行走或協(xié)調(diào)行動來探索地圖，人工智能算法卻出奇地困難。

國際象棋大師加里·卡斯帕羅夫曾在《Deep Thinking》中寫道：任何足夠先進的算法都不難在同時進行的比賽中擊敗 20 名頂級棋手。但是沒有 AI(機器人)可以在擁擠的酒吧中四處走動和自行移動棋子。

機器學(xué)習(xí)在非常特定的情況下工作

但是你可能會問為什么我們不使用最新的機器學(xué)習(xí)(ML)算法來解決我們的問題呢?......ML-only 算法只能被用于特定的任務(wù)。

是的，強化學(xué)習(xí)(RL)算法非常流行，可以解決超難的問題，例如在 Atari 游戲或圍棋中展現(xiàn)出超人類的水平。但是這些游戲都是具備小數(shù)據(jù)輸入的全可視性游戲，這與我們的尋寶問題并不相同，因為地圖在開始時并不完全可見。

但是，OpenAI 不是在多智能體系統(tǒng)上，用機器學(xué)習(xí)算法在 Dota 2 的 5 vs 5 中戰(zhàn)勝了人類嗎?你可能會問。

是的，當(dāng)在 Dota 2 1 vs 1 中戰(zhàn)勝世界冠軍時，OpenAI 展現(xiàn)了令人印象深刻的結(jié)果。但是這主要是因為它們強大的計算能力，并不是人工智能的突破。

它們的目標(biāo)是利用一個包含 580 萬場比賽的數(shù)據(jù)集在 5 vs 5 比賽中獲勝。所以，它們似乎正在使用完全機器學(xué)習(xí)方法(從人類游戲中學(xué)習(xí))研究多智能體問題，并且似乎缺少多智能體系統(tǒng)的自上而下方法。

智能體不會推斷和概括。純機器學(xué)習(xí)可用于單個智能體或完全可觀察的系統(tǒng)，但是多智能體系統(tǒng)不是一個完全已知的世界，必須采用一個更普遍的方法。

我們不知道如何實現(xiàn)可擴展行為

在只有兩個智能體在走廊上朝相反方向走的時候，我們遇到了一個問題。實施協(xié)議來處理這一特定問題是可能的。

但是如果是 100 個智能體在具備 400 個節(jié)點的地圖上呢?

少數(shù)智能體的硬編碼功能與多智能體系統(tǒng)的可擴展和可泛化實現(xiàn)之間存在差距。

需要做什么

經(jīng)過研究，必須開發(fā)特定的多智能體協(xié)議來解決這類問題。沒有先驗知識的學(xué)習(xí)不會教授智能體如何溝通，因為搜索空間太大。純數(shù)據(jù)驅(qū)動的方法不會帶來任何結(jié)果。

結(jié)論

實現(xiàn)一個解決尋寶問題的算法比看起來要困難得多。構(gòu)思能夠解決簡單問題的多智能體系統(tǒng)絕非易事。機器學(xué)習(xí)算法在過去十年中取得了巨大成果，但僅憑機器學(xué)習(xí)無法解決所有的人工智能問題。