善於單挑卻難以協作，構建多智能體AI系統為何如此之難？

人工智慧已經在圍棋、圖像識別和語音識別等領域實現了超越人類專家的水平，但今天看來，智能化的機器還離我們很遠。要想實現通用智能，AI 智能體必須學習如何在共享環境中與「他人」進行互動：這就是多智能體強化學習面臨的挑戰。

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

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

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

明確定義的多智能體設置

「智能體是指任何通過感測器感知環境、通過效應器作用於環境的事物。」Stuart Russell&Peter Norvig，《Artificial Intelligence: A Modern Approach》

使用 GraphStream 庫模擬多智能體系統收集寶藏。

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

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

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

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

你的目標：實現智能體的行為，使之在一定時間內收集儘可能多的寶藏。

看起來很簡單，是吧？

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

重要的行為

想像兩個智能體在長廊中朝相反方向移動。圖的每個節點上只能有一個智能體，所以它們必須協調行為以避免阻礙別人。考慮到這種情況，我們必須實施一個特定的協議。

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

協調

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

探險者智能體必須同意誰來探索未知圖形的哪個部分，以優化它們的移動並防止衝突。

信息交換

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

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

然而，在我們的問題中，直到所有節點都被探索時才能知曉完整信息，這使得演算法稍微複雜一些，因為總的知識是動態的（智能體探索的圖越多，它們的知識總量越多）。

這時就出現了優化妥協（optimization compromise）。為了讓全部智能體知道所有秘密，這 n 個智能體之間必須交換消息的最佳數量是多少？更多信息意味著更好的全局知識和更好的協調。然而，由於有數千個智能體和數百萬個節點，每毫秒發送數千條消息的成本遠遠無法忽略，成為一個計算負擔。

非同步通信

智能體之間的通信是非同步的。由於智能體的執行是分散式的，所以沒有全局時鐘來同步智能體的動作。此外，在交換信息時，每個智能體都有一個郵箱，其中包含來自其他智能體的郵件，所以通信可能會延遲。在延遲期間，一個智能體可能會移動很遠，並且永遠不會回復原始信息。

聯盟形成

聯盟形成示例（圖源：https://www.slideshare.net/SurSamtani/coalition-formation-and-price-of-anarchy-in-cournot-oligopolies）

某些目標不能單獨實現（比如抬起重物）。因此，智能體可能會同意組成一組智能體，稱為聯盟（coalition），來實現共同目標。

有了具備三種不同必要技能（探索、收集和積累）的智能體，一個至少包括三個智能體的聯盟才會形成。因此，必須實施創建和更新聯盟的協議。可以使用 Shapley 值（由智能體聯盟創造的剩餘額）來確定哪些聯盟是最有價值的。

即使是在簡單的問題設置中，有幾個障礙出現得非常快，演算法的複雜性似乎是無法克服的。當嘗試構建行為類似人類的 AI 演算法時，這是一個反覆出現的現象。

讓 AI 執行簡單的行為是困難的

「要讓計算機如成人般地做智力測試或下棋是相對容易的，但是要讓它們有如一歲小孩般的感知和行動能力卻是相當困難甚至是不可能的。」Moravec（1988），《Mind Children》

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

莫拉維克悖論：

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

說到下象棋，AI 表現出了超人類的水平。但是對於基本的人類行為，例如行走或協調行動來探索地圖，人工智慧演算法卻出奇地困難。

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

來源：https://www.youtube.com/watch?v=adFd0f7K46w

機器學習在非常特定的情況下工作

但是你可能會問為什麼我們不使用最新的機器學習（ML）演算法來解決我們的問題呢？......ML-only 演算法只能被用於特定的任務。

是的，強化學習（RL）演算法非常流行，可以解決超難的問題，例如在 Atari 遊戲或圍棋中展現出超人類的水平。但是這些遊戲都是具備小數據輸入的全可視性遊戲，這與我們的尋寶問題並不相同，因為地圖在開始時並不完全可見。

（圖注）來源：http://deep%20reinforcement%20learning%20doesn%27t%20work%20yet/（Feb. 2018）

但是，OpenAI 不是在多智能體系統上，用機器學習演算法在 Dota 2 的 5 vs 5 中戰勝了人類嗎？你可能會問。

是的，當在 Dota 2 1 vs 1 中戰勝世界冠軍時，OpenAI 展現了令人印象深刻的結果。但是這主要是因為它們強大的計算能力，並不是人工智慧的突破。

它們的目標是利用一個包含 580 萬場比賽的數據集在 5 vs 5 比賽中獲勝。所以，它們似乎正在使用完全機器學習方法（從人類遊戲中學習）研究多智能體問題，並且似乎缺少多智能體系統的自上而下方法。

智能體不會推斷和概括。純機器學習可用於單個智能體或完全可觀察的系統，但是多智能體系統不是一個完全已知的世界，必須採用一個更普遍的方法。

我們不知道如何實現可擴展行為

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

但是如果是 100 個智能體在具備 400 個節點的地圖上呢？

少數智能體的硬編碼功能與多智能體系統的可擴展和可泛化實現之間存在差距。

需要做什麼

經過研究，必須開發特定的多智能體協議來解決這類問題。沒有先驗知識的學習不會教授智能體如何溝通，因為搜索空間太大。純數據驅動的方法不會帶來任何結果。

結論

實現一個解決尋寶問題的演算法比看起來要困難得多。構思能夠解決簡單問題的多智能體系統絕非易事。機器學習演算法在過去十年中取得了巨大成果，但僅憑機器學習無法解決所有的人工智慧問題。

原文鏈接：https://hackernoon.com/why-coding-multi-agent-systems-is-hard-2064e93e29bb

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！