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

倉(cāng)儲(chǔ)物流機(jī)器人集群的智能調(diào)度和路徑規(guī)劃

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

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

倉(cāng)儲(chǔ)物流；移動(dòng)機(jī)器人；智能調(diào)度；路徑規(guī)劃：A?算法

隨著電子商務(wù)近年來(lái)突飛猛進(jìn)的發(fā)展，物流配送逐漸成為電子商務(wù)的核心要素。由于需要協(xié)調(diào)與調(diào)度的資源數(shù)量和種類眾多，給倉(cāng)儲(chǔ)物流中心的運(yùn)作管理帶來(lái)了前所未有的挑戰(zhàn)。根據(jù)相關(guān)調(diào)查，傳統(tǒng)模式的倉(cāng)庫(kù)中工人有60%～70%的時(shí)間都耗費(fèi)在取貨上［1］。在當(dāng)前的電子商務(wù)中，物流配送具有發(fā)貨單位小型化的特點(diǎn)，品種多、批量小、批次多、周期短，傳統(tǒng)的人工操作、傳送帶式亦或AGV式的倉(cāng)儲(chǔ)物流方式已經(jīng)難以適應(yīng)電子商務(wù)的發(fā)展需求，以亞馬遜的Kiva Systems為代表的基于移動(dòng)機(jī)器人的自動(dòng)化倉(cāng)儲(chǔ)正在興起。

將自主移動(dòng)機(jī)器人引入倉(cāng)儲(chǔ)空間中，代替人工搬運(yùn)貨物，可以有效地減少工人的勞動(dòng)強(qiáng)度，降低維護(hù)成本，提高運(yùn)行效率，并且對(duì)倉(cāng)儲(chǔ)空間的布局具有良好的可重構(gòu)性。移動(dòng)機(jī)器人在倉(cāng)儲(chǔ)空間中的定位，可以通過(guò)二維碼、RFID、室內(nèi)GPS等技術(shù)來(lái)解決。移動(dòng)機(jī)器人集群與中心控制系統(tǒng)之間的通信，可以通過(guò)無(wú)線網(wǎng)絡(luò)實(shí)現(xiàn)。在此基礎(chǔ)上，要實(shí)現(xiàn)一個(gè)機(jī)器人化的自動(dòng)化倉(cāng)儲(chǔ)環(huán)境，機(jī)器人集群需要解決的關(guān)鍵問(wèn)題主要有：1）在訂單任務(wù)到達(dá)之后，移動(dòng)機(jī)器人的智能調(diào)度；2）在移動(dòng)機(jī)器人集群運(yùn)行的倉(cāng)儲(chǔ)環(huán)境中，機(jī)器人移動(dòng)路徑的規(guī)劃和碰撞的預(yù)測(cè)、檢測(cè)、防止；3）在給定倉(cāng)儲(chǔ)空間和訂單任務(wù)密度后，機(jī)器人配置數(shù)量的優(yōu)化。

1 倉(cāng)儲(chǔ)空間結(jié)構(gòu)和物流任務(wù)分析

建立一個(gè)機(jī)器人化的自動(dòng)化倉(cāng)儲(chǔ)空間的模型如圖1所示。主要考慮停放位置（空閑或貨架占用）、入貨口、出貨口、縱向道路和橫向道路。每個(gè)被2條縱向道路和2條橫向道路圍起來(lái)的區(qū)域內(nèi)，有2排停放位置。

圖1 倉(cāng)儲(chǔ)空間全局平面示意圖Fig.1 W arehouse floor p lan overview

這個(gè)倉(cāng)儲(chǔ)模型具有良好的可重構(gòu)性，倉(cāng)儲(chǔ)空間的長(zhǎng)度寬度、貨架和道路的數(shù)量和密度、入貨口出貨口的數(shù)量和位置、訂單的數(shù)量和密度等參數(shù)，都可以根據(jù)具體需要靈活設(shè)定。

在此倉(cāng)儲(chǔ)空間中，多個(gè)移動(dòng)機(jī)器人同時(shí)運(yùn)行，為了避免碰撞沖突、簡(jiǎn)化機(jī)器人的運(yùn)行規(guī)則、提高系統(tǒng)安全運(yùn)行的魯棒性，設(shè)定貨架區(qū)域間的橫向、縱向道路均為單行道。

對(duì)于建立的倉(cāng)儲(chǔ)空間模型，物流任務(wù)的形式是運(yùn)送某一貨架從停放位置n1到某個(gè)入貨口／出貨口位置n2，待入貨／出貨任務(wù)完成后，再搬運(yùn)回貨架區(qū)域位置n3，如圖2所示。

圖2 任務(wù)形式Fig.2 Task form

