機器人集群路徑規劃技術研究現狀*

高 明，唐 洪，張 鵬

(1.國防科技大學 智能科學學院，湖南 長沙 410073；2.國防科技大學 研究生院，湖南 長沙 410073；3.國防科技大學 教務處，湖南 長沙 410073)

設機器人集群通過簡單的相互作用和環境相互作用，使大量機器人能夠完成復雜的任務[1]。機器人集群從諸如螞蟻、蜜蜂、魚群、鳥群等社會型群居生物中汲取靈感衍生出群體智能(swarm intelligence)的新概念，該術語最初由Beni和Wang于1989年在其蜂窩機器人系統的背景下提出，其現象是當它們遵循非常簡單的規則，并通過個體之間進行簡單的交互時，群體能夠展現出智能、靈活、高效、可擴展和高可靠等優勢。例如：蟻群可以共同努力建立巨大的巢穴，魚群能夠共同抵御比自己個頭大幾百倍的鯨鯊，鳥群則能夠在遷徙過程中形成特定隊形以實現節能飛行，等等。當然，該現象不僅局限于低端生物，即便在具有高等智能的人類身上也會自發地出現，比如人群僅憑借簡單的觀察和神經反射就會避免擁擠。群體的行為由個體局部交互涌現，這種行為是自組織的，具有自適應和完全分散的特點。群體智能模擬“分散的自組織系統的群體行為”[2]。這些系統通常是簡單智能體，它們彼此之間以及與環境相互作用。雖然他們缺乏對系統全局狀態的了解以及根據一系列簡單規則來行動的能力，但他們之間的相互作用往往會在某些情況下產生全局行為并智能涌現。任何群體智能行為都具有兩個基本特征[3]：自組織和分工。自組織是指一組動態機制，它們為智能體純粹的底層交互建立基本規則，并產生全局層面可觀察的現象；分工則指的是不同的任務由特定個體同時執行，它們相互合作以實現更大的目標。

機器人領域的學者和研究人員為了更好地了解社會型群居生物如何相互作用并實現目標，開始模擬這些群體及其行為，因此形成了“機器人集群”這個新的研究領域，從而能夠將機器人應用于更廣泛的領域。目前，機器人集群已經在以下任務背景下開展研究：

1)聚合，指機器人在空間上組合在一起。聚合用于將集群中的機器人足夠靠近，并且可以用來作為執行一些任務的起點，比如集體運輸。

2)按圖形編隊，指機器人編隊形成特定的幾何圖案，如圓形、正方形、線形、星形、格子等。這些圖形可確保集群保持通信范圍和克服環境限制，比如形成一條鏈通過狹窄通道。

3)物理連接，指機器人彼此連接以形成特定結構。用于增加機器人的牽引力，比如在粗糙地形上移動時為集群提供穩定性，組裝成特定結構用于搭建房屋等。

4)收集和組裝零件，收集遍布環境中的零件并在特定區域中組裝它們。可用于產生二維或三維結構(例如墻壁)。

5)導航，指機器人集群內相互導航。某個機器人不知道它們的實際位置或目標的位置，集群可由先前部署的機器人提供方向引導，形成通信中繼。如機器人從獵物到巢穴形成鏈條，并在覓食任務中指明其他機器人的方向。

6)繪圖+定位，指機器人集群獲取環境地圖的過程。繪圖和定位通常是一起解決的，首先，它用于對以前未知的環境進行繪圖;其次，確定機器人或目標位置。

7)部署，指通過集群覆蓋盡可能多的空間來解決在環境中部署機器人的問題?？蓱糜诎卜阑虮O視等場合。

8)協調運動，指移動的同時保持隊形，可用于相互之間避碰和規避外部障礙物。

9)集體運輸，指機器人協作共同運輸物體。

10)集體表決，指在一致性和集體決策中，機器人必須就共同決策達成一致，例如選取哪條路徑或跟蹤哪些目標。

11)覓食，指機器人集群尋找獵物并將其帶回巢穴?？蓱糜诼摵纤阉骱途仍袆印?/p>

當然，還有很多這樣的例子，單個機器人的能源和資源有限，機器人集群由許多機器人組成，它們協同工作并像團隊一樣相互協調，協作完成更復雜的任務，從而提高任務效率和任務質量，實現任務執行的靈活性。

