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

在審

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

1.一種基于改進A-star算法的無人機路徑規劃方法，其特征在于，包括以下步驟：

步驟一：獲取無人機飛行區域的衛星地圖；

步驟二：將無人機飛行的衛星地圖轉化為柵格地圖,障礙物區域用黑色柵格表示、可通行區域用白色柵格表示；

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

步驟四：獲取初始信息，包括無人機在路徑規劃中設定的起始點S和目標點G的坐標，障礙物區域的大小和位置信息，連接起始點S和目標點G，構造基準線；

步驟五：從起始點S開始，將當前節點放入close列表，與當前節點相鄰的8個節點放入open列表；

步驟六：采用改進的A-star算法從open列表中選擇F(i)值最小的節點作為下一路徑節點，并放入close列表；

步驟七：判斷close列表中的節點個數是否大于或等于3；

步驟八：若close列表中的節點個數大于或者等于3，則通過篩選函數P(x,y)對close列表末尾三個連續節點中相鄰兩節點之間的坐標關系以及是否存在障礙物進行判斷，對其中不滿足篩選函數P(x,y)的節點進行刪除；

步驟九：若close列表中的節點個數小于3或滿足篩選函數P(x,y)，則利用改進A-star算法繼續搜索新的節點；

步驟十：當搜索到目標節點G時，將目標節點放入close列表，同時結束搜索。

2.根據權利要求1所述的基于改進A-star算法的無人機路徑規劃方法，其特征在于，步驟二中，對無人機的飛行環境進行柵格化，柵格的邊長d由無人機的最大外形尺寸l來確定；同時為了避免了無人機在等高飛行過程中與障礙物發生碰撞，按照一定的比例對障礙物進行膨脹，保證了無人機在飛行過程中的安全。

3.根據權利要求1所述的基于改進A-star算法的無人機路徑規劃方法，其特征在于，步驟三中，為了便于對路徑進行描述和計算路徑參數，利用坐標法和序號法對柵格地圖中的柵格進行標記，并給出了兩種標記方式的轉換公式：

式中：m、n分別表示柵格地圖的行數和列數；mod函數表示兩數相除后取余運算；ceil函數表示向上取整運算；柵格坐標由柵格中心點的坐標值(x,y)來表示；柵格序號用g來表示。

4.根據權利要求1所述的基于改進A-star算法的無人機路徑規劃方法，其特征在于，步驟六中，針對節點搜索的代價函數為F(i)＝G(i)+H(i)+sinθ_i，其中，F(i)為節點i的代價函數；G(i)為起始點S到預定生成的第二步航點i的距離代價；H(i)為預定生成的第二步航點i到目標點距離G的代價；θ為預定生成的第二步航點i到目標點距離G連線與基準線之間的夾角，稱為方位角。

5.根據權利要求1所述的基于改進A-star算法的無人機路徑規劃方法，其特征在于，步驟七中，通過判斷close列表中的節點個數是否大于等于3，來決定是否通過篩選函數P(x,y)對列表末尾的三個節點進行判斷。

6.根據權利要求1所述的基于改進A-star算法的無人機路徑規劃方法，其特征在于，步驟八中，當close列表中的節點個數大于或等于3時，通過篩選函數P(x,y)判斷列表末尾三個節點中兩兩相鄰的節點之間的坐標是否滿足對應關系，來決定是否對節點進行刪除，從而避免了傳統A-star算法因為逃離局部而導致路徑長度變長。

7.根據權利要求1所述的基于改進A-star算法的無人機路徑規劃方法，其特征在于，步驟九中，當close列表中的節點個數小于3或滿足篩選函數P(x,y)時，則只需要通過改進A-star算法繼續搜索新的路徑節點。