場景感知的分布式多智能體目標搜索方法

馬成宇，劉華平，葛泉波

（1.南通大學 電氣工程學院，江蘇 南通 226019;2.清華大學 計算機科學與技術系，北京 100084;3.同濟大學 電子與信息工程學院，上海 201804;4.南京信息工程大學 自動化學院，江蘇 南京 210044）

在視覺語義導航任務中，智能體需要規(guī)劃自己的動作與環(huán)境產(chǎn)生交互，根據(jù)觀測到的視覺信息來導航到目標位置。根據(jù)目標可見還是不可見，該任務可分為可見場景和不可見場景。在不可見場景下，本文將任務稱作目標搜索任務。它在人工智能領域有著非常重要的地位，也有著廣泛的應用前景，包括室內(nèi)搜索、災難救援、倉庫搬運、戰(zhàn)場探索等。同時，視覺語義導航任務也有利于其他具有挑戰(zhàn)性的研究，比如：具身知識問答[1]、視覺語言導航[2]、視覺音頻導航等。

近年來，許多學者開始進行視覺語義導航任務的相關研究，文獻[3]提出了一種利用強化學習使智能體僅通過視覺信息導航到目標位置的方法。文獻[4]提出了一種“面向目標的語義探索”系統(tǒng)來提高智能體的搜索表現(xiàn)。還有一些研究利用強化學習方法作為智能體動作決策模塊，包括DQN[5]、A3C[6]、PPO[7]和分層強化學習方法[8]等。同時也有一些方法致力于利用監(jiān)督學習[9]、遷移學習[10]解決視覺語義導航任務。但是，這些研究基本上都是使用基于學習的方法使智能體找到目標，當搜索場景發(fā)生變化，智能體還需要重新訓練，而且在真實世界中獲取數(shù)據(jù)集的成本很高，這使得方法的可移植性較差，無法在現(xiàn)實場景中應用。同時這些方法都只適用于單智能體，導致算法效率低，容錯性能差，一個智能體執(zhí)行了錯誤動作將導致整個任務失敗。

多智能體協(xié)同技術有著很大的研究潛力，它相比于單智能體有著更高的效率和容錯能力，使得系統(tǒng)可以完成單智能體無法完成的更復雜的任務。多智能體協(xié)同技術有著廣闊的應用場景，比如：工業(yè)生產(chǎn)、軍事對抗、家庭服務、復雜環(huán)境中的搜索救援等。但是一個錯誤的協(xié)作策略反而會降低智能體工作的效率，因此智能體之間的協(xié)作策略是多智能體系統(tǒng)研究的重點。早期的一些研究致力于使用約束條件下尋找最優(yōu)解的方法來規(guī)劃最優(yōu)路徑[11]。隨后，越來越多的研究利用啟發(fā)式算法[12-14]規(guī)劃多智能體動作來最大化對整個環(huán)境的覆蓋率，以此完成搜索[15-16]。但是這些啟發(fā)式算法的收斂速度非常慢，復雜場景下的搜索效率很低。另外，一些學者研究了多智能體的具身任務，比如使兩個智能體在場景中找到目標重物并合作舉起重物[17]、使兩個機器人協(xié)作找到目標并將其搬到另一個位置[18]，但是這些研究仍然使用了基于學習的方法，而且只考慮了兩個智能體的場景，無法適用于更多智能體的任務場景。當智能體在環(huán)境中執(zhí)行目標搜索任務時，關于關聯(lián)性物體的先驗知識可以有效地幫助智能體搜索目標[19-20]。這一類利用場景圖譜增加搜索效率的方法同樣適用于本文的多智能體任務。

蒙特卡洛樹搜索算法(Monte Carlo tree search,MCTS)是一種通過隨機采樣在動作空間建立搜索樹來尋找最優(yōu)決策的方法。它在可以被描述為連續(xù)決策樹的場景中有著十分重要的應用。在早期研究中，蒙特卡洛樹搜索通常作為AI 游戲中的動作決策器，特別是棋類游戲[21]。最近，一些研究開始使用蒙特卡洛樹搜索算法來解決優(yōu)化問題[22-23]、作為智能體的動作規(guī)劃器，文獻[24]提出了一種帕累托蒙特卡洛樹搜索算法來進行多目標優(yōu)化，但是該算法只適用于單智能體。文獻[25]提出了一種分布式多智能體蒙特卡洛樹算法，文獻[26]利用分布式蒙特卡洛樹搜索算法來規(guī)劃機械臂動作完成三維場景重建任務。

