Robot Darwinian Particle Swarm Optimization

with Self-adaptive Tuning Parameters

余志鵬

(順德職業(yè)技術學院電信系，廣東 佛山　528333)

帶自適應整定參數(shù)的機器人達爾文粒子群優(yōu)化算法

Robot Darwinian Particle Swarm Optimization

with Self-adaptive Tuning Parameters

余志鵬

(順德職業(yè)技術學院電信系，廣東 佛山528333)

摘要：對基數(shù)龐大的機器人群族引入達爾文粒子群優(yōu)化算法(DPSO)。該算法將自然選擇應用到粒子群算法中，對整個機器人群族進行動態(tài)分割，根據(jù)上下文評價指標配合機器人行為對機器人的行為進行預測，提高了機器人群族運動的最優(yōu)逃脫方案成功率。仿真試驗表明，通過對該算法的輸入?yún)?shù)進行自適應整定，可以改進系統(tǒng)的收斂率，增加通信的約束，使整個機器人群族在未來更大的范圍內有效驅動數(shù)量更大的無線機器人群族。

關鍵詞：RDPSO機器人群族上下文評價自適應感知能力

Abstract：The Darwinian particle swarm optimization (DPSO) is introduced in the robots swarm with tremendous cardinality. The algorithm applies natural choice in particle swarm algorithm, dynamically divides the entire robots swarm, and predicts the behavior of robots according to the context evaluation indicator with robot’s behavior, to increase the optimal escape rate of the motion of robots swarm. The simulation tests show that through adaptive tuning of the input parameters of the algorithm, the convergence rate of the system can be improved, the communication constrain is increased, which lead to larger wireless robots swarm can be efficiently driven by entire robots swarm in larger scope in the future.

Keywords：Robot Darwinian particle swarm optimization(RDPSO)Robot swarmContext evaluationSelf-adaptionSensory ability

0引言

在基于群族智能化的仿生算法里，比較著名的是粒子群優(yōu)化算法(particle swarm optimization，PSO)[1]。PSO包含很多個粒子，這些粒子一起進行空間探索，以找到最優(yōu)的解決方案。PSO的擴展式(如robotic Darwinian PSO, RDPSO)提出在面對動態(tài)和復雜問題時會出現(xiàn)一些障礙，如隨時間變化的大量次佳方案問題。通常在自然界中發(fā)現(xiàn)的對關聯(lián)信息缺乏自適應性會作用于次佳方案，可以通過全面的解決方案(如統(tǒng)一機器人的行動)來克服這個缺點[2]。例如，在搜救應用中受難者只要還有一點機會獲救，機器人應該堅持搜救。盡管之前提出的RDPSO本來就具備獎懲規(guī)則，以激發(fā)自然選擇來避免停滯，但機器人可能會花費大量時間才意識到它們陷于次優(yōu)方案或者方案已過時。如對于一個基于嗅覺的群族，因氣味受擴散和氣流原因影響，所以很難尋找到氣味的源頭(如對致命氣體源的尋找)[3]。對于這些方案，本文將提出幾個已有的相關研究。

1相關研究

不考慮PSO的主要變體，解決設定和調整參數(shù)的困難，以及在更大范圍保持搜索能力的問題，仍然是近來研究工作的重點[4-5]。例如，學界提出的一個最常用的、解決PSO參數(shù)設置和調整問題的策略就是基于對該算法的穩(wěn)定性分析。在文獻[5]中，對單個粒子軌跡的廣義模型進行分析，廣義模型包含了一組系數(shù)控制系統(tǒng)的收斂度。經(jīng)過運算后的系統(tǒng)是一個二階線性系統(tǒng)，它的穩(wěn)定性和參數(shù)取決于極點的位置，或者狀態(tài)矩陣的特征值。

Yasuda等人[6]提出一個基于行為的數(shù)值穩(wěn)定性分析算法，包含研究過程中對控制多樣化和激烈化的群組行為的反饋。Yasuda等人展示了使用PSO的穩(wěn)定和非穩(wěn)定區(qū)可控制群組行為。但是，對于分布式的方法，例如RDPSO，在計算群組行為時忽略了一個事實，就是群組里每個機器人不僅需要即時共享它的位置，還需要即時共享它對所有其他成員的相對速度。帶有模糊邏輯的合成PSO算法已經(jīng)完成對這些信息的共享，可以替代上述算法。

模糊邏輯的作用在于不確定性能被包含在決策過程里。模糊和不精確與定性數(shù)據(jù)的關聯(lián)衍生出這種邏輯算法，它用語言變量和不確定范圍內的重疊關系函數(shù)得到結果。例如，在Shi and Eberhart[7]的論文中，把模糊控制與PSO相結合，使系統(tǒng)能動態(tài)地自適應粒子慣量。類似地，Liu等人[8]提出一種邏輯控制器，以自適應地調整PSO粒子的最小速率。

