基于遺傳算法和蟻群算法相結(jié)合的無人機(jī)目標(biāo)全覆蓋方法研究

李寧

廣州南方衛(wèi)星導(dǎo)航儀器有限公司，廣東廣州，510663

0 引言

隨著無人機(jī)技術(shù)的不斷發(fā)展，無人機(jī)在各個(gè)領(lǐng)域的應(yīng)用越來越廣泛。其中，無人機(jī)目標(biāo)全覆蓋是無人機(jī)應(yīng)用的一個(gè)重要問題。無人機(jī)目標(biāo)全覆蓋問題在農(nóng)業(yè)、環(huán)境監(jiān)測(cè)、災(zāi)害管理、公共安全等領(lǐng)域都有著廣泛的應(yīng)用。本文針對(duì)無人機(jī)目標(biāo)全覆蓋問題，提出了一種基于遺傳算法和蟻群算法相結(jié)合的無人機(jī)目標(biāo)全覆蓋方法。該方法可以有效地解決無人機(jī)目標(biāo)全覆蓋問題，并且相比于傳統(tǒng)的方法具有更好的性能和效果。

1 無人機(jī)區(qū)域航跡規(guī)劃總體設(shè)計(jì)方案

1.1 矩形測(cè)區(qū)的航跡規(guī)劃

矩形測(cè)區(qū)的航跡規(guī)劃是指在矩形區(qū)域內(nèi)規(guī)劃無人機(jī)航跡，以實(shí)現(xiàn)對(duì)該區(qū)域內(nèi)的目標(biāo)進(jìn)行全覆蓋的過程。該問題通常可以看作是一個(gè)優(yōu)化問題，可以利用遺傳算法、粒子群算法、模擬退火算法等進(jìn)行求解[1]。矩形測(cè)區(qū)的航跡規(guī)劃可以分為兩個(gè)步驟：第一步是規(guī)劃無人機(jī)的航跡，第二步是優(yōu)化無人機(jī)的航跡，使得無人機(jī)的飛行路徑更加平滑，從而提高飛行效率和舒適性。

1.2 傳統(tǒng)方法的局限性

傳統(tǒng)的無人機(jī)區(qū)域航跡規(guī)劃方法存在著多種局限性，無法滿足實(shí)際應(yīng)用的需求。因此，需要采用新的無人機(jī)區(qū)域航跡規(guī)劃方法，以提高規(guī)劃效率和適應(yīng)性，同時(shí)也需要考慮到多種因素的影響，以確保無人機(jī)能夠安全、高效地完成任務(wù)[2]。

1.3 航線質(zhì)量評(píng)價(jià)

無人機(jī)區(qū)域航跡規(guī)劃航線質(zhì)量評(píng)價(jià)是指對(duì)規(guī)劃出的航線進(jìn)行評(píng)估和優(yōu)化[3]，以提高航線的質(zhì)量和效率。航線質(zhì)量評(píng)價(jià)通常包括以下幾個(gè)方面。①航線長(zhǎng)度：航線長(zhǎng)度是指無人機(jī)需要飛行的總距離，航線長(zhǎng)度越短，無人機(jī)的飛行時(shí)間和能耗就越少，航線質(zhì)量就越高。②航線安全性：航線安全性是指無人機(jī)在飛行過程中避免與障礙物和限制區(qū)域發(fā)生碰撞的能力，航線安全性越高，無人機(jī)的飛行安全性就越高。③航線平滑度：航線平滑度是指無人機(jī)在飛行過程中的姿態(tài)變化和加速度變化，航線平滑度越高，無人機(jī)的飛行穩(wěn)定性就越高。④航線覆蓋率：航線覆蓋率是指無人機(jī)在飛行過程中對(duì)目標(biāo)區(qū)域的覆蓋程度，航線覆蓋率越高，無人機(jī)的巡航效率就越高。⑤航線時(shí)間：航線時(shí)間是指無人機(jī)需要完成巡航任務(wù)的時(shí)間，航線時(shí)間越短，無人機(jī)的巡航效率就越高。

1.4 總體設(shè)計(jì)方案