本文提出了一種分布式多目標優(yōu)化蒙特卡洛樹搜索算法框架，不需要提前訓練，智能體執(zhí)行一個動作后，利用視覺觀測信息結合場景認知實時更新對場景的估計生成獎勵地圖，隨后通過獎勵地圖驅動蒙特卡洛樹搜索算法重新規(guī)劃智能體的動作，如此反復直到任務成功或到達限制條件。

本文結合了多智能體系統(tǒng)和場景先驗知識的優(yōu)點來解決未知環(huán)境中的目標搜索任務。主要貢獻如下：

1)本文將單智能體視覺語義導航任務擴展到了多智能體系統(tǒng)，并且利用物體間的空間位置關系作為場景先驗知識，使智能體在發(fā)現(xiàn)關聯(lián)性物體時進行有傾向的規(guī)劃，從而提高智能體完成任務的效率。

2)本文提出了一種分布式多目標蒙特卡洛樹搜索算法，在現(xiàn)有的分布式蒙特卡洛樹算法的基礎上結合帕累托最優(yōu)原理，實現(xiàn)分布式多目標優(yōu)化，使得智能體群體在探索關聯(lián)性物體區(qū)域同時兼顧未被探索的區(qū)域。在不需要提前訓練的情況下實時進行規(guī)劃，快速地完成目標搜索任務。

3)本文將算法在Matterport3D 仿真環(huán)境中實現(xiàn)并進行實驗驗證，實驗結果表明本文提出的方法相較于單智能體，效率有著顯著的提升。

1 問題描述

在多智能體視覺語義導航任務中，智能體的目標是通過以自我為中心的視覺觀測信息和目標的類別，與其他智能體協(xié)同發(fā)現(xiàn)并導航到環(huán)境中目標的位置。本文旨在使多智能體系統(tǒng)在環(huán)境中執(zhí)行動作的過程中，根據(jù)觀測到的信息，實時更新對環(huán)境的估計，并且重新規(guī)劃動作以盡可能少的動作數(shù)尋找并導航到目標附近。

本文設定在環(huán)境S中，存在多個不同種類的物體，表示為集合O={O1,O2,···,OK}，其中每一個元素Ok(k=1,2,···,K) 表示一個確定的物體種類，K表示環(huán)境 S中存在的物體種類個數(shù)。假設有N個智能體，在每一個步驟t內(nèi)智能體r在執(zhí)行動作后訪問過的位置以及朝向為pr，除了智能體r之外的所有其他智能體訪問過的位置和朝向為p(r)。本文采用Matterport3D 中的柵格地圖作為導航地圖，所以智能體的動作視為在柵格上的向前一格、向右一格和向左一格3 個動作，因此智能體的控制指令即動作空間為 A，其共有3 個動作，分別為前進25 cm、左轉90°后前進25 cm、右轉90°后前進25 cm。在不同的場景下，也可以采用其他導航方法，如Navmesh 方法，此情況下智能體動作空間中的動作分別為發(fā)送指令移動到與所有該智能體所在導航點相鄰的導航點坐標處。所有智能體的動作集合為a={a1,a2,···,aN}，a(r)表示除了智能體r之外的所有智能體的動作，即a(r)=aar。集合表示智能體在步驟t觀測到的關聯(lián)性物體信息，集合表示其他智能體觀測到的關聯(lián)性物體信息。任務中目標的種類記為Oj∈O。多智能體的目標是在盡可能少的動作數(shù)下，在環(huán)境中找到種類為Oj的物體。

2 算法框架

本文提出的模型由3 個主要模塊組成：關聯(lián)物體匹配模塊，獎勵地圖更新模塊，分布式多目標蒙特卡洛樹搜索動作規(guī)劃模塊。如圖1 所示，智能體在接收到輸入目標種類后，根據(jù)場景圖譜得到與目標存在關聯(lián)性的物體種類。智能體執(zhí)行動作后得到視覺觀測，并判斷是否檢測到關聯(lián)性物體，之后將觀測信息以及自身的位置發(fā)送給其他智能體，同時接收其他智能體的相關信息并根據(jù)更新獎勵地圖。最后分布式多目標優(yōu)化蒙特卡洛樹搜索動作規(guī)劃模塊根據(jù)獎勵地圖重新對智能體進行動作規(guī)劃。智能體之間的協(xié)作分為兩個階段：第一階段智能體在生成獎勵地圖時考慮其他機器人的動作信息來更新對環(huán)境獎勵的估計，第二階段智能體在多目標優(yōu)化蒙特卡洛樹搜索過程中MCTS 模擬階段的獎勵計算時考慮到了其他機器人的動作。

