[發明專利]基于改進雙向快速擴展隨機樹算法的無人機路徑優化方法

有效

• 申請號: 201810399683.0
• 申請日: 2018-04-28
• 公開（公告）號: CN108681787B
• 公開（公告）日: 2021-11-16
• 發明（設計）人: 沈志遠;趙帥;盧朝陽
• 申請（專利權）人: 南京航空航天大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N20/00;G01C21/20
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 姜慧勤

本發明公開了基于改進雙向快速擴展隨機樹算法的無人機路徑優化方法，該方法包括以下幾個步驟：一、建立無人機運動學約束模型和確定二維空間內起始點和目標點；二、基于后向扇形區域采樣方法擴展雙向隨機樹的節點；三、基于動態自適應步長方法解決在障礙物附近生長局限性的問題；四、通過連接雙向搜索樹的節點，形成一條完整的飛行路徑。本發明在經典B?RRT*算法的基礎上，基于后向扇形區域采樣方法，當節點擴展時把隨機樹采樣點限制在后向扇形區域，同時基于動態自適應步長方法解決了在障礙物附近生長局限性的問題，最后連接各節點，生成一條符合無人機真實可飛的飛行路徑，為低空下無人機自主導航飛行提供了可行的方法。

技術領域

本發明涉及基于改進雙向快速擴展隨機樹算法的無人機路徑優化方法，屬于低空下無人機自主導航飛行及運行安全保障技術領域。

背景技術

隨著電子信息技術的進步和科技的發展，無人機UAV(Unmanned Aerial Vehicle)憑借體積小、成本低、效率較高、無人員傷亡、生存能力強、機動性能好、使用方便等優點，越來越受到各國的青睞。并且無人機的用途從一開始僅限于軍用領域擴展到了民用領域。隨著軍民用無人機市場的迅猛發展，考慮到無人機的種類繁多，執行任務也各不相同，對每一架無人機進行路徑規劃是很有必要的。隨著未來低空空域逐步放開，無人機數量持續增加，如何保證在低空空域下多無人機執行不同任務的安全飛行就成為研究的一個重點。因此對無人機進行路徑規劃，實現自主導航是很有必要的。

無人機路徑規劃算法很多，最常見的有以下幾種：傳統的路徑規劃算法如遺傳算法、蟻群算法、粒子群算法等，這些算法在處理簡單的路徑規劃問題時具有一定的優越性，但是在復雜環境下和高維空間中時，這些算法的復雜性會急劇增加，導致收斂時間長、求解困難。另外，基于啟發式函數和人工勢場的算法，如A*、D*和人工勢場法，在處理規劃問題時雖然能滿足最優性和實時性等要求，但是因并未考慮到無人機自身性能約束和運動學限制，使得規劃的路徑不一定能被無人機所執行。基于采樣的航跡規劃算法已被證明可以高效地解決航跡規劃問題，概率路線圖算法(Probability Roadmap Method，PRM)和快速擴展隨機樹算法(Rapidly-exploring Random-Tree，RRT)是目前兩種主要的采樣方法。RRT算法收斂速度快，效率高，且樹的航跡搜索比圖的航跡搜索更容易實現。

RRT算法是隨機在空間生成采樣點，利用樹結構進行節點擴展，最后通過對節點連接，形成完整路徑的一種算法。但是RRT算法在算法復雜度和收斂速度上都存在局限，針對此，近些年也相繼出現了很多基于RRT算法的改進型算法。如RRT*算法，有效改進了由基本RRT算法產生的并非概率最優解的問題；利用一個輕微變異的貪心RRT-connect作為啟發函數來連接兩顆隨機樹的B-RRT*算法，提升了算法的趨向性和智能性；還有基于三角幾何選擇節點提出的TG-RRT*算法，解決了得到最優解所需要的迭代次數，從而加速算法快速收斂；基于雙向快速擴展隨機樹算法，通過智能樣本插入的啟發函數使得B-RRT*算法快速收斂到最優路徑，但是該算法并未考慮到無人機自身性能約束和運動學約束模型的限制。

發明內容

本發明所要解決的技術問題是：提供基于改進雙向快速擴展隨機樹算法的無人機路徑優化方法，解決了現有技術中B-RRT*算法不能直接用于無人機路徑規劃和效率不佳的問題。

本發明為解決上述技術問題采用以下技術方案：

基于改進雙向快速擴展隨機樹算法的無人機路徑優化方法，包括以下步驟：

步驟1，考慮無人機自身的飛行性能約束，建立無人機動力學約束模型，同時確定無人機在二維空間內的起始點和目標點；