機器人集群涵蓋機器人平臺、通信、集群自主決策、集群任務規劃、集群路徑規劃、集群控制等多項核心技術。其中，機器人集群路徑規劃是實現機器人集群路徑生成、避障、避碰等導航和協調任務的關鍵，內涵是“在線實時為集群內每一個機器人生成從其起始位置到目標位置的運動路徑，并要求集群路徑總代價最低或較低，能夠實現集群內機器人相互避碰，且避免與環境碰撞”。具體到路徑規劃問題的建模和優化求解，描述機器人集群路徑規劃問題模型各異，有仿生學模型、人工勢場模型、幾何曲線模型、經典柵格模型等，但規劃問題的目標是統一的，即集群內機器人從各自起始位置出發，同時到達各自目標位置、次序到達各自目標位置或時間窗間隔到達目標位置，規劃問題的約束具體包括空間障礙約束、避碰約束、到達次序約束、到達時間窗約束等。相比于單個機器人路徑規劃問題，集群路徑規劃問題難點在于：第一，由于集群通常由大量機器人組成，底層位形空間具有高維度，路徑規劃變得具有挑戰性；第二，路徑規劃的多項式空間(Polynomial SPACE,PSPACE)是完整的，尋求一個精確解的規劃算法(如果存在，或者不存在則報告無解)僅限于在低維系統可行；第三，數學上規模通常很大且計算復雜，特別是在對特定最優性提出要求時，該問題變成計算復雜度很高的問題，對問題維度呈指數依賴，即使是離線都難以求解。尋求復雜環境中高效率和可擴展性的反應式協調規劃算法成為機器人集群領域的熱點問題。

目前，針對多機器人、多智能體、多無人平臺都有相應的文獻綜述和學術歸納，但這些研究側重于規劃算法本身、機器人編隊、協調控制等問題。文獻[4]討論多機器人路徑規劃方法的重要特征，機器人之間的協調對于路徑規劃非常重要，質量和精度需要眾多機器人之間協作以實現其目標。隨著機器人數量增加，釋放少量優先權給機器人，使它們能夠無碰地執行分配。文獻[5]總結了多無人機協同路徑規劃方法研究。首先給出了問題描述和約束，然后總結了解框架和路徑協調方法，接著介紹了幾個常用于多無人機的協同路徑規劃方法，最后展望了未來可能的研究方向。文獻[6]對空中機器人集群關鍵技術進行了系統性綜述，將具有分布式分配的同步規劃作為其中一項核心關鍵技術，但它側重于介紹分布式任務分配問題，對于協同路徑規劃問題只是簡單地提及。文獻[7]從多無人車編隊角度系統地研究了編隊控制和編隊路徑規劃方法，認為人工勢場法、遺傳算法和最優控制方法是多無人車編隊路徑規劃的三種主流方法。不過，該綜述未從可擴展性和求解框架角度對多無人車路徑規劃問題進行分析。

本文較全面深入地調研了機器人集群路徑規劃的技術發展現狀。不同于絕大多數多智能體協同規劃綜述文獻，本文創新性地歸納了適用于不同集群規模、可擴展性要求、通信需求以及算法要求的集群規劃基礎計算架構，即冗余計算架構、分布計算架構和分層計算架構，為該領域研究人員提供了切實可行的參考思路；從可擴展性和適用性角度，分類介紹了機器人集群路徑規劃方法，包括仿生學方法、人工勢場法、幾何學方法、經典搜索法和進化學習法；收集整理了可免費下載或開源的機器人集群仿真平臺，以便于高校學生或研究人員快速構建集群仿真驗證環境。

1 集群分布計算架構

機器人集群路徑規劃問題本質上是一個群體智能計算問題，計算架構對于集群效能的發揮至關重要。根據群體規模、通信條件和任務需求，設計合理的計算架構成為實現機器人集群系統的關鍵和重要前提。考慮集群可擴展性以及同路徑規劃算法的適應性，可以歸納為三種主要計算架構：冗余計算架構、分布計算架構和分層計算架構。

1.1 冗余計算架構

天線冗余計算架構是指將同一個路徑規劃算法復制至每個機器人規劃器中，規劃器啟動前，每個機器人收集當前時刻集群內其他機器人的狀態信息，將其輸入至規劃器(虛擬中心)，同步執行集群路徑規劃，再將規劃器產生的集群路徑中屬于自己的路徑計劃取出來發送給執行器[8-9]，如圖1所示。

圖1 冗余計算架構Fig.1 Redundant computing architecture

該計算架構適用于無法或難以實現完全分布式計算的路徑規劃算法，比如幾何學路徑規劃方法。它對通信即時可靠性和電磁環境要求很高，嚴重依賴于輸入狀態信息的一致性，一旦因為通信時延或者丟包導致信息不一致，就會造成規劃結果的不一致甚至是路徑沖突，該架構僅僅適合于小規模機器人集群在相對理想通信條件下使用。在工程實踐中，一方面通過多次重傳機制確保輸入信息的一致；另一方面，盡可能限定運用于小規模集群路徑規劃問題。