圖1 本文算法框架Fig.1 Algorithm framework of this paper

2.1 場景圖譜

本文將場景先驗知識以無向圖的形式表現(xiàn)，場景圖譜G={B,E}，B中的節(jié)點表示不同的物體種類，邊E表示兩個類別物體之間特殊的位置關系。本文從視覺基因組數(shù)據(jù)集[27]中抽取場景中存在的物體種類之間的關系。該數(shù)據(jù)集包括了100 000 多張圖片，每一張圖片中平均有21 種物體，18 種屬性，18 對物體之間的關系。本文從中抽取在Matterport3D 數(shù)據(jù)集中存在的所有的物體種類之間的關系來表示場景先驗知識圖譜，并記錄各個物體之間出現(xiàn)關系的頻率。圖2 是場景圖譜示意圖，圖中圓表示物體，線表示物體之間的空間關系。此外，由于本文的場景圖譜是從數(shù)據(jù)集中直接提取的物體之間普適關系，所以不用提前進行預訓練。

圖2 場景圖譜示意Fig.2 Scene-aware decentralized multi-agent system for target discovery

2.2 獎勵地圖更新

2.2.1 獎勵地圖

本文根據(jù)Matterport3D 數(shù)據(jù)集生成搜索場景的占用地圖，并且利用每一個步驟智能體執(zhí)行動作后得到的觀測信息來產(chǎn)生對環(huán)境的估計。本文根據(jù)兩種不同的機制對場景進行估計進而產(chǎn)生兩種獎勵地圖，假設獎勵地圖Mreward為一個2×L×W的矩陣，其中L和W表示場景的長度和寬度，矩陣中的每一個元素表示環(huán)境中25 cm×25 cm 的方格。

2.2.2 獎勵地圖更新機制

本節(jié)將介紹獎勵地圖的更新機制，在大部分搜索任務中，目標之間都會存在一定的關聯(lián)性。比如椅子通常在桌子旁邊。本文將這些先驗知識輸入到多智能體系統(tǒng)中，用以對場景進行估計并更新獎勵地圖，獎勵地圖更新流程見圖3。

圖3 獎勵地圖更新過程Fig.3 Chart of reward map update process

智能體在搜索的過程中，首先根據(jù)現(xiàn)有的信息對Matterport3D 中場景柵格地圖上的每一個可導航點即對評估每一個柵格的獎勵值更新獎勵，其中單個柵格大小為25 cm×25 cm，所有場景大小都在150×150 柵格之內(nèi)。

在更新第一張獎勵地圖的過程中，如果某個智能體發(fā)現(xiàn)了與目標Oj相關聯(lián)的物體Oi，那么智能體認為Oi的附近可能出現(xiàn)目標，并推測每一個可導航點出現(xiàn)目標的概率。智能體假設目標Oj在關聯(lián)物體Oi周圍出現(xiàn)的概率呈高斯分布。本文將每一個導航點出現(xiàn)目標Oi的概率分布值作為獎勵累加到獎勵地圖中：

式中：pnav表示導航點在地圖中的坐標；σi表示物體Oi與目標Oj之間關聯(lián)性的強弱，該參數(shù)由兩個物體關系在視覺基因組數(shù)據(jù)集中出現(xiàn)的頻率決定。智能體在與其他智能體通信交換信息后，利用觀測信息Qt獲取被發(fā)現(xiàn)的關聯(lián)性物體的種類以及坐標，并根據(jù)上述方法更新獎勵地圖1 中各個導航點的獎勵。

同時對于第二張獎勵地圖，本文設定在任務開始時，所有導航點獎勵均為1，隨著步驟的增加，智能體探索過的區(qū)域獎勵會逐漸降低，從而驅動智能體偏向于探索未探索過的區(qū)域，具體更新方式為：統(tǒng)計各個導航點以自身為中心周圍9×9柵格范圍內(nèi)所有導航點的被訪問情況，其自身獎勵為周圍 9×9柵格范圍內(nèi)未被訪問的導航點個數(shù)和范圍內(nèi)所有導航點個數(shù)的比值。智能體在與其他智能體通信交換信息后，利用所有智能體的歷史位置坐標集合p，更新各個可導航點的訪問情況，并根據(jù)上述方法更新獎勵地圖2 中各個導航點的獎勵。如圖4 所示，兩張地圖即為根據(jù)上述方法更新后的獎勵地圖。

