屈云豪，丁永生，郝礦榮，王彤

多移動機器人的協(xié)同編隊是多機器人研究的關(guān)鍵技術(shù)之一，多機器人的協(xié)同編隊包含三方面內(nèi)容：隊形構(gòu)建、隊形保持和隊形重構(gòu)，其關(guān)鍵在于設(shè)計一個高效、高魯棒性的多機器人編隊控制策略。

近年來，隨著科學(xué)技術(shù)的長足進步，多智能體的研究已經(jīng)得到了廣泛的應(yīng)用，如機場碼頭轉(zhuǎn)運、大型貨物運輸、搜索救援、三維地圖繪制等。而多機器人協(xié)同編隊又是多智能體研究中的關(guān)鍵環(huán)節(jié)。多機器人協(xié)同編隊的重點是隊形控制模型。文獻[1]在原有的領(lǐng)航者追隨者策略中引入了一個新的隊形控制策略，使得追隨者的位置相對于領(lǐng)航者不是固定的，而是在以領(lǐng)航者為圓心的適當(dāng)圓弧中變化。文獻[2]分析了兩輪機器人的運動模型，并設(shè)計摩擦補償策略，建立低成本高性能的兩輪機器人控制模型。文獻[3]基于領(lǐng)航者–跟隨者控制模型，設(shè)計了動態(tài)領(lǐng)航者選擇策略，可以在領(lǐng)航者失效的情況下，繼續(xù)編隊行進，同時提高了機器人從局部極值點逃離的可能性。文獻[4]在編隊領(lǐng)航者–跟隨者的研究中提出了二維平面下的距離–角度反饋控制器和距離–距離反饋控制器。文獻[5]設(shè)計了一種基于神經(jīng)動態(tài)優(yōu)化的非線性模糊預(yù)測控制器用于控制領(lǐng)航者追隨者編隊的形成。文獻[6]設(shè)計了一種觀察者利用視覺和速度信息、領(lǐng)導(dǎo)者的方向和速度信息以及追隨者的距離信息等，估計追隨者機器人位置信息的方法。文獻[7]提出了創(chuàng)建魯棒圖的算法，設(shè)計彈性機器人結(jié)構(gòu)方法，提高了機器人結(jié)構(gòu)的穩(wěn)定性和魯棒性。文獻[8]針對機器人速度受限的情況，提出一種基于錐形方法的幾何舵點策略，可以使機器人有效地移動到自己的舵點。文獻[9]在領(lǐng)航者追隨者策略中引入滾動優(yōu)化的概念，實驗表明可以以較快的誤差收斂速度來解決多機器人的編隊問題。文獻[10]引入了虛擬跟隨機器人，將編隊控制轉(zhuǎn)化為跟隨機器人對虛擬跟隨機器人的軌跡跟蹤控制，實現(xiàn)實時導(dǎo)航的目的。文獻[11]設(shè)計了一種基于自治操作條件反射自動機的仿生學(xué)習(xí)算法，實現(xiàn)機器人的自主平衡學(xué)習(xí)控制。文獻[12] 采用不依賴系統(tǒng)模型的模糊控制方法，對領(lǐng)導(dǎo)者進行路徑跟蹤控制，設(shè)計的控制率可以有效地控制編隊。

本文基于領(lǐng)航者–追隨者結(jié)構(gòu)的編隊控制方法，從軍隊急行軍中得到啟發(fā)，設(shè)計了同列依次替補和末排向內(nèi)收攏原則，提出多機器人緊密隊形保持策略。通過實驗驗證了該策略的有效性和優(yōu)越性。

1 急行軍編隊機制

對于多機器人系統(tǒng)的分布控制，研究者們提出了許多方法[4-9,11]。典型的方法有基于行為和規(guī)則的方法、領(lǐng)航者追隨者方法、圖論方法和物理方法。

