張 辰，周樂(lè)來(lái)，李貽斌

（1.山東大學(xué)控制科學(xué)與工程學(xué)院，濟(jì)南250061；2.智能無(wú)人系統(tǒng)教育部工程研究中心，濟(jì)南250061）

1 引 言

機(jī)器人在人類生產(chǎn)生活中扮演重要的角色，極大提高了生產(chǎn)效率。隨著機(jī)器人技術(shù)的飛速發(fā)展，多機(jī)器人系統(tǒng)相關(guān)技術(shù)不斷涌現(xiàn)，多機(jī)器人系統(tǒng)逐漸在工農(nóng)業(yè)生產(chǎn)、高危環(huán)境作業(yè)、水下與空間環(huán)境探測(cè)、衛(wèi)星協(xié)同控制等領(lǐng)域大量應(yīng)用。相對(duì)于單機(jī)器人系統(tǒng)而言，多機(jī)器人系統(tǒng)適應(yīng)更加復(fù)雜多變的動(dòng)態(tài)環(huán)境，對(duì)環(huán)境中的干擾和機(jī)器人故障具備更好的魯棒性；通過(guò)多個(gè)結(jié)構(gòu)簡(jiǎn)單、成本較低的機(jī)器人組建團(tuán)隊(duì)，能夠達(dá)到甚至超越成本高昂的單機(jī)器人所能產(chǎn)生的效果；多個(gè)機(jī)器人組成協(xié)作團(tuán)隊(duì)，能夠并行執(zhí)行更加復(fù)雜的分布式任務(wù)，效率更高。因此多機(jī)器人系統(tǒng)及其協(xié)調(diào)控制成為機(jī)器人技術(shù)的研究熱點(diǎn)之一。

多機(jī)器人系統(tǒng)的導(dǎo)航作為一項(xiàng)關(guān)鍵技術(shù)，是多機(jī)器人系統(tǒng)正常執(zhí)行設(shè)計(jì)功能的基礎(chǔ)。多機(jī)器人通過(guò)協(xié)同定位方法，獲取當(dāng)前各機(jī)器人的位置；通過(guò)路徑規(guī)劃方法對(duì)每一個(gè)機(jī)器人的行進(jìn)路徑進(jìn)行規(guī)劃計(jì)算，并完成協(xié)調(diào)控制；通過(guò)任務(wù)分配方法，對(duì)多機(jī)器人多任務(wù)進(jìn)行最優(yōu)化分配，提高整體團(tuán)隊(duì)的協(xié)同效率。

2 多機(jī)器人協(xié)同定位技術(shù)

單一機(jī)器人受限于傳感器種類、感知范圍和信息處理能力，其定位精度有限，且對(duì)于環(huán)境中的擾動(dòng)和自身的故障缺乏魯棒性。多機(jī)器人系統(tǒng)通過(guò)融合各個(gè)機(jī)器人的定位信息，提高機(jī)器人團(tuán)隊(duì)的整體定位精度，增強(qiáng)抗干擾能力和魯棒性。

定位信息的獲取是實(shí)現(xiàn)協(xié)同定位的基礎(chǔ)。目前多機(jī)器人系統(tǒng)可以通過(guò)多種方式獲取環(huán)境信息和機(jī)器人之間的相對(duì)信息，這些方式可以劃分為絕對(duì)式與相對(duì)式兩類［1］。絕對(duì)式定位技術(shù)是通過(guò)計(jì)算實(shí)時(shí)獲取機(jī)器人在環(huán)境中的絕對(duì)位置，與機(jī)器人初始狀態(tài)和歷史信息無(wú)關(guān)。相對(duì)式定位技術(shù)則需要根據(jù)初始狀態(tài)和歷史信息，估計(jì)當(dāng)前的位置，即本地測(cè)量；或者借助某種技術(shù)估算自身相對(duì)于多機(jī)器人團(tuán)隊(duì)中其他機(jī)器人的位置，即外感測(cè)量。根據(jù)測(cè)量的相對(duì)信息種類不同，可分為基于相對(duì)距離、相對(duì)方位、相對(duì)航向等類型［2］。常用的絕對(duì)式和相對(duì)式定位技術(shù)如表1和表2所示。

表1 絕對(duì)式定位技術(shù)Table 1 The absolute positioning technology

表2 相對(duì)式定位技術(shù)Table 2 The relative positioning technology

