結(jié)合遺傳算法和滾動調(diào)度的多機器人任務(wù)分配算法

鄧輔秦，黃煥釗，譚朝恩，付蘭慧，張建民，林天麟

結(jié)合遺傳算法和滾動調(diào)度的多機器人任務(wù)分配算法

鄧輔秦1，2，黃煥釗1，譚朝恩1，付蘭慧1，張建民1，林天麟2*

（1.五邑大學 智能制造學部，廣東 江門 529020； 2.香港中文大學（深圳）深圳市人工智能與機器人研究院，廣東 深圳 518116）（?通信作者電子郵箱tllam@cuhk.edu.cn）

研究多機器人任務(wù)分配（MRTA）的目的是提高智能工廠中機器人完成任務(wù)的效率。針對現(xiàn)有算法在處理大規(guī)模、多約束的MRTA時存在不足的問題，提出一種結(jié)合遺傳算法和滾動調(diào)度的MRTA算法（ACGARS）。首先，在遺傳算法中采用基于有向無環(huán)圖（DAG）的編碼方式高效地處理任務(wù)之間的優(yōu)先級約束；其次，在遺傳算法的初始種群中加入先驗知識以提高算法的搜索效率；最后，設(shè)計基于任務(wù)組的滾動調(diào)度策略用于減小求解問題的規(guī)模，從而實現(xiàn)對大規(guī)模問題的高效求解。在大規(guī)模問題實例上的實驗結(jié)果表明，相較于構(gòu)造性啟發(fā)式算法（CHA）、最小化干擾算法（MIA）和基于懲罰策略的遺傳算法（GAPS）生成的方案，當任務(wù)組數(shù)為20時，所提算法生成的方案的平均訂單完成時間分別縮短了30.02%、16.86%和75.65%，驗證了所提算法能有效地縮短訂單的平均等待時間，提升多機器人任務(wù)分配效率。

多機器人任務(wù)分配；遺傳算法；智能工廠；有向無環(huán)圖；滾動調(diào)度策略

0 引言

隨著人們生活水平的不斷提高和信息技術(shù)的不斷發(fā)展，個性化的消費形式正逐步取代大范圍、單調(diào)統(tǒng)一的消費形式。個性化消費基于訂單消費的小批量、定制化和多種類等特性，將成為未來主流消費方式，因此按需批量生產(chǎn)個性化產(chǎn)品也是智能制造業(yè)未來轉(zhuǎn)型升級的主要發(fā)展趨勢，而智能工廠是智能制造過程的關(guān)鍵部分［1］。智能工廠需要根據(jù)收到的每個訂單的個性化需求與所需產(chǎn)品數(shù)量靈活安排多個產(chǎn)品的生產(chǎn)流程，從而生產(chǎn)訂單需要的產(chǎn)品，快速響應(yīng)市場需求；但是，傳統(tǒng)的工廠固定的生產(chǎn)模式無法滿足客戶小批量高度定制產(chǎn)品的需求。針對傳統(tǒng)工廠的缺點，目前已有許多先進的智能工廠解決方案。其中，基于模塊化自重構(gòu)機器人［2］的多機器人系統(tǒng)是一種具有代表性的制造系統(tǒng)［3-4］。多機器人系統(tǒng)將訂單視為一組生產(chǎn)制造任務(wù)，并控制多個機器人共同協(xié)作完成任務(wù)。相較于傳統(tǒng)工廠，多機器人系統(tǒng)能夠根據(jù)不同訂單的需求靈活地為每個任務(wù)分配不同數(shù)量的機器人。這些基于模塊化自重構(gòu)機器人可以根據(jù)任務(wù)的需求進行重構(gòu)［5］，滿足動態(tài)的個性化訂單需求。

在智能工廠的多機器人系統(tǒng)中，需要控制數(shù)量龐大的機器人，目標是合理規(guī)劃機器人執(zhí)行計劃，最小化訂單的平均等待時間，從而快速響應(yīng)需求。因此在設(shè)計、構(gòu)建和使用多機器人系統(tǒng)時，需要解決的一個問題是：系統(tǒng)中各個機器人在各個時刻分別應(yīng)該選取什么動作，執(zhí)行什么任務(wù)？即多機器人任務(wù)分配（Multi-Robot Task Allocation， MRTA）問題。MRTA問題存在于許多領(lǐng)域，例如農(nóng)業(yè)生產(chǎn)［6-8］、災(zāi)后搜索救援［9-11］、水下監(jiān)測［12-13］和環(huán)境探索［14］等。本文重點研究智能工廠背景下的MRTA問題。在該問題中，機器人每次只能執(zhí)行一個任務(wù)，每個任務(wù)需要多個機器人組成團隊協(xié)同執(zhí)行。由于任務(wù)數(shù)較多，機器人需要在不同的時間內(nèi)完成多個任務(wù)；此外，任務(wù)之間存在優(yōu)先級關(guān)系，所以機器人執(zhí)行任務(wù)的情況不僅與自身有關(guān)，還會受到其他機器人的影響［15］，使得高質(zhì)量調(diào)度方案的生成較難。根據(jù)文獻［16］，該MRTA問題在iTax分類法下屬于單任務(wù)機器人、多機器人任務(wù)和包含跨時間表依賴的時間擴展分配類型的MRTA問題。

