久久一区二区免费播放,国产在线欧美日韩一区二区,国产综合色在线视频,精品伊人久久久香线蕉,精品视频麻豆网站,玖玖国产,国内精品久久久久影,在线观看精品视频一区二区三区,午夜久久影院,国产精品一区久久

一種基于改進(jìn)a*算法的無人機(jī)航線規(guī)劃算法
【專利摘要】本發(fā)明涉及一種無人機(jī)在大范圍復(fù)雜三維空間的航線規(guī)劃算法，包括以下步驟，首先基于2.5維網(wǎng)格(每個網(wǎng)格點包含經(jīng)度、緯度、高程信息)劃分三維空間；然后在雷達(dá)、災(zāi)害天氣、禁飛區(qū)等約束條件下，綜合考慮航線高度、被探測概率、航線長度等影響因子改進(jìn)A*代價函數(shù)，基于算法搜索流程，確定初始航線；最后為了滿足無人機(jī)性能約束(包括最小步長、轉(zhuǎn)彎半徑、爬升率、安全高度等)，進(jìn)行一系列處理得到最終的可飛行航線。本發(fā)明涉及算法穩(wěn)定、收斂性好、效率高、可滿足大范圍低空航線規(guī)劃要求，可運用于軍事國防、應(yīng)急救災(zāi)等相關(guān)領(lǐng)域之中。
【專利說明】—種基于改進(jìn)A*算法的無人機(jī)航線規(guī)劃算法

【技術(shù)領(lǐng)域】
[0001]本發(fā)明具體涉及一種算法，特別是一種用于無人機(jī)在大范圍復(fù)雜三維空間的航線規(guī)劃算法。

【背景技術(shù)】
[0002]現(xiàn)代軍事低空突防主要由無人機(jī)完成，為了提高無人機(jī)低空突防生存概率和作戰(zhàn)效能，需要利用地形的遮蔽作用，在敵防御系統(tǒng)盲區(qū)內(nèi)低空或超低空飛行。其中，關(guān)鍵問題是無人機(jī)的航線規(guī)劃。對于該問題的研究已有多年的歷史，有很多研究成果。一些學(xué)者試圖在人工智能等相關(guān)領(lǐng)域?qū)ふ抑悄軆?yōu)化算法，但它們解決大范圍無人機(jī)路徑搜索問題都有一些常見的弊病。A*算法在二維圖形搜索領(lǐng)域的成熟運用使得它解決該問題具有先天的優(yōu)勢，但目前成果存在以下問題:(I)目標(biāo)空間為小范圍人造簡單地形圖，障礙物少且規(guī)則，未考慮雷達(dá)、惡劣天氣等復(fù)雜威脅體。無法體現(xiàn)算法在復(fù)雜環(huán)境中的適應(yīng)性、收斂性及效率問題。(2) —些學(xué)者使用平面區(qū)域劃分(Voronoi圖等)的方法，這類空間劃分是基于一定高度的，因此本質(zhì)上依然是在二維空間中進(jìn)行路徑規(guī)劃。但山區(qū)地形實時截面運算的計算量太大，而且無人機(jī)基于一定高度上飛行的理論前提不成立。(3)不考慮無人機(jī)的機(jī)動性能約束，不是可飛航線。


【發(fā)明內(nèi)容】

[0003]本發(fā)明目的在于提供一種表用于無人機(jī)在大范圍復(fù)雜三維空間的航線規(guī)劃算法，所涉及算法可滿足大范圍低空航線規(guī)劃要求。
[0004]本發(fā)明采用的技術(shù)方案如下:
[0005]首先將三維連續(xù)空間使用離散二維空間表示，即規(guī)劃空間表示為一定經(jīng)差和緯差離散網(wǎng)格的網(wǎng)絡(luò)圖，并且為每個節(jié)點賦予當(dāng)?shù)氐匦蔚母叱绦畔ⅲ蝗缓笤诶走_(dá)、災(zāi)害天氣、禁飛區(qū)等約束條件下，改進(jìn)A*代價函數(shù)使航線高度、被探測概率、航線長度三項指標(biāo)同方向作用關(guān)系，并進(jìn)行歸一化處理，在此基礎(chǔ)上使用算法搜索流程，確定初始航線；在無人機(jī)最小步長、轉(zhuǎn)彎半徑、爬升率、安全高度約束下，建立航線保護(hù)區(qū)模型，進(jìn)行一系列處理得到最終的可飛行航線，最后檢驗算法的穩(wěn)定性和收斂性以及效率。
[0006]本發(fā)明與現(xiàn)有技術(shù)相比具有以下優(yōu)點:
[0007]基于2.5維網(wǎng)格模型，每個節(jié)點的鄰域僅僅存在8個可擴(kuò)展方向，算法計算效率要遠(yuǎn)大于3維網(wǎng)格劃分方式；在雷達(dá)、災(zāi)害天氣、禁飛區(qū)等約束條件下，將航線高度、被探測概率、航線長度進(jìn)行歸一化處理，改進(jìn)了 A*算法；在無人機(jī)最小步長、轉(zhuǎn)彎半徑、爬升率、安全高度約束下，優(yōu)化了航線。本發(fā)明涉及算法穩(wěn)定、收斂性好、效率高、可滿足大范圍低空航線規(guī)劃要求。

