集群的概念源于自然界中大量生物的自組織行為，例如昆蟲，魚類或鳥群等，它們基于簡單本地交互規(guī)則，或相互協(xié)調(diào)并協(xié)同解決問題，而出現(xiàn)的涌現(xiàn)性群體行為（emergent collective behavior）。 隨著科技進(jìn)步及日益增長的應(yīng)用需求，近年來無人機(jī)呈現(xiàn)井噴式發(fā)展。 由于傳統(tǒng)單機(jī)作業(yè)的局限性，無人機(jī)集群受到了越來越多的關(guān)注，研究人員開始探索如何讓無人機(jī)集群像自然界生物群體一樣高效自主的完成特定任務(wù)，從而設(shè)計出各式各樣的集群算法。

但是，這些算法很少在真實硬件平臺（無人機(jī)）上飛出實際集群效果，往往為了簡化模型而忽略一些在多機(jī)器人系統(tǒng)中非常重要的問題，比如： 運動約束、系統(tǒng)通信能力、時延、障礙物和噪聲等，因為考慮這些因素的同時也必然造成模型的復(fù)雜度和對應(yīng)控制參數(shù)數(shù)量的增加，因此就需要合適的優(yōu)化方法對模型及參數(shù)進(jìn)行優(yōu)化。

本 文通過一篇2018年的經(jīng)典論文為大家介紹： 無人機(jī)集群如何從理論 ‘飛進(jìn)’ 現(xiàn)實？

▌集群算法介紹

為真正地使多無人機(jī)能夠在實際中飛出集群效果，需設(shè)計穩(wěn)定且可擴(kuò)展的集群控制算法，因此要解決算法的現(xiàn)實差距、適應(yīng)性、擴(kuò)展性和高維度問題。來自羅蘭大學(xué)的Vásárhelyi Gábor團(tuán)隊在2014年為解決這些問題，設(shè)計出一套真正考慮這些因素的集群算法。

為了盡可能模擬實際無人機(jī)飛行時的狀態(tài)，算法首先以Reynolds經(jīng)典三定律：短距離排斥、中距離速度對齊，遠(yuǎn)距離吸引為基本控制思路，增加‘粘性摩擦項’（該項對整體算法的控制效果非常重要，有興趣的同學(xué)可在原文深入了解），同時考慮現(xiàn)實與理論的差距和可能出現(xiàn)的不確定性，將無人機(jī)慣性、內(nèi)/外噪聲、傳感器刷新頻率、通信范圍、時延等諸多現(xiàn)實因素加入到算法設(shè)計中，同時引入‘shill’-agent來完成有界環(huán)境下和存在障礙物環(huán)境中的控制，進(jìn)而實現(xiàn)一種理論算法的模型實例化。為實現(xiàn)自組織集群和集群目標(biāo)跟蹤效果，分別提出兩種控制律：

(1) 集群算法：

(2) 集群目標(biāo)跟蹤算法：

Vásárhelyi 在 2014年提出此針對現(xiàn)實場景的集群算法，同年一并實現(xiàn)用十架無人機(jī)在實際環(huán)境中真正飛出該算法的實際效果。 下面為算法的仿真和實際飛行效果：

圖1. 第一行：兩種集群算法仿真效果；

第二行：集群算法實際飛行效果；(圖片取自引文[2][3])

▌優(yōu)化的目的及方法介紹

關(guān)注模型的實例化（模型及其參數(shù)的特定值）是從理論算法到實際飛行非常重要的一環(huán)，當(dāng)無視參數(shù)時可以說任何模型都是最好的實例，所以當(dāng)擁有的模型不足以生成研究的運動模式時，為使模型可執(zhí)行，需通過模型實例化才能實現(xiàn)算法從理論到實際的跨越。

從上面集群算法模型的復(fù)雜度可知，考慮現(xiàn)實因素后伴隨著可調(diào)參數(shù)的數(shù)量增加，為使設(shè)計的集群算法真正能在現(xiàn)實中實現(xiàn)，需用正確合適的優(yōu)化方法對模型參數(shù)進(jìn)行優(yōu)化。當(dāng)前的很多集群模型和多機(jī)器人的系統(tǒng)較少關(guān)注模型的實例化，因此在實際實現(xiàn)中存在較大難度，Vásárhelyi團(tuán)隊為解決該問題，使用進(jìn)化算法進(jìn)行優(yōu)化。

進(jìn)化算法是受自然進(jìn)化的啟發(fā)，在面對諸如不可區(qū)分性、不連續(xù)性、多個局部最優(yōu)和非線性相互作用等具有挑戰(zhàn)性的問題時，已證明在解決難題方面具有競爭性。進(jìn)化算法包含幾個主要原則的變體：遺傳算法，進(jìn)化策略，差分進(jìn)化和粒子群優(yōu)化等等。進(jìn)化策略，特別是協(xié)方差矩陣自適應(yīng)演化策略(CMA-ES)，被認(rèn)為是連續(xù)參數(shù)空間中的優(yōu)秀優(yōu)化器，因此Vásárhelyi團(tuán)隊使用CMA-ES對個體參數(shù)和算法參數(shù)進(jìn)行優(yōu)化。

