基于混合粒子群算法的巡檢機器人路徑規(guī)劃

孫宗濤，朱永強

(青島理工大學 機械與汽車工程學院，山東 青島 266520)

近些年來，隨著計算機技術在機器人領域的廣泛應用，巡檢機器人開始逐漸出現(xiàn)于人類工作的各個領域。

機器人巡檢相對于人工巡檢優(yōu)點明顯，當為其規(guī)劃好一條巡視路徑后，機器人就可以在無人干預的條件下按照后臺指示完成相應的巡檢任務，這也可以減少人工巡檢的工作量。當天氣環(huán)境比較惡劣或工作區(qū)設備發(fā)生故障時，它還可以降低人們受傷的風險。

由此看來，為巡檢機器人找到一條合適的最短路徑就尤為重要。針對巡檢機器人路徑規(guī)劃問題，許多研究者提出了多種有效的算法，如A*算法[1]、遺傳算法[2]、粒子群算法[3]、人工狼群算法[4]、蟻群算法[5]等，這些算法均取得了一定成果，同時也存在著一些缺點。

鑒于此，針對巡檢機器人在工作區(qū)的路徑規(guī)劃問題，結合了粒子群算法的優(yōu)缺點，提出了基于遺傳算法改進的混和粒子群算法，通過遺傳算法中的交叉和變異策略與傳統(tǒng)粒子群算法的改進融合，采用取整交叉方法對個體與個體極值和群體極值進行交叉更新得到新粒子后，對自身進行變異從而得到更好的個體，以此種方式來搜索工作區(qū)節(jié)點之間路徑的最優(yōu)解。

1 建立數(shù)學模型

研究巡檢機器人路徑規(guī)劃的目的在于，當需要機器人在工作區(qū)中進行巡檢任務時，機器人根據(jù)自身當前所處位置以及工作區(qū)各個節(jié)點的位置信息，根據(jù)后臺要求采用一定的路徑搜索方法，快速尋找出一條耗時最短或路徑最短的優(yōu)化路徑，并沿著此最優(yōu)路徑經(jīng)過各個工作區(qū)節(jié)點，完成相應的巡視任務。

巡視機器人從某個起點出發(fā)，遍歷工作區(qū)中各個節(jié)點的問題，此過程可看作是一個典型的旅行商(TSP)問題。旅行商問題是一個經(jīng)典的組合優(yōu)化問題,主要用于求解商人有且僅有一次經(jīng)過N個城市并最終返回到起點的最短路徑[6]。如果城市節(jié)點大規(guī)模增加的話,該問題就不可能采用窮舉方式找到最優(yōu)解,稱為NP-Hard問題[7]。之后越來越多的學者逐步采用了啟發(fā)式算法和智能算法來求解問題,以替代早期的精確算法[8]。在巡視機器人的工作場景，其巡視的TSP問題可以被定義如下：當已知工作區(qū)各節(jié)點位置橫縱坐標位置時，巡視機器人從起點出發(fā)，遍歷經(jīng)過各個工作區(qū)節(jié)點一次，然后回到出發(fā)點，在巡視過程中找出一條距離最短的規(guī)劃路徑，即巡視中的優(yōu)化路徑滿足以下方程[9]。

(1)

(2)

其中：i,j為工作區(qū)兩個節(jié)點，i,j∈(1,2,…,n)；dis(i,j)為i,j兩節(jié)點間歐式距離；fpath為最短遍歷路徑。

2 混合粒子群算法

2.1 算法理論

粒子群算法(PSO)是一種啟發(fā)式隨機算法。鳥群中每一只鳥相當于粒子群算法中一個粒子。粒子有三項主要特征，即速度、位置與適應度函數(shù)值，適應度函數(shù)值可以通過優(yōu)化的目標函數(shù)計算而得到，之后粒子在規(guī)定的搜索空間中運動，從而尋找函數(shù)最優(yōu)解。設種群中初始的粒子數(shù)目為n，當它們在規(guī)定的N維空間中進行搜索時，傳統(tǒng)粒子群算法的更新公式如下：

(3)

(4)

傳統(tǒng)粒子群算法通過個體極值和群體極值來完成尋優(yōu)過程，操作比較簡單，收斂速度較快，但其也存在著比較明顯的缺點，當?shù)螖?shù)不斷變大時，種群會不斷收斂集中，存在于種群中的粒子相似程度也越來越高，這就導致了可能會發(fā)生陷入局部最優(yōu)解的情況[10]，所以有必要對傳統(tǒng)粒子群算法進行改進優(yōu)化。

