基于分布式拍賣機制的多移動機器人動態(tài)任務分配算法

許佳杰, 陳思魯, 張子棟, 邵兵兵, 劉 強, 張 馳, 楊桂林

基于分布式拍賣機制的多移動機器人動態(tài)任務分配算法

許佳杰1,2, 陳思魯2*, 張子棟1,2, 邵兵兵1,2, 劉 強2, 張 馳2, 楊桂林2

（1.寧波大學 信息科學與工程學院, 浙江 寧波 315211; 2.中國科學院 寧波材料技術與工程研究所, 浙江 寧波 315201）

任務分配是多移動機器人調(diào)度系統(tǒng)的關鍵問題之一, 為了提高任務整體完成效率, 提出了一種基于分布式拍賣機制的多移動機器人動態(tài)任務分配算法. 該方法對機器人群體采用分布式控制方法, 彼此共享且動態(tài)更新任務集, 采用分布式的拍賣機制競拍任務, 增加了調(diào)整任務執(zhí)行順序環(huán)節(jié), 考慮任務整體完成效率, 最后在Linux系統(tǒng)下搭建了多機器人和障礙物的仿真環(huán)境. 結果表明, 該算法分配效率高于線性(CLP)算法和混合整數(shù)求解(CBC)算法, 且具有穩(wěn)定性, 相比執(zhí)行效率高的深度強化學習(DQN)算法和空缺鏈(VC)算法, 執(zhí)行效率穩(wěn)定, 移動代價降低了55％, 實現(xiàn)了較高執(zhí)行效率和低移動代價之間的平衡, 可應用于實際仿真環(huán)境, 具有可行性.

多移動機器人調(diào)度系統(tǒng); 動態(tài)任務分配; 拍賣機制; 分布式控制

隨著智能制造時代的到來, 各類可移動機器人被廣泛應用于各個領域, 隨之配套的多移動機器人調(diào)度系統(tǒng)也顯得舉足輕重. 而任務分配算法是多移動機器人調(diào)度系統(tǒng)中的核心, 如何將任務分配給移動機器人, 使整個多移動機器人調(diào)度系統(tǒng)的效益最大化, 是多移動機器人任務分配領域亟待解決的問題[1]. 多移動機器人任務分配(Multi- Robot Task Allocation, MRTA)是機器人領域的核心問題之一, 是一個NP-hard問題, 主要分為兩種類型: 第一種為Gerkey等[2]所提出的將其分為8種子類型; 第二種為Korsah等[3]提出的基于相互依賴的資源和約束, 將其分為4種子類型, 成為iTax分類. 任務分配策略根據(jù)相應的移動機器人應用進行分類, 主要分為基于拍賣任務分配策略和基于優(yōu)化策略. 對實際任務分配環(huán)境的MRTA問題[4], 通常采用基于市場拍賣的任務分配策略來解決[5].

基于市場拍賣算法是一種突出的多移動機器人任務分配策略[6-8], 拍賣機制是其算法的核心. 啟發(fā)式的遺傳算法和拍賣算法的性能對比結果表明, 拍賣算法在分配問題上具有性能優(yōu)勢[9]. 近年來, 研究人員專注于開發(fā)針對復雜約束問題的動態(tài)任務分配策略和具有多種不確定性條件的魯棒策略[10], 原因是傳統(tǒng)的基于拍賣機制的任務分配方法面對動態(tài)場景時難以給出實時的分配方案, 失去了靜態(tài)場景下的性能優(yōu)勢, 且魯棒性差[11]. 基于市場的任務分配方法依賴于強連接的機器人網(wǎng)絡, 其在溝通缺失或弱溝通環(huán)境下的任務完成率較差, 且局限于提高任務分配效率而不是任務整體完成效率[12-13]. 然而, 實際移動機器人任務分配場景不僅包括任務分配, 還包括任務執(zhí)行; 而移動機器人運行狀態(tài)決定了移動機器人是否能前往任務點執(zhí)行任務[14].