根據(jù)多機(jī)器人協(xié)同定位的結(jié)構(gòu)，可以分為主從式和并行式兩類。在主從式協(xié)作定位系統(tǒng)中，由攜帶高精度導(dǎo)航傳感器的機(jī)器人作為主節(jié)點(diǎn)，其他攜帶低成本低精度導(dǎo)航傳感器的機(jī)器人作為從節(jié)點(diǎn)。在協(xié)同定位過(guò)程中，主節(jié)點(diǎn)為團(tuán)隊(duì)提供高精度的導(dǎo)航參考信息，從節(jié)點(diǎn)在自身定位基礎(chǔ)上，通過(guò)接收主節(jié)點(diǎn)的導(dǎo)航數(shù)據(jù)，或?qū)χ鞴?jié)點(diǎn)進(jìn)行觀測(cè)獲得相對(duì)位姿數(shù)據(jù)，對(duì)自身定位結(jié)果進(jìn)行校正［3］。主從式結(jié)構(gòu)簡(jiǎn)單，通信拓?fù)涿鞔_，系統(tǒng)成本低，但是對(duì)于主機(jī)器人的定位精度依賴較高，要求主機(jī)器人具備較好的穩(wěn)定性和魯棒性。當(dāng)主機(jī)器人發(fā)生故障時(shí)，容易導(dǎo)致整個(gè)團(tuán)隊(duì)的定位精度下降，甚至定位失敗。

在并行式協(xié)作定位系統(tǒng)中，各個(gè)機(jī)器人搭載相同的傳感設(shè)備，在團(tuán)隊(duì)中地位相同。在定位過(guò)程中，通過(guò)融合各機(jī)器人的定位數(shù)據(jù)，實(shí)現(xiàn)互相校正。并行式結(jié)構(gòu)沒(méi)有主從之分，不依賴于某一個(gè)機(jī)器人的定位精度，在機(jī)器人節(jié)點(diǎn)發(fā)生故障或者通信失敗時(shí)，仍可保證其余個(gè)體的準(zhǔn)確定位，具備更好的魯棒性。但是去中心化的并行網(wǎng)絡(luò)結(jié)構(gòu)拓?fù)鋸?fù)雜，各機(jī)器人之間互相校正機(jī)制容易導(dǎo)致?tīng)顟B(tài)相關(guān)性問(wèn)題，融合算法更為復(fù)雜。

2.1 概率估計(jì)方法

概率估計(jì)方法是將每個(gè)機(jī)器人的位置視為概率分布，通過(guò)對(duì)機(jī)器人的位置進(jìn)行優(yōu)化估計(jì)，獲得各機(jī)器人的準(zhǔn)確定位。常用的概率估計(jì)方法有濾波類方法、極大似然估計(jì)法、最大后驗(yàn)概率估計(jì)法等。

目前常見(jiàn)的基于濾波的多機(jī)器人協(xié)同定位方法包括擴(kuò)展卡爾曼濾波（EKF）［4］、無(wú)跡卡爾曼濾波（UKF）［5］、容積卡爾曼濾波（CKF）［6］、粒子濾波（PF）［7］、信息濾波（IF）［8］方法，以及上述方法的改進(jìn)算法等。

EKF、UKF、CKF是針對(duì)基于高斯假設(shè)的非線性系統(tǒng)狀態(tài)估計(jì)問(wèn)題提出的方法，是在卡爾曼濾波框架下，通過(guò)對(duì)系統(tǒng)非線性的不同處理實(shí)現(xiàn)狀態(tài)估計(jì)。在多機(jī)器人系統(tǒng)中，非線性卡爾曼濾波框架包括以下4 個(gè)步驟：（1）系統(tǒng)建模：分析系統(tǒng)運(yùn)動(dòng)模型，構(gòu)建運(yùn)動(dòng)方程和觀測(cè)方程。（2）時(shí)間更新：依據(jù)前一時(shí)刻的最佳狀態(tài)估計(jì)值，結(jié)合機(jī)器人線速度、角速度等運(yùn)動(dòng)信息，在運(yùn)動(dòng)方程中進(jìn)行一步預(yù)測(cè)，計(jì)算當(dāng)前時(shí)刻機(jī)器人的預(yù)測(cè)位置，并對(duì)預(yù)測(cè)協(xié)方差進(jìn)行一步預(yù)測(cè)。（3）量測(cè)更新：根據(jù)機(jī)器人外部感知獲取的當(dāng)前時(shí)刻相對(duì)數(shù)據(jù)，結(jié)合時(shí)間更新過(guò)程得到的當(dāng)前時(shí)刻預(yù)測(cè)位置，對(duì)機(jī)器人位置進(jìn)行最優(yōu)估計(jì)，并計(jì)算當(dāng)前時(shí)刻的估計(jì)協(xié)方差。（4）循環(huán)（2）、（3）步，遞歸地進(jìn)行最優(yōu)估計(jì)。

基于以上框架，經(jīng)典的EKF算法通過(guò)對(duì)非線性函數(shù)的線性化，將非線性函數(shù)進(jìn)行泰勒展開(kāi)，忽略高階項(xiàng)部分，保留一階項(xiàng)部分以實(shí)現(xiàn)線性化近似。經(jīng)典EKF 算法由于忽略了高階項(xiàng)，引入了線性誤差，容易導(dǎo)致算法發(fā)散。經(jīng)典的UKF算法不再對(duì)非線性函數(shù)進(jìn)行逼近，而是通過(guò)選擇一定數(shù)量的確定的采樣點(diǎn)對(duì)非線性函數(shù)的概率分布進(jìn)行逼近，獲得了更好的精度。CKF 算法基于三階球面徑向準(zhǔn)測(cè)，通過(guò)容積積分近似高斯加權(quán)積分，利用容積點(diǎn)逼近非線性系統(tǒng)的概率分布，是近年來(lái)新出現(xiàn)的一種濾波方法。

