基于QPSO方法的足球機器人路徑規劃

陸克中

（池州學院 數學與計算機科學系，安徽 池州 247000）

基于QPSO方法的足球機器人路徑規劃

陸克中

（池州學院 數學與計算機科學系，安徽 池州 247000）

提出了一種基于量子粒子群優化算法(QPSO)的足球機器人路徑規劃方法。為適應QPSO算法的自身特點和提高算法搜索的效率，在傳統柵格法的基礎上引入實際坐標系法，對環境進行建模；為了更好地評價粒子（即解）的性能，在進行碰撞判定的基礎之上，引入罰函數方法，克服了傳統適應度函數難以更好地表達粒子性能的缺點。與PSO算法的對比仿真實驗表明，該算法在足球機器人路徑規劃方面是可行的、有效的。

量子粒子群優化算法；路徑規劃；足球機器人

機器人足球由加拿大不列顛哥倫比亞大學的教授Alan Mackworth在1992年的論文《On Seeing Robots》中首次提出[1]，其目的是通過機器人足球比賽，為人工智能和智能機器人學科的發展提供一個具有標志性和挑戰性的課題。在機器人足球賽中，路徑規劃作為足球機器人基本動作實現的基礎，它的優劣直接影響機器人動作的實時性和準確性。因此，路徑規劃是機器人足球比賽的一個重要研究內容。路徑規劃就是在有障礙物的工作環境中，按照某一性能指標搜索一條從起始狀態到目標狀態的最優或近似最優的無碰路徑[2]。

機器人路徑規劃實質上是一個有約束的優化問題。目前，各國學者對此問題已經做了大量的研究工作，這其中包括人工勢場法[3]、神經網絡法[4]、遺傳算法[5]、蟻群算法[6]和粒子群優化算法[7]等。量子粒子群優化算法 (Quantum-behaved Particle Swarm Optmization,QPSO)是一種改進的粒子群優化算法(Particle Swarm Optmization，PSO)，與 PSO 算法在量子空間中粒子滿足聚集態的性質完全不同，QPSO算法可以在整個可行解空間中進行搜索，因而它的全局搜索性能優于一般的PSO算法[8]。

本研究提出了一種基于QPSO算法的足球機器人路徑規劃方法。首先為適應QPSO算法的自身特點和提高算法搜索的效率，在傳統柵格法的基礎上引入實際坐標系法，對環境進行建模；然后為了更好地評價粒子（即解）的性能，在進行碰撞判定的基礎之上，引入罰函數方法，評價粒子的性能；最后利用QPSO算法實現足球機器人路徑規劃仿真并與PSO算法進行了比較分析。

1 QPSO算法原理

2004年，Sun等人在研究了Clerc等人關于粒子收斂行為的研究成果后，從量子力學的角度出發提出了一種新的PSO算法模型。這種模型是以DELTA勢阱為基礎，認為粒子具有量子的行為，并根據這種模型提出了量子粒子群算法。與在量子空間中粒子滿足聚集態的性質完全不同，它可以在整個可行解空間中進行搜索，因而QPSO算法的全局搜索性能優于標準PSO算法。

在量子空間中，粒子的速度和位置是不能同時確定的，因此文獻[8]通過波函數來描述粒子的狀態，并通過求解薛定諤方程得到粒子在空間某一點出現的概率密度函數，隨后通過蒙特卡羅隨機模擬的方式得到粒子的位置方程。具體如下：

D維搜索空間中，有m個粒子，其中第i個粒子的位置是x→i=(xi1,xi2,…xiD)， i=1,2,…，m。將x→i帶入目標函數可計算出其適應值。記第i個粒子搜索到的最優位置為=(Pi1,Pi2,…PiD)，整個粒子群搜索到的最優位置為(Pg1,Pg2,…PgD)，勢中心點 P(r1Pid+r2Pgd)/(r1+r2)。粒子狀態更新操作如下：

其中，i=1,2，…，m,d=1,2,…D；u，r1和 r2是介于[0，1]之間的隨機數；t為當前迭代次數；z是小于的非負常數，起到收縮擴張作用，可將參數z作如下線性變化：

