基于能量懲罰的多機(jī)器人任務(wù)分配優(yōu)化方法

朱良恒，梁利東，賈文友，蘇學(xué)滿

基于能量懲罰的多機(jī)器人任務(wù)分配優(yōu)化方法

朱良恒，*梁利東，賈文友，蘇學(xué)滿

（安徽工程大學(xué)機(jī)械工程學(xué)院，安徽，蕪湖 241000）

針對多機(jī)器人任務(wù)分配中存在的能量消耗不均衡問題，提出了基于能量懲罰策略的遺傳算法完成任務(wù)分配與任務(wù)序列的優(yōu)化過程。首先，建立多機(jī)器人任務(wù)分配的數(shù)學(xué)模型，每項(xiàng)任務(wù)設(shè)定不同的難度系數(shù)，以機(jī)器人完成任務(wù)所消耗的總能量為優(yōu)化目標(biāo)，并確定安全能量的約束條件；然后在每次迭代中通過計(jì)算每個(gè)機(jī)器人相對平均能耗的超額進(jìn)行能量懲罰以尋求能量均衡的最優(yōu)解。仿真實(shí)驗(yàn)表明，在總能量消耗最低的尋優(yōu)中有效提高了各機(jī)器人的能量平衡性。

多任務(wù)分配；遺傳算法；能量懲罰

0 引言

近年來，機(jī)器人在越來越多領(lǐng)域得到廣泛應(yīng)用，對于解決復(fù)雜的多任務(wù)問題，單機(jī)器人已不能滿足實(shí)際應(yīng)用的需求，因此多機(jī)器人系統(tǒng)已成為近年來的研究熱點(diǎn)和發(fā)展方向[1]。多機(jī)器人任務(wù)分配( Multi-Robot Task Allocation，MRTA) 是多機(jī)器人系統(tǒng)中重要的一部分，伴隨著任務(wù)難度與機(jī)器人數(shù)量的不斷增多，解決多機(jī)器人任務(wù)規(guī)劃問題涉及數(shù)值計(jì)算方法和最優(yōu)化理論，具有一定的研究意義和使用價(jià)值。

多機(jī)器人任務(wù)分配是將系統(tǒng)中多個(gè)任務(wù)分配給多機(jī)器人執(zhí)行，以完成任務(wù)總時(shí)間最短、總消耗能量最優(yōu)以及任務(wù)完成度最優(yōu)等為目標(biāo)[2]。近年來智能算法已廣泛用于求解MRTA問題，如遺傳算法[3]、蟻群算法[4-7]、蜜蜂算法[8-9]，布谷鳥搜索算法[10]等，其中文獻(xiàn)[4]在傳統(tǒng)蟻群算法中求解多機(jī)器人任務(wù)分配，收斂速度慢且易于陷入局部最優(yōu)問題的基礎(chǔ)上加入了局部優(yōu)化的變異算子以及加入改進(jìn)的模擬退火算法，仿真結(jié)果表明能夠很好的解決任務(wù)分配中的問題；文獻(xiàn)[10]利用改進(jìn)的布谷鳥搜索算法可以根據(jù)任務(wù)的位置點(diǎn)信息，找到最佳的機(jī)器人位置以此來解決多機(jī)器人任務(wù)分配及路徑規(guī)劃的問題。這些方法分別從不同方向?qū)Χ鄼C(jī)器人任務(wù)規(guī)劃問題進(jìn)行探究。集中式分配和分布式分配是任務(wù)規(guī)劃的主要方法，集中式任務(wù)分配模型包括多維旅行商模型[11]、多維動態(tài)網(wǎng)絡(luò)流優(yōu)化模型[12]、多維多選擇背包問題模型[13]以及相關(guān)模型的改進(jìn)，其中文獻(xiàn)[11]利用模擬退火算法解決多旅行商中城市約束問題。分布式任務(wù)分配模型主要有博弈論模型[14]，拍賣算法模型[15]等。

以上算法通常僅針對最優(yōu)消耗能量來解決任務(wù)分配問題，并未考慮到多機(jī)器人的能量均衡問題，因此本文基于遺傳算法引入能量懲罰策略求解多機(jī)器人能量均衡的最優(yōu)解，并通過仿真實(shí)驗(yàn)證明算法的有效性和可行性。

1 問題描述及數(shù)學(xué)模型