物流任務(wù)可以分解成如圖3所示的3個(gè)步驟。其中，第1個(gè)和第3個(gè)步驟可以通過(guò)任務(wù)的分配調(diào)度進(jìn)行優(yōu)化，減少所花費(fèi)的時(shí)間；第2個(gè)步驟可以采用路徑規(guī)劃方法對(duì)機(jī)器人的路徑進(jìn)行優(yōu)化。

圖3 一個(gè)任務(wù)的流程圖Fig.3 Task flow chart

2 機(jī)器人的智能調(diào)度和路徑規(guī)劃

2.1 機(jī)器人的智能調(diào)度算法

針對(duì)前述物流任務(wù)的第1個(gè)步驟進(jìn)行優(yōu)化，應(yīng)使承擔(dān)任務(wù)的機(jī)器人能盡早地運(yùn)行到對(duì)應(yīng)貨架處。因此根據(jù)一個(gè)評(píng)價(jià)函數(shù)對(duì)所有可能執(zhí)行任務(wù)的機(jī)器人進(jìn)行評(píng)價(jià)，從中選取最合適的機(jī)器人［2］。

總的評(píng)價(jià)函數(shù)為

式（1）表示第n個(gè)機(jī)器人執(zhí)行此任務(wù)的總代價(jià)，tn1表示第n個(gè)機(jī)器人完成當(dāng)前正在運(yùn)行的任務(wù)預(yù)計(jì)要耗費(fèi)的時(shí)間（若當(dāng)前為空閑狀態(tài)則此項(xiàng)為0）。w表示擁塞系數(shù)，用來(lái)反映系統(tǒng)的擁塞程度。設(shè)置w＞1可以反映完成當(dāng)前任務(wù)耗費(fèi)的實(shí)際時(shí)間要多于預(yù)計(jì)的時(shí)間。tn2表示第n個(gè)機(jī)器人運(yùn)行到任務(wù)要求貨架處花費(fèi)的時(shí)間。

根據(jù)評(píng)價(jià)函數(shù)，將所有的機(jī)器人分成2類，1）正在執(zhí)行當(dāng)前任務(wù)；2）處于空閑狀態(tài)。分別計(jì)算等待代價(jià)和路徑代價(jià)，再根據(jù)兩者之和對(duì)所有的機(jī)器人進(jìn)行評(píng)價(jià)，選取總代價(jià)gn最小的機(jī)器人承擔(dān)任務(wù)。

針對(duì)前述物流任務(wù)的第3個(gè)步驟進(jìn)行優(yōu)化，應(yīng)使機(jī)器人搬運(yùn)的貨架盡快停放在空閑區(qū)域內(nèi)，從而使得機(jī)器人可以繼續(xù)執(zhí)行下一個(gè)任務(wù)。因此，選取距離起點(diǎn)（機(jī)器人的當(dāng)前位置）最近的一個(gè)空閑位置停放。使用曼哈頓距離估計(jì)代價(jià)：

gn＝abs（cur.x－n.x）＋abs（cur.y－n.y）（2）式中：gn表示停放到第n個(gè)存放位置的代價(jià)。cur.x表示當(dāng)前點(diǎn)的橫坐標(biāo)，cur.y表示當(dāng)前點(diǎn)的縱坐標(biāo)。n.x表示第n個(gè)存放位置的橫坐標(biāo)，n.y表示第n個(gè)存放位置的縱坐標(biāo)。abs表示求絕對(duì)值的函數(shù)。

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

在設(shè)計(jì)的倉(cāng)儲(chǔ)空間結(jié)構(gòu)中，目前，應(yīng)用于多機(jī)器人系統(tǒng)運(yùn)動(dòng)規(guī)劃的方法有人工勢(shì)場(chǎng)法［3?4］、神經(jīng)網(wǎng)絡(luò)［5?6］、模糊邏輯［7?8］、A?等算法。其中，A?算法已經(jīng)得到了廣泛地應(yīng)用，而且能夠保證找到最優(yōu)的求解路徑［9?10］?？紤]倉(cāng)儲(chǔ)空間結(jié)構(gòu)中道路單向運(yùn)行的約束，在A?算法的基礎(chǔ)上進(jìn)行修正和改進(jìn)。

A?算法的基本流程是從起始點(diǎn)開始，根據(jù)估計(jì)代價(jià)選擇性地?cái)U(kuò)展節(jié)點(diǎn)，直到將目標(biāo)點(diǎn)擴(kuò)展進(jìn)來(lái)。關(guān)鍵是選擇合適的評(píng)價(jià)函數(shù)：

