倉儲物流機器人集群的智能調度和路徑規劃

沈博聞，于寧波，劉景泰（.南開大學機器人與信息自動化研究所，天津30007；2.美國紐約州立大學布法羅分校）

倉儲物流機器人集群的智能調度和路徑規劃

沈博聞1，2，于寧波1，劉景泰1
（1.南開大學機器人與信息自動化研究所，天津300071；2.美國紐約州立大學布法羅分校）

電子商務迅猛發展，為倉儲物流帶來了新的需求和挑戰。其發貨單位小型化，品種多、批量小、批次多、周期短，傳統的倉儲物流難以適應新的需求，基于移動機器人的自動化倉儲技術正在興起。首先基于電子商務倉儲物流的任務特點，建立了一個靈活可重構的倉儲空間模型，制訂了適于倉儲物流的機器人運行規則。隨后，將物流任務分解，給出了綜合考慮曼哈頓路徑代價和等待時間代價的機器人調度方法，修正A?算法實現了在特殊道路規則約束下的路徑規劃，進而加入時序建立了時間空間運行地圖進行三維路徑規劃。通過仿真，比較了路徑規劃方法和機器人數量對任務完成時間、運行總里程、道路沖突協調的影響，驗證了智能調度和路徑規劃方法的有效性。

倉儲物流；移動機器人；智能調度；路徑規劃：A?算法

隨著電子商務近年來突飛猛進的發展，物流配送逐漸成為電子商務的核心要素。由于需要協調與調度的資源數量和種類眾多，給倉儲物流中心的運作管理帶來了前所未有的挑戰。根據相關調查，傳統模式的倉庫中工人有60%～70%的時間都耗費在取貨上［1］。在當前的電子商務中，物流配送具有發貨單位小型化的特點，品種多、批量小、批次多、周期短，傳統的人工操作、傳送帶式亦或AGV式的倉儲物流方式已經難以適應電子商務的發展需求，以亞馬遜的Kiva Systems為代表的基于移動機器人的自動化倉儲正在興起。

將自主移動機器人引入倉儲空間中，代替人工搬運貨物，可以有效地減少工人的勞動強度，降低維護成本，提高運行效率，并且對倉儲空間的布局具有良好的可重構性。移動機器人在倉儲空間中的定位，可以通過二維碼、RFID、室內GPS等技術來解決。移動機器人集群與中心控制系統之間的通信，可以通過無線網絡實現。在此基礎上，要實現一個機器人化的自動化倉儲環境，機器人集群需要解決的關鍵問題主要有：1）在訂單任務到達之后，移動機器人的智能調度；2）在移動機器人集群運行的倉儲環境中，機器人移動路徑的規劃和碰撞的預測、檢測、防止；3）在給定倉儲空間和訂單任務密度后，機器人配置數量的優化。

1 倉儲空間結構和物流任務分析

建立一個機器人化的自動化倉儲空間的模型如圖1所示。主要考慮停放位置（空閑或貨架占用）、入貨口、出貨口、縱向道路和橫向道路。每個被2條縱向道路和2條橫向道路圍起來的區域內，有2排停放位置。

圖1 倉儲空間全局平面示意圖Fig.1 W arehouse floor p lan overview

這個倉儲模型具有良好的可重構性，倉儲空間的長度寬度、貨架和道路的數量和密度、入貨口出貨口的數量和位置、訂單的數量和密度等參數，都可以根據具體需要靈活設定。

在此倉儲空間中，多個移動機器人同時運行，為了避免碰撞沖突、簡化機器人的運行規則、提高系統安全運行的魯棒性，設定貨架區域間的橫向、縱向道路均為單行道。

對于建立的倉儲空間模型，物流任務的形式是運送某一貨架從停放位置n1到某個入貨口／出貨口位置n2，待入貨／出貨任務完成后，再搬運回貨架區域位置n3，如圖2所示。

圖2 任務形式Fig.2 Task form

