[發明專利]一種基于懲罰權重的路徑規劃方法、導航格以及柵格地圖

有效

• 申請號: 201911265365.6
• 申請日: 2019-12-11
• 公開（公告）號: CN110986951B
• 公開（公告）日: 2023-03-24
• 發明（設計）人: 鄧軍
• 申請（專利權）人: 廣州市技田信息技術有限公司
• 主分類號: G01C21/20
• 分類號: G01C21/20
• 代理公司: 廣州新諾專利商標事務所有限公司 44100
• 代理人: 劉杉

本發明提供了一種基于懲罰權重的路徑規劃方法、導航格以及柵格地圖，通過設置導航格的權重信息和主方向信息以對柵格地圖的局限條件進行設定，并在設定好的局限條件下進行有效的搜索算法以尋找最優路徑，可以大大提高路徑規劃的效率和準確度，并有效減小路徑規劃的計算量。

技術領域

本發明屬于路徑規劃技術領域，具體涉及一種基于懲罰權重的路徑規劃方法、導航格以及柵格地圖。

背景技術

路徑規劃是運動規劃技術領域的重點研究對象之一，連接起點位置和終點位置的序列點或曲線被稱為路徑，為得到這一路徑所采用的策略就是路徑規劃。

路徑規劃在很多領域都具有廣泛的應用。在高新科技領域的應用有：機器人的自主無碰行動；無人機的避障突防飛行；巡航導彈躲避雷達搜索、防反彈襲擊、完成突防爆破任務等。在日常生活領域的應用有：GPS導航；基于GIS 系統的道路規劃；城市道路網規劃導航等。在決策管理領域的應用有：物流管理中的車輛問題(VRP)及類似的資源管理資源配置問題。通信技術領域的路由問題等。凡是可拓撲為點線網絡的規劃問題基本上都可以采用路徑規劃的方法解決。

目前，在解決如AGV小車等行駛器具的路徑規劃問題時，大多采用較為復雜的全局搜索算法，沒有考慮到AGV小車的行駛的特點和倉庫的擺放特點，具有算法復雜、計算量大、計算效率低的問題。

發明內容

本發明的目的在于針對現有技術的缺陷，提供一種基于懲罰權重的路徑規劃方法、導航格以及柵格地圖，在設定好的局限條件下進行有效的搜索算法以尋找最優路徑，可以大大提高路徑規劃的效率和準確度，并有效減小路徑規劃的計算量。

本發明的技術方案如下：

一種基于懲罰權重的路徑規劃方法，包括以下步驟:

S1、在鋪設有多個導航格的柵格地圖上選取起始格和終點格，并將所述起始格放入計算集中；每一所述導航格內設置有坐標信息、主方向信息和權重信息；

S2、在所述計算集不為空時，選取所述計算集中的一個導航格作為起始計算格，根據所述起始計算格的主方向信息對應的可行方向，獲得所述起始計算格的可通行鄰近格集；所述可通行鄰近格集包括所述起始計算格在所述可行方向上的相鄰的導航格；

S3、在所述可通行鄰近格集中選取一個導航格作為進階計算格，將所述起始計算格移出所述計算集；并獲取所述進階計算格的路徑代價，并判斷：

S31、當所述進階計算格的路徑代價為零時，保存所述進階計算格的路徑代價等于當前代價，保存所述進階計算格的前一連接格為所述起始計算格，若所述進階計算格不在所述計算集中將所述進階計算格放入所述計算集；所述當前代價為所述起始計算格的路徑代價+所述進階計算格的權重信息；當所述起始計算格為所述起始格時，所述起始計算格的路徑代價等于所述起始計算格的權重信息；

S32、當所述進階計算格的路徑代價大于零且大于所述當前代價時，保存所述進階計算格的路徑代價等于所述當前代價，保存所述進階計算格的前一連接格為所述起始計算格；

S33、當所述進階計算格的路徑代價大于零且小于所述當前代價時，所述進階計算格的路徑代價和前一連接格均保持不變；

S4、重復所述步驟S2-S33，直到所述計算集為空；

S5、從所述柵格地圖上的所述終點格開始，依次獲取當前格的所述前一連接格，直到得到整條規劃路徑。

進一步的，所述主方向信息可以為多個方向中的一個方向；所述主方向信息對應的可行方向為所述多個方向中除了與所述主方向信息相反的方向以外的其他所有方向。

進一步的，所述多個方向為上、下、左、右四個方向。

進一步的，所述步驟S31的所述當前代價為所述起始計算格的路徑代價+所述進階計算格的權重信息+行駛權重；