1.2 分布計算架構

分布計算架構是指一種完全分布式計算的架構，機器人集群擁有一個全局優化目標，機器人規劃器以此為自身的優化目標(也容許考慮私有目標，比如避碰等)，結合感知器感知的環境狀態和通信獲得的其他機器人當前狀態，以同步或異步方式規劃自身路徑，再將規劃得到的路徑計劃發送給執行器[10-11]，如圖2所示。

圖2 分布計算架構Fig.2 Distributed computing architecture

該計算架構適用于完全分布式計算的路徑規劃算法，如：仿生學路徑規劃方法、人工勢場法、進化學習路徑規劃方法等。它對通信即時可靠性和電磁環境要求較低，對信息的不一致性不敏感，不過，對于通信帶寬有一定要求，在集群規劃器執行時刻甚至需要連續頻繁大容量的信息交換，對即時帶寬有較高的要求。該架構適合于中等規模機器人集群在相對復雜通信條件下使用，當規模達到一定程度時，也存在規劃算法難以收斂的問題。

1.3 分層計算架構

分層計算架構是一種全局集中、局部分散的計算架構，由機器人集群中的一個中心節點或虛擬中心節點執行全局路徑規劃，將路徑計劃(中間目標點)分發給集群內所有機器人，機器人再以仿生方式跟蹤這些中間點，在跟蹤過程中考慮同環境的避障問題以及同其他機器人的避碰問題[11]，如圖3所示。

圖3 分層計算架構Fig.3 Layered computing architecture

該計算架構適用于可分層計算的路徑規劃算法，如人工勢場路徑規劃法、經典搜索路徑規劃法，也適用于仿生學方法。它無論對通信即時可靠性還是對通信帶寬的要求都很低，對信息的不一致不敏感，規劃器工作過程中不需要大量的信息交互。該架構適合于大規模機器人集群在復雜通信條件下使用，當然集群密度不能夠超出環境容限。

2 集群路徑規劃方法

從可擴展性和適用性角度，重點介紹仿生學方法、人工勢場法、幾何學方法、經典搜索法、進化學習五類可以用于集群路徑規劃問題的方法。其中，仿生學方法、人工勢場法由于其分布或分層特點可以天然地應用于機器人集群路徑規劃；幾何學方法、經典搜索法是機器人路徑規劃的經典方法類別，通過采用冗余計算架構，可以用于集群路徑規劃；進化學習法是近年來伴隨著機器學習熱潮產生的一類新方法。

2.1 仿生學方法

仿生群體智能算法是一類最適用于機器人集群路徑規劃的方法，一直是群體智能領域研究熱點，它受自然界社會型生物行為啟發，如蟻群、魚群、鴿群、螢火蟲、粒子群以及蝙蝠等，這些生物基于鄰近個體間的直接交互，或者所有個體內的共識主動性來實現信息交換，通過個體間自組織協作實現復雜行為的智能涌現，具有分布式、自組織、可擴展等天然優勢。大量研究人員通過模擬上述生物行為，設計了各種群體智能算法，如蟻群算法、魚群算法、鴿群算法、螢火蟲算法、粒子群等。

2.1.1 蟻群算法

蟻群優化(Ant Colony Optimization,ACO)算法[1]受螞蟻覓食行為啟發，它是啟發式方法與螞蟻環境交互行為相結合的產物，屬于非線性優化的元啟發式算法，其使用群體智能模型來模擬螞蟻尋找食物最短路徑行為。螞蟻表現出復雜社會行為——共識主動性，該現象是在著名的雙橋實驗[10]中觀察到的：當選擇短路徑和長路徑食物源時，螞蟻在一段時間后始終會找到最短路徑。

盡管ACO易于獲得近似最優解，但很難找到最優解，文獻[11]提出一種蟻群路徑規劃算法，可獲得更高質量的全局最優路徑，且可在滿意解和迭代次數之間進行靈活的權衡。文獻[12]提出一種基于蟻群優化的動態環境下機器人集群路徑規劃算法。為了避免ACO易于陷入局部僵局和停滯問題，文獻[13]將自組織協作機制引入集群路徑規劃中，通過局域信息交換，增強局部范圍內機器人之間的通信協作，避免死鎖。當某個機器人進入死鎖區域時，同周圍其他個體共享死鎖區域位置，主動改變蟻群停留在死鎖范圍內的信息素，以便其他機器人繞過死鎖范圍，繼續尋找最短路徑。不過由于螞蟻運動具有一定隨機性，當種群規模較大時，很難在短時間內找到更優路徑，這仍是大規模集群面臨的難題。