領(lǐng)航者追隨者方法是將隊形中的機器人劃分為兩種角色，即領(lǐng)航者和追隨者，控制追隨者跟蹤領(lǐng)航者以實現(xiàn)編隊控制。其優(yōu)點是，控制簡單，僅給定領(lǐng)航者的運動軌跡就可以控制整個機器人編隊。不足之處主要有兩點：1)領(lǐng)航者和追隨者相對獨立，沒有明確的隊形反饋，實際使用中如果領(lǐng)航者前進速度過快，會產(chǎn)生追隨者無法及時跟蹤的情況；2)編隊中承擔(dān)領(lǐng)航者角色的機器人如果失效，那么整個編隊將無法保持。

本文主要研究的是第二個缺陷，使用多機器人緊密隊形保持策略可以消除這一缺點。

在步兵、騎兵或坦克部隊行軍過程中兩個重要的考量因素是行軍速度和警戒性。行軍速度快慢由任務(wù)、敵情、道路、氣候條件和部隊行軍能力確定，行軍速度也可依此規(guī)定。常言道，兵貴神速，行軍途中，在條件允許的情況下，行軍速度越快對任務(wù)的按時完成越有利。同時，在滿足機動性的前提下盡量緊密地編隊行進也有利于盡快發(fā)現(xiàn)敵情并傳播出去。

軍隊的指揮官們在實戰(zhàn)中總結(jié)出了部隊行軍的一般原則，即坦克或步兵行軍當(dāng)中，每一列為一縱隊，相鄰縱隊之間間隔適當(dāng)?shù)木嚯x，確保出現(xiàn)突發(fā)事件，坦克或戰(zhàn)士可以在不妨礙行軍的前提下撤出編隊。同時，最后一排的坦克或士兵應(yīng)盡量向內(nèi)收攏，維持緊密行軍隊形。

受急行軍的啟發(fā)，我們總結(jié)出兩個行軍原則：同列依次替補和末排向內(nèi)收攏原則。這兩個原則可以確保行軍的速度和警惕性。

2 多機器人緊密隊形保持策略

將同列依次替補和末排向內(nèi)收攏原則提煉并遷移到多機器人協(xié)同編隊中來，提出了多機器人緊密隊形保持策略。下面用圖示法論述多機器人緊密隊形保持策略的具體實現(xiàn)方法。

2.1 同列依次替補和末排向內(nèi)收攏原則

圖示中圓形代表機器人個體，圓中標(biāo)號代表機器人的標(biāo)號，線段代表領(lǐng)航者和追隨者的跟蹤關(guān)系，箭頭方向代表跟蹤方向。例如，圖1中C機器人箭頭指向A，代表C機器人是追隨者，A機器人是其領(lǐng)航者，C機器人跟蹤A機器人。

圖1 和圖2論述同列依次替補原則的具體內(nèi)容，圖3和圖4論述末排向內(nèi)收攏原則的具體內(nèi)容。

當(dāng)失效的機器人C位于邊緣隊列時，如圖1所示，作為處于同一列且是C機器人的追隨者的機器人D向前替補，同時原來C機器人的參考機器人A和B變?yōu)镈機器人的參考機器人。隨后在機器人運動模型的控制下D機器人完全替補了C機器人原來的位置，緊密編隊得以繼續(xù)。

當(dāng)失效的機器人C位于非邊緣位置時，如圖2所示。首先作為處于同一列且是C機器人的追隨者的機器人F向前替補，同時原來C機器人的參考機器人A和B變?yōu)镕機器人的參考機器人，C機器人的追隨者機器人D變?yōu)闄C器人F的追隨者。最后在機器人運動模型的控制下機器人F和機器人H向前替補了機器人C和機器人F原來的位置，緊密編隊得以繼續(xù)。

圖2 同列依次替補原則非邊緣C機器人失效示意圖Fig. 2 Non-edge C robot failure with substitution in the same column diagram

當(dāng)同一列的機器人依次替補完成后，就需要檢查是否滿足緊密隊形約束。如果滿足就結(jié)束隊形重組，如果不滿足就需要根據(jù)圖3和圖4所示的不同情況進一步調(diào)整。

