工業(yè)移動機器人多機調(diào)度系統(tǒng)性能指標定義及性能優(yōu)化

張慧

（南京中興新軟件有限責任公司 江蘇省南京市 210012）

1 前言

AGV/AMR 是廣泛應用于倉儲和生產(chǎn)線進行智能搬運的移動機器人，是物流自動化升級的利器。通常，在一個項目中會存在多個AGV/AMR 同時運行，由調(diào)度系統(tǒng)進行協(xié)同調(diào)度管控。小型的多機協(xié)同項目，對調(diào)度系統(tǒng)的要求不是很高。但在大型多機協(xié)同項目中，尤其要求同時調(diào)度超過100臺，甚至1000 臺時，調(diào)度系統(tǒng)的性能就會成為一個瓶頸。由于不同的工作場景、任務類型差異很大，業(yè)界并沒有一個標準來定義調(diào)度系統(tǒng)性能指標。所以，本文分析調(diào)度系統(tǒng)性能影響因素、試圖建立一種標準的參考業(yè)務模型，在此模型下進行性能指標的計算和定義，并提出性能優(yōu)化的方法進行驗證。

因為自然導航方式的移動機器人AMR，較自動導引車AGV 的功能更加復雜，所以，下文以激光SLAM 導航的AMR 為例進行分析。

2 調(diào)度系統(tǒng)性能影響因素

2.1 移動機器人與調(diào)度系統(tǒng)的控制架構(gòu)

在實際應用場景中，會存在多臺移動機器人同時運行。但上位機MES 或WMS 等系統(tǒng)發(fā)布作業(yè)任務時，需要由調(diào)度系統(tǒng)來完成多臺機器人之間的協(xié)同，進行任務分配、路徑規(guī)劃以及交通沖突的預防和解決。如圖1 所示，移動機器人和調(diào)度系統(tǒng)之間有集中式和分布式兩種控制架構(gòu)。集中式那就是有一個統(tǒng)一的調(diào)度系統(tǒng)來完成調(diào)度工作，分布式調(diào)度是一種更自主式更靈活的調(diào)度方式。當前集中式的調(diào)度系統(tǒng)占絕大多數(shù)，分布式調(diào)度對算法、計算資源、通信都有較高的要求，目前還不成熟。所以，本文以集中式調(diào)度系統(tǒng)為研究內(nèi)容。

圖1： 機器人與調(diào)度系統(tǒng)之間的控制架構(gòu)

2.2 調(diào)度系統(tǒng)的組成及性能影響分析

調(diào)度系統(tǒng)包括一些地圖管理、車輛/站點配置、任務查看、統(tǒng)計分析等非實時業(yè)務功能，但是影響性能指標的主要是實時性要求高和多并發(fā)的調(diào)度任務。

一次調(diào)度任務主要包括如圖2 幾個部分：

圖2： 調(diào)度任務流程

（1）任務分配：收到MES 等外部調(diào)度任務時，需要按照任務分配策略進行分配。分配策略可以有很多種，目前比較常用的策略是，先要尋找空閑的AMR，如果有多個，需要在其中計算出一個離目的地最近的AMR；如果沒有空閑的AMR，進入任務等待列表，并不斷掃描未執(zhí)行任務列表。這個過程，如果空閑的很少，有空閑的就被分配了任務，那沒有太多耗CPU 資源的操作。如果空閑的較多，則與下述路徑規(guī)劃中最短路徑的計算相關。

（2）路徑規(guī)劃：這個過程對CPU 資源消耗較大。AMR通過激光SLAM 形成地圖，并在地圖中已規(guī)劃好的可行駛線路圖，包括節(jié)點和線段，并指定了線路的方向。對于任務起始A、B 點之間有多條路徑，系統(tǒng)需要比較每條路徑的最優(yōu)化選擇。如果AB 兩點之間越長，線路節(jié)點(交叉點，以及長線段中的中間節(jié)點）越多，計算就會越復雜。最極端情況，與2（n 為節(jié)點個數(shù)）成正比。

（3）交通管制：AMR 運行過程中，每隔一個時間間隔（各廠家有不同，幾十到幾百毫秒）上報給調(diào)度系統(tǒng)當前位置和行駛方向。調(diào)度系統(tǒng)后計算這輛車和其他AMR 的距離，判斷是否有碰撞風險。最極端情況，需要N*C(N,2)次計算（N為AMR 的臺數(shù)）。

綜上，影響調(diào)度任務性能的客觀因素是任務頻次、地圖規(guī)劃線路的交叉點及節(jié)點數(shù)以及AMR 個數(shù)，主觀因素就是算法本身的合理性。

3 調(diào)度系統(tǒng)性能指標定義

3.1 模型的考慮

從上述分析可以看出，每個項目中的地理空間大小、路徑多少、任務的頻次、AMR 個數(shù)的不同，調(diào)度系統(tǒng)呈現(xiàn)出來的性能表現(xiàn)將會不同。但我們?nèi)匀恍枰幸粋€客觀的指標來表征調(diào)度系統(tǒng)的性能，所以，我們需要在一個標準的“業(yè)務模型”下測試并表征出我們調(diào)度系統(tǒng)的性能。

