許佳杰, 陳思魯, 張子棟, 邵兵兵, 劉 強(qiáng), 張 馳, 楊桂林

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

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

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

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

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

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

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

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

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

1.1 多移動(dòng)機(jī)器人任務(wù)分配定義

1.2 多移動(dòng)機(jī)器人動(dòng)態(tài)任務(wù)分配

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

總收益最大為:

圖1 多移動(dòng)機(jī)器人動(dòng)態(tài)任務(wù)分配過(guò)程

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

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

2.1 分布式拍賣(mài)機(jī)制的競(jìng)價(jià)與報(bào)價(jià)更新規(guī)則

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

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

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

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

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

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

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

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

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

具體基于分布式拍賣(mài)機(jī)制的多移動(dòng)機(jī)器人動(dòng)態(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 計(jì)算任務(wù)執(zhí)行順序

24 end

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

29 else

32 end

33 end

34 end

35 end

3 結(jié)果與分析

3.1 算法分配效率比較

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

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

圖2 算法分配效率

3.2 算法整體性能比較

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

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

3.3 算法可行性分析

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

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

3個(gè)移動(dòng)機(jī)器人分別前往任務(wù)點(diǎn)的移動(dòng)代價(jià)見(jiàn)表1. 最終移動(dòng)機(jī)器人A1競(jìng)拍到任務(wù)B1, 價(jià)格為8.35. 移動(dòng)機(jī)器人A2競(jìng)拍到任務(wù)B3, 價(jià)格為7.18, 移動(dòng)機(jī)器人A3競(jìng)拍到任務(wù)B2, 價(jià)格為8.21.

表1 移動(dòng)代價(jià)

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

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

4 結(jié)語(yǔ)

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

[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] 楊博, 王葉群, 黃國(guó)策, 等. 基于沖突分解的短波頻點(diǎn)真實(shí)在線雙拍賣(mài)算法[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áng)超, 李珍妮. 面向資源最優(yōu)分配的深度學(xué)習(xí)雙邊拍賣(mài)算法[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é)報(bào)（理工版）網(wǎng)址: http://journallg.nbu.edu.cn/

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

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

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

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