任務(wù)規(guī)劃問題是指分配出最優(yōu)或近似最優(yōu)的任務(wù)的順序與數(shù)量，使得每個(gè)機(jī)器人從起點(diǎn)開始執(zhí)行分配給自己的任務(wù)總消耗能量是近似最少的，但是可能會出現(xiàn)多機(jī)器人消耗能量值差異較大的情況。因此在數(shù)學(xué)模型中加入了懲罰機(jī)制，可保持總能量最優(yōu)的基礎(chǔ)上控制每個(gè)機(jī)器人能量消耗趨于均衡，以方便對機(jī)器人和設(shè)備的統(tǒng)一維護(hù)。

1）機(jī)器人的數(shù)量約束

為表現(xiàn)機(jī)器人依次執(zhí)行任務(wù)，因此要求每個(gè)機(jī)器人執(zhí)行多個(gè)任務(wù)且每個(gè)任務(wù)只需被一個(gè)機(jī)器人執(zhí)行，可表示為：

Q= 1或Q= 0

Q= 1表示第個(gè)機(jī)器人執(zhí)行第個(gè)任務(wù)；Q= 0則表示不執(zhí)行此任務(wù)。

機(jī)器人的序號。

任務(wù)的序號。

2）任務(wù)數(shù)量約束

4）機(jī)器人執(zhí)行任務(wù)的運(yùn)動距離

4）機(jī)器人所消耗的能量

A：每單位距離所消耗的能量，本文假設(shè)機(jī)器人均為勻速運(yùn)動即為定值。

5）安全能量約束

安全能量為了保證機(jī)器人在完成執(zhí)行任務(wù)后，確保能順利安全的回到初始點(diǎn)，故預(yù)留安全能量，具體表示如下：

6）目標(biāo)函數(shù)

文獻(xiàn)[16]在傳統(tǒng)遺傳算法的基礎(chǔ)上結(jié)合懲罰函數(shù)的方法根據(jù)系統(tǒng)超出量構(gòu)造新的目標(biāo)函數(shù)，解決由于目標(biāo)函數(shù)設(shè)計(jì)不當(dāng)造成系統(tǒng)反應(yīng)速度慢和不穩(wěn)定的問題。將系統(tǒng)的超出量作為懲罰項(xiàng)加入目標(biāo)函數(shù)中，懲罰函數(shù)構(gòu)造復(fù)雜，而且懲罰因子是連續(xù)變化的。本文與文獻(xiàn)[16]相比則根據(jù)每個(gè)機(jī)器人消耗能量超出平均值的機(jī)制來構(gòu)造懲罰能量，并設(shè)定一個(gè)可調(diào)整超出誤差閾值，能在總能量消耗最優(yōu)的基礎(chǔ)上輕松達(dá)到多目標(biāo)平衡，構(gòu)造相對簡單，可實(shí)施性更高，更貼切實(shí)際情況。

為保證各機(jī)器人的能量消耗趨于均衡，本文以消耗總能量和懲罰能量之和最小作為優(yōu)化目標(biāo)，表示為：

：能量百分比。

2 遺傳算法求解MRTA問題

2.1 基本遺傳算法描述

遺傳算法(Genetic algorithm,GA)是一種按照自然界適者生存、優(yōu)劣淘汰的遺傳機(jī)制演化的隨機(jī)性搜索算法，其主要特點(diǎn)表現(xiàn)為：直接對對象進(jìn)行操作，具有較好的全局搜索能力；采用概率化的搜尋方法，能夠自動獲得和指引優(yōu)化的搜索空間，自適應(yīng)調(diào)整搜索的方向，不需要特定的規(guī)則[17]。目前遺傳算法已經(jīng)應(yīng)用到組合優(yōu)化，車輛調(diào)度與自適應(yīng)控制方向，文獻(xiàn)[18]采用連續(xù)權(quán)重平均法的遺傳算法解決選擇公交車道和公交信號優(yōu)先控制的優(yōu)化模型，文獻(xiàn)[19]提出量子遺傳算法求解含有配送時(shí)間與車輛承重約束的動態(tài)車輛調(diào)度模型，求出了車輛最優(yōu)路徑。本文應(yīng)用遺傳算法優(yōu)化策略改進(jìn)目標(biāo)函數(shù)模型，求解出多任務(wù)分配在能量消耗最優(yōu)的基礎(chǔ)上保證各機(jī)器人能量消耗平衡。

2.2 編碼方法

2.3 適應(yīng)度函數(shù)

以最優(yōu)能量值與能量懲罰值之和作為適應(yīng)度函數(shù)。當(dāng)適應(yīng)度函數(shù)值越小時(shí)，種群越好，越易于遺傳到下一代，適應(yīng)度函數(shù)為：