混合粒子群算法通過將遺傳算法中的交叉和變異策略與傳統(tǒng)粒子群算法的改進融合，對算法進行優(yōu)化。在解決巡視機器人在工作區(qū)節(jié)點間巡視的問題中其適應度函數(shù)為遍歷節(jié)點的路徑長度，即：

(5)

其中：n為工作區(qū)節(jié)點數(shù)量，pathi,j為i,j兩節(jié)點之間路徑長度。

(1)交叉策略：采用取整交叉策略來將個體與個體極值或群體極值進行交叉更新，在獲得新粒子后通過比較新舊粒子的適應度函數(shù)值來保留適應度函數(shù)值更高的粒子來完成更新過程。

(2)變異策略：首先設定變異概率來對處于粒子種群中所有的粒子進行判斷是否需要變異，判定需要變異的粒子進行變異，在獲得新粒子后通過比較新舊粒子的適應度函數(shù)值來保留適應度函數(shù)值更高的粒子來完成更新過程，從而得到更好的粒子。

2.2 混合粒子群算法流程

引入遺傳算法中的交叉和變異策略的混合粒子群算法流程如圖1所示。

圖1 混合粒子群算法流程

3 試驗仿真分析

為了測試混合粒子群算法的性能，使用MATLAB軟件在70m×70m的巡視機器人工作區(qū)中設置了40個工作區(qū)節(jié)點。以遍歷所有工作區(qū)節(jié)點為前提，路徑距離最短為評價指標進行了仿真試驗，每種算法在一次試驗中都進行100次迭代。所設置巡視機器人二維工作區(qū)如圖2所示，圖中正方形塊為工作區(qū)各節(jié)點。

圖2 巡視機器人二維工作區(qū)模型

同時為了驗證混合粒子群算法的有效性，采用傳統(tǒng)粒子群算法、遺傳算法在同樣的工作區(qū)環(huán)境進行仿真試驗，比較三種算法的收斂速度、最短路徑距離。在上述的三種算法中，在MATLAB軟件中為巡視機器人規(guī)劃路徑結果如圖3-5所示，表1記錄了在三種算法下巡視機器人具體規(guī)劃路徑的結果。

a 規(guī)劃路徑圖

b 算法訓練過程圖圖3 傳統(tǒng)粒子群算法下的規(guī)劃路徑迭代圖

a 規(guī)劃路徑圖

b 算法訓練過程圖圖4 遺傳算法下的規(guī)劃路徑迭代圖

a 規(guī)劃路徑圖

b 算法訓練過程圖圖5 混合粒子群算法下的規(guī)劃路徑迭代圖

從圖5中可以看出，當巡視機器人接受到巡視工作區(qū)各節(jié)點的指令時，系統(tǒng)在運用以上三種算法的情況下，均可為巡視機器人搜索出一條優(yōu)化路徑。

表1 三種算法下巡視機器人的路徑規(guī)劃結果

由圖5和表1可知，在搜索最短路徑的過程中，經(jīng)過多次迭代后，傳統(tǒng)粒子群算法經(jīng)過89次迭代后，搜索出一條390.51m的最短路徑；遺傳算法經(jīng)過78次迭代后，搜索出一條369.92m的最短路徑；混合粒子群算法經(jīng)過55次迭代后，搜索出一條346.58m的最短路徑。從以上數(shù)據(jù)分析可知：相比于傳統(tǒng)粒子群算法與遺傳算法，混合粒子群算法在訓練迭代過程中收斂更快，在全局搜索能力方面更強。

為了避免單次試驗的偶然因素，使得試驗結果更具可靠性，每種算法各進行了10次試驗，試驗結果證實了混合粒子群算法的有效性，三種算法在10次試驗下每次的最短路徑如圖6所示。

圖6 三種算法在10次試驗下每次迭代的最短路徑圖

4 結論

針對巡檢機器人的路徑規(guī)劃問題，提出了基于遺傳算法改進的混和粒子群算法，通過遺傳算法中的交叉和變異策略與傳統(tǒng)粒子群算法的改進融合，提高了算法的收斂速度與全局搜索能力，使其發(fā)生陷入局部最優(yōu)解的情況概率大大減小。通過在MATLAB軟件中對三種算法的仿真試驗，結果表明，相對于傳統(tǒng)粒子群算法和遺傳算法來說，混合粒子群算法具有更高的搜索最優(yōu)路徑的能力，具有一定的科研與實際應用價值。