無人機(jī)區(qū)域航跡規(guī)劃總體設(shè)計(jì)方案需要考慮多個(gè)因素，包括以下幾個(gè)步驟。①確定任務(wù)需求：根據(jù)實(shí)際需求確定無人機(jī)的巡航任務(wù)，包括巡航區(qū)域、巡航時(shí)間、巡航目標(biāo)等。②確定巡航區(qū)域：根據(jù)任務(wù)需求和實(shí)際情況，確定無人機(jī)的巡航區(qū)域，包括巡航區(qū)域的邊界、大小和形狀等[4]。③確定巡航高度和速度：根據(jù)無人機(jī)的飛行能力和任務(wù)需求，確定無人機(jī)的巡航高度和速度，以確保無人機(jī)能夠安全、高效地完成任務(wù)。④確定航跡規(guī)劃算法：根據(jù)任務(wù)需求和巡航區(qū)域的特點(diǎn)，選擇合適的航跡規(guī)劃算法，如遺傳算法、粒子群算法等。⑤進(jìn)行航跡規(guī)劃：根據(jù)航跡規(guī)劃算法，對(duì)巡航區(qū)域進(jìn)行航跡規(guī)劃，生成無人機(jī)的航跡點(diǎn)。⑥進(jìn)行航跡優(yōu)化：對(duì)生成的航跡點(diǎn)進(jìn)行優(yōu)化，以提高航線的質(zhì)量和效率。⑦進(jìn)行航跡仿真：對(duì)優(yōu)化后的航跡進(jìn)行仿真和測(cè)試，以確保無人機(jī)能夠按照規(guī)劃的航跡順利完成任務(wù)。⑧實(shí)施巡航任務(wù)：根據(jù)航跡規(guī)劃和仿真結(jié)果，實(shí)施無人機(jī)的巡航任務(wù)，同時(shí)對(duì)巡航過程進(jìn)行監(jiān)控和控制。

2 無人機(jī)全覆蓋航跡規(guī)劃方法

2.1 規(guī)劃思想

規(guī)劃思想是優(yōu)化無人機(jī)的航跡，包括以下幾個(gè)方面。①目標(biāo)點(diǎn)分布分析：首先需要對(duì)目標(biāo)點(diǎn)的分布情況進(jìn)行分析，以確定無人機(jī)的起點(diǎn)和終點(diǎn)，并確定無人機(jī)需要覆蓋的區(qū)域[5]。②航跡規(guī)劃算法選擇：根據(jù)目標(biāo)點(diǎn)的分布情況，選擇合適的航跡規(guī)劃算法。常用的航跡規(guī)劃算法包括遺傳算法、蟻群算法、粒子群算法等。③航跡優(yōu)化：通過航跡規(guī)劃算法得到初步的航跡后，需要對(duì)航跡進(jìn)行優(yōu)化，以提高無人機(jī)的覆蓋效率和精度。常用的航跡優(yōu)化方法包括局部搜索、全局搜索等。④航跡實(shí)現(xiàn)：根據(jù)優(yōu)化后的航跡，實(shí)現(xiàn)無人機(jī)的飛行控制，使其能夠按照規(guī)劃的航跡覆蓋到所有目標(biāo)點(diǎn)。

2.2 規(guī)劃構(gòu)成

2.2.1 描述規(guī)劃空間

規(guī)劃空間指的是無人機(jī)進(jìn)行全覆蓋航跡規(guī)劃的空間范圍，通常是一個(gè)平面區(qū)域或者一個(gè)三維空間。在無人機(jī)目標(biāo)全覆蓋問題中，規(guī)劃空間的大小和形狀直接影響航跡規(guī)劃的復(fù)雜度和難度。因此，在進(jìn)行航跡規(guī)劃前需要確定規(guī)劃空間的大小和形狀，并根據(jù)實(shí)際情況選擇合適的規(guī)劃算法和優(yōu)化策略，以實(shí)現(xiàn)高效、精確的航跡規(guī)劃。同時(shí)，在規(guī)劃空間中可能存在一些障礙物或禁飛區(qū)域，需要在航跡規(guī)劃中進(jìn)行考慮和處理[6]。

