基于A* 算法的搬運機器人路徑規劃
——以菜鳥智能倉為例

閆 妍，陶美春 YAN Yan, TAO Meichun

（新疆財經大學 工商管理學院，新疆 烏魯木齊830012）

(School of Business Abministration, Xinjiang University of Finance and Economics, Urumqi 830012, China)

0 引 言

隨著移動互聯網的普及和發展，電商物流平臺已經迎來了新的世紀，物流業的發展作為其重要的支撐，也一直推動著其快速的發展。倉儲物流作為物流中一個重要環節，提高貨物流通效率降低成本已是當今社會對倉儲物流的訴求。電商平臺訂單數量日益增長，傳統的揀選模式占整個倉庫操作流程的60%-70%[1]，效率低成本高，已難以適應現在大型物流企業的需要。隨著自動化技術以及智能機器人的發展和應用，倉儲物流開始大量發展自動化立體倉庫，一些大型物流企業率先使用智能搬運機器人，使得揀選效率大大提高，智能搬運機器人在物流業中占據著重要地位。

另一方面，伴隨著我國人口老齡化的到來，勞動資源豐富的“人口紅利”時代已經逐漸退去[2]，企業成本日益增高，提升倉儲自動化水平，使用智能搬運機器人代替人工已是必然趨勢。

綜上所述，電子商務的快速發展極大地推動著我國物流業的現代化、自動化，智能搬運機器人在自動化倉庫中的使用已成趨勢。但是這項搬運機器人技術的投資昂貴，我國的倉儲運輸和物流發展相對薄弱，很多的企業可望而不可及，同時也面臨著搬運機器人調度，路徑規劃不合理的問題，使得搬運機器人的推廣和應用受到了制約，所以研究搬運機器人的路徑規劃問題迫在眉睫。

1 文獻綜述

1.1 算法研究

關于搬運機器人的路徑規劃，算法是核心內容，學者們對算法的研究成果頗豐。劉晶等人（2019） 對生物激勵神經網絡算法產生的路徑規劃長度長，轉彎次數多的問題，提出結合A*算法進行改進，讓機器人使用最短的路徑逃離死鎖[3]。成怡、肖宏圖（2020） 融合改進A*算法和Morphin 搜索樹算法，規劃全局路徑實現動態避障。雖然方法取得了一定的效果，但運算復雜檢索速度慢[4]。薛緯洋（2016） 將A*算法作為基礎同時運用三維地圖，使此算法具有方向搜索的功能，節約了計算的時間，可有效解決碰撞沖突的情況[5]。

1.2 避障研究

在搬運機器人運行的環境中，除了有倉庫中已有的設施設備以及其它靜態障礙物，還會碰到其它搬運機器人擋道等動態障礙物。越來越多機器人的使用，除了紅外線、超聲波等感知技術不斷研究應用，同時還引來許多學者對避障方法的研究。潘成浩（2017） 對存在碰撞沖突的搬運機器人進行優先級的判斷，讓優先級低的及時做出路徑調整避免沖突[6]。劉敬一（2018） 根據任務的需求對優先級的設置進行了詳細的闡述，并根據實時情況調整搬運機器人的優先級[7]。

通過對文獻的研究和梳理，可以發現對于搬運機器人路徑規劃相關研究不少。但也發現還存在許多不足，如算法自身的缺陷，對于遺傳算法雖然迭代效果很好，但是搜索時間長。很多路徑規劃還停留在以規劃路徑最短為最終目標，并未考慮到搬運機器人在運行過程中轉彎次數不同對時間和能量消耗也不同。目前對于倉儲中搬運機器人的路徑規劃技術、避障技術尚處于研究的初級階段，并不是很成熟。同時缺乏全局動態路徑規劃，難以解決倉儲企業的實際問題。基于A*算法能通過啟發式函數找到環境中的最優解，并且研究成果相對成熟，考慮到A*算法的可靠穩定性，將以A*算法作為基礎來進行路徑規劃。對于傳統的A*算法是以路徑最短為衡量標準對其進行改進，綜合考慮在路徑最短的前提下同時保證時間最短，因為對于企業來說時間就是金錢。對于現實中動態避障，將時間預約表和交通規則結合，解決搬運機器人在運行過程中出現的碰撞沖突和死鎖問題。

2 菜鳥智能倉搬運機器人作業環境簡介

2.1 菜鳥智能倉庫系統概述

菜鳥聯盟首個全自動化倉庫正式開倉運營，位于我國廣州增城物流園區，占地面達10 萬多平方米。目前主要對天貓超市商品進行存儲和分揀，菜鳥智能倉標志著我國倉儲物流進入了一個全新水平，智能化的設備代替人工作業精準高效，實現了我國倉儲智能化的新突破。

