空中機(jī)器人路徑規(guī)劃算法研究

林文

（長(zhǎng)沙航空職業(yè)技術(shù)學(xué)院，湖南長(zhǎng)沙 410014）

1 引言

空中機(jī)器人的發(fā)展至今已有70多年歷史，已經(jīng)取得豐碩的研究成果。特別是其典型組成部分無(wú)人機(jī)技術(shù)已經(jīng)在諸多領(lǐng)域取得了成功應(yīng)用。當(dāng)前，空中機(jī)器人在軍事領(lǐng)域和民用領(lǐng)域都已經(jīng)發(fā)揮了越來(lái)越重要的作用。

在軍事方面，空中機(jī)器人既能夠執(zhí)行殺傷性任務(wù)，又能夠執(zhí)行非殺傷性任務(wù)。已經(jīng)從擔(dān)負(fù)單純的空中偵察、靶機(jī)擴(kuò)展到情報(bào)監(jiān)視、指揮和控制、火力制導(dǎo)、導(dǎo)彈導(dǎo)航、充當(dāng)誘餌、電子戰(zhàn)、通信中繼、邊境巡邏、戰(zhàn)場(chǎng)評(píng)估甚至戰(zhàn)斗等任務(wù)。目前，固定翼空中機(jī)器人已經(jīng)在為軍隊(duì)服務(wù)，在幾次局部戰(zhàn)爭(zhēng)和反恐戰(zhàn)爭(zhēng)中由于其體積小、成本低、隱蔽性強(qiáng)無(wú)、機(jī)動(dòng)靈活、無(wú)人員傷亡且戰(zhàn)場(chǎng)生存能力強(qiáng)等特點(diǎn)都發(fā)揮了重要作用，取得了良好的軍事效益，具有巨大的應(yīng)用前景。當(dāng)前的世界局勢(shì)決定了未來(lái)戰(zhàn)爭(zhēng)將是高技術(shù)條件下的局部戰(zhàn)爭(zhēng)，在這種形式下空中機(jī)器人也將有更廣闊的應(yīng)用空間。

在民用方面，隨著科技的發(fā)展，各種微小型的空中機(jī)器人憑借采購(gòu)和使用費(fèi)用低、使用方式靈活等優(yōu)點(diǎn)，已經(jīng)可以替代有人機(jī)完成搜救救援、空中巡邏、交通監(jiān)控、資源勘探、災(zāi)情監(jiān)測(cè)、電力巡線、森林防火、對(duì)地觀測(cè)、農(nóng)藥噴灑等任務(wù)，具有光明的應(yīng)用前景和市場(chǎng)效益。

隨著空中機(jī)器人在軍事領(lǐng)域中的作用逐漸增大，我國(guó)對(duì)于空中機(jī)器人的研究也越來(lái)越多，越來(lái)越深入，也取得了一定的研究成果。路徑規(guī)劃是空中機(jī)器人的主要技術(shù)之一，也成為了很多科研人員的研究方向。本文從軍事角度出發(fā)，從戰(zhàn)場(chǎng)威脅方面來(lái)對(duì)空中機(jī)器人的路徑規(guī)劃進(jìn)行研究。

2 戰(zhàn)場(chǎng)環(huán)境的Voronoi圖構(gòu)建

2.1 Voronoi圖定義

Voronoi圖又稱為泰森多邊形或者Dirichlet圖。Voronoi圖是對(duì)平面n個(gè)離散點(diǎn)而言的，它把平面分為幾個(gè)區(qū)，每一個(gè)區(qū)包括一個(gè)點(diǎn)，該點(diǎn)所在的區(qū)是到該點(diǎn)距離最近點(diǎn)的集合。設(shè)P是一離散點(diǎn)集合P1，P2，…Pn∈P，定義Pi的Voronoi區(qū)域V（Pi）為所有到Pi距離最小點(diǎn)的集合：V（Pi）={P/d（P，Pi）≤d（P，Pj），j≠i，j=1，2，…n}

假設(shè)P是一離散點(diǎn)集合，P1，P2，…Pn∈P，定義P的Voronoi圖V（P）為：V（P）={V（P1）,V（P2）,…,V（Pn）}，其中Pi稱為V圖生成元。

2.2 Voronoi圖的特性