2.1.2 魚群算法

人工魚群(Artificial Fish Swarm,AFS)算法[14]模仿魚群交互行為，找到最高密度食物源。建模的魚群具有四種基本行為：一是覓食，趨向于高食物濃度區域；二是聚集，游到高食物濃度區域而不會過分聚集在食物中心；三是追尾，追尾食物濃度高的個體，但不會聚集在其周圍；四是隨機，自由游動，不斷擴大其搜索范圍。該算法模擬真實魚類的尾跡和活動，利用自下而上優化模型實現全局優化，具有全局性、快速收斂性、搜索空間自適應性、參數魯棒性以及可追溯性等優點。不過，算法也存在缺陷，即早期收斂速度明顯快于后期、參數選擇會影響收斂速度和解的精確性、魚群數量越多優化時間越長、過寬的優化范圍和小的變化可能導致收斂速度變慢等問題。

同蟻群算法類似，AFS易于陷入局部最優，文獻[15]提出一種混合改進人工魚群算法，首先利用A*算法確定次優路徑，然后基于慣性權重因子改進AFS的自適應行為，引入衰減函數來改善魚的視覺范圍和移動步長，用于平衡全局和局部路徑規劃，提高收斂速度和質量。該算法在避免局部最優、收斂速度和精度方面得到了改進，不過當魚群規模過大時，算法需大量計算并占用更多存儲空間；而當魚群數量太少時，魚群局部優化、早熟且易于落入局部極值。針對經典AFS最優解不精確和收斂效率低的問題，文獻[16]提出一種自適應增強獵食行為和分段自適應魚視距與步長的魚群算法，稱其為混合自適應人工魚群算法。自適應增強獵食行為用于改進魚的獵食過程，設計分段自適應策略用于改造魚的視野和步長。

2.1.3 鴿群算法

鴿群優化(Pigeon-Inspired Optimization,PIO)算法[17]受自然界中鴿子歸巢行為啟發，模仿鴿子在尋找目標的不同階段使用不同導航工具這一機制，包括兩種不同算子模型：一種是地圖和指南針算子，使用磁性物體感知地磁場，在頭腦中形成地圖，把太陽高度作為指南針來調整飛行方向，當接近目的地時，對太陽和磁性物體的依賴性減小。另一種是地標算子，模擬導航工具中地標對鴿子的影響，當飛近目的地時，將更多依賴附近地標。如果鴿子對地標熟悉，將直接飛向目的地。否則，將跟隨那些對地標熟悉的鴿子飛行。鴿群優化算法相比于蟻群、粒子群等傳統仿生智能算法，不容易陷入局部最優，具有收斂速度快、計算簡單、魯棒性強等優勢，不過算法對于一些較為復雜的收斂速度問題，仍然存在速度較慢、收斂精度偏低、穩定性較差等問題。

2.1.4 螢火蟲算法

螢火蟲算法[18]是基于螢火蟲閃爍行為的群體智能算法，它能夠產生生物發光化學反應，通過不同強度的持續發光或閃爍來吸引其他螢火蟲，亮度可隨環境改變，吸引力則與亮度成正比。對于集群路徑規劃問題，螢火蟲算法具有兩大優勢，即具有自動細分群體和處理多模態的能力。首先，吸引力隨距離減小，這導致整個群體可以自動細分為子群，且每個群體可以圍繞每種模態或局部最優進行群集；其次，如果種群大小大于模態的規模，這種細分允許螢火蟲能夠同時找到所有最佳集群[19]。

文獻[20]提出一種基于路徑選擇的全局路徑規劃方法。首先利用群搜索優化(Group Search Optimizer,GSO)算法覆蓋多個局部最優解的能力，一次生成多條路徑；然后針對多條路徑提出兩種選擇算法，在通過路徑交叉點時，對交叉路徑進行重新評估并選擇較優路徑，最終達到路徑最優；最后通過啟發式搜索快速選擇到適當路徑，它重用了原搜索結果，從而避免了二次規劃。文獻[21]提出一種基于螢火蟲方法(Firefly-based Approach,FA)的機器人集群路徑規劃方法，將螢火蟲社會行為用來優化群體行為。考慮到路徑規劃問題是一個NP-復雜度問題，多目標進化算法是求解該問題的一種有效方法，為此，文獻[20]提出一種多目標螢火蟲算法用于解決機器人路徑規劃問題的路徑安全性、路徑長度和路徑光滑性等問題。