菜鳥智能倉采用“貨到人”的揀選模式，在倉庫接到訂單以后，發布任務給搬運機器人，機器人會在接到倉庫管理系統的指令后立即來到一個存放指定貨物的貨架前，將貨架從底部頂起，搬運至進行揀貨的平臺供倉庫揀貨員進行揀選。這途中代替了傳統的人在貨架間奔波，尋找貨物的揀選任務模式。揀貨的效率至少可以提高30%，揀貨準確率幾乎可以達到100%。這種自動化的倉庫大幅減少和降低了倉庫揀貨員的勞動強度，大大提高了分揀出庫的效率。

2.2 搬運機器人作業環境描述及簡化模型

（1） 作業環境描述。菜鳥智能倉中搬運機器人“小藍人”們，主要作業在貨物揀選區，揀選區有6 個揀貨臺，1 160 個存放小件貨物的移動貨架，230 個存放大件貨物的托盤，100 臺搬運機器人，在倉庫最里面有搬運機器人的充電樁。并對智能搬運機器人的行走速度、移動貨架區的行走道路長度、揀選貨架的承載力進行了詳細的調研，詳情見表1。

表1 揀貨作業相關數據調研

（2） 簡化模型。為了簡化菜鳥智能倉庫模型，首先對搬運機器人和菜鳥智能倉庫環境做出如下分析：

·為了簡化菜鳥智能倉揀選作業區環境，本文使用柵格地圖。

·智能倉中搬運機器人根據訂單分配指令搬運貨架。

·搬運機器人按照上、下、左、右的方向行駛。

·每一臺搬運機器人都是勻速行駛的。

·搬運機器人裝有傳感設備，可以感知周邊的障礙物。

·搬運機器人和所有的貨物以及貨架都有自己的ID，磁軌上都鋪有二維碼，搬運機器人通過掃描二維碼確定自己的路徑。

·搬運機器人執行任務時有三類指令：運行、充電、休眠，每一臺搬運機器人都是相對獨立自由的。

·以搬運機器人完成任務的時間代價作為衡量運行效率的標準。

根據菜鳥揀選作業區實際情況簡化智能倉庫模型，如圖1 所示。倉庫最左邊的區域為揀貨工作人員進行貨物分揀的區域，

總共有6 處揀選臺，由綠色方格代表，搬運機器人把貨物搬運至揀選臺附近供揀貨人員對貨物進行揀選。倉庫右邊黃色區域為移動貨架區域，每一臺貨架都有自己的ID 以便搬運機器人查找。灰色區域為大件托盤區，搬運機器人只需直接將托盤搬運至打包區進行打包。白色部分為機器人行走的道路，紅色為目標貨架，藍色圓圈代表智能搬運機器人，機器人只能在白色道路上行走。

圖1 菜鳥智能倉庫簡化模型

2.3 搬運機器人智能倉庫系統的問題分析

通過對菜鳥智能搬運機器人的行走路徑調研，發現存在以下幾個問題，會出現站臺等待時間長，造成作業效率低下。

由于規劃錯誤原路返回和道路被占用，為了避讓和等待退回，導致機器人會在找到目標貨架或者搬運貨架時往返迂回。由于規劃不合理，導致行走路徑過長。同時多機器人同時工作時，沒有一定的交通規則必然會出現擁堵和等待，為了避讓機器人會選擇繞路，所以導致行走路徑過長。在機器人從充電區域進入工作區域時，沒有合理的分配作業任務，導致先行走的機器人搬運就近貨物，后行走的搬運最遠貨物，造成站臺等待時間過高。

3 搬運機器人行走路徑建模

3.1 行走路徑建模概述

菜鳥智能倉庫中搬運機器人動態路徑規劃系統可以表示為由ROB、Map、O、D四種元素組成的系統，ROB表示在菜鳥智能倉庫中運行的搬運機器人系統，即ROB=rob1,…,robn（倉庫中的N臺搬運機器人）。Map表示由倉庫中放置的貨架、揀選臺、充電樁以及其它的設施設備，即這些靜態的障礙物，還包括機器人在運行過程中遇到的工作人員和其它搬運機器人，即動態障礙物組成的倉庫環境。O則表示所有機器人的起始點，在運行過程中N臺機器人有N個起始點（O=o1,…,on），可以是揀選臺，可以是充電樁，也可以是倉庫中的任意位置，要看搬運機器人在接到指令時的位置。D則表示搬運機器人的目標點，當機器人是去尋找目標貨架，則目標點就是目標貨架所在的位置。如果是將目標貨架搬運至相應的揀選臺，則目標點是揀選臺。為了提高菜鳥智能倉的揀貨作業效率，以智能搬運機器人搬運貨架的時間長短作為衡量標準，通過縮短機器人在行走中的時間浪費，來減少揀貨站臺的等待時間。

