基于多機(jī)器人協(xié)作的關(guān)鍵問(wèn)題：有限帶寬和地圖拼接

協(xié)作探索是指由多個(gè)機(jī)器人共同探索未知環(huán)境，機(jī)器人通過(guò)信息交換彼此共享對(duì)方 的環(huán)境信息，并通過(guò)任務(wù)分配機(jī)制協(xié)調(diào)不同機(jī)器人之間的行為，從而提高探索任務(wù)完成的 效率。多機(jī)器人協(xié)作探索的目的取決于其實(shí)際的應(yīng)用，在大部分情況下地圖創(chuàng)建和信息 融合只是協(xié)作探索的中間環(huán)節(jié)，通過(guò)多任務(wù)分配機(jī)制提高探索的效率才是其Z終目的。 原因非常簡(jiǎn)單，如果探索的目的只是創(chuàng)建準(zhǔn)確的環(huán)境地圖而忽略了地圖創(chuàng)建的效率，由單 個(gè)機(jī)器人完成地圖創(chuàng)建功能比由多個(gè)機(jī)器人協(xié)作地圖創(chuàng)建要簡(jiǎn)單得多。

利用多個(gè)移動(dòng)機(jī)器人協(xié)作探索未知環(huán)境與單機(jī)器人探索相比具有明顯的優(yōu)勢(shì)。多機(jī) 器人系統(tǒng)需要更短的時(shí)間去完成同樣的任務(wù)。多機(jī)器人間的信息冗余有助于克服傳感器 信息的不確定性，實(shí)現(xiàn)機(jī)器人更加準(zhǔn)確的定位和創(chuàng)建更加準(zhǔn)確的地圖。多機(jī)器人系統(tǒng)的 容錯(cuò)性使單個(gè)機(jī)器人的功能喪失不會(huì)影響整個(gè)任務(wù)的完成。

國(guó)內(nèi)外學(xué)者重點(diǎn)從兩個(gè)方面對(duì)多機(jī)器人協(xié)作探索進(jìn)行了研究，即目標(biāo)點(diǎn)發(fā)現(xiàn)和多任 務(wù)分配。目標(biāo)點(diǎn)的選取與地圖的表示形式息息相關(guān)，本章從地圖的角度出發(fā)，研究地圖對(duì) 協(xié)作探索效率的影響。多任務(wù)分配即如何選擇合適的探索策略，是協(xié)作探索的核心所 在。

張飛等人針對(duì)提高機(jī)器人對(duì)未知環(huán)境的探索效率需要通過(guò)協(xié)商來(lái)解決多個(gè)機(jī)器 人之間的任務(wù)分配問(wèn)題，提出了改進(jìn)市場(chǎng)法。該方法利用機(jī)器人提交的標(biāo)的信息，采用數(shù) 據(jù)融合方法更新其他機(jī)器人的本地地圖，在連通條件下計(jì)算原先無(wú)法計(jì)算的花費(fèi)，而且未 增加額外的通信量。另外，還提出用目標(biāo)點(diǎn)切換率這一新指標(biāo)來(lái)衡量機(jī)器人之間的協(xié)作 程度。仿真實(shí)驗(yàn)結(jié)果驗(yàn)證了改進(jìn)算法的有效性。

在多機(jī)器人協(xié)作探索中，有限帶寬和地圖拼接是亟待解決的兩個(gè)關(guān)鍵問(wèn)題。

1.有限帶寬

