淺談AGV的路徑規劃

李景，程瑞嘉，張文忠

（安徽工業大學電氣與信息工程學院，安徽 馬鞍山 243032）

隨著電子商務、快遞、互聯網以及新能源技術的日新月異，人們對物質生活的需求也會越來越高，電商行業的訂單邁向多種類，小層次，高頻次的步伐。這種消費模式給傳統“人到貨”的揀選方式帶來巨大挑戰，為了應對這種問題，現代的智能倉儲系統提出了“貨到人”的揀選理念。

在這種智能倉庫中，大多采用定制的倉庫機器人（AGV）代替人工來實現貨物的揀貨、分揀、搬用到派送等一些操作。根據倉庫訂單，利用中央處理單元對倉庫機器人進行分配任務，其次對整個倉庫研究分析，建立基礎地圖模型,分配好機器人任務，建立好地圖模型并對AGV進行路徑規劃，主要有總體路徑規劃［1］以及局部的路徑規劃［2］，本文針對整體流程做出簡介。

1 AGV地圖模型的構建

構建倉庫地圖模型是相當重要的，也是之后對其調度路徑規劃的基礎。在研究眾多文獻后，大致可以得出以下幾種方法：

（1）簡易模型柵格化。（2）有向圖的模型地圖。（3）時空地圖模型。

1.1 簡易模型柵格化

將整個倉庫假定為區域a，以最左下角為坐標原點，橫軸為X軸，縱軸為Y軸，建立XOY狄克爾坐標系，機器人為一小格，等同于一像素點。而貨架等同于幾個像素點不可通過，設機器人步長為u，倉庫最大面積等于Xmax*Ymax，所以可得柵格數則為N C=Xmax/u,Nl=Ymax/u。故機器人的運動可以看成點在坐標系的運動模型。即如圖1所示。

圖1 簡易柵格圖

1.2 有向圖的模型地圖

機器人運行空間由不同類型且相同尺寸的單位塊組成，這些單位塊用來表示站點中的出發點、分揀格口、緩沖區、路徑等。我們用端點來表示所有的單位塊，并且用有向邊來相互連接。注意同一時間內一個單位塊只能通過一輛AGV。

首先，多輛AGV機器人可以在出貨口同時裝撿快件或暫時停靠。叉號標示的單位塊表示分揀格口，由單行單方向的所有的路徑塊都被賦予了通行方向，并且AGV機器人在每個時間插槽內只能夠停靠一輛。其次字母B單位塊表示緩沖區塊，AGV機器人在這里可以暫時停靠，避免與其他工作機器人發生沖突。

1.3 時空地圖模型

利用二維元胞數組記錄各節點占用時間段集合，其中節點（x,y）的占用時間段集合表示為：

式中tin、tout分別為AGV進入、離開節點（x,y）的時刻，i表示占用節點的AGV編號。其時空地圖模型如下圖2所示：

圖2 時空地圖

2 AGV調度的路徑規劃

在為機器人分配任務以及建立好倉庫地圖模型之后，接下來更重要的一步也是整個AGV調度中最為重要的一步就是關于AGV調度的路徑規劃問題。許多學者對這部分的研究大體分為兩種：第一種是集中式系統規劃［3］，這種方法對中央處理單元要求性能較高，在倉庫這種級別中無法要求處理單元性能優異。第二種就是分布式系統規劃［4］，這種方法對每一臺智能機器人要求性能較高，既要規劃路徑又要接受任務分配等工作，所以工作量大。

現在更多的學者偏向于將全局路徑規劃以及局部路徑規劃結合起來使用，常用的方法有：基于雙種群遺傳算法的路徑規劃，基于時空地圖的路徑規劃與基于時間窗的路徑規劃。

2.1 基于時間窗的路徑規劃

通過加入時間窗的方法來實現其路徑規劃，具體過程如下：

對于單機器人多負載路徑規劃。步驟1：每一個AGV都要有兩條及以上的備選路徑；步驟2：每條路徑都會涉及到多個路徑塊，每個路徑塊都有各自的空閑時間窗，通過統計全部空閑的時間窗可以算出Sch（pk），即每條備選路徑pk的通行時間安排；步驟3：選出用時最短的備選路徑，及時預定此路徑涉及到的所有路徑塊。對于步驟1，為了避免預約通行的其他AGV在相同的時間相遇，采用基于A*的帶懲罰算法來生成候選路徑集，即對每個時間格加入權重，最后通過尋找權重小的路徑展開，尋找到最合適的路徑。對于步驟2，我們給出兩種時間窗搜索的算法，分別是前向時間窗搜索算法以及重選擇時間窗搜索算法，在此基礎上再去計算路徑調度。

而對于多機器人負載時：首先在出發點獲取多個快件，通過每個負載快件互異的目的點，系統會自動規劃出無沖突的路徑方案傳遞給機器人執行，之后AGV根據路徑行走完所有目的地后返回出發點重新加貨。

3 結論

以上討論的方法以及模型大多數是建立在如下所示的理想模型下進行的，在現實世界中存在著很多的不確定因素，故上述很多方法都是失效的或者說效果不佳的。理想模型：（1）AGV只能沿直角方向（即橫縱向）跨越柵格，AGV不能斜向跨越柵格。（2）將每個AGV的裝載時間、卸載時間理想化為零。（3）所有包裹在零時刻到達，所有AGV在零時刻可用。（4）AGV運行過程中保持勻速。（5）不考慮包裹到達投遞區之后的出庫過程。（6）不考慮機器人空載以及負載情況下的運貨速度，以及機器人充電時間。

今后機器人的目標就是向著這個方向改進，首先需要考慮機器人充放電情況，雖然在這方面有一些相關的介紹，但是過于簡單，不能加以推廣應用；其次就是機器人運動過程中可能存在一些均加速以及均減速的情況，這樣機器人在面對碰撞沖突問題上可以不用通過停下來等待來解決節點沖突以及相向沖突問題，此時也會多了一個追擊沖突。這種情況將會更加復雜，有待于進一步研究。