2.2.2 航跡表示

無人機(jī)全覆蓋航跡規(guī)劃方法的航跡表示可以采用一系列坐標(biāo)點(diǎn)表示，這些坐標(biāo)點(diǎn)構(gòu)成了無人機(jī)的航跡。在規(guī)劃過程中，需要考慮無人機(jī)在飛行過程中的速度、飛行高度、方向等因素，以及無人機(jī)的轉(zhuǎn)彎半徑和航跡間隔等限制條件。基于這些條件和限制，可以通過優(yōu)化算法生成一系列的航跡坐標(biāo)點(diǎn)，從而實(shí)現(xiàn)無人機(jī)的全覆蓋。

2.2.3 分析約束條件

無人機(jī)全覆蓋航跡規(guī)劃構(gòu)成分析約束條件是指在航跡規(guī)劃和優(yōu)化過程中需要考慮的約束條件，首先，無人機(jī)在飛行過程中需要避免與障礙物和限制區(qū)域發(fā)生碰撞，因此需要考慮飛行安全約束條件，如避障、避讓等；其次，無人機(jī)的飛行能力是航跡規(guī)劃和優(yōu)化的重要考慮因素，需要考慮無人機(jī)的最大飛行速度、最大飛行高度、最大飛行距離等因素；再次，航跡平滑度是指無人機(jī)在飛行過程中的姿態(tài)變化和加速度變化，需要考慮航跡平滑度約束條件，以提高無人機(jī)的飛行穩(wěn)定性；航跡覆蓋率是指無人機(jī)在飛行過程中對(duì)目標(biāo)區(qū)域的覆蓋程度，也是需要考慮航跡覆蓋率約束條件[7]，以確保無人機(jī)能夠覆蓋所有目標(biāo)點(diǎn)；最后，航跡長(zhǎng)度約束條件：航跡長(zhǎng)度是指無人機(jī)需要飛行的總距離，需要考慮航跡長(zhǎng)度約束條件，以確保無人機(jī)能夠在規(guī)定時(shí)間內(nèi)完成任務(wù)。

2.2.4 確定代價(jià)函數(shù)

確定代價(jià)函數(shù)是無人機(jī)全覆蓋航跡規(guī)劃方法中的一個(gè)關(guān)鍵步驟。代價(jià)函數(shù)是衡量航跡規(guī)劃質(zhì)量的指標(biāo)，可以根據(jù)實(shí)際需求設(shè)計(jì)。常見的代價(jià)函數(shù)包括覆蓋率、航跡長(zhǎng)度、能耗、飛行時(shí)間等。選擇合適的代價(jià)函數(shù)有助于提高航跡規(guī)劃的精度和效率，同時(shí)還能夠根據(jù)實(shí)際需求進(jìn)行定制化設(shè)計(jì)。

例如，在目標(biāo)全覆蓋問題中，可以將代價(jià)函數(shù)定義為覆蓋率與航跡長(zhǎng)度之和的加權(quán)和，其中覆蓋率表示無人機(jī)對(duì)目標(biāo)區(qū)域的覆蓋程度，航跡長(zhǎng)度表示無人機(jī)在規(guī)劃空間中飛行的總距離。通過優(yōu)化代價(jià)函數(shù)，可以得到滿足覆蓋率要求的最短航跡，從而實(shí)現(xiàn)無人機(jī)的全覆蓋任務(wù)。在確定代價(jià)函數(shù)時(shí)需要考慮實(shí)際需求和可行性，同時(shí)還需要注意代價(jià)函數(shù)的計(jì)算復(fù)雜度，以確保航跡規(guī)劃過程的高效性。

2.2.5 航跡平滑

航跡平滑是指對(duì)于經(jīng)過優(yōu)化的無人機(jī)航跡，進(jìn)一步優(yōu)化航跡形狀和飛行軌跡，使其更加平滑和符合實(shí)際飛行要求的過程。航跡平滑可以減小無人機(jī)的飛行姿態(tài)變化，降低飛行的震動(dòng)和噪聲，從而提高航跡規(guī)劃的效果和舒適性。航跡平滑的實(shí)現(xiàn)可以采用多種方法，其中比較常用的方法包括三次樣條曲線擬合、二次規(guī)劃、局部最小化等。