本文提出了一種基于分布式拍賣機制的多移動機器人動態(tài)任務分配算法, 對移動機器人采用基于機器人操作系統(tǒng)(Robot Operating System, ROS)的分布式控制, 彼此共享且動態(tài)更新任務集, 采用分布式的拍賣機制競拍任務, 根據(jù)移動機器人的狀態(tài)信息確定移動代價最小的任務執(zhí)行順序, 實現(xiàn)了較高執(zhí)行效率和低移動代價之間的平衡, 優(yōu)化了任務分配結果, 提高了任務整體完成效率.

1 多移動機器人動態(tài)任務分配模型

1.1 多移動機器人任務分配定義

1.2 多移動機器人動態(tài)任務分配

多移動機器人的動態(tài)任務分配相比靜態(tài)任務分配更適合應用在實際任務分配環(huán)境中. 以圖1為例說明本文算法中動態(tài)任務的分配過程, 圖1中方塊為任務, 圓為移動機器人.

總收益最大為:

圖1 多移動機器人動態(tài)任務分配過程

多移動機器人動態(tài)任務分配的目標是將動態(tài)變化的任務按照收益的大小合理地分配給每個移動機器人, 同時調(diào)整每個移動機器人的任務執(zhí)行順序, 最終使移動機器人完成所有任務后獲得較好的任務收益, 使整個系統(tǒng)的總收益最大化.

2 基于分布式拍賣機制的多移動機器人動態(tài)任務分配算法設計

2.1 分布式拍賣機制的競價與報價更新規(guī)則

ROS是一個分布式計算環(huán)境, 運行中ROS系統(tǒng)可以包含分布在多臺計算機上的多個節(jié)點, 根據(jù)系統(tǒng)配置方式, 任何節(jié)點可以隨時與任何其他節(jié)點進行通信. 對移動機器人采用基于ROS的分布式控制, 傳統(tǒng)的集中式拍賣機制將轉(zhuǎn)變?yōu)榉植际脚馁u機制, 不需要統(tǒng)一的調(diào)度中心進行任務分配, 移動機器人之間能夠互相通信, 實現(xiàn)共享, 且實時更新任務集.

2.2 基于分布式拍賣機制的多移動機器人動態(tài)任務分配算法

當任務分配過程中滿足條件:

任務分配結束.

本文提出一種基于分布式拍賣機制的多移動機器人動態(tài)任務分配算法(Auctalgo算法), 具體執(zhí)行通?？煞譃橐韵聨讉€步驟:

(1)初始化: 統(tǒng)計所有待分配任務與機器人的相關信息(式(3)), 計算任務初始收益(式(2)), 移動機器人根據(jù)任務收益確定是否參與競拍.

(2)競價階段: 機器人在確保自己利潤最大化前提下對任務加價競拍(式(7)), 如果任務當前價格大于預期利潤, 則放棄競拍(式(8)); 如果某個任務有最高出價的機器人出現(xiàn), 報價將不再變動(式(9)).

(3)任務分配與執(zhí)行階段: 根據(jù)機器人的狀態(tài)信息決定是否將任務分配給最高報價的機器人(式(12)), 如果被分配任務機器人無法執(zhí)行任務(式(13)), 則由空閑最高報價機器人替代其執(zhí)行任務, 并根據(jù)任務集確定移動代價最小的任務執(zhí)行順序.

(4)算法收斂條件: 如果總?cè)蝿占癁榭占?式(11)), 算法停止; 否則進行新一輪分布式拍賣, 轉(zhuǎn)向步驟1.

具體基于分布式拍賣機制的多移動機器人動態(tài)任務分配算法如下:

輸出: 任務分配結果

1 初始化參數(shù);

2 while 環(huán)境中還有未完成的任務do

11 else

12 跳出行4

13 end

14 else

15 跳出行4

16 end

23 計算任務執(zhí)行順序

24 end

28 計算任務執(zhí)行順序

29 else

32 end

33 end

34 end

35 end

3 結果與分析

3.1 算法分配效率比較