有限帶寬限制了機(jī)器人之間的信息交互，當(dāng)傳遞的信息量較大時(shí)容易引起網(wǎng)絡(luò)堵塞， 降低通信的效率。當(dāng)機(jī)器人之間利用點(diǎn)對(duì)點(diǎn)方式通信時(shí)，單個(gè)機(jī)器人只能與有效工作半 徑內(nèi)的機(jī)器人取得聯(lián)系。有限帶寬問(wèn)題與多機(jī)器人系統(tǒng)結(jié)構(gòu)密切相關(guān)。從控制的角度來(lái) 看，多機(jī)器人系統(tǒng)可分為集中式(Centralized) 、 分 散 式(Decentralized) 和 分 布 式 (Distributed) 三種。集中式控制結(jié)構(gòu)[162通常由一臺(tái)主控機(jī)器人掌握全部環(huán)境信息及各 受控機(jī)器人的信息，它是一種自上而下的層次控制結(jié)構(gòu)。集中式控制結(jié)構(gòu)的優(yōu)點(diǎn)在于系 統(tǒng)的協(xié)調(diào)性較好，實(shí)現(xiàn)起來(lái)較為直觀，但實(shí)時(shí)性、靈活性、容錯(cuò)性、適應(yīng)性等方面較差。另 外，主控機(jī)器人和其他機(jī)器人之間還存在通信瓶頸問(wèn)題，由于主控機(jī)器人承擔(dān)著主要的通 信任務(wù)，通信堵塞和通信延遲在很大程度上影響機(jī)器人協(xié)作探索的實(shí)際效果。并且主控 機(jī)器人失效將會(huì)導(dǎo)致整個(gè)機(jī)器人系統(tǒng)的崩潰。在分散式控制結(jié)構(gòu)[163][164]中，機(jī)器人具有 高度自治能力，自行處理信息、規(guī)劃與決策、執(zhí)行自己的任務(wù)，與其他機(jī)器人相互通信以協(xié) 調(diào)各自行為而沒(méi)有任何集中控制單元。這種結(jié)構(gòu)具有較好的容錯(cuò)能力和可擴(kuò)展性，但對(duì) 通信要求較高，且多邊協(xié)商效率較低，無(wú)法保證全局目標(biāo)的實(shí)現(xiàn)。分布式控制方式165][166介于上述兩者之間，是一種全局上各機(jī)器人等同的自主分布式分層結(jié)構(gòu)而局部 集中的結(jié)構(gòu)方式。這種結(jié)構(gòu)方式是分散式的水平交互和集中式的垂直控制相結(jié)合的產(chǎn) 物，既提高了協(xié)調(diào)效率，又不影響系統(tǒng)的實(shí)時(shí)性、動(dòng)態(tài)性、容錯(cuò)性和可擴(kuò)展性。

通信是機(jī)器人之間進(jìn)行交互和組織的基礎(chǔ)。通過(guò)通信，多機(jī)器人系統(tǒng)中各機(jī)器人了 解其他機(jī)器人的意圖、動(dòng)機(jī)、目標(biāo)、動(dòng)作、策略以及當(dāng)前環(huán)境狀態(tài)等信息，進(jìn)而進(jìn)行有效地 協(xié)商、協(xié)作以完成任務(wù)。機(jī)器人之間通信大致可以分成隱式通信和顯式通信兩種。使用 隱式通信的多機(jī)器人系統(tǒng)通過(guò)外界環(huán)境和自身傳感器來(lái)獲取所需的信息并實(shí)現(xiàn)相互之間 的協(xié)作，機(jī)器人之間沒(méi)有通過(guò)某種共有的規(guī)則和方式進(jìn)行數(shù)據(jù)和信息交換來(lái)實(shí)現(xiàn)特定含 義的信息傳遞[167][1683。隱式通信的優(yōu)點(diǎn)在于不存在通信瓶頸問(wèn)題，但由于各機(jī)器人相互 之間沒(méi)有數(shù)據(jù)、信息的顯式交換，因此難以實(shí)現(xiàn)一些高J的協(xié)作策略�；�于顯式通信的群 機(jī)器人系統(tǒng)利用特定的通信媒介，通過(guò)共有的規(guī)則和方式實(shí)現(xiàn)特定信息的傳遞，因此可以 快速、有效地完成數(shù)據(jù)、信息的轉(zhuǎn)移和交換，實(shí)現(xiàn)許多在隱式通信下無(wú)法完成的高J協(xié)作 策略[1⁶9。多機(jī)器人系統(tǒng)的顯式通信雖然可以強(qiáng)化機(jī)器人之間的協(xié)作關(guān)系，但也存在問(wèn) 題：機(jī)器人的通信過(guò)程延長(zhǎng)了系統(tǒng)對(duì)外界環(huán)境變化的反應(yīng)時(shí)間；通信帶寬的限制使機(jī)器人 之間信息傳遞和交換出現(xiàn)瓶頸；隨著系統(tǒng)中機(jī)器人數(shù)量的增加，通信所需時(shí)間大量增加， 信息傳遞的瓶頸問(wèn)題將會(huì)更加嚴(yán)重。

2.地圖拼接

多機(jī)器人協(xié)作探索中的地圖拼接問(wèn)題是單機(jī)器人地圖創(chuàng)建中數(shù)據(jù)關(guān)聯(lián)的擴(kuò)展。對(duì)于 單機(jī)器人而言，大部分文獻(xiàn)假定機(jī)器人的初始位姿已知，換句話說(shuō)，在未知環(huán)境中可以把 機(jī)器人的初始位姿作為世界坐標(biāo)系的原點(diǎn)。機(jī)器人重新回到地圖中的某一地點(diǎn)，綜合考 慮機(jī)器人的當(dāng)前坐標(biāo)以及當(dāng)前檢測(cè)到的環(huán)境特征，可以實(shí)現(xiàn)傳感器數(shù)據(jù)與相應(yīng)地圖數(shù)據(jù) 的關(guān)聯(lián)。

在多機(jī)器人系統(tǒng)中地圖拼接卻異常困難，原因在于：不同機(jī)器人之間的地圖融合需要 知道其中一個(gè)機(jī)器人在另外一個(gè)機(jī)器人局部地圖中的相對(duì)位姿。Howard和Colleagues 利 用機(jī)器人間的相互檢測(cè)實(shí)現(xiàn)相互定位[170]。這種方法的優(yōu)點(diǎn)是有益于系統(tǒng)的擴(kuò)展，缺點(diǎn) 是地圖拼接后的精度在很大程度上取決于相對(duì)定位的精度，并且在大規(guī)模環(huán)境下，有可能 機(jī)器人之間經(jīng)歷了很長(zhǎng)的探索過(guò)程也無(wú)法相遇，這就很難保證某一機(jī)器人當(dāng)前所在的區(qū) 域是否已經(jīng)被其他機(jī)器人訪問(wèn)過(guò)了。如果機(jī)器人無(wú)法檢測(cè)其他機(jī)器人的相對(duì)位姿，那么 在多機(jī)器人探索未知環(huán)境時(shí)需要從同一地點(diǎn)出發(fā)以獲得統(tǒng)一的世界坐標(biāo)系。

Fox 和 Ko等人也使用相對(duì)位姿檢測(cè)的方法融合共享地圖，機(jī)器人可以從任意地點(diǎn)出 發(fā)，各自創(chuàng)建自己的局部地圖[171]。當(dāng)檢測(cè)到其他機(jī)器人的信息時(shí)，相互交互傳感器數(shù)據(jù) 以獲得較好的假設(shè)，然后采用集結(jié)點(diǎn)方法驗(yàn)證這一假設(shè)。當(dāng)假設(shè)成立時(shí)，機(jī)器人可以拼接 它們的地圖并由此產(chǎn)生協(xié)作策略。該方法的優(yōu)點(diǎn)是不要求機(jī)器人從同一地點(diǎn)出發(fā)，改善 了協(xié)作探索的效率；缺點(diǎn)是需要匹配機(jī)器人傳感器數(shù)據(jù)與其他機(jī)器人的局部地圖數(shù)據(jù)，當(dāng) 環(huán)境規(guī)模很大時(shí)，數(shù)據(jù)關(guān)聯(lián)的效率在很大程度上取決于地圖的表示形式。對(duì)于多機(jī)器人 而言，一種好的地圖表示方法不僅要易于創(chuàng)建和維護(hù)，而且要方便多個(gè)機(jī)器人共同完成。 度量地圖雖然能夠提供環(huán)境準(zhǔn)確的表示，但創(chuàng)建大規(guī)模地圖需要處理大量的數(shù)據(jù)，難以保 證實(shí)時(shí)性。盡管近幾年關(guān)于度量地圖的研究進(jìn)展使大規(guī)模環(huán)境的簡(jiǎn)約表示成為可能，但拓?fù)涞貓D在大規(guī)模地圖創(chuàng)建中無(wú)疑具有d到的優(yōu)勢(shì)。很多學(xué)者因此采用混合地圖的方式 實(shí)現(xiàn)不同地圖的優(yōu)勢(shì)互補(bǔ)�；旌系貓D的生成一般有兩種方式，一種方式是用度量信息注 釋拓?fù)涞貓D，另一種方式是從度量地圖中提取拓?fù)涞貓D。前者拓?fù)涞貓D的節(jié)點(diǎn)包含了節(jié) 點(diǎn)插入?yún)^(qū)域的度量信息，該地圖的缺點(diǎn)是計(jì)算量較大，通常以離線的方式使用。后者一般 采用分割的方法把度量地圖分為不同的區(qū)域，并且使用的地圖通常為柵格地圖。