與以上三種使用近似思想解決非線性系統(tǒng)估計(jì)問(wèn)題的濾波方法不同，PF 方法拋棄高斯假設(shè)，基于蒙特卡洛法思想，通過(guò)大量的隨機(jī)采樣點(diǎn)對(duì)非線性模型和非高斯分布進(jìn)行模擬。PF 方法理論上能夠適應(yīng)任意形狀的分布，但是需要的粒子數(shù)量巨大，計(jì)算負(fù)擔(dān)較重。

最大后驗(yàn)概率方法通過(guò)最大化后驗(yàn)概率的狀態(tài)位置作為機(jī)器人位置的最佳估計(jì)，來(lái)求解多機(jī)器人定位問(wèn)題。機(jī)器人i通過(guò)本地測(cè)量獲取自身線速度與角速度，組成向量u=[v，ω]T，通過(guò)外感測(cè)量獲取相對(duì)于機(jī)器人j的相對(duì)距離和角度數(shù)據(jù)z=[d，θ]T，通過(guò)迭代方法求解使后驗(yàn)概率函數(shù)P(x|u，z) 取得最大值的，即為機(jī)器人位置的估計(jì)［9］。

極大似然估計(jì)通過(guò)最大化似然函數(shù)的狀態(tài)位姿作為機(jī)器人位姿的估計(jì)［10］。通過(guò)機(jī)器人之間的相對(duì)觀測(cè)結(jié)果和機(jī)器人本地測(cè)量數(shù)據(jù)構(gòu)建似然函數(shù)P(z|x)，通過(guò)求解使似然函數(shù)取得最大值的，作為機(jī)器人位姿的估計(jì)。

2.2 優(yōu)化方法

優(yōu)化方法采用了與濾波方法不同的思想。濾波方法通過(guò)前一時(shí)刻各機(jī)器人的位姿估計(jì)當(dāng)前時(shí)刻各機(jī)器人的位姿。優(yōu)化方法通過(guò)建立約束方程和目標(biāo)函數(shù)，通過(guò)優(yōu)化求解目標(biāo)函數(shù)極值，來(lái)計(jì)算各機(jī)器人的位姿。研究人員提出了一系列的優(yōu)化方法，包括滾動(dòng)時(shí)域法、粒子群優(yōu)化法、梯度下降法［2］等。

滾動(dòng)時(shí)域估計(jì)（Moving Horizon Estimation，MHE）方法近年來(lái)逐漸在許多領(lǐng)域開(kāi)展應(yīng)用，取得了良好的效果。MHE 是一種動(dòng)態(tài)滾動(dòng)式的最優(yōu)估計(jì)方法，通過(guò)建立固定時(shí)間域長(zhǎng)度的優(yōu)化計(jì)算窗口，設(shè)置先入先出的狀態(tài)滾動(dòng)更新機(jī)制，引入多機(jī)器人系統(tǒng)狀態(tài)約束條件，使用時(shí)間窗開(kāi)始時(shí)刻的多機(jī)器人位姿數(shù)據(jù)組成系統(tǒng)狀態(tài)向量、時(shí)間窗內(nèi)各時(shí)刻的狀態(tài)噪聲序列和到達(dá)代價(jià)函數(shù)，構(gòu)建性能指標(biāo)函數(shù)。通過(guò)最小化性能指標(biāo)函數(shù)，估計(jì)時(shí)間窗結(jié)束時(shí)刻的各機(jī)器人的位姿數(shù)據(jù)［11］。MHE 方法的滾動(dòng)時(shí)間窗如圖1所示。由于MHE 方法的實(shí)時(shí)性和動(dòng)態(tài)性特點(diǎn)，算法對(duì)于計(jì)算能力要求較高。

圖1 滾動(dòng)時(shí)間窗口示意圖Fig.1 The moving horizon of MHE

梯度下降法作為一種經(jīng)典的估計(jì)目標(biāo)函數(shù)極小值的算法，近年來(lái)在深度學(xué)習(xí)等領(lǐng)域廣泛應(yīng)用，研究人員也將梯度下降方法引入到多機(jī)器人協(xié)同定位中，對(duì)機(jī)器人的位姿進(jìn)行優(yōu)化求解。測(cè)量每個(gè)機(jī)器人與鄰居機(jī)器人的局部距離信息或相對(duì)方位信息，通過(guò)每個(gè)機(jī)器人的位姿估計(jì)值計(jì)算對(duì)應(yīng)的相對(duì)距離或相對(duì)方位，構(gòu)造測(cè)量值與估計(jì)值的均方差目標(biāo)函數(shù)。通過(guò)梯度下降法求解目標(biāo)函數(shù)的最小值，獲得機(jī)器人位置的最佳估計(jì)［12］。梯度下降法示意圖如圖2所示，其中錨點(diǎn)機(jī)器人用于確定多機(jī)器人團(tuán)隊(duì)的全局坐標(biāo)。