物流任務可以分解成如圖3所示的3個步驟。其中，第1個和第3個步驟可以通過任務的分配調度進行優化，減少所花費的時間；第2個步驟可以采用路徑規劃方法對機器人的路徑進行優化。

圖3 一個任務的流程圖Fig.3 Task flow chart

2 機器人的智能調度和路徑規劃

2.1 機器人的智能調度算法

針對前述物流任務的第1個步驟進行優化，應使承擔任務的機器人能盡早地運行到對應貨架處。因此根據一個評價函數對所有可能執行任務的機器人進行評價，從中選取最合適的機器人［2］。

總的評價函數為

式（1）表示第n個機器人執行此任務的總代價，tn1表示第n個機器人完成當前正在運行的任務預計要耗費的時間（若當前為空閑狀態則此項為0）。w表示擁塞系數，用來反映系統的擁塞程度。設置w＞1可以反映完成當前任務耗費的實際時間要多于預計的時間。tn2表示第n個機器人運行到任務要求貨架處花費的時間。

根據評價函數，將所有的機器人分成2類，1）正在執行當前任務；2）處于空閑狀態。分別計算等待代價和路徑代價，再根據兩者之和對所有的機器人進行評價，選取總代價gn最小的機器人承擔任務。

針對前述物流任務的第3個步驟進行優化，應使機器人搬運的貨架盡快停放在空閑區域內，從而使得機器人可以繼續執行下一個任務。因此，選取距離起點（機器人的當前位置）最近的一個空閑位置停放。使用曼哈頓距離估計代價：

gn＝abs（cur.x－n.x）＋abs（cur.y－n.y）（2）式中：gn表示停放到第n個存放位置的代價。cur.x表示當前點的橫坐標，cur.y表示當前點的縱坐標。n.x表示第n個存放位置的橫坐標，n.y表示第n個存放位置的縱坐標。abs表示求絕對值的函數。

2.2 特殊規則約束下基于A?算法的路徑規劃

在設計的倉儲空間結構中，目前，應用于多機器人系統運動規劃的方法有人工勢場法［3?4］、神經網絡［5?6］、模糊邏輯［7?8］、A?等算法。其中，A?算法已經得到了廣泛地應用，而且能夠保證找到最優的求解路徑［9?10］?？紤]倉儲空間結構中道路單向運行的約束，在A?算法的基礎上進行修正和改進。

A?算法的基本流程是從起始點開始，根據估計代價選擇性地擴展節點，直到將目標點擴展進來。關鍵是選擇合適的評價函數：

f（n）＝g（n）＋h（n）（3）式中：f（n）代表從起始點經過節點n到達目標點的預估代價。g（n）代表從起始點到節點n的真實代價。f（n）代表從節點n到目標點的估計代價。

考慮到倉庫環境中所有的道路均為單行線，在單行線上擴展節點是單向且有序的，如圖4所示，沿縱向道路L1從n1擴展的后繼節點依次是n2、n3、n4、n5、n6、n7。而其中n2、n3以及n5、n6是順次擴展的固定流程，關鍵只在于在n4、n6節點處是否轉向到橫向道路H2、H3。為簡化步驟，將A?算法中以網格為節點擴展路徑修改成以道路為節點擴展路徑。由此，一條完整路徑可以表示為起始點－道路1－道路2…道路n－目標點。如圖4所示，沿縱向道路L1從n1擴展的后繼節點依次是n2、n3，代表橫向道路H2、H3。

圖4 A?算法路徑規劃的節點拓展Fig.4 Node expansion of A?path planning

以道路為節點減少了擴展次數，節省了時間。但是，路徑的起點和終點不一定是道路，還有可能是貨架所在的存放空間。所以，需要加入特殊情況處理，將節點擴展分為3種情況：道路擴展道路、起點擴展道路、道路擴展終點。

當前節點是貨架（起點），則可擴展的節點為相鄰道路上的相鄰位置。如圖5（a）所示，黑色方塊為貨架n1，淺色方塊為可擴展的后續節點，節點n2即縱向道路L1，節點n3即橫向道路H1。當前節點是道路，則可擴展的節點為與此道路交叉的且在道路前方的所有道路。如圖5（b）所示，黑色方塊為節點n1，即縱向道路L1。淺色方塊為可以擴展的節點，包括節點n2，橫向道路H2；節點n3，橫向道路H3；節點n4，橫向道路H4。