當(dāng)進(jìn)行每一次迭代計(jì)算時(shí)，個(gè)體超出平均值后將給予能量懲罰，超出的越多，懲罰力度也會越大，使得每個(gè)機(jī)器人消耗能量向平衡角度發(fā)展。

2.4 選擇算子

選擇算子運(yùn)算根據(jù)輪盤賭來選擇，每個(gè)個(gè)體被選擇的概率與其適應(yīng)度函數(shù)值成反比。

適應(yīng)度函數(shù)的值越小，說明這個(gè)種群被選擇的概率越大，說明這個(gè)種群比較好，這組解中多機(jī)器人消耗的總能量低并且能量消耗也比較均衡。

2.5 交叉算子和變異算子

交叉運(yùn)算和變異運(yùn)算中每個(gè)個(gè)體是由任務(wù)的數(shù)量和任務(wù)的序列號組成。選擇兩個(gè)父體進(jìn)行交叉運(yùn)算，將父體中深色與淺色染色體片段交叉來構(gòu)成下一代以此來提高種群的多樣性。具體操作過程如圖1所示。

圖1 交叉操作過程結(jié)果圖

變異運(yùn)算是隨機(jī)選出一個(gè)父代，根據(jù)變異運(yùn)算概率和隨機(jī)選擇變異基因位置，使得機(jī)器人的任務(wù)數(shù)量和序列號得以改變，假設(shè)變異運(yùn)算選擇深色部分的基因型變異。變異操作過程結(jié)果如圖2所示。

圖2 變異操作過程結(jié)果圖

2.6 算法實(shí)現(xiàn)

本文算法的主要步驟：

Step1：初始種群以及參數(shù)設(shè)置；

Step2：計(jì)算適應(yīng)度函數(shù)值，并分析個(gè)體的優(yōu)劣；

Step3：計(jì)算迭代一次每個(gè)機(jī)器人消耗的能量，并計(jì)算平均值，并根據(jù)懲罰機(jī)制計(jì)算懲罰能量；

Step4：計(jì)算目標(biāo)函數(shù)值及每個(gè)機(jī)器人的能量標(biāo)準(zhǔn)差（用于分析能量消耗的均衡程度）；

Step5：在當(dāng)前群體中選擇較優(yōu)個(gè)體遺傳到下一代；通過交叉和變異操作產(chǎn)生新個(gè)體構(gòu)成下一代種群，繼續(xù)進(jìn)行迭代；

Step6：重復(fù)Step2～Step5的步驟，達(dá)到要求的迭代次數(shù)，從中選出一個(gè)最優(yōu)解并輸出多機(jī)器人的任務(wù)數(shù)量和任務(wù)序列。

具體流程圖如圖3所示。

圖3算法流程圖

3 仿真實(shí)驗(yàn)

實(shí)驗(yàn)環(huán)境如下：軟件采用Matlab R2019a，硬件包括：電腦設(shè)備名稱戴爾G3 3590；處理器Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz 2.59 GHz；機(jī)帶RAM8.00 GB；系統(tǒng)類型64 位操作系統(tǒng), 基于 x64 的處理器。

實(shí)驗(yàn)1：3個(gè)機(jī)器人任務(wù)規(guī)劃仿真結(jié)果

3個(gè)機(jī)器人執(zhí)行任務(wù)數(shù)量及任務(wù)序列號仿真結(jié)果如圖4所示，圖5為多機(jī)器人消耗能量和總能量曲線圖。具體實(shí)驗(yàn)運(yùn)行參數(shù)結(jié)果如表1所示。

圖4 3個(gè)機(jī)器人執(zhí)行任務(wù)數(shù)量和序列圖

圖5 3個(gè)機(jī)器人消耗能量和總能量曲線圖

表1 3個(gè)機(jī)器人本文算法與基本遺傳算法運(yùn)行參數(shù)比較

Table 1 Comparison of operation parameters between three robot algorithms and basic genetic algorithm

算法E1E2E3總能量標(biāo)準(zhǔn)差 本文算法220.1245.0204.6669.720.4 基本遺傳算法174.6308.1218.1700.868.1

數(shù)據(jù)結(jié)果表明：加入懲罰機(jī)制遺傳算法的總能量消耗相比未加入懲罰機(jī)制的總能量降低了4.4%，標(biāo)準(zhǔn)差也減少了70.0%?？梢姂土P機(jī)制不僅能讓系統(tǒng)消耗的總能量降低，而且使每個(gè)機(jī)器人消耗的能量也相對均衡。

