面向飛機(jī)蒙皮檢測(cè)任務(wù)的空-地異構(gòu)機(jī)器人協(xié)同覆蓋路徑規(guī)劃

摘 要：飛機(jī)蒙皮檢測(cè)對(duì)于保證飛機(jī)飛行安全至關(guān)重要。采用移動(dòng)機(jī)器人自主檢測(cè)方式能夠大大提高檢測(cè)效率以及降低安全風(fēng)險(xiǎn)。但由于飛機(jī)結(jié)構(gòu)復(fù)雜，僅使用單一種類機(jī)器人作業(yè)難以實(shí)現(xiàn)飛機(jī)蒙皮全覆蓋。所以，提出了一種空-地異構(gòu)機(jī)器人協(xié)同覆蓋路徑規(guī)劃方法（AG-CCPP）。首先引入無人機(jī)（UAV）、無人車（UGV）異構(gòu)機(jī)器人系統(tǒng)，分析規(guī)劃過程中必要的約束條件，包括作業(yè)空間約束、續(xù)航時(shí)間約束等，采用整數(shù)線性規(guī)劃方法建立優(yōu)化模型。其次，提出一種基于貪婪分配策略的多精英種群雙染色體遺傳算法進(jìn)行任務(wù)分配與路徑規(guī)劃聯(lián)合求解，增加分配染色體實(shí)現(xiàn)任務(wù)分配與路徑規(guī)劃聯(lián)合求解，實(shí)現(xiàn)全局優(yōu)化；基于續(xù)航約束進(jìn)行貪婪分配，充分利用異構(gòu)機(jī)器人優(yōu)點(diǎn)；多層次精英種群設(shè)計(jì)，減少低效交叉種群數(shù)量，提升算法運(yùn)行效率。最后，通過波音737-300的仿真實(shí)驗(yàn)進(jìn)行對(duì)比分析，結(jié)果表明所提方法在機(jī)器人協(xié)同覆蓋完成時(shí)間與程序執(zhí)行時(shí)間方面均優(yōu)于現(xiàn)有算法。

關(guān)鍵詞：飛機(jī)蒙皮檢測(cè)；異構(gòu)機(jī)器人協(xié)同；覆蓋路徑規(guī)劃；遺傳算法；任務(wù)分配

