[發明專利]一種基于改進A-star算法的無人機路徑規劃方法

在審

• 申請號: 202010769976.0
• 申請日: 2020-08-04
• 公開（公告）號: CN111679692A
• 公開（公告）日: 2020-09-18
• 發明（設計）人: 唐剛;唐從強;邵長專;胡雄
• 申請（專利權）人: 上海海事大學
• 主分類號: G05D1/10
• 分類號: G05D1/10
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明提出了一種基于改進A?star算法的無人機路徑規劃方法。包括以下步驟：(1)采集無人機飛行區域的衛星地圖，使用柵格法將無人機的飛行環境地圖轉化為柵格地圖，柵格大小根據無人機最大幾何尺寸來確定；(2)根據柵格在環境中位置的不同，將柵格分為兩大類:障礙柵格、自由柵格；(3)在自由柵格中選取合適的柵格作為無人機飛行的起始點和目標點；(4)在規劃路徑時通過篩選函數P(x,y)對close列表末尾三個連續節點中相鄰兩節點之間的坐標關系以及是否存在障礙物進行判斷，刪除其中不必要的節點，從而達到縮短路徑長度的目的。

技術領域

本發明屬于無人機路徑規劃技術領域，尤其是涉及一種無人機避障飛行路徑的規劃方法。

背景技術

無人機路徑規劃是在給定的規劃區域內，以及特定的約束條件下，在初始位置和目標位置之間尋找一條最優或者接近最優的飛行路徑。根據無人機對環境信息掌握的程度不同，路徑規劃可以分為基于先驗完全信息的全局路徑規劃和基于傳感器信息的局部路徑規劃，其中，全局規劃方法主要包括可視圖法、柵格法、自由空間法、神經網絡法等。其中，柵格法一般作為路徑規劃的環境建模技術來使用，作為路徑規劃的方法它很難解決復雜環境信息的問題，一般需要和其他智能算法結合。

文獻“基于柵格法的機器人快速路徑規劃，微電子學與計算機，2015Vol.22(6),p98-100”采用柵格法對機器人活動場地進行柵格劃分，并用序號對柵格劃分好的場地進行編號，降低了環境建模的難度，便于節點篩選，但是文中并未涉及到對復雜多邊形如何進行柵格化處理。專利文獻CN 104808688A公開了一種基于A-star搜索的無人機路徑動態規劃方法，判斷起始點和目標點構成線段與危險區域多邊形的外包圓是否相交，如果有交點則基于A-star搜索算法規劃生成規避多邊形威脅區域的路徑,但是采用外包圓的方式對障礙物多邊形進行處理，容易將最優路徑囊括到障礙物區域內。

傳統的A-star算法是建立在模擬柵格地圖的基礎上，基于啟發式的算法。能夠利用選擇的啟發式函數評估、選擇出優勢節點，在很大程度上提升了搜索效率；但是傳統A-star算法中的啟發函數未考慮了方位對于搜索節點的影響，導致節點搜索具有盲目性。另外，算法在陷入局部最優后，在搜索節點脫離局部最優點的過程中，會產生多余節點，導致搜索路徑的整體變長。

發明內容

為了克服現有方法對復雜環境中存在的多邊形障礙物建模適應性差以及傳統A-star算法陷入局部最優后導致路徑長度變長的缺點，本發明提供了一種基于改進A-star算法的無人機路徑規劃方法。

本發明能夠適應于存在復雜的多邊形障礙物的環境，規劃出一條最短的路徑。本發明解決其技術問題所采用的技術方案：一種基于改進A-star算法的無人機路徑規劃方法，其特點是包括以下步驟：

步驟一：將無人機路徑規劃的環境地圖轉化為柵格地圖；

利用采集到的衛星地圖，識別其中的障礙區域，根據無人機的大小確定柵格大小；使用柵格法對無人機的飛行環境進行建模，將連續的空間離散化，得到無人機的飛行區域的柵格狀地圖。

步驟二：采用坐標法和序號法對柵格進行編號；

為了便于對環境模型進行描述，同時采用坐標法和序號法對規格為m×n的柵格地圖中的柵格進行編號，兩種方法可以依據一定的比例相互換算得到。

步驟三：對柵格進行分類；

針對柵格在實際環境中位置的不同，將柵格分為兩大類:黑色的障礙柵格、白色的自由柵格。

步驟四：獲取初始數據；

包括無人機在路徑規劃當中的起始點S和目標點G的坐標以及障礙物區域的參數數據，連接起始點S和目標點G構造基準線。

步驟五：從起始點開始，采用改進的啟發函數F(i)搜索路徑節點；