2.2 人工勢場法

人工勢場函數(Artificial Potential Functions,APFs)方法[22]將機器人工作空間定義為勢場，勢能是機器人導航過程中為避免碰撞障礙物而產生的力量，目標所在的低勢能位置吸引機器人，障礙物所在的高勢能位置則排斥機器人，這種通過施加障礙物虛擬斥力和目標的吸引力來計算勢能僅需簡單計算，它在機器人路徑規劃中極具吸引力，特別是在實時和動態環境應用中。APFs可基于分布式計算架構，獨立運算于每個機器人之上，相當于多個機器人獨立執行個體路徑規劃。由于無須統一建模與求解，特別適用于大規模集群路徑規劃問題。其優點在于：①APFs的計算速度很快，因為群體中每個機器人的合力僅取決于附近障礙物、目標以及與相鄰機器人的有限交互；②具有可擴展性，當群體增加新機器人時通常只需計算障礙物的排斥力、目標的吸引力以及與鄰近機器人的有限交互所產生的力。設計避免或最小化機器人陷入局部最小值概率的人工勢場函數是一個具有挑戰性的問題[23]。此外，充滿復雜幾何形狀的多障礙環境中的機器人集群路徑規劃方法實際上目前仍不存在。

文獻[24]運用APFs來獲得流線型路徑，將其用于復雜形狀建筑的城市環境中無人機集群路徑規劃和協作目標跟蹤問題。為提高集群路徑規劃效率，文獻[25]將概率路標圖與勢場法相結合，提出一種組合路標圖與勢場集群(Combined Roadmaps and Potentials for Swarms,CRoPS)路徑規劃算法，使集群有效移動到期望目的地，同時避免相互碰撞以及同靜態障礙物碰撞。CRoPS不使用概率路標圖來規劃群體整條路徑，而是生成一系列中間目標，這些目標充當吸引勢，以引導群體朝向期望的目的地運動；人工勢場則為機器人提供局部反應式行為，這些行為旨在使群體保持內聚并遠離障礙物。通過存在大量障礙物和狹窄通道的復雜環境仿真驗證了CRoPS的有效性和可擴展性。文獻[26]進一步對CRoPS算法進行擴展，提出一種可規避動態障礙物的組合路標圖與勢場集群(Combined Roadmaps and Potentials for Swarms for dynamic obstacles,dCRoPS)路徑規劃算法。首先，dCRoPS改進了CRoPS，使集群能夠快速響應向其靠近的動態障礙物；其次，當機器人由于動態障礙物的干擾而無法到達計劃的中間目標時，dCRoPS為群體中的機器人提供了目標的替代引導。文獻[27]通過設計優先級選擇機制并改進兩種人工勢場函數SWARM和SPREAD，實時實現集群分布式路徑規劃問題。通過在群組移動人工勢場函數SWARM和不同優先級人工勢場函數SPREAD中增加新的勢場因子，使勢函數可用于機器人集群路徑避障協調階段，同時解決人工勢場法的局部最小問題。

2.3 幾何學方法

除了從路徑尋優角度研究機器人集群路徑規劃方法，也有不少研究側重于使用B樣條曲線、Bezier曲線、Dubins曲線，畢達哥拉斯曲線等二維平面或三維空間幾何方法來生成或平滑路徑。這類方法通常需要建立集群統一的數學幾何路徑曲線優化模型或集群內個體路徑曲線之間的約束模型，集群規模容易造成模型或約束過于復雜，難于優化求解，僅適用于小規模集群路徑規劃問題。

2.3.1 杜賓斯曲線法

杜賓斯(Dubins)曲線是在滿足曲率約束和規定始/末端切線方向的條件下，連接兩個二維平面的最短路徑。對于路徑規劃問題，主要考慮路徑表示的簡易性、路徑曲率長度的計算復雜度以及改變路徑長度的容易度3個問題。Dubins路徑由圓弧及其切線連接而成，由于其表示及推導非常簡單，已廣泛應用于機器人路徑規劃問題。文獻[28]研究了三維空間無人機集群協調路徑規劃方法，無人機安全飛行路徑的同時到達問題。無人機同時到達由等長路徑保證，考慮了無人機曲率的最大界限、無人機之間的最小間隔距離以及沿著飛行路徑保證相等長度的路徑非交叉等約束。通過測量路徑之間的距離并通過找到路徑交叉點來驗證安全約束。

2.3.2 貝塞爾曲線法

