馬成宇，劉華平，葛泉波

（1.南通大學(xué) 電氣工程學(xué)院，江蘇 南通 226019;2.清華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系，北京 100084;3.同濟(jì)大學(xué) 電子與信息工程學(xué)院，上海 201804;4.南京信息工程大學(xué) 自動(dòng)化學(xué)院，江蘇 南京 210044）

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

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

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

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

本文提出了一種分布式多目標(biāo)優(yōu)化蒙特卡洛樹(shù)搜索算法框架，不需要提前訓(xùn)練，智能體執(zhí)行一個(gè)動(dòng)作后，利用視覺(jué)觀測(cè)信息結(jié)合場(chǎng)景認(rèn)知實(shí)時(shí)更新對(duì)場(chǎng)景的估計(jì)生成獎(jiǎng)勵(lì)地圖，隨后通過(guò)獎(jiǎng)勵(lì)地圖驅(qū)動(dòng)蒙特卡洛樹(shù)搜索算法重新規(guī)劃智能體的動(dòng)作，如此反復(fù)直到任務(wù)成功或到達(dá)限制條件。

本文結(jié)合了多智能體系統(tǒng)和場(chǎng)景先驗(yàn)知識(shí)的優(yōu)點(diǎn)來(lái)解決未知環(huán)境中的目標(biāo)搜索任務(wù)。主要貢獻(xiàn)如下：

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

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

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

1 問(wèn)題描述

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

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

2 算法框架

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

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

2.1 場(chǎng)景圖譜

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

圖2 場(chǎng)景圖譜示意Fig.2 Scene-aware decentralized multi-agent system for target discovery

2.2 獎(jiǎng)勵(lì)地圖更新

2.2.1 獎(jiǎng)勵(lì)地圖

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

2.2.2 獎(jiǎng)勵(lì)地圖更新機(jī)制

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

圖3 獎(jiǎng)勵(lì)地圖更新過(guò)程Fig.3 Chart of reward map update process

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

在更新第一張獎(jiǎng)勵(lì)地圖的過(guò)程中，如果某個(gè)智能體發(fā)現(xiàn)了與目標(biāo)Oj相關(guān)聯(lián)的物體Oi，那么智能體認(rèn)為Oi的附近可能出現(xiàn)目標(biāo)，并推測(cè)每一個(gè)可導(dǎo)航點(diǎn)出現(xiàn)目標(biāo)的概率。智能體假設(shè)目標(biāo)Oj在關(guān)聯(lián)物體Oi周?chē)霈F(xiàn)的概率呈高斯分布。本文將每一個(gè)導(dǎo)航點(diǎn)出現(xiàn)目標(biāo)Oi的概率分布值作為獎(jiǎng)勵(lì)累加到獎(jiǎng)勵(lì)地圖中：

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

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

圖4 獎(jiǎng)勵(lì)地圖Fig.4 Reward map

2.3 分布式多目標(biāo)蒙特卡洛樹(shù)搜索算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

智能體將當(dāng)前位置作為根節(jié)點(diǎn)擴(kuò)展搜索樹(shù)，多目標(biāo)優(yōu)化蒙特卡洛樹(shù)搜索算法擴(kuò)展搜索樹(shù)的步驟如下:

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

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

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

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

式中：Z 表示當(dāng)前節(jié)點(diǎn)；Zm表示 Z 節(jié)點(diǎn)的第m個(gè)子節(jié)點(diǎn)；R()表示該節(jié)點(diǎn)累積的獎(jiǎng)勵(lì)；V()表示該節(jié)點(diǎn)被訪問(wèn)的次數(shù)。

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

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

帕累托最優(yōu)點(diǎn)集：假設(shè)一個(gè)由點(diǎn)構(gòu)成的集合V，當(dāng)且僅當(dāng)滿足以下條件時(shí)，P*?V稱(chēng)為帕累托最優(yōu)點(diǎn)集：

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

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)置

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

3.2 實(shí)驗(yàn)細(xì)節(jié)

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

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

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

3.3 評(píng)估函數(shù)

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

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

平均路徑長(zhǎng)度被定義為

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

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

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

3.4 實(shí)驗(yàn)結(jié)果

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

表1 實(shí)驗(yàn)1 中4 類(lèi)算法效果對(duì)比Table 1 Comparison of four kinds of algorithms in experiment 1

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

表2 實(shí)驗(yàn)2 中3 類(lèi)算法效果對(duì)比Table 2 Comparison of three kinds of algorithms in experiment 2 %

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

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

圖7 單目標(biāo)搜索定性結(jié)果Fig.7 Qualitative results of a single target search

圖8 多目標(biāo)搜索定性結(jié)果Fig.8 Qualitative results of a multi-target search

4 結(jié)束語(yǔ)

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