圖2 梯度下降法協(xié)同定位過(guò)程示意圖Fig.2 Co-localization process with gradient descent method

2.3 地圖匹配方法

基于地圖匹配的方法常用于對(duì)無(wú)人飛行器進(jìn)行導(dǎo)航。提前建立飛行器航線經(jīng)過(guò)地區(qū)的地圖，在無(wú)人機(jī)飛行過(guò)程中通過(guò)感知地形地貌，與提前建立的地圖進(jìn)行匹配，并結(jié)合飛行器的慣性導(dǎo)航系統(tǒng)，以確定飛行器當(dāng)前的位置。飛行器可搭載相機(jī)系統(tǒng)，對(duì)地形地貌進(jìn)行拍攝，并與實(shí)景地圖進(jìn)行匹配；或者搭載測(cè)距傳感器，對(duì)地面起伏進(jìn)行建模，并與地圖進(jìn)行匹配。

基于地圖匹配的思想近年來(lái)也在多機(jī)器人協(xié)同定位問(wèn)題中廣泛使用，尤其在空地異構(gòu)機(jī)器人協(xié)同定位中，地圖匹配成為聯(lián)系空地不同視角的橋梁：將無(wú)人機(jī)俯拍視角與地面機(jī)器人平視全景視角進(jìn)行匹配，可以實(shí)現(xiàn)二者的協(xié)同定位。通過(guò)無(wú)人機(jī)單目相機(jī)搜索地面機(jī)器人，并觸發(fā)SLAM，通過(guò)雷達(dá)點(diǎn)云建立地面機(jī)器人周圍2.5D 地圖；地面機(jī)器人搭載全景相機(jī)，將全景圖像中的特征點(diǎn)與2.5D地圖進(jìn)行匹配，以估計(jì)自身在地圖中的位置和朝向［13］。基于地圖匹配的空地協(xié)同定位示意圖如圖3所示。

3 多機(jī)器人路徑規(guī)劃技術(shù)

路徑規(guī)劃是多機(jī)器人團(tuán)隊(duì)實(shí)現(xiàn)移動(dòng)和順利執(zhí)行任務(wù)的關(guān)鍵技術(shù)，相對(duì)于單機(jī)器人路徑規(guī)劃問(wèn)題，多機(jī)器人路徑規(guī)劃問(wèn)題存在以下幾個(gè)特點(diǎn)：（1）機(jī)器人團(tuán)隊(duì)存在更多約束，例如需要保持一定隊(duì)形，或者需要滿足運(yùn)動(dòng)的先后順序約束，即某機(jī)器人的行動(dòng)完成作為另一機(jī)器人開(kāi)始行動(dòng)的條件。（2）機(jī)器人團(tuán)隊(duì)內(nèi)部存在規(guī)劃沖突問(wèn)題，即在執(zhí)行規(guī)劃路徑過(guò)程中兩機(jī)器人可能在同一時(shí)刻到達(dá)同一位置，導(dǎo)致碰撞。因此多機(jī)器人路徑規(guī)劃的研究成為多機(jī)器人系統(tǒng)的研究重點(diǎn)之一。

圖3 基于地圖匹配的空地協(xié)同定位示意圖Fig.3 Air-ground cooperative positioning based on map matching method

多機(jī)器人路徑規(guī)劃技術(shù)可以分為耦合式方法和解耦式方法。耦合式方法是將多機(jī)器人視為一個(gè)整體，將各機(jī)器人的所有自由度整合成一個(gè)多自由度空間，對(duì)其進(jìn)行搜索和規(guī)劃。解耦式方法是對(duì)每個(gè)機(jī)器人進(jìn)行獨(dú)立的路徑規(guī)劃，之后再通過(guò)協(xié)調(diào)方法對(duì)多個(gè)獨(dú)立路徑進(jìn)行協(xié)調(diào)和修改，以解決沖突問(wèn)題。

3.1 耦合式路徑規(guī)劃方法