貝塞爾(Bezier)曲線，依據四個位置任意的點坐標繪制出一條光滑曲線，常用于非完整機器人集群路徑規劃。大多數非完整機器人具有最小轉彎半徑約束，須在最小轉彎半徑約束和連續性約束下改進路徑。文獻[29]提出一種基于Bezier曲線的平滑方法，用于非完整機器人集群路徑規劃。算法包括全局路徑規劃、局部運動規劃和優化規劃三階段：第一階段，全局路徑規劃器在自由空間的Voronoi圖分割中規劃路徑；第二階段，運動規劃器是基于Memetic算法的遺傳算法；第三階段，導航點被視為貝塞爾曲線控制點，可獲得具有最小轉彎半徑約束的最優路徑。由于提出算法還考慮了避碰問題，因此每個機器人始終沿規劃路徑與其他機器人保持最小安全距離。

2.3.3 畢達哥拉斯曲線法

畢達哥拉斯速端(Pythagorean hodograph)曲線[30]具有以下特點：①曲線上點均勻分布；②在計算路徑長度時消除數值求積；③參數速度是其參數的多項式函數；④曲率和偏移曲線是有理形式。Shanmugavel等證明畢達哥拉斯曲線可用于自由空間以及有障礙區域的路徑規劃問題[31]。文獻[32]重點研究無人機路徑規劃，使用畢達哥拉斯路徑規劃用于跟蹤、檢測和模擬污染云的形狀。

2.4 經典搜索法

在經典搜索方法領域也存在不少可應用于機器人集群路徑規劃的有效研究。

2.4.1 概率路標圖

概率路標圖(Probabilistic Roadmap Maps,PRMs)算法[33]通過從機器人位形空間(簡稱C-空間)隨機采樣，保留滿足特定可行性要求的點(例如，須對應可移動物體的無碰撞位形)，使用一些簡單規劃方法來連接這些點以形成路標圖，在搜索路徑過程中，采用標準圖搜索技術從路標圖中提取連接其起始位形至目標位形的路徑。文獻[26]提出一種可規避動態障礙物的組合路標圖與勢場集群路徑規劃算法，其集群路徑是通過構建和搜索無碰撞路標圖得到的，當群體由于動態障礙物干擾而偏離或無法達到計劃的中間目標時，則再次搜索路標圖以獲得備選路徑。雖然概率路標圖算法可有效避免局部最小值問題，但在處理大規模機器人集群問題時其可擴展性仍然會出現問題。由于集群位形空間由每個機器人的各個位形空間的笛卡爾積組成，因此生成無沖突位形并通過無沖突路徑連接相鄰位形變得極具挑戰性。目前，盡管存在大量的模擬群體行為的方法，但這些方法通常只能提供簡單的導航和規劃能力。為實現更復雜群體行為，文獻[34]提出一種路標圖路徑規劃與群體智能相結合的方法。它使用概率路標圖的一種變體，即中軸概率路標圖，不在C-空間隨機均勻地生成節點，而在中軸或附近生成，非常適合于群體行為；另一方面，它將行為規則嵌入個體成員和路標圖中，根據成員位置和狀態來修改路標圖邊緣權重，實現了歸巢、覆蓋、搜索、穿越狹窄區域和放牧等群體行為。

2.4.2 經典路徑尋優法

迪杰斯特拉(Dijkstra)算法是從一個頂點到其余各頂點的最短路徑尋優算法，解決有向圖中最短路徑問題，作為最經典路徑尋優算法被廣泛應用于機器人路徑規劃問題。針對無人機集群協同路徑規劃問題，文獻[33]提出一種自上而下的分層控制策略，群體首先使用Voronoi圖和Dijkstra算法規劃群體最優或次優路徑，接著在底層設計自組織協調運動策略來引導無人機運動。著名的快速搜索隨機樹(Rapid-exploration Random Tree,RRT)是一種樹形數據存儲結構和算法，但RRT算法并不適用于機器人集群，文獻[35]針對磁性微型機器人引導藥物至瘤細胞問題提出了一種障礙加權快速搜索隨機樹，它將微型機器人引導至自由空間中軸區域附近以減小管壁對微型機器人集群的干擾，并采用分而治之策略通過離散區域轉換執行群體聚合。

2.4.3 啟發式搜索