其中 z0，z1為常數，t為迭代步數，Tmax 為設定的最大迭代次數。

2 基于QPSO算法的足球機器人路徑規劃方法

2.1 環境建模

實現路徑規劃的前提是對環境進行描述，即對環境進行建模。建模的方法有柵格法，實際坐標系法等[8]。柵格法當規劃范圍較大時計算量相當大，用實際坐標系法雖然建模簡單，但很難和其他成熟的規劃方法結合。為了適用本文算法，且減少計算量，本文借鑒柵格法與實際坐標系法的各自優點，采用半柵格半實際坐標系法，即在橫向坐標上使用柵格法，而縱向坐標上使用實際坐標系法。同時為了縮小足球機器人的搜索空間，提高搜索速度，這里將搜索范圍確定為：當前機器人R，目標點G，R到G的距離為L，以L為長，L/2為寬，RG為中分線作一矩形，此矩形即為搜索空間。在矩形空間內的任何人（己方隊員和對方隊員）都將被看作障礙物。如圖1所示，其中圓表示障礙物。

圖1 足球機器人障礙環境描述與坐標變換

為了方便計算，在環境地圖中建立了一個新的坐標系 X’RY’，即以 RG的連線為 X’軸，過 R且與X’垂直的直線為Y’軸。對應的坐標變換公式如下：

其中(X,Y)和(X’,Y’)分別為環境地圖中的一點在XOY和X’RY’中的坐標，(XR,YR)為R點在XOY中的坐標。

2.2 粒子編碼表示

基于上面的半柵格半實際坐標系方法，在X’RY’坐標系中，將RG線段等分m+1等份，在每個等分點作RG的垂線，垂線長度為RG/2，得到VL1,VL2,…,VLm線段，如圖1所示。足球機器人從起點R沿著RG方向階段性前進，通過調節VLi(i=1,2,…,m)上的坐標點，使得足球機器人能夠尋找到一條不穿過任何障礙物 （即不與任何障礙物碰撞）的路徑，如圖1中的從R到G的一條S形路徑。我們的目標就是找尋這樣路徑中長度最短的哪一條。因此粒子群算法中的粒子就是由一系列VLi(i=1,2,…,m)上的Y’軸坐標點和起止點R和G的縱坐標構成，即（0 VL1,VL2,…,VLm 0）。 這樣的編碼直接而簡潔，且在VLi(i=1,2,…,m)上可自由移動，沒有柵格法受柵格的限制，有利于粒子在解空間中搜索。

2.3 適應度函數的確定

機器人足球路徑規劃就是在有障礙的環境下，尋找一條由起點到目標點的路徑點集合，使其構成的路徑安全無碰撞，且長度最短。據此，我們將適應度函數定義為路徑中各路段長度之和。對于無碰撞的路段，用其兩端點之間的歐式距離表示；對于有碰撞的路段，則采取罰函數的方法，將其長度乘以一個比較大的懲罰系數，從而降低該路徑的評價性能。對于有碰撞的線段通過如下步驟來判斷：

計算障礙物中心點到路徑線段所在直線的距離d，如果d>=r（r為障礙物的安全半徑），則線段為安全線段，如圖2.1所示；否則，計算障礙物中心點到路徑線段所在直線的垂足，判斷垂足是否在線段中間，如果是，如圖2.2和2.3所示，則判斷為有碰撞；否則，計算障礙物中心點到路徑線段兩端的距離，如果任何一端的距離小于障礙物的安全半徑r，如圖2.4和2.5所示，則判斷為有碰撞，其它情況被認為安全無碰撞。

根據以上表述，可將適應度函數定義為：

其中fi為路段i兩端點之間的歐式距離，λi為路段i對應的懲罰系數。

圖2 碰撞示意圖

2.4 基于QPSO的足球機器人路徑規劃

(1)確定粒子的維數（即RG線段的等分數m+2）和群體規模M，初始化粒子群體，在解空間范圍內隨機確定每個粒子的初始位置（即路徑），每個粒子的初始速度設置為0。