實(shí)驗(yàn)2：4個(gè)機(jī)器人任務(wù)分配仿真結(jié)果

圖6為4個(gè)機(jī)器人執(zhí)行任務(wù)數(shù)量和任務(wù)序列號仿真結(jié)果，圖7為多機(jī)器人消耗能量和總能量曲線圖。算法運(yùn)行參數(shù)結(jié)果比較如表2所示。

圖6 4個(gè)機(jī)器人執(zhí)行任務(wù)數(shù)量和序列圖

圖7 4個(gè)機(jī)器人消耗能量和總能量曲線圖

表2 4個(gè)機(jī)器人本文算法與基本遺傳算法運(yùn)行參數(shù)比較

Table 2 Comparison of operation parameters of four robots and basic genetic algorithm

算法E1E2E3E4總能量標(biāo)準(zhǔn)差 本文算法180.4174.1181.1151.7687.313.8 基本遺傳算法110.5140.8271.7197.7720.770.9

通過對比加入懲罰機(jī)制消耗的總能量比未加入懲罰機(jī)制消耗的總能量減少4.6%，標(biāo)準(zhǔn)差也相比較低了80.5%。仿真結(jié)果證明基于懲罰機(jī)制的遺傳算法能夠有效的解決總能量消耗最優(yōu)及能量不均衡問題。

實(shí)驗(yàn)3：本文算法與文獻(xiàn)[16]算法仿真比較

為驗(yàn)證本文算法與文獻(xiàn)[16]中算法的性能差異，采用5個(gè)機(jī)器人，30個(gè)任務(wù)點(diǎn)，且遺傳算法中參數(shù)設(shè)置均相等進(jìn)行仿真驗(yàn)算。5個(gè)機(jī)器人消耗能量和均衡性比較如圖8所示。

圖8 5個(gè)機(jī)器人消耗能量和總能量曲線圖

從圖中可以直觀看出本文算法在迭代平穩(wěn)時(shí)消耗的總能量較低，且5個(gè)機(jī)器人消耗的能量曲線更集中，說明本文算法性能優(yōu)于文獻(xiàn)中的算法。具體運(yùn)行的參數(shù)如表3所示。

表3 5個(gè)機(jī)器人本文算法與文獻(xiàn)算法運(yùn)行參數(shù)比較

Table 3 Comparison of operation parameters between algorithms in this paper and those in literature for five robots

算法E1E2E3E4E5總能量標(biāo)準(zhǔn)差 本文算法141.6148.1145.091.9120.1646.723.6 文獻(xiàn)算法98.7165.1152.0126.6157.3699.727.2

4 結(jié)論

本文采用能量懲罰機(jī)制的遺傳算法對多機(jī)器人任務(wù)分配進(jìn)行研究，考慮到以消耗總能量為目標(biāo)函數(shù)分配任務(wù)時(shí)可能會導(dǎo)致每個(gè)機(jī)器人消耗能量不均勻的情況，所以在數(shù)學(xué)模型的設(shè)計(jì)上加上超出消耗能量平均值的懲罰機(jī)制，使得多機(jī)器人在執(zhí)行任務(wù)消耗總量最小的基礎(chǔ)上再讓每個(gè)機(jī)器人消耗的能量盡可能的均衡。從仿真結(jié)果來看此機(jī)制能夠很好地解決這一問題。

[1] 李功捷. 基于智能優(yōu)化的倉儲機(jī)器人任務(wù)分配研究[D].哈爾濱:哈爾濱工業(yè)大學(xué),2013.

[2] Chopra S，Notarstefano G，Rice M，et al. DistributedVersion of the Hungarian Method for a Multi-robot Assignment[J]. IEEE Transactions on Robotics,2017(99) :1-16.

[3] 朱明哲,孫丙宇.基于遺傳算法的工廠倉儲系統(tǒng)多AGV調(diào)度策略研究[J].電子技術(shù),2021,50(1):33-37.

[4] 秦新立,宗群,李曉瑜,等.基于改進(jìn)蟻群算法的多機(jī)器人任務(wù)分配[J].空間控制技術(shù)與應(yīng)用,2018, 44 (5): 55-59.

[5] 劉瑞軒.張永林.基于改進(jìn)蟻群算法的多自主式水下機(jī)器人任務(wù)分配[J].中國艦船研究,2018,13(6):107-112.