（1）vor（s）把平面劃分為n個(gè)多邊形域，每個(gè)多邊形域V（pi）包含且只包含S的一個(gè)點(diǎn)pi。

（2）vor（s）的邊是S中某對(duì)點(diǎn)的中垂線的一個(gè)線段或者射線。

（3）V（pi）是無(wú)界的，當(dāng)且僅當(dāng)pi屬于凸包外界的點(diǎn)集。（4）Voronoi圖之多有2*n-5個(gè)頂點(diǎn)和3*n-6條邊。

（5）每個(gè)Voronoi點(diǎn)恰好是三條Voronoi邊的交點(diǎn)（假設(shè)任何四點(diǎn)都不共圓的話）。也就是說(shuō)Voronoi點(diǎn)就是形成三邊的三點(diǎn)的外界圓圓心，而且所有的這些外界圓都有個(gè)特點(diǎn)：各自內(nèi)部不含任何S點(diǎn)集的點(diǎn)（空心圓）。

從上面的Voronoi圖特性可以看出，Voronoi圖的邊是能夠最好地規(guī)避對(duì)應(yīng)的兩個(gè)威脅的線段，因此，選擇Voronoi圖來(lái)構(gòu)造整個(gè)戰(zhàn)場(chǎng)，不但可以把路徑規(guī)劃的空間進(jìn)行簡(jiǎn)化，而且很大程度上提高了工作效率。

2.3 Voronoi圖的構(gòu)造

目前，對(duì)于Voronoi圖的構(gòu)造已經(jīng)有了很成熟的算法，不過(guò)，根據(jù)算法計(jì)算出來(lái)的Voronoi圖的頂點(diǎn)沒(méi)有包含空中機(jī)器人的起始位置和目標(biāo)位置，要對(duì)起始位置和目標(biāo)位置之間的最佳路徑進(jìn)行規(guī)劃，就必須把這兩個(gè)位置添加到Voronoi圖中。具體的方法是將空中機(jī)器人的起始位置作為Voronoi圖的一個(gè)頂點(diǎn)，然后將這個(gè)頂點(diǎn)與Voronoi圖中與之最近的3個(gè)點(diǎn)連接起來(lái)，對(duì)于目標(biāo)位置也進(jìn)行相應(yīng)操作，從而計(jì)算出最短路徑的Voronoi圖。

3 路徑段的代價(jià)計(jì)算

由于在構(gòu)造Voronoi圖時(shí)，是把所有的威脅的中心位置當(dāng)成母點(diǎn)。然而，在實(shí)際的戰(zhàn)場(chǎng)上，所有的威脅都是有一定作用范圍的，因此，要在戰(zhàn)場(chǎng)上對(duì)空中機(jī)器人進(jìn)行路徑規(guī)劃，就必須要模擬戰(zhàn)場(chǎng)的真實(shí)環(huán)境。本文從禁飛區(qū)、火力威脅和雷達(dá)探測(cè)威脅三個(gè)方面來(lái)進(jìn)行路徑規(guī)劃研究。

3.1 禁飛區(qū)和威脅的處理

禁飛區(qū)、火力威脅和雷達(dá)探測(cè)威脅都是對(duì)空中機(jī)器人飛行障礙。具體來(lái)說(shuō)，可以分為兩類威脅，一類是軟殺傷威脅，一類是硬殺傷威脅。軟殺傷威脅包括火力威脅和雷達(dá)探測(cè)威脅，當(dāng)空中機(jī)器人進(jìn)入這類區(qū)域，可能會(huì)被殺傷或者被探測(cè)到，但是如果成功穿越了這類威脅的作用區(qū)域，就有不被損毀的概率；硬殺傷威脅則是主要指禁飛區(qū)，禁飛區(qū)是由于政治因素或者物理因素限定不允許飛行的區(qū)域，空中機(jī)器人一旦穿越，就會(huì)被損毀。在對(duì)空中機(jī)器人進(jìn)行路徑規(guī)劃時(shí)，必須對(duì)軟殺傷威脅和硬殺傷威脅進(jìn)行計(jì)算，軟殺傷威脅的相關(guān)計(jì)算信息包括威脅的中心位置，作用半徑和殺傷概率，硬殺傷威脅的計(jì)算信息包括禁飛區(qū)的中心位置和半徑。對(duì)空中機(jī)器人進(jìn)行路徑規(guī)劃時(shí)，對(duì)每個(gè)Voronoi圖的邊的代價(jià)估計(jì)應(yīng)該要對(duì)每個(gè)威脅進(jìn)行相應(yīng)處理。