圖5 從貨架和道路擴展到道路Fig.5 Expansion from shelf or road to road

當前節點所在的道路與目標點相鄰，則擴展當前點時可以加入目標點。如圖6所示，當前點n1擴展后繼節點n2，即縱向道路L1?？v向道路L1與黑色方塊目標點相鄰。因此，n2可以擴展目標點n3。

圖6 擴展目標點Fig.6 Expand destination

以道路為基本節點，評價函數需要相應的調整。除了基本的曼哈頓距離，還需要根據道路的方向加上相應的轉向代價，如圖7所示。

圖7 估價函數h（n）Fig.7 Cost function h（n）

2.3 加入時序A?算法的路徑規劃

如果預先知道每個時刻各機器人的具體位置，就可以在路徑規劃時預測并避免可能發生的道路沖突。為此，可以設置“時空運行地圖”，記錄下每個機器人隨時間運行的軌跡，把規劃出的機器人軌跡記錄下來形成一張“橫－縱－時間”的三維地圖，作為軌跡規劃的參考。仍然基于A?算法進行規劃，但是將F、G、H的路徑代價替換為時間代價。同時，在考慮運動到某個位置的路程的基礎上，進一步加入因防止碰撞而增加的等待時間代價。由此，在路徑規劃中考慮了沖突延時，可以減少規劃出的路徑產生沖突。

由于道路的單向性，規劃的先后順序并不能夠保證運行時的優先級。如果后規劃的任務插入到先規劃的任務道路前方，那么也只能由在道路后方的先規劃的任務等待。這樣就導致實際的軌跡跟原有的規劃不完全符合。在這種情況下，任務仍然能夠根據規劃出來的路徑完成，只是時間可能不合拍。如果繼續根據有時間偏差的時空運行地圖去規劃新的任務，誤差會積累，雖然任務仍然能夠完成，但是路徑不是最優。為此，修正路徑規劃方法，在每一次非規劃的避讓發生之后及時修正時空運行地圖，使得地圖與實際相符。

2.4 碰撞預防

已經為了避免可能發生的碰撞，設置獨占點。在某個時刻某個位置只能由一個移動機器人獨自占用。同一時刻的其他機器人想要進入此位置必須等待。在實際系統中，這可以由安裝在機器人上的超聲波或紅外傳感器實現。在檢測到與其他機器人距離小于警戒值的情況下，緊急剎車，防止碰撞。

3 仿真實驗

通過仿真實驗，檢驗智能調度和路徑規劃方法是否有效，并進一步研究機器人的數量配置對任務執行效率的影響。仿真程序和結果都在MATLAB 2013a（Math Works Corporation，USA）上完成。

3.1 任務生成和實驗設定

為保證仿真實驗結果的客觀性，要避免受到任務本身特點可能帶來的的影響。為此：

1）采用隨機算法產生任務。貨架與機器人的初始位置也隨機產生。任務調用的貨架編號和入貨口／出貨口符合隨機高斯分布。

2）任務數量設為1 000，隨機產生10組任務。移動機器人的數量分別設定為10、20、30、40和50共5種情況。每種情況下，利用智能調度算法和2種路徑規劃算法完成給定的10組任務?？偣策M行了100次實驗。

3.2 實驗結果

在進行的100次實驗中，所有任務都順利完成，驗證了倉儲空間架構設計、智能調度和路徑規劃方法的可行性和有效性。

表1中，利用雙因子方差分析評價機器人數量和路徑規劃算法對于完成物流任務所運行總里程、耗費時間以及搶路沖突的影響（置信度p＝0.05）。機器人的數量配置對于運行總里程、耗費時間和搶路沖突具有顯著的影響，而2種路徑規劃算法在運行總里程和耗費時間這兩方面沒有體現出顯著差別，但是在搶路沖突方面表現出了明顯的差別。