[6] 段勇,王宇,喻祥尤.基于免疫遺傳算法的多機(jī)器人環(huán)境探索[J].沈陽工業(yè)大學(xué)學(xué)報(bào),2018,40(3):299-303.

[7] 馮珊珊. 基于適應(yīng)度與蟻群分散搜索的多機(jī)器人任務(wù)分配[D].鄭州:鄭州大學(xué),2018.

[8] 田微. 基于動態(tài)粒子蜜蜂算法的群機(jī)器人任務(wù)分配方法研究[D].長春:吉林大學(xué),2017.

[9] 朱范炳. 基于蜂群算法與聚類的多機(jī)器人探索優(yōu)化研究[D].鄭州:中原工學(xué)院,2018.

[10] 謝永盛,曾簫瀟,馮文健.改進(jìn)布谷鳥搜索算法在多機(jī)器人任務(wù)分配及路徑規(guī)劃中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件, 2021, 38(2):285-290.

[11] 梁星星,馬揚(yáng),馮旸赫,等.面向多旅行商問題的多目標(biāo)模擬退火算法研究[J].南京師大學(xué)報(bào):自然科學(xué)版,2017 ,40 (3):80-86.

[12] 萬路軍,姚佩陽,稅冬東,等.多編組任務(wù)分配動態(tài)優(yōu)化模型及IVFSA算法求解[J].電光與控制, 2014, 21 (5): 43-49,57.

[13] Duenas A, Martinelly C D, Tincgy. Amultidimensional multiple-choice knapsack model for re-source allocation in a construction equipment manufac-turer setting using an evolutionary algorithm[J]. IFIP Advances in Information ＆ Communication Technology,2016,438: 539-546.

[14] Kanakia A,Tourib, Correll N.Modeling-multi-robot task allocation with limited information as global game[J]. Swarm Intelligence,2016,10 (2) :147-160.

[15] Luo L,Chakraborty N,Sycara K. Provably-good distributed algorithm for constrained multi-robot task assignment for grouped tasks[J]. IEEE Transac-tions on Robotics,2015,31(1) : 19-30．

[16] 高興泉,黃東冬,丁三毛.懲罰函數(shù)結(jié)合遺傳算法的PID參數(shù)優(yōu)化[J].吉林化工學(xué)院學(xué)報(bào),2021,38(3):57-60.

[17] 梁肖,周湘貞. 基于遺傳算法的小麥?zhǔn)崭顧C(jī)路徑智能優(yōu)化控制研究[J].農(nóng)機(jī)化研究,2018,40(2):56-60.

[18] 盧小林,潘述亮,鄒難.公交專用道選址與公交優(yōu)先控制組合優(yōu)化模型[J].上海交通大學(xué)學(xué)報(bào),2017,51(7):846-854.

[19] 陳瀟. 基于云平臺的物流配送車輛調(diào)度系統(tǒng)[D].西安:西安科技大學(xué),2020.

MULTI ROBOTS TASK ALLOCATION OPTIMIZATION METHOD BASED ON ENERGY PENALTY

ZHU Liang-heng,*LIANG Li-dong, JIA Wen-you, SU Xue-man

School of Mechanical Engineering, Anhui Polytechnic University, Wuhu, Anhui 241000, China）

In order to solve the problem of energy consumption imbalance in task allocation of multi robots, a genetic algorithm based on energy penalty strategy is proposed to optimize task allocation and task sequence. Firstly, the mathematical model of task assignment of multi robots is established. Each task is set with different difficulty coefficients. The total energy consumed by the robot to complete the task is the optimization goal. The constraints of the safety energy are determined. Then, in each iteration, the energy penalty is performed by calculating the excess energy consumption of each robot to find the optimal solution of energy balance. The simulation results show that the energy balance of each robot is effectively improved in the optimization of the lowest total energy consumption.

multitask assignment; genetic algorithm; energy penalty

1674-8085（2022）02-0088-06

TP242

A

10.3969/j.issn.1674-8085.2022.02.014

2021-09-07；

2021-11-26

安徽省教育廳科學(xué)技術(shù)研究項(xiàng)目（KJ2019A0147,KJ2018A0102）

朱良恒(1994-)，男，安徽淮北人，碩士生，主要從事智能計(jì)算與優(yōu)化設(shè)計(jì)研究(E-mail:zhu_liangheng@126.com)；

*梁利東(1972-），男，山西忻州人，副教授，博士，主要從事計(jì)算機(jī)輔助設(shè)計(jì)制造及信息工程等研究(E-mail:mark_liang2003@126.com).