3.2 代價(jià)計(jì)算

在Voronoi圖構(gòu)造完成之后，圖中的邊是最后規(guī)劃路徑的組成，稱為路徑段。要進(jìn)行路徑規(guī)劃，就必須要對(duì)每個(gè)路徑段進(jìn)行代價(jià)計(jì)算，代價(jià)計(jì)算主要有兩個(gè)方面，一個(gè)是威脅接近代價(jià)，一個(gè)是燃料代價(jià)。這兩個(gè)代價(jià)的加權(quán)和就是這個(gè)路徑段總代價(jià)。具體公式如下：

其中，Ji是路徑段的總代價(jià)，Jit是威脅接近代價(jià)，Jif是燃油代價(jià)，k是加權(quán)系數(shù)，范圍在0-1之間。在計(jì)算路徑段總代價(jià)的時(shí)候，需要根據(jù)任務(wù)的安全要求和燃油要求，對(duì)k的值進(jìn)行相應(yīng)調(diào)整。根據(jù)路徑段總代價(jià)的計(jì)算方法，對(duì)Voronoi圖中的每條邊進(jìn)行代價(jià)計(jì)算，然后就對(duì)最優(yōu)路徑進(jìn)行計(jì)算。

4 最優(yōu)路徑生成

4.1 初始路徑生成

根據(jù)上面的步驟完成Voronoi圖中每條邊的代價(jià)和之后，再把各條邊的代價(jià)值的有向圖G計(jì)算出來(lái)，G=（V，A，W），V是Voronoi頂點(diǎn)的集合，A是頂點(diǎn)之間Voronoi邊的集合，W表示邊的代價(jià)值，其中，V（v1，v2，v3·······vn），n是頂點(diǎn)的個(gè)數(shù)。利用有解有向圖的Dijstra最短路徑法來(lái)進(jìn)行計(jì)算，從而得出指定節(jié)點(diǎn)之間的最短路徑，進(jìn)而得出空中機(jī)器人的起始位置和目標(biāo)位置之間的初始路徑。

4.2 路徑修正

Dijstra算法只是能夠計(jì)算出最短路徑，也就是Voronoi圖中的最佳路徑，然而，這是否符合空中機(jī)器人的是實(shí)際情況，是否適應(yīng)空中機(jī)器人的實(shí)際飛行需求，還需要進(jìn)一步的修正。具體來(lái)說(shuō)，需要從以下幾個(gè)方面來(lái)進(jìn)行修正：第一，是否能夠進(jìn)一步縮短空中機(jī)器人的飛行距離；第二，在Voronoi圖中的兩條邊，其夾角是不是滿足空中機(jī)器人飛行的最小轉(zhuǎn)彎半徑，如果不能滿足，就必須要進(jìn)行相應(yīng)修正；第三，如果空中機(jī)器人的初始航向角與路徑規(guī)劃時(shí)的起始航向角之間差異太大，也需要進(jìn)行修正。

4.2.1 縮短距離的處理

從Voronoi圖的定義和特點(diǎn)來(lái)看，Voronoi圖的邊會(huì)最大程度地避免母點(diǎn)，因此，Voronoi圖是在戰(zhàn)場(chǎng)進(jìn)行空中機(jī)器人路徑規(guī)劃的最佳方案。然而，在實(shí)際的戰(zhàn)場(chǎng)上面，空中機(jī)器人只需要避免威脅，而不需要圍著每個(gè)威脅來(lái)走折線。因此，在進(jìn)行路經(jīng)修正時(shí)，可以通過(guò)直線化來(lái)縮短飛行距離。

