改進布谷鳥搜索算法在多機器人任務(wù)分配及路徑規(guī)劃中的應(yīng)用

謝永盛 曾簫瀟* 馮文健

1(廣西科技師范學院數(shù)學與計算機科學學院 廣西 來賓 546100)2(柳州鐵道職業(yè)技術(shù)學院 廣西 柳州 545616)

0 引 言

隨著智能技術(shù)的發(fā)展，機器人已被應(yīng)用于各個領(lǐng)域，然而單個機器人對一些復雜任務(wù)并不能滿足人類需求，繼而產(chǎn)生多機器人系統(tǒng)。多機器人任務(wù)分配(Multi-Robot Task Allocation,MRTA)是多機器人系統(tǒng)研究中的基本問題，隨著機器人和任務(wù)難度的增加，任務(wù)分配問題變得越來越重要[1]。多機器人任務(wù)分配及路徑規(guī)劃是根據(jù)已有的任務(wù)目標，尋找機器人最佳位置，使其無重復并以較優(yōu)的路徑遍歷所有任務(wù)目標，行駛距離最短或消耗能量最低，以此來提高機器人的工作效率。近年來一些智能算法用來求解MRTA問題，比如遺傳算法[2]、蟻群算法[3-6]、Pareto改進算法[7]、蜜蜂算法[8-9]等，這些方法分別從不同角度對多機器人任務(wù)分配及路徑規(guī)劃進行探討。本文使用布谷鳥搜索算法研究了多機器人任務(wù)分配及路徑規(guī)劃方法，任務(wù)分配方法是使r個機器人到其分配的任務(wù)點距離最短建立數(shù)學模型，然后使用改進布谷鳥搜索算法在任務(wù)點中尋找最佳機器人位置；在任務(wù)分配點的基礎(chǔ)之上再采用改進布谷鳥搜索算法進行路徑規(guī)劃，使其遍歷路徑最短，并為多機器人續(xù)航能量提供科學依據(jù)。

1 多機器人任務(wù)分配問題的數(shù)學模型

本文研究的是在t個任務(wù)點中搜索r個機器人的位置，使得r個機器人到其分配的任務(wù)點距離最短，同時滿足每一個任務(wù)點只能由一個機器人服務(wù)。故機器人選址的數(shù)學模型如下：

(1)

(2)

uij∈{0,1}

(3)

i=1,2,…,rj=1,2,…,t

(4)

式中：J為目標函數(shù)；r表示機器人數(shù)目；t表示任務(wù)數(shù)目；distij表示第i個機器人與第j個任務(wù)點之間的距離；uij為1時表示第j個任務(wù)點由第i個機器人負責。式(2)和式(3)為約束條件，表示每一個任務(wù)點只能由一個機器人負責。

2 基本布谷鳥搜索算法

基本布谷鳥搜索算法(Cuckoo Search algorithm，CS)由Yang等[10]于2009年提出，該算法通過Levy飛行尋窩和以一定的概率拋棄鳥巢來模擬布谷鳥尋窩產(chǎn)卵的過程。其迭代公式為：

(5)

3 改進布谷鳥搜索算法求解多機器人任務(wù)分配

3.1 編 碼

多機器人任務(wù)分配是個離散問題，而基本的布谷鳥是為解決連續(xù)問題而提出的，因此應(yīng)將其離散化。依然對鳥巢的位置采用浮點編碼，然后將其升或降序排序則得到整數(shù)序列，例如，10個任務(wù)點3個機器人的任務(wù)分配位置編碼，如表1所示。

表1 機器人位置編碼

3.2 改進策略

上述編碼方式雖然提高了機器人位置的多樣性，對小規(guī)模多機器人分配問題可以取得全局最優(yōu)解，但對大規(guī)模多機器人分配問題的求解結(jié)果仍不理想。于是采用融合遺傳算法中的選擇、交叉和變異操作，其中選擇和交叉操作中均采用精英策略，即保留當前最優(yōu)解。實施步驟如算法1所示。

算法1改進布谷鳥搜索算法

Step1按表1方式初始化種群信息及參數(shù)設(shè)置。

Step2利用式(1)計算目標函數(shù)值和最優(yōu)解。

Step3根據(jù)式(5)獲取新的鳥巢，重新計算目標函數(shù)值和最優(yōu)解，如果較之前的值優(yōu)越則進行替換。

Step4以一定的概率棄巢，重新計算目標函數(shù)值和最優(yōu)解，如果較之前的值優(yōu)越則進行替換。

Step5對當前鳥巢進行遺傳算子操作，重新計算目標函數(shù)值和最優(yōu)解，如果較之前的值優(yōu)越則進行替換。

Step6判斷是否到達終止條件，如果是，輸出最優(yōu)值和最優(yōu)解，否則跳轉(zhuǎn)至Step 3。

