機(jī)器人集群路徑規(guī)劃技術(shù)研究現(xiàn)狀*

高 明，唐 洪，張 鵬

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

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

機(jī)器人領(lǐng)域的學(xué)者和研究人員為了更好地了解社會(huì)型群居生物如何相互作用并實(shí)現(xiàn)目標(biāo)，開始模擬這些群體及其行為，因此形成了“機(jī)器人集群”這個(gè)新的研究領(lǐng)域，從而能夠?qū)C(jī)器人應(yīng)用于更廣泛的領(lǐng)域。目前，機(jī)器人集群已經(jīng)在以下任務(wù)背景下開展研究：

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

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

3)物理連接，指機(jī)器人彼此連接以形成特定結(jié)構(gòu)。用于增加機(jī)器人的牽引力，比如在粗糙地形上移動(dòng)時(shí)為集群提供穩(wěn)定性，組裝成特定結(jié)構(gòu)用于搭建房屋等。

4)收集和組裝零件，收集遍布環(huán)境中的零件并在特定區(qū)域中組裝它們?？捎糜诋a(chǎn)生二維或三維結(jié)構(gòu)(例如墻壁)。

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

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

7)部署，指通過集群覆蓋盡可能多的空間來解決在環(huán)境中部署機(jī)器人的問題。可應(yīng)用于安防或監(jiān)視等場合。

8)協(xié)調(diào)運(yùn)動(dòng)，指移動(dòng)的同時(shí)保持隊(duì)形，可用于相互之間避碰和規(guī)避外部障礙物。

9)集體運(yùn)輸，指機(jī)器人協(xié)作共同運(yùn)輸物體。

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

11)覓食，指機(jī)器人集群尋找獵物并將其帶回巢穴?？蓱?yīng)用于聯(lián)合搜索和救援行動(dòng)。

當(dāng)然，還有很多這樣的例子，單個(gè)機(jī)器人的能源和資源有限，機(jī)器人集群由許多機(jī)器人組成，它們協(xié)同工作并像團(tuán)隊(duì)一樣相互協(xié)調(diào)，協(xié)作完成更復(fù)雜的任務(wù)，從而提高任務(wù)效率和任務(wù)質(zhì)量，實(shí)現(xiàn)任務(wù)執(zhí)行的靈活性。

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

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

本文較全面深入地調(diào)研了機(jī)器人集群路徑規(guī)劃的技術(shù)發(fā)展現(xiàn)狀。不同于絕大多數(shù)多智能體協(xié)同規(guī)劃綜述文獻(xiàn)，本文創(chuàng)新性地歸納了適用于不同集群規(guī)模、可擴(kuò)展性要求、通信需求以及算法要求的集群規(guī)劃基礎(chǔ)計(jì)算架構(gòu)，即冗余計(jì)算架構(gòu)、分布計(jì)算架構(gòu)和分層計(jì)算架構(gòu)，為該領(lǐng)域研究人員提供了切實(shí)可行的參考思路；從可擴(kuò)展性和適用性角度，分類介紹了機(jī)器人集群路徑規(guī)劃方法，包括仿生學(xué)方法、人工勢(shì)場法、幾何學(xué)方法、經(jīng)典搜索法和進(jìn)化學(xué)習(xí)法；收集整理了可免費(fèi)下載或開源的機(jī)器人集群仿真平臺(tái)，以便于高校學(xué)生或研究人員快速構(gòu)建集群仿真驗(yàn)證環(huán)境。

1 集群分布計(jì)算架構(gòu)

機(jī)器人集群路徑規(guī)劃問題本質(zhì)上是一個(gè)群體智能計(jì)算問題，計(jì)算架構(gòu)對(duì)于集群效能的發(fā)揮至關(guān)重要。根據(jù)群體規(guī)模、通信條件和任務(wù)需求，設(shè)計(jì)合理的計(jì)算架構(gòu)成為實(shí)現(xiàn)機(jī)器人集群系統(tǒng)的關(guān)鍵和重要前提。考慮集群可擴(kuò)展性以及同路徑規(guī)劃算法的適應(yīng)性，可以歸納為三種主要計(jì)算架構(gòu)：冗余計(jì)算架構(gòu)、分布計(jì)算架構(gòu)和分層計(jì)算架構(gòu)。

1.1 冗余計(jì)算架構(gòu)

