[發(fā)明專利]一種動態(tài)環(huán)境下的自動導引運輸車路徑規(guī)劃方法

有效

• 申請?zhí)枺?/td>: 202010740840.7
• 申請日: 2020-07-29
• 公開（公告）號: CN111735470B
• 公開（公告）日: 2021-03-02
• 發(fā)明（設計）人: 方懷瑾;黃秀松;呂長虹;朱玥煒
• 申請（專利權）人: 上海國際港務（集團）股份有限公司;華東師范大學
• 主分類號: G01C21/34
• 分類號: G01C21/34;G01C21/20
• 代理公司: 上海愉騰專利代理事務所(普通合伙) 31306
• 代理人: 唐海波

本發(fā)明公開了一種動態(tài)環(huán)境下的自動導引運輸車路徑規(guī)劃方法，包括以下步驟：獲取起點和終點信息以及動態(tài)環(huán)境信息；利用所述動態(tài)環(huán)境信息、起點和終點信息，通過柵格法進行動態(tài)環(huán)境建模，構建柵格環(huán)境地圖，并引入時間參數(shù)對柵格環(huán)境地圖進行描述；基于時間參數(shù)構建A*算法；根據(jù)基于時間參數(shù)的A*算法得到路徑作為規(guī)劃路徑輸出給自動導引運輸車；基于時間參數(shù)構建的A*算法在速度上非常快，其歸因于該算法搜索的是二維柵格圖，雖然其中包含著時間維度，但其搜索的柵格數(shù)與靜態(tài)的相同。在效果方面，當環(huán)境處于非擁擠狀態(tài)時，該算法不會產生碰撞，且在遇到障礙時更傾向于繞路行駛，對于碼頭貨物運輸場景非常合適，且安全。

技術領域

本發(fā)明涉及路徑規(guī)劃技術領域，尤其涉及一種動態(tài)環(huán)境下的自動導引運輸車路徑規(guī)劃方法。

背景技術

自動導引路徑規(guī)劃問題一般處理已知環(huán)境情況和未知環(huán)境情況。現(xiàn)有許多算法可以解決其路徑規(guī)劃問題，但對于動態(tài)環(huán)境下的（移動障礙物）路徑規(guī)劃問題，算法無法快速地解決該場景下的問題，且給出的規(guī)劃路線會有碰撞的可能。

如一般的A*算法結合了深度搜索和廣度搜索的優(yōu)點，使得尋路算法可以在保證速度的情況下大概率地找到解。但A*算法無法處理動態(tài)環(huán)境的問題。并且在復雜的環(huán)境下，A*算法的搜索效率會變低。

發(fā)明內容

鑒于目前存在的上述不足，本發(fā)明提供一種動態(tài)環(huán)境下的自動導引運輸車路徑規(guī)劃方法，基于時間維度構建的A*算法進行路徑規(guī)劃，其搜索的柵格數(shù)與靜態(tài)的相同，在速度上非常快，規(guī)避動態(tài)障礙物，適用多種運輸車的場景，安全性高。

為達到上述目的，本發(fā)明的實施例采用如下技術方案：

一種動態(tài)環(huán)境下的自動導引運輸車路徑規(guī)劃方法，所述動態(tài)環(huán)境下的自動導引運輸車路徑規(guī)劃方法包括以下步驟：

獲取起點和終點信息以及動態(tài)環(huán)境信息；

利用所述動態(tài)環(huán)境信息、起點和終點信息，通過柵格法進行動態(tài)環(huán)境建模，構建柵格環(huán)境地圖，并引入時間參數(shù)對柵格環(huán)境地圖進行描述；

基于時間參數(shù)構建A*算法；

根據(jù)基于時間參數(shù)的A*算法得到路徑作為規(guī)劃路徑輸出給自動導引運輸車。

依照本發(fā)明的一個方面，所述通過柵格法進行動態(tài)環(huán)境建模，構建柵格環(huán)境地圖，并引入時間參數(shù)對柵格環(huán)境地圖進行描述具體為：

記環(huán)境地圖E為一矩形，其左下角為坐標原點，X軸正方向向右，Y軸正方向向上，為E的長，為E的寬；以w為步長將E切割成柵格，每一行柵格數(shù)為，每一列柵格數(shù)為；設任意柵格為，為所在的行列表示，其中，，柵格劃分為自由柵格集M與障礙柵格集Q，M集可以被規(guī)劃，Q集不允許被通過；

設起始柵格為，目標柵格為，路徑集為P，引入時間參數(shù)后得：

起始柵格描述為，為規(guī)劃起始時間；

障礙柵格集Q中的每個元素描述為，其中為障礙物位于的時刻；

路徑集P中的每個元素描述為，其中為規(guī)劃至的時刻。

依照本發(fā)明的一個方面，所述路徑集P中的時間t是由規(guī)劃物移動速度v以及移動距離s計算得出。

依照本發(fā)明的一個方面，所述基于時間參數(shù)構建A*算法具體為：

構建由起始柵格經號柵格到達目標柵格的代價函數(shù)值，公式如下：

是坐標的當前柵格，到達時間為t，是由起始柵格到號柵格的實際代價值，是由號柵格到目標柵格的估計代價值；值為權重系數(shù)，用來控制與的占比；表示從當前柵格到目標柵格的方向的小范圍路段的繁忙程度函數(shù)，用該路段在未來個單位時間內通過距離范圍的障礙物數(shù)來刻畫，。