高計算成本、陷入局部極小值是造成大多數經典搜索路徑規劃方法失敗的原因之一。其中，啟發式策略被認為是解決這些問題的方法之一，啟發式基于短時間間隔內結果的可用性，這對于NP完全問題是有效的[12]。文獻[36]提出一種三維環境下無人機集群路徑規劃方法，采用A*啟發式算法為每架無人機規劃趨向于目標的路徑，采用三維空間歐幾里得距離作為啟發式代價，并考慮減少整個集群路徑長度的最佳組合，以最小化總路徑長度為優化目標，計算所有飛機到達所有目標的可行路徑長度，再分布式協商實現目標最優組合。文獻[37]研究了機器人集群動態路徑規劃問題，要求群體中至少有一個機器人訪問區域內次要目標或檢查點，同時須避開靜態和動態障礙物，它采用D*lite算法用于動態路徑規劃，并設計分布式集群自組織規劃策略用于遍歷檢查點，仿真驗證了算法適用于不同規模機器人和不同障礙數量的路徑規劃問題。

2.5 進化學習法

可以看出，無論是經典搜索法、人工勢場法，還是仿生學方法，大多都存在路徑適應性差、計算復雜度高、搜索時間長、收斂精度低、容易陷入局部最優等問題。為克服這些缺點，研究人員一直嘗試不同技術，其中機器學習方法最受關注。通常，機器學習方法可分為三類[38]：監督學習、進化方法和強化學習。在機器人集群路徑規劃技術領域，都有運用這三類方法開展研究的案例。

2.5.1 監督學習

機器人領域的監督學習將神經網絡引入經典搜索方法中，使算法既具備探索世界的能力又具有存儲經驗的能力。通過學習，機器人能夠將所呈現的問題與已知問題和適當的解決方案進行比較，并且如果關于解的知識存儲在經驗中則快速響應。文獻[39]提出一種集成群體智能與神經網絡的障礙環境路徑規劃算法，稱為蟻群交配算法。它通過將ACO與自適應共振理論神經網絡結合，展現出良好的優化特性，能夠針對不同環境在不到100代的時間內得到解。不過，該方法仍然存在缺點：適應度函數的參數調節十分煩瑣，而且ART-1的警戒參數對網絡的粒度具有顯著影響。

2.5.2 進化方法

在機器人領域，進化方法的應用大多基于遺傳算法。遺傳算法是一種并行隨機搜索優化方法。文獻[40]提出一種基于遺傳算法的水下機器人集群路徑規劃方法，為每個機器人生成最短避碰路徑。機器人行進路徑的笛卡爾坐標是隨機生成的，它們被編碼到染色體中，其適應度由位移總和來定義。通過仿真驗證該算法能夠為機器人集群規劃安全無碰撞路徑，增加更多機器人，方法仍然能夠獲得最優路徑。

2.5.3 強化學習

強化學習是一種目標導向的機器學習方法。與監督學習不同，強化學習所需的訓練信息是評價而非指導，其主要目的是研究從狀態到行動的最佳映射，以得到最大化回報。強化學習在移動機器人的路徑規劃、運動控制等方面具有普遍適用性。文獻[41]研究如何將經典Q-學習方法應用于機器人集群路徑規劃問題，利用蟻群算法的信息素機制解決了強化學習系統中的信息共享問題，并對Q-學習方法存在的問題進行了一些改進，并在Player/Stage群體智能體仿真平臺上進行了仿真驗證。相比經典粒子群優化(Particle Swarm Optimization,PSO)算法，該方法在群體機器人路徑規劃中具有更高的效率。

2.5.4 其他方法

基于教學-學習的優化(Teaching-Learning-Based Optimization,TLBO)算法[42-43]模擬教學現象。該算法憑借其收斂速度快、精度高的優點，非常適合解決機器人路徑規劃問題，為全局路徑規劃提供了一種新解決方案。文獻[44]提出了一種改進TLBO機器人全局路徑規劃方法，稱為非線性慣性加權改進教學-學習優化(Nonlinear Inertia Weighted Teaching-Learning-Based Optimization,NIWTLBO)算法，它在TLBO中引入非線性慣性加權因子來控制學習者的記憶率，并使用動態慣性加權因子代替教師階段和學習者階段的原始隨機數。NIWTLBO不僅具有更快的收斂速度，而且與TLBO相比，計算精度更高。仿真實驗表明：該方法比TLBO和其他算法具有更快的收斂速度和更高的搜索路徑精度。

3 機器人集群驗證平臺

20多年來，來自機器人集群的挑戰吸引了眾多領域的研究人員。許多新的仿真模型和工具被開發用于研究群體智能理論與方法。本節將以年代為主線介紹幾款適用于大規模智能體集群問題研究的仿真引擎，這些引擎具有較好的可視化效果，便于更直觀地研究機器人群體行為，可為高校和研究院所的學生和老師提供重要參考。

3.1 StarLogo