天線冗余計(jì)算架構(gòu)是指將同一個(gè)路徑規(guī)劃算法復(fù)制至每個(gè)機(jī)器人規(guī)劃器中，規(guī)劃器啟動(dòng)前，每個(gè)機(jī)器人收集當(dāng)前時(shí)刻集群內(nèi)其他機(jī)器人的狀態(tài)信息，將其輸入至規(guī)劃器(虛擬中心)，同步執(zhí)行集群路徑規(guī)劃，再將規(guī)劃器產(chǎn)生的集群路徑中屬于自己的路徑計(jì)劃取出來發(fā)送給執(zhí)行器[8-9]，如圖1所示。

圖1 冗余計(jì)算架構(gòu)Fig.1 Redundant computing architecture

該計(jì)算架構(gòu)適用于無法或難以實(shí)現(xiàn)完全分布式計(jì)算的路徑規(guī)劃算法，比如幾何學(xué)路徑規(guī)劃方法。它對(duì)通信即時(shí)可靠性和電磁環(huán)境要求很高，嚴(yán)重依賴于輸入狀態(tài)信息的一致性，一旦因?yàn)橥ㄐ艜r(shí)延或者丟包導(dǎo)致信息不一致，就會(huì)造成規(guī)劃結(jié)果的不一致甚至是路徑?jīng)_突，該架構(gòu)僅僅適合于小規(guī)模機(jī)器人集群在相對(duì)理想通信條件下使用。在工程實(shí)踐中，一方面通過多次重傳機(jī)制確保輸入信息的一致；另一方面，盡可能限定運(yùn)用于小規(guī)模集群路徑規(guī)劃問題。

1.2 分布計(jì)算架構(gòu)

分布計(jì)算架構(gòu)是指一種完全分布式計(jì)算的架構(gòu)，機(jī)器人集群擁有一個(gè)全局優(yōu)化目標(biāo)，機(jī)器人規(guī)劃器以此為自身的優(yōu)化目標(biāo)(也容許考慮私有目標(biāo)，比如避碰等)，結(jié)合感知器感知的環(huán)境狀態(tài)和通信獲得的其他機(jī)器人當(dāng)前狀態(tài)，以同步或異步方式規(guī)劃自身路徑，再將規(guī)劃得到的路徑計(jì)劃發(fā)送給執(zhí)行器[10-11]，如圖2所示。

圖2 分布計(jì)算架構(gòu)Fig.2 Distributed computing architecture

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

1.3 分層計(jì)算架構(gòu)

分層計(jì)算架構(gòu)是一種全局集中、局部分散的計(jì)算架構(gòu)，由機(jī)器人集群中的一個(gè)中心節(jié)點(diǎn)或虛擬中心節(jié)點(diǎn)執(zhí)行全局路徑規(guī)劃，將路徑計(jì)劃(中間目標(biāo)點(diǎn))分發(fā)給集群內(nèi)所有機(jī)器人，機(jī)器人再以仿生方式跟蹤這些中間點(diǎn)，在跟蹤過程中考慮同環(huán)境的避障問題以及同其他機(jī)器人的避碰問題[11]，如圖3所示。

圖3 分層計(jì)算架構(gòu)Fig.3 Layered computing architecture

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

2 集群路徑規(guī)劃方法

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

2.1 仿生學(xué)方法

仿生群體智能算法是一類最適用于機(jī)器人集群路徑規(guī)劃的方法，一直是群體智能領(lǐng)域研究熱點(diǎn)，它受自然界社會(huì)型生物行為啟發(fā)，如蟻群、魚群、鴿群、螢火蟲、粒子群以及蝙蝠等，這些生物基于鄰近個(gè)體間的直接交互，或者所有個(gè)體內(nèi)的共識(shí)主動(dòng)性來實(shí)現(xiàn)信息交換，通過個(gè)體間自組織協(xié)作實(shí)現(xiàn)復(fù)雜行為的智能涌現(xiàn)，具有分布式、自組織、可擴(kuò)展等天然優(yōu)勢(shì)。大量研究人員通過模擬上述生物行為，設(shè)計(jì)了各種群體智能算法，如蟻群算法、魚群算法、鴿群算法、螢火蟲算法、粒子群等。

2.1.1 蟻群算法

