一、概述
1.1 名詞介紹
（1）AGV：Automated Guided Vehicle，自動(dòng)導(dǎo)引車，是一類輪式移動(dòng)機(jī)器人，沿著地板上的磁條、標(biāo)記塊，或者通過視覺導(dǎo)航或激光導(dǎo)航進(jìn)行運(yùn)動(dòng)。
（2）揀選：倉(cāng)儲(chǔ)配送中心的配貨人員按訂單要求的商品名，規(guī)格，型號(hào)，數(shù)量，將商品從存儲(chǔ)的貨架或貨垛中取出。
（3）分揀：揀選作業(yè)完成后，將揀選出的商品按照不同的客戶，不同的配送路線進(jìn)行分類，集中等待裝車配載，送貨作業(yè)的流程。
（4）運(yùn)力組：用于完成特定任務(wù)的一組運(yùn)力資源的集合。
（5）移庫(kù)：由于業(yè)務(wù)需要，將倉(cāng)內(nèi)物料移動(dòng)至同一邏輯區(qū)下的另一個(gè)位置。
（6）容器：用于存放商品的器具，常見容器包括料箱、中轉(zhuǎn)箱、托盤等。
（7）托盤搬運(yùn)AGV：Pallet Shuttle,一種搬運(yùn)托盤的AGV。
（8）料箱機(jī)器人：一種可同時(shí)搬運(yùn)多個(gè)料箱的機(jī)器人。
（9）出口：用于存放同一訂單或同一目的地對(duì)應(yīng)商品的虛擬格口。
（10）疊托：當(dāng)托盤被撿空后，將多個(gè)托盤疊在一起，便于回收及存儲(chǔ)。
1.2 概述
本文主要介紹倉(cāng)內(nèi)智能機(jī)器人任務(wù)的分發(fā)及執(zhí)行的相關(guān)內(nèi)容。任務(wù)分發(fā)，顧名思義，針對(duì)當(dāng)前待執(zhí)行的一批任務(wù)(倉(cāng)內(nèi)場(chǎng)景常見任務(wù)包括搬運(yùn)任務(wù)及泊車任務(wù)），為其分配可用的AGV資源，即倉(cāng)內(nèi)不同場(chǎng)景下的任務(wù)需求與可用搬運(yùn)機(jī)器人資源的匹配。AGV資源是執(zhí)行任務(wù)的運(yùn)力資源，因此任務(wù)分發(fā)又叫做運(yùn)力分配。一個(gè)簡(jiǎn)單的示例如下圖1所示。
一個(gè)優(yōu)秀的任務(wù)分發(fā)系統(tǒng)，可以充分調(diào)動(dòng)機(jī)器人資源，并在運(yùn)行時(shí)間、距離等方面全局或局部最優(yōu)，從而達(dá)到效率最高。本文對(duì)現(xiàn)有機(jī)器人常見的兩大類任務(wù)，即搬運(yùn)任務(wù)和泊車任務(wù)，進(jìn)行具體討論，探討搬運(yùn)任務(wù)中的任務(wù)分配模式和執(zhí)行策略以及泊車任務(wù)中的泊車點(diǎn)選擇等內(nèi)容。
二、背景介紹
隨著機(jī)器人技術(shù)的不斷發(fā)展、企業(yè)數(shù)字化和自動(dòng)化程度的不斷提升，越來越多的機(jī)器人逐漸進(jìn)入倉(cāng)儲(chǔ)和生產(chǎn)相關(guān)領(lǐng)域各環(huán)節(jié)作業(yè)場(chǎng)景中。雖然機(jī)器人形式多樣并且應(yīng)用的作業(yè)環(huán)節(jié)或者作業(yè)模式各有不同，但是所執(zhí)行的基本操作或者所實(shí)現(xiàn)的基本功能卻有共性，即完成搬運(yùn)功能并在任務(wù)完成后選擇合適地點(diǎn)泊車等待后續(xù)任務(wù)。
機(jī)器人搬運(yùn)任務(wù)可以抽象為將需搬運(yùn)目標(biāo)(比如托盤、貨架、料箱和商品等)從起始點(diǎn)(比如儲(chǔ)位、提升機(jī)接駁點(diǎn)、上包臺(tái)和貨架揀選處等)搬運(yùn)至目的點(diǎn)(比如揀選工作站、分揀口和復(fù)核打包工作站等)，泊車任務(wù)即機(jī)器人完成任務(wù)后選擇合適泊車點(diǎn)等待，從而能夠快速響應(yīng)之后任務(wù)，提高作業(yè)效率。
三、搬運(yùn)任務(wù)分發(fā)
3.1搬運(yùn)任務(wù)分發(fā)
當(dāng)前倉(cāng)儲(chǔ)和生產(chǎn)制造等領(lǐng)域，地面機(jī)器人主要實(shí)現(xiàn)的核心功能之一就是對(duì)物品或者容器的搬運(yùn)。一條搬運(yùn)任務(wù)的要素主要包括：機(jī)器人、搬運(yùn)目標(biāo)、起始點(diǎn)、中轉(zhuǎn)點(diǎn)、目的點(diǎn)和行駛路線，其中：
（1）機(jī)器人：搬運(yùn)任務(wù)的具體執(zhí)行載體。
（2）搬運(yùn)目標(biāo)：機(jī)器人要搬運(yùn)的實(shí)體，在不同場(chǎng)景下其具體表現(xiàn)形式不唯一。比如，在貨到人系統(tǒng)中搬運(yùn)目標(biāo)主要是多層貨架或者托盤；在分揀場(chǎng)景下主要是待分撥的包裹；而在揀選支持系統(tǒng)中則是人工揀選出的貨品。
（3）起始點(diǎn)：機(jī)器人開始執(zhí)行任務(wù)的所在點(diǎn)，比如泊車點(diǎn)或者工作站等。
（4）中轉(zhuǎn)點(diǎn)：搬運(yùn)任務(wù)下必經(jīng)的關(guān)鍵節(jié)點(diǎn)，而非行駛路徑上的一般節(jié)點(diǎn)。這里的中轉(zhuǎn)點(diǎn)往往是有業(yè)務(wù)相關(guān)的節(jié)點(diǎn)。比如，貨到人機(jī)器人系統(tǒng)下的貨架存放點(diǎn)，也就是儲(chǔ)位點(diǎn)，機(jī)器人從初始點(diǎn)出發(fā)前往儲(chǔ)位點(diǎn)搬取貨架之后送到工作站；在揀選支持機(jī)器人系統(tǒng)中則是一系列揀選點(diǎn)，機(jī)器人需要經(jīng)停并揀選或者搬運(yùn)由人工揀選出的貨品。
（5）目的點(diǎn)：搬運(yùn)目標(biāo)最終需要到達(dá)的地方，比如工作站或者分揀隔口等。
（6）行駛路徑：依據(jù)路網(wǎng)連通性和道路擁堵情況等因素規(guī)劃出的機(jī)器人行走路徑。
每一條任務(wù)包含一個(gè)機(jī)器人和對(duì)應(yīng)的一個(gè)搬運(yùn)目標(biāo)，機(jī)器人從一個(gè)起始點(diǎn)出發(fā)，可以經(jīng)過一個(gè)或多個(gè)中轉(zhuǎn)點(diǎn)到達(dá)一個(gè)或多個(gè)目的點(diǎn)。對(duì)于入庫(kù)上架和回庫(kù)任務(wù)，在庫(kù)存系統(tǒng)對(duì)貨架和儲(chǔ)位進(jìn)行了選擇。經(jīng)過庫(kù)存系統(tǒng)和訂單批處理系統(tǒng)處理，搬運(yùn)任務(wù)中的搬運(yùn)目標(biāo)、中轉(zhuǎn)點(diǎn)和目的點(diǎn)均已經(jīng)確定。
3.2任務(wù)約束及優(yōu)先級(jí)
3.2.1 任務(wù)約束
搬運(yùn)任務(wù)的任務(wù)分發(fā)系統(tǒng)分為兩層，分別為上層的業(yè)務(wù)約束定義和底層的核心匹配算法。業(yè)務(wù)約束涉及大量不同場(chǎng)景，需要滿足不同業(yè)務(wù)要求，較為復(fù)雜。
舉例說明，在執(zhí)行任務(wù)分發(fā)時(shí)，待做任務(wù)可能是不同類型的，有的任務(wù)更緊急，優(yōu)先級(jí)更高，需要先做；有的任務(wù)等待成本較高，因此需要為其時(shí)刻預(yù)留一定的運(yùn)力，保證當(dāng)該類任務(wù)下發(fā)時(shí)，可以立即分配運(yùn)力進(jìn)行搬運(yùn)；閑置AGV可能存在不同類型，有的類型的AGV只能執(zhí)行特定類型的任務(wù)。
由于業(yè)務(wù)要求的復(fù)雜性，對(duì)業(yè)務(wù)進(jìn)行分層、細(xì)致的梳理，是對(duì)倉(cāng)內(nèi)搬運(yùn)任務(wù)進(jìn)行提效的重點(diǎn)。
3.2.2 任務(wù)優(yōu)先級(jí)
不同任務(wù)的優(yōu)先級(jí)不同，具體可用以下指標(biāo)衡量：
（1）任務(wù)下發(fā)/截止時(shí)間：在當(dāng)前非空任務(wù)池中，不同任務(wù)存在不同的下發(fā)時(shí)間或截至?xí)r間，一般來說優(yōu)先考慮截止時(shí)間，越早優(yōu)先級(jí)越高。
（2）任務(wù)類型：任務(wù)按照類型劃分，包含托盤入庫(kù)、托盤出庫(kù)、空托回庫(kù)、疊托移庫(kù)、料箱入庫(kù)、料箱出庫(kù)、物料投送及物料駁接等。
（3）排隊(duì)狀況：以料箱機(jī)器人入庫(kù)任務(wù)為例，某個(gè)工作站可能積壓了大量任務(wù)需要料箱機(jī)器人來搬運(yùn)，因此該工作站任務(wù)的優(yōu)先級(jí)高于其他工作站。
3.2.3優(yōu)先級(jí)評(píng)分機(jī)制
對(duì)于每一個(gè)任務(wù)，都可以根據(jù)其指標(biāo)屬性給出一個(gè)綜合打分，來評(píng)價(jià)其優(yōu)先程度；分?jǐn)?shù)越低，優(yōu)先級(jí)越高。
對(duì)于單個(gè)指標(biāo)，限定每個(gè)任務(wù)對(duì)應(yīng)分?jǐn)?shù)在0-1之間，且可配置。比如配置入庫(kù)任務(wù)分?jǐn)?shù)0.5，出庫(kù)任務(wù)分?jǐn)?shù)0.8，則代表出庫(kù)任務(wù)先于入庫(kù)任務(wù)。
不同指標(biāo)同樣存在優(yōu)先考慮順序，一種簡(jiǎn)單的方法是為不同指標(biāo)的評(píng)分乘以一個(gè)具有顯著區(qū)分度的權(quán)重，得到每個(gè)任務(wù)加權(quán)后的綜合分?jǐn)?shù)，如下圖2所示。
3.2.4 任務(wù)依賴
不同任務(wù)可能存在任務(wù)依賴，例如托盤搬運(yùn)AGV人工區(qū)出庫(kù)，當(dāng)前工作站需要在上一個(gè)任務(wù)完成并移走托盤后，才能執(zhí)行下一個(gè)出庫(kù)搬運(yùn)任務(wù)。因此出庫(kù)搬運(yùn)任務(wù)依賴于對(duì)應(yīng)工作站的托盤回庫(kù)或空托回收任務(wù)。因此對(duì)于已根據(jù)優(yōu)先級(jí)生成的任務(wù)隊(duì)列，對(duì)于每一個(gè)存在依賴的任務(wù)，需要在該任務(wù)前插相應(yīng)依賴任務(wù)。
不同任務(wù)可能存在任務(wù)依賴，例如托盤搬運(yùn)AGV人工區(qū)出庫(kù)，當(dāng)前工作站需要在上一個(gè)任務(wù)完成并移走托盤后，才能執(zhí)行下一個(gè)出庫(kù)搬運(yùn)任務(wù)。因此出庫(kù)搬運(yùn)任務(wù)依賴于對(duì)應(yīng)工作站的托盤回庫(kù)或空托回收任務(wù)。因此對(duì)于已根據(jù)優(yōu)先級(jí)生成的任務(wù)隊(duì)列，對(duì)于每一個(gè)存在依賴的任務(wù)，需要在該任務(wù)前插相應(yīng)依賴任務(wù)。
一般來說，不同任務(wù)類型存在優(yōu)先級(jí)，或者相互依賴關(guān)系，例如托盤搬運(yùn)AGV區(qū)出庫(kù)托盤拆空后，需要先將空托盤搬走，否則下一個(gè)綁定在該站點(diǎn)的入庫(kù)任務(wù)無(wú)法執(zhí)行。而疊托移庫(kù)任務(wù)需要先于空托回庫(kù)執(zhí)行，否則疊托占用疊托機(jī)，導(dǎo)致空托回庫(kù)任務(wù)無(wú)法執(zhí)行。
3.2.5 運(yùn)力配比
以托盤搬運(yùn)AGV區(qū)為例，雖然出庫(kù)任務(wù)優(yōu)先級(jí)更高，但如果出庫(kù)任務(wù)較多，可能導(dǎo)致所有AGV全部執(zhí)行出庫(kù)搬運(yùn)任務(wù)，造成入庫(kù)托盤在接駁點(diǎn)積壓，因此需預(yù)留一定配比的AGV運(yùn)力只為或優(yōu)先為入庫(kù)任務(wù)服務(wù)。
3.2.6容量限制
由于起始點(diǎn)、目的地或行駛區(qū)域的物理容量限制，需要對(duì)同一時(shí)間到達(dá)相應(yīng)地點(diǎn)的AGV或搬運(yùn)容器實(shí)施容量限制，例如短時(shí)間內(nèi)目的站點(diǎn)可容納容器數(shù)、巷道可駛?cè)?/span>AGV數(shù)等。該限制條件可根據(jù)具體業(yè)務(wù)場(chǎng)景靈活配置。
3.2.7 AGV約束
可執(zhí)行任務(wù)類型限制劃分運(yùn)力組后，每個(gè)AGV只能執(zhí)行特定類型任務(wù)。
AGV優(yōu)先級(jí)劃分常見料箱機(jī)器人場(chǎng)景，例如同一巷道內(nèi)的任務(wù)優(yōu)先分給已被分配該巷道任務(wù)的AGV，出入庫(kù)任務(wù)優(yōu)先分配正在前往相應(yīng)工作站的AGV。
3.3 核心匹配算法
基于任務(wù)選車或基于車選任務(wù)是兩種不同的方式。一般來說，某個(gè)任務(wù)長(zhǎng)期無(wú)法執(zhí)行，比如某輛AGV長(zhǎng)期閑置更加嚴(yán)重，因此基于任務(wù)選車是一種更合適的方式。
核心匹配算法主要涉及到任務(wù)和AGV兩個(gè)主體部分。一般來說，根據(jù)某一時(shí)刻機(jī)器人可掛載的最多任務(wù)數(shù)量可以分為兩種模式：
（1）單一任務(wù)模式
在單一任務(wù)模式下，機(jī)器人一次只能執(zhí)行一個(gè)任務(wù)，在完成當(dāng)前任務(wù)后才可以領(lǐng)取執(zhí)行下一任務(wù)。
（2）任務(wù)隊(duì)列模式
對(duì)于任務(wù)隊(duì)列模式，機(jī)器人可以一次分配多個(gè)任務(wù)，根據(jù)場(chǎng)景不同可以按照一定順序或者同時(shí)執(zhí)行。
根據(jù)任務(wù)分發(fā)模型中的兩方(即AGV和搬運(yùn)任務(wù))數(shù)量的多少，可采用多對(duì)多輪詢模型。
在新任務(wù)生成時(shí)從多個(gè)可選機(jī)器人中選擇最為合適的一個(gè)執(zhí)行任務(wù)。如何從可選機(jī)器人中選擇最合適的那一個(gè)，是整個(gè)策略的核心。一般來說，有如下原則：
① 最近原則
② 最長(zhǎng)閑置原則
③ 最少空駛時(shí)間/距離原則
對(duì)于當(dāng)前待執(zhí)行任務(wù)池（任務(wù)間無(wú)優(yōu)先級(jí)），依次對(duì)每個(gè)任務(wù)執(zhí)行以上選取原則，為每個(gè)任務(wù)匹配一個(gè)最優(yōu)AGV，然后按照成本從低到高選取個(gè)數(shù)不超過AGV數(shù)量與任務(wù)數(shù)量最大者的配對(duì)，作為分配結(jié)果。
對(duì)于當(dāng)前可用AGV資源池，依次對(duì)每個(gè)AGV執(zhí)行以上選取原則，為每個(gè)AGV匹配一個(gè)最優(yōu)任務(wù)，然后按照成本從低到高選取個(gè)數(shù)不超過可用AGV數(shù)量與任務(wù)數(shù)量最大者的配對(duì)，作為分配結(jié)果。
3.4 搬運(yùn)成本
一般來說，搬運(yùn)任務(wù)的起終點(diǎn)在下發(fā)任務(wù)時(shí)就已確定，因此某個(gè)指定運(yùn)力執(zhí)行某個(gè)指定搬運(yùn)任務(wù)的成本可以明確地定義。常見的定義方式包括搬運(yùn)距離、搬運(yùn)時(shí)間。
考慮到倉(cāng)內(nèi)AGV的行駛方向一般為二維平面的水平、垂直兩個(gè)正交方向，常用路徑自動(dòng)規(guī)劃算法計(jì)算，自動(dòng)計(jì)算AGV→任務(wù)起點(diǎn)→任務(wù)終點(diǎn)的最短路徑的完整距離，如下圖3所示的曼哈頓距離。
該方法尤其適用于路網(wǎng)中存在單向路的情形。考慮到實(shí)時(shí)計(jì)算成本較高，可將地圖中所有完整路徑的距離存儲(chǔ)下來，直接查詢即可。
在考慮路線擁堵的情況下，可根據(jù)地圖熱點(diǎn)信息為每條邊定義不同成本。搬運(yùn)距離和搬運(yùn)時(shí)間可以相互轉(zhuǎn)化。例如對(duì)于完整路徑內(nèi)的每一段直線路徑，可根據(jù)AGV的加速度信息，求出基于速度規(guī)劃的行駛時(shí)間，并為每個(gè)轉(zhuǎn)彎行為加入轉(zhuǎn)彎時(shí)間。
3.5 任務(wù)執(zhí)行
對(duì)于以掛載任務(wù)隊(duì)列或多中轉(zhuǎn)點(diǎn)任務(wù)的情形，為使機(jī)器人可以執(zhí)行任務(wù)，還需要確定任務(wù)涉及的順序問題。
（1）如果存在多個(gè)中轉(zhuǎn)點(diǎn)或者目的點(diǎn)，需要確定他們之間到達(dá)服務(wù)順序。
（2）如果采用任務(wù)隊(duì)列模式，需要確定多任務(wù)之間的執(zhí)行順序。
確定執(zhí)行順序在不同場(chǎng)景下方式不盡相同，主要考慮因素包括任務(wù)拆分、距離、加工配合及交通管制等多個(gè)因素。
每個(gè)機(jī)器需要指派一個(gè)或多個(gè)搬運(yùn)任務(wù),并且需要確定每個(gè)機(jī)器人分別需要搬運(yùn)的貨架以及搬運(yùn)順序,使得所有機(jī)器人總搬運(yùn)距離最短或者使得所有任務(wù)的完成時(shí)間最短。
3.6 評(píng)價(jià)及靈敏度分析
任務(wù)分配和執(zhí)行的策略會(huì)依據(jù)不同場(chǎng)景不同需求而有所不同，而在同一場(chǎng)景下面對(duì)同樣的業(yè)務(wù)需求，通常也會(huì)有多種不同的調(diào)度策略可供選擇，即便同一種策略也會(huì)因?yàn)椴煌膬?nèi)置參數(shù)選擇而產(chǎn)生不同表現(xiàn)，現(xiàn)實(shí)中通常很難完全確定某一單一環(huán)節(jié)如何影響整體系統(tǒng)生產(chǎn)效率，可用若干用于評(píng)價(jià)調(diào)度策略性能的統(tǒng)計(jì)量，其中包括：
（1）訂單生產(chǎn)效率：—定時(shí)間內(nèi)生產(chǎn)完成訂單數(shù)量與接受訂單數(shù)量的比例。
（2）響應(yīng)時(shí)間：任務(wù)等待機(jī)器人執(zhí)行的時(shí)間與機(jī)器人空駛時(shí)間之和。
（3）生產(chǎn)時(shí)間：訂單在系統(tǒng)中生產(chǎn)的時(shí)間。
（4）機(jī)器人平均利用率：機(jī)器人執(zhí)行任務(wù)的時(shí)間(包括空駛和滿載時(shí)間與總時(shí)間的比值)。
四、泊車任務(wù)調(diào)度
當(dāng)機(jī)器人完成前一個(gè)任務(wù)后，如果沒有后續(xù)任務(wù)也無(wú)需進(jìn)行充電的情況下，通常需要執(zhí)行泊車任務(wù)。
泊車任務(wù)是指空閑機(jī)器人前往選擇的?？奎c(diǎn)進(jìn)行等待直到分配下一任務(wù)，?？奎c(diǎn)的選擇需要考慮距離和其它機(jī)器人位置等因素，在不影響其它工作機(jī)器人作業(yè)的情況下，選擇合適的泊車點(diǎn)可以提高機(jī)器人系統(tǒng)對(duì)新任務(wù)的響應(yīng)速度從而提高整體作業(yè)效率。對(duì)于AMR/AGV系統(tǒng)，常見的泊車情形包括：
（1）前往預(yù)先規(guī)劃的指定停車地點(diǎn)泊車；
（2）在規(guī)劃的路徑上巡行直到有新任務(wù)指派；
（3）在上一任務(wù)完成地點(diǎn)等待。
現(xiàn)實(shí)場(chǎng)景下，空閑機(jī)器人泊車任務(wù)調(diào)度主要包括首先選擇合適的泊車位，在前往泊車點(diǎn)和在泊車點(diǎn)等待的過程中可以隨時(shí)終止泊車任務(wù)去執(zhí)行新的搬運(yùn)任務(wù)。
生成泊車位的整體選擇過程可宏觀上分為兩個(gè)步驟，首先需要確定可選泊車位范圍，可能在一些場(chǎng)景下在規(guī)劃之初已經(jīng)設(shè)計(jì)了若干固定的泊車位置，而空閑機(jī)器人只能在這些泊車位中選擇當(dāng)前未被其它機(jī)器人占用的位置進(jìn)行泊車；而在另外一些場(chǎng)景下,沒有固定的泊車位置，機(jī)器人可以選擇任何可選位置(不可選位置包括造成路線堵塞的點(diǎn)等)進(jìn)行泊車。
其次，需要根據(jù)距離和其它空閑機(jī)器人泊車位置選擇本次具體泊車位。其中距離因素考慮盡量選擇下一任務(wù)可能發(fā)生區(qū)域的位置從而降低移動(dòng)距離提高響應(yīng)速度，同時(shí)也需考慮其它空閑機(jī)器人泊車位置，平衡各區(qū)域機(jī)器人分布密度，避免特定區(qū)域空閑機(jī)器人過多造成資源浪費(fèi)，而其它區(qū)域缺少機(jī)器人造成接受任務(wù)后響應(yīng)不及時(shí)的情況。
本文部分內(nèi)容參考AGV網(wǎng)（https://www.chinaagv.com/），特別說明！