具體方法如下：假設(shè)初始路徑中的各個(gè)點(diǎn)分別是（xs，ys）（x1，y1）（x2，y2）（x3，y3）···（xi，yi）···（xn，yn）（xt，yt）。其中，（xs，ys）為起始位置，（xt，yt）是目標(biāo)位置，在整條路徑上，總共有n個(gè)節(jié)點(diǎn)數(shù)?？s短路徑的步驟就是把當(dāng)前點(diǎn)當(dāng)作目標(biāo)點(diǎn)，從當(dāng)前點(diǎn)出發(fā)依次向之前的點(diǎn)進(jìn)行連線，如果連線穿越了威脅，記錄這個(gè)點(diǎn)之前的那個(gè)點(diǎn)當(dāng)作當(dāng)前點(diǎn)，把這個(gè)當(dāng)前點(diǎn)與上一個(gè)當(dāng)前點(diǎn)之間的節(jié)點(diǎn)刪除。然后重復(fù)這些步驟，重新從這個(gè)當(dāng)前點(diǎn)出發(fā)，再繼續(xù)往前連線，直到到達(dá)初始點(diǎn)位置。

4.2.2 路徑中的拐角的平滑處理

在Voronoi圖中的兩條邊，如果夾角太過(guò)尖銳，就會(huì)讓空中機(jī)器人無(wú)法正常轉(zhuǎn)彎，因此，需要對(duì)太過(guò)尖銳的夾角進(jìn)行平滑處理。進(jìn)行平滑處理就是在尖銳的拐角處加一個(gè)圓弧，這個(gè)圓弧的半徑通常都是選擇空中機(jī)器人的最小轉(zhuǎn)彎半徑，從而，可以讓空中機(jī)器人順利轉(zhuǎn)彎。

4.2.3 初始航向角處理

如果空中機(jī)器人的初始航向角與路徑規(guī)劃時(shí)的起始航向角之間差異太大，需要對(duì)航向角進(jìn)行相應(yīng)修正。對(duì)航向角進(jìn)行修正，首先需要沿著與當(dāng)前位置相連的圓弧進(jìn)行飛行，然后轉(zhuǎn)入第二個(gè)圓弧，第二個(gè)圓弧是與第一個(gè)圓弧光滑連接的，然后并接入第一段路徑，第一段圓弧與空中機(jī)器人航向光滑銜接。這兩個(gè)圓弧的連接點(diǎn)，就是路徑上面空中機(jī)器人當(dāng)前狀態(tài)到達(dá)期望路徑的轉(zhuǎn)節(jié)點(diǎn)。需要注意的是，兩個(gè)圓弧之間的半徑應(yīng)該要大于等于空中機(jī)器人的最小轉(zhuǎn)彎半徑，從而保證空中機(jī)器人能夠順利轉(zhuǎn)彎。這樣，就可以在路徑出發(fā)點(diǎn)不變的情況下，只需要進(jìn)行少量調(diào)整，就可以改變空中機(jī)器人的飛行航向角。

通過(guò)縮短距離的處理、路徑中的拐角的平滑處理和初始航向角處理，就可以得出空中機(jī)器人的最優(yōu)路徑，這也是在已經(jīng)給定威脅分布的戰(zhàn)場(chǎng)環(huán)境下，空中機(jī)器人的飛行最優(yōu)路徑。

5 結(jié)論

本文對(duì)已經(jīng)明確威脅分布的戰(zhàn)場(chǎng)環(huán)境下，空中機(jī)器人的飛行最優(yōu)路徑進(jìn)行了研究。在已經(jīng)明確威脅分布的戰(zhàn)場(chǎng)環(huán)境中，通過(guò)Voronoi圖構(gòu)建避免威脅的初始路徑段，然后根據(jù)這些威脅的具體情況，計(jì)算出待選路徑段的代價(jià)值，再利用Dijstra算法計(jì)算出初始路徑，最后再進(jìn)行縮短距離的處理、路徑中的拐角的平滑處理和初始航向角處理，從而得出空中機(jī)器人的飛行最優(yōu)路徑。

[1]丁希侖；俞玉樹.一種多旋翼多功能空中機(jī)器人及其腿式壁面行走運(yùn)動(dòng)規(guī)劃[J].航空學(xué)報(bào)，2010，56(10)：175-186.

[2]張銀玲;牛小梅.蟻群算法在移動(dòng)機(jī)器人路徑規(guī)劃中的仿真研究[J].計(jì)算機(jī)仿真，2011，28(06)：237-240.

[3]鄔再新;李艷宏;劉濤.多移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)的研究現(xiàn)狀與展望 [J].機(jī)械，2008，47(01)：6-8+21.