蟻群優(yōu)化(Ant Colony Optimization,ACO)算法[1]受螞蟻覓食行為啟發(fā)，它是啟發(fā)式方法與螞蟻環(huán)境交互行為相結(jié)合的產(chǎn)物，屬于非線性優(yōu)化的元啟發(fā)式算法，其使用群體智能模型來模擬螞蟻尋找食物最短路徑行為。螞蟻表現(xiàn)出復(fù)雜社會(huì)行為——共識(shí)主動(dòng)性，該現(xiàn)象是在著名的雙橋?qū)嶒?yàn)[10]中觀察到的：當(dāng)選擇短路徑和長路徑食物源時(shí)，螞蟻在一段時(shí)間后始終會(huì)找到最短路徑。

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

2.1.2 魚群算法

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

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

2.1.3 鴿群算法

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

2.1.4 螢火蟲算法

螢火蟲算法[18]是基于螢火蟲閃爍行為的群體智能算法，它能夠產(chǎn)生生物發(fā)光化學(xué)反應(yīng)，通過不同強(qiáng)度的持續(xù)發(fā)光或閃爍來吸引其他螢火蟲，亮度可隨環(huán)境改變，吸引力則與亮度成正比。對(duì)于集群路徑規(guī)劃問題，螢火蟲算法具有兩大優(yōu)勢(shì)，即具有自動(dòng)細(xì)分群體和處理多模態(tài)的能力。首先，吸引力隨距離減小，這導(dǎo)致整個(gè)群體可以自動(dòng)細(xì)分為子群，且每個(gè)群體可以圍繞每種模態(tài)或局部最優(yōu)進(jìn)行群集；其次，如果種群大小大于模態(tài)的規(guī)模，這種細(xì)分允許螢火蟲能夠同時(shí)找到所有最佳集群[19]。

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

2.2 人工勢(shì)場法

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

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

2.3 幾何學(xué)方法

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

2.3.1 杜賓斯曲線法

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

2.3.2 貝塞爾曲線法

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

2.3.3 畢達(dá)哥拉斯曲線法

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

2.4 經(jīng)典搜索法

在經(jīng)典搜索方法領(lǐng)域也存在不少可應(yīng)用于機(jī)器人集群路徑規(guī)劃的有效研究。

2.4.1 概率路標(biāo)圖

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

2.4.2 經(jīng)典路徑尋優(yōu)法

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

2.4.3 啟發(fā)式搜索

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

2.5 進(jìn)化學(xué)習(xí)法

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

2.5.1 監(jiān)督學(xué)習(xí)

機(jī)器人領(lǐng)域的監(jiān)督學(xué)習(xí)將神經(jīng)網(wǎng)絡(luò)引入經(jīng)典搜索方法中，使算法既具備探索世界的能力又具有存儲(chǔ)經(jīng)驗(yàn)的能力。通過學(xué)習(xí)，機(jī)器人能夠?qū)⑺尸F(xiàn)的問題與已知問題和適當(dāng)?shù)慕鉀Q方案進(jìn)行比較，并且如果關(guān)于解的知識(shí)存儲(chǔ)在經(jīng)驗(yàn)中則快速響應(yīng)。文獻(xiàn)[39]提出一種集成群體智能與神經(jīng)網(wǎng)絡(luò)的障礙環(huán)境路徑規(guī)劃算法，稱為蟻群交配算法。它通過將ACO與自適應(yīng)共振理論神經(jīng)網(wǎng)絡(luò)結(jié)合，展現(xiàn)出良好的優(yōu)化特性，能夠針對(duì)不同環(huán)境在不到100代的時(shí)間內(nèi)得到解。不過，該方法仍然存在缺點(diǎn)：適應(yīng)度函數(shù)的參數(shù)調(diào)節(jié)十分煩瑣，而且ART-1的警戒參數(shù)對(duì)網(wǎng)絡(luò)的粒度具有顯著影響。

2.5.2 進(jìn)化方法

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

2.5.3 強(qiáng)化學(xué)習(xí)

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

2.5.4 其他方法

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

3 機(jī)器人集群驗(yàn)證平臺(tái)

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

3.1 StarLogo

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

3.2 Webots

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

3.3 Swarm

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

3.4 Breve