圖3 末排向內(nèi)收攏原則C機器人失效示意圖Fig. 3 C robot failure with inward convergence diagram

圖4 末排向內(nèi)收攏原則C機器人替補示意圖Fig. 4 C robot substitute with convergence diagram

當(dāng)末排的機器人C失效時，如圖3所示，先判斷機器人C是否處于中間位置，如果處于中間位置，則將任意一邊的機器人向內(nèi)收攏，其隊形緊密程度相等。否則，就將該機器人向內(nèi)收攏。假設(shè)圖3中，機器人C偏向右側(cè)，則將機器人C右側(cè)的機器人E向內(nèi)收攏。機器人E首先替補了機器人C的位置，同時機器人C原來的參考機器人A和B變成了機器人E 的參考機器人，隨后在機器人運動模型的控制下機器人E完全代替了機器人C。緊密編隊得以繼續(xù)。

當(dāng)末排的機器人C向前替補時，如圖4所示，當(dāng)最后一排中機器人C向前替補后，先判斷機器人C是否處于中間位置，如果處于中間位置，則將任意一邊的機器人向內(nèi)收攏，其隊形緊密程度相等。否則，就將該機器人向內(nèi)收攏。假設(shè)圖4中，機器人C偏向右側(cè)，則將機器人C右側(cè)的機器人E向內(nèi)收攏。因為機器人C向前替補，機器人A也就不再是機器人C的參考機器人，此時機器人E前來替補機器人C，則機器人A就變成了機器人E的參考機器人。隨后在機器人運動模型的控制下機器人E完全替補了機器人C原來的位置。緊密編隊得以繼續(xù)。

2.2 多機器人緊密隊形保持策略算法實現(xiàn)

本文專注于研究多機器人緊密隊形保持策略，對于失效機器人的檢測、兩輪差動機器人的運動模型、機器人的控制模型等問題不做過多闡述，只是借用當(dāng)前已有的成熟模型。下面闡述多機器人緊密隊形保持策略的算法實現(xiàn)。

1)當(dāng)檢測到編隊中有機器人失效時，首先觸發(fā)同列依次替補原則。將失效機器人所在列的機器人依次向前替補。如果失效機器人或替補后的機器人處于該列的末尾，則同列依次替補原則結(jié)束。

2)隨后觸發(fā)末排向內(nèi)收攏原則，首先判斷失效機器人所在列所處的位置，將失效機器人偏向的方向的機器人向內(nèi)收攏。如果失效機器人或收攏后的機器人處于末排的邊緣，則末排向內(nèi)收攏原則結(jié)束。

3)最后機器人個數(shù)減1。

2.2.1 同列依次替補算法實現(xiàn)

1)首先判斷失效或需要替補的機器人是否處于該列的末尾。如果位于列尾，則同列依次替補算法結(jié)束。

2)否則就將失效或需要替補的機器人的所有參考關(guān)系都轉(zhuǎn)移到替補機器人上面。以領(lǐng)航者追隨者控制方法為例，即將失效或需要替補的機器人的領(lǐng)航者變?yōu)樘嫜a機器人的領(lǐng)航者，同時失效或需要替補的機器人的所有追隨者(排除替補機器人)都變?yōu)樽冯S替補機器人。

3)因為替補機器人前去替補失效的或需要替補的機器人，替補機器人原來的位置無機器人。接下來將替補機器人原來的位置作為需要替補的機器人位置，將該列下一個機器人作為替補機器人，重新調(diào)用步驟1)，繼續(xù)依次替補。直到失效或需要替補的機器人處于該列的末尾。

同列依次替補算法的流程圖如圖5所示。

圖5 同列依次替補算法流程圖Fig. 5 The algorithm flowchart of substitution in the same column

2.2.2 末排向內(nèi)收攏算法實現(xiàn)

1)首先判斷失效或需要替補的機器人是否處于末排的邊緣。如果位于邊緣，則末排向內(nèi)收攏算法結(jié)束。

