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

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

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

「研究人工智能三十五年來(lái)的主要經(jīng)驗(yàn)是：困難的問(wèn)題是易解的，簡(jiǎn)單的問(wèn)題是難解的?！筆inker (1994)，《The Language Instinct》

我之前覺(jué)得編寫一個(gè)軟件智能體來(lái)收集圖上的寶藏是件簡(jiǎn)單的小事。但是我完全錯(cuò)了。編寫出不愚蠢行動(dòng)的智能體實(shí)際上非常困難。

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

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

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

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

有三種智能體：探險(xiǎn)者、收集者和無(wú)限背包(Infinite-backpack)智能體。探險(xiǎn)者注定要探索地圖，因?yàn)樗鼈儾辉试S收集寶藏。收集者才可以收集，但它們不能攜帶太多，并且必須將它們收集的寶藏分發(fā)給無(wú)限背包智能體。

智能體的感知有限，但可以記住過(guò)去的觀察結(jié)果。每個(gè)智能體都有自己的世界表征形式、自己的圖(真實(shí)圖的子圖)。智能體的子圖是它們?cè)L問(wèn)過(guò)的所有節(jié)點(diǎn)的記憶，以及它們?cè)?jīng)見(jiàn)過(guò)或走過(guò)的邊。它們必須將此圖傳達(dá)給其他智能體，以便它們都可以共享來(lái)自所有子圖的修復(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)收集盡可能多的寶藏。

看起來(lái)很簡(jiǎn)單，是吧?

(注意：該項(xiàng)目是《多智能體系統(tǒng)簡(jiǎn)介》(ANDROIDE 的一門課程)的一部分。靈感來(lái)自于生存恐怖游戲 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é)議。它們必須分享自己的子圖，看看誰(shuí)更接近高度連接的節(jié)點(diǎn)，并就誰(shuí)來(lái)移動(dòng)達(dá)成一致。

探險(xiǎn)者智能體必須同意誰(shuí)來(lái)探索未知圖形的哪個(gè)部分，以優(yōu)化它們的移動(dòng)并防止沖突。

信息交換

在多智能體設(shè)置中交換信息以便讓每個(gè)智能體都能獲取全局知識(shí)的過(guò)程被稱為 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)單算法非常接近。

然而，在我們的問(wè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ù)百萬(wàn)個(gè)節(jié)點(diǎn)，每毫秒發(fā)送數(shù)千條消息的成本遠(yuǎn)遠(yuǎn)無(wú)法忽略，成為一個(gè)計(jì)算負(fù)擔(dān)。

異步通信

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

聯(lián)盟形成

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

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

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

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

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

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

莫拉維克悖論：

對(duì)人類來(lái)說(shuō)容易的事對(duì)機(jī)器來(lái)說(shuō)卻難以置信地困難。

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

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

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

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

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

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

是的，當(dāng)在 Dota 2 1 vs 1 中戰(zhàn)勝世界冠軍時(shí)，OpenAI 展現(xiàn)了令人印象深刻的結(jié)果。但是這主要是因?yàn)樗鼈儚?qiáng)大的計(jì)算能力，并不是人工智能的突破。

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

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

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

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

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

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

需要做什么

經(jīng)過(guò)研究，必須開(kāi)發(fā)特定的多智能體協(xié)議來(lái)解決這類問(wèn)題。沒(méi)有先驗(yàn)知識(shí)的學(xué)習(xí)不會(huì)教授智能體如何溝通，因?yàn)樗阉骺臻g太大。純數(shù)據(jù)驅(qū)動(dòng)的方法不會(huì)帶來(lái)任何結(jié)果。

結(jié)論

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