[發明專利]基于改進的多目標粒子群算法的無人車路徑規劃方法

有效

• 申請號: 201711427582.1
• 申請日: 2017-12-26
• 公開（公告）號: CN107992051B
• 公開（公告）日: 2020-10-23
• 發明（設計）人: 葛洪偉;錢小宇;葛陽
• 申請（專利權）人: 江南大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 哈爾濱市陽光惠遠知識產權代理有限公司 23211
• 代理人: 張勇

1.基于改進的多目標粒子群算法的無人車路徑規劃方法，其特征在于，包括如下步驟：

(1)利用直角坐標系來對無人車的行駛環境進行二維空間模擬，障礙物用不同半徑的圓形表示，無人車用點代替，將無人車整個路徑的位置點通過起止點用線連接起來，然后將該路徑分成若干等分路段，規定無人車行駛過程中的位置點為相鄰兩路段的連接點，將位置點包括起止點連起來就得到一條路徑；粒子x是由p₁,p₂,…,p_n組成的集合，p_i，i∈[1,2,...,n]，p_i為粒子x中的第i個位置點，p₀和p_n+1表示無人車運動的起點和終點位置，將粒子與起止位置點組合成該粒子對應的路徑，并將該路徑表示為P＝[p₀,p₁,p₂,…,p_n,p_n+1]，|p_ip_i+1|表示路段p_ip_i+1的長度，n表示無人車行駛過程中經過的位置點的個數；

(2)無人車最優路徑的參考指標建模即目標函數min F(x)的構建如下所示：

min F(x)＝(f₁(x),f₂(x),f₃(x))

其中f₁(x)就是這條路徑上所有路段之和，即路徑長度，f₁(x)越小，表明無人車行駛路徑長度越短；f₂(x)中的θ_i表示粒子x對應的路徑P在p_i位置點處的兩個相鄰路段的夾角，f₂(x)越小，表明相鄰兩個路段的夾角越大，路線越平滑；f₃(x)指路徑上位置點集合Q中的點與障礙物圓心距離的倒數之和，值越小表明無人車與障礙物發生碰撞的可能性越小，其中無人車的行駛路徑上距離第s個障礙物圓心R_s最近的位置點為q，s∈{1,2,…,w}，w表示障礙物的個數，以障礙物圓心R_s為起點，在R_sq兩側作兩條射線與無人車路徑相交，R_sq兩側的射線與其夾角都是當集合Q中的點的個數大于9時，保留離障礙物圓心最近的9個位置點，其余的從Q中刪除，n為集合Q中位置點的個數，‖Q_k-R_s‖指Q中第k個位置點Q_k到第s個障礙物圓心R_s的距離；

(3)初始化2N個粒子的位置，2N個粒子的位置集合記為POP，初始化N個粒子的速度，N個粒子的速度集合記為V，設目標函數的個數為m，初始化最大迭代次數gmax，粒子位置在x軸方向約束的范圍xmin和xmax，y軸方向的約束范圍ymin和ymax，每個子區域容量Vol∈[1,3]，鄰域個數T以及子區域數目M；

(4)進行目標空間分解操作：把目標空間Y分成M個子區域Y₁,Y₂,…Y_j,…,Y_M，令j∈{1,2,…,M}，對任一給定的第j個子區域，其對應的目標函數值在所有目標函數值之和中所占有的權重a_j，所組成的向量(a₁,a₂,…,a_M)定義為第j個子區域的中心向量A_j，j＝1,2,…,M，且

當目標函數個數m＝2時，則第j子區域的中心向量A_j表示為

當m＝3時，進行兩層循環，令k₁為第1層循環變量，k₂為第2層循環變量，k₁從0取到h，k₂從0取到h-k₁，每次循環得到第個子區域，其中h和M滿足以下關系：h取滿足時的最小值，則第j個子區域的中心向量為

當m3時，進行m-1層循環，k₁為第一層循環變量，依次由外向內，令k_i為第i層循環變量，k_m-1為第m-1層循環變量，k₁從0取到h，k₂從0取到h-k₁，k_i從0取到h-k₁-k₂-...-k_i-1，最里層循環變量k_m-1從0取到h-k₁-k₂-...-k_m-2，每次循環得到第

個子區域，其中參數h、m和子區域數M滿足以下關系：h取滿足時的最小值，則第j個子區域的中心向量為l為中間變量，l＝1,2,…,m-1；

當m≥3時，一共產生個中心向量，個中心向量的下標為若則從第j＝2個子區域開始，以為步長依次刪除個下標對應的中心向量，然后將剩下的M個中心向量依次作為A_j，j＝1,2,…,M，通過每個子區域的中心向量找出每個子區域的T個相鄰的子區域，參考指標為兩個中心向量的余弦值；

(5)計算粒子群POP中每個粒子目標函數值時，將每個粒子的位置和無人車起止點的位置組合,形成每個粒子相對應的路徑，計算各粒子對應路徑的參考指標，然后將其作為各粒子的目標函數值，接著確定參考點R，用于計算每個粒子的方向向量，令參考點R為原點O；

(6)進行粒子的分類與更新操作，接著將當前所有子區域的粒子位置信息存入集合EPOP中，并計算新粒子的方向向量，清空POP備用；

(7)gbest的選擇：產生[0,1]之間的隨機數rd₁,當rd₁大于閾值0.8時，隨機從EPOP集合中選擇一個粒子作為當前粒子的gbest；否則，在該粒子所在區域的鄰域內操作：首先計算該粒子鄰域中每個子區域的中心向量和該子區域中粒子方向向量的余弦值，然后選出余弦值最大的子區域中的粒子作為當前粒子的gbest；產生[0,1]之間的隨機數rd₂,當rd₂小于閾值0.6時，對選出的引導粒子位置進行連續變異操作，否則，不對gbest進行變異操作；

(8)pbest的選擇：產生[0,1]之間的隨機數rd₃，當rd₃大于閾值0.8時，隨機從EPOP集合中選擇一個粒子；否則，從該粒子的所在區域的鄰域中隨機選擇一個粒子，讓當前粒子和這個隨機選出的粒子進行比較，選出支配權優先的作為當前粒子的pbest；

(9)通過上述選出的gbest和pbest，根據粒子速度和位置更新公式產生下一代新的粒子群體，若新的粒子位置超出相應的約束范圍，就令新粒子的位置點為邊界值，所有新粒子的位置集合記為NPOP，下一代新的速度集合重新覆蓋集合V，速度和位置更新公式分別如下：

其中k指粒子群中第k個粒子，t為當前迭代次數，W為權衡局部搜索和全局搜索的參數，W∈[0.1,0.9]，C₁和C₂為學習因子，其大小都為2，R₁和R₂都是[0，1]之間的隨機數，pbest指當前粒子最好位置，gbest指引導粒子的位置，指在第t次迭代中第k個粒子的速度，指在第t次迭代中第k個粒子的位置；

(10)如果tgmax，則循環結束，輸出EPOP作為最優解集，否則把EPOP和NPOP合并放入POP中，然后跳轉至步驟(5)繼續循環；

(11)通過最優解中的粒子和起止點規劃出無人車的行駛路徑。