自適應(yīng)協(xié)方差矩陣進(jìn)化策略算法(CMA-ES）是Nikolaus Hansen等人提出的一種新的進(jìn)化算 法，通過模擬自然界生物進(jìn)化過程，達(dá)到尋優(yōu)目的，多個測試函數(shù)結(jié)果表明，該算法具有全局性 能好、尋優(yōu)效率高的特點，為高計算代價復(fù)雜工程優(yōu)化問題的求解提供了新的途徑。有興趣的同 學(xué)可以查詢相關(guān)資料，下面為CMA-ES相比于進(jìn)化策略(ES)和 遺傳算法(GA)在二維 Schaffer 測試函數(shù)的具體優(yōu)化效果展示。

圖2. ES、GA、CMA-ES算法分別在 Schaffffer函數(shù)上的測試效果.

(圖片取自CSDN:進(jìn)化策略入門：最優(yōu)化問題的另一種視角)

▌集群算法的優(yōu)化過程和效果

為優(yōu)化所提出的集群算法，使集群效果盡可能滿足最大化集群連貫性和聚集性、最小化個體間和與邊界的碰撞風(fēng)險，盡可能達(dá)到整體期望集群速度并減少集群分裂，Vásárhelyi團(tuán)隊定義了6個評價函數(shù)指標(biāo)：最小個體間碰撞風(fēng)險  、最小個體與邊界碰撞風(fēng)險  、最大速度連貫性  、個體速度與 期望集群速度一致性  、最大聚集個體數(shù)  、最少分離個體數(shù) 每個評價函數(shù)的范圍區(qū)間為0~1，通過相乘得出最終評價函數(shù)：

整體優(yōu)化過程中包含無人機(jī)個體中的建模參數(shù)、集群算法中的控制參數(shù)和優(yōu)化過程中的優(yōu)化參數(shù)，需要優(yōu)化的參數(shù)眾多，同時包含整體仿真的初始配置，該團(tuán)隊對該模型在超級計算機(jī)上最終進(jìn)化了150代，15000次充分適應(yīng)進(jìn)化，單代進(jìn)化需要2~6天的計算。同時為了驗證穩(wěn)定性，對每個速度優(yōu)化出來的參數(shù)又進(jìn)行了100次隨機(jī)試驗，最后通過對比打分確定合適的參數(shù)設(shè)置后，放在實際無人機(jī)上進(jìn)行真實實驗，最終實現(xiàn)了三十架無人機(jī)在受限環(huán)境下的全自主飛行，也是當(dāng)時最多數(shù)量的無人機(jī)全自主集群飛行！

圖3. 左圖：優(yōu)化后算法飛行實驗軌跡效果；

右圖：真實無人機(jī)集群效果；(圖片取自引文[1])

▌結(jié)語

前面的介紹大體講述了無人機(jī)集群如何從理論 ‘飛進(jìn)’ 現(xiàn)實：首先在無人機(jī)建模時需要考慮現(xiàn)實因素，比如機(jī)體本身慣性、內(nèi)/外噪聲、傳感器刷新頻率等等，其次在設(shè)計集群算法時考慮受限環(huán)境條件、避碰/障、集群方式等以達(dá)到期望集群效果，然后選擇合適的優(yōu)化方法，制定優(yōu)化目標(biāo)參數(shù)，最后實現(xiàn)集群算法從理論‘飛進(jìn)’現(xiàn)實的效果。

這項工作無論是從算法設(shè)計、優(yōu)化方法還是集群實際飛行都是相當(dāng)具有挑戰(zhàn)性的，最后能飛出如此驚艷的集群效果每一環(huán)節(jié)都是極其重要的，為真實無人機(jī)全自主集群飛行這一領(lǐng)域奠定了基礎(chǔ)，這既是壓力也是動力，所以，讓無人機(jī)集群創(chuàng)造出更多、更有價值的事情需要我們繼續(xù)努力！

參考資料

[1]. Vásárhelyi G, Virágh C, Somorjai G, et al, ''Optimized flocking of autonomous drones in

confined environments'', Science Robotics, vol. 3, no. 20, 2018.

[2]. Virágh C, Vásárhelyi G, Tarcai N, et al. ''Flocking algorithm for autonomous flying robots''.

Bioinspiration and Biomimetics, vol. 9, no. 2, 2014.

[3]. Vásárhelyi G, Virágh C, Somorjai G, et al, "Outdoor flocking and formation flight with

autonomous aerial robots", in Proceedings of the IEEE/RSJ International Conference on Intelligent

Robots and Systems, pp. 3866-3873, 2014.

[4]. Hansen N, ''The CMA evolution strategy: A tutorial'', arXiv:1604.00772, 2016.

文章來源：無人機(jī)

免責(zé)聲明：本文系網(wǎng)絡(luò)轉(zhuǎn)載，版權(quán)歸原作者所有。如涉及版權(quán)，請聯(lián)系刪除！