圖4 獎勵地圖Fig.4 Reward map

2.3 分布式多目標蒙特卡洛樹搜索算法

本節(jié)將介紹分布式多目標蒙特卡洛樹搜索算法規(guī)劃智能體動作的具體步驟，主要分為兩個部分：分布式智能體系統(tǒng)，多目標優(yōu)化蒙特卡洛樹搜索算法。

2.3.1 分布式智能體系統(tǒng)

在搜索過程中，智能體異步、循環(huán)執(zhí)行以下3 個步驟：1）使用多目標蒙特卡洛樹搜索算法，該算法在考慮到其他智能體動作的情況下增長搜索樹；2）通過決策樹選擇下一步動作ar；3）發(fā)送位置信息pr和觀測信息，接收其他智能體的位置信息p(r)和觀測信息。無論通信是否成功，智能體都會繼續(xù)重復上述3 個步驟直到任務成功或者達到最大步驟數(shù)。其中多智能體系統(tǒng)算法的全局目標函數(shù)f是所有智能體在場景中移動，從獎勵圖中沿路徑采集獎勵向量總和。

本文中單個智能體通過優(yōu)化自己的局部目標函數(shù)fr來優(yōu)化全局目標函數(shù)f達到分布式控制的效果[25]，定義fr為智能體r在環(huán)境中執(zhí)行動作ar的全局目標函數(shù)值與執(zhí)行無獎勵動作a之間的差值：

2.3.2 多目標優(yōu)化蒙特卡洛樹搜索算法

智能體使用多目標優(yōu)化蒙特卡洛樹搜索算法[24]規(guī)劃最優(yōu)動作。在智能體每一個步驟擴展的搜索樹中，搜索樹的節(jié)點代表了智能體在地圖中的位置，邊代表了智能體的動作，由于智能體有3 個動作，所以每一個節(jié)點可以擴展3 個子節(jié)點。在模擬的過程中，獎勵向量通過采集兩張獎勵地圖中的獎勵獲得，并且根據(jù)帕累托最優(yōu)原理選擇節(jié)點。

帕累托原理：假設Xm是與選擇m相關聯(lián)的D維向量，表示第m個選擇，Xm,d是它的第d個元素。當且僅當滿足以下條件可以稱第m個選擇比其他選擇n更好，即m支配n，表示為m?n：

1)Xm中的任何元素都不小于Xn中相應位置的元素，即 ?d=1,2,···,D,Xm,d≥Xn,d；

2)Xm中至少有一個元素大于Xn中相應位置的元素，即 ?d∈{1,2,···,D},Xm,d＞Xn,d。

如果只滿足第一個條件，則稱m弱支配n，表示為m?n。而如果存在一個元素d1使得Xm,d1＞Xn,d1，同時存在另一個元素d2使得Xm,d2＜Xn,d2，則稱m和n不可比較，即m||n。

本文用兩種不同的策略更新兩張獎勵地圖，即D=2，則多目標優(yōu)化需要解決以下最大化問題:

式中：ar表示智能體r的動作；A表示智能體的動作空間；分別表示智能體r在執(zhí)行動作ar后，根據(jù)獎勵地圖1 和獎勵地圖2 獲得的局部目標函數(shù)值。

如圖5 所示，在搜索過程中，智能體根據(jù)當前對環(huán)境的估計所生成的獎勵地圖，利用多目標優(yōu)化蒙特卡洛樹搜索算法規(guī)劃動作，當智能體沿著路徑行進時，不斷利用深度相機對場景進行觀測，并且與其他智能體通信交換信息。之后根據(jù)觀測信息重新對環(huán)境進行估計并更新獎勵地圖。圖5 中，c是最大模擬次數(shù)，asim為模擬過程中隨機選擇的動作。

圖5 多目標優(yōu)化蒙特卡洛樹搜索示意Fig.5 Schematic diagram of multi-objective optimization Monte Carlo tree search

智能體將當前位置作為根節(jié)點擴展搜索樹，多目標優(yōu)化蒙特卡洛樹搜索算法擴展搜索樹的步驟如下:

