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

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

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

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

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

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

0 引言

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

在智能工廠的多機(jī)器人系統(tǒng)中，需要控制數(shù)量龐大的機(jī)器人，目標(biāo)是合理規(guī)劃機(jī)器人執(zhí)行計(jì)劃，最小化訂單的平均等待時(shí)間，從而快速響應(yīng)需求。因此在設(shè)計(jì)、構(gòu)建和使用多機(jī)器人系統(tǒng)時(shí)，需要解決的一個(gè)問題是：系統(tǒng)中各個(gè)機(jī)器人在各個(gè)時(shí)刻分別應(yīng)該選取什么動(dòng)作，執(zhí)行什么任務(wù)？即多機(jī)器人任務(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］等。本文重點(diǎn)研究智能工廠背景下的MRTA問題。在該問題中，機(jī)器人每次只能執(zhí)行一個(gè)任務(wù)，每個(gè)任務(wù)需要多個(gè)機(jī)器人組成團(tuán)隊(duì)協(xié)同執(zhí)行。由于任務(wù)數(shù)較多，機(jī)器人需要在不同的時(shí)間內(nèi)完成多個(gè)任務(wù)；此外，任務(wù)之間存在優(yōu)先級(jí)關(guān)系，所以機(jī)器人執(zhí)行任務(wù)的情況不僅與自身有關(guān)，還會(huì)受到其他機(jī)器人的影響［15］，使得高質(zhì)量調(diào)度方案的生成較難。根據(jù)文獻(xiàn)［16］，該MRTA問題在iTax分類法下屬于單任務(wù)機(jī)器人、多機(jī)器人任務(wù)和包含跨時(shí)間表依賴的時(shí)間擴(kuò)展分配類型的MRTA問題。

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

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

1 問題描述

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

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

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

2 本文算法

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

圖2　本文算法的整體框架

2.1　改進(jìn)遺傳算法

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

圖3　改進(jìn)遺傳算法的流程

2.1.1編碼方式

圖4　分配矩陣確定執(zhí)行任務(wù)的機(jī)器人團(tuán)隊(duì)示例

最終的優(yōu)化目標(biāo)是最小化所有任務(wù)組的平均完成時(shí)間。因此，設(shè)置適應(yīng)度函數(shù)為每個(gè)染色體所對應(yīng)解的目標(biāo)函數(shù)。因?yàn)樵谒阉鬟^程中不會(huì)生成不可行解，所以不需要在適應(yīng)度函數(shù)中設(shè)置懲罰項(xiàng)函數(shù)。

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

2.1.2種群初始化

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

2.1.3操作算子

圖6　交叉算子示意圖

圖7　突變算子示意圖

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

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

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

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

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

3 實(shí)驗(yàn)與結(jié)果分析

3.1　實(shí)驗(yàn)設(shè)置

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

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

3.2　實(shí)驗(yàn)結(jié)果與分析

3.2.1基于DAG的編碼與先驗(yàn)知識(shí)對算法的提升

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

[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è)多機(jī)器人任務(wù)分配［J］.計(jì)算機(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] 林思?jí)? 基于粒子群算法的災(zāi)后救援多機(jī)器人任務(wù)分配［D］.徐州：中國礦業(yè)大學(xué)，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］.計(jì)算機(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] 范學(xué)滿，薛昌友，張會(huì).基于多種群遺傳算法的多UUV任務(wù)分配方法［J］.水下無人系統(tǒng)學(xué)報(bào)，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ū)動(dòng)的Job Shop滾動(dòng)調(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。

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

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