目前，沒有研究引進自適應行為來克服真實世界情境里的動態(tài)特性。機器人的行為需要根據(jù)環(huán)境的上下文信息來改變。當考慮基于因子、任務相關以及環(huán)境情況時[9]，要把上下文知識概念納入計算中。

2RDPSO算法簡介

本節(jié)簡單地介紹文獻[9]提出的RDPSO算法，在文獻[10]有進一步的擴展。由于RDPOS算法是在真實移動機器人里對DPSO的改進版，其具有5個特點。①基于分階數(shù)微積分，有更好的慣性影響；②有故障回避動作，避免撞車；③有算法保證MANET協(xié)議在整個任務中保持連接；④用異常處理算法對機器人建立二維慣性調度，保護MANET協(xié)議的連接，這個算法在機器人里傳播得越廣越好；⑤用異常賞罰機制來評估機器人的檢測和創(chuàng)新效果。

機器人n的行為可以用以下積分方程來描述，在每個離散時間片中，t∈No：

(1)

(2)

部分系數(shù)α允許描述機器人的軌道現(xiàn)象，因為它的內在記憶屬性。認知組件χ1[t]和社會組件χ2[t]在PSO算法里是常規(guī)的，χ1[t]代表機器人n的局部最佳位置，χ2[t]代表機器人n的全局最佳位置。避障組件χ3[t]由每個機器人的位置代表，它使一個檢測距離的障礙的函數(shù)g(xn[t])單調遞增或遞減。在一個沒有障礙的環(huán)境里，障礙敏感性權重ρ3被設為0。但是，在現(xiàn)實世界中，必須考慮障礙，ρ3的值取決于幾個情況：跟主要目標相關(例如，最小消耗功能或最大適應力功能)；跟傳感器信息相關(如g(xn[t])的單調性)。MANET組件χ4[t]用最接近的機器人的位置代表，它的位置隨著當前機器人位置的最大通信范圍dmax增加而增加。更大的ρ4可以提高網(wǎng)絡連接，以保證機器人間的特定的范圍或者機器人間的信號質量。

除了這些組件，RDPSO用多群族代表，例如，幾組機器人一起形成一個群族，各個群族各的行為通過式(1)和式(2)描述。這次方案中，搜索和獎懲規(guī)則管理著整個機器人群族，基于“社會排斥”概念(更多細節(jié)請查閱[9])。RDOSO獎懲規(guī)則如表1所示。

表1　RDPSO獎懲規(guī)則

在族群中選取特定的機器人單獨考慮，而不是像其他活躍群里的機器人一樣尋找目標函數(shù)的最優(yōu)解，因為這樣會使機器人隨機地游移在場景之中。這樣改進算法，使它沒那么容易允許目標陷入次優(yōu)方案之中。存在多個群族允許分布式的方法，因為以往用所有機器人口定義的網(wǎng)絡如今被劃分成多個更小的網(wǎng)絡(每個群族1個)，因此節(jié)點減少了，機器人間的信息交換在相同的網(wǎng)絡下進行。這就是說，機器人間的相互作用被限制在同一群族內部的相互作用，使得RDPSO的可擴展性可以延伸到大量的機器人。

3自適應系統(tǒng)參數(shù)調整

為提高群族里RDPSO機器人的收斂率，機器人應該盡量分散。它們必須保持機器人間最大通信距離或最小信號質量。在此預期下，需要找到加強通信因子ρ4和任務因子(如ρ1和ρ2)的最佳組合，因為機器人通過MANET網(wǎng)絡通信的同時要規(guī)劃自身的路線。

機器人利用之前結果數(shù)據(jù)最簡易的方法是當機器人間的距離接近極限值(如最大距離或最小信號質量)時保證增加通信因子ρ4的權重。因此，探索內部的知識允許定義一個基于因子的上下文標準來表示機器人間的距離。

然而，這種標準需要依靠機器人間最大通信距離dmax或最小信號質量qmin。在現(xiàn)實中，只考慮dmax不能匹配實際的傳播模型，因為它更復雜。信號的大小不僅取決于距離，還取決于被其他障礙物反射的多種路徑。

這種結構的整體組織與常用的反饋控制器相似，上下文知識是通過對數(shù)據(jù)的推理分析獲得的，再用這些知識控制機器人。因此，基于之前提出和定義的指標，人們可以進入模糊系統(tǒng)工程的輸入和輸出關系，關系函數(shù)會用廣義的鐘形函數(shù)定義。廣義鐘形函數(shù)典型的高斯函數(shù)多一個參數(shù)，在關系函數(shù)里使用的高斯函數(shù)的定義為：

(3)