目前，已有許多類型的方法用于解決MRTA問題，包括精確算法［14，17］、基于機器學習的方法［18］、基于規(guī)則的啟發(fā)式算法［19］和遺傳算法［20-25］等。面對這一類MRTA問題，精確算法雖然能得到最優(yōu)解，但它的求解時間隨著問題規(guī)模的增加呈指數(shù)增長［26］；而基于機器學習的方法則需要花費大量成本用于制作訓(xùn)練集［18］。目前求解這一類MRTA問題的主要方法是基于規(guī)則的啟發(fā)式算法和遺傳算法：基于規(guī)則的啟發(fā)式算法按照一定的規(guī)則將任務(wù)分配給相應(yīng)的機器人團隊，簡單易實現(xiàn)，但算法并不以全局最優(yōu)為目標，且在不同的案例中性能可能會有很大的差異；而遺傳算法則是將任務(wù)分配方案編碼為個體，用適應(yīng)度函數(shù)評價個體的競爭力，然后模仿自然進化的方式搜索最優(yōu)個體。近年來，許多研究團隊使用遺傳算法解決MRTA問題［21-25］：文獻［24］中提出一種多種群遺傳算法用于求解多無人水下航行器的任務(wù)分配問題；文獻［25］中為倉儲物流應(yīng)用中的多機器人系統(tǒng)設(shè)計了基于遺傳算法的任務(wù)分配方法。針對任務(wù)之間的優(yōu)先級約束，在Miloradovi?等［21-22］提出的遺傳算法中，設(shè)計了優(yōu)先約束修復(fù)算子用于修復(fù)違背約束的個體，確保生成的個體都能夠滿足優(yōu)先級約束。雖然進化算法在MRTA問題的應(yīng)用研究廣泛，但大多數(shù)研究的問題集中于單機器人任務(wù)類型，即每個任務(wù)只需要一個機器人執(zhí)行，沒有同時考慮多機器人協(xié)作與有任務(wù)優(yōu)先級，與本文研究的問題屬于不同類型。當前用于解決這類MRTA問題的主要方法是基于懲罰策略的遺傳算法（Genetic Algorithm with Penalty Strategy， GAPS）［20］。GAPS根據(jù)生成解方案的違背約束程度，在相應(yīng)個體的適應(yīng)度函數(shù)上增加懲罰函數(shù)，在處理小規(guī)模問題時簡單高效；然而在面對較大規(guī)模問題時，由于任務(wù)之間優(yōu)先級關(guān)系數(shù)量與復(fù)雜性增加，導(dǎo)致生成的個體更容易違背約束，使算法的尋優(yōu)能力下降。

綜上所述，雖然現(xiàn)有用于求解MRTA問題的遺傳算法較多，但都不能較好地解決大規(guī)模的包含任務(wù)優(yōu)先級約束的MRTA問題。針對這個問題，本文提出了一種結(jié)合遺傳算法和滾動調(diào)度的MRTA算法（MRTA Algorithm Combining Genetic Algorithm and Rolling Scheduling， ACGARS）。本文算法主要有以下特點：首先，針對GAPS搜索能力不足的問題，增強算法處理優(yōu)先級約束的能力，本文提出使用拓撲圖的編碼方式的遺傳算法，使算法能夠處理任務(wù)之間的優(yōu)先級約束，使算法在搜索的過程中不會產(chǎn)生不可行解，并在初始化種群時加入先驗知識，引導(dǎo)算法的優(yōu)化，通過這兩種方式提高算法搜索能力；其次，針對算法在處理更大規(guī)模問題時搜索效率下降的問題，采用基于滾動調(diào)度的策略，對問題進行分解以減小求解問題的規(guī)模，并增強算法對動態(tài)環(huán)境的反應(yīng)能力。

1 問題描述

圖1　代表一個任務(wù)組的DAG