表1 仿真實驗結果Tab le 1 Results of simulation experim ents

圖8給出了不同數量配置的機器人集群在2種路徑規劃算法下完成1 000個任務所運行總里程的10次實驗平均值。隨著機器人數量的增加，機器人集群完成設定任務所運行的總里程逐漸降低。增加的機器人為系統的調度提供了更大的靈活度，可以選擇與任務貨架距離更近的機器人承擔物流任務。

圖8 完成設定任務運行總里程隨機器人數量的增加而減少Fig.8 The total pathway decreases as robot number increases

圖9 給出了不同數量配置的機器人在2種路徑規劃算法下完成1 000個任務耗費時間的10次實驗平均值。隨著機器人數量的增加，完成設定任務所耗費的總時間明顯降低。但是同時，所需要協調的搶路沖突也明顯增加，如圖10所示。

圖9 完成設定任務運行總里程隨機器人數量的增加而減少Fig.9 The total pathway decreases as robot number increases

圖10 完成設定任務運行總里程隨機器人數量的增加而減少Fig.10 The total pathway decreases as robot number increases

由圖8和圖9可以直觀看出，在特殊道路規則的約束下，基于修正的A?算法和加入時序的A?算法這2種路徑規劃方法在完成任務運行總路程和耗費時間2個方面，表現接近。加入了時序的路徑規劃算法，降低了運行中發生的搶路次數，如圖10所示。但是，在倉儲空間中道路單向運行設定的約束下，加入時序的A?算法無法全部避免搶路沖突，沖突次數隨著機器人數量的增加而明顯上升。

4 結束語

電子商務的迅猛發展為倉儲物流帶來了新的需求和挑戰，本文對應用移動機器人技術發展新一代的智能倉儲物流進行了探索。建立了一個靈活可重構的倉儲空間模型，制訂了執行物流任務的移動機器人集群的運行規則，對智能調度和路徑規劃進行了方法研究和仿真驗證。由此表明，基于移動機器人集群的自動化倉儲技術有望在電子商務物流中起到顛覆性的關鍵作用。

本文中，訂單是按照時間順序發送給機器人中心控制系統的。將來，可以對訂單分批優化之后再釋放，能夠更加有效地對機器人進行調度和規劃。

［1］鄒爽心.倉儲機器人的應用現狀與發展戰略探討［J］.物流工程與管理，2013，35（6）：171?172.ZOU Shuangxin.The present and future of warehouse robot［J］.Logistics Engineering and Management，2013，35（6）：171?172.

［2］曹寶文.自動化倉庫中多AGV系統路徑規劃研究［D］.天津：南開大學，2012：21?23.CAO Baowen.Path planning of multi?AGV system in auto?matic warehouse［D］.Tianjin：Nankai University，2012：21?23.

［3］張建英，趙志萍，劉暾.基于人工勢場法的機器人路徑規劃［J］.哈爾濱工業大學學報，2006，38（8）：1306?1309.ZHANG Jianying，ZHAO Zhiping，LIU Tun.A path plan?ningmethod for mobile robot based on artificial potential field［J］.Journal of Harbin Institute of Technology，2006，38（8）：1306?1309.

［4］于振中，閆繼宏，趙杰，等.改進人工勢場法的移動機器人路徑規劃［J］.哈爾濱工業大學學報，2011，43（1）：50?55.YU Zhenzhong，YAN Jihong，ZHAO Jie，et al.Mobile ro?bot path planning based on improved artificial potential field method［J］.Journal of Harbin Institute of Technology，2011，43（1）：50?55.

［5］黃磊.基于神經網絡的移動機器人路徑規劃研究［D］.武漢：武漢理工大學，2008：17?27.HUANG Lei.Research on path planning of mobile robots based on neural networks［D］.Wuhan：Wuhan University of Technology，2008：17?27.