式中：參數(shù)a、b和c各代表曲線的寬度、斜率、中心。

所有的指標都定義為0~1，只有半條曲線被用作代表群族和機器人的狀態(tài)，如c=1。為了得到更柔和的響應，寬度和斜率可以定義為a=0.5、b=3。

每個輸入的一般關系函數(shù)如圖1所示。

圖1　每個輸入的一般關系函數(shù)

群族動作從屬函數(shù)μAS(AS[t])代表群族的活躍程度。至于機器人的社會化參數(shù)μSn(Sn[t])，它代表機器人的社會化程度。對于避障從屬闡述μOn(On[t])，可以作出同樣的分析，這里代表了指定機器人里障礙有多遠。近似從屬函數(shù)μPn(Pn[t])代表某個機器人離其鄰居的距離。

對于后面的函數(shù)，基于對之前部分提出的初步試驗評價，定義如圖2所示的三角成員關系。這些函數(shù)不僅可以軟化和表達輸出，更重要的一點是還可以把文獻[11]所示的吸引因子常規(guī)化。

圖2　系數(shù)量化結果的關系函數(shù)

加入模糊系統(tǒng)的目的在于對RDPSO算法可以系統(tǒng)地調整它的行為。通過這種方法，機器人通過觀察參數(shù)的發(fā)展變化，就可以容易地明白關于機器人和群族的上下文信息。因此，上下文知識的使用，通過允許對環(huán)境和任務的快速檢測，探索真實世界的特性的動態(tài)信息，提高了機器人的感知能力(如檢測障礙)。

基于用之前定義的指標所代表的輸入所提供的信息，模糊邏輯系統(tǒng)可以推論出上下文知識，它可以通過參數(shù)的自適應來控制RDPSO的行為。其邏輯推理如圖3所示。

圖3　模糊自適應系統(tǒng)控制RDPSO行為邏輯推理圖

4仿真試驗

本節(jié)使用虛擬機器人進行仿真，這樣可以對更大數(shù)量的機器人在更大的場地里的自適應RDPSO行為進行分析。試驗在600 m×600 m模擬場地進行，每次嘗試障礙都隨機防止?；鶞史匠蘁(x,y)定義為標準的高斯函數(shù)。

(4)

式中：x-y代表平面坐標，m。

所以，機器人隊伍的目標是最大化F (x, y)，也就是最小化原始基準函數(shù)F (x, y)，機器人群族要尋找f (x, y)=1的最優(yōu)方案，而且要避免障礙和保證網(wǎng)絡連接。

測試組進行100次測試和500次迭代，每次被設成機器人向量N={50,100,}。然后，一個初始的最小和最大的機器人群族的數(shù)量分別為2、5、8。迭代間的最大行走距離被設為0.750 m，也就是max|xn[t+1]-xn[t]|=0.750，機器人間最大通信距離設為dmax=15 m。

圖4描述了在50次試驗中應用了非自適應和自適應RDPSO算法，計算出的最優(yōu)方案在中值、首個和第三個四分位數(shù)的對于機器人N={50,100}的最終輸出。

通過對圖4的分析，可以清楚地知道給定的任務可以由任何數(shù)量≥25的機器人完成。事實上，除去機器人數(shù)量這個因數(shù)，大部分情況下，包括非自適應和自適應RDPSO都是收斂的。然而，非自適應算法需要占用首個和1/4中值鍵間的更大的區(qū)域，尤其對于機器人數(shù)目巨大的情況。

圖4　利用非自適應和自適應RDPSO的群族表現(xiàn)

因為環(huán)境是連續(xù)不斷地變化的，對環(huán)境的最優(yōu)方案也是隨時間變化的。這要求RDPSO能在短期內找到方案，而且能找到最優(yōu)方案的軌跡。非自適應算法如常規(guī)的RDPSO，在動態(tài)環(huán)境中通常會出現(xiàn)幾個錯誤，因為它們缺少在動態(tài)改變環(huán)境中追蹤不平穩(wěn)的最優(yōu)方案的能力(如文獻[12-13])。

函數(shù)F(x,y)的動作的A序列如圖5所示。

圖5　基于強制Duffing振蕩器的F(x,y)函數(shù)頂峰的平面運動。

混沌函數(shù)是最普遍和得到充分研究的方法—產(chǎn)生不穩(wěn)定函數(shù)(如logistic函數(shù)[14])。在這篇文獻里，采用一種基于強制杜芬振蕩器[15]的常規(guī)方法動態(tài)地改變峰值位置。因此，函數(shù)F(x,y)定義為動態(tài)時變高斯方程。