選擇：算法從根節(jié)點開始訪問，逐步利用每一個子節(jié)點的帕累托置信上限向量，選出其中的帕累托最優(yōu)點集，再根據(jù)智能體的偏向選擇當前節(jié)點的某一個子節(jié)點作為下一個訪問的節(jié)點直到訪問到某個可以被擴展的節(jié)點處。

擴展：在可擴展節(jié)點處選擇未被擴展的動作，得到智能體執(zhí)行動作后的位置作為子節(jié)點。

模擬：根據(jù)預先定義好的策略，從新擴展的該節(jié)點進行模擬。在本文的目標搜索任務中，策略被設定為隨機執(zhí)行動作。智能體收集在獎勵地圖 Mreward中采集到的相應路徑的獎勵向量值，并且該獎勵值通過局部目標函數(shù)fr計算獲得。

回溯：在進行模擬之后，得到的獎勵被回溯累加到訪問該節(jié)點之前，選擇和擴展步驟訪問過的節(jié)點上。在本文算法中，搜索樹的每一個節(jié)點都保存了它被訪問的次數(shù)以及累積的通過模擬獲得的獎勵向量值。并且利用式(1)[24]計算該節(jié)點的帕累托置信上限相量 ：

式中：Z 表示當前節(jié)點；Zm表示 Z 節(jié)點的第m個子節(jié)點；R()表示該節(jié)點累積的獎勵；V()表示該節(jié)點被訪問的次數(shù)。

智能體循環(huán)執(zhí)行上述4 個步驟直到達到最大迭代次數(shù)，擴展完畢后算法選擇訪問次數(shù)最多的節(jié)點的邊作為動作。

在蒙特卡洛樹搜索算法中，每一個節(jié)點的置信上限都是標量，選擇節(jié)點時都是選擇置信上限最大的節(jié)點作為下一個訪問節(jié)點，而本文方法所形成的置信上限是一個向量，代表了對場景的兩種不同的估計：將關聯(lián)性物體周圍的區(qū)域作為感興趣區(qū)域，將未被智能體探索過的區(qū)域作為感興趣區(qū)域。這導致了智能體在動作規(guī)劃中需要考慮兩種不同的策略：探索和利用。本文利用帕累托最優(yōu)原理，從所有子節(jié)點的置信上限向量中選擇出帕累托最優(yōu)點集，帕累托最優(yōu)點集中的節(jié)點不可比較，不會被另一個節(jié)點支配。之后根據(jù)智能體不同的偏好來選擇下一個訪問的節(jié)點。這樣可以達到在搜索過程中，完成智能體之間的合作，確保探索和利用策略之間的平衡。

帕累托最優(yōu)點集：假設一個由點構成的集合V，當且僅當滿足以下條件時，P*?V稱為帕累托最優(yōu)點集：

智能體在擴展搜索樹時的節(jié)點選擇過程中，首先計算每個子節(jié)點的帕累托置信上限向量，然后使用生成的帕累托置信上限向量構建近似帕累托最優(yōu)集，最后根據(jù)智能體的偏好選擇最佳的節(jié)點訪問。在本文實驗中，智能體被設置為在任務初期，偏向于訪問獎勵地圖1 中獎勵較高的區(qū)域來探索關聯(lián)性物體周圍的區(qū)域，隨著動作數(shù)的增長逐漸偏向于訪問獎勵地圖2 中獎勵較高的區(qū)域來探索之前沒有探索過的區(qū)域，以獲得最大化場景覆蓋率。

3 仿真實驗

3.1 實驗設置

本文將算法在Matterport3D 數(shù)據(jù)集[28]中進行實驗驗證，Matterport3D 數(shù)據(jù)集包括了90 個不同的由真實房間3 維重建生成的場景。本文從中選擇10 個場景來驗證算法。對于目標種類，本文從Matterport3D 數(shù)據(jù)集和視覺基因組數(shù)據(jù)集中出現(xiàn)次數(shù)都比較多的物體種類中選擇6 個物體種類作為目標，其包括椅子、桌子、床、馬桶、電視機、水池。

3.2 實驗細節(jié)

在實驗中，智能體配備了深度攝像機，可以執(zhí)行前進25 cm，左轉90°后前進25 cm，和右轉90°后前進25 cm 三個動作。如果目標和關聯(lián)性物體在智能體的視覺觀測范圍內(nèi)、并且與智能體之間的距離小于1.5 m，視為智能體發(fā)現(xiàn)了該物體。

