基于CVT和模擬退火的多機器人均勻部署

嚴李平，吳玉秀，張文忠

（安徽工業大學 電氣與信息工程學院，安徽 馬鞍山 243032）

0 引 言

在災害救援搜索，大面積環境監測，臨時網絡動態構建等方面，多機器人在空間的擴展性上較單個機器人有明顯的優勢。本文針對上述問題，對機器人均勻部署覆蓋的問題進行研究。

涉及到多機器人覆蓋在模擬圖形區域，面臨了如何分割圖形使得每個機器人的覆蓋面積一致以及如何分配多機器人到分割的區域的問題。對于圖形分割，基于生成元的Voronoi 圖分割，由于生成元的不確定性，導致圖形分割的不均勻，每個機器人覆蓋的面積不均勻，無法滿足多機器人對圖形的模擬。文獻[3]中提到一種基于螢火蟲群優化的傳感器部署方案，擴大了傳感器的覆蓋范圍，但區域冗余的可能性很大。文獻[4]研究了基于投標的優化算法，提高了覆蓋率且減少了重疊覆蓋，文獻[5]中調整傳感半徑，使相鄰的兩兩傳感器之間的重復覆蓋減少。文獻[6]采用了沃羅諾伊-螢火蟲群優化-K-means 算法提高了網絡覆蓋率。本文借助傳感網絡覆蓋的思想，采用質心Voronoi 劃分對模擬的圖形來對圖形的覆蓋。對于多機器人多任務分配是指用一種方案把多個任務分給多個機器人，以達到總的任務執行方案時間最短、消耗最少、任務完成度最高等目的。本文所需要考慮問題是機器人行走的總路程最少，類似于TSP 問題。文獻[8]提到一種改進蟻群遺傳算法，提高了TSP 問題的效率。文獻[9]和文獻[10]提出針對旅行商問題的改進交叉算子遺傳算法，收斂度有一定提升，提高了遺傳算法的效率和高質量的解。鑒于本文的要求，一個機器人只需要去完成一個任務，故將問題轉化為背包限制的旅行商問題。如今，一個機器人完成一個任務的任務分配問題用得最多的就是拍賣算法。單物品拍賣算法具有局部最優解的窘境，對于組合優化問題并不適用，可改進為組合拍賣，這是一個NP 難題。故本文使用模擬退火算法來解決多機器人多目標優化問題。

本文的目標是實現多機器人在某個圖形區域來完成均勻部署，首先通過采用質心Voronoi 來完成對目標區域的劃分，得到部署點的位置，然后采用模擬退火方法，對這些部署點進行分配，使得多機器人到達每個部署點的總路程最近。

1 目標的生成

機器人要完成某一區域中均勻部署，首先需對此區域進行均勻劃分。該處采用質心Voronoi 方法，將待部署區域的劃分為多個小區域，每個小區域的質心即為機器人的目標位置。

1.1 Voronoi 圖

Voronoi 圖是基于Delauany 三角對于空間限定區域采用節點中垂線相連接方法組成的區域劃分。在一個平面隨機散（（1，2，…，））個點，對相鄰兩個點做中垂線，即可獲取多個多邊形，并且形狀可能存在不一，這樣使得各多邊形均存在一個點，多邊形中任意一點到形成這個多邊形的點距離最近。如圖1所示。

圖1 泰森多邊形

對一個平面圖形，有如下公式：

1.2 質心Voronoi 圖

“形心沃羅諾伊鑲嵌法”用于實現形心沃羅諾伊圖的原理，在計算上非常有效。這些圖將任意維空間中任意形狀的區域細分成任意數量的幾乎均勻的子體積。

給定一個區域?R和這個區域的密度函數，則這個區域的質心公式如下：

當個生成元與其每個重合時，這樣的Voronoi 劃分稱為質心Voronoi 劃分，如圖2所示。

圖2 質心Voronoi 圖

2 模擬退火算法任務分配

多機器人任務分配問題主要有四種情況：

（1）單目標機器人：一個機器人只能到達一個目標點。

（2）多目標機器人：一個機器人有多個需要到達的目標點。

（3）單機器人目標：一個目標點只需要一個機器人到達。

（4）多機器人目標：一個目標點可以由多機器人到達。

此處主要研究單目標機器人，機器人數量和任務數一樣多，即每個機器人有且僅有一個任務（目標）需要執行。

2.1 任務的描述

假設機器人數量個集合為={，，…，R}，任務數量也為個={，，…，T}，此處的任務可以描述為：將個目標唯一的分配給個機器人，即上述分配問題可以用元置換π：{1，2，…，}→{1，2，…，}來表示，定義置換矩陣：