問題的方案包括每個機器人執(zhí)行任務(wù)的順序以及任務(wù)的起始時間與結(jié)束時間，通過這兩部分確定每個機器人執(zhí)行任務(wù)的時間表。為了得到滿足上述約束的解決方案，本文采用混合整數(shù)線性規(guī)劃建立了該問題的全局優(yōu)化模型描述，式（1）～（12）為該問題的混合整數(shù)規(guī)劃（Mixed-Integer Linear Programming， MILP）模型：

問題的主要特點是需要在多個機器人協(xié)作的任務(wù)中考慮任務(wù)的優(yōu)先級約束；主要難點是當問題的規(guī)模增大時，在合理的時間內(nèi)得到更高質(zhì)量的解。

2 本文算法

求解上述問題具有一定的挑戰(zhàn)性，因為當問題規(guī)模增大時，更多的變量和線性約束使上述模型變得更加復(fù)雜［20，27］。面對這類復(fù)雜的問題，遺傳算法能夠在合理的時間內(nèi)得到高質(zhì)量的解。因此本文提出一種用于MRTA的算法ACGARS。本文算法的整體框架如圖2所示。整個算法主要有兩個部分：一部分是改進遺傳算法，包括使用基于DAG的編碼方式和在初始化種群中加入先驗知識，從而使算法能更直接高效地處理優(yōu)先級約束并提高算法的搜索能力；另一部分則是優(yōu)化問題的求解方式，采用基于滾動調(diào)度策略的方式，利用基于分解的思想將大規(guī)模的問題分解為一系列任務(wù)組窗口問題，再使用遺傳算法進行多次求解，而非直接對整個問題使用遺傳算法進行求解，從而減小求解問題的規(guī)模，提高算法的求解效率。

圖2　本文算法的整體框架

2.1　改進遺傳算法

改進遺傳算法的流程如圖3所示。首先使用基于優(yōu)先無環(huán)圖的編碼方式生成初始種群；其次使用基于規(guī)則的啟發(fā)式算法生成的方案作為先驗知識，并將這些方案編碼為個體加入初始種群；再次算法為種群內(nèi)的每個個體計算適應(yīng)度函數(shù)，并使用選擇算子根據(jù)適應(yīng)度選擇用于生成子代的個體；繼次通過使用變異算子對選取的個體進行操作的方式生成新一代種群的個體；最后根據(jù)是否滿足終止條件決定是繼續(xù)循環(huán)生成下一代個體，或是終止循環(huán)并輸出當前種群中最優(yōu)個體對應(yīng)的方案。

圖3　改進遺傳算法的流程

2.1.1編碼方式

圖4　分配矩陣確定執(zhí)行任務(wù)的機器人團隊示例

最終的優(yōu)化目標是最小化所有任務(wù)組的平均完成時間。因此，設(shè)置適應(yīng)度函數(shù)為每個染色體所對應(yīng)解的目標函數(shù)。因為在搜索過程中不會生成不可行解，所以不需要在適應(yīng)度函數(shù)中設(shè)置懲罰項函數(shù)。

圖5　根據(jù)DAG與調(diào)度矩陣確定任務(wù)的執(zhí)行順序示例

2.1.2種群初始化

在生成初始種群的過程中，為了提高算法效率，算法使用啟發(fā)式算法產(chǎn)生的解作為先驗知識加入初始種群。具體的實現(xiàn)方式為：首先不同的啟發(fā)式算法生成對應(yīng)的解，再將這些解編碼成染色體，最后將這些染色體加入初始化的種群。算法選用文獻［19，28］中的啟發(fā)式算法作為先驗知識，同時作為后續(xù)實驗的對比算法。

2.1.3操作算子

圖6　交叉算子示意圖

圖7　突變算子示意圖

通過上述的操作算子可以生成子代種群，然后在父代種群中，選取最好的個體直接復(fù)制到子代種群中，并替換最差的個體。這種精英保留策略能夠讓遺傳算法更快地收斂。

2.2　基于任務(wù)組窗口的滾動調(diào)度策略

雖然改良后的遺傳算法在搜索效率上有了較大的提高，但是隨著機器人與任務(wù)組數(shù)增加，問題規(guī)模也在增大。為了高效地求解大規(guī)模的問題，本文借鑒了文獻［29］中的思想設(shè)計了基于任務(wù)組窗口的滾動調(diào)度策略，將大規(guī)模的問題分解為一系列小規(guī)模的子問題。滾動調(diào)度策略流程如圖8所示。

圖8　基于任務(wù)組窗口的滾動調(diào)度策略的流程