中圖分類號(hào)：TP391"" 文獻(xiàn)標(biāo)志碼：A""" 文章編號(hào)：1001-3695（2025）04-010-1044-06

doi： 10.19734/j.issn.1001-3695.2024.09.0336

Cooperative coverage path planning for aerial-ground heterogeneous robots in aircraft skin inspection tasks

Piao Minnan， Luo Jia， Li Haifeng， Zhou Yuhan

（College of Computer Science amp; Technology， Civil Aviation University of China， Tianjin 300300， China）

Abstract：The inspection of aircraft skin is critical to ensuring the safety of aircraft flights. Employing autonomous mobile robots for inspection can significantly enhance inspection efficiency and reduce safety risks. However， achieving full coverage of aircraft skin with a single type of robot is challenging due to the complexity of aircraft structures. Therefore， this paper proposed an aerial-ground cooperative coverage path planning （AG-CCPP） method for heterogeneous robots. Firstly， this paper introduced a heterogeneous robot system consisting of unmanned aerial vehicles （UAV） and unmanned ground vehicles （UGV） ， analyzed the necessary constraints in the planning process， including workspace constraints， endurance constraints， and so on， and established an optimization model using integer linear programming. Subsequently， this paper proposed a dual-chromosome genetic algorithm with a multi-elite population based on a greedy allocation strategy for jointly solving task allocation and path planning. By incorporating an allocation chromosome， it achieved joint solution for task allocation and path planning， enabling global optimization. It conducted greedy allocation based on endurance constraints， fully leveraging the advantages of heterogeneous robots. It adopted a multi-level elite population design to reduce the number of inefficient crossover populations and enhance the algorithm’s operational efficiency. Finally， simulation experiments and comparative analysis conducted on a Boeing 737-300 demonstrate that the proposed method outperforms existing algorithms in terms of both the completion time for cooperative coverage by robots and the program execution time.

Key words：aircraft skin inspection; heterogeneous robot cooperation; coverage path planning; GA; task allocation

0 引言

飛機(jī)蒙皮損傷檢測(cè)是保障飛機(jī)飛行安全的重要舉措。飛機(jī)蒙皮作為飛機(jī)的重要組成部分，在每次執(zhí)行飛行任務(wù)時(shí)，都會(huì)經(jīng)歷一次增壓與減壓的過程。長(zhǎng)期的這種交變載荷以及自然環(huán)境中的腐蝕、雷擊、冰雹等，會(huì)導(dǎo)致飛機(jī)蒙皮出現(xiàn)損傷。當(dāng)損傷達(dá)到一定程度后，將影響飛機(jī)氣動(dòng)性性能，甚至造成結(jié)構(gòu)性斷裂破壞，從而引發(fā)飛行事故。因此，為保證飛機(jī)的持續(xù)適航性與安全性，需定期對(duì)飛機(jī)蒙皮進(jìn)行檢查。當(dāng)前的檢查方式主要以專業(yè)人員采用目視或手持無損檢測(cè)設(shè)備，通過步行繞機(jī)、工作梯托舉、繩索攀爬等方式靠近待檢區(qū)域進(jìn)行檢測(cè)。這種作業(yè)方式存在檢測(cè)效率低、難以保證全覆蓋、誤檢/漏檢率高等問題。

隨著機(jī)器人以及各種檢測(cè)技術(shù)的迅猛發(fā)展，采用移動(dòng)機(jī)器人搭載檢測(cè)設(shè)備執(zhí)行該檢測(cè)任務(wù)能夠有效彌補(bǔ)上述缺陷。國內(nèi)外也有不少學(xué)者展開了相應(yīng)的研究工作，但這些工作大多采用UAV［1，2］、UGV［3，4］、爬壁機(jī)器人［5，6］等單一種類機(jī)器人。文獻(xiàn)［1，2］基于原始采樣方法生成覆蓋飛機(jī)表面的視點(diǎn)集合，并進(jìn)一步采用遺傳算法、蒙特卡羅樹搜索等方法規(guī)劃UAV的路徑。樸敏楠等人［4］針對(duì)拍攝約束和UGV運(yùn)動(dòng)約束，提出了基于單元格分解的視點(diǎn)生成方法，并基于最小化路徑點(diǎn)數(shù)量原則規(guī)劃UGV的路徑。UGV負(fù)載、續(xù)航能力較強(qiáng)，可同時(shí)攜帶高清面陣相機(jī)、主動(dòng)紅外熱成像等多種檢測(cè)設(shè)備，且運(yùn)動(dòng)穩(wěn)定，能夠?qū)崿F(xiàn)較好的定位精度以及保證作業(yè)的安全性，但是其無法覆蓋機(jī)背、機(jī)翼、尾翼等較高區(qū)域。相比而言，UAV可以靈活覆蓋到這些部位，然而其負(fù)載、續(xù)航能力較差，除環(huán)境感知傳感器外基本上只能攜帶一種檢測(cè)設(shè)備，尤其是UAV運(yùn)動(dòng)相對(duì)不穩(wěn)定，在機(jī)腹下方等狹窄空間內(nèi)運(yùn)動(dòng)仍存在風(fēng)險(xiǎn)。理論上，爬壁機(jī)器人能夠?qū)崿F(xiàn)飛機(jī)蒙皮全覆蓋檢測(cè)需求，但該種方式目前還存在檢測(cè)效率低且需要接觸式檢測(cè)的問題，在應(yīng)用上還具有一定困難。因此，基于兩種機(jī)器人的特點(diǎn)，本文首次探索將UAV與UGV相結(jié)合，研究滿足飛機(jī)蒙皮全覆蓋、高效率檢測(cè)需求的UAV和UGV協(xié)同作業(yè)方法。

協(xié)同覆蓋路徑規(guī)劃（cooperative coverage path planning，CCPP）是多機(jī)器人實(shí)現(xiàn)飛機(jī)蒙皮全覆蓋檢測(cè)任務(wù)需要解決的核心問題。該問題主要涉及視點(diǎn)集生成、視點(diǎn)分配和路徑規(guī)劃三個(gè)步驟［7］。視點(diǎn)指的是檢測(cè)設(shè)備在采集飛機(jī)蒙皮數(shù)據(jù)時(shí)的位姿，例如相機(jī)在拍攝時(shí)的位置和姿態(tài)。視點(diǎn)集生成的目的是根據(jù)待檢測(cè)飛機(jī)的模型確定一系列用于觀察或測(cè)量的視點(diǎn)的過程；視點(diǎn)分配是在視點(diǎn)集生成之后，根據(jù)具體的任務(wù)需求或優(yōu)化目標(biāo)，將視點(diǎn)分配給不同的檢測(cè)設(shè)備，以實(shí)現(xiàn)對(duì)飛機(jī)蒙皮的全覆蓋、高效檢測(cè)；路徑規(guī)劃基于分配給每個(gè)機(jī)器人的視點(diǎn)，求解旅行商問題（traveling salesman problem，TSP）確定視點(diǎn)間的遍歷順序，規(guī)劃出一條時(shí)間/能耗最優(yōu)的運(yùn)動(dòng)路徑。其中，視點(diǎn)集生成相對(duì)獨(dú)立，視點(diǎn)分配和路徑規(guī)劃可采用單獨(dú)或聯(lián)合求解框架。

對(duì)于視點(diǎn)分配和路徑規(guī)劃單獨(dú)求解，目前多采用基于聚類的方法［8～13］，其主要思想是根據(jù)機(jī)器人的數(shù)量、初始位置等信息對(duì)視點(diǎn)進(jìn)行聚類，然后將不同類視點(diǎn)分配給不同的機(jī)器人，最后針對(duì)每個(gè)機(jī)器人求解TSP。Tang等人［8］通過改進(jìn)的K-means聚類對(duì)視點(diǎn)進(jìn)行分類，并引入反饋機(jī)制以平衡每個(gè)機(jī)器人路徑的長(zhǎng)度。Collins等人［9］使用一種基于Voronoi圖的迭代聚類方法—Lloyd算法對(duì)視點(diǎn)進(jìn)行分組。Sharif等人［10］設(shè)計(jì)了一種針對(duì)風(fēng)力發(fā)電機(jī)模型的策略，首先通過K-means聚類確定分支的數(shù)量，然后根據(jù)機(jī)器人以及分支的數(shù)量進(jìn)行視點(diǎn)分配。考慮到上述方法無法處理機(jī)器人異構(gòu)的情形，文獻(xiàn)［11，12］進(jìn)一步將聚類方法進(jìn)行了拓展。Xiao等人［11］首先利用質(zhì)心迭代和時(shí)空相似性的聚類方法來劃分區(qū)域，然后采用最近端策略來優(yōu)化訪問順序，從而實(shí)現(xiàn)了異構(gòu)UAV對(duì)多區(qū)域的全覆蓋。雖然聚類過程引入了不同機(jī)器人特性差異，但是仍然只能做近似處理，例如在區(qū)域密度計(jì)算時(shí)使用了所有機(jī)器人飛行時(shí)間的平均值。單獨(dú)求解方式雖然能夠通過簡(jiǎn)化問題提高算法的運(yùn)行效率，然而在視點(diǎn)分配階段無法充分考慮機(jī)器人間的異構(gòu)特性，從而難以取得最優(yōu)或接近于最優(yōu)的高質(zhì)量解。

對(duì)于視點(diǎn)分配和路徑規(guī)劃聯(lián)合求解，已有研究大多將其描述為車輛路徑規(guī)劃問題（vehicle routing problem，VRP）的各種變種，是典型的NP-hard問題。針對(duì)這類問題主要的方法包括精確算法以及啟發(fā)式算法。文獻(xiàn)［13，14］將CCPP建模為混合整型規(guī)劃（mixed-integer linear programming，MILP）問題，并采用分支定界方法進(jìn)行求解。精確算法無法避開指數(shù)爆炸問題，只能求解小規(guī)模VRP，難以在時(shí)間限制內(nèi)求解出結(jié)果。近些年，遺傳算法［15，16］、蟻群算法［17］等啟發(fā)式算法廣泛用于CCPP。相比于精確算法，啟發(fā)式算法針對(duì)大規(guī)模問題往往能夠更加快速地找到高質(zhì)量的解。程曉明等人［15］針對(duì)大型三維結(jié)構(gòu)的覆蓋檢測(cè)問題，提出了一種工業(yè)多機(jī)器人路徑規(guī)劃的新方法。該方法通過貪心算法獲得全覆蓋視點(diǎn)集，為解決多機(jī)任務(wù)分配與路徑規(guī)劃綜合尋優(yōu)問題，提出了改進(jìn)遺傳算法。Jing等人［16］設(shè)計(jì)一種改進(jìn)的BRKGA算法實(shí)現(xiàn)多UAV對(duì)大型復(fù)雜結(jié)構(gòu)的檢測(cè)。基于文獻(xiàn)［16］，Li等人［17］進(jìn)一步采用異步蟻群優(yōu)化算法求解該問題。這些方法雖然能夠?qū)崿F(xiàn)對(duì)大型復(fù)雜三維結(jié)構(gòu)的全覆蓋，但都是針對(duì)同構(gòu)機(jī)器人設(shè)計(jì)，無法適用于本文中工作空間、檢測(cè)視野、運(yùn)動(dòng)特性差異大的異構(gòu)機(jī)器人情形。受獵物與捕食者關(guān)系的啟發(fā)，Hassan等人［18］提出了一種面向異構(gòu)機(jī)器人的CCPP方法，能夠?qū)崿F(xiàn)任務(wù)分配與路徑規(guī)劃聯(lián)合求解，但其需要迭代優(yōu)化權(quán)重參數(shù)，耗時(shí)較長(zhǎng)，此外由于采用局部貪心策略，仍無法充分考慮例如整體作業(yè)時(shí)間等全局優(yōu)化指標(biāo)。

綜上，針對(duì)當(dāng)前研究采用單一種類機(jī)器人難以實(shí)現(xiàn)飛機(jī)蒙皮全覆蓋檢查任務(wù)，且現(xiàn)有基于異構(gòu)機(jī)器人協(xié)同的覆蓋路徑規(guī)劃尚存在難以實(shí)現(xiàn)高效全局優(yōu)化的問題，本文提出了一種針對(duì)飛機(jī)蒙皮檢測(cè)任務(wù)的空-地異構(gòu)機(jī)器人協(xié)同覆蓋路徑規(guī)劃新框架（AG-CCPP）。此外，求解機(jī)器人協(xié)同覆蓋路徑規(guī)劃這一問題是一個(gè)經(jīng)典的NP-hard問題，對(duì)于較大規(guī)模情況，傳統(tǒng)的精確算法往往因?yàn)橛?jì)算量大，難以在合理時(shí)間內(nèi)求得解。遺傳算法通過使用種群中的多個(gè)個(gè)體進(jìn)行并行搜索，具有較強(qiáng)的全局搜索能力，能夠在廣泛的解空間中以較快速度尋得較優(yōu)解。同時(shí)考慮到異構(gòu)機(jī)器人的不同特性，比如可活動(dòng)空間的限制所導(dǎo)致的空間可達(dá)性約束，且遺傳算法在求解時(shí)存在較強(qiáng)的隨機(jī)性與不確定性，求解大規(guī)模問題時(shí)將會(huì)產(chǎn)生大量的無效解，因此本文采用了在遺傳算法中加入貪婪策略的思想，使每次迭代過程具有更強(qiáng)的方向性，從而實(shí)現(xiàn)快速收斂。另外，遺傳算法的隨機(jī)性與不確定性也容易導(dǎo)致迭代過程中所出現(xiàn)的優(yōu)秀個(gè)體被丟失，因此本文采用精英種群的策略以實(shí)現(xiàn)有效保留優(yōu)秀個(gè)體。并且，由于每次迭代計(jì)算成本較大，所以本文又在精英種群的基礎(chǔ)上增加了計(jì)算成本較小的隨機(jī)變異策略，通過增加種群的多樣性，并以一定概率實(shí)現(xiàn)在精英種群的基礎(chǔ)上精益求精，從而實(shí)現(xiàn)進(jìn)一步快速收斂，達(dá)到高效求解的目的。基于此，本文針對(duì)性地提出了一種改進(jìn)遺傳算法。本文主要貢獻(xiàn)如下：a）引入U(xiǎn)AV、UGV異構(gòu)機(jī)器人系統(tǒng)，實(shí)現(xiàn)飛機(jī)蒙皮的全覆蓋檢測(cè)任務(wù)，并采用整數(shù)線性規(guī)劃方法建立優(yōu)化模型，將任務(wù)分配與路徑規(guī)劃進(jìn)行耦合求解，實(shí)現(xiàn)全局優(yōu)化。b）提出一種高效的多精英種群雙染色體改進(jìn)遺傳算法。該算法考慮了不同機(jī)器人的作業(yè)空間約束、續(xù)航性約束和速度約束，采用貪婪分配策略以及多精英種群策略，能夠快速實(shí)現(xiàn)任務(wù)分配與路徑規(guī)劃的聯(lián)合求解。

1 問題描述

本文研究基于異構(gòu)機(jī)器人的飛機(jī)蒙皮視覺覆蓋檢測(cè)，如圖1所示。對(duì)于給定的飛機(jī)蒙皮檢測(cè)任務(wù)，假設(shè)飛機(jī)的三維模型是已知的，該模型主要用于機(jī)器人的視點(diǎn)集合和無碰撞路徑生成。本文使用的UAV配備六自由度云臺(tái)相機(jī)。UGV上搭載升降裝置，升降裝置頂端同樣搭載六自由度云臺(tái)相機(jī)。假設(shè)云臺(tái)的角度范圍能夠保證機(jī)器人到達(dá)規(guī)劃的視點(diǎn)姿態(tài)。為了保證飛行安全，為UAV設(shè)置最小飛行高度，即其無法檢測(cè)機(jī)腹下方的狹窄空間。為了拓展UGV的檢測(cè)范圍，并防止重心偏高帶來的安全問題，將升降裝置的高度限制在一定范圍，保證其能檢測(cè)UAV無法到達(dá)的低矮空間。在進(jìn)行機(jī)器人局部路徑規(guī)劃時(shí)，假設(shè)UAV為質(zhì)點(diǎn)，此外假設(shè)UGV在運(yùn)動(dòng)過程中保持起始視點(diǎn)處的高度不變。機(jī)器人的體積可由飛機(jī)模型膨脹安全距離來體現(xiàn)。

本文的研究基于筆者之前工作得到的視點(diǎn)集［4］。該視點(diǎn)集通過對(duì)飛機(jī)各部件模型進(jìn)行單元格分解生成，滿足拍攝距離、拍攝傾角以及拍攝重疊率約束的同時(shí)實(shí)現(xiàn)對(duì)飛機(jī)蒙皮的全覆蓋。由于假設(shè)視點(diǎn)的姿態(tài)能夠通過控制云臺(tái)實(shí)現(xiàn)，本文使用的視點(diǎn)集合不包含姿態(tài)信息，表示為Smin=xi，yi，zii=1，2，…，n，其中xi，yi，zi為第i個(gè)視點(diǎn)的位置，n為視點(diǎn)的數(shù)量。本文將重點(diǎn)研究視點(diǎn)分配和路徑規(guī)劃的聯(lián)合求解，其數(shù)學(xué)描述為

C1：X（k，i）∈SminC2：X（0，：）∪X（1，：）=SminC3：X（0，：）∩X（1，：）=C4：hmink≤hX（k，i）≤hmaxk i=1，2，…，nkXC5：TX（k，：）≤Tk

其中：k表示機(jī)器人的序列號(hào)，k=0表示UAV，k=1表示UGV；X（k，i）表示分配給機(jī)器人k的第i個(gè)視點(diǎn)的位置；nkX表示分配給機(jī)器人k的視點(diǎn)數(shù)量；DX（k，i），X（k，i+1）表示兩個(gè)路徑點(diǎn)間的無碰撞路徑長(zhǎng)度；Vk表示機(jī)器人k的線速度；X（k，：）表示分配給機(jī)器人k的所有視點(diǎn)位置的集合；hX（k，i）代表分配給機(jī)器人k的第i個(gè)視點(diǎn)的高度，hmink和hmaxk分別代表hX（k，i）的最小和最大容許值；TX（k，：）代表遍歷機(jī)器人k的視點(diǎn)所需要的總時(shí)間；Tk代表機(jī)器人k的續(xù)航時(shí)間約束。約束C1～C3保證將所有視點(diǎn)全部分配并且每個(gè)視點(diǎn)只分配給一個(gè)機(jī)器人，可以避免對(duì)視點(diǎn)的冗余訪問從而降低檢測(cè)效率。C4和C5為滿足不同機(jī)器人的可達(dá)空間和續(xù)航時(shí)間約束。由于日常的飛機(jī)蒙皮繞機(jī)檢測(cè)對(duì)作業(yè)時(shí)間有嚴(yán)格的要求，所以本文的優(yōu)化目標(biāo)設(shè)計(jì)為最小化整體的作業(yè)時(shí)間。

2 提出方案

針對(duì)飛機(jī)蒙皮全覆蓋檢測(cè)任務(wù)，本文提出了一種全新的空-地異構(gòu)機(jī)器人CCPP算法框架（AG-CCPP）。首先，根據(jù)不同機(jī)器人的可達(dá)性約束構(gòu)建可達(dá)性矩陣；之后，基于可達(dá)性矩陣，根據(jù)不同機(jī)器人的速度約束生成無碰撞路徑時(shí)間成本矩陣；最后，針對(duì)性地設(shè)計(jì)多精英種群雙染色體遺傳算法，并在其中嵌入考慮續(xù)航性約束的貪婪分配策略，實(shí)現(xiàn)任務(wù)分配與路徑規(guī)劃的聯(lián)合求解。所提方法框架如圖2所示。

2.1 可達(dá)性矩陣構(gòu)建

針對(duì)飛機(jī)結(jié)構(gòu)復(fù)雜的特點(diǎn)以及UAV、UGV的作用空間約束，本文首先對(duì)最小覆蓋視點(diǎn)集進(jìn)行分類。首先根據(jù)機(jī)器人作業(yè)高度閾值，將視點(diǎn)初步分成三類，分類情況如表1所示。

之后，針對(duì)第2、3類視點(diǎn)，進(jìn)行無人車不可穿越性約束判斷，具體判斷方法為：若該視點(diǎn)豎直向下作垂線與飛機(jī)模型產(chǎn)生碰撞，則將該視點(diǎn)劃歸為第1類視點(diǎn)集，因?yàn)闊o人車攜帶的升降裝置及云臺(tái)相機(jī)無法穿過機(jī)身抵達(dá)該視點(diǎn)位置。最終，通過這種高度閾值與無人車不可穿越性約束條件相結(jié)合的方式，得到符合實(shí)際需求的三類視點(diǎn)，并根據(jù)這三類視點(diǎn)構(gòu)造可達(dá)性矩陣。

可達(dá)性矩陣的具體構(gòu)建采用一個(gè)二行N列的二維矩陣（N為最小覆蓋視點(diǎn)集中視點(diǎn)總數(shù)），第0行表示UAV可達(dá)情況，第1行表示UG可達(dá)情況，可達(dá)則置1，不可達(dá)則置0。例如，第n個(gè)視點(diǎn)UGV可達(dá)，則AM［1， n］=1（AM表示可達(dá)性矩陣）。矩陣結(jié)構(gòu)下所示。

AM=aA0aA1...aAn...aAN-1aG0aG1...aGn...aGN-12×N

2.2 無碰撞時(shí)間成本矩陣構(gòu)建

由于異構(gòu)機(jī)器人機(jī)動(dòng)性能不同，采用時(shí)間成本代價(jià)能夠更直觀反映兩機(jī)器人運(yùn)動(dòng)代價(jià)。同時(shí)，由于兩視點(diǎn)間直連或與飛機(jī)產(chǎn)生碰撞，所以需要進(jìn)行無碰撞路徑生成。此外，遺傳算法迭代求解TSP時(shí)涉及多次重復(fù)計(jì)算兩視點(diǎn)間代價(jià)成本的操作，離線構(gòu)建成本矩陣能夠有效減少該類冗余計(jì)算，提升算法運(yùn)行效率。綜上，本文基于可達(dá)性矩陣進(jìn)行了無碰撞時(shí)間成本矩陣的構(gòu)建，具體步驟如算法1所示。其中，collision_detect（）方法用于判斷兩視點(diǎn)直連是否與飛機(jī)模型產(chǎn)生碰撞；RRT*（）方法用于尋找兩視點(diǎn)間的一條無碰撞路徑［19］；calc_Edistance（）方法用于計(jì)算兩視點(diǎn)間的歐氏距離。

算法1 Collision_free_matrix_construction

輸入：機(jī)器人k可達(dá)視點(diǎn)集VkA；機(jī)器人k線速度Vk；障礙物地圖Grid_Map。

輸出： 機(jī)器人k的無碰撞時(shí)間成本矩陣 TCost_Matrix。

TCost_Matrix ← "http://初始化時(shí)間成本矩陣

for vki ∈ VkA do" //遍歷機(jī)器人可達(dá)視點(diǎn)集

for vkj ∈ VkA do

if collision_detect（vki，vkj） then //兩視點(diǎn)直連碰撞

distance ← RRT*（vki，vkj） //使用RRT*尋找無碰撞路徑

else //若兩視點(diǎn)直連無碰撞

distance ← calc_Edistancce（vki，vkj）

end if

T_cost ← distance / Vk //計(jì)算時(shí)間成本

TCost_Matrix ← append（TCost_Matrix， T_cost）

end for

end for

return TCost_Matrix

2.3 多精英種群雙染色體遺傳算法設(shè)計(jì)

TSP問題是一個(gè)經(jīng)典的NP-hard問題，對(duì)于較大規(guī)模的問題，傳統(tǒng)的精確算法往往因?yàn)橛?jì)算量大，難以在合理時(shí)間內(nèi)求得解。遺傳算法通過使用種群中的多個(gè)個(gè)體進(jìn)行并行搜索，具有較強(qiáng)的全局搜索能力，可以在廣泛的解空間中以較快速度尋得較優(yōu)解，因而被廣泛應(yīng)用于求解TSP等NP-hard問題上。同時(shí)，CCPP中任務(wù)分配與TSP問題通常都是相互關(guān)聯(lián)的，通過聯(lián)合求解，可以將任務(wù)分配方案與旅行商路徑優(yōu)化綜合考慮，從而使得最終的結(jié)果更加全局優(yōu)化。基于上述考慮，本文在傳統(tǒng)的遺傳算法只有一條染色體的基礎(chǔ)上額外增一條分配染色體，從而實(shí)現(xiàn)多機(jī)器人任務(wù)分配與路徑規(guī)劃的聯(lián)合求解。此外，由于異構(gòu)機(jī)器人具有不同的機(jī)動(dòng)性能與續(xù)航能力，本文針對(duì)性地設(shè)計(jì)了分配策略，并且增加精英+貪婪、精英+貪婪+變異兩種種群以增加種群的多樣性，進(jìn)一步優(yōu)化求解性能。

2.3.1 編解碼與分配策略

傳統(tǒng)遺傳算法通常只有一條視點(diǎn)染色體編碼結(jié)構(gòu)，如圖3（a）所示，在解決多機(jī)器人CCPP問題時(shí)難以適用。因此，本文在其基礎(chǔ)上又增加了一條分配染色體編碼結(jié)構(gòu)，如圖3（b）所示，兩染色體通過基因在染色體中的位置一一對(duì)應(yīng)，解碼得各機(jī)器人路徑情況如圖3（c）所示。

其中，視點(diǎn)染色體中每個(gè)基因值代表每個(gè)視點(diǎn)，分配染色體中對(duì)應(yīng)的基因值通過在可達(dá)性矩陣中查找該視點(diǎn)的可達(dá)性情況以及結(jié)合所設(shè)計(jì)的貪婪分配策略得到。具體為：若該視點(diǎn)僅屬于某一機(jī)器人可達(dá)，則直接將該視點(diǎn)分配給某一機(jī)器人；若該視點(diǎn)兩機(jī)器人皆可達(dá)，則通過比較已解碼得到的兩機(jī)器人路徑時(shí)間代價(jià)決定。算法2給出了分配染色體的詳細(xì)構(gòu)建步驟。

算法2 Allocation_chromosome_construction

輸入： 視點(diǎn)染色體 C；可達(dá)性矩陣 AM；UAV續(xù)航能力TA。

輸出： 分配染色體 AC。

AC， UAV_path， UGV_path ← ， ，

for i ＜ sizeof（C） do

if AM［0， Ci］ == 0 then //若該視點(diǎn)UAV不可達(dá)

UGV_path ← append （UGV_path， Ci）

AC← append （AC， 1）

elif AM［1， Ci］ == 0 then //若該視點(diǎn)UGV不可達(dá)

UAV_path ← append （UAV_path， Ci）

AC← append （AC， 0）

else

UAV_path_cost ← calc_path_cost（UAV_path）

//如果UAV路徑成本大于其續(xù)航能力

if UAV_path_cost gt; TA then

//將該視點(diǎn)添加至UAV路徑列表

UGV_path ← append （UGV_path， Ci）

//將相應(yīng)的標(biāo)志符添加至分配染色體

AC← append （AC， 1）

else

UGV_path_cost ← calc_path_cost（UGV_path）

if UAV_path_cost gt; UGV_path_cost then

UGV_path ← append （UGV_path， Ci）

AC ← append （AC， 1）

else

UAV_path ← append （UAV_path， Ci）

AC ← append （AC， 0）

end if

end if

end if

end for

return AC

其中：sizeof（）方法用于統(tǒng)計(jì)染色體中基因個(gè)數(shù)；calc_path_cost（）方法用于計(jì)算分離出來的機(jī)器人路徑成本。

2.3.2 種群初始化

為保證種群中個(gè)體的多樣性，以增加獲得最佳方案的概率，種群初始化時(shí)，本文采取對(duì)原始視點(diǎn)染色體進(jìn)行隨機(jī)重新排列的策略，并在每次重排后通過算法2構(gòu)造相應(yīng)的分配染色體，從而得到初始的視點(diǎn)染色體種群和對(duì)應(yīng)的分配染色體種群。

2.3.3 適應(yīng)度函數(shù)設(shè)計(jì)

首先，通過將視點(diǎn)染色體與對(duì)應(yīng)的分配染色體相結(jié)合，分離出不同機(jī)器人的視點(diǎn)，從而得到不同機(jī)器人的運(yùn)動(dòng)路徑，如圖3（c）所示。然后，根據(jù)每個(gè)機(jī)器人的時(shí)間代價(jià)矩陣，計(jì)算出相應(yīng)機(jī)器人路徑的時(shí)間代價(jià)，計(jì)算公式如下：

TkX=∑nkX－1i=1D（X（k，i），X（k，i+1）Vk

（2）

之后，將得到的時(shí)間成本與對(duì)應(yīng)機(jī)器人的續(xù)航時(shí)間進(jìn)行比較。若兩條機(jī)器人路徑的時(shí)間成本都超過各自的續(xù)航時(shí)間時(shí)，優(yōu)先優(yōu)化無人機(jī)路徑，即將無人機(jī)的時(shí)間成本的倒數(shù)作為適應(yīng)度值返回；若兩機(jī)器人路徑的時(shí)間成本都在各自的續(xù)航時(shí)間內(nèi)，則返回兩條機(jī)器人路徑之間較長(zhǎng)的時(shí)間代價(jià)的倒數(shù)作為適應(yīng)度值。因?yàn)楸疚牡哪繕?biāo)是在各機(jī)器人續(xù)航約束下最小化最長(zhǎng)時(shí)間，適應(yīng)度值的計(jì)算可表示為

f=1/TAXTAXgt;TA1/max（TkX）otherwise

（3）

2.3.4 多精英種群貪婪策略

由于傳統(tǒng)遺傳算法具有較強(qiáng)的隨機(jī)性與不確定性，且本文需考慮可達(dá)性約束，在求解大規(guī)模問題時(shí)會(huì)導(dǎo)致產(chǎn)生大量無效解，所以本文采用了在遺傳算法中增加貪婪策略的思想［15］，以使每次迭代具有更強(qiáng)的方向性，從而實(shí)現(xiàn)快速收斂。同時(shí)，為進(jìn)一步提升算法性能，本文又增加了精英+貪婪變異、精英+貪婪變異+隨機(jī)變異兩種種群，使種群更加多元化，從而提升獲得更優(yōu)解的概率，并實(shí)現(xiàn)更為快速的收斂。算法3給出了新增加的精英貪婪種群策略具體步驟。

算法3 Elite_greedy_population_construction

輸入： 視點(diǎn)染色體種群 PC；適應(yīng)度列表 F；精英數(shù)量 E_Size；隨機(jī)變異數(shù)量 R_N。

輸出： 精英+貪婪變異種群 PEg；精英+貪婪+隨機(jī)變異種群 PEr。

PEg， PEr ← ，

E_Index_lst ← argsort（F， E_Size） //排序得到精英索引

for i ∈ E_Index_lst do

E ← PC［i］ //根據(jù)索引從種群中得到精英個(gè)體

Eg ← greedy_mute（E） //對(duì)精英個(gè)體進(jìn)行貪婪變異

Er ← random_mute（Eg， R_N） //隨機(jī)變異

PEg ← append（PEg，Eg）

PEr ← append（PEr，Er）

end for

return PEg， PEr

其中：argsort（）方法用于根據(jù)適應(yīng)度列表篩選出適應(yīng)度值較大的精英個(gè)體；greedy_mute（）方法用于對(duì)精英個(gè)體進(jìn)行貪婪變異，具體為對(duì)精英個(gè)體隨機(jī)生成一個(gè)變異位置索引，將該索引所指元素刪除后，再通過貪婪方式插入到精英個(gè)體中最佳位置；random_mute（）方法用于對(duì)經(jīng)過貪婪變異后的精英個(gè)體進(jìn)行隨機(jī)變異，具體為對(duì)一個(gè)經(jīng)過貪婪變異后的精英個(gè)體進(jìn)行多次隨機(jī)變異得到多個(gè)隨機(jī)變異后的個(gè)體，每個(gè)隨機(jī)變異后的個(gè)體都是通過對(duì)精英個(gè)體中的隨機(jī)兩個(gè)基因進(jìn)行對(duì)調(diào)得到，目的是以計(jì)算量較小的變異方式，得到較優(yōu)的結(jié)果，從而提升算法效率。

3 實(shí)驗(yàn)結(jié)果

本章對(duì)提出的AG-CCPP算法進(jìn)行了仿真實(shí)驗(yàn)，以驗(yàn)證其有效性。仿真環(huán)境語言為Python，所用的電腦配置為Intel CoreTM i7-8550U CPU @ 1.80 GHz 2.00 GHz。同時(shí)，為進(jìn)一步評(píng)估所提算法的性能，本章將所提方法與現(xiàn)有的兩種最先進(jìn)的多機(jī)器人覆蓋路徑規(guī)劃方法進(jìn)行了比較：基于貪婪遺傳算法的大型結(jié)構(gòu)檢查規(guī)劃器Planner［15］和受捕食者-獵物啟發(fā)的分布式多機(jī)器人覆蓋路徑規(guī)劃方法Dec-PPCPP［18］。

3.1 實(shí)驗(yàn)設(shè)置

本文選擇了一個(gè)高精度的波音737-300飛機(jī)模型作為待檢測(cè)目標(biāo)結(jié)構(gòu)，其翼展28.8 m、長(zhǎng)33.5 m、高11.0 m；最小覆蓋視點(diǎn)集來自于筆者之前的工作［4］，為380個(gè)。該視點(diǎn)集通過對(duì)飛機(jī)各部件模型進(jìn)行單元格分解生成，滿足拍攝距離、拍攝傾角以及拍攝重疊率約束的同時(shí)實(shí)現(xiàn)對(duì)飛機(jī)蒙皮的全覆蓋；同時(shí)，考慮到飛機(jī)的嚴(yán)格對(duì)稱性，以及視點(diǎn)的對(duì)稱性，因而本文對(duì)飛機(jī)一側(cè)的視點(diǎn)求解機(jī)器人協(xié)同覆蓋路徑規(guī)劃問題，得到覆蓋路徑，對(duì)另一側(cè)覆蓋路徑采用鏡像方式得到。因此，染色體長(zhǎng)度為所有視點(diǎn)數(shù)量的一半，為190個(gè)；障礙物地圖通過對(duì)飛機(jī)模型柵格化構(gòu)建，地圖柵格尺寸為0.1 m；機(jī)器人與遺傳算法相關(guān)參數(shù)分別如表2、3所示。

3.2 仿真實(shí)驗(yàn)

由于無人機(jī)不適于低空作業(yè)，無人車不適于高空作業(yè)，本文規(guī)定，hmin0=2 m，hmin1=0.3 m，hmax1=4 m。通過可達(dá)性計(jì)算，三類視點(diǎn)數(shù)量分別為160、194、26。視點(diǎn)分類結(jié)果如圖4所示，其中紅色、綠色、橙色分別代表第1、2、3類視點(diǎn)（見電子版）。

隨后，基于視點(diǎn)分類情況，進(jìn)行無碰撞路徑時(shí)間成本矩陣生成，并進(jìn)行覆蓋路徑規(guī)劃，圖5為所提算法視點(diǎn)序列規(guī)劃結(jié)果（藍(lán)色和綠色分別代表UGV、UAV視點(diǎn)序列，見電子版）。圖6為所提算法路徑規(guī)劃結(jié)果（藍(lán)色和綠色分別代表UGV、UAV路徑，見電子版）。此外，為進(jìn)一步證明所提算法的性能，本文AG-CCPP與結(jié)構(gòu)規(guī)劃器Planner［15］和Dec-PPCPP［18］進(jìn)行了對(duì)比分析，其中Planner方法的遺傳算法參數(shù)除沒有精英貪婪變異數(shù)量與隨機(jī)變異數(shù)量外，其他參數(shù)與本文遺傳算法參數(shù)一致，Dec-PPCPP的全局參數(shù)優(yōu)化采用遺傳算法實(shí)現(xiàn)。表4展示了相應(yīng)的對(duì)比結(jié)果，對(duì)比指標(biāo)為協(xié)同覆蓋任務(wù)完成時(shí)間以及算法運(yùn)行時(shí)間，其中黑體加粗表示協(xié)同覆蓋任務(wù)完成時(shí)間。

由表4可知，本文方法無論是任務(wù)完成時(shí)間還是程序運(yùn)行時(shí)間，均優(yōu)于現(xiàn)有方法。首先，通過觀察表中各機(jī)器人任務(wù)執(zhí)行時(shí)間及視點(diǎn)分配情況可以發(fā)現(xiàn)，在滿足續(xù)航性及可達(dá)性約束條件下，本文方法能夠盡可能將更多視點(diǎn)分配給機(jī)動(dòng)性能更強(qiáng)的機(jī)器人（即優(yōu)先將視點(diǎn)分配給機(jī)動(dòng)性能更強(qiáng)的機(jī)器人），從而有效縮短任務(wù)完成時(shí)間。因?yàn)槿蝿?wù)協(xié)同完成時(shí)間往往取決于機(jī)動(dòng)性能相對(duì)較差的機(jī)器人的任務(wù)完成時(shí)間，實(shí)驗(yàn)結(jié)果中視點(diǎn)分配情況與機(jī)器人任務(wù)執(zhí)行完成時(shí)間這兩項(xiàng)數(shù)據(jù)有力地證明了該點(diǎn)，并進(jìn)而驗(yàn)證了本文所提分配策略的有效性。而Planner方法由于未考慮異構(gòu)的因素，采用的是通過兩機(jī)器人視點(diǎn)數(shù)量及路徑差值的綜合比例關(guān)系決定視點(diǎn)分配給距離該視點(diǎn)分配最近的機(jī)器人還是分配給已分配視點(diǎn)數(shù)量較少的機(jī)器人，從而分配效果不如本文方法。而Dec-PPCPP方法由于采用局部貪婪策略，依次只是將離自己最近的可達(dá)視點(diǎn)納入自己的路徑集中，所以全局分配效果不佳。其次，通過比較本文方法與Planner方法的算法運(yùn)行時(shí)間可以得出，本文所提出的多精英種群策略有效提升了求解速度。這主要是因?yàn)樵谶z傳算法的每次迭代求解過程當(dāng)中，在保證滿足可行解的約束條件下進(jìn)行貪婪交叉與變異需要耗費(fèi)較多計(jì)算資源，尤其是交叉操作，從而增加運(yùn)行時(shí)間成本。而本文通過在精英種群的基礎(chǔ)上進(jìn)一步增加種群類型，從而有效減少每次迭代過程中需要進(jìn)行交叉的個(gè)體數(shù)量（即需要進(jìn)行交叉的種群中個(gè)體數(shù)量，因?yàn)槊看蔚兴玫降淖罱K子代中有部分是直接通過上次的精英種群直接遺傳得到），進(jìn)而減少交叉次數(shù)，有效縮短算法運(yùn)行時(shí)間。圖7展示了對(duì)本文方法與Planner方法運(yùn)行10次所得到的算法運(yùn)行時(shí)間對(duì)比結(jié)果。最后，通過觀察表中各機(jī)器人任務(wù)執(zhí)行時(shí)間差異，可以發(fā)現(xiàn)本文方法兩機(jī)器人執(zhí)行時(shí)間趨于一致，這也說明了本文方法的有效性，即在進(jìn)行兩者皆可達(dá)視點(diǎn)的分配時(shí)優(yōu)先分配給已分配路徑時(shí)間成本較短的機(jī)器人，從而實(shí)現(xiàn)兩機(jī)器人整體時(shí)間差異較小，保證整體任務(wù)執(zhí)行時(shí)間最短，而Dec-PPCPP由于采用局部貪心策略，抽以無法充分考慮整體作業(yè)時(shí)間全局優(yōu)化。

4 結(jié)束語

針對(duì)飛機(jī)蒙皮這一大型復(fù)雜結(jié)構(gòu)檢測(cè)任務(wù)，本文首次探索將UAV與UGV相結(jié)合，研究滿足飛機(jī)蒙皮全覆蓋、高效率檢測(cè)需求的UAV和UGV協(xié)同作業(yè)方法，提出了一種空-地異構(gòu)機(jī)器人協(xié)同檢測(cè)新方法AG-CCPP。首先引入無人機(jī)、無人車異構(gòu)機(jī)器人系統(tǒng)，充分考慮異構(gòu)機(jī)器人的作業(yè)空間約束、續(xù)航時(shí)間約束，采用整數(shù)線性規(guī)劃方法建立優(yōu)化模型，將任務(wù)分配與路徑規(guī)劃進(jìn)行耦合求解；接著，提出了一種基于貪婪分配策略的多精英種群雙染色體遺傳算法，增加分配染色體實(shí)現(xiàn)任務(wù)分配與路徑規(guī)劃聯(lián)合求解，基于續(xù)航約束進(jìn)行貪婪分配，多層次精英種群設(shè)計(jì)減少低效交叉種群數(shù)量，提升算法運(yùn)行效率，最終實(shí)現(xiàn)在滿足對(duì)飛機(jī)蒙皮全覆蓋的情況下使協(xié)同檢查時(shí)間最短；最后，通過仿真和對(duì)比實(shí)驗(yàn)，驗(yàn)證了所提方法在任務(wù)完成時(shí)間與算法運(yùn)行時(shí)間方面均優(yōu)于現(xiàn)有方法。

雖然本文方法給飛機(jī)蒙皮檢測(cè)任務(wù)提供了一個(gè)有效的解決方案，但仍有許多方面值得進(jìn)一步研究與改進(jìn)。例如機(jī)器人間的避碰、路徑的平滑和優(yōu)化以及其他不確定性處理等。

參考文獻(xiàn)：

［1］Tappe M， Dose D， Alpen M，et al. Autonomous surface inspection of airplanes with unmanned aerial systems［C］// Proc of the 7th International Conference on Automation， Robotics and Applications. Pisca-taway，NJ： IEEE Press， 2021： 135-139.

［2］Sun Yufeng， Ma Ou. Automating aircraft scanning for inspection or 3D model creation with a UAV and optimal path planning ［J］. Drones， 2022， 6 （4）： 87.

［3］Jovanevi I， Larnier S， Orteu J，et al. Automated exterior inspection of an aircraft with a pan-tilt-zoom camera mounted on a mobile robot ［J］. Journal of Electronic Imaging， 2015， 24 （6）： 061110.

［4］樸敏楠， 杜心鵬， 李海豐， 等. 飛機(jī)蒙皮圖像覆蓋采集無人車系統(tǒng)設(shè)計(jì) ［J］. 制造業(yè)自動(dòng)化， 2025， 47（2）：34-44. （Piao Minnan， Du Xinpeng， Li Haifeng， et al. Design of unmanned vehicle system for aircraft skin image overlay acquisition ［J］. Manufacturing Automation， 2025， 47（2）：34-44. ）

［5］沈桂鵬， 王從慶， 王琪. 雙框架飛機(jī)蒙皮檢測(cè)機(jī)器人切換運(yùn)動(dòng)控制方法 ［J］. 航空學(xué)報(bào)， 2015， 36（6）： 2064-2073. （Shen Guipeng， Wang Congqing， Wang Qi. Switching motion control me-thod for double-frame aircraft skin inspection robot ［J］. Acta Aeronautica et Astronautica Sinica， 2015， 36（6）： 2064-2073.）

［6］Ramalingam B， Manuel V， Elara M R，et al. Visual inspection of the aircraft surface using a teleoperated reconfigurable climbing robot and enhanced deep learning technique ［J］. International Journal of Aerospace Engineering， 2019， 2019（1）： article ID 5137139.

［7］Almadhoun R， Taha T， Seneviratne L，et al. A survey on multi-robot coverage path planning for model reconstruction and mapping ［J］. Applied Sciences， 2019， 1： 1-24.

［8］Tang Yuan， Zhou Rui， Sun Guibin，et al. A novel cooperative path planning for multirobot persistent coverage in complex environments ［J］. IEEE Sensors Journal， 2020， 20 （8）： 4485-4495.

［9］Collins L， Ghassemi P， Esfahani E T，et al. Scalable coverage path planning of multi-robot teams for monitoring non-convex areas［C］// Proc of IEEE International Conference on Robotics and Automation. Piscataway，NJ： IEEE Press， 2021： 7393-7399.

［10］Sharif M， Kanellakis C， Fresk E，et al. Cooperative coverage path planning for visual inspection ［J］. Control Engineering Practice， 2018， 74： 118-131.

［11］Xiao Peng， Li Ni， Xie Feng，et al. Clustering-based multi-region coverage-path planning of heterogeneous UAVs ［J］. Drones， 2023， 7 （11）： 664.

［12］Chen Jinchao， Du Chenglie， Zhang Ying，et al. A clustering-based coverage path planning method for autonomous heterogeneous UAVs ［J］. IEEE Trans on Intelligent Transportation Systems， 2021， 23 （12）： 25546-25556.

［13］Maini P， Yu K， Sujit P，et al. Persistent monitoring with refueling on a terrain using a team of aerial and ground robots［C］// Proc of IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway，NJ： IEEE Press， 2018： 8493-8498.

［14］Xie Junfei， Chen Jun. Multiregional coverage path planning for multiple energy constrained UAVs ［J］. IEEE Trans on Intelligent Transportation Systems， 2022， 23 （10）： 17366-17381.

［15］程曉明， 劉銀華， 趙文政. 面向大型三維結(jié)構(gòu)檢測(cè)的多機(jī)器人覆蓋路徑規(guī)劃方法 ［J］. 計(jì)算機(jī)集成制造系統(tǒng)， 2023， 29（1）： 246-253. （Cheng Xiaoming， Liu Yinhua， Zhao Wenzheng. A multi-robot coverage path planning method for large-scale 3D structure inspection ［J］. Computer Integrated Manufacturing Systems， 2023， 29（1）： 246-253. ）

［16］Jing Wei， Deng Di， Wu Yan，et al. Multi-UAV coverage path planning for the inspection of large and complex structures［C］// Proc of IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway，NJ： IEEE Press， 2020： 1480-1486.

［17］Li Hui， Chen Yang， Chen Zhihuan，et al. Multi-UAV cooperative 3D coverage path planning based on asynchronous ant colony optimization［C］// Proc of the 40th Chinese Control Conference. Piscataway，NJ： IEEE Press， 2021： 4255-4260.

［18］Hassan M， Mustafic D， Liu D. Dec-PPCPP：a decentralized predator-prey-based approach to adaptive coverage path planning amid moving obstacles［C］// Proc of IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway，NJ： IEEE Press， 2020： 11732-11739.

［19］Pharpatar P， Hérissé B， Pepy R，et al. Shortest path for aerial vehicles in heterogeneous environment using RRT*［C］// Proc of IEEE International Conference on Robotics and Automation. Piscataway，NJ： IEEE Press， 2015： 6388-6393.