f（n）＝g（n）＋h（n）（3）式中：f（n）代表從起始點(diǎn)經(jīng)過(guò)節(jié)點(diǎn)n到達(dá)目標(biāo)點(diǎn)的預(yù)估代價(jià)。g（n）代表從起始點(diǎn)到節(jié)點(diǎn)n的真實(shí)代價(jià)。f（n）代表從節(jié)點(diǎn)n到目標(biāo)點(diǎn)的估計(jì)代價(jià)。

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

圖4 A?算法路徑規(guī)劃的節(jié)點(diǎn)拓展Fig.4 Node expansion of A?path planning

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

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

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

當(dāng)前節(jié)點(diǎn)所在的道路與目標(biāo)點(diǎn)相鄰，則擴(kuò)展當(dāng)前點(diǎn)時(shí)可以加入目標(biāo)點(diǎn)。如圖6所示，當(dāng)前點(diǎn)n1擴(kuò)展后繼節(jié)點(diǎn)n2，即縱向道路L1?？v向道路L1與黑色方塊目標(biāo)點(diǎn)相鄰。因此，n2可以擴(kuò)展目標(biāo)點(diǎn)n3。

圖6 擴(kuò)展目標(biāo)點(diǎn)Fig.6 Expand destination

以道路為基本節(jié)點(diǎn)，評(píng)價(jià)函數(shù)需要相應(yīng)的調(diào)整。除了基本的曼哈頓距離，還需要根據(jù)道路的方向加上相應(yīng)的轉(zhuǎn)向代價(jià)，如圖7所示。

圖7 估價(jià)函數(shù)h（n）Fig.7 Cost function h（n）

2.3 加入時(shí)序A?算法的路徑規(guī)劃

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

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

2.4 碰撞預(yù)防

已經(jīng)為了避免可能發(fā)生的碰撞，設(shè)置獨(dú)占點(diǎn)。在某個(gè)時(shí)刻某個(gè)位置只能由一個(gè)移動(dòng)機(jī)器人獨(dú)自占用。同一時(shí)刻的其他機(jī)器人想要進(jìn)入此位置必須等待。在實(shí)際系統(tǒng)中，這可以由安裝在機(jī)器人上的超聲波或紅外傳感器實(shí)現(xiàn)。在檢測(cè)到與其他機(jī)器人距離小于警戒值的情況下，緊急剎車，防止碰撞。

3 仿真實(shí)驗(yàn)

通過(guò)仿真實(shí)驗(yàn)，檢驗(yàn)智能調(diào)度和路徑規(guī)劃方法是否有效，并進(jìn)一步研究機(jī)器人的數(shù)量配置對(duì)任務(wù)執(zhí)行效率的影響。仿真程序和結(jié)果都在MATLAB 2013a（Math Works Corporation，USA）上完成。

3.1 任務(wù)生成和實(shí)驗(yàn)設(shè)定

為保證仿真實(shí)驗(yàn)結(jié)果的客觀性，要避免受到任務(wù)本身特點(diǎn)可能帶來(lái)的的影響。為此：

1）采用隨機(jī)算法產(chǎn)生任務(wù)。貨架與機(jī)器人的初始位置也隨機(jī)產(chǎn)生。任務(wù)調(diào)用的貨架編號(hào)和入貨口／出貨口符合隨機(jī)高斯分布。

2）任務(wù)數(shù)量設(shè)為1 000，隨機(jī)產(chǎn)生10組任務(wù)。移動(dòng)機(jī)器人的數(shù)量分別設(shè)定為10、20、30、40和50共5種情況。每種情況下，利用智能調(diào)度算法和2種路徑規(guī)劃算法完成給定的10組任務(wù)?？偣策M(jìn)行了100次實(shí)驗(yàn)。

3.2 實(shí)驗(yàn)結(jié)果

在進(jìn)行的100次實(shí)驗(yàn)中，所有任務(wù)都順利完成，驗(yàn)證了倉(cāng)儲(chǔ)空間架構(gòu)設(shè)計(jì)、智能調(diào)度和路徑規(guī)劃方法的可行性和有效性。

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

表1 仿真實(shí)驗(yàn)結(jié)果Tab le 1 Results of simulation experim ents

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

圖8 完成設(shè)定任務(wù)運(yùn)行總里程隨機(jī)器人數(shù)量的增加而減少Fig.8 The total pathway decreases as robot number increases

圖9 給出了不同數(shù)量配置的機(jī)器人在2種路徑規(guī)劃算法下完成1 000個(gè)任務(wù)耗費(fèi)時(shí)間的10次實(shí)驗(yàn)平均值。隨著機(jī)器人數(shù)量的增加，完成設(shè)定任務(wù)所耗費(fèi)的總時(shí)間明顯降低。但是同時(shí)，所需要協(xié)調(diào)的搶路沖突也明顯增加，如圖10所示。

