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

嚴李平，吳玉秀，張文忠

（安徽工業(yè)大學(xué) 電氣與信息工程學(xué)院，安徽 馬鞍山 243032）

0 引 言

在災(zāi)害救援搜索，大面積環(huán)境監(jiān)測，臨時網(wǎng)絡(luò)動態(tài)構(gòu)建等方面，多機器人在空間的擴展性上較單個機器人有明顯的優(yōu)勢。本文針對上述問題，對機器人均勻部署覆蓋的問題進行研究。

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

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

1 目標的生成

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

1.1 Voronoi 圖

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

圖1 泰森多邊形

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

1.2 質(zhì)心Voronoi 圖

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

給定一個區(qū)域?R和這個區(qū)域的密度函數(shù)，則這個區(qū)域的質(zhì)心公式如下：

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

圖2 質(zhì)心Voronoi 圖

2 模擬退火算法任務(wù)分配

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

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

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

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

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

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

2.1 任務(wù)的描述

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

定義→執(zhí)行任務(wù)的代價矩陣：

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

任務(wù)分配目標函數(shù)定義為：

2.2 模擬退火算法

2.2.1 爬山法

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

2.2.2 模擬退火

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

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

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

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

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

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

2.2.3 模擬退火新解產(chǎn)生的規(guī)則

根據(jù)目標函數(shù)及約束條件，生成一個隨機初始解，然后在初始解附近產(chǎn)生一個新解，產(chǎn)生新解的規(guī)則有以下三種；

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

解：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

倒置法：隨機生成兩個點的位置，這兩點的位置形成一個區(qū)間，將這個區(qū)間里的點順序調(diào)換，例：

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

新解：7 8 5 2 3 6 4 1

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

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

▲Procedures CVT： 偽代碼Begin initialize n,sample_num,r[],dim_num;//生成元數(shù)量，隨機種子數(shù)，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);//畫出質(zhì)心voronoi end目標分配的偽代碼為：▲Procedures SA： 偽代碼begin initialize Path0,Distance0,T;//初始路徑,距離及初始溫度while(t ＜= maxgen) do //maxgen 為外循環(huán)的次數(shù)for i = 1 to LK do //LK 為內(nèi)循環(huán)的次數(shù)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 實驗仿真與結(jié)果

4.1 算法驗證

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

圖3 部署區(qū)域

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

圖4 質(zhì)心Voronoi 分割圖

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

圖5中為不同圖形，不同目標節(jié)點的分配圖，圖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 中運用遺傳算法、模擬退火算法、單物品拍賣算法對圖形目標點進行分配，得到路徑距離數(shù)據(jù)，對這些數(shù)據(jù)進行處理，然后在Origin 2018 中對處理后的數(shù)據(jù)進行多Y 軸畫圖，如圖6所示。

圖6 “L”形-多Y 軸圖

從圖6、圖7、圖8中可以看到，橫軸為機器人的數(shù)量，縱軸為機器人的路徑長度。圖6是三種算法機器人到“L”-形下的路徑長度對比，當機器人數(shù)量為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”-形下的路徑長度對比，當機器人數(shù)量為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”-形下的路徑長度對比，由于機器人的最小數(shù)量隨著圖形復(fù)雜度變大而增多，所以“star”-形的機器人最小數(shù)量選取為20，當機器人數(shù)量為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 中運用遺傳算法、模擬退火算法、單物品拍賣算法對不同數(shù)量的機器人進行目標分配，收斂時間如表1所示。

表1 三種算法收斂速度表

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

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

5 結(jié) 論

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