Breve[48]是一個(gè)專為分布式系統(tǒng)和智能體模擬而設(shè)計(jì)的三維模擬環(huán)境，其仿真用戶界面如圖7所示。雖然Breve在概念上類似于Swarm和StarLogo等軟件包，支持Linux、Windows、MacOS等操作系統(tǒng)。但是在模擬連續(xù)時(shí)間和連續(xù)三維空間方面，Breve的實(shí)現(xiàn)是完全不同的。Breve包括了面向?qū)ο蠼忉尩恼Z言界面、OpenGL顯示引擎、碰撞檢測(cè)，以及關(guān)節(jié)體物理模擬和靜態(tài)或動(dòng)態(tài)摩擦等功能。其目標(biāo)是允許快速輕松地實(shí)現(xiàn)分布式模擬以及先進(jìn)的人工生命模擬。

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

3.5 Player/Stage

Player/Stage[49]是美國南加州大學(xué)機(jī)器人實(shí)驗(yàn)室開發(fā)的多機(jī)器人系統(tǒng)仿真環(huán)境。其中，Player是一個(gè)多線程的機(jī)器人驅(qū)動(dòng)服務(wù)器，提供了方便的接口程序用于驅(qū)動(dòng)機(jī)器人和傳感器等設(shè)備，支持Linux、Solaris等操作系統(tǒng)；而Stage模擬這些設(shè)備，其虛擬得到的設(shè)備可以被Player控制，Stage在被設(shè)計(jì)時(shí)就考慮了多智能體系統(tǒng)的問題，可以提供對(duì)多機(jī)器人系統(tǒng)的測(cè)試仿真。Player/Stage軟件界面效果如圖8所示。

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

3.6 SwarmFare

SwarmFare[50]是一個(gè)自組織沙箱系統(tǒng)，同時(shí)可以創(chuàng)建一個(gè)可合理模擬無人機(jī)運(yùn)動(dòng)學(xué)和通信的仿真環(huán)境，用于測(cè)試許多不同的多智能體場景和行為，其軟件效果如圖9所示。憑借強(qiáng)大的庫和良好的界面，該系統(tǒng)在研究如何管理依據(jù)規(guī)則集運(yùn)行的群體行為的過程中是一個(gè)功能強(qiáng)大的工具。

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

3.7 ARGoS/Buzz

ARGoS/Buzz[51]是歐盟資助的Swarmanoid項(xiàng)目中開發(fā)的官方通用模擬器，其集群仿真效果如圖10所示。ARGoS/Buzz是第一款同時(shí)兼具高效(多機(jī)器人快速驅(qū)動(dòng))和靈活性(支持自由定制)的多機(jī)器人模擬器，可用于模擬大規(guī)模異構(gòu)機(jī)器人集群的復(fù)雜實(shí)驗(yàn)，支持對(duì)10 000個(gè)機(jī)器人進(jìn)行精確的實(shí)時(shí)二維動(dòng)態(tài)仿真，并且可以對(duì)相同數(shù)量的機(jī)器人進(jìn)行精確的實(shí)時(shí)三維動(dòng)力學(xué)仿真。

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

4 結(jié)論

本文全面深入地調(diào)研了機(jī)器人集群路徑規(guī)劃的技術(shù)發(fā)展現(xiàn)狀，創(chuàng)新性地歸納了適用于不同集群規(guī)模、可擴(kuò)展性要求、通信需求以及算法要求的集群規(guī)劃基礎(chǔ)計(jì)算架構(gòu)，包括冗余計(jì)算架構(gòu)、分布計(jì)算架構(gòu)和分層計(jì)算架構(gòu)。從可擴(kuò)展性和適用性角度，分類梳理了最適用于機(jī)器人集群的路徑規(guī)劃方法，包括仿生學(xué)方法、人工勢(shì)場法、幾何學(xué)方法、經(jīng)典搜索法和進(jìn)化學(xué)習(xí)法。并為集群仿真驗(yàn)證研究提供了七款可免費(fèi)下載或開源的機(jī)器人集群仿真驗(yàn)證平臺(tái)。

未來將以此為基礎(chǔ)，更加全面地跟蹤梳理領(lǐng)域相關(guān)研究，并將機(jī)器人集群路徑規(guī)劃技術(shù)綜述拓展至機(jī)器人集群運(yùn)動(dòng)規(guī)劃和機(jī)器人任務(wù)規(guī)劃領(lǐng)域，為科學(xué)研究和教學(xué)工作提供更加科學(xué)的指導(dǎo)。