“業(yè)務模型”的抽取盡可能是影響因素相互正交。我們可以看出：

Performance ∝ Efficiency CPU ∝ F& N& Duration& N

性能Performance 越高，CPU 效率越高，完成任務數(shù)F、通過的節(jié)點數(shù)N、能執(zhí)行任務時長Duration 越多。因為路徑的節(jié)點數(shù)N、單任務執(zhí)行時長Duration，客戶是不可能在實施前告知，但客戶是能告知業(yè)務執(zhí)行的節(jié)拍，即調(diào)度任務的頻次F和工作區(qū)域的面積Area 的。

∵ N、N∝ Area

∵ Duration ∝ Area

∴ 當F、Area 確定時，Performance ∝ N，即調(diào)度系統(tǒng)的性能可以用同時支持的AMR 數(shù)來表征。

3.2 標準模型的設定

Area 的模型，我們可以參照一些項目，折算N800個貨架/10000m，則折算系統(tǒng)的節(jié)點數(shù)N按1000 計算。（單位面積中貨架數(shù)可以根據(jù)部署的合理性進行調(diào)整）

F，正常情況下應是客戶給定。但在上述10000m的假設條件下，我們可以估算一個調(diào)度任務的節(jié)拍。

10000m空間，長100m*寬100m，

考慮到站點位之間距離最長390m，最短10m，接任務先從停車場或充電區(qū)或途中到任務起始點。則推算單任務平均運行距離S=（390+10）/2+40=240m；

平均速度是1.2m/s，加上對接貨架2 次，每次20s，另外需要考慮充電時間影響的效率因素。充電2 小時，跑6 小時，效率為0.75。則單任務時間

Duration= （240/1.2+2*20s）/ 0.75 =240s/ 0.75 =320s

按前期討論10000 平米，合理AMR 數(shù)不超過50 臺。則

Ftask = 3600s/(320s/50)=562.5 次/h ≈560 次/h

綜上，我們可以按10000 平米，800 個貨架，每小時560 次調(diào)度任務為一個標準模型。

3.3 性能指標

在這個標準“業(yè)務模型”下，我們的性能指標就可以AMR 個數(shù)來表征。我們需要測試出單個業(yè)務單AMR 的CPU 占用。對應到相應的F、N、Duration 下每AMR的CPU、CPU、CPU。計算出系統(tǒng)能支持的最大AMR 數(shù)，這就是對應到標準業(yè)務模型下的性能指標。這個不同實現(xiàn)方式的不同廠家可以在同一基線上進行比較了。

對于具體的項目而言，也可以更快地計算出調(diào)度系統(tǒng)的硬件資源的需求和進行合理規(guī)劃。比如，可以根據(jù)和標準模型之間的折算，計算出合理配置的AMR 個數(shù)。若超過系統(tǒng)的性能極限，就需要想辦法劃分區(qū)域、分多個調(diào)度系統(tǒng)等的規(guī)劃。

4 性能優(yōu)化分析

4.1 路徑規(guī)劃

以最常用A*算法為例。A*算法是在加權(quán)圖的最小路徑計算中最常用的經(jīng)典圖搜索算法之一。該算法采用加權(quán)圖的形式，包括節(jié)點和節(jié)點之間的線段，包含節(jié)點間線段的開銷、權(quán)重。該算法從初始起始節(jié)點開始，逐級訪問評估下一個相鄰節(jié)點來完成整個路徑規(guī)劃。

可以考慮的在基礎算法上進行的優(yōu)化：

4.1.1 靜態(tài)路徑表

（1）固定站點之間的路徑，可以通過事先配置形成路徑表，程序啟動時，讀到內(nèi)存中，供每次路徑規(guī)劃直接查詢使用；