首先，算法根據(jù)任務(wù)組的工作量選取一定數(shù)量的任務(wù)組（選取的任務(wù)組集合即為任務(wù)組窗口）；其次，采用改進的遺傳算法為任務(wù)組窗口內(nèi)的任務(wù)生成調(diào)度方案；最后，機器人根據(jù)調(diào)度方案執(zhí)行任務(wù)。在機器人執(zhí)行任務(wù)的過程中，如果有一個任務(wù)組的所有任務(wù)都被完成，則將該任務(wù)組從窗口中移除，再選取一個未被執(zhí)行的任務(wù)組加入任務(wù)組窗口，并再次調(diào)用遺傳算法重新為窗口內(nèi)的所有任務(wù)生成調(diào)度方案。這個過程需重復(fù)進行，直到將所有任務(wù)組完成?；谶@種策略，每次遺傳算法只需為一部分任務(wù)組而非問題內(nèi)的所有任務(wù)組生成調(diào)度方案，雖然犧牲了全局最優(yōu)性，但減小了遺傳算法所需要求解的問題規(guī)模，提高了算法的求解效率和對動態(tài)環(huán)境的適應(yīng)性，增強了算法的實用性。

3 實驗與結(jié)果分析

3.1　實驗設(shè)置

為了驗證本文算法的效果，進行數(shù)值仿真實驗。所有實驗在操作系統(tǒng)為Windows 10，編程語言為Python的環(huán)境下進行。為了生成隨機的MRTA問題實例，本文使用文獻［30］中的方法生成代表任務(wù)組的DAG。每個任務(wù)組的任務(wù)數(shù)隨機選取，范圍為［5，10］。每個任務(wù)的總工作負載從［10 000，15 000］的整數(shù)中采樣。機器人在屬于不同任務(wù)之間轉(zhuǎn)移的時間為1 000單位時間。

為了驗證本文算法的效果，將本文算法與構(gòu)造性啟發(fā)式算法（Constructive Heuristic Algorithm， CHA）［19］、最小化干擾算法（MinInterfere Algorithm， MIA）［28］和基于懲罰策略的遺傳算法（GAPS）［20］進行比較，其中CHA、MIA為基于規(guī)則的啟發(fā)式算法。出于驗證算法各模塊效果的目的，本文對使用不同模塊的算法進行命名：只使用DAG編碼的遺傳算法命名為改進遺傳算法（Improved Genetic Algorithm， IGA）；使用先驗知識與DAG編碼的遺傳算法則稱為帶先驗知識的改進遺傳算法（Improved Genetic Algorithm with Priori Knowledge， IGAPK）。為保證實驗公平，所有遺傳算法的參數(shù)都統(tǒng)一設(shè)置為：種群規(guī)模為40，迭代次數(shù)為200，交叉率為0.7，突變率為0.5。其中，種群規(guī)模、交叉率和突變率參照文獻［20，31］確定；迭代次數(shù)設(shè)置為200的依據(jù)是在實驗中觀察到的能夠確保兩個對比算法穩(wěn)定收斂的最小值；優(yōu)化的目標函數(shù)值為所有任務(wù)組的平均完成時間。

3.2　實驗結(jié)果與分析

3.2.1基于DAG的編碼與先驗知識對算法的提升

首先，為了驗證基于DAG的編碼方式效果，本文將IGA與GAPS求解同一問題實例，并觀察兩者的求解效果。實例中，機器人數(shù)為5，任務(wù)組數(shù)為1，任務(wù)的優(yōu)先級關(guān)系如圖1所示。每個任務(wù)需要的機器人數(shù)從［2，5］中隨機選取。圖9為兩個算法生成方案對應(yīng)的甘特圖，圖10為兩個算法在迭代過程中最優(yōu)目標函數(shù)的變化情況。

圖9　兩個算法生成方案對應(yīng)的甘特圖

圖10　兩個算法迭代過程中目標函數(shù)最優(yōu)值的變化

從圖9、10中可見，IGA在整個迭代過程中的最優(yōu)值都優(yōu)于GAPS，表明使用DAG編碼的遺傳算法能夠更快地得到高質(zhì)量的求解方案。初始時，IGA的最優(yōu)值遠小于GAPS，這是因為IGA采用基于DAG的編碼方式，所以算法的初始種群中的解都滿足任務(wù)之間的優(yōu)先級約束；而GAPS算法處理優(yōu)先級約束的方式是在違背約束的解的適應(yīng)性函數(shù)中增加懲罰函數(shù)，它的編碼方式并沒有考慮優(yōu)先級約束。由于GAPS生成初始種群時不考慮優(yōu)先級約束，所以它初始種群中有許多的解違背了任務(wù)的優(yōu)先級約束，這些違背約束的解的適應(yīng)值也增加了懲罰項，使得這些初始解的最優(yōu)值遠大于IGA的初始解的最優(yōu)值。