為了驗證本文提出算法的分配效率、穩(wěn)定性和可行性, 進行了仿真實驗. 采用OR-Tools開源組合優(yōu)化問題求解器中處理復雜分配問題的線性(CLP)和混合整數(shù)求解算法(CBC)[15]與Auctalgo算法進行分配效率對比.

移動機器人與任務數(shù)量比設定為1:1, 3種算法在不同數(shù)量移動機器人下的分配效率如圖2(a)所示. 仿真結果表明, 當移動機器人數(shù)量超過300個時, CLP算法與CBC算法的分配效率驟降, Auctalgo算法的分配效率相對穩(wěn)定. 為進一步探究算法的穩(wěn)定性, 繼續(xù)增加移動機器人數(shù)量來測試算法的分配效率, 最終結果如圖2(b)所示. 從圖2(b)可發(fā)現(xiàn), 在移動機器人數(shù)量超過32000個后, 算法的分配時間才開始明顯增加, 表明在面對眾多數(shù)量移動機器人場景下Auctalgo算法穩(wěn)定.

圖2 算法分配效率

3.2 算法整體性能比較

實際任務分配場景包括任務的分配和執(zhí)行, 因此算法的分配效率并不能決定任務整體完成的效率. 因此, 將從任務完成時間和移動代價兩方面來評價算法的性能. 通過多移動機器人任務分配模擬系統(tǒng)進行仿真實驗, 該系統(tǒng)基于ROS對移動機器人采用分布式控制, 接近真實環(huán)境[16]. 將算法與執(zhí)行效率高的空缺鏈(VC)算法和深度強化學習(DQN)算法對比, 結果如圖3所示.

圖3(a)～(c)為擁有5個移動機器人和5個任務場景下任務分配結果, 圖3(d)～(f)為擁有5個移動機器人和10個任務場景下任務分配結果. 為了減少方差并過濾掉隨機影響, 每組算法進行8次. DQN、VC、Auctalgo 3種算法在任務完成時間上區(qū)別不大, DQN算法和VC算法在平均移動代價上分別為Auctalgo算法的1.9和1.8倍. 3種算法中DQN算法在任務完成時間上表現(xiàn)最差, VC算法在任務完成時間上比Auctalgo算法略有優(yōu)勢, 但DQN算法和VC算法在平均移動代價上分別為Auctalgo算法的2.5和2.2倍. 在任務數(shù)量增加情況下, Auctalgo算法在移動代價表現(xiàn)上優(yōu)勢明顯, 實現(xiàn)了較高執(zhí)行效率和低移動代價之間的平衡.

3.3 算法可行性分析

設計采用包含多移動機器人和障礙物的仿真環(huán)境來驗證Auctalgo算法在實際任務分配場景下的可行性. 算法在Linux操作系統(tǒng)、內(nèi)存為8G、基于ROS的move_base導航環(huán)境下運行. 仿真環(huán)境搭建和算法驗證步驟如下: (1)創(chuàng)建基于激光雷達和IMU傳感器導航的移動機器人統(tǒng)一機器人描述格式(URDF)模型, 然后在仿真平臺Gazebo中加載模型, 最后設計包含3個移動機器人和障礙物信息的仿真環(huán)境, 借助機器人數(shù)據(jù)可視化工具Rviz可視化話題信息, 隨機分配任務. (2)移動機器人群體采用基于ROS分布式控制, 彼此交換任務信息后, 最終算法給出整體無沖突, 且任務收益最大的任務分配方案. (3)移動機器人采集激光雷達和IMU數(shù)據(jù), 并結合Move_base導航框架實現(xiàn)路徑規(guī)劃. 最終移動機器人根據(jù)算法調(diào)整任務執(zhí)行順序, 結合自身狀態(tài)信息確認是否前往任務點執(zhí)行任務.

圖3 不同算法任務分配結果

3個移動機器人分別前往任務點的移動代價見表1. 最終移動機器人A1競拍到任務B1, 價格為8.35. 移動機器人A2競拍到任務B3, 價格為7.18, 移動機器人A3競拍到任務B2, 價格為8.21.

