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

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

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

▌集群算法介紹

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

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

(1) 集群算法：

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

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

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

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

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

進(jìn)化算法是受自然進(jìn)化的啟發(fā)，在面對(duì)諸如不可區(qū)分性、不連續(xù)性、多個(gè)局部最優(yōu)和非線性相互作用等具有挑戰(zhàn)性的問(wèn)題時(shí)，已證明在解決難題方面具有競(jìng)爭(zhēng)性。進(jìn)化算法包含幾個(gè)主要原則的變體：遺傳算法，進(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)隊(duì)使用CMA-ES對(duì)個(gè)體參數(shù)和算法參數(shù)進(jìn)行優(yōu)化。

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

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

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

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

▌結(jié)語(yǔ)

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

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

本文共2342字

由西湖大學(xué)智能無(wú)人系統(tǒng)實(shí)驗(yàn)室博士生李康原創(chuàng)

申請(qǐng)文章授權(quán)請(qǐng)聯(lián)系后臺(tái)相關(guān)運(yùn)營(yíng)人員

▌微信公眾號(hào)：空中機(jī)器人前沿

▌知乎：空中機(jī)器人前沿（本文鏈接：https://zhuanlan.zhihu.com/p/535423499）

▌Youtube：Aerial robotics @ Westlake University

▌實(shí)驗(yàn)室網(wǎng)站：https://shiyuzhao.westlake.edu.cn/?