為了進一步說明基于DAG的編碼方式與加入先驗知識的效果，本文在機器人數(shù)為5的情況下，即在小規(guī)模問題下測試有無先驗知識的情況下的遺傳算法的效果，并與GAPS與啟發(fā)式算法進行比較。本文為不同的任務(wù)組規(guī)模生成10個問題實例用于測試，并計算測試結(jié)果的平均值作為結(jié)果。從表1中可以看到，當任務(wù)組數(shù)為1時，IGA相較于CHA、MIA和GAPS，目標函數(shù)分別減少了6.40%、4.61%和3.45%；當任務(wù)組數(shù)為2時，目標函數(shù)分別減少了13.84%、10.64%和25.71%；當任務(wù)組數(shù)為3時，目標函數(shù)分別減少了18.62%、13.06%和38.06%。這說明采用IGA得到的方案質(zhì)量更高，隨著任務(wù)組規(guī)模增加，質(zhì)量的提升更顯著。此外，在當任務(wù)組數(shù)為2和3時，IGAPK的目標函數(shù)相較于IGA分別減少了2.02%和1.64%。這表明加入先驗知識初始化后，IGAPK的性能相較于IGA有了進一步的提升。

表1小規(guī)模問題上不同算法的目標函數(shù)值對比

Tab.1　Comparison of objective function values of different algorithms on small-scale problems

3.2.2基于任務(wù)組的滾動調(diào)度策略對算法的提升

為了驗證滾動調(diào)度策略在大規(guī)模問題下的效果，在機器人數(shù)為20的情況下，在不同任務(wù)組數(shù)下比較遺傳算法使用與不使用滾動調(diào)度策略的效果，并與其他算法進行比較。每個任務(wù)需要的機器人數(shù)從［4，11］隨機選取。本文為不同的任務(wù)組規(guī)模生成10個問題實例用于測試，并計算測試結(jié)果的平均值作為結(jié)果，在ACGARS中，任務(wù)組窗口的寬度設(shè)置為2個任務(wù)組，結(jié)果如表2所示。從表2中可見，當任務(wù)組數(shù)為10時，ACGARS相較于CHA、MIA、GAPS和IGAPK，目標函數(shù)分別減少了26.75%、17.42%、64.89%和14.96%；當任務(wù)組數(shù)為15時，目標函數(shù)分別減少了27.82%、17.22%、69.35%和17.04%；當任務(wù)組數(shù)為20時，目標函數(shù)分別減少了30.02%、16.86%、75.65%和16.34%?？梢杂^察到，在大規(guī)模的問題下，GAPS的性能相較于其他算法顯著下降，這是因為GAPS生成個體時不考慮任務(wù)優(yōu)先級約束，在問題規(guī)模增大的情況下，任務(wù)的優(yōu)先級約束更復(fù)雜，此時生成的個體更容易違背任務(wù)優(yōu)先級約束，即使對違背約束的個體的適應(yīng)度函數(shù)施加懲罰函數(shù)也難以搜尋到高質(zhì)量的可行解，最終使它搜索效果變差。此外，從表2中還可以看到，IGAPK的性能相較于啟發(fā)式算法雖然仍有一定的優(yōu)勢，但相較于在較小規(guī)模下的實驗結(jié)果，生成方案的質(zhì)量相較于啟發(fā)式算法的優(yōu)勢程度有較明顯的下降。原因是即使IGAPK的搜索效率相較于GAPS有提高，但所要搜索的解的數(shù)量隨著問題規(guī)模呈指數(shù)增長，IGAPK仍難以在短時間內(nèi)為大規(guī)模的問題生成高質(zhì)量的解。使用基于任務(wù)組的滾動調(diào)度策略的ACGARS的性能相較于IGAPK有了提升，這是因為滾動調(diào)度策略雖然犧牲了整體的最優(yōu)性導(dǎo)致理論上難以找到全局最優(yōu)解，但減少了所需要搜索的解的數(shù)量，算法能在短時間內(nèi)找到高質(zhì)量的解。這也驗證了在大規(guī)模問題下使用滾動調(diào)度策略的必要性。

表2大規(guī)模問題上不同算法的目標函數(shù)值對比

Tab.2　Comparison of objective function values of different algorithms on large-scale problems

