改進布谷鳥搜索算法在多機器人任務分配及路徑規劃中的應用

謝永盛 曾簫瀟* 馮文健

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

0 引 言

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

1 多機器人任務分配問題的數學模型

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

(1)

(2)

uij∈{0,1}

(3)

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

(4)

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

2 基本布谷鳥搜索算法

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

(5)

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

3.1 編 碼

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

表1 機器人位置編碼

3.2 改進策略

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

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

Step1按表1方式初始化種群信息及參數設置。

Step2利用式(1)計算目標函數值和最優解。

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

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

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

Step6判斷是否到達終止條件，如果是，輸出最優值和最優解，否則跳轉至Step 3。

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

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

4.1 全局搜索

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

(6)

4.2 局部搜索

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

4.3 編 碼

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

4.4 評價函數

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

(7)

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

4.5 改進策略

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

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

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

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

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

Step2利用式(7)計算目標函數值和最優解。

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

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

Step5計算溫度的衰減值。

Step6判斷是否到達終止條件，如果是，輸出最優值和最優解，否則跳轉至Step 3。

5 仿真實驗與結果分析

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

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

表2 兩種算法計算結果比較

表3 CS求解機器人位置及任務分配

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

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

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

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

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

表5 兩種算法計算結果比較

表6 CS求解機器人位置及任務分配

續表6

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

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

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

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

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

表8 兩種算法計算結果比較

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

圖5 CS算法求解單機器人路徑規劃

圖6 算法2求解單機器人路徑規劃

圖7 算法2求解多機器人路徑規劃

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

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

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

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

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

圖9 算法2求解多機器人路徑規劃

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

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

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

6 結 語

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