3.2 基于傳統A*算法的行走路徑規劃建模

（1） 柵格地圖。為了更好地方便研究搬運機器人在菜鳥智能倉的路徑規劃，首先采用了柵格地圖，例如圖2。由于搬運機器人倉庫的環境為目前已知的一種結構化倉庫環境，環境中往往存在大量的工具如倉庫揀選臺、貨架、機器人等倉庫基礎設施，他們的工具數量多、形狀規范且能夠整齊有序的排列在了倉庫中。因此，首先使用了柵格法地圖來設計和構建一個基于菜鳥機器人的倉庫行走地圖，使多搬運機器人根據菜鳥的柵格地圖信息進行路徑的規劃，能夠達到最大限度地簡化機器人在菜鳥倉庫行走的地圖，并準確達到表示柵格地圖信息的路徑規劃目的。將一個智能搬運機器人的地圖和運動環境的地圖看做一個二維的平面時，則為運動環境的地圖Map，據菜鳥智能倉的調研數據顯示每格是1.5m*1.5m，所以每個柵格的邊長為1.5m*1.5m。柵格地圖X軸的坐標表示柵格的列，Y軸的坐標表示柵格的行，對柵格地圖中的每個柵格進行標號，每個柵格可以表示為點P，Pi的位置為Pi x,（ ）

y。

（2） 傳統A*算法。A*算法的啟發式估算函數表達式為：

其中：n表示柵格地圖中某一要被估算代價的節點，g（）

n則是指從某一起始點到該節點的真實代價，此代價主要為路程，h（n）則是指從柵格結點n移動到目標節點的啟發估算代價。h*（n）表示從柵格節點n移動到目標節點的真實最優代價，該代價在機器人到達目標節點之前可以估算范圍，不能計算準確的值。f（n）由g（n）和h（n）結合估算得到，表示從起始節點，經過柵格節點n后到達目標節點的啟發式估算代價。只有當h（n）≤h*（n）時，f（n）才能保證A*算法的完備性和最優性。通常情況下，選擇采用的啟發式估算函數因為不考慮其他環節因素，如障礙物等，均可以h（n）≤h*（n）的條件。

A*算法的啟發式估算函數在柵格地圖中有多重選擇，由于在智能倉庫環境結構固定，通過采用曼哈頓距離進行估算，能更接近搬運機器人可能行走的實際路程。在以下的表達式中，n表示柵格地圖中的某個柵格節點，nx表示節點n的x坐標，ny表示節點n的y坐標，同理，goal.x表示目標節點goal的x坐標，goal.y表示目標節點goal的y坐標，常用估算函數如下：

曼哈頓距離：

它表示為兩個節點之間在x軸和y軸方向的距離之和。

4 基于合作的多機器人協同路徑規劃

傳統的A*算法雖然能幫助搬運機器人在倉庫中找到一條距離最短的路徑，但是在實際情況中仍然還有很多問題，比如多機器人在同時運行會出現碰撞和死鎖等問題，下面將提出機器人的交通規則和預約表來解決這些問題，并進一步優化傳統的A*算法。

4.1 基于合作的交通規則

菜鳥智能倉庫中，多個搬運機器人在同一個貨架區域和揀選區域之間來回的穿梭，所以在他們共同行走的過程中難免會出現碰撞。這種碰撞通常分為以下三種情況：

a. 迎面碰撞：正面相遇碰撞的具體情況。

b. 交叉碰撞：搬運機器人在其行駛的整個過程中雖然沒有面對面的走，但是在拐角處仍然存在交叉碰撞相遇的情況。

c. 多個碰撞并存：當多個機器人同時在拐角處相遇時，迎面碰撞和交叉碰撞的情況將同時發生。

對于以上三種碰撞情況，交叉碰撞時機器人可以設置有優先級，由優先級低的機器人等待優先級高的機器人通過之后再通行，這種情況雖然很好解決，但是在遇到迎面碰撞和多種碰撞并存的情況時，就只有由一臺機器人避讓或者繞路，這樣在運行中可能就會出現不停的避讓和繞路的情況，使得機器人效率低下，行走更多不必要的路程。所以給倉庫中的道路規定為不同方向的單行道，這樣就可以很好地解決迎面碰撞和多種碰撞并存的情況。

