結合遺傳算法和滾動調度的多機器人任務分配算法

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

結合遺傳算法和滾動調度的多機器人任務分配算法

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

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

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

多機器人任務分配；遺傳算法；智能工廠；有向無環圖；滾動調度策略

0 引言

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

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

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

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

1 問題描述

圖1　代表一個任務組的DAG

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

問題的主要特點是需要在多個機器人協作的任務中考慮任務的優先級約束；主要難點是當問題的規模增大時，在合理的時間內得到更高質量的解。

2 本文算法

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

圖2　本文算法的整體框架

2.1　改進遺傳算法

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

圖3　改進遺傳算法的流程

2.1.1編碼方式

圖4　分配矩陣確定執行任務的機器人團隊示例

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

圖5　根據DAG與調度矩陣確定任務的執行順序示例

2.1.2種群初始化

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

2.1.3操作算子

圖6　交叉算子示意圖

圖7　突變算子示意圖

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

2.2　基于任務組窗口的滾動調度策略

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

圖8　基于任務組窗口的滾動調度策略的流程

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

3 實驗與結果分析

3.1　實驗設置

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

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

3.2　實驗結果與分析

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

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

圖9　兩個算法生成方案對應的甘特圖

圖10　兩個算法迭代過程中目標函數最優值的變化

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

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

表1小規模問題上不同算法的目標函數值對比

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

3.2.2基于任務組的滾動調度策略對算法的提升

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

表2大規模問題上不同算法的目標函數值對比

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

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

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

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

3.3　計算復雜性分析

4 結語

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

[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] 趙輝，郝夢雅，王紅君，等. 基于資源拍賣的農業多機器人任務分配［J］.計算機應用與軟件，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] 林思夢. 基于粒子群算法的災后救援多機器人任務分配［D］.徐州：中國礦業大學，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模型的多水下自主航行器任務分配策略［J］.計算機應用，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任務分配方法［J］.水下無人系統學報，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] 方劍，席裕庚.周期性和事件驅動的Job Shop滾動調度策略［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。

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

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