2)否則就先判斷失效或需要替補的機器人是否處于中間位置，如果處于中間位置，則將任意一邊的機器人向內(nèi)收攏，其隊形緊密程度相等。否則，就將該機器人偏向方向的機器人向內(nèi)收攏。該機器人偏向方向的相鄰機器人是其替補機器人。

收攏方法：將失效或需要替補的機器人的所有參考關(guān)系都轉(zhuǎn)移到替補機器人上面。

3)因為替補機器人前去替補失效或需要替補的機器人，替補機器人原來的位置無機器人。接下來將替補機器人原來的位置作為需要替補的機器人位置，將末排下一個機器人作為替補機器人，重新調(diào)用步驟1)，繼續(xù)收攏隊形。直到失效或需要替補的機器人處于末排的邊緣。

末排向內(nèi)收攏算法的流程如圖6所示。

2.3 性能評價指標(biāo)

多機器人緊密隊形保持策略主要包含兩個原則：同列依次替補和末排向內(nèi)收攏原則。同列替補原則的優(yōu)化目標(biāo)是機器人在編隊重組過程中的路程最短，末排向內(nèi)收攏原則的優(yōu)化目標(biāo)是更緊密的編隊隊形。據(jù)此我們引入兩個隊形評價指標(biāo)：能耗和隊形緊密度。

1) 能耗

假設(shè)單位路程長度的能耗為1，則能耗就等價于編隊在機器人失效時到機器人到達(dá)目標(biāo)點之間走過的路程。定義隊列中的各個機器人在失效時的位置為，到達(dá)目標(biāo)點時的各個機器人位置為。能耗最小就轉(zhuǎn)化為求各個機器人從機器人失效到重新編隊到達(dá)目標(biāo)點的總路程之和最小，描述如下：

圖6 末排向內(nèi)收攏算法流程Fig. 6 The algorithm flowchart of approach inward

2) 隊形緊密度

定義隊形緊密度為編隊中各個機器人到隊形幾何中心的距離之和的倒數(shù)，即各個機器人到隊形幾何中心的距離之和越大，隊形緊密度越小。定義機器人隊形的幾何中心為

隊形緊密度可描述為

為了直觀地比較同列依次替補原則對于能耗的提升效果，本文設(shè)計了4個機器人排成一列前進，然后在某一時刻1號追隨者機器人失效，隨后分別計算使用同列依次替補原則的機器人總路程和不使用該原則的機器人總路程。路程更短的一方能耗更低。

仿真中，0號機器人是領(lǐng)航者機器人，其余的是追隨者機器人。領(lǐng)航者機器人設(shè)置限速8，否則會出現(xiàn)追隨者無法追蹤的情況。機器人的運動模型采用兩輪差分運動模型[1-2,10]，控制模型使用控制模型[4,12]。

圖7 使用同列依次替補原則的機器人路徑對比Fig. 7 Comparison of robot path using substitution

統(tǒng)計結(jié)果顯示，未使用同列依次替補原則時的總路程是1 662.166 9 cm，而使用同列依次替補原則時的總路程是1 590.560 3 cm。依據(jù)假設(shè)單位路程的能耗相等，則使用同列依次替補原則能耗更低。

接下來驗證使用末排向內(nèi)收攏原則的效果，如圖8所示，當(dāng)8號機器人失效的時候，左側(cè)是沒有使用末排向內(nèi)收攏原則所形成的隊形，右側(cè)是使用末排向內(nèi)收攏原則所形成的隊形。根據(jù)公式(2)計算可得，沒有使用末排向內(nèi)收攏原則的緊密度是cm–1，使用末排向內(nèi)收攏原則的緊密度是cm–1。顯然，使用末排向內(nèi)收攏原則有更高的隊形緊密度。

圖8 末排向內(nèi)收攏原則編隊隊形比較Fig. 8 The comparative figure of the formation using inward convergence rule

3 仿真結(jié)果分析

本節(jié)中將使用基于同列依次替補和末排向內(nèi)收攏原則的多機器人緊密隊形策略，處理機器人失效情況下的編隊重組任務(wù)[3,12-14]。

