多機器人系統(tǒng)中基于環(huán)境側信息的移動任務調(diào)度算法

葉 剛 周慶隆

1(埃森哲(中國)有限公司先進技術中心 上海 200072)2(佳能信息系統(tǒng)(上海)有限公司 上海 200235)

0 引 言

隨著機器視覺﹑語音識別等人工智能技術和自動駕駛技術的快速發(fā)展，基于此類技術的服務型機器人也得到了飛速發(fā)展。近年來，我國適齡勞動人口數(shù)量開始逐步減少，勞動力成本不斷增加，為企業(yè)帶來了較高的成本壓力。這些都為服務型機器人進入酒店賓館服務業(yè)領域提供了應用場景的需求。目前在條件具備的酒店賓館企業(yè)試驗、測試和部署服務型機器人的商業(yè)機會越來越多，也促進了這一新技術研究和開發(fā)不斷走向成熟[1]。

在為某國際知名酒店經(jīng)營管理集團規(guī)劃未來的企業(yè)發(fā)展戰(zhàn)略的項目中，本文提出了基于智能服務型機器人驅動商業(yè)場景變革的計劃，并對POC(Proof of Concept)系統(tǒng)及其對所規(guī)劃的商業(yè)場景應用進行了驗證性測試。以實用化為目標，基于分散型的環(huán)境側信息獲取手段，構筑并實現(xiàn)了應用于模擬酒店環(huán)境的智能移動機器人系統(tǒng)，并通過仿真機器人與實際機器人相結合的方法驗證了系統(tǒng)性能能夠滿足實際產(chǎn)品工程化的需要。

1 智能機器人系統(tǒng)的應用場景

POC系統(tǒng)以酒店的客房服務為應用場景，客戶通過手機或者房間內(nèi)的智能音箱向系統(tǒng)請求客房服務。系統(tǒng)設計了一個任務分發(fā)器來接受和響應配送服務請求，在機器人允許承載條件下將一個或者多個服務任務動態(tài)分配給合適的機器人。機器人接受任務后，從待機位置移動到預先設置的配送源位置，裝載配送貨物后向配送任務目標位置移動，到達后系統(tǒng)通知客戶自取配送物。機器人通過攝像機進行人臉識別確認客戶，并通過搭載語音設備和客戶交流，當客戶取得配送物，命令機器人返回后，機器人返回待機位置等待下一次任務。

2 系統(tǒng)實驗的基礎設施

系統(tǒng)實驗環(huán)境由模擬典型酒店的2個樓層和電梯組成，如圖1所示。在每個樓層分別布置了多個超寬帶UWB無線定位系統(tǒng)的錨點，采用6 GHz的頻譜實現(xiàn)對機器人搭載的移動UWB標簽的無線定位[2]。

圖1 系統(tǒng)實驗環(huán)境

同時，酒店中一般都設置有WLAN的無線通信環(huán)境，也可以用于移動機器人和系統(tǒng)控制之間的通信。由于機器人需要在不同樓層間移動，所以系統(tǒng)還集成了電梯控制器接受系統(tǒng)指令，通過電信號的旁路輸入模擬電梯按鍵的樓層選擇，以實現(xiàn)不同樓層之間的配送服務。

移動機器人和搭載設備如圖2所示。采用了一套DC12V 37AH的電池作為機器人和搭載設備的供電電源；機器人搭載了一臺WLAN無線路由器實現(xiàn)和后臺系統(tǒng)的通信；機器人的移動由2個步進電機控制驅動輪和2個維持機器人平衡的萬向從動輪，利用一套Arduino Mega 2560微控制器的控制板作為主動輪步進電機驅動控制器[3]；機器人前向具有3個超聲波探測器，后向具有1個超聲波探測器，并搭載了一套單線SLAM探測器用于環(huán)境掃描和地圖構建[4]；機器人搭載了一套UWB移動定位標簽和一套運行ROS Kinetic[5]版本的樹莓派3B+嵌入式系統(tǒng)。由于UWB難于滿足局部的精確定位和導航，所以在機器人定位和導航中，采用基于UWB無線定位技術來實現(xiàn)多臺機器人全局路徑規(guī)劃。結合單臺機器人自身基于SLAM、慣性導航和超聲波避障的局部路徑規(guī)劃，設計了兩層結構的路徑規(guī)劃器在復雜的人機共存環(huán)境中將多個移動機器人導航到各自的目的地。

圖2 移動機器人和搭載設備

