行軍啟發的多機器人緊密隊形保持策略

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

多移動機器人的協同編隊是多機器人研究的關鍵技術之一，多機器人的協同編隊包含三方面內容：隊形構建、隊形保持和隊形重構，其關鍵在于設計一個高效、高魯棒性的多機器人編隊控制策略。

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

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

1 急行軍編隊機制

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

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

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

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

軍隊的指揮官們在實戰中總結出了部隊行軍的一般原則，即坦克或步兵行軍當中，每一列為一縱隊，相鄰縱隊之間間隔適當的距離，確保出現突發事件，坦克或戰士可以在不妨礙行軍的前提下撤出編隊。同時，最后一排的坦克或士兵應盡量向內收攏，維持緊密行軍隊形。

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

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

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

2.1 同列依次替補和末排向內收攏原則

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

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

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

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

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

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

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

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

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

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

2.2 多機器人緊密隊形保持策略算法實現

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

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

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

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

2.2.1 同列依次替補算法實現

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

2)否則就將失效或需要替補的機器人的所有參考關系都轉移到替補機器人上面。以領航者追隨者控制方法為例，即將失效或需要替補的機器人的領航者變為替補機器人的領航者，同時失效或需要替補的機器人的所有追隨者(排除替補機器人)都變為追隨替補機器人。

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

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

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

2.2.2 末排向內收攏算法實現

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

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

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

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

末排向內收攏算法的流程如圖6所示。

2.3 性能評價指標

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

1) 能耗

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

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

2) 隊形緊密度

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

隊形緊密度可描述為

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

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

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

統計結果顯示，未使用同列依次替補原則時的總路程是1 662.166 9 cm，而使用同列依次替補原則時的總路程是1 590.560 3 cm。依據假設單位路程的能耗相等，則使用同列依次替補原則能耗更低。

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

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

3 仿真結果分析

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

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

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

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

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

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

圖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

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

4 結束語

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