張慧

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

1 前言

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

因?yàn)樽匀粚?dǎo)航方式的移動(dòng)機(jī)器人AMR，較自動(dòng)導(dǎo)引車AGV 的功能更加復(fù)雜，所以，下文以激光SLAM 導(dǎo)航的AMR 為例進(jìn)行分析。

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 模型的考慮

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

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

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

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

∵ N、N∝ Area

∵ Duration ∝ Area

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

3.2 標(biāo)準(zhǔn)模型的設(shè)定

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

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

10000m空間，長(zhǎng)100m*寬100m，

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

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

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

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

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

綜上，我們可以按10000 平米，800 個(gè)貨架，每小時(shí)560 次調(diào)度任務(wù)為一個(gè)標(biāo)準(zhǔn)模型。

3.3 性能指標(biāo)

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

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

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

4.1 路徑規(guī)劃

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

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

4.1.1 靜態(tài)路徑表

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

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

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

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

圖3： 地圖示例

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

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

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

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

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

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

4.2 交通管制

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

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

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

4.2.2 局部閉鎖

在節(jié)點(diǎn)密集的庫位、停車場(chǎng)等區(qū)域，進(jìn)行局部閉鎖的方式。以圖4 某項(xiàng)目中的停車區(qū)為例。停車場(chǎng)有P1 到P14，14 個(gè)停車位，當(dāng)需要同時(shí)出來的時(shí)候，就會(huì)相互鎖死。

圖4： 停車場(chǎng)站點(diǎn)示意圖

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

4.2.3 分布式管制

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

5 實(shí)驗(yàn)及總結(jié)

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

表1：

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

表2：

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