(2)根據式(6)計算每條路徑的適應度值fiti，若當前值優于Pibest，則Pibest=fiti，若在所有個體極值中，有優于 Pg的值，則 Pg＝fiti。

(3)根據式(1)-(4)，更新每個粒子的新位置，并把它們限制在一定范圍內。

(4)t=t+1，返回到步驟(2)，直到獲得一個預期的適應值或t達到設定的最大迭代次數。

3 路徑規劃仿真

仿真環境中，足球機器人起始點R(200,150)，目標點G(400,260)，障礙物坐標分別是：(240,160)、(280,200)、(320,230)，障礙物安全半徑為 16。QPSO和PSO算法中群體規模M＝20，粒子維數dim=22，最大迭代次數Tmax=400。PSO算法中學習因子c1=c2=2，慣性權重w隨迭代次數的增加線性地從0.9遞減到0.4。QPSO算法中，收縮擴張因子的z0=0.9，z1=0.5。仿真結果如表1所示。

表1是分別使用PSO和QPSO算法對足球機器人路徑規劃的30次仿真結果。從表中可以看出，由于采用了帶懲罰系數的碰撞檢測技術，保證了兩種算法產生的所有路徑都是安全無碰撞路徑；從最小路徑長度可見，兩種算法都能夠找到最優路徑，最優路徑如圖3所示；但是QPSO算法在平均尋優性能方面明顯優于PSO算法，這體現在平均路徑長度等參數上，QPSO算法的平均路徑長度255.56接近其最優路徑長度231.98，而PSO算法的平均路徑長度495.01遠大于其最優路徑長度232.01，這在實際應用中是非常重要的。

表1 兩種算法30次路徑規劃仿真結果比較

圖3 最優規劃路徑

4 結論

本文將QPSO算法應用于足球機器人路徑規劃，為了適應QPSO算法的自身特點和提高算法搜索的效率，在傳統柵格法的基礎上引入實際坐標系法，對環境進行建模；為了更好地評價粒子（即解）的性能，在進行碰撞判定的基礎之上，引入罰函數方法，克服了傳統適應度函數難以更好地表達粒子性能的缺點。通過與PSO算法進行對比，仿真實驗表明，該算法在足球機器人路徑規劃方面的可行性和有效性。

[1]Alan K Mackworth.On Seeing Robot,Computer vision:system,theory and application[M].Singapore：World Scientific Press,1993:1-13.

[2]柳長安,鄢小虎,劉春陽,等.基于改進蟻群算法的移動機器人動態路徑規劃方法[J].電子學報，2009,39(5):1220-1224.

[3]Derek J Bennet,Colin R McInnes.Distributed control of multi-robot systems using bifurcating potential fields[J].Robotics and Autonomous Systems,2010,58(3):256-264.

[4]鄧萬,鄭慶,陳琳,等.神經網絡極速學習方法研究[J].計算機學報,2010,33(2):279-287.

[5]劉玲,王耀南,況菲,等.基于神經網絡和遺傳算法的移動機器人路徑規劃[J].計算機應用研究,2007,24(2):264-268.

[6]華路,周之平.不確定環境下一種新的雙蟻群路徑規劃算法[J].計算機工程與應用,2011,47(15):245-248.

[7]唐國新,陳雄,袁楊.微粒群算法在機器人路徑規劃中的應用[J].計算機工程與應用,2007,43(16):231-234.

[8]Jun S,Wen-bo X,Bin F.A global search strategy of quantum-behaved particle swarm optimization[C]//Proceeding of IEEE confereuce on Cybernetics and Intelligent Systems,2004:111-116.

TP242

A

1674-1103(2012)03-0009-03

2011-11-11

安徽省自然科學研究項目(KJ2011Z266)；池州學院自然科學研究項目(2010ZRZ07)。

陸克中(1976-)，男，安徽樅陽人，池州學院數學與計算機系講師，碩士，研究方向為粒子群優化算法的理論及其應用。

[責任編輯：曹懷火]