最后，為了驗證滾動調(diào)度策略對算法處理動態(tài)能力的影響，本文比較了IGAPK與ACGARS在求解相同規(guī)模問題時所需要的CPU時間，并與其他算法進行比較。如表3所示，可以發(fā)現(xiàn)，在使用滾動調(diào)度策略后，ACGARS在求解3個規(guī)模的問題所需的CPU時間相較于IGAPK分別縮短了76.05%、85.94%和91.81%。上述結(jié)果采用滾動調(diào)度策略能夠縮短算法所需的CPU計算時間，從而能夠在短時間內(nèi)作出決策，增強了算法處理動態(tài)問題的能力。雖然計算時間相較于CHA、MIA這兩個啟發(fā)式算法長，但ACGARS的求解質(zhì)量相較于CHA、MIA有明顯提升，所以是可以接受的。

表3大規(guī)模問題上不同算法的CPU耗時對比 單位：s

Tab.3　Comparison of CPU time consumption of different algorithms on large-scale problems unit：s

3.3　計算復(fù)雜性分析

4 結(jié)語

針對已有遺傳算法面對智能工廠中大規(guī)模多約束MRTA問題求解效果一般的問題，提出了結(jié)合遺傳算法和滾動調(diào)度的MRTA算法（ACGARS）。首先采用基于DAG的編碼方式，使得產(chǎn)生的解能滿足任務(wù)優(yōu)先級約束，提高算法的搜索效率；其次使用基于規(guī)則的啟發(fā)式算法生成的方案作為先驗知識加入初始種群，以進一步提高搜索效率；最后使用滾動調(diào)度策略，減小每次求解問題的規(guī)模。實驗結(jié)果表明，本文算法優(yōu)于現(xiàn)有的啟發(fā)式與遺傳算法，提高了多機器人團隊的生產(chǎn)效率。下一步的研究工作考慮將更多的實際約束加入到問題中求解。

[1] LI X， LI D， WAN J， et al. A review of industrial wireless networks in the context of Industry 4.0 ［J］. Wireless Networks， 2017， 23（1）： 23-41.

[2] LIANG G， LUO H， LI M， et al. FreeBOT： a freeform modular self-reconfigurable robot with arbitrary connection point-design and implementation［C］// Proceedings of the 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway： IEEE， 2020： 6506-6513.

[3] CHEN K-C， LIN S-C， HSIAO J-H， et al. Wireless networked multirobot systems in smart factories ［J］. Proceedings of the IEEE， 2020， 109（4）： 468-494.

[4] WANG S， WAN J， ZHANG D， et al. Towards smart factory for industry 4.0： a self-organized multi-agent system with big data based feedback and coordination ［J］. Computer Networks， 2016， 101： 158-168.

[5] FECZKO J， MANKA M， KROL P， et al. Review of the modular self reconfigurable robotic systems［C］// Proceedings of the 2015 10th International Workshop on Robot Motion and Control. Piscataway： IEEE， 2015： 182-187.

[6] 趙輝，郝夢雅，王紅君，等. 基于資源拍賣的農(nóng)業(yè)多機器人任務(wù)分配［J］.計算機應(yīng)用與軟件，2021，38（12）：286-290，313.（ZHAO H， HAO M Y， WANG H J， et al. Cooperative task allocation of agricultural multi-robot based on resource auction［J］. Computer Applications and Software， 2021，38（12）：286-290，313.）

[7] KIM J， SON H I. A Voronoi diagram-based workspace partition for weak cooperation of multi-robot system in orchard ［J］. IEEE Access， 2020， 8： 20676-20686.

[8] NIKITENKO A， LAVENDELIS E， EKMANIS M， et al. Task allocation methods for homogeneous multi-robot systems： feed pushing case study ［J］. Automatic Control and Computer Sciences， 2018， 52： 371-381.

[9] 林思夢. 基于粒子群算法的災(zāi)后救援多機器人任務(wù)分配［D］.徐州：中國礦業(yè)大學，2020： 2.（LIN S M. Multi-robot task allocation for rescue after disaster based on particle swarm optimization algorithm［D］. Xuzhou： China University of Mining and Technology， 2020： 2.）

[10] MOURADIAN C， SAHOO J， GLITHO R H， et al. A coalition formation algorithm for multi-robot task allocation in large-scale natural disasters ［C］// Proceedings of the 2017 13th International Wireless Communications and Mobile Computing Conference. Piscataway： IEEE， 2017： 1909-1914.

[11] GUNN T， ANDERSON J. Dynamic heterogeneous team formation for robotic urban search and rescue ［J］. Journal of Computer and System Sciences， 2015， 81（3）： 553-567.