［6］陳華志，謝存禧，曾德懷.基于神經網絡的移動機器人路徑規劃算法的仿真［J］.華南理工大學學報：自然科學版，2003，31（6）：56?59.CHEN Huazhi，XIE Cunxi，ZENG Dehuai.Simulation of path planning algorithm of mobile robots based on neural networks［J］.Journalof South China University of Technolo?gy：Natural Science，2003，31（6）：56?59.

［7］蘇治寶，陸際聯.用模糊邏輯法對移動機器人進行路徑規劃的研究［J］.北京理工大學學報，2003，23（3）：290?293.SU Zhibao，LU Jilian.A study on the path planning ofmo?bile robot with the fuzzy logic method［J］.Transactions of Beijing Institute of Technology，2003，23（3）：290?293.

［8］卓睿，陳宗海，陳春林.基于強化學習和模糊邏輯的移動機器人導航［J］.計算機仿真，2005，22（8）：157?162.ZHUO Rui，CHEN Zonghai，CHEN Chunlin.Navigation for mobile robots using reinforcement learning and fuzzy logic［J］.Computer Simulation，2005，22（8）：157?162.

［9］HART P E，NILSSON N J，RAPHAEL B.A formal basis for the heuristic determination of minimum cost paths［J］.IEEE Transactions on Systems Science and Cybernetics，1968，4（2）：100?107.

［10］王勇.智能倉庫系統多移動機器人路勁規劃研究［D］.哈爾濱：哈爾濱工業大學，2010：19?30.WANG Yong.Research about path planning of multiple mobile robots in intelligentwarehouse system［D］.Harbin：Harbin Institute of Technology，2010：19?30.

沈博聞，男，1991年生，美國紐約州立大學布法羅分校攻讀碩士研究生，主要研究方向為機器人與智能系統、人與機器人的交互、協作與控制、智能服務和輔助機器人。

于寧波，男，1991年生，副教授.博士，主要研究方向為機器人與智能系統、人與機器人的交互、協作與控制，智能服務和輔助機器人。

劉景泰，男，1964年生，教授，博士，主要研究方向為機器人技術、計算機應用與信息自動化系統、智能科學與技術。

Intelligent scheduling and path planning of warehousemobile robots

SHEN Bowen1，2，YU Ningbo1，LIU Jingtai1
（Institute of Robotics and Automatic Information System，Nankai University，Tianjin Key Laboratory on Intelligent Robotics，Tianjin 300071，China）

The rapid increase of E?commerce brings new challenges for warehouse logistics.The shipments are char?acterized as big variety，smallvolume，large number of small batchesand shortcycle，and thus are difficult to han?dle.Emerging logistic technology based on mobile robots is the promising solution.In thiswork，firstly awarehouse modelwith flexible re?configurability was set up and a setof rules to govern warehouse logistics and robotmovement were defined.After that，the logistic task was decomposed and a robot schedulingmethod taking into account the Manhattan path cost and the waiting time cost was proposed.Next，the A?algorithm was adapted for robot path planning under the special constraint rules.Finally，timing information was included for consideration and a time?space map was established to carry out three?dimensional path planning.The intelligent scheduling and path plan?ningmethodswere validated by simulation experiments.The path planningmethods and number of robotswere com?pared in relation to total time cost，totalmileage and number of conflicts.

warehouse logistics；mobile robots；intelligent scheduling；path planning；A?algorithm

TP242.6

A

1673?4785（2014）06?659?06

沈博聞，于寧波，劉景泰.倉儲物流機器人集群的智能調度和路徑規劃［J］.智能系統學報，2014，9（6）：659?664.

英文引用格式：SHEN Bowen，YU Ningbo，LIU Jingtai.Intelligent scheduling and path p lanning of warehouse mobile robots［J］.CAAI Transactions on Intelligent System s，2014，9（6）：659?664.

10.3969／j.issn.1673?4785.201312048

http：／／www.cnki.net／kcms／doi／10.3969／j.issn.1673?4785.201312048.htm l

2013?12?24.

日期：2014?11?13.

國家“863”計劃資助項目（2012AA041403）.

于寧波.E?mail：nyu＠nankai.edu.cn.