表1 移動代價

任務分配過程和結果如圖4所示, 包含了3個移動機器人當前位姿和障礙物以及運行路徑等信息. 最終移動機器人A1從當前點出發(fā)到達任務點B1, 移動機器人A2從當前點出發(fā)到達任務點B3, 移動機器人A3從當前點出發(fā)到達任務點B2. 當出現(xiàn)新任務時, 算法能進行實時任務分配使移動機器人最終完成任務執(zhí)行. 仿真結果表明, 在分布式控制下, Auctalgo算法能夠應用于多移動機器人任務分配的仿真環(huán)境, 成功實現(xiàn)任務的分配和執(zhí)行, 驗證了算法的可行性.

圖4 不同任務數(shù)量下的任務分配結果

4 結語

本文針對傳統(tǒng)拍賣算法的拍賣機制在動態(tài)任務分配場景下魯棒性差、忽略任務整體完成效率、在弱溝通環(huán)境下任務分配完成率較差等問題, 提出了一種基于分布式拍賣機制的多移動機器人動態(tài)任務分配算法. 算法綜合考慮機器人狀態(tài)信息對任務完成的影響來評價任務分配整體效率, 增加了調(diào)整任務執(zhí)行順序環(huán)節(jié), 實現(xiàn)了較高執(zhí)行效率和低移動代價之間的平衡, 對動態(tài)任務分配場景有較強的魯棒性, 顯著提高了任務分配效率. 對移動機器人群體采用分布式控制方式, 不需要統(tǒng)一的調(diào)度中心分配任務, 彼此共享且實時更新任務集. 搭建了包含多移動機器人和障礙物的任務分配仿真環(huán)境進行仿真實驗, 結果表明, 該算法分配效率高、穩(wěn)定性強、具有可行性, 能解決多移動機器人動態(tài)任務的分配問題.

[1] D’Emidio M, Khan I. Multi-robot task allocation problem: Current trends and new ideas[EB/OL]. [2022-07-10]. https://ceur-ws.org/Vol-1949/ICTCSpaper07.pdf.

[2] Gerkey B P, Matari? M J. A formal analysis and taxonomy of task allocation in multi-robot systems[J]. The International Journal of Robotics Research, 2004, 23(9):939-954.

[3] Korsah G A, Stentz A, Dias M B. A comprehensive taxonomy for multi-robot task allocation[J]. The Inter- national Journal of Robotics Research, 2013, 32(12): 1495-1512.

[4] Tsang K F E, Ni Y Q, Wong C F R, et al. A novel warehouse multi-robot automation system with semi- complete and computationally efficient path planning and adaptive genetic task allocation algorithms[C]//2018 15th International Conference on Control, Automation, Robotics and Vision (ICARCV), Singapore, 2018:1671- 1676.

[5] Luo L. Distributed algorithm design for constrained multirobot task assignment[EB/OL]. [2022-07-10]. https://www.ri.cmu.edu/pub_files/2014/8/Lingzhi_Luo_robotics_2014.pdf.

[6] 楊博, 王葉群, 黃國策, 等. 基于沖突分解的短波頻點真實在線雙拍賣算法[J]. 系統(tǒng)工程與電子技術, 2022, 44(9):2947-2954.

[7] Schneider E, Sklar E I, Parsons S. Mechanism selection for multi-robot task allocation[C]//Gao Y, Fallah S, Jin Y, et al. Annual Conference Towards Autonomous Robotic Systems, Cham: Springer, 2017:421-435.

[8] 鄭陽超, 李珍妮. 面向資源最優(yōu)分配的深度學習雙邊拍賣算法[EB/OL]. [2022-07-10]. https://www.doc88. com/p-39999494108107.html.

[9] Dai X F, Wang J Z, Zhao J Q. Research on multi-robot task allocation based on BP neural network optimized by genetic algorithm[C]//2018 5th International Conference on Information Science and Control Engineering (ICISCE), Zhengzhou, China, 2019:478-481.

