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

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

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

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

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

使用 GraphStream 庫模擬多智能體系統(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)榭偟闹�識(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)困難甚至是不可能的�！筂oravec（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://www.jiqizhixin.com/articles/why-coding-multi-agent-systems-is-hard

 

標(biāo)簽： 搜索 通信

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。