StarLogo[45]是MIT多媒體實驗室于1994年開發的軟件包，其仿真用戶界面如圖4所示。StarLogo提供了Logo編程語言Lisp的擴展和模擬多智能體系統的集成環境。不過盡管它易于使用且功能強大，但無法模擬復雜的三維世界以及物理實現?？捎糜诮７植际较到y行為，可模擬許多現實群體現象,比如鳥群、螞蟻和市場經濟等。

3.2 Webots

Webots[46]是洛桑瑞士聯邦理工學院開發的具備建模、編程和仿真的移動機器人開發平臺，其集群仿真效果如圖5所示。用戶可以在一個共享環境中設計多種復雜的異構機器人，支持用戶自定義環境，它使用開源動力學求解引擎(Open Dynamics Engine,ODE)檢測物體碰撞和模擬剛性結構的動力學特性，可精確模擬物體速度、慣性和摩擦力等物理屬性。每個機器人可以裝配大量可供選擇的仿真傳感器和驅動器，機器人控制器可以通過內部集成化開發環境或者第三方開發環境進行編程，支持機器人行為在真實世界中測試，支持的操作系統包括Linux、Windows和MacOS。

3.3 Swarm

Swarm[47]是Minar等開發的模擬分布式系統的軟件包，其集群仿真效果如圖6所示。雖然Swarm提供了一個完備的系統來創建對象的層次結構和觸發事件，但它并沒有為三維模擬或可視化提供支持。Swarm通過訪問Objective-C或Java庫進行集合，而非獨立的應用程序，涉及大量的編程工作。

3.4 Breve

Breve[48]是一個專為分布式系統和智能體模擬而設計的三維模擬環境，其仿真用戶界面如圖7所示。雖然Breve在概念上類似于Swarm和StarLogo等軟件包，支持Linux、Windows、MacOS等操作系統。但是在模擬連續時間和連續三維空間方面，Breve的實現是完全不同的。Breve包括了面向對象解釋的語言界面、OpenGL顯示引擎、碰撞檢測，以及關節體物理模擬和靜態或動態摩擦等功能。其目標是允許快速輕松地實現分布式模擬以及先進的人工生命模擬。

(a) 可視化腳本(a) Visual script

3.5 Player/Stage

Player/Stage[49]是美國南加州大學機器人實驗室開發的多機器人系統仿真環境。其中，Player是一個多線程的機器人驅動服務器，提供了方便的接口程序用于驅動機器人和傳感器等設備，支持Linux、Solaris等操作系統；而Stage模擬這些設備，其虛擬得到的設備可以被Player控制，Stage在被設計時就考慮了多智能體系統的問題，可以提供對多機器人系統的測試仿真。Player/Stage軟件界面效果如圖8所示。

圖8 Player/Stage軟件界面效果Fig.8 Player/Stage software interface effect

3.6 SwarmFare

SwarmFare[50]是一個自組織沙箱系統，同時可以創建一個可合理模擬無人機運動學和通信的仿真環境，用于測試許多不同的多智能體場景和行為，其軟件效果如圖9所示。憑借強大的庫和良好的界面，該系統在研究如何管理依據規則集運行的群體行為的過程中是一個功能強大的工具。

(a) 可視化腳本(a) Visual script

3.7 ARGoS/Buzz

ARGoS/Buzz[51]是歐盟資助的Swarmanoid項目中開發的官方通用模擬器，其集群仿真效果如圖10所示。ARGoS/Buzz是第一款同時兼具高效(多機器人快速驅動)和靈活性(支持自由定制)的多機器人模擬器，可用于模擬大規模異構機器人集群的復雜實驗，支持對10 000個機器人進行精確的實時二維動態仿真，并且可以對相同數量的機器人進行精確的實時三維動力學仿真。

(a) Breve仿真微型機器人(a) Breve simulation micro robot

4 結論

本文全面深入地調研了機器人集群路徑規劃的技術發展現狀，創新性地歸納了適用于不同集群規模、可擴展性要求、通信需求以及算法要求的集群規劃基礎計算架構，包括冗余計算架構、分布計算架構和分層計算架構。從可擴展性和適用性角度，分類梳理了最適用于機器人集群的路徑規劃方法，包括仿生學方法、人工勢場法、幾何學方法、經典搜索法和進化學習法。并為集群仿真驗證研究提供了七款可免費下載或開源的機器人集群仿真驗證平臺。

未來將以此為基礎，更加全面地跟蹤梳理領域相關研究，并將機器人集群路徑規劃技術綜述拓展至機器人集群運動規劃和機器人任務規劃領域，為科學研究和教學工作提供更加科學的指導。