機器人搭載了一臺嵌入式工控機作為視覺控制器，一套6自由度的機械手臂和一臺高清云臺攝像機。利用機器視覺技術在大場景中實現(xiàn)物體分類，以實現(xiàn)目標物體的發(fā)現(xiàn)，并初步估算目標物距離和方位以供全局移動路徑規(guī)劃。在機械手臂手爪的末端搭載了一臺雙眼同步攝像機和一個激光測距模塊實現(xiàn)了一套眼在手(Eye In Hand)系統(tǒng)[6]。雙眼同步攝像機結合激光測距模塊實現(xiàn)近距離對目標物的幾何尺寸和手臂與目標物之間空間距離的感知，以供手臂動作控制器實現(xiàn)抓取動作的規(guī)劃。

另外，機器人搭載了一套6麥克語音矩陣和喇叭，實現(xiàn)360度聲源定位和關鍵字語音喚醒。麥克風矩陣后端的語音控制器，利用其CUDA庫實現(xiàn)語音到文字的高速識別和文字到語音的合成[7]。該控制器通過網(wǎng)絡和后臺的名為XBot的自然語言處理的對話應答系統(tǒng)進行通信實現(xiàn)語義理解，并產(chǎn)生應答文字的轉換音頻輸出，實現(xiàn)和客戶的語音交流。

3 多臺移動機器人配送系統(tǒng)的構成

POC系統(tǒng)由多臺移動機器人、各樓層的機器人UWB實時定位服務器、機器人位置管理服務器、機器人控制指令服務器、視頻傳輸媒體服務器、人臉識別服務器(iFace)、語音對話應答服務器(XBot)、系統(tǒng)運行管理服務器、配送任務調(diào)度服務器、電梯控制裝置等構成。各個服務器和設備通過WLAN無線網(wǎng)絡和LAN連接成一個分布式系統(tǒng)。其構成如圖3所示。

圖3 配送系統(tǒng)的構成圖

其中，任務調(diào)度服務器負責機器人移動和機械手臂的動作任務規(guī)劃，iFace負責機器視覺和人臉識別，XBot負責語義理解和應答對話，機器人位置管理服務器負責機器人在全局地圖中的坐標管理，機器人控制指令服務器負責不同樓層的路徑規(guī)劃和機器人控制指令的轉換等工作。

4 移動任務調(diào)度器及其評價算法

POC系統(tǒng)中的配送任務調(diào)度服務器利用在預知環(huán)境中部署的環(huán)境側傳感器來定位機器人[8]。其調(diào)度方法采用全部機器人的總移動距離和用戶任務從請求到實行完成所需要的時間作為評價函數(shù)的主要參量，實現(xiàn)了滿足多個客戶配送請求的多機器人任務動態(tài)分配和移動規(guī)劃。

4.1 調(diào)度的評價要素和目標

在機器人數(shù)量足夠的情況下，用戶的配送請求可以按照請求的時間順序向各個移動機器人按照先進先出調(diào)度策略進行任務分配。一臺機器人執(zhí)行一個客戶的配送請求，任務完成的及時性非常高，但是機器人總移動距離最長，系統(tǒng)整體效率低下。如果能夠調(diào)度一臺機器人能在一次移動中同時盡可能承擔多個客戶配送請求，那么系統(tǒng)的整體效率就可以得到極大的提升。POC系統(tǒng)中采用的調(diào)度算法實現(xiàn)了從客戶配送請求開始到任務執(zhí)行完成所需時間盡可能短的同時，機器人移動效率盡可能高的效果。

4.1.1 評價要素1

機器人的作業(yè)領域按照圖1的若干個區(qū)域進行粗粒度的網(wǎng)格化分割。POC系統(tǒng)調(diào)度考慮如下的區(qū)域重合度調(diào)度策略：對于分配了配送任務的機器人i，為了完成實行中的任務所必須通過的區(qū)域，以及新分配的任務所必須通過的區(qū)域，這兩者之間的區(qū)域重合度是非常重要的一個考量。一般而言，向重合度高的機器人分配任務，系統(tǒng)全局效率可以得到較大提高。為了實現(xiàn)上述構想，考慮到算法搜索計算的實時性，可以將機器人實際作業(yè)空間和網(wǎng)格化分割的抽象作業(yè)空間作為2層的階層化的搜索空間。本文將此粗粒度網(wǎng)格化[9]的搜索空間稱為Meta Level的空間，此搜索空間的狀態(tài)根據(jù)配送請求的到達時間而動態(tài)變化。采用深度優(yōu)先圖搜索算法[10]的機器人實際移動的空間稱為Base Level空間，根據(jù)Meta Level空間狀態(tài)的動態(tài)變化，Base Level的通過點的順序也動態(tài)變化。這個階層化的搜索空間如圖4所示。

圖4 階層化的搜索狀態(tài)空間