[12] 李鑫濱，章壽濤，閆磊，等. 基于魯棒Restless Bandits模型的多水下自主航行器任務(wù)分配策略［J］.計算機應(yīng)用，2019，39（10）：2795-2801.（LI X B， ZHANG S T， YAN L， et al. Multiple autonomous underwater vehicle task allocation policy based on robust Restless Bandit model［J］. Journal of Computer Applications， 2019，39（10）：2795-2801.）

[13] CARRENO Y， PAIRET è， PETILLOT Y， et al. A decentralized strategy for heterogeneous AUV missions via goal distribution and temporal planning ［C］// Proceedings of the 2020 International Conference on Automated Planning and Scheduling. Palo Alto： AAAI Press， 2020： 431-439.

[14] GUO X， HU J， CHEN J， et al. Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment ［J］. IEEE Robotics and Automation Letters， 2021， 6（4）： 8349-8356.

[15] KORASH G A， STENTZ A， DIAS M B. A comprehensive taxonomy for multi-robot task allocation ［J］. The International Journal of Robotics Research， 2013， 32（12）：1495-1512.

[16] 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.

[17] KORSAH G A， KANNAN B， BROWNING B， et al. xBots： an approach to generating and executing optimal multi-robot plans with cross-schedule dependencies［C］// Proceedings of the 2012 IEEE International Conference on Robotics and Automation. Piscataway： IEEE， 2012： 115-122.

[18] WANG Z， GOMBOLAY M. Learning scheduling policies for multi-robot coordination with graph attention networks ［J］. IEEE Robotics and Automation Letters， 2020， 5（3）： 4509-4516.

[19] BISCHOFF E， MEYER F， INGA J， et al. Multi-robot task allocation and scheduling considering cooperative tasks and precedence constraints［C］// Proceedings of the 2020 IEEE International Conference on Systems， Man， and Cybernetics. Piscataway： IEEE， 2020： 3949-3956.

[20] BISCHOFF E， TEUFEL J， INGA J， et al. Towards interactive coordination of heterogeneous robotic teams — introduction of a reoptimization framework ［C］// Proceedings of the 2021 IEEE International Conference on Systems， Man， and Cybernetics. Piscataway： IEEE， 2021： 1380-1386.

[21] MILORADOVI? B， ?üRüKLü B， EKSTR?M M， et al. A genetic algorithm approach to multi-agent mission planning problems［C］// Proceedings of the 2020 9th International Conference on Operations Operations Research and Enterprise Systems. Cham： Springer， 2020： 109-134.

[22] MILORADOVI? B， ?üRüKLü B， EKSTR?M M， et al. Extended colored traveling salesperson for modeling multi-agent mission planning problems ［C］// Proceedings of the 2019 8th International Conference on Operations Research and Enterprise Systems. Cham： Springer， 2019： 237-244.

[23] QI B， PU L， XU C， et al. Multi-robot task assignment method in the construction waste sorting system ［C］// Proceedings of the 2022 IEEE International Conference on Mechatronics and Automation. Piscataway： IEEE， 2022： 1364-1369.

[24] CECHINEL A K， DE PIERI E R， FERNANDES PEREZ A L， et al. Multi-robot task allocation using island model genetic algorithm ［J］. IFAC-PapersonLine， 2021， 54（1）： 558-563.

[25] 范學滿，薛昌友，張會.基于多種群遺傳算法的多UUV任務(wù)分配方法［J］.水下無人系統(tǒng)學報，2022，30（5）：621-630.（FAN X M， XUE C Y， ZHANG H. Task assignment method for multiple UUVs based on multi-population genetic algorithm ［J］. Journal of Unmanned Undersea Systems，2022，30（5）：621-630.）

[26] RAMCHURN S D， POLUKAROV M， FARINELLI A， et al. Coalition formation with spatial and temporal constraints［C］// Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems. New York： ACM， 2010，3： 1181-1188.

[27] KOES M， NOURBAKHSH I， SYCARA K， et al. Heterogeneous multi-robot coordination with spatial and temporal constraints［C］// Proceedings of the 20th National Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2005： 1292-1297.

[28] ZHANG Y， PARKER L E. Multi-robot task scheduling［C］// Proceedings of the 2013 IEEE International Conference on Robotics and Automation. Piscataway： IEEE， 2013： 2992-2998.

[29] 方劍，席裕庚.周期性和事件驅(qū)動的Job Shop滾動調(diào)度策略［J］.控制與決策，1997， 12（2）：159-162，166.（FANG J， XI Y G. A periodic and event-driven rolling horizon job shop scheduling strategy［J］. Control and Decision， 1997， 12（2）：159-162，166.）