（2）非固定路徑，如AMR 在完成任務后回停車場途中接受到任務，可以分區(qū)設定虛擬固定站點，分段計算和查詢路徑表。

4.1.2 全局規(guī)劃與局部規(guī)劃結(jié)合

以一個實際工業(yè)應用中的地圖為例，如圖3。

圖3： 地圖示例

（1）主干道、干線交通由調(diào)度系統(tǒng)集中規(guī)劃；

（2）由AMR 自主路徑規(guī)劃支路上的路由。尤其在倉儲庫位、停車場區(qū)域，節(jié)點密集，交叉點多，易發(fā)生交通沖突。結(jié)合分布式交通管制（下一節(jié)描述），自主式避障，繞障的局部規(guī)劃，更適合由AMR 來完成。

①局部路由區(qū)域，可以實現(xiàn)定義。區(qū)域的路徑表，也可以配置成靜態(tài)內(nèi)存表。正常情況下，按路徑表中選擇路徑。

②增強AMR 的感知能力（可考慮增加接近傳感器），自主感知交通沖突。等發(fā)生交通沖突后，AMR 自行進行局部路徑規(guī)劃，可以停止等待，可以進行局部繞障路徑規(guī)劃?？梢圆捎肰FH 算法（以AMR 為視角的障礙物密度進行方向選擇）進行繞障。

通行優(yōu)先級可按一定交通規(guī)則，如東西向讓行南北向，先至交叉口者優(yōu)先等原則；在雙向道路上相向沖突，制定如北向繞道讓南向AMR 等原則；或者設置全局各AMR 的優(yōu)先級等等規(guī)則。

AMR 自己進行停障或繞障（推薦），繞障方式可以減少等待時間，讓整體效率更高。

4.2 交通管制

交通管制是為了防止發(fā)生AMR 之間的交通沖突，如果全局計算AMR兩兩之間的交通沖突，會非常消耗資源。所以，可以考慮多種算法的優(yōu)化：

4.2.1 縮小到?jīng)_突區(qū)檢測

劃分不同的沖突區(qū)，將可能出現(xiàn)沖突的交叉口周圍畫成沖突區(qū)，不在同一沖突區(qū)范圍內(nèi)或不在沖突可能范圍的AMR 就不需要計算。

4.2.2 局部閉鎖

在節(jié)點密集的庫位、停車場等區(qū)域，進行局部閉鎖的方式。以圖4 某項目中的停車區(qū)為例。停車場有P1 到P14，14 個停車位，當需要同時出來的時候，就會相互鎖死。

圖4： 停車場站點示意圖

我們可以嘗試一下高鐵和地鐵的閉鎖方式。將停車場這個區(qū)域設為閉鎖聯(lián)動區(qū)。假設當P6 的AMR 要出庫，就請求將S6、S5、S4、S3 閉塞，當沒有更高優(yōu)先級的AMR 同時申請，則調(diào)度系統(tǒng)確認閉塞。調(diào)度系統(tǒng)若收到有該區(qū)域的AMR 上報位置信息，即通知閉鎖區(qū)域。假設此時有P4 的AMR 要出庫，判斷路徑規(guī)劃中有S4、S3 被閉塞，則等待閉塞取消。這樣做的好處是，當有多臺同時出入時，調(diào)度系統(tǒng)只需廣播閉塞信息，由AMR 自行計算是否停止等待。

4.2.3 分布式管制

同上一節(jié)。增強AMR 的感知能力（可考慮增加接近傳感器），自主感知交通沖突。等發(fā)生交通沖突后，AMR 自行進行局部路徑規(guī)劃，可以停止等待，可以進行局部繞障路徑規(guī)劃?？梢圆捎肰FH 算法（以AMR 為視角的障礙物密度進行方向選擇）進行繞障。

5 實驗及總結(jié)

總結(jié)第4 章表述的優(yōu)化方法如表1。

表1：

為了測試這些優(yōu)化手段的效果，按3.2 設定的標準模型，對以上功能進行對比試驗。局部繞障和局部閉鎖功能觸發(fā)條件有限，占總CPU 消耗的比例較小。所以，也沒有進行具體的對比。其他幾項對比結(jié)果（在標準模型）下，單項改進對CPU 消耗的對比，如表2。

表2：

綜上，通過對影響多機調(diào)度性能的因素的分析，建立了一個標準化業(yè)務模型和性能指標表征方法。并通過優(yōu)化算法，計算調(diào)度性能進行對比，驗證了模型的可用性。