對于單個機器人，用戶的配送請求到達時，通過區(qū)域的重合度如圖5所示。

圖5 多個配送任務的重合度

圖5中，QA的灰色區(qū)域為機器人i分配的執(zhí)行任務中已經(jīng)通過的區(qū)域；在現(xiàn)在時刻t，新的客戶配送請求到達移動任務調(diào)度器，QB為此新任務預定通過區(qū)域，QC為機器人i在時刻t的未通過區(qū)域；在時刻s，客戶的配送請求任務如果被分配給機器人i，則QB和QC求和的集合QD就成為了機器人i的新的搜索空間。根據(jù)Meta Level中QD的通過區(qū)域的順序，將其Meta Cell中所包含Base Level層中的通過點隊列，在圖4的搜索狀態(tài)空間中向Base Level層投影，就可以確定Base Level通過點的順序。

4.1.2 評價要素2

為方便起見，假定配送作業(yè)中，任何機器人的移動速度相同。圖6給出了某配送任務的移動路徑，按箭頭指向的移動路徑進行配送的話，配送任務從出發(fā)位置到目標位置移動所需要的時間和機器人的移動距離就成比例關系。所以，統(tǒng)計出機器人從出發(fā)位置到目標位置的移動時間，也就確定了其移動的距離。

圖6 機器人移動路徑圖

4.2 調(diào)度器的評價函數(shù)

針對時刻t接收到的新配送請求向機器人進行移動任務分配時的評價函數(shù)進行說明。評價函數(shù)綜合以下要素：(1) 通過區(qū)域的重合度，(2) 機器人現(xiàn)在位置到該任務的出發(fā)位置的移動步數(shù)，機器人的可配送重量，配送優(yōu)先度等級等。可用以下的算法表示。

(1) 機器人i的順序待通過區(qū)域的隊列定義為:

Queue(l)={q[1],…,q[i],…,q[l]},where ?i≥0q[i]∈Nandq[i]≤Amax

Queue(0) is a null Queue

q[i]是通過區(qū)域的ID編號，N是一個自然數(shù)，Amax表示通過區(qū)域ID編號的最大值。

(2) Meta Level搜索空間的定義為:

T=Queue(0)∪Queue(l)

(3) 通過區(qū)域隊列的方向函數(shù)定義為:

Direction(Queue(l))=

(4) 機器人執(zhí)行中的配送任務表示為:

Task(r,Q,s)=(r,Queue(l),s), whereQis a Queue,ris the robot, andsis the time when the task is viable

projection:

μQ(Task)=Q, Task projection on Queue

μr(Task)=r, Task projection on robot

μs(Task)=s, Task projection on s

Task(r,Q,s)為機器人r在時刻s被分配的任務的狀態(tài)空間的通過區(qū)域。μQ(Task)為配送任務Task(r,Q,s)在Q上的投影，即Meta Cell的有向待通過隊列。μr(Task)為配送任務Task(r,Q,s)在r上的投影，表示某一臺機器人。μs(Task)為配送任務Task(r,Q,s)在s上的投影，這里的時刻s是指機器人r現(xiàn)在執(zhí)行中的配送任務的被分配的時刻，即求取時刻s的函數(shù)。新配送請求到達時，執(zhí)行中任務的未完成部分為：

Unexecuted(r,Task,t)=(φt(μQ(Task)),r)

?t≥μs(Task)

where Task=(Queue(l),r)

Unexecuted(r,Task,t)表示新配送請求到達的時刻t，機器人r已經(jīng)執(zhí)行中任務的未通過區(qū)域的求解函數(shù)。其中函數(shù):

φt(μQ(Task))=φt(Queue(m))=

where

len(t) is the Queue subscript to be executed at timetandlen(μs(Task))=l

φt(μQ(Task))表示新配送請求到達的時刻t，機器人r從當前位置開始的μQ(Task)中未通過區(qū)域的獲取函數(shù)。len(t)表示新配送請求的到達時刻t，μQ(Task)中已通過區(qū)域長度的求解函數(shù)。新配送請求達到時刻t，機器人r的殘留未通過區(qū)域的求解函數(shù)為:

Mexe(Unexecuted(r,Task,t))=φt(Queue(m))