2.3 航跡規(guī)劃算法

航跡規(guī)劃算法是指在無人機(jī)飛行任務(wù)中，根據(jù)任務(wù)需求和環(huán)境條件，通過計(jì)算和優(yōu)化，生成無人機(jī)的航跡點(diǎn)和航跡線的算法。常用的航跡規(guī)劃算法包括以下幾種。①A算法：A算法是一種啟發(fā)式搜索算法，可以在有限時(shí)間內(nèi)找到最優(yōu)解，適用于航跡規(guī)劃和優(yōu)化問題[8]。②Dijkstra算法：Dijkstra算法是一種貪心算法，可以在有限時(shí)間內(nèi)找到最短路徑，適用于航跡規(guī)劃和優(yōu)化問題。③RRT算法：RRT算法是一種基于隨機(jī)采樣的搜索算法，可以在復(fù)雜環(huán)境中生成無人機(jī)的航跡點(diǎn)和航跡線，適用于航跡規(guī)劃和優(yōu)化問題。④Dubins曲線算法：Dubins曲線算法是一種基于最小曲率路徑的航跡規(guī)劃算法，可以生成無人機(jī)的航跡點(diǎn)和航跡線，適用于航跡規(guī)劃和優(yōu)化問題。

3 單聯(lián)通區(qū)域全覆蓋航跡規(guī)劃

3.1 牛耕法的調(diào)整

單聯(lián)通區(qū)域全覆蓋航跡規(guī)劃的牛耕法調(diào)整需要考慮以下幾個(gè)方面。第一，區(qū)域劃分：將單聯(lián)通區(qū)域劃分成若干個(gè)小塊，以便更好地規(guī)劃航跡。劃分的大小和形狀應(yīng)該根據(jù)無人機(jī)的飛行能力和任務(wù)需求來確定。第二，航跡規(guī)劃順序：根據(jù)區(qū)域劃分的結(jié)果，確定航跡規(guī)劃的順序。一般來說，應(yīng)該按照塊的大小和形狀，從小到大依次規(guī)劃航跡，以確保無人機(jī)能夠高效地覆蓋整個(gè)區(qū)域[9]。第三，航跡點(diǎn)的密度：根據(jù)塊的大小和形狀，確定航跡點(diǎn)的密度。一般來說，塊越小，航跡點(diǎn)的密度就應(yīng)該越高，以確保無人機(jī)能夠覆蓋整個(gè)塊。第四，航跡點(diǎn)的位置：根據(jù)塊的形狀和無人機(jī)的飛行能力，確定航跡點(diǎn)的位置。一般來說，應(yīng)該選擇塊的中心位置或者邊緣位置作為航跡點(diǎn)，以確保無人機(jī)能夠高效地覆蓋整個(gè)塊。第五，航跡線的優(yōu)化：根據(jù)航跡點(diǎn)的位置和無人機(jī)的飛行能力，對(duì)航跡線進(jìn)行優(yōu)化。一般來說，應(yīng)該選擇最短路徑或者最優(yōu)路徑作為航跡線，以確保無人機(jī)能夠高效地覆蓋整個(gè)塊。

3.2 基于非線性自適應(yīng)權(quán)重粒子群算法的凸多邊形軌跡規(guī)劃

基于非線性自適應(yīng)權(quán)重粒子群算法的凸多邊形軌跡規(guī)劃是一種常用的無人機(jī)軌跡規(guī)劃方法。它可以將航跡規(guī)劃問題轉(zhuǎn)化為優(yōu)化問題，并利用非線性自適應(yīng)權(quán)重粒子群算法進(jìn)行求解。這種方法具有求解效率高、精度高等優(yōu)點(diǎn)，已被廣泛應(yīng)用于無人機(jī)目標(biāo)跟蹤、地形跟蹤等領(lǐng)域。凸多邊形軌跡規(guī)劃是指在凸多邊形內(nèi)部規(guī)劃無人機(jī)航跡，使得無人機(jī)可以覆蓋凸多邊形內(nèi)的所有區(qū)域，并且飛行路徑最短。在這個(gè)問題中，首先需要將凸多邊形劃分為多個(gè)三角形，然后再利用非線性自適應(yīng)權(quán)重粒子群算法對(duì)無人機(jī)的航跡進(jìn)行規(guī)劃。