在耦合方法中，許多單機(jī)器人路徑規(guī)劃的經(jīng)典方法被擴(kuò)展到多機(jī)器人路徑規(guī)劃中。人工勢(shì)場(chǎng)法是機(jī)器人路徑規(guī)劃問(wèn)題的經(jīng)典方法，通過(guò)在機(jī)器人的運(yùn)行空間中構(gòu)建勢(shì)能場(chǎng)，目標(biāo)點(diǎn)對(duì)機(jī)器人產(chǎn)生引力，障礙物對(duì)機(jī)器人以及機(jī)器人之間產(chǎn)生斥力，通過(guò)合力引導(dǎo)機(jī)器人走向目標(biāo)點(diǎn)。由于引入機(jī)器人之間的斥力，人工勢(shì)場(chǎng)法能夠較好地解決多機(jī)沖突問(wèn)題，廣泛應(yīng)用于解決多機(jī)編隊(duì)中的路徑規(guī)劃問(wèn)題［14］。但是在復(fù)雜環(huán)境中容易出現(xiàn)合力為零情況，陷入“死鎖”狀態(tài)，因此研究者提出了多種改進(jìn)方法，通過(guò)加入偏向力使機(jī)器人跳出“死鎖”狀態(tài)，繼續(xù)行進(jìn)。多機(jī)器人通過(guò)人工勢(shì)場(chǎng)法繞過(guò)障礙物的過(guò)程示意圖如圖4所示。

概率類規(guī)劃方法通過(guò)隨機(jī)采樣的方法，在復(fù)雜環(huán)境中規(guī)劃路徑，計(jì)算量小且速度較快，具備概率完備性，尤其適合在高維系統(tǒng)中進(jìn)行可行路徑的規(guī)劃。常見(jiàn)的概率類方法有概率路線圖法（Probabilistic Roadmap，PRM）、快速搜索隨機(jī)樹(shù)（Rapid-exploration Random Tree，RRT）等。將m個(gè)機(jī)器人在某時(shí)刻的位置組合成m維空間的一點(diǎn)（起始點(diǎn)），將m個(gè)目標(biāo)位置組合成m維空間內(nèi)的路徑規(guī)劃目標(biāo)點(diǎn)，通過(guò)對(duì)該m維空間進(jìn)行隨機(jī)采樣，建立隨機(jī)路線圖或生成隨機(jī)擴(kuò)展樹(shù)，建立起始點(diǎn)與目標(biāo)點(diǎn)的連接線路［15］?？焖偎阉麟S機(jī)樹(shù)方法的規(guī)劃示意圖如圖5所示。

圖4 人工勢(shì)場(chǎng)法示意圖Fig.4 Formation control with artificial potential field method

圖5 RRT方法的規(guī)劃過(guò)程Fig.5 The planning process of rrt method

耦合式規(guī)劃方法能夠在全局范圍內(nèi)進(jìn)行優(yōu)化搜索，但是多機(jī)器人組合形成的多自由度空間維度高，尤其對(duì)于機(jī)器人團(tuán)隊(duì)中機(jī)器人數(shù)目較多的情況，計(jì)算和搜索的復(fù)雜度將會(huì)呈指數(shù)增長(zhǎng)，嚴(yán)重影響規(guī)劃的速度和實(shí)時(shí)性。

3.2 解耦式路徑規(guī)劃方法

解耦式方法中，首先對(duì)各機(jī)器人進(jìn)行單獨(dú)的路徑規(guī)劃，再通過(guò)協(xié)調(diào)算法將發(fā)生沖突的機(jī)器人路徑進(jìn)行調(diào)整。因此經(jīng)典的面向單機(jī)器人的路徑規(guī)劃方法可以用于生成每個(gè)機(jī)器人的路徑。

研究者們提出了許多不同的路徑協(xié)調(diào)方法。M*算法［16］使用亞維展開(kāi)框架，以經(jīng)典的A*算法作為底層路徑規(guī)劃器。在多機(jī)器人系統(tǒng)空間中創(chuàng)建一維的搜索空間，通過(guò)A*算法為每個(gè)機(jī)器人單獨(dú)規(guī)劃最優(yōu)路徑；在規(guī)劃過(guò)程中若發(fā)現(xiàn)兩機(jī)器人碰撞，則局部增加搜索空間的維數(shù)，以協(xié)調(diào)機(jī)器人之間的運(yùn)動(dòng)。

基于沖突的搜索算法［17］（Conflict Based Search，CBS），采用兩級(jí)算法結(jié)構(gòu)，底層使用A*算法對(duì)單機(jī)器人進(jìn)行路徑規(guī)劃搜索，在頂層建立基于單個(gè)機(jī)器人的時(shí)間、位置約束的二叉約束樹(shù)。當(dāng)多機(jī)器人之間的路徑產(chǎn)生沖突時(shí)，對(duì)樹(shù)執(zhí)行節(jié)點(diǎn)搜索，實(shí)現(xiàn)沖突調(diào)節(jié)。

基于保留區(qū)域的方法［18-19］考慮了機(jī)器人在未來(lái)幾個(gè)時(shí)間步的運(yùn)動(dòng)過(guò)程，在柵格地圖中對(duì)單個(gè)機(jī)器人進(jìn)行獨(dú)立路徑規(guī)劃，同時(shí)根據(jù)運(yùn)動(dòng)方向計(jì)算未來(lái)幾個(gè)時(shí)間步內(nèi)機(jī)器人將要到達(dá)的柵格位置，稱為保留區(qū)域。當(dāng)兩機(jī)器人保留區(qū)域重疊，則形成多機(jī)器人沖突描述，交由中央模塊進(jìn)行任務(wù)分配和協(xié)調(diào)。