本文將搬運機器人運行的倉庫環境設置如圖3 所示的交通規則，在貨架所在的通道設置成單向行駛的通道，橫向的則設置為向左向右交替行駛的單向通道，縱向的則設置為向上向下交替的單向行駛通道，然而在倉庫的最左邊是揀貨區，所以留出兩行供搬運機器人停靠。由于可能有多臺機器人服務于一個揀選臺，就有可能出現碰撞，所以我們規定所有的機器人到達揀選區域要遵循左邊進右邊出的規則，這樣就可以有效避免沖突。

4.2 基于合作的預約表

在采用上文的交通規則之后可以有效解決迎面碰撞和多種碰撞并存的情況，但是像圖4 所示的交叉碰撞并沒有很好的得到解決，所以本文將進一步提出預約表，對搬運機器人進行優先級的設定，通過識別優先級進行避讓，可以有效解決交叉碰撞的情況。除此之外，不同機器人可能還會有搬運同一貨架的取貨沖突，設定優先級還可以有效解決機器人的取貨沖突。

本文用柵格地圖對菜鳥智能倉進行簡化后，每一個柵格都表示一個節點，在預約表中每一個柵格都是一個時點，當一臺搬運機器人準備駛入這個節點時，先要占有這個節點，將此節點在預約表上的狀態改為占有，其它搬運機器人就不能再駛入該節點，只有等待其變為未被占有的狀態，才能通行。每一臺搬運機器人在駛入某一節點時都需要查詢預約表的狀態，只有查詢在未被占有的狀態下將該節點的狀態更改為占有才能順利通行。每一臺搬運機器人也有自己的ID，當它要占有某一個節點時，就將其自己的ID 輸入預約表的時點內，這樣在其它機器人查詢時就會知道該搬運機器人已經占有該時點，就會根據情況作出相應的調整，要么等待要么調整路徑重新作出規劃。

圖3 交通規則地圖

4.3 基于合作優化A*算法進行路徑規劃建模

根據上面制定的交通規則和預約表，將其相結合幾乎可以實現多搬運機器人完全無碰撞的運行。基于交通規則和預約表的運用和啟發，可以對傳統的A*算法做進一步的改進和優化，來提升多搬運機器人系統中單個搬運機器人的運行管理效率。

本文之前介紹了傳統的A*算法估算函數，通常情況下是用它來估算搬運機器人到達目標節點的距離代價，而在現實倉儲物流中，通常以完成一項任務的時間長短來評判一項作業的效率。因此，對傳統的A*算法進行改進，將采用時間代價作為估算函數估算的代價。將g（n）和h（n）的距離估算同時除以一個搬運機器人的行駛速度，轉化為時間估算代價g'（n）和h'（n）。其中g'（n）代表搬運機器人從起始柵格節點出發移動到當前柵格節點n所花費的真實時間代價：

其中：v表示搬運機器人取貨時的行駛速度，d表示搬運機器人從起始柵格移動到當前柵格n的真實距離。h'（n）表示搬運機器人從當前柵格n行走到目標柵格的估算時間代價：

其中：h（n）是上文所示的曼哈頓距離。

圖4 相同長度下的不同路徑

在傳統的A*算法下，從相同的起點出發到達相同的目標點，會產生三條長度相等的不同路徑，將其稱為路徑①、路徑②、路徑③，如圖4 所示。這三條路徑均滿足距離最短的條件，傳統的A*算法會選擇其中任意一條作為最佳路徑。在實際倉庫中機器人的轉彎也會帶來時間的消耗，選擇不同的路徑產生的時間代價也不同。選擇路徑①時則只有一次轉彎，選擇路徑②時會有三次轉彎，選擇路徑③時甚至會有四次轉彎。無疑轉彎次數越多，所消耗的時間越多。考慮到這一因素，將機器人轉彎的時間代價t也加入到算法中。當搬運機器人在柵格地圖中行走時，如果下一節點的方向和上一節點不一樣，即機器人將要進行轉彎，那么就需要將轉彎時間代價t考慮到估算函數f（n）中。此時將公式優化為：

其中：m表示搬運機器人在路徑規劃中轉彎的次數。

運用此方法不僅可以減少機器人的行駛距離，還可以很快找到一條時間最短的路徑，最快最準確地找到一條最高效率、最低成本的路徑規劃來完成揀貨作業。

5 方案的實施及評價

5.1 方案的實施

下面以菜鳥智能倉揀貨作業過程中的其中一個智能搬運機器人的行走路徑為例，用運改進后的A*算法對它重新進行路徑規劃，求出最優解，減少搬運時間，提高作業效率。