3.3 凹多邊形全覆蓋航跡規(guī)劃方法

單聯(lián)通區(qū)域全覆蓋航跡規(guī)劃的凹多邊形全覆蓋航跡規(guī)劃方法是一種針對(duì)凹多邊形區(qū)域的航跡規(guī)劃方法，將凹多邊形區(qū)域劃分成若干個(gè)凸多邊形，通過優(yōu)化航跡點(diǎn)和航跡線，以實(shí)現(xiàn)全覆蓋航跡規(guī)劃。

4 基于改進(jìn)蟻群算法的區(qū)域航跡規(guī)劃

4.1 基本蟻群算法

區(qū)域航跡規(guī)劃的基本蟻群算法是一種基于螞蟻尋找食物的行為來尋找最優(yōu)解的算法，其基本思路是將區(qū)域劃分成若干個(gè)小塊，然后通過模擬螞蟻尋找食物的行為來尋找最優(yōu)的航跡點(diǎn)和航跡線。

4.2 改進(jìn)的蟻群算法

區(qū)域航跡規(guī)劃改進(jìn)的蟻群算法是在基本蟻群算法的基礎(chǔ)上，通過引入一些改進(jìn)措施來提高算法的效率和精度。以下是常見的改進(jìn)措施。第一，多目標(biāo)優(yōu)化：將航跡規(guī)劃問題轉(zhuǎn)化為多目標(biāo)優(yōu)化問題，同時(shí)考慮航跡長(zhǎng)度、時(shí)間、能耗等多個(gè)因素，以達(dá)到更好的航跡規(guī)劃效果。第二，動(dòng)態(tài)調(diào)整參數(shù)：根據(jù)螞蟻的行走結(jié)果，動(dòng)態(tài)調(diào)整參數(shù)，如信息素?fù)]發(fā)速率、信息素釋放量等，以提高算法的效率和精度。第三，路徑優(yōu)化：在螞蟻行走過程中，對(duì)路徑進(jìn)行優(yōu)化，如路徑平滑、路徑長(zhǎng)度優(yōu)化等，以提高航跡規(guī)劃的效果。第四，并行計(jì)算：采用并行計(jì)算的方式，同時(shí)處理多個(gè)螞蟻的行走過程，以提高算法的效率。第五，蟻群混合算法：將蟻群算法與其他優(yōu)化算法相結(jié)合，如遺傳算法、粒子群算法等，以提高算法的效率和精度。

4.3 基于改進(jìn)蟻群算法的區(qū)域間航跡規(guī)劃

基于改進(jìn)蟻群算法的區(qū)域間航跡規(guī)劃是針對(duì)多個(gè)區(qū)域之間的航跡規(guī)劃問題的解決方案。其基本思路是將多個(gè)區(qū)域劃分成若干個(gè)小塊，通過改進(jìn)蟻群算法來尋找最優(yōu)的航跡點(diǎn)和航跡線，以實(shí)現(xiàn)區(qū)域間的航跡規(guī)劃?；诟倪M(jìn)蟻群算法的區(qū)域間航跡規(guī)劃是一種高效、精確的航跡規(guī)劃方法，可以根據(jù)具體情況進(jìn)行調(diào)整，以適應(yīng)不同區(qū)域和無人機(jī)飛行需求[10]。

5 結(jié)論

總之，文中提出的無人機(jī)目標(biāo)全覆蓋技術(shù)將為數(shù)字化轉(zhuǎn)型提供支撐，在未來智能電網(wǎng)建設(shè)中發(fā)揮更大的作用，同時(shí)為以自動(dòng)駕駛巡視為主的工作模式奠定堅(jiān)實(shí)基礎(chǔ)。