4 改進布谷鳥搜索算法求解多機器人任務(wù)分配的路徑規(guī)劃

通過算法1可以求得每一個機器人的任務(wù)分配，要求機器人執(zhí)行每一個任務(wù)點有且只有一次的路徑，并使路徑總長度最短(能量消耗最低)，該問題歸結(jié)為多旅行商問題(MTSP)。

4.1 全局搜索

智能算法在種群迭代的過程中均朝最優(yōu)解靠攏，式(5)針對離散問題需要重新定義為：

(6)

4.2 局部搜索

為了增強算法的局部搜索能力，對當前機器人的執(zhí)行順序進行交換、逆序和插入操作。

4.3 編 碼

假設(shè)第i個鳥巢的位置定義為：xi=(xi1,xi2,…,xin)，其中n為任務(wù)點的數(shù)目，(xi1,xi2,…,xin)是(1,2,…,n)的一個置換，則第i只布谷鳥執(zhí)行路徑的順序為：xi1→xi2→…→xin。

4.4 評價函數(shù)

機器人執(zhí)行每一個任務(wù)點有且只有一次的路徑，并使路徑總長度最短(能量消耗最低)可由式(7)來計算：

(7)

式中：d(ci,ci-1)為任務(wù)點ci與ci-1之間的距離，i=1,2,…,n-1；d(cn,c1)為cn與c1之間的距離。

4.5 改進策略

(1) 模擬退火算法的Metropolis準則。設(shè)w為初始解，計算目標值f(w)，布谷鳥算法運行后的新解w1，計算目標值f(w1)，Δf=f(w1)-f(w)，如果Δf≤0，則w=w1；f(w)=f(w1)；否則按Metropolis準則接受新解。

(2) 2-opt領(lǐng)域結(jié)構(gòu)。2-opt是一種快速求解TSP問題的有效算法，它依次交換路徑中不相鄰的兩個結(jié)點，若D(a，c)+D(a，d)

因此，在算法1的基礎(chǔ)上應(yīng)用改進布谷鳥搜索算法求解路徑規(guī)劃，其實施步驟如算法2所示。

算法2用于求解路徑規(guī)劃的改進布谷鳥搜索算法

Step1依據(jù)算法1求解的每一個機器人任務(wù)分配點集合，按4.3節(jié)編碼方式初始化種群信息及參數(shù)設(shè)置。

Step2利用式(7)計算目標函數(shù)值和最優(yōu)解。

Step3執(zhí)行4.1節(jié)全局搜索和4.2節(jié)局部搜索，重新計算目標函數(shù)值，然后按模擬退火算法的Metropolis準則接受差解，如果目標函數(shù)值比最優(yōu)值優(yōu)越則替換最優(yōu)值和最優(yōu)解。

Step4對種群中的每一個個體采用2-opt操作，重新計算目標函數(shù)值，如果較之前的值優(yōu)越則替換最優(yōu)值和最優(yōu)解。

Step5計算溫度的衰減值。

Step6判斷是否到達終止條件，如果是，輸出最優(yōu)值和最優(yōu)解，否則跳轉(zhuǎn)至Step 3。

5 仿真實驗與結(jié)果分析

為驗證所提算法在多機器人任務(wù)分配及路徑規(guī)劃的正確性及有效性，所有的實驗均運行在操作系統(tǒng)為Windows 10、處理器為Intel i7、內(nèi)存為8 GB的PC上，以MATLAB 2010a編寫代碼。

實驗一40個任務(wù)6個機器人問題(隨機生成40個任務(wù)點)，在40個任務(wù)點中選擇6個機器人位置。參數(shù)設(shè)置為：種群規(guī)模20，迭代次數(shù)50，棄巢率0.25。分別用基本布谷鳥搜索算法和算法1進行求解，每個算法獨立運行20次，計算結(jié)果如表2-表4所示。

表2 兩種算法計算結(jié)果比較

表3 CS求解機器人位置及任務(wù)分配

表4 算法1求解機器人位置及任務(wù)分配

從表2可知，無論是最優(yōu)值、平均值還是最差值，本文設(shè)計的算法1均優(yōu)于CS算法；從表3和表4可知，算法1求解的機器人位置和任務(wù)分配點發(fā)生了變化，求解效果優(yōu)于CS算法，比如機器人位置為14，表示機器人放置第14個任務(wù)點處，機器人位置和任務(wù)分配如圖1和圖2所示。由于任務(wù)點個數(shù)較少，未應(yīng)用算法2對其任務(wù)點進行路徑規(guī)劃，算法1對小規(guī)模問題雖然體現(xiàn)出優(yōu)勢但不夠明顯，繼續(xù)實驗。

圖1 CS算法求解的機器人位置及任務(wù)分配

圖2 算法1求解的機器人位置及任務(wù)分配

