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

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

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

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

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

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

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

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

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

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

1.1 多移動機器人任務(wù)分配定義

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

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

總收益最大為:

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

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

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

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)度中心進行任務(wù)分配, 移動機器人之間能夠互相通信, 實現(xiàn)共享, 且實時更新任務(wù)集.

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

當(dāng)任務(wù)分配過程中滿足條件:

任務(wù)分配結(jié)束.

本文提出一種基于分布式拍賣機制的多移動機器人動態(tài)任務(wù)分配算法(Auctalgo算法), 具體執(zhí)行通常可分為以下幾個步驟:

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

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

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

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

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

輸出: 任務(wù)分配結(jié)果

1 初始化參數(shù);

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

11 else

12 跳出行4

13 end

14 else

15 跳出行4

16 end

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

24 end

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

29 else

32 end

33 end

34 end

35 end

3 結(jié)果與分析

3.1 算法分配效率比較

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

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

圖2 算法分配效率

3.2 算法整體性能比較

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

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

3.3 算法可行性分析

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

圖3 不同算法任務(wù)分配結(jié)果

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

表1 移動代價

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

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

4 結(jié)語

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

[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)工程與電子技術(shù), 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)分配的深度學(xué)習(xí)雙邊拍賣算法[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.

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

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

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

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

（責(zé)任編輯 史小麗）