圖9 完成設(shè)定任務(wù)運(yùn)行總里程隨機(jī)器人數(shù)量的增加而減少Fig.9 The total pathway decreases as robot number increases

圖10 完成設(shè)定任務(wù)運(yùn)行總里程隨機(jī)器人數(shù)量的增加而減少Fig.10 The total pathway decreases as robot number increases

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

4 結(jié)束語(yǔ)

電子商務(wù)的迅猛發(fā)展為倉(cāng)儲(chǔ)物流帶來(lái)了新的需求和挑戰(zhàn)，本文對(duì)應(yīng)用移動(dòng)機(jī)器人技術(shù)發(fā)展新一代的智能倉(cāng)儲(chǔ)物流進(jìn)行了探索。建立了一個(gè)靈活可重構(gòu)的倉(cāng)儲(chǔ)空間模型，制訂了執(zhí)行物流任務(wù)的移動(dòng)機(jī)器人集群的運(yùn)行規(guī)則，對(duì)智能調(diào)度和路徑規(guī)劃進(jìn)行了方法研究和仿真驗(yàn)證。由此表明，基于移動(dòng)機(jī)器人集群的自動(dòng)化倉(cāng)儲(chǔ)技術(shù)有望在電子商務(wù)物流中起到顛覆性的關(guān)鍵作用。

本文中，訂單是按照時(shí)間順序發(fā)送給機(jī)器人中心控制系統(tǒng)的。將來(lái)，可以對(duì)訂單分批優(yōu)化之后再釋放，能夠更加有效地對(duì)機(jī)器人進(jìn)行調(diào)度和規(guī)劃。

［1］鄒爽心.倉(cāng)儲(chǔ)機(jī)器人的應(yīng)用現(xiàn)狀與發(fā)展戰(zhàn)略探討［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］曹寶文.自動(dòng)化倉(cāng)庫(kù)中多AGV系統(tǒng)路徑規(guī)劃研究［D］.天津：南開大學(xué)，2012：21?23.CAO Baowen.Path planning of multi?AGV system in auto?matic warehouse［D］.Tianjin：Nankai University，2012：21?23.

［3］張建英，趙志萍，劉暾.基于人工勢(shì)場(chǎng)法的機(jī)器人路徑規(guī)劃［J］.哈爾濱工業(yè)大學(xué)學(xué)報(bào)，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ìn)人工勢(shì)場(chǎng)法的移動(dòng)機(jī)器人路徑規(guī)劃［J］.哈爾濱工業(yè)大學(xué)學(xué)報(bào)，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］黃磊.基于神經(jīng)網(wǎng)絡(luò)的移動(dòng)機(jī)器人路徑規(guī)劃研究［D］.武漢：武漢理工大學(xué)，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īng)網(wǎng)絡(luò)的移動(dòng)機(jī)器人路徑規(guī)劃算法的仿真［J］.華南理工大學(xué)學(xué)報(bào)：自然科學(xué)版，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］蘇治寶，陸際聯(lián).用模糊邏輯法對(duì)移動(dòng)機(jī)器人進(jìn)行路徑規(guī)劃的研究［J］.北京理工大學(xué)學(xué)報(bào)，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］卓睿，陳宗海，陳春林.基于強(qiáng)化學(xué)習(xí)和模糊邏輯的移動(dòng)機(jī)器人導(dǎo)航［J］.計(jì)算機(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］王勇.智能倉(cāng)庫(kù)系統(tǒng)多移動(dòng)機(jī)器人路勁規(guī)劃研究［D］.哈爾濱：哈爾濱工業(yè)大學(xué)，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年生，美國(guó)紐約州立大學(xué)布法羅分校攻讀碩士研究生，主要研究方向?yàn)闄C(jī)器人與智能系統(tǒng)、人與機(jī)器人的交互、協(xié)作與控制、智能服務(wù)和輔助機(jī)器人。

于寧波，男，1991年生，副教授.博士，主要研究方向?yàn)闄C(jī)器人與智能系統(tǒng)、人與機(jī)器人的交互、協(xié)作與控制，智能服務(wù)和輔助機(jī)器人。

劉景泰，男，1964年生，教授，博士，主要研究方向?yàn)闄C(jī)器人技術(shù)、計(jì)算機(jī)應(yīng)用與信息自動(dòng)化系統(tǒng)、智能科學(xué)與技術(shù)。

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

沈博聞，于寧波，劉景泰.倉(cāng)儲(chǔ)物流機(jī)器人集群的智能調(diào)度和路徑規(guī)劃［J］.智能系統(tǒng)學(xué)報(bào)，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.

國(guó)家“863”計(jì)劃資助項(xiàng)目（2012AA041403）.

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