以上多機(jī)器人路徑規(guī)劃方法都是針對(duì)短生命周期過(guò)程的一次路徑規(guī)劃，機(jī)器人數(shù)量和目標(biāo)點(diǎn)數(shù)量基本對(duì)等且固定不變，各個(gè)機(jī)器人到達(dá)各自的目標(biāo)點(diǎn)后，路徑規(guī)劃過(guò)程隨即結(jié)束。針對(duì)短生命周期的路徑規(guī)劃方法不具備持續(xù)性和時(shí)變性問(wèn)題，有研究者提出了長(zhǎng)生命周期的路徑規(guī)劃概念［20］。長(zhǎng)生命周期的路徑規(guī)劃方法面向變化的多目標(biāo)點(diǎn)，團(tuán)隊(duì)中某機(jī)器人在到達(dá)某一目標(biāo)點(diǎn)后會(huì)再次獲得新的目標(biāo)點(diǎn)任務(wù)，規(guī)劃過(guò)程長(zhǎng)期運(yùn)行，提高了方法的動(dòng)態(tài)性，更加符合實(shí)際應(yīng)用需求。

解耦式方法將路徑規(guī)劃分散到單機(jī)器人尺度，通過(guò)協(xié)調(diào)算法調(diào)解沖突，問(wèn)題復(fù)雜度較低，動(dòng)態(tài)性較好。但是解耦式方法難以獲得全局最優(yōu)解，容易陷入局部極小值或者陷入“死鎖”狀態(tài)。

4 多機(jī)器人任務(wù)分配技術(shù)

任務(wù)分配技術(shù)是多機(jī)器人協(xié)同控制系統(tǒng)中的關(guān)鍵技術(shù)之一，在傳感器覆蓋問(wèn)題、兵器多目標(biāo)打擊、以及無(wú)人機(jī)多點(diǎn)任務(wù)分配等場(chǎng)景中處于基礎(chǔ)性的地位。任務(wù)分配問(wèn)題是組合優(yōu)化問(wèn)題，目標(biāo)是找到機(jī)器人和任務(wù)之間的最佳匹配，實(shí)現(xiàn)完成任務(wù)耗時(shí)最少，機(jī)器人整體移動(dòng)路徑長(zhǎng)度最短，機(jī)器人團(tuán)隊(duì)總體能量消耗最低等優(yōu)化目標(biāo)，最大限度地提高團(tuán)隊(duì)的整體效能。

任務(wù)分配問(wèn)題的解決方法主要有基于行為的分配方法、市場(chǎng)機(jī)制方法、群體智能方法等。

4.1 基于行為的分配方法

基于行為的任務(wù)分配算法［21］是較早提出的任務(wù)分配方法之一，通過(guò)找到一個(gè)具有最大效用的機(jī)器人-任務(wù)對(duì)，將任務(wù)分配給機(jī)器人。

典型的基于行為的任務(wù)分配方法包括ALLIANCE 方法、本地資格廣播（Broadcast of Local Eligibility，BIE）方法等。對(duì)于每個(gè)任務(wù)，每個(gè)機(jī)器人都有能夠執(zhí)行該任務(wù)的行為。針對(duì)對(duì)應(yīng)的任務(wù)，每個(gè)機(jī)器人對(duì)每個(gè)任務(wù)維持效用評(píng)估，用于描述自身解決該任務(wù)的效能和成本。在運(yùn)行過(guò)程中，各機(jī)器人定期進(jìn)行任務(wù)重新分配的規(guī)劃，每個(gè)機(jī)器人向其他機(jī)器人傳播它對(duì)每個(gè)任務(wù)的效用值。在收到其他機(jī)器人的效用后，每個(gè)機(jī)器人中執(zhí)行貪婪策略，針對(duì)一個(gè)任務(wù)，將其自身的效用評(píng)價(jià)與其他每個(gè)機(jī)器人的效用評(píng)價(jià)進(jìn)行比較，選擇自身效用最高的為高優(yōu)先級(jí)任務(wù)，實(shí)現(xiàn)任務(wù)分配。

在效用值傳播過(guò)程中，借助通信的傳播方法對(duì)于通信的要求較高，研究人員提出了相對(duì)觀測(cè)的分散計(jì)算方式：通過(guò)維持包含“默許”和“耐心”的離散效能評(píng)估方法，當(dāng)某機(jī)器人正在執(zhí)行一項(xiàng)任務(wù)時(shí)，隨著時(shí)間的推移，其自身對(duì)于該任務(wù)的默許值逐漸增加，而其他機(jī)器人對(duì)于該任務(wù)的耐心程度下降，導(dǎo)致該機(jī)器人對(duì)于該任務(wù)的效用評(píng)價(jià)逐漸降低。各個(gè)機(jī)器人在通信心跳幀作用下同步且獨(dú)立地刷新各機(jī)器人的效能評(píng)估，降低通信壓力。

