某車間智能引導小車路徑規劃設計

曾慶 潘啟宏

摘? 要：本文通過對AGV路徑規劃現狀和路徑規劃算法的學習研究，在對AGV工作環境建模的基礎上，采用Dijkstra算法對多AGV的路徑進行規劃并結合實際情況提出優化方法，把Dijkstra算法和時間窗方法相結合以解決多AGV避撞問題，從而實現多AGV路徑規劃，并提出路徑優化策略。

關鍵詞：智能引導小車;AGV;路徑規劃;算法設計

1? 車間簡介

HD公司現為一家從事煤炭行業專業機械設備生產和維修的的公司，公司建有機械零部件加工、鋼鐵鑄造、機電設備制造、產品儲存車間等生產車間，公司主要營業范圍是機械、電器設備及配件的設計、制造、維修和銷售。本文選擇某產品儲存車間為研究對象，綜合利用Dijkstra算法和時間窗方法研究多AGV（智能引導小車）路徑實現的問題，為了計算方便，省去了倉庫無關部分，如圖1為倉庫平面示意圖，倉庫有12個貨架。

2? 多AGV路徑模型設定

現假設該倉庫加入多臺AGV小車以實現自動化物流運輸，在地圖模型中加入AGV停車區域和鋪設好的小車工作路徑，用綠色陰影部分代表小車的停車區域，藍色線段代表鋪設的小車作業路徑。根據所建立的路徑信息，為計算方便，現在人為加入節點信息并為每一段路徑入權值（權值大小依據長度值，橫向相鄰兩節點權值為2，縱向相鄰兩節點權值為3）如圖2所示。

3? 時間窗方法

在利用時間窗方法解決多AGV路徑規劃問題前，首先做出如下假設：

（1）在實際作業中忽略了AGV在轉彎速度變化，所有AGV運行的速度為固定值。

（2）圖中路徑任意兩相鄰節點可相互到達。

（3）AGV在裝卸貨物操作的時間為固定值。

（4）當發生沖突時，保證優先級Pi高的AGV小車任務的執行，調整優先級低的AGV小車任務。針對優先級高低的界定，本論文依據AGV小車接受任務的時間先后順序劃分任務優先級。

基于以上假設，因為AGV速度和裝卸時間為固定值，因此AGV之間不存在趕超沖突。現在假設所有AGV均空閑并下達任務，任務1：AGV1去貨架4-3執行卸貨任務;任務2：AGV2去貨架2-1執行卸貨任務，現在利用基于Dijkstra算法和時間窗方法計算多AGV路徑，算法步驟：

（1）按照發布的m（這里m=2）個任務的時間先后對任務進行優先級排序。根據任務接受時間先后，任務1優先級高于任務2。

（2）選擇最高優先級的任務（任務1），并使用Dijkstra算法規劃出最短路徑，安排AGV1去完成任務并計算出該任務中小車占用的所有路徑的進入時間tin 和駛出時間tout，初始化各個路段的時間窗。

（3）選擇次優任務（任務2），再次使用Dijkstra算法進行路徑規劃并安排AGV2區完成任務并計算出該AGV小車所有占用的所有路徑的進入時間tin和駛出時間tout，更新各個路段的時間窗表。

（4）按照更新后獲得的時間窗表，檢驗是不是存在碰撞。若不存在碰撞，小車工作路徑規劃成功;若存在碰撞情況，則該碰撞發生的路段不可用，并根據優先級再次運用Dijkstra算法規劃優先級低的任務路徑，直到問題得到解決。若路徑規劃失敗，找不到完成任務的路徑，則停止對該任務的規劃，等待新的任務命令和新的優先級后再執行。

綜上即可完成多AGV路徑規劃，對于任務數量較多情況的算法只需重復上述步驟，但是所得到的時間窗更復雜，可能需要多次使用Dijkstra算法。根據Dijkstra算法得到任務1最短路徑為3→7→6→12→18→19，如圖4-4紅色線段所示，任務2的最短路徑為2→6→7→8→9如圖3黃色線段所示。

根據圖3可知，使用Dijkstra算法對兩小車工作路徑規劃后在路段為6-7出現了兩AGV共同占用的現象，該路段可能導致兩AGV發生碰撞，畫出兩條路徑的時間窗，其中黃色部分表示任務2時間窗，紅色部分表示任務1時間窗，如圖4所示。圖4中，路段6-7之間兩任務時間窗出現了重疊，根據任務1的優先級，調整任務2的路徑，根據Dijkstra算法搜索無碰撞次優路徑可得任務2路徑為2→3→7→8→9，如圖5所示。

畫出兩條路徑的時間窗，如圖6，可以看到更新后的時間窗不存在堆疊情況，路徑優化后得到了無碰撞的路徑，路徑規劃成功。

4? 總結

本文運用Dijkstra算法和時間窗方法相結合實現了對多AGV路徑的規劃，通國對路徑規劃算法的學習和研究，并結合公司車間的實際情況，運用Dijkstra算法完成了多AGV路徑的規劃，并提出路徑優化策略。

參考文獻

[1]? 金亞萍.自動導引車關鍵技術現狀及發展趨勢[J]. 物流技術與應用，2015，20（11）：96-98.

[2]? 石朝俠，洪炳镕，周彤，等.大規模環境下的拓撲地圖創建與導航[J].機器人，2007，29（5）：433-438.

[3]? 樊征，曹其新，楊揚，等.面向移動機器人的拓撲地圖自動生成[J]. 華中科技大學學報：自然科學版，2008（S1）：172-175.

作者簡介：曾慶，男（1972.1—），漢族，四川攀枝花人，碩士，講師，研究方向：智能制造。

潘啟宏，男（1995.5—），漢族，四川攀枝花人，本科在讀，研究方向：智能制造。