如圖5 菜鳥智能倉某一搬運機器人的行走路徑，可以看出它的行走路徑有重疊，有迂回。據調研顯示搬運機器人的行走速度是1.5m/s，轉一次彎大概花費0.5s。可得整個行走路徑長達115.5 米，耗時104 秒，總共轉彎5 次。

圖5 某一搬運機器人行走路徑

接下來運用改進后的A*算法，對搬運機器人重新進行路徑規劃，如圖6 基于改進后的A*算法路徑規劃，此時整個行走路徑長達108 米，耗時98 秒，總共轉彎3 次。

圖6 改進后的A*算法路徑規劃

用運改進后的A*算法，不僅可以解決搬運機器人行走路徑重疊，迂回的問題，配合交通規則和預約表可以解決機器人擁堵和避讓而繞路導致行走路徑過長的問題，考慮先走搬遠，后走搬近的原則減少等待時間。以上規劃從原來的總路徑長達115.5m 縮短至108m，總耗時由原來的104s 減少到98s，轉彎次數由原來的5 次減低到3 次，大大降低了總的消耗代價，詳情見表2 某一機器人路徑規劃數據對比。

5.2 方案的評價

（1） 搬運機器人購買成本計算。通過菜鳥智能倉的調研，搬運機器人數量為100 臺，根據實地調查一個智能搬運機器人的單價大概是10 萬元，所需要花費的購買費用是：購買總費用=單價*購買數量=10*100=1 000 萬元。

表2 某一機器人路徑規劃數據對比圖

（2） 電費成本計算。通過查詢智能搬運機器人的充電瓦數是1.8kw/h，充滿一次電需要2 小時，可連續使用6 小時，那么一天24 小時至少要充3 次電。廣州市商業用電的平均電費是0.617 元/度，則智能搬運機器人一年需要消耗的電費是：一年總電費=用電度數*用電時間*平均電費*臺數=1.8*6*365*0.617*100=24.32 萬元。

（3） 搬運機器人年折舊成本計算。年折舊率= （1-預計殘值率）/折舊年限×100%（注：預計殘值率為固定資產原值的3%～5%），根據調查與生產經營有關的工具計提折舊的最低年限為5 年，所以確定折舊年限為5 年，預計殘值率取原值的5%。所以一年的折舊費用是：年折舊費用=年折舊率*總價值=19%*1 000=190 萬元。

（4） 搬運機器人維護費成本計算。根據調查智能搬運機器人的電池使用壽命大概是兩年，更換一次電池的成本大概是11 000 元。為了對智能搬運機器人定期進行維護保養，至少三個月清掃一次灰塵和添加潤滑油，一次成本300 元左右，所以智能搬運機器人的一年維護費用是：年維護費用= （電池折舊+保養費）*機器人數量= （0.55+0.12 ）*100=67 萬元。

（5） 使用人工的成本計算。倉庫分揀人員的工資平均在4 500 元/月左右，每年的高溫補貼費、高峰期加班費和節假日福利一年大概在2 500 元/人左右，工作人員一般是工作八小時，進行三班倒。綜合以上使用人工的一年成本為：年人工成本=（基本工資+福利補貼） *工作人員數= （0.45*12+0.25 ）*300=1 695 萬元。

（6） 成本對比分析。使用機器人的年平均成本=折舊費+電費+維護費=190 萬元+24.32 萬元+67 萬元=281.32 萬元。

使用人工的年平均費用=總基本工資+總福利補貼=1 620 萬元+75 萬元=1 695 萬元。

根據以上公式分別計算出了菜鳥智能倉使用機器人的成本費用和使用人工的成本費用，機器人可以24 小時工作，人工需要三班倒，所以使用1 個機器人相當于雇傭3 個工作人員，從以上所述進行成本對比分析，可以看出使用機器人要比使用人工減少1 413.68 萬元的成本。

6 總 結

菜鳥聯盟憑借全面覆蓋的物流網點、高效的配送服務、先進的現代物流技術、專業的物流倉儲的服務和管理能力，在國內電商物流零售倉儲服務領域名列前茅。但其中還是存在著發展道路上的一些問題，還需要進一步的研究和創新加以解決。本文對菜鳥智能倉庫中的智能搬運機器人的路徑規劃相關問題進行了針對性的優化分析設計。目的主要是在當前傳統電商服務行業和現代工業自動化制造行業快速發展的背景和情況下，通過優化設計，來有效提高機器人服務的效率。結合菜鳥智能倉的實際情況，改進了傳統的A*算法，以時間代價作為優化的衡量標準，并考慮搬運機器人轉彎的時間代價t，實現為搬運機器人尋找一條最高效最準確的路徑。