基于行為的方法實(shí)時(shí)性、容錯(cuò)性和魯棒性好，但只能求得局部最優(yōu)解，無(wú)法實(shí)現(xiàn)全局的優(yōu)化求解。

4.2 市場(chǎng)機(jī)制方法

市場(chǎng)機(jī)制方法［22-23］是一種基于協(xié)商思想的任務(wù)分配方法，多機(jī)器人系統(tǒng)在某種協(xié)議基礎(chǔ)上通過(guò)機(jī)器人之間的相互協(xié)商、談判來(lái)完成任務(wù)分配。

市場(chǎng)機(jī)制方法包括多種分配方法，其中最典型的是基于合同網(wǎng)協(xié)議的方法。該方法基于市場(chǎng)拍賣(mài)模型，主要包括任務(wù)發(fā)布、任務(wù)投標(biāo)和任務(wù)分配三個(gè)階段。首先對(duì)任務(wù)和機(jī)器人的能力進(jìn)行建模，建立機(jī)器人的能力集和環(huán)境中的任務(wù)集。

在任務(wù)發(fā)布階段，當(dāng)系統(tǒng)被指定一個(gè)新的任務(wù)，或某機(jī)器人根據(jù)當(dāng)前局勢(shì)發(fā)現(xiàn)一個(gè)新的任務(wù)時(shí)，任務(wù)中心通過(guò)通信網(wǎng)絡(luò)將任務(wù)廣播至每一個(gè)機(jī)器人中。在任務(wù)投標(biāo)階段，接收到任務(wù)的機(jī)器人根據(jù)自身的能力，對(duì)任務(wù)進(jìn)行評(píng)價(jià)，計(jì)算完成任務(wù)需要花費(fèi)的代價(jià)，以及預(yù)計(jì)的完成時(shí)間等要素，組合成投標(biāo)信息發(fā)送給任務(wù)中心。在任務(wù)分配階段，任務(wù)中心收到各機(jī)器人的投標(biāo)信息之后，根據(jù)投標(biāo)信息中的要素計(jì)算各機(jī)器人或機(jī)器人組的投標(biāo)收益，選擇投標(biāo)收益最高的機(jī)器人或機(jī)器人組作為該任務(wù)的贏家，向其分配任務(wù)。

基于市場(chǎng)的方法適合于在任務(wù)和機(jī)器人狀態(tài)可知的中小規(guī)模異構(gòu)機(jī)器人中進(jìn)行分布式問(wèn)題的協(xié)作求解，能夠?qū)崿F(xiàn)全局最優(yōu)任務(wù)分配。

4.3 群體智能方法

群體智能（Swarm Intelligence，SI）是仿照自然界生物體的自組織行為，通過(guò)對(duì)鳥(niǎo)群、蟻群、蜂群等生物群體系統(tǒng)的行為進(jìn)行研究和模擬，提出的用于解決群機(jī)器人行為自組織和規(guī)劃的智能方法。該類方法沒(méi)有中央控制單元，由相互作用的簡(jiǎn)單獨(dú)立自主個(gè)體，按照一定的規(guī)律，通過(guò)涌現(xiàn)的方法求解某一類問(wèn)題。

在群體智能方法中，蟻群算法［24］是最為典型的代表之一，在各個(gè)領(lǐng)域獲得了廣泛的應(yīng)用。通過(guò)模仿自然界螞蟻的覓食行為，對(duì)機(jī)器人的任務(wù)空間進(jìn)行優(yōu)化求解。機(jī)器人從完成某任務(wù)轉(zhuǎn)移到下一個(gè)任務(wù)過(guò)程中，根據(jù)完成任務(wù)的代價(jià)，在兩任務(wù)之間的路徑上留下不同濃度的信息素。通過(guò)信息素累加和蒸發(fā)因子作用，更新路徑上的信息素濃度。信息素濃度影響任務(wù)轉(zhuǎn)移概率函數(shù)的值，機(jī)器人根據(jù)轉(zhuǎn)移概率函數(shù)選擇下一步將要執(zhí)行的任務(wù)，直到所有任務(wù)被多機(jī)器人團(tuán)隊(duì)執(zhí)行完成。

4.4 人機(jī)共融的多機(jī)器人任務(wù)分配方法

近年來(lái)，許多基于人機(jī)協(xié)同的多機(jī)器人協(xié)作系統(tǒng)出現(xiàn)，多機(jī)器人系統(tǒng)不再僅僅由機(jī)器人構(gòu)成，人在閉環(huán)的人-多異構(gòu)機(jī)器人協(xié)作模式成為新的研究熱點(diǎn)。