[10] Sarkar C, Paul H S, Pal A. A scalable multi-robot task allocation algorithm[C]//2018 IEEE International Conference on Robotics and Automation (ICRA), Brisbane, Australia, 2018:5022-5027.

[11] Bertsekas D P. Auction algorithms for network flow problems: A tutorial introduction[J]. Computational Optimization and Applications, 1992, 1(1):7-66.

[12] Otte M, Kuhlman M J, Sofge D. Auctions for multi-robot task allocation in communication limited environments[J]. Autonomous Robots, 2020, 44(3/4):547-584.

[13] Whitbrook A, Meng Q G, Chung P W H. Addressing robustness in time-critical, distributed, task allocation algorithms[J]. Applied Intelligence, 2019, 49(1):1-15.

[14] Zhou X, Wang H M, Ding B, et al. Balanced connected task allocations for multi-robot systems: An exact flow-based integer program and an approximate tree-based genetic algorithm[J]. Expert Systems with Applications, 2019, 116:10-20.

[15] Menouer T, Le Cun B. A parallelization mixing OR- tools/gecode solvers on top of the bobpp framework [C]//2013 Eighth International Conference on P2P, Parallel, Grid, Cloud and Internet Computing, Compiegne, France, 2013:242-246.

[16] Dai W, Lu H M, Xiao J H, et al. Multi-robot dynamic task allocation for exploration and destruction[J]. Journal of Intelligent & Robotic Systems, 2020, 98(2):455-479.

Dynamic task assignment algorithm for multi-mobile robots based on distributed auction mechanism

XU Jiajie1,2, CHEN Silu2*, ZHANG Zidong1,2, SHAO Bingbing1,2, LIU Qiang2, ZHANG Chi2, YANG Guilin2

( 1.Faculty of Electrical Engineering and Computer Science, Ningbo University, Ningbo 315211, China; 2.Ningbo Institute of Materials Technology & Engineering, Chinese Academy of Sciences, Ningbo 315201, China )

Task allocation is one of the key issues in multi-mobile robot scheduling system. The existing methods tend to focus on improving the efficiency of task assignment without considering the task execution time, ignoring the overall task completion efficiency and the computational cost. In addition, they usually adopt a centralized control architecture, which requires the robot to be in a stable and reliable communication environment. In order to solve the above problems, a distributed auction mechanism-based dynamic task assignment algorithm for multiple mobile robots is proposed. The method adopts a distributed control method for robot groups, shares and dynamically updates task sets with each other, bids for tasks using a distributed auction mechanism, adds a link to adjust the task execution order, and considers the overall task completion efficiency. Finally, a simulation environment with multiple robots and obstacles is built under Linux system and relevant experiments are conducted. The experimental results show that the algorithm has higher allocation efficiency than the linear and mixed integer solving algorithms CLP and CBC, and has stability. Comparing with the Deep Reinforcement Learning (DQN) and Vacancy Chain (VC) algorithms, the execution efficiency remains stable while the movement cost is significantly reduced by 55％, which achieves a balance between the efficiency and cost in operation. This study, as believed, can be put to the real-world applications with promising outlook.

multi-mobile robot scheduling system; dynamic task assignment; auction mechanism; distributed control

TP242.6

A

1001-5132（2023）03-0029-07

2022?09?21.

寧波大學學報（理工版）網(wǎng)址: http://journallg.nbu.edu.cn/

國家自然科學基金（U1509202）; 浙江省基礎公益研究計劃（LGG19E050007）; 浙江省機器人與智能制造裝備技術重點實驗室（2015E10011）; 寧波市“科技創(chuàng)新2025”重大專項（2018B10010, 2020Z020）.

許佳杰（1997－）, 男, 浙江杭州人, 在讀碩士研究生, 主要研究方向: 多移動機器人調(diào)度. E-mail: xujiajie@nimte.ac.cn

通信作者:陳思魯（1982－）, 男, 福建福州人, 研究員, 主要研究方向: 高速、高精度運動控制及工業(yè)自動化. E-mail: chensilu@nimte.ac.cn

（責任編輯 史小麗）