多機(jī)器人編隊(duì)方法理論基礎(chǔ)概述目錄TOC\o"1-3"\h\u9788多機(jī)器人編隊(duì)方法理論基礎(chǔ)概述 177511.1領(lǐng)航者跟隨法（Leader-follower法） 375671.2虛擬結(jié)構(gòu)法 4251971.3圖論法 684241.4基于行為法 8編隊(duì)行為是自然界常見(jiàn)的生物集群現(xiàn)象REF_Ref15784\r\h[2]。群居生物在運(yùn)動(dòng)過(guò)程中保持一定的隊(duì)形，可以大大提高每個(gè)個(gè)體存活率和尋找食物的效率，降低單體的體能消耗，提高其活動(dòng)范圍（如圖2-1所示）。圖2-1自然界編隊(duì)集群行為受自然界動(dòng)物的編隊(duì)和集群行為諸多優(yōu)點(diǎn)如任務(wù)執(zhí)行效率高、運(yùn)動(dòng)過(guò)程穩(wěn)定、降低能量消耗等的啟發(fā)，在人類(lèi)生活中也越來(lái)越多地應(yīng)用了集群編隊(duì)（如圖2-2所示）。軍事領(lǐng)域上，多種不同機(jī)型的飛機(jī)混合編隊(duì)可以通過(guò)任務(wù)分配細(xì)化，專(zhuān)精尖的執(zhí)行既定作戰(zhàn)任務(wù)，可以在軍事護(hù)航、協(xié)同一體化作戰(zhàn)、空中加油等復(fù)雜任務(wù)中發(fā)揮不可替代的作用；由各類(lèi)軍艦、潛艇組成的航母編隊(duì)可以大幅提高航母編隊(duì)的作戰(zhàn)能力和戰(zhàn)場(chǎng)存活能力，發(fā)揮出大規(guī)模集群作戰(zhàn)的戰(zhàn)略威懾力；在人們?nèi)粘？梢?jiàn)的交通運(yùn)輸領(lǐng)域，車(chē)輛自覺(jué)地形成的編隊(duì)可以大幅提高交通通行率以及道路利用率。不僅如此，高速公路上車(chē)輛編隊(duì)的形成可以有效降低風(fēng)阻從而減少能源消耗。在多機(jī)器人研究領(lǐng)域，專(zhuān)業(yè)技術(shù)人員也越來(lái)越多地將多智能機(jī)器人群體編隊(duì)技術(shù)應(yīng)用到礦物資源勘探、事故災(zāi)害救援等領(lǐng)域。圖2-2國(guó)慶70周年飛機(jī)編隊(duì)，航母編隊(duì)人們研究多移動(dòng)機(jī)器人編隊(duì)系統(tǒng)的初衷也是由于單個(gè)機(jī)器人上所能搭載的傳感器數(shù)量有限且探測(cè)范圍較小，導(dǎo)致每位“隊(duì)員”數(shù)據(jù)獲取量有限，執(zhí)行任務(wù)能力存在有限性、局限性。通過(guò)多機(jī)器人的編隊(duì)，機(jī)器人之間可相互交流信息，一方面大大減少每個(gè)“隊(duì)員”數(shù)據(jù)的獲取量，另一方面可以增加群體對(duì)外界數(shù)據(jù)的采集，從而提高機(jī)器人群體的整體探測(cè)精度與任務(wù)執(zhí)行能力，提高群體反應(yīng)速度。多移動(dòng)機(jī)器人系統(tǒng)由多個(gè)能力有限的機(jī)器人組成，提高了工作效率與任務(wù)執(zhí)行效率REF_Ref15918\r\h[3]。與單機(jī)器人相比，多機(jī)器人系統(tǒng)具體有如下優(yōu)勢(shì)：（1）環(huán)境適應(yīng)力強(qiáng)：多機(jī)器人系統(tǒng)在靈活性和對(duì)任務(wù)執(zhí)行過(guò)程中的變通性得到了大幅提升。由于多機(jī)器人系統(tǒng)擁有環(huán)境的部分或全局信息，因此能夠維護(hù)、加強(qiáng)和調(diào)整它們的定位模式，以便在有限的時(shí)間內(nèi)完成它們的任務(wù)，適應(yīng)性強(qiáng)。不同編隊(duì)隊(duì)形可以適應(yīng)不同場(chǎng)景，在群體執(zhí)行力和空間分布性上顯著優(yōu)于單個(gè)機(jī)器人。針對(duì)不同的復(fù)雜地形設(shè)計(jì)不同的編隊(duì)策略成為編隊(duì)的重要優(yōu)勢(shì)之一。（2）任務(wù)承受力強(qiáng)：“人多力量大”，一個(gè)大任務(wù)被分配到每個(gè)成員機(jī)器人上，每個(gè)機(jī)器人執(zhí)行大任務(wù)下的子任務(wù)，這就提高了任務(wù)的承載力REF_Ref15957\r\h[4]。每個(gè)機(jī)器人在完成自己部分的工作任務(wù)的同時(shí)，需配合其他機(jī)器人對(duì)總?cè)蝿?wù)負(fù)責(zé)，有效提高任務(wù)完成的效率，更好地解決復(fù)雜度較高的任務(wù)，保證任務(wù)順利完成。（3）魯棒性高REF_Ref15999\r\h[5]：在多機(jī)器人系統(tǒng)中，任務(wù)進(jìn)行了過(guò)程上的劃分，階段性的分配執(zhí)行，由各位子成員共同參與完成，并不由一個(gè)機(jī)器人“說(shuō)了算”。這樣做的好處是，即使群體中一個(gè)成員出現(xiàn)問(wèn)題，可以有其它機(jī)器人接管，交由其他機(jī)器人完成相應(yīng)任務(wù)，不導(dǎo)致整個(gè)任務(wù)的全盤(pán)失敗。且一旦障礙環(huán)境發(fā)生改變，多機(jī)器人避障系統(tǒng)可以更好地調(diào)整適應(yīng)，具有更強(qiáng)的環(huán)境適應(yīng)能力和更高的系統(tǒng)魯棒性。面對(duì)復(fù)雜的任務(wù)和多變的情況，顯然僅僅依靠單個(gè)機(jī)器人的能力是不夠的，需要多機(jī)器人協(xié)同完成，這就不得不考慮到協(xié)同編隊(duì)以及避障的問(wèn)題。多機(jī)器人的協(xié)同編隊(duì)控制問(wèn)題，包含了從形成編隊(duì)隊(duì)形，隊(duì)形的保持，遇障礙隊(duì)形變換這三大關(guān)鍵性問(wèn)題REF_Ref16039\r\h[6]。多機(jī)器人編隊(duì)方法有領(lǐng)航者跟隨法、虛擬結(jié)構(gòu)法、圖論法以及基于行為法等REF_Ref14308\r\h[7]。領(lǐng)航者跟隨法（Leader-follower法）領(lǐng)航者跟隨法（Leader-follower法）編隊(duì)控制方法是多移動(dòng)機(jī)器人系統(tǒng)中最早得以利用的一種編隊(duì)實(shí)現(xiàn)方法。領(lǐng)航者跟隨法的基本思想是在機(jī)器人群體中選定一個(gè)作為多機(jī)器人編隊(duì)的“領(lǐng)航者”REF_Ref17743\r\h[8]，并以此機(jī)器人為基，建立極坐標(biāo)系，編隊(duì)中其他機(jī)器人設(shè)定為跟隨者，可以建立不同的拓?fù)?。跟隨者機(jī)器人根據(jù)編隊(duì)隊(duì)形的不同以一定的相對(duì)距離l和相對(duì)角度ψ跟隨“領(lǐng)航者”運(yùn)動(dòng)，從而保持穩(wěn)定的隊(duì)形。其中領(lǐng)航者既可以是真實(shí)的個(gè)體成員機(jī)器人，也可以是虛擬的領(lǐng)航機(jī)REF_Ref19157\r\h[9]。在編隊(duì)形成及保持過(guò)程中，領(lǐng)航者機(jī)器人的作用是控制整個(gè)機(jī)器人編隊(duì)的前行（如圖2-3所示）。在實(shí)際編隊(duì)行進(jìn)中，需要做到跟隨者機(jī)器人與領(lǐng)航者機(jī)器人之間的實(shí)際距離LLF趨于根據(jù)隊(duì)形要求設(shè)定好的理論間距L，兩者的相對(duì)角度ΨLF趨于理論值Ψ。即實(shí)際距離和實(shí)際方位角要漸進(jìn)穩(wěn)定于期望值。圖2-3領(lǐng)航者跟隨法編隊(duì)模型領(lǐng)航者跟隨法最早于1991年由Wang在文獻(xiàn)REF_Ref20845\r\h[10]提出。在此基礎(chǔ)上Kumar教授及其團(tuán)隊(duì)（GRASP）經(jīng)過(guò)理論探索和實(shí)驗(yàn)探索，在其論述REF_Ref27400\r\h[11]中提出了基于領(lǐng)航者跟隨法的l—ψ和l—l構(gòu)型，通過(guò)仿真實(shí)驗(yàn)和實(shí)地試驗(yàn)得出的結(jié)論也驗(yàn)證了其所提出的編隊(duì)構(gòu)型和控制方法的有效性。HanzhenXiaoREF_Ref27184\r\h[12]等人采用基于神經(jīng)動(dòng)力學(xué)優(yōu)化的非線(xiàn)性模型預(yù)測(cè)控制算法實(shí)現(xiàn)了領(lǐng)航者跟隨法機(jī)器人編隊(duì)，同時(shí)進(jìn)行了編隊(duì)避障的研究。ParkBongSeokREF_Ref28141\r\h[13]等人針對(duì)不確定的非完整移動(dòng)機(jī)器人的主從編隊(duì)跟蹤問(wèn)題，提出了一種基于連通性保持的避障方法，推導(dǎo)了機(jī)器人之間在避障時(shí)保持領(lǐng)航者和跟隨者之間連通性所需的相對(duì)角度，以制定一種新的保持連通性的避障策略。Jadbabaie等證明了如果每一個(gè)跟隨者都與領(lǐng)航者保持跟隨狀態(tài)，那么隨著時(shí)間的推移，跟隨者機(jī)器人的狀態(tài)將趨于領(lǐng)航者的狀態(tài)REF_Ref28164\r\h[14]。國(guó)內(nèi)，南開(kāi)大學(xué)王中林REF_Ref3651\r\h[15]等人研究了基于離散時(shí)間模型的多智能體領(lǐng)航跟隨編隊(duì)控制算法，并分別通過(guò)Matlab仿真和在Amigobot機(jī)器人平臺(tái)上做實(shí)驗(yàn)，驗(yàn)證了該算法的正確性及可行性。領(lǐng)航者跟隨法編隊(duì)控制的優(yōu)點(diǎn)是所需的信息量相對(duì)較少，表現(xiàn)在當(dāng)領(lǐng)航者的運(yùn)動(dòng)狀態(tài)確定后，其余跟隨者就能通過(guò)跟隨領(lǐng)航者來(lái)實(shí)現(xiàn)編隊(duì)控制，而且控制策略較為靈活。其缺點(diǎn)是，一旦領(lǐng)航者出現(xiàn)故障，那么整個(gè)多機(jī)器人系統(tǒng)就會(huì)無(wú)法工作，而且領(lǐng)航者機(jī)器人難以根據(jù)跟隨者機(jī)器人的運(yùn)行狀態(tài)做出相應(yīng)的運(yùn)行狀態(tài)上的調(diào)整，這樣多機(jī)器人系統(tǒng)的魯棒性不強(qiáng)。除此之外，若跟隨者出現(xiàn)網(wǎng)絡(luò)延遲等傳輸延遲問(wèn)題時(shí)也會(huì)導(dǎo)致跟蹤不及時(shí)，進(jìn)而影響到整個(gè)多機(jī)器人編隊(duì)的控制效果REF_Ref3929\r\h[16]。領(lǐng)航者跟隨法是最常用、最成熟的策略。在有限資源的情況下，該方法有著先天的優(yōu)勢(shì)。虛擬結(jié)構(gòu)法早在1997年，M.AnthonyLewis