綜上所述，對于不同目標種類，本文通過兩種不同的實驗設置來驗證算法的有效性。在這兩種實驗中，本文都在10 個場景中各運行100 個驗證輪次共1 000 次實驗。實驗1 在每一個輪次開始前，從床、馬桶、電視機、水池中隨機選擇一類作為目標。當每一個智能體在環(huán)境中進行200 個動作后，如果還沒找到對應種類的目標，則視為該輪次實驗失敗。如果過程中發(fā)現(xiàn)了目標，則視為該輪次實驗成功，進入下一輪次。最后實驗通過成功率以及成功輪次智能體平均路徑長度作為衡量標準。通常來說，在一個場景里會存在許多個某些種類的物體。所以第2 個實驗分別以椅子、桌子作為目標，智能體在執(zhí)行200 個動作后，實驗通過統(tǒng)計所發(fā)現(xiàn)的目標數(shù)量占場景中該目標的總數(shù)量的比重作為算法的衡量標準。同時，本文在定性實驗中展示了在場景中尋找一個電視機和尋找所有電視機的過程。

實驗中，本文設置蒙特卡洛樹搜索算法每次的最大迭代次數(shù)為1 000 次，最大模擬次數(shù)c為5 次。

3.3 評估函數(shù)

在視覺語義導航任務中，一般通過衡量智能體完成任務的成功率以及完成任務時的效率來評價算法的優(yōu)劣。因此本文設置成功率和平均路徑長度作為綜合評價標準。但對于本文的多智能體視覺語義導航任務來說，智能體之間互相協(xié)作在探索和利用之間進行平衡，使得智能體在搜索關聯(lián)性物體附近區(qū)域的同時也會逐漸重視未探索的區(qū)域來增加對場景的覆蓋率。為了更加直觀地體現(xiàn)本文提出的多目標優(yōu)化的效果，本文除綜合評價標準外還設置了第二個評價標準，從而設計了兩個不同的實驗。在實驗1 中，本文使用成功率(ω)，平均路徑長度(θ)兩種評估函數(shù)檢驗算法的效果，成功率被定義為

式中：第i個輪次實驗成功時Ri=1，否則Ri=0；Ntask是實驗總輪次數(shù)量。成功率越高多智能體搜索效果越好。

平均路徑長度被定義為

式中：PLi表示智能體在第i個成功的輪次中，移動的平均路徑長度；Nsuccess表示成功輪次的總數(shù)。平均路徑長度越低多智能體搜索目標的效率越高。

在實驗2 中，本文使用搜索覆蓋率(ρ)作為評估函數(shù)來檢驗算法的效果，搜索覆蓋率被定義為

式中：ρi是智能體在第i個輪次實驗中執(zhí)行200 次動作之后，所發(fā)現(xiàn)的目標數(shù)量占場景中該目標總數(shù)量的比重。ρ越高說明多智能體系統(tǒng)能夠搜索到的目標越多，性能越好。

3.4 實驗結果

實驗1 將本文算法與文獻[25]中的算法、無場景感知先驗知識的算法、隨機算法分別進行比較，實驗結果見表1。實驗1 結果表明，隨著智能體數(shù)量的增加，本文算法與文獻[25]中算法相比較，在智能體數(shù)量為2、3、4 時，本文算法成功率和平均路徑長度都優(yōu)于文獻[25]。隨機方法的平均路徑長度會比其他方法的平均路徑長度短，因為隨機算法使得智能體容易在初始點附近徘徊，只能搜索到初始點附近的目標，較遠的目標基本無法搜索到，成功率低，因此平均路徑長度反而會縮短。而智能體數(shù)量從1 個增加為2 個時，平均路徑長度不縮反長也是因為一個智能體時很難搜索遠處的目標，導致成功率很低。由實驗結果可以看出，本文算法更適用于視覺語義導航任務，本文提出的多目標優(yōu)化蒙特卡洛樹搜索可以有效地提高搜索成功率，而且多智能體系統(tǒng)可以大幅度地提高效率。在相同的條件下，有場景感知先驗知識模塊的模型優(yōu)于無場景感知先驗知識模塊的模型，這說明即使沒有提前訓練的最普適的物體關聯(lián)性場景先驗知識仍然可以有效幫助多智能體系統(tǒng)搜索目標。此外，雖然本文的場景先驗知識總體提高了機器人搜索的成功率以及效率，但是在特別場景下反而會起到減少成功率的反作用，比如在場景中某一與目標相關聯(lián)的物體周圍并沒有目標，而智能體仍然會在其附近搜索。因此隨著場景先驗準確率的提高，智能體整體性能也會有所提高。

