[發明專利]動態障礙物下的無人巡航船多目標路徑規劃方法

有效

• 申請號: 202010340555.6
• 申請日: 2020-04-26
• 公開（公告）號: CN111457927B
• 公開（公告）日: 2021-03-05
• 發明（設計）人: 于家斌;劉冠東;王小藝;許繼平;趙峙堯;王立;白玉廷;孫茜;張慧妍
• 申請（專利權）人: 北京工商大學
• 主分類號: G01C21/20
• 分類號: G01C21/20
• 代理公司: 北京永創新實專利事務所 11121
• 代理人: 冀學軍

本發明公開了一種動態障礙物下的無人巡航船多目標路徑規劃方法，涉及水質采樣和路徑規劃技術領域。首先，無人機對湖面環境采集圖像，進行柵格分割，在柵格地圖設置起始點和若干采樣點；采用改進的灰狼優化算法對若干采樣點進行順序優化，并將最優順序的各采樣點一一標記到地圖上；利用D*Lite算法計算柵格地圖中標記的每兩個采樣點之間的最優柵格路徑，得到一條從起始點到最終采樣點之間的最優路徑；最后，自主巡航船沿最優路徑完成巡航。本發明對灰狼優化算法中的收斂因子進行改進，平衡了灰狼優化算法的全局搜索和局部搜索能力，提高了灰狼優化算法的收斂速度和穩定性，可以實現在動態未知環境情況下多個目標點的路徑規劃。

技術領域

本發明屬于湖泊流域水質采樣和路徑規劃技術領域，具體是一種動態障礙物下的無人巡航船多目標路徑規劃方法。

背景技術

如今，水環境保護問題越來越受到國家的重視。隨著科技的發展，在水質采樣領域，智能水質采樣巡航船逐漸替代人工采集，應用越來越廣泛。

但是，智能水質采樣巡航船的路徑規劃問題一直以來都是國內外學者所關注的重點以及難點，其路徑的選擇是否合理直接影響著巡航船的運行效率。一種適合當前環境、能快速規劃出采樣最優路徑的方法能顯著地提高采樣效率同時降低采樣成本。

當前已有很多傳統方法和智能方法被用來解決巡航船的多目標點路徑規劃問題，如：遺傳算法和蟻群算法等。

灰狼優化算法是2014年提出的一種群體智能優化算法，可以實現對多個目標點的順序優化。但是，該算法無法解決動態未知環境的路徑規劃問題，并且該算法的收斂性較緩慢。

D*Lite算法是一種能夠解決動態未知環境的路徑規劃問題的算法，它采用的是反向搜索方式。但是，該算法只能夠解決單目標點的問題，不能夠僅用該算法去遍歷多個目標點。

發明內容

本發明針對自主巡航船在動態環境中采集多個點的需求問題，提出了一種動態障礙物下的無人巡航船多目標路徑規劃方法，利用D*Lite算法結合改進后的灰狼優化算法，充分利用兩種算法的優勢，縮短了搜索路徑所消耗的時間，減少了設備成本，并有效解決了動態環境下多個目標點的路徑規劃問題。

所述的動態障礙物下的無人巡航船多目標路徑規劃方法，具體步驟如下：

步驟一：無人機對湖面的環境采集圖像，采用柵格法進行分割，得到柵格地圖并設置起始點和d個采樣點；

具體為：首先，將湖面圖像分割成大小相等的柵格，組成一個柵格地圖；并將環境中的障礙物設置為黑色柵格，將不規則障礙物進行填充處理，將可行區域設置為白色柵格，在柵格地圖中運用二維坐標設置一個起始點和d個采樣點。

d為正整數。

步驟二：采用改進的灰狼優化算法對d個采樣點進行順序優化，得到最優順序并保存。

所述采用改進的灰狼優化算法得到最優順序的步驟如下：

步驟201：初始化灰狼優化算法的參數。

參數包括：灰狼種群數量n，最大迭代次數t，將采樣點個數定義為搜索空間的維數d，灰狼種群的初始位置，以及每只灰狼各自一條隨機路徑等；

步驟202：每只灰狼在d個采樣點的空間中搜索獵物，構建搜索空間與灰狼位置關系的空間域矩陣P；

首先，定義第i只灰狼的位置X_i為一組互不相同的正整數序列，公式如下：

則代表灰狼種群中的第i只灰狼在第d個采樣點上的值；

然后，n只灰狼的位置組成空間域矩陣P，公式如下：