[發明專利]基于混合粒子群的移動機器人全局路徑規劃算法

在審

• 申請號: 201710633541.1
• 申請日: 2017-07-28
• 公開（公告）號: CN107368075A
• 公開（公告）日: 2017-11-21
• 發明（設計）人: 朱戰霞;唐必偉;劉紅慶;袁建平
• 申請（專利權）人: 西北工業大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 西安通大專利代理有限責任公司61200
• 代理人: 強宏超

1.基于混合粒子群的移動機器人全局路徑規劃算法，其特征在于包括以下步驟：

步驟一、建立混合粒子群算法

粒子按照以下方式對其速度和位置進行更新：

Vmk+1=ωVmk+c1r1(pbestmk-Xmk)+c2r2(gbestmk-Xmk)---(1)]]>

Xmk+1=Vmk+1+Xmk---(2)]]>

其中，ω表示粒子的慣性權重系數；c₁表示粒子的認知加速度系數；c₂表示粒子的社會認知加速度系數；和分別表示粒子m在第k和k+1次迭代時刻的速度；和分別表示粒子m在第k和k+1次迭代時刻的位置；和分別表示在第k次迭代時刻粒子m的個體最優位置和群體的全局最優位置；

ω、c₁、c₂是影響算法性能的三個主要控制參數，采用以下自適應法則對這三個參數進行更新：

ω=ωmax-ωminexp(δm·βm·k)+ωmin---(3)]]>

c1=c1s-c1fexp(δc1·βm·k)+c1f---(4)]]>

c2=c2s-c2fexp(-δc2·βm·k)+c2f---(5)]]>

其中：

δm=ωmax-ωminkmax---(6)]]>

δc1=c1s-c1fkmax---(7)]]>

δc2=c2s-c2fkmax---(8)]]>

βm=||Vmk-1||+||Vmk||2||Vmk-1||+Δ---(9)]]>

ω_max和ω_min表示ω的上限和下限；c_1s和c_1f表示c₁的初始值和最終值；c_2s和c_2f表示c₂的初始值和最終值；k_max表示最大迭代次數；和表示在第k-1和第k迭代時刻粒子m速度矢量的二范數；Δ是為了防止β_m的分母變為0而引入的一個極小的正常數，Δ＝1e-25；算法中要求滿足ω_max>ω_min，c_1s>c_1f和c_2s<c_2f；

步驟二、建立差分演化算法

變異操作通過隨機改變三個不同父輩的基因信息，按照下列公式產生一個新的個體：

vi(k)=xi3(k)+Fi(xi1(k)-xi2(k))---(10)]]>

其中，和是從i≠i₁≠i₂≠i₃的當前種群中隨機選擇的個體，F_i表示差分進化算法的縮放因子；

采用基于群體多樣性的新的自適應方法來更新縮放向量F_i，使得每個元素按照如下的公式進行更新：

F_i,j＝1-div_i,j(k) (11)

divi,j(k)=Σi=1SPESP·max(E)---(12)]]>

E=Σj=1D[xi,j(k)-x‾j(k)]2---(13)]]>

x‾j(k)=1SPΣi=1SPx‾i,j(k)---(14)]]>

其中，F_i,j是縮放向量F_i的第j個元素；SP表示種群的大小；div_i,j(k)表示在第k次迭代時刻第i個父輩個體的歸一化的多樣性；表示第k次迭代時刻種群中所有父輩個體的第j維多樣性的平均值；E表示當前群體中第i個父輩個體相對于群體中所有個體平均多樣性的差異；

在差分演化算法中按照公式(10)-(14)給出的變異操作產生新個體后，采用標準差分進化算法中的交叉和變異操作對新個體進行更新；

步驟三、移動機器人工作環境建模

假設機器人在二維空間里進行工作，并且其工作的環境中包含一定數目的障礙物，首先建立一個全局坐標系o-xy，其中st和ta分別表示機器人的起始和終點位置，在o-xy中，線段st-ta被n個導航點等分為n+1段，其中n是一個預定義的常數參數；通過這些導航點畫出n條垂線，得到一系列線l₁,l₂,...,l_n；機器人的任意一條待選路徑ph＝[st,p₁,...,p_n,ta]在這些垂線上隨機產生；

步驟四、移動機器人路徑規劃問題數學建模

假設用p₀和p_n+1分別表示步驟四中所描述的機器人的起點st和終點位置ta，則路徑規劃問題建立成如下的數學模型：

finding:ph=[st=p0,p1,p2,...,pn,ta=pn+1]minimize:Jcost=w1·JL+w2·1Jss.t.pipi+1∈semi-free workspace,0≤i≤n---(15)]]>

其中，J_L和J_s分別表示路徑長度和路徑安全性；w₁和w₂是兩個加權參數，表示J_L和J_s的相對重要性；

步驟五、基于混合粒子群和差分演化算法的移動機器人路徑規劃框架

用來表示導航點p₁,...p_n的y坐標，作為使用混合粒子群和差分演化算法對待優化量進行優化的粒子編碼；

通過下面的飽和機制來調節每個待優化變量

ypi=width2,if ypi>width2-width2,if ypi<width2ypi,otherwise---(18)]]>

其中，width表示工作空間的寬度；

假設在機器人的規劃空間中給定Nob個障礙物，HNTVPSO-RBSADE中粒子m₁的違反約束度可以通過如下的公式計算得到：

violationm1=1NobΣj=1Nobviolm1j]]>

violm1j=1if m1collides with obstacle j0otherwise---(19)]]>

假設用NP表示HNTVPSO-RBSADE中群體所包含的粒子總數，并且用表示在第k次迭代過程中粒子的個體最優解位置集合，建立基于HNTVPSO-RBSADE算法求解機器人路徑規劃問題的框架如下：

Step1.在機器人的規劃空間中隨機產生一個初始種群,并且獲得初始時刻算法的全局最優位置gbest和BP；

Step2.判斷當前迭代次數是否到達最大迭代次數，如果是，則跳轉至Step14；否則，跳入Step3；

Step3.為BP中的每個個體進行變異，交叉和選擇操作；

Step4.按照公式(11)-(14)更新BP中每個個體的縮放因子；

Step5.按照公式(1)更新HNTVPSO-RBSADE中每個粒子的速度；

Step6.按照公式(2)更新HNTVPSO-RBSADE中每個粒子的位置；

Step7.按照公式(18)給出的飽和機制修正HNTVPSO-RBSADE中每個粒子的位置；

Step8.按照公式(15)-(17)計算HNTVPSO-RBSADE中每個粒子的目標函數值；

Step9.按照公式(19)計算HNTVPSO-RBSADE中每個粒子的違反約束度；

Step10.按照公式(3)-(9)更新HNTVPSO-RBSADE中每個粒子的三個控制參數；

Step11.按照解的可行性原則更新HNTVPSO-RBSADE中每個粒子的個體最優位置pbest；

Step12.按照解的可行性原則將每個粒子的pbest存放在BP中；

Step13.按照解的可行性原則更新HNTVPSO-RBSADE中群體的全局最優位置gbest；

Step14.結束循環，并且輸出gbest。