[30] SUSLOVA E， FAZLI P. Multi-robot task allocation with time window and ordering constraints［C］// Proceedings of the 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway： IEEE， 2020： 6909-6916.

[31] ENTEZARI Z， MAHOOTCHI M. Developing a mathematical model for staff routing and scheduling in home health care industries： genetic algorithm-based solution scheme ［J］. Scientia Iranica， 2021， 28（6）： 3692-3718.

Multi-robot task allocation algorithm combining genetic algorithm and rolling scheduling

DENG Fuqin1，2， HUANG Huanzhao1， TAN Chaoen1， FU Lanhui1， ZHANG Jianmin1， LAM Tinlun2*

（1，，529020，；2，，，518116，）

The purpose of research on Multi-Robot Task Allocation （MRTA） is to improve the task completion efficiency of robots in smart factories. Aiming at the deficiency of the existing algorithms in dealing with large-scale multi-constrained MRTA， an MRTA Algorithm Combining Genetic Algorithm and Rolling Scheduling （ACGARS） was proposed. Firstly， the coding method based on Directed Acyclic Graph （DAG） was adopted in genetic algorithm to efficiently deal with the priority constraints among tasks. Then， the prior knowledge was added to the initial population of genetic algorithm to improve the search efficiency of the algorithm. Finally， a rolling scheduling strategy based on task groups was designed to reduce the scale of the problem to be solved， thereby solving large-scale problems efficiently. Experimental results on large-scale problem instances show that compared with the schemes generated by Constructive Heuristic Algorithm （CHA）， MinInterfere Algorithm （MIA）， and Genetic Algorithm with Penalty Strategy （GAPS）， the scheme generated by the proposed algorithm has the average order completion time shortened by 30.02%， 16.86% and 75.65% respectively when the number of task groups is 20， which verifies that the proposed algorithm can effectively shorten the average waiting time of orders and improve the efficiency of multi-robot task allocation.

multi-robot task allocation; genetic algorithm; smart factory; Directed Acyclic Graph (DAG); rolling scheduling strategy

This work is partially supported by National Key Research and Development Program “Intelligent Robot” Key Project （2020YFB1313300）， Shenzhen Science and Technology Program （KQTD2016113010470345）， Exploratory Research Project of Shenzhen Institute of Artificial Intelligence and Robotics for Society （AC01202101103）， Wuyi University Horizontal Research Project （33520098）.

DENG Fuqin， born in 1982， Ph. D.， senior engineer. His research interests include machine learning， mobile robotic systems and multi-robot systems.

HUANG Huanzhao， born in 1998， M. S. candidate. His research interests include multi-robot task allocation.

TAN Chaoen， born in 1999， M. S. candidate. His research interests include multi-robot path planning.

FU Lanhui， born in 1987， Ph. D.， lecturer. His research interests include machine learning， image information processing.

ZHANG Jianmin， born in 1981， M. S.， lecturer. His research interests include machine learning， mobile robotic systems and multi-robot systems.

LAM Tinlun， born in 1984， Ph. D.， assistant professor. His research interests include modular self-reconfigurable robots， multi-robot systems.

TP242

A

1001-9081（2023）12-3833-07

10.11772/j.issn.1001-9081.2022121916

2023?01?04；

2023?02?21；

2023?02?22。

國家重點研發(fā)計劃“智能機器人”重點專項（2020YFB1313300）；深圳市科技計劃項目（KQTD2016113010470345）；深圳市人工智能與機器人研究院探索性研究項目（AC01202101103）；五邑大學橫向課題項目（33520098）。

鄧輔秦（1982—），男，湖南郴州人，高級工程師，博士，主要研究方向：機器學習、移動機器人系統(tǒng)與多機器人系統(tǒng)；黃煥釗（1998—），男，廣東汕頭人，碩士研究生，主要研究方向：多機器人任務(wù)分配；譚朝恩（1999—），男，廣東順德人，碩士研究生，主要研究方向：多機器人路徑規(guī)劃；付蘭慧（1987—），女，河南新鄉(xiāng)人，講師，博士，主要研究方向：機器學習、圖像信息處理；張建民（1981—），男，河北滄州人，講師，碩士，主要研究方向：機器學習、移動機器人系統(tǒng)與多機器人系統(tǒng)；林天麟（1984—），男，香港人，助理教授，博士，CCF會員，主要研究方向：模塊化自重構(gòu)機器人、多機器人系統(tǒng)。