表1 實驗1 中4 類算法效果對比Table 1 Comparison of four kinds of algorithms in experiment 1

實驗2 將本文算法與文獻[25]算法、無場景感知先驗知識的本文算法相比較，結果見表2。可以看出，隨著智能體數(shù)量的增加，算法可以在有限的步驟內(nèi)找到更多的桌子或椅子，表現(xiàn)了多智能體系統(tǒng)在多目標搜索任務中的優(yōu)越性。同時文獻[25] 中算法效果低于本文算法，這說明多目標優(yōu)化蒙特卡洛樹搜索算法能夠有效地平衡智能體探索和利用策略，增加了對場景的覆蓋率。圖6 為3 類算法發(fā)現(xiàn)目標時智能體執(zhí)行動作數(shù)分布的比較圖。其中，本文所提方法使得智能體發(fā)現(xiàn)目標的步驟數(shù)相對于無場景感知先驗知識的方法來說，更加集中在前100 步，這說明了場景圖譜可以有效地幫助智能體根據(jù)物體關聯(lián)性快速地找到目標。文獻[25]方法步驟分布比起本文方法雖然相差不大，但是無法保證搜索覆蓋率。

表2 實驗2 中3 類算法效果對比Table 2 Comparison of three kinds of algorithms in experiment 2 %

圖6 3 類算法發(fā)現(xiàn)目標步驟數(shù)分布Fig.6 Distribution of target-discovery steps of three kinds of algorithms

為了更加具體地展現(xiàn)算法的實現(xiàn)過程，本文在Matterport3D 中的“8WUmh-Lawc2A”場景進行實驗定性結果的展示。如圖7 所示，在每一個步驟中，智能體根據(jù)觀測到的信息結合先驗知識推測目標可能出現(xiàn)的區(qū)域并更新獎勵地圖1，同時逐漸減少探索過區(qū)域對應的獎勵地圖2 的獎勵，之后智能體利用蒙特卡洛樹搜索算法規(guī)劃動作探索興趣區(qū)域?？梢钥吹剑谒阉鬟^程中智能體1 已經(jīng)很接近目標，但是視野中沒有發(fā)現(xiàn)目標，當智能體3 發(fā)現(xiàn)了關聯(lián)性物體沙發(fā)后，在獎勵地圖1 上更新了獎勵，客廳變成了興趣區(qū)域，使得智能體1 探索該區(qū)域并找到目標。如圖8 所示，在場景中存在5 個電視機作為目標，實驗目的是在每個智能體移動500 步內(nèi)找到所有的電視機。在搜索過程中，智能體根據(jù)找到的關聯(lián)性物體實時更新獎勵地圖1，同時逐漸減少智能體已經(jīng)探索過的地區(qū)的獎勵地圖2 中的獎勵。隨著步驟的增加，智能體趨向于探索之前沒有探索過的區(qū)域來最大化對場景的覆蓋率，以此盡可能多地找到目標。最終，4 個智能體協(xié)作找到了場景中的所有目標。

圖7 單目標搜索定性結果Fig.7 Qualitative results of a single target search

圖8 多目標搜索定性結果Fig.8 Qualitative results of a multi-target search

4 結束語

仿真實驗結果可得：本文提出的分布式多目標蒙特卡洛樹搜索算法框架適用于室內(nèi)場景的多智能體視覺語義導航任務，無需提前訓練，智能體在場景中實時更新、實時規(guī)劃。相比較于其他文獻的分布式算法、無場景感知先驗知識本文算法、隨機算法，本文提出的主動感知方法對環(huán)境探索的效率更高，覆蓋率更大。同時，由于算法分布式運行，智能體在搜索過程中即使通信沒有成功也可以繼續(xù)進行規(guī)劃，因此有著很強的容錯能力。本文算法僅在Matterport3D 仿真環(huán)境中進行驗證，因此以后可以在真實環(huán)境中實現(xiàn)算法的深入研究，并且可以根據(jù)不同的任務需求，通過其他算法加入對場景先驗的實時更新模塊，從而更好地完成任務。