首先仿真編隊隊形是三角隊形的情況。如圖9所示，仿真中機器人個數(shù)是10個，包含1個領(lǐng)航者和9個追隨者。它們共同組成了一個三角形編隊。在行進過程中，2號追隨者機器人突然失效，按照多機器人緊密隊形保持策略，同列的8號機器人遵從同列依次替補原則需要去替補2號機器人，然后9號機器人遵從末排向內(nèi)收攏原則替補8號機器人。

圖9 緊密隊形保持策略三角隊形編隊路徑Fig. 9 Triangle formation path using compact formation strategy

如圖9所示，2號機器人失效后，8號機器人快速駛向原來2號機器人的位置，來替換2號機器人。很明顯，8號替補2號機器人會比9號前去替換路程更短，能耗更小。同時9號機器人向內(nèi)收攏來替換8號機器人。假如果9號不前去替補8號的位置，那么形成的隊形將較為分散，隊形緊密度偏低。5號機器人在這一過程中會稍有偏移。仿真過程中各個機器人左右輪的速度時間曲線如圖10所示。在s時，2號機器人失效后其左右輪的速度突變?yōu)榱悖?號和9號機器人因為需要前去替補，其速度有較大幅度的變動，5號機器人因為參考8號和9號機器人的位置，所以其速度也有突變。當(dāng)s時，隊形重構(gòu)基本完成。

圖10 三角隊形編隊各個機器人左右輪速度時間曲線Fig. 10 The left and right wheel speed-time curves of each robot using triangle formation

為了說明該策略的可推廣性，接下來考慮編隊隊形是矩形隊形的情況。如圖11所示，仿真中共有9個機器人，包含1個領(lǐng)航者機器人和8個追隨者機器人。它們共同組成了一個矩形編隊。在行進過程中，4號追隨者機器人突然失效，按照多機器人緊密隊形保持策略，同列的7號機器人遵從同列依次替補原則需要去替補4號機器人，然后8號機器人遵從末排向內(nèi)收攏原則替補7號機器人。如圖11所示，4號機器人失效后，7號機器人快速駛向原來4號機器人的位置，來替換4號機器人。很明顯，7號替補4號機器人會比8號前去替換路程更短，能耗更小。同時8號機器人向內(nèi)收攏來替換7號機器人。如果8號不前去替補7號的位置，那么形成的隊形將較為分散，隊形緊密度偏低。仿真過程中各個機器人左右輪的速度時間曲線如圖12所示。在s時，4號機器人失效后其左右輪的速度突變?yōu)榱悖?號機器人因為要加速前進替補4號機器人，所以其速度有突增。8號機器人因為需要前去替補7號機器人，參考關(guān)系的變化使得其速度小幅度消減后再次上升。當(dāng)s時，隊形重構(gòu)基本完成。

圖11 緊密隊形保持策略矩形隊形編隊路徑Fig. 11 Rectangle formation path using compact formation strategy

圖12 矩形隊形編隊各個機器人左右輪速度時間曲線Fig. 12 The left and right wheel speed-time curves of each robot using rectangle formation

從上述實驗結(jié)果可以看出，同列依次替補原則會使隊形在出現(xiàn)突發(fā)事件，更優(yōu)地實現(xiàn)隊形重組，能耗更低。末排向內(nèi)收攏原則可以確保編隊重組之后隊形有更好的緊密度。進一步實驗表明，行軍啟發(fā)的多機器人緊密隊形策略，能夠在出現(xiàn)機器人失效的情況下繼續(xù)實現(xiàn)緊密編隊，順利到達(dá)目標(biāo)點。

4 結(jié)束語

本文針對領(lǐng)航者–追隨者結(jié)構(gòu)隊形控制方法中存在的機器人失效，即無法維持編隊的缺陷，提出了基于同列依次替補和末排向內(nèi)收攏原則的多機器人緊密隊形保持策略。并通過實驗驗證了多機器人緊密隊形保持策略的有效性和優(yōu)越性，對多機器人編隊研究有一定的參考價值。