多機器人系統中基于環境側信息的移動任務調度算法

葉 剛 周慶隆

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

0 引 言

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

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

1 智能機器人系統的應用場景

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

2 系統實驗的基礎設施

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

圖1 系統實驗環境

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

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

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

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

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

3 多臺移動機器人配送系統的構成

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

圖3 配送系統的構成圖

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

4 移動任務調度器及其評價算法

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

4.1 調度的評價要素和目標

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

4.1.1 評價要素1

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

圖4 階層化的搜索狀態空間

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

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

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

4.1.2 評價要素2

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

圖6 機器人移動路徑圖

4.2 調度器的評價函數

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

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

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

Queue(0) is a null Queue

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

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

T=Queue(0)∪Queue(l)

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

Direction(Queue(l))=

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

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被分配的任務的狀態空間的通過區域。μ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現在執行中的配送任務的被分配的時刻，即求取時刻s的函數。新配送請求到達時，執行中任務的未完成部分為：

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

?t≥μs(Task)

where Task=(Queue(l),r)

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

φ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)中未通過區域的獲取函數。len(t)表示新配送請求的到達時刻t，μQ(Task)中已通過區域長度的求解函數。新配送請求達到時刻t，機器人r的殘留未通過區域的求解函數為:

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

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

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

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

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

任務調度評價函數的計算表達式如下：

whenTaskAddas the queue for new planned task

ifTaskAdd=Queue(n) Then

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

約束條件如下：

r∈Ω(TaskAdd)

Ω(TaskAdd)=

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

5 移動任務調度器的系統架構

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

圖7 移動任務調度器系統架構圖

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

圖8 Robot Agent模塊的內部處理

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

6 實 驗

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

圖9 實驗系統架構

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

表1 不同重合度系數的執行時間結果表

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

圖10 配送任務位置圖

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

表2 配送任務位置表

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

表3 基于三種調度算法2個任務的總執行時間結果表

7 結 語

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