就給出了虛擬結(jié)構(gòu)的定義REF_Ref4223\r\h[17]，即虛擬結(jié)構(gòu)(VirtualStructure)是元件的集合，例如機(jī)器人，它們彼此之間以及與參考系之間保持(半)剛性幾何關(guān)系。舉例來(lái)講，推箱子問(wèn)題是利用虛擬結(jié)構(gòu)法解決多機(jī)器人協(xié)同編隊(duì)的一個(gè)經(jīng)典演繹。如圖2-4所示，當(dāng)機(jī)器人推動(dòng)一個(gè)盒子在地面做運(yùn)動(dòng)的時(shí)候，要想得到穩(wěn)定的推動(dòng)效果，就要要求多機(jī)器人與盒子保持嚴(yán)格固定的幾何關(guān)系。不嚴(yán)格遵守幾何約束會(huì)導(dǎo)致荷載不均勻，甚至當(dāng)機(jī)器人沿著盒子滑動(dòng)或失去與盒子的聯(lián)系時(shí)會(huì)發(fā)生推動(dòng)失敗。解決這個(gè)問(wèn)題的一種方法是，將多機(jī)器人群體中每個(gè)機(jī)器人想象成是嵌入盒子結(jié)構(gòu)中的粒子。實(shí)際結(jié)構(gòu)中通常機(jī)械施加的約束是由控制策略施加的。多個(gè)機(jī)器人可以利用與箱子的運(yùn)動(dòng)并行性、一致性增強(qiáng)它們的隊(duì)形保持能力。由于每個(gè)機(jī)器人的不論如何運(yùn)動(dòng)，但其與盒子的位置始終保持相對(duì)固定，就好像它們嵌入了這個(gè)箱子一樣。稱(chēng)之為虛擬結(jié)構(gòu)。圖2-4多個(gè)移動(dòng)機(jī)器人推動(dòng)盒子虛擬結(jié)構(gòu)模型中根據(jù)多機(jī)器人編隊(duì)為每個(gè)機(jī)器人設(shè)定了相應(yīng)的虛擬個(gè)體，設(shè)置了一種虛擬框架結(jié)構(gòu)，虛擬個(gè)體的位姿即為實(shí)際機(jī)器人的期望位姿。多機(jī)器人編隊(duì)在整體運(yùn)行時(shí)，雖然每個(gè)機(jī)器人的絕對(duì)坐標(biāo)發(fā)生了變化，但機(jī)器人間的相對(duì)坐標(biāo)卻保持不變。把每個(gè)機(jī)器人看作剛體結(jié)構(gòu)中的一個(gè)固定點(diǎn)，所以只需要知道一個(gè)機(jī)器人的運(yùn)動(dòng)，然后通過(guò)機(jī)器人之間的幾何關(guān)系，就可以推導(dǎo)出編隊(duì)中其他機(jī)器人的運(yùn)動(dòng)狀態(tài)，從而達(dá)到控制編隊(duì)隊(duì)形的效果。在應(yīng)用虛擬結(jié)構(gòu)法編隊(duì)思想時(shí)。首先，依據(jù)任務(wù)所需，提前編排好多機(jī)器人隊(duì)形，采用相應(yīng)的編隊(duì)隊(duì)形結(jié)構(gòu)。接著，通過(guò)形成的整個(gè)隊(duì)形得出每個(gè)機(jī)器人的相對(duì)位置，繼而得出出每個(gè)機(jī)器人應(yīng)該完成的相應(yīng)運(yùn)動(dòng)。最后，為每個(gè)機(jī)器人設(shè)計(jì)合適群體編隊(duì)行為的運(yùn)動(dòng)軌跡。如圖2-5所示，三輛移動(dòng)機(jī)器人依據(jù)三角形虛擬結(jié)構(gòu)，形成三角形編隊(duì)。圖2-5基于虛擬結(jié)構(gòu)的編隊(duì)南京航空航天大學(xué)的何真等人提出了一種基于虛擬結(jié)構(gòu)的分布式編隊(duì)控制方法用于編隊(duì)運(yùn)動(dòng)控制REF_Ref6166\r\h[18]。以虛擬結(jié)構(gòu)為框架，在編隊(duì)控制算法中加入隊(duì)形反饋，使得虛擬結(jié)構(gòu)法設(shè)計(jì)的編隊(duì)控制器既能控制編隊(duì)機(jī)動(dòng)運(yùn)動(dòng)速度，又能在編隊(duì)運(yùn)行過(guò)程中較好地維持設(shè)定的隊(duì)形。實(shí)驗(yàn)證明了該編隊(duì)控制方法的收斂性。針對(duì)無(wú)人機(jī)編隊(duì)控制問(wèn)題，天津大學(xué)的李正平等人提出了一種基于虛擬結(jié)構(gòu)法的非線(xiàn)性魯棒控制算法REF_Ref6365\r\h[19]并基于Lyapunov穩(wěn)定性分析方法證明了閉環(huán)系統(tǒng)的穩(wěn)定性。虛擬結(jié)構(gòu)法的優(yōu)點(diǎn)是降低了任務(wù)分配的難度和工作量，其控制規(guī)律的設(shè)計(jì)通常需要考慮反饋環(huán)節(jié)來(lái)消除編隊(duì)誤差，并且由于其剛性結(jié)構(gòu)，有良好的隊(duì)形反饋，編隊(duì)隊(duì)形形成起來(lái)較為輕松，且編隊(duì)能夠較為迅速的達(dá)到穩(wěn)定。另外易于設(shè)計(jì)每個(gè)機(jī)器人的運(yùn)動(dòng)軌跡，且隊(duì)形運(yùn)動(dòng)軌跡具有較高的精度。但剛性的結(jié)構(gòu)也使他缺乏靈活性，一旦需要變化隊(duì)形就必須重新設(shè)計(jì)虛擬剛體編隊(duì)以及各個(gè)機(jī)器人的控制規(guī)律。此外若機(jī)器人數(shù)量較多時(shí)，不僅設(shè)計(jì)控制規(guī)律會(huì)很繁瑣，而且系統(tǒng)穩(wěn)定性較難保證，魯棒性和適應(yīng)性也不佳。對(duì)機(jī)器人間的相對(duì)位置要求苛刻，實(shí)用性往往不夠，穩(wěn)定性不高，且對(duì)通信和機(jī)載計(jì)算能力要求高。圖論法圖論法是以圖作為研究對(duì)象的方法。圖論法的提出由來(lái)已久，早在18世紀(jì)，大數(shù)學(xué)家歐拉為了解決著名的哥尼斯堡七橋問(wèn)題（如圖2-6所示），探究是否可以不重復(fù)的走過(guò)點(diǎn)之間的連線(xiàn)而完整地走過(guò)所有路徑。從而創(chuàng)立了圖論這一研究方法。圖論法由此而來(lái)，歐拉也成了圖論法的始祖。時(shí)至今日，無(wú)論是在數(shù)學(xué)、天文學(xué)、化學(xué)、物理學(xué)等許多重要學(xué)科，圖論法都為問(wèn)題的解決搭建了基礎(chǔ)性的框架。圖2-6哥尼斯堡七橋問(wèn)題簡(jiǎn)化圖應(yīng)用到機(jī)器人領(lǐng)域，機(jī)器人搜索區(qū)域內(nèi)的圖由地圖上的節(jié)點(diǎn)及節(jié)點(diǎn)與節(jié)點(diǎn)之間的連線(xiàn)兩種元素組成。用圖的節(jié)點(diǎn)來(lái)指示機(jī)器人的動(dòng)力學(xué)特性，用連接節(jié)點(diǎn)的邊線(xiàn)來(lái)示意機(jī)器人間的通信拓?fù)潢P(guān)系。如圖2-7所示，我們可以清楚從圖中看出節(jié)點(diǎn)間的相互關(guān)聯(lián)以及他們的信息流向。可將圖中元素的關(guān)系用函數(shù)抽象地描述為G=(V，E，Φ)，其中V表示搜索圖的頂點(diǎn)，E是圖的頂點(diǎn)的連線(xiàn)，Φ表示V，E間的某種函數(shù)關(guān)系。圖論法在用來(lái)分析解決多機(jī)器人的編隊(duì)的問(wèn)題時(shí)，將多機(jī)器人形成的編隊(duì)看作一幅圖。在用圖論法研究多機(jī)器人編隊(duì)問(wèn)題時(shí)只需注意兩機(jī)器人間是否被一連線(xiàn)所連，而機(jī)器人形成的頂點(diǎn)的位置和連接的方式則無(wú)關(guān)緊要。圖2-7三種機(jī)器人編隊(duì)拓?fù)浣Y(jié)構(gòu)運(yùn)用圖論法解決多機(jī)器人編隊(duì)問(wèn)題時(shí)，首要做得事就是將多機(jī)器人編隊(duì)系統(tǒng)轉(zhuǎn)化成對(duì)應(yīng)的圖，接著運(yùn)用圖論法加以分析。圖論法首先是對(duì)機(jī)器人編隊(duì)進(jìn)行圖形化建模，通過(guò)使用相關(guān)的控制理論和圖論知識(shí)從而得到編隊(duì)的控制規(guī)律。在實(shí)際應(yīng)用圖論法研究多機(jī)器人編隊(duì)問(wèn)題時(shí)，其主要對(duì)多機(jī)器人一致性REF_Ref9604\r\h[20]問(wèn)題的研究大有裨益，從而分析出多機(jī)器人編隊(duì)中每個(gè)機(jī)器人的位置狀態(tài)能否隨著相關(guān)算法的指引最終形成限定區(qū)域內(nèi)的一致。運(yùn)用圖論法研究多機(jī)器人編隊(duì)的優(yōu)點(diǎn)是相關(guān)理論豐厚且成熟。可以參考數(shù)學(xué)上關(guān)于圖論的知識(shí)，尤其是在理論上分析涉及到多機(jī)器人編隊(duì)隊(duì)形上有變化的情況時(shí)，圖論法顯得簡(jiǎn)單得多。另外，在多機(jī)器人隊(duì)形隨意的時(shí)候比較有優(yōu)勢(shì)，使得編隊(duì)的隊(duì)形轉(zhuǎn)換更為容易，包括機(jī)器人個(gè)數(shù)增減以及相互之間關(guān)系的變化REF_Ref8363\r\h[21]。缺點(diǎn)是很難物理實(shí)現(xiàn)，更多的是運(yùn)用到理論分析和仿真實(shí)驗(yàn)中?；谛袨榉ㄋ^基于行為法，即進(jìn)行編隊(duì)控制時(shí)，首先對(duì)機(jī)器人所有可能出現(xiàn)的，提前可以分析出的行為加以預(yù)測(cè)，比如機(jī)器人編隊(duì)整體的運(yùn)行方向、各個(gè)機(jī)器人的運(yùn)動(dòng)姿態(tài)、避障采取的動(dòng)作等等REF_Ref10812\r\h[22]。在對(duì)機(jī)器人的行為進(jìn)行預(yù)先考慮后，所有的預(yù)期行為都有自己的任務(wù)和目標(biāo)，針對(duì)機(jī)器人的每一種具體行為進(jìn)行控制器設(shè)計(jì)，則多機(jī)器人系統(tǒng)最終的控制協(xié)議是由這些子行為的控制協(xié)議融合而成，針對(duì)行為設(shè)計(jì)的控制器可以有效的使得最終的多機(jī)器人群體產(chǎn)生所需的整體行為。子行為的融合方法，根據(jù)外界障礙的不同及多機(jī)器人的編隊(duì)任務(wù)的不同而不同。為了實(shí)現(xiàn)子行為間執(zhí)行的優(yōu)先排序，可以對(duì)各個(gè)子行為賦以相應(yīng)的權(quán)重，從而有效實(shí)現(xiàn)對(duì)多機(jī)器人各個(gè)子系統(tǒng)的控制，分行為設(shè)計(jì)相關(guān)策略?；谛袨榉ǖ暮诵氖菍?duì)機(jī)器人在環(huán)境中所有可能出現(xiàn)的各種基本行為加以預(yù)測(cè)，并對(duì)這些行為進(jìn)行協(xié)調(diào)統(tǒng)籌，如圖2-8所示。圖2-8基于行為法示意圖Balch和ARkin首先提出了基于行為的控制方法REF_Re