【具體實施方式】
[0008]以下以航線規(guī)劃算法流程對本發(fā)明作進(jìn)一步的詳細(xì)說明，但本發(fā)明的保護(hù)范圍并不局限于此。
[0009]I目標(biāo)空間劃分
[0010]A*算法是一種啟發(fā)式搜索算法，需要一個由點和邊組成的網(wǎng)絡(luò)空間，在此目標(biāo)空間中引入啟發(fā)信息，由定義好的代價函數(shù)確定節(jié)點拓展的規(guī)則，最終得到兩點之間的最優(yōu)路徑。但基于DEM和DOM的三維環(huán)境本質(zhì)上是一個連續(xù)狀態(tài)的柵格空間，并不存在傳統(tǒng)二維路徑搜索中的路由網(wǎng)，從而無法利用路徑搜索算法尋找最短路徑中的節(jié)點和邊，必須對其進(jìn)行空間劃分。
[0011]一些研究嘗試使用規(guī)則三維網(wǎng)格的空間劃分方法。該方法的最大問題在于每個節(jié)點的可擴(kuò)展方向在僅僅考慮鄰域的情況下也有26個，要收斂到最優(yōu)解會耗費大量的時間和內(nèi)存資源，且隨規(guī)劃空間增大呈指數(shù)級增長。因此本發(fā)明提出如圖1所示的2.5維網(wǎng)格模型，每個網(wǎng)格點包含經(jīng)度、緯度、高程信息。此時每個節(jié)點的鄰域僅僅存在8個可擴(kuò)展方向，算法計算效率要遠(yuǎn)大于3維網(wǎng)格劃分方式。
[0012]2基于A*算法的初始航線確定
[0013]2.1代價函數(shù)改進(jìn)
[0014]對于以上劃分的目標(biāo)網(wǎng)絡(luò)空間，需要定義A*算法的代價函數(shù)對可拓展節(jié)點進(jìn)行評估，從而挑選出最優(yōu)路徑中的節(jié)點-邊列表。A*代價函數(shù)一般公式如下:
[0015]f (n) = g (n) +h (η)(I)
[0016]其中η是待擴(kuò)展節(jié)點，g(n)是狀態(tài)空間中從初始節(jié)點到節(jié)點η的實際代價，h(n)是從節(jié)點η到目標(biāo)節(jié)點的估計代價。A*算法本身的性質(zhì)決定了代價函數(shù)的表達(dá)式是影響搜索性能的主要因素。對于無人機(jī)低空航線規(guī)劃問題，Asseo S.J給出了對代價函數(shù)的參考公式，如下所示:

【權(quán)利要求】
1.一種無人機(jī)航線規(guī)劃算法，其特征在于:包括以下步驟:首先基于2.5維網(wǎng)格劃分三維空間；然后在雷達(dá)、災(zāi)害天氣、禁飛區(qū)等約束條件下，綜合考慮航線高度、被探測概率、航線長度等影響因子改進(jìn)A*代價函數(shù)，基于算法搜索流程，確定初始航線；最后在最小步長、轉(zhuǎn)彎半徑、爬升率、安全高度約束下，進(jìn)行一系列處理得到最終的可飛行航線；該算法穩(wěn)定、收斂性好、效率高。
2.根據(jù)權(quán)利要求1所述一種無人機(jī)航線規(guī)劃算法，其特征在于:所述2.5維網(wǎng)格為2.5維網(wǎng)格模型，每個網(wǎng)格點包含經(jīng)度、緯度、高程信息，其每個網(wǎng)格點的鄰域存在8個可擴(kuò)展方向。
3.根據(jù)權(quán)利要求1所述一種無人機(jī)航線規(guī)劃算法，其特征在于:基于2.5維網(wǎng)格劃分三維空間，其每個網(wǎng)格點的鄰域存在8個可擴(kuò)展方向遠(yuǎn)小于規(guī)則三維網(wǎng)格的空間劃分中每個網(wǎng)格點的鄰域存在26個可擴(kuò)展方向。
4.根據(jù)權(quán)利要求1所述一種無人機(jī)航線規(guī)劃算法，其特征在于:A*代價函數(shù)中g(shù)(H)首先改進(jìn)為
，使代價函數(shù)的航線高度、被探測概率、航線長度三項指標(biāo)是同方向的作用關(guān)系。
5.根據(jù)權(quán)利要求1所述一種無人機(jī)航線規(guī)劃算法，其特征在于:A*代價函數(shù)中(進(jìn)行歸一化處理，進(jìn)一步改進(jìn)為
6.根據(jù)權(quán)利要求 1 所述一種無人機(jī)航線規(guī)劃算法，其特征在于:A*代價函數(shù)中
7.根據(jù)權(quán)利要求1所述一種無人機(jī)航線規(guī)劃算法，其特征在于:算法搜索基于2.5維空間劃分和改進(jìn)Α*代價函數(shù)。
8.根據(jù)權(quán)利要求1所述一種無人機(jī)航線規(guī)劃算法，其特征在于:在最小步長、轉(zhuǎn)彎半徑約束下采用FFP算法對航線數(shù)據(jù)進(jìn)行數(shù)據(jù)壓縮，使無人機(jī)能夠找出盡可能最長的直線趨勢，從而避免頻繁的轉(zhuǎn)彎。
9.根據(jù)權(quán)利要求1所述一種無人機(jī)航線規(guī)劃算法，其特征在于:在爬升率、安全高度約束下，建立航線保護(hù)區(qū)模型，計算得到優(yōu)化后的轉(zhuǎn)折點，構(gòu)成航線。
10.根據(jù)權(quán)利要求1所述一種無人機(jī)航線規(guī)劃算法，其特征在于:該算法穩(wěn)定、收斂性好為算法在不同距離、不同網(wǎng)格大小的情況下均可以并且快速的計算出一條最優(yōu)航線。
【文檔編號】G01C21/20GK104075717SQ201410025640
【公開日】2014年10月1日 申請日期:2014年1月21日 優(yōu)先權(quán)日:2014年1月21日
【發(fā)明者】王偉, 江華, 王鵬, 占偉偉 申請人:武漢吉嘉偉業(yè)科技發(fā)展有限公司