實驗二100個任務(wù)6個機器人問題(隨機生成100個任務(wù)點)，在100個任務(wù)點中選擇6個機器人位置。參數(shù)設(shè)置與實驗一相同。分別使用基本布谷鳥搜索算法和算法1進行求解，每個算法獨立運行20次，計算結(jié)果如表5-表7所示。

表5 兩種算法計算結(jié)果比較

表6 CS求解機器人位置及任務(wù)分配

續(xù)表6

表7 算法1求解機器人位置及任務(wù)分配

從表5可知，無論是最優(yōu)值、平均值還是最差值，本文設(shè)計的算法1均優(yōu)于CS算法；從表6和表7可知，算法1求解的機器人位置和任務(wù)分配點發(fā)生了根本變化，求解效果優(yōu)于CS算法，機器人位置和任務(wù)分配圖如圖3和圖4所示，實驗表明，任務(wù)點數(shù)目越多，算法1的優(yōu)越性越明顯。

圖3 CS算法求解機器人位置及任務(wù)分配

圖4 算法1求解機器人位置及任務(wù)分配

利用算法1求得每個機器人最佳位置后，再用算法2對任務(wù)分配點進行路徑規(guī)劃，以第17個位置為例，共有26個任務(wù)分配點，分別用CS算法和算法2獨立運行20次進行求解(計算兩點間的距離進行了取整操作)。參數(shù)設(shè)置：模擬退火算法溫度初始值T=5，溫度衰減因子?=0.99，其他參數(shù)設(shè)置與實驗一相同，所得計算結(jié)果如表8所示。

表8 兩種算法計算結(jié)果比較

從表8可知，本文設(shè)計的算法2求解的結(jié)果無論是最優(yōu)值、平均值還是最差值均優(yōu)于CS算法，且每次均達到了全局最優(yōu)值，優(yōu)越性明顯，單個機器人路徑規(guī)劃效果圖如圖5-圖6所示。從圖5可知，CS算法路徑規(guī)劃效果較差，出現(xiàn)了交叉現(xiàn)象。說明路徑規(guī)劃沒有達到最優(yōu)解，而算法2路徑規(guī)劃消除了交叉現(xiàn)象。多機器人路徑規(guī)劃效果如圖7所示。

圖5 CS算法求解單機器人路徑規(guī)劃

圖6 算法2求解單機器人路徑規(guī)劃

圖7 算法2求解多機器人路徑規(guī)劃

算法2針對100個任務(wù)6個機器人問題，求解的機器人最優(yōu)位置及最低能量如表9所示。假設(shè)所有機器人單位能量消耗均為1，則本文設(shè)計的算法求解機器人最優(yōu)位置為17、56、21、16、83、79任務(wù)點，每個機器人最低能量至少為202、147、112、159、89、155。

表9 算法2計算機器人位置及最低能量

實驗三200個任務(wù)6個機器人問題(隨機生成200個任務(wù)點)，即在200個任務(wù)點中選擇6個機器人位置。參數(shù)設(shè)置：種群規(guī)模20，迭代次數(shù)100，棄巢率0.25。針對大規(guī)模問題，僅用改進布谷鳥搜索算法求解任務(wù)分配及路徑規(guī)劃。算法1求解機器人位置和任務(wù)分配點如表10所示，算法1求解任務(wù)分配圖如圖8所示，算法2求解的多機器人路徑規(guī)劃如圖9所示。

表10 算法1求解的機器人位置及任務(wù)分配

圖8 算法1求解機器人位置及任務(wù)分配

圖9 算法2求解多機器人路徑規(guī)劃

算法2針對200個任務(wù)6個機器人問題，求解的機器人最優(yōu)位置及最低能量如表11所示，假設(shè)所有機器人單位能量消耗均為1，則本文設(shè)計的算法求解機器人最優(yōu)位置為45、149、139、135、148、178任務(wù)點，每個機器人最低能量至少為306、182、198、115、156、202。

表11 算法2計算機器人位置及最低能量

上述所有實驗結(jié)果表明，本文設(shè)計的算法比基本布谷鳥搜索算法性能優(yōu)越，對多機器人任務(wù)分配及路徑規(guī)劃所需能量消耗最低，并為機器人續(xù)行能量提供科學依據(jù)。

6 結(jié) 語

本文研究了多機器人任務(wù)分配及路徑規(guī)劃問題，針對基本布谷鳥搜索算法求解該問題時效果差，提出一種改進布谷鳥搜索算法。求解該問題的過程分為兩步：第一步使用算法1實現(xiàn)多機器人的最佳位置及最佳任務(wù)分配方案；第二步在任務(wù)分配的基礎(chǔ)之上使用算法2實現(xiàn)路徑規(guī)劃。3個不同規(guī)模的仿真實驗表明，本文設(shè)計的算法保證機器人執(zhí)行任務(wù)代價最小，獲得利益最大，同時為多機器人續(xù)航能量提供了科學依據(jù)。