定義→執行任務的代價矩陣：

其中：C為機器人R到任務點T的歐式距離。令：

任務分配目標函數定義為：

2.2 模擬退火算法

2.2.1 爬山法

爬山算法是一種模仿爬山的過程，首先任意指定一個點上山，然后附近選擇一個點，若這個點得到結果更優，即選擇這個點為下個點，這樣結果向著更優方向移動，直到山頂。若有多個山峰，爬山算法步入局部最優解，根據初始點位置可得是否獲取全局最優解。若初始點在全局最優解臨近，這樣就可以獲得最優解。

2.2.2 模擬退火

為防止爬山法陷入全局最優，Kirkpatrick 等提出了模擬退火算法（SA）。此此算法由Metropolis 算法和退火過程兩個部分組成。Metropolis 算法（即Metropolis 準則）是描述一種以概率來接受新解的方法，它可以使解脫離局部最優的困境，是一種非完全確定準則。利用退火在初始進行擴展搜索，預防進入局部最優；而到了后期則需要擴大局部搜索，方便更快獲取最優解。對本文的問題求解基本過程如下：

（1）對目標函數隨機生成一個初始解，計算初始解的函數值（）；

（2）在初始解的附近需要對目標函數隨機生成一個解，計算解的函數值（）；

（3）將（）、（）兩個函數值進行比較，若（）＜（），則將解賦值給解，然后重復（2）步驟；若（）≥（），那么將計算接受的概率，的計算公式如下：

然后生成一個[0，1]之間的隨機數，如果＜，就將解賦值給解，然后重復（2）的步驟，否則，不將解賦值給解，重復（2）步驟。

上述（3）中，Δ為|（）-（）|，T為衰減函數，T=αT-1 其中為常數，可以取值為0.5～0.99，它的取值決定了降溫過程。

2.2.3 模擬退火新解產生的規則

根據目標函數及約束條件，生成一個隨機初始解，然后在初始解附近產生一個新解，產生新解的規則有以下三種；

交換法：隨機生成兩個交換點的位置，互換這兩個位置上的點。例：

解：7 8 6 |3 2 |5 4 1

新解：7 8 6 5 2 3 4 1

移位法：隨機生成三個點的位置、、，將到之間的點包括和位置上的點放置到位置點后，如下：

解：7 |8 6 |3 2 5 |4 1

新解：7 2 5 4 8 6 3 1

倒置法：隨機生成兩個點的位置，這兩點的位置形成一個區間，將這個區間里的點順序調換，例：

解：7 8 |6 3 2 |5 4 1

新解：7 8 5 2 3 6 4 1

3 目標生成及分配的偽代碼

本文的圖形劃分采用的是質心Voronoi 劃分，采用模擬退火算法對目標點進行分配，目標生成的偽代碼為：

▲Procedures CVT： 偽代碼Begin initialize n,sample_num,r[],dim_num;//生成元數量，隨機種子數，r[]//儲生成元位置，維度get(n,sample_num);//獲取生成元的初始位置及種子的位置while(i ＜= iterate) do distance();//計算種子到各個生成元位置的距離find（）； //每個種子找到離自己最近距離的生成元for j = 1 to n do r1(1:dim_num,j)=r2(1:dim_num,j)/count(j);//計算新生成元位置end for Update generator locationr[];//更新生成元位置end while voronoi(x,y);//畫出質心voronoi end目標分配的偽代碼為：▲Procedures SA： 偽代碼begin initialize Path0,Distance0,T;//初始路徑,距離及初始溫度while(t ＜= maxgen) do //maxgen 為外循環的次數for i = 1 to LK do //LK 為內循環的次數Path1=gen_new_path(Path0);//生成新路徑Path1 Distance1 of Path1;//計算新路徑距離if＜Distance1＜Distance0＞ //判斷新路徑與初始路徑的距離Path0=Path1； //得到下代路徑Distance0=Distance1；else以一定概率接受新路徑;end if end for Update temperature T;//更新當前溫度if (T＜0.0001) //終止條件判斷break；end if end while end

4 實驗仿真與結果

4.1 算法驗證

為了驗證本文提出的算法，給出3 種不規則圖形的部署區域如圖3所示。在Matlab 環境中，分別用不同數量的機器人數量對圖3（a）（b）和（c）中的“L”“T”和“Star”-形進行部署仿真。

圖3 部署區域

對圖形進行質心Voronoi 劃分得到所需要的目標點，即任務點。如圖4所示。

圖4 質心Voronoi 分割圖