2018年，Chowdhury等［25］提出了一種基于距離、剩余能量、機(jī)器人的能力和可用性的異構(gòu)機(jī)器人選擇算法，通過(guò)建立任務(wù)請(qǐng)求-任務(wù)應(yīng)答-代價(jià)評(píng)估-擇優(yōu)分配-故障實(shí)時(shí)監(jiān)測(cè)，在網(wǎng)絡(luò)協(xié)議層集成本地和非本地任務(wù)分配，解決如何有效地將給定的人工任務(wù)分配給合適的機(jī)器人、如何低成本求解任務(wù)分配和非本地任務(wù)分配的問(wèn)題。

Anima等［26］研究了基于層次任務(wù)計(jì)劃的人機(jī)協(xié)同任務(wù)執(zhí)行問(wèn)題，將人-機(jī)器人協(xié)同任務(wù)以樹(shù)狀結(jié)構(gòu)表示，并針對(duì)重疊和非重疊子任務(wù)的沖突進(jìn)行了不同處理，提高了人-機(jī)器人團(tuán)隊(duì)中任務(wù)的動(dòng)態(tài)分配能力和不同環(huán)境條件下的機(jī)會(huì)式任務(wù)執(zhí)行能力。

Talebpour 等［27］提出了一種在多機(jī)器人任務(wù)分配環(huán)境下的基于風(fēng)險(xiǎn)的自適應(yīng)重新規(guī)劃策略，基于社會(huì)風(fēng)險(xiǎn)和人類運(yùn)動(dòng)預(yù)測(cè)不確定性的變化，實(shí)時(shí)動(dòng)態(tài)的調(diào)整任務(wù)分配，以處理局部感知的局限性和不可預(yù)測(cè)的人類行為。

以上的成果能夠?qū)⑷诉@一因素加入到多機(jī)器人任務(wù)分配過(guò)程中，但人仍在任務(wù)分配回環(huán)以外，通過(guò)指令或任務(wù)下達(dá)的方式對(duì)多機(jī)器人任務(wù)分配形成干預(yù)。伴隨著機(jī)器人任務(wù)的復(fù)雜化，尤其在多機(jī)器人協(xié)作團(tuán)隊(duì)在有人存在的復(fù)雜環(huán)境中作業(yè)，作為增強(qiáng)人機(jī)共融協(xié)作環(huán)境適應(yīng)能力，提高人-群機(jī)器人協(xié)作工作效率的關(guān)鍵，人機(jī)共融的多機(jī)器人任務(wù)分配研究具有重要意義。

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

本文針對(duì)多機(jī)器人協(xié)同導(dǎo)航技術(shù)的研究進(jìn)行了綜合評(píng)述，重點(diǎn)針對(duì)多機(jī)器人系統(tǒng)導(dǎo)航過(guò)程中涉及到的三個(gè)關(guān)鍵問(wèn)題：協(xié)同定位、路徑規(guī)劃和任務(wù)分配問(wèn)題，分析了多機(jī)器人系統(tǒng)的特點(diǎn)和面臨的挑戰(zhàn)。總結(jié)并比較了多機(jī)器人定位數(shù)據(jù)獲取技術(shù)，重點(diǎn)評(píng)述了協(xié)同定位算法和技術(shù)的種類及特點(diǎn)；總結(jié)了多機(jī)器人路徑規(guī)劃的方法，以及避免機(jī)器人之間沖突的協(xié)調(diào)方法；總結(jié)并比較了多機(jī)器人任務(wù)分配常用的方法，針對(duì)有人存在的多機(jī)器人協(xié)同環(huán)境，總結(jié)了現(xiàn)有的方法。

多機(jī)器人協(xié)同導(dǎo)航技術(shù)經(jīng)過(guò)多年的發(fā)展，已經(jīng)取得巨大的進(jìn)步。但仍面臨一些挑戰(zhàn)：

（1）如何實(shí)現(xiàn)更加高效可靠的多機(jī)器人通信、更加簡(jiǎn)潔的系統(tǒng)結(jié)構(gòu)、更加智能的協(xié)調(diào)策略等基礎(chǔ)技術(shù)，仍需進(jìn)一步研究。

（2）目前的多機(jī)器人協(xié)同導(dǎo)航技術(shù)涉及的機(jī)器人數(shù)量較少，在大規(guī)模多機(jī)器人協(xié)同方面成果較少，存在一定困難。如何擴(kuò)展機(jī)器人團(tuán)隊(duì)數(shù)量需要深入研究。

（3）如何將人這一要素引入多機(jī)器人協(xié)同導(dǎo)航過(guò)程中，突破人以簡(jiǎn)單命令下達(dá)或參數(shù)設(shè)定方式對(duì)多機(jī)器人導(dǎo)航過(guò)程進(jìn)行干預(yù)的現(xiàn)狀，實(shí)現(xiàn)真正的人在回環(huán)內(nèi)的協(xié)同控制，具有重要的研究?jī)r(jià)值。