Unexecuted(r,Task,t)=(φt(Queue(m),r)

新配送請求達到時刻t，機器人r的狀態(tài)表示為:

0：機器人r待機中，無執(zhí)行中的任務。

1：機器人r有一個或者多個任務執(zhí)行中。

任務調(diào)度評價函數(shù)的計算表達式如下：

whenTaskAddas the queue for new planned task

ifTaskAdd=Queue(n) Then

式中:TaskAdd表示新配送任務，一個具有執(zhí)行順序的通過區(qū)域的隊列。Sr(t,TaskAdd)表示在時刻t的機器人r，從當前位置到新配送任務的開始位置的距離。StepMax：正規(guī)化的定數(shù)，具有足夠大的值。Cr()表示機器人r的新配送請求的通過區(qū)域，和新請求到達時機器人原有任務的未通過區(qū)域的重合度的求解函數(shù)。δr(t)表示新配送請求到達時刻t，機器人r的狀態(tài)。α表示重合度系數(shù)。

約束條件如下：

r∈Ω(TaskAdd)

Ω(TaskAdd)=

式中:r為某臺機器人。Ω(TaskAdd)為新配送請求被系統(tǒng)接收時的機器人的集合。Direction(Kr(t,Task,TaskAdd)×Direction(TaskAdd)表示機器人r的新配送請求的移動方向和該機器人現(xiàn)在執(zhí)行中任務的移動方向是否一致的判斷。NumberTask表示機器人r可以承受的負載量。Priority(Kr(t,Task))表示機器人r執(zhí)行中的配送請求的緊急程度。

5 移動任務調(diào)度器的系統(tǒng)架構

為了驗證調(diào)度算法的有效性，本文采用AOP(Agent Oriented Programming[11])的概念，設計了具有記憶能力的Multi-Agent反射型系統(tǒng)架構[12]，如圖7所示。

圖7 移動任務調(diào)度器系統(tǒng)架構圖

調(diào)度器的戰(zhàn)略層根據(jù)前述的評價函數(shù)，可以從多臺移動機器人中，選取最合適的機器人執(zhí)行客戶的配送請求。這里的RA作為各個機器人的Agent運行在內(nèi)存中實現(xiàn)對Meta Level的搜索。最后，將各自的移動步數(shù)和移動路徑的重合度向戰(zhàn)略層匯報。RA的內(nèi)部處理如圖8所示。

圖8 Robot Agent模塊的內(nèi)部處理

配送任務管理層根據(jù)圖5中QD=QB∪QC的計算公式，將機器人執(zhí)行中配送任務的通過點和新配送任務的計劃通過點進行匹配，所生成的通過點的隊列作為機器人的新通過的隊列，由機器人迭代后續(xù)執(zhí)行。

6 實 驗

由于只有一臺移動機器人，為了驗證調(diào)度算法在多臺機器人情況下的有效性，本文參照移動機器人的參數(shù)，在圖9所示實驗系統(tǒng)中，通過機器人模擬程序向機器人位置管理服務器發(fā)送模擬實時位置信息的方式模擬了2臺機器人，與移動機器人一起進行了實驗。

圖9 實驗系統(tǒng)架構

為了驗證不同重合度系數(shù)對于系統(tǒng)配送總時間的影響，向實驗系統(tǒng)在短時間內(nèi)輸入了15個具有路徑重合的配送請求。通過設置重合度系數(shù)的不同變化，對配送任務的執(zhí)行平均時間進行了統(tǒng)計，其結果如表1所示。

表1 不同重合度系數(shù)的執(zhí)行時間結果表

為了驗證調(diào)度算法的效率，本文選取了一個典型的配送任務場景進行實驗，使用如圖10中的兩個配送任務。分別對機器人采用：在資源無限情況下配送任務獨占機器人，及時性最高的任務調(diào)度策略；在資源受限情況下單臺機器人按照FIFO方式的任務調(diào)度策略；按照本文算法的任務調(diào)度策略在實驗系統(tǒng)上進行了測試。最后，和本文算法的理論計算數(shù)據(jù)進行對比。

圖10 配送任務位置圖

表2是配送任務A→B和C→D的起始點坐標數(shù)據(jù)。機器人的待機位置如圖6所示，其中待機位置A1配置實機機器人。

表2 配送任務位置表

機器人移動速度為100 mm/s的情況下，使用1臺機器人和2臺模擬機器人對設定的2個配送任務，按照上述三種調(diào)度策略分別進行了實驗，得到的2個任務合計配送時間的實驗結果如表3所示。

表3 基于三種調(diào)度算法2個任務的總執(zhí)行時間結果表

7 結 語

為了解決設定場景中時間序列上的多個用戶向多臺移動機器人的配送系統(tǒng)不斷發(fā)起配送請求下，實現(xiàn)系統(tǒng)整體效率的優(yōu)化，提出了以合并相近時間序列上配送任務中移動路徑重合度較高的多個配送任務為手法的任務調(diào)度算法。并在設定的目標應用場景的實驗環(huán)境中進行了測試，對提出的任務調(diào)度算法的有效性進行了評價。