圖4為不同圖形，不同節點的質心Voronoi 分割圖，圖4（a）、4（b）、4（c）分別為10、50、100 個點在“L”-形中的質心Voronoi 分割圖，圖4（d）、4（e）、4（f）分別為10、50、100 個點在“T”-形中的質心Voronoi 分割圖，圖4（g）、4（h）、4（i）分別為20、50、100 個點在“Star”-形中的質心Voronoi 分割圖，每個質心點的位置就是機器人目標點的位置，通過模擬退火算法對機器人的目標點進行分配，得到平面上的多機器人到目標點的總路徑。目標分配如圖5所示。

圖5中為不同圖形，不同目標節點的分配圖，圖5（a）、5（b）、5（c）分別為10、50、100 個機器人分配到“L”-形中位置的圖，圖5（d）、5（e）、5（f）分別為10、50、100 個機器人分配到“T”-形中位置的圖，圖5（g）、5（h）、5（i）分別為20、50、100 個機器人分配到“Star”-形中位置的圖。

圖5 目標分配圖

4.2 算法對比

在同樣的機器人初始位置下，在Matlab 2017b 中運用遺傳算法、模擬退火算法、單物品拍賣算法對圖形目標點進行分配，得到路徑距離數據，對這些數據進行處理，然后在Origin 2018 中對處理后的數據進行多Y 軸畫圖，如圖6所示。

圖6 “L”形-多Y 軸圖

從圖6、圖7、圖8中可以看到，橫軸為機器人的數量，縱軸為機器人的路徑長度。圖6是三種算法機器人到“L”-形下的路徑長度對比，當機器人數量為10、35、50、75、100時，模擬退火所得的平均路徑長度波動分別為0、±0.000 9、±0.004 4、±0.013 6、±0.030 8；遺傳算法所得的平均路徑長度波動分別為±0.345 1、±2.815 6、±6.640 2、±6.582 0、±11.061 6；單物品拍賣算法平均路徑長度無變化。圖7是三種算法機器人到“T”-形下的路徑長度對比，當機器人數量為10、35、50、75、100 時，模擬退火所得的平均路徑長度波動分別為0、±0.008 8、±0.002 6、±0.046 8、±0.066 9；遺傳算法所得的平均路徑長度波動分別為±0.189 6、±0.499 6、±1.945 2、±2.811 3、±4.024 1；單物品拍賣算法平均路徑長度無變化。圖8是三種算法機器人到“star”-形下的路徑長度對比，由于機器人的最小數量隨著圖形復雜度變大而增多，所以“star”-形的機器人最小數量選取為20，當機器人數量為20、35、50、75、100時，模擬退火所得的平均路徑長度波動分別為0、±0.060 5、±0.180 2、±0.426 9、±0.824 2；遺傳算法所得的平均路徑長度波動分別為±6.150 7、±6.247 4、±11.539 9、±27.796 3、±37.342 4；單物品拍賣算法平均路徑長度無變化。

圖7 “T”形-多Y 軸圖

圖8 “star”形-多Y 軸圖

在Matlab 2017b 中運用遺傳算法、模擬退火算法、單物品拍賣算法對不同數量的機器人進行目標分配，收斂時間如表1所示。

表1 三種算法收斂速度表

上述表1可以看出，再任何機器人數量下遺傳算法的收斂時間都要比模擬退火的收斂時間長。在機器人數量較少時，拍賣算法的收斂時間比模擬退火的收斂時間都較快，隨著機器人數量的增加，拍賣算法的收斂時間比模擬退火的收斂時間要慢很多。

由路徑長度和收斂時間的對比可得出：在相同機器人數量，相同初始位置下的機器人分配到同一個圖形下，模擬退火算法和單物品拍賣得到的總路徑長度比遺傳算法得到的總路徑長度要穩定，幾乎沒有方差，模擬退火算法在上述三個方法中得到了最短的總路徑長度且收斂時間較短，避免了單物品拍賣和遺傳算法可能得不到全局最優解的缺陷，較穩定。

5 結 論

本文采用了質心Voronoi 圖劃分出了所模擬圖形目標點的位置，對于多機器人多目標分配，本文給出了以最短總路徑為目標，以每個機器人有且僅有一個任務需要執行為約束條件的模型，且使用了三種算法對多機器人進行目標分配，讓其單機器人執行單任務。通過對上述算法進行驗證和對比，驗證了模擬退火算法在求路徑最短問題的優越性。本文后續的研究將圍繞機器人的軌跡規劃、跟蹤和機器人之間的沖突消解展開。