每個峰值的動作可以通過元組{γ,ω,ε,Γ,Ω}配置。在元組里，γ控制阻尼的大小，ω控制復原力的大小，ε復原力的非線性量的大小，?？刂浦芷隍寗恿Φ恼穹?，Ω控制周期驅動力的頻率。盡管為了得到更不可預見的和混沌的行為，元組{γ,ω,ε,Γ,Ω}可能隨機定義，為了更好地理解實驗結果，他們將被定義為常數(shù){0.1, 1, 0.25, 1, 0.5}。為了使表面平滑，應用一個循環(huán)平均過濾器。

5結束語

本文提出RDPSO的延伸算法，具有基于上下文信息的自適應能力。為使算法具有自適應能力，把一個群族置于仿真環(huán)境中，以評估機器人障礙與通信等約束下的動態(tài)表現(xiàn)。基于上下文的度量被用作模糊系統(tǒng)的輸入，系統(tǒng)地適應RDPSO算法。仿真試驗結果表明，應用了自適應算法的RDPSO比普通版本的具有更好的收斂性。該算法使用上下文知識，允許對環(huán)境和任務的快速檢測，探索真實世界的特性的動態(tài)信息，提高了機器人的感知能力。即使在動態(tài)分布中，自適應RDPSO依然可以比非自適應RDPSO更容易找到最優(yōu)路徑。在日后的工作中，期望在數(shù)量更大的機器人群族里使用自適應RDPSO，并將RDPSO與傳統(tǒng)類型的機器人群族算法做比對。

參考文獻

[1] James K,Russel E.A new optimizer using particle swarm theory[C]//Proceedings of the IEEE Sixth International Symposium on Micro Machine and Human Science,Nagoya,Japan,1995:39-43.

[2] Jim S,Robert M.A survey of animal foraging for directed, persistent search by rescue robotics[C]//Proceedings of the 2011 IEEE International Symposium on Safety,Security and Rescue Robotics,Kyoto,Japan,2011:314-320.

[3] Lino M,Urbano N,Almeida A.Particle swarm-based olfactory guided search Autonomous Robots,2006,20 (3):277-287.

[4] 曾建潮，介婧，崔志華.微粒群算法[M].北京：科學出版社，2004:89-112.

[5] Maurice C,James K.The particle swarm—explosion,stability,and convergence in a multidimensional complex space[J].IEEE Transactions on Evolutionary Computation,2002,6(1):58-73.

[6] Kellchiro Y,Nobuhiro I,Genki U,et al.Particle swarm optimization: a numerical stability analysis and parameter adjustment based on swarm activity[J].IEEJ Transactions on Electrical and Electronic Engineering,2008(3):642-659.

[7] Yuhui Shi,Russel E.Fuzzy adaptive particle swarm optimization[C]//Proceedings of IEEE Computer,2001:101-106.

[8] Liu Hongbo,Abraham A.A fuzzy adaptive turbulent particle swarm optimization[J].International Journal of Innovative Computing and Applications,2007,1(1):39-47.

[9] 張立川，徐德民，劉明雍，等.基于移動長基線的多 AUV協(xié)同導航[J].機器人，2009，31(6)：581-585,593.

[10]Micheal S,Couceiro R,Rocha N M.Ferreira.Ensuring Ad Hoc connectivity in distributed search with Robotic Darwinian swarms[C]//Proceedings of the IEEE International Symposium on Safety,Security,and Rescue Robotics,SSRR2011,Kyoto,Japan,2011:284-289.

[11]Micheal S,Couceiro S,Fernando M L.Analysis and parameter adjustment of the RDPSO—towards an understanding of robotic network dynamic partitioning based on Darwin’s theory[J].International Mathematical Forum,2012,7(32)1587-1601.

[12]Aaron C,Gerry D.Adapting particle swarm optimization to dynamic environments[C]//Proceedings of the International Conference on Artificial Intelligence,Las Vegas,USA,2000:429-433.

[13]Xiaohui Cui,Thomas E.Distributed adaptive particle swarm optimizer in dynamic environment[C]//IEEE International Parallel and Distributed Processing Symposium,IPDPS’07,Long Beach,CA,2007: 1-7.

[14]Morrison R,Kenneth A.A test problem generator for non-stationary environments[C]//Proceedings of the 1999 Congress on Evolutionary Computation,CEC’99,Washington DC,USA,1999:786-793.

[15]Chin.A,Kang B.Chaotic motions of a Duffing oscillator subjected to combined parametric and quasiperiodic excitation[J].International Journal of Nonlinear Sciences and Numerical Simulation,2001,2(4):353-364.

中圖分類號：TP1

文獻標志碼：A

DOI:10.16086/j.cnki.issn1000-0380.201503021

修改稿收到日期：2014-06-23。

作者余志鵬(1981-)，男，2007年畢業(yè)于華南理工大學控制理論與控制工程專業(yè)，獲碩士學位，講師；主要從事機器人控制系統(tǒng)開發(fā)的研究。