[發(fā)明專利]移動機器人及其基于自適應(yīng)遺傳算法的路徑規(guī)劃方法

有效

• 申請?zhí)枺?/td>: 202011486397.1
• 申請日: 2020-12-16
• 公開（公告）號: CN112686429B
• 公開（公告）日: 2022-07-29
• 發(fā)明（設(shè)計）人: 郝琨;趙家樂;趙璐;于凱丞
• 申請（專利權(quán)）人: 天津城建大學(xué)
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/12;G01C21/20
• 代理公司: 石家莊知住優(yōu)創(chuàng)知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 13131
• 代理人: 林艷艷

1.一種基于自適應(yīng)遺傳算法的移動機器人路徑規(guī)劃方法，其特征在于，所述的基于自適應(yīng)遺傳算法的移動機器人路徑規(guī)劃方法包括按順序進(jìn)行的下列步驟：

步驟一：進(jìn)行地圖建模和地圖預(yù)處理；采用柵格法建立地圖模型，將移動機器人所處的二維工作空間劃分為若干個大小相等的柵格，然后對每一個柵格進(jìn)行編號，將可行區(qū)域標(biāo)記為白色，將不可行區(qū)域標(biāo)記為黑色，形成柵格模型；對所述柵格模型進(jìn)行預(yù)處理，將移動機器人等效為質(zhì)量點同時對障礙物做膨脹化處理，若障礙物為不規(guī)則障礙物，則將障礙物所處的柵格全部標(biāo)記為黑色；若一個白色柵格的八個方向全部為黑色柵格，則此白色柵格也標(biāo)記為黑色柵格，生成柵格地圖；

步驟二：在步驟一生成的柵格地圖上，運用自適應(yīng)遺傳算法，得到一條優(yōu)質(zhì)可行路徑；

步驟三：設(shè)計碰撞檢測算法，檢測步驟二中生成的路徑是否與障礙物發(fā)生碰撞，若一條路徑由若干個路徑點所組成，檢測該路徑中所有相鄰路徑點的連線是否與障礙物柵格發(fā)生碰撞，如果所有相鄰路徑點連線均不與障礙物柵格發(fā)生碰撞，則認(rèn)為該路徑不與障礙物柵格發(fā)生碰撞；若有任何一個相鄰路徑點連線與障礙物柵格發(fā)生了碰撞，則認(rèn)為該路徑與障礙物柵格發(fā)生了碰撞；

步驟四：設(shè)計優(yōu)化算子，刪除掉路徑中的冗余路徑點，從而簡化路徑；

步驟五：通過優(yōu)化算子對步驟二中自適應(yīng)遺傳算法生成的優(yōu)質(zhì)可行路徑進(jìn)行第二次優(yōu)化，從而得到一條改善的路徑；

在步驟二中，當(dāng)生成柵格地圖后，利用自適應(yīng)遺傳算法生成優(yōu)質(zhì)可行路徑的具體方法是：

2.1選擇編碼方式，采用實數(shù)編碼，即采用柵格編號表示柵格位置的編碼方式；

2.2生成初始種群；采用先驗知識加隨機擾動的方法進(jìn)行種群初始化；假設(shè)list表為空，將起始節(jié)點作為當(dāng)前柵格節(jié)點加入list表中，則生成初始種群中某一個體的具體步驟如下：

2.2.1在地圖內(nèi)，以50％的概率選擇終點作為目標(biāo)點，以剩下的50％的概率選擇任意一個自由柵格作為目標(biāo)點；轉(zhuǎn)入步驟2.2.2；

2.2.2計算出當(dāng)前柵格節(jié)點周圍的鄰居?xùn)鸥窬嚯x目標(biāo)點的歐幾里得距離，若該鄰居?xùn)鸥駷檎系K物柵格，則將該鄰居?xùn)鸥窬嚯x目標(biāo)點的歐幾里得距離記為無窮大，轉(zhuǎn)入步驟2.2.3；

2.2.3通過歐幾里得距離，選擇距離目標(biāo)點最近的鄰居?xùn)鸥褡鳛楫?dāng)前柵格節(jié)點并將該當(dāng)前柵格節(jié)點加入list表中，若該當(dāng)前柵格節(jié)點為終點，則個體生成結(jié)束，list表中的柵格編號集合即為生成的個體；若該當(dāng)前柵格節(jié)點不為終點，則轉(zhuǎn)入步驟2.2.1；

通過上述步驟可以生成初始種群中的某一個體，若初始種群所需要的個體數(shù)量為m，則需要將上述步驟執(zhí)行m次；

2.3設(shè)計適應(yīng)度函數(shù)；綜合考慮路徑長度、路徑平滑度、路徑安全性評價指標(biāo)，通過加權(quán)和的形式，將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，總適應(yīng)度函數(shù)定義如下：

fitness＝w1*f1+w2*f2+w3*f3 (3)

其中，f1表示路徑長度的適應(yīng)度函數(shù)，f2表示路徑平滑度的適應(yīng)度函數(shù)，f3表示路徑安全性的適應(yīng)度函數(shù)；w1、w2、w3分別為三者的權(quán)重且和為1；

f1、f2、f3定義如下：

其中，path表示路徑長度，smoothness表示路徑平滑度，safety表示路徑安全性；

假設(shè)一條路徑由n個路徑點組成，第i個路徑點的坐標(biāo)為P_i(x_i，y_i)，第i+1個路徑點的坐標(biāo)為P_i+1(x_i+1，y_i+1)，則路徑長度可表示為：

假設(shè)一條路徑由n個路徑點組成，第i-1個路徑點的坐標(biāo)為P_i-1(x_i-1，y_i-1)，第i個路徑點的坐標(biāo)為P_i(x_i，y_i)，第i+1個路徑點的坐標(biāo)為P_i+1(x_i+1，y_i+1)，三個連續(xù)路徑點可形成兩個路徑段P_i-1P_i和P_iP_i+1；設(shè)θ_i為兩路徑段P_i-1P_i和P_iP_i+1之間的旋轉(zhuǎn)角，則路徑平滑度可表示為：

θ_i的計算公式如下所示：

α_i＝cos^-1d_i (13)

公式(7)、公式(8)分別計算了兩路徑段P_i-1P_i和P_iP_i+1的斜率，公式(9)根據(jù)兩路徑段斜率之間的關(guān)系，討論了θ_i的取值情況；在公式(9)中，α_i表示兩路徑段P_i-1P_i和P_iP_i+1之間的夾角，公式(10)到公式(13)為α_i的計算過程，其中cos^-1表示反余弦函數(shù)；

假設(shè)一條路徑由n個路徑點組成，第i個路徑點的坐標(biāo)為P_i(x_i，y_i)，則路徑安全性可表示為：

在公式(14)中，S_i表示第i個路徑點所獲得的安全懲罰度；在公式(15)中，punishment_ω_j表示第i個路徑點周圍的第j個柵格所提供的安全懲罰度；其中ω_j表示第i個路徑點周圍的第j個柵格；在公式(16)中，如果ω_j是障礙物柵格且沒有為其它路徑點提供過安全懲罰度，則會給第i個路徑點提供0.1的安全懲罰度；如果ω_j不是障礙物柵格，則不會給第i個路徑點提供安全懲罰度，即提供的安全懲罰度為0；如果ω_j是障礙物柵格但已經(jīng)為其它路徑點提供過安全懲罰度，則也不會給第i個路徑點提供安全懲罰度；

2.4選擇算子；將輪盤賭選擇與精英選擇進(jìn)行融合，使算法快速收斂到一個高質(zhì)量的解；假設(shè)種群有m個個體，則將輪盤賭選擇與精英選擇進(jìn)行融合的具體過程如下：

2.4.1計算出群體中每個個體的適應(yīng)度f(x_i)，i＝1，2，…，m，并將適應(yīng)度值最大的個體標(biāo)記為精英個體；

2.4.2計算出每個個體被遺傳到下一代群體中的概率；計算公式如下所示：

其中，p(x_i)表示第i個個體被遺傳到下一代群體中的概率，f(x_i)表示第i個個體的適應(yīng)度；

2.4.3計算出每個個體的累積概率；計算公式如下所示：

其中，q_i稱為第i個個體的累積概率；

2.4.4在[0，1]區(qū)間內(nèi)產(chǎn)生一個均勻分布的偽隨機數(shù)r；

2.4.5若r＜q₁，則選擇個體1；否則，選擇個體k，使得q_k-1＜r≤q_k成立；

2.4.6重復(fù)2.4.4和2.4.5共m次，得到m個新個體；所述m個新個體組成一個新種群；

2.4.7利用精英個體替換掉新種群中適應(yīng)度值最小的個體；

2.5交叉算子；采用一種新的自適應(yīng)交叉概率，既考慮種群中個體之間的關(guān)系，又考慮個體與迭代次數(shù)之間的關(guān)系；

新的自適應(yīng)交叉概率公式如下：

在公式(19)中，pc_temp是公式(20)中的一個參數(shù)，f是兩個被選中的個體中較大的適應(yīng)度值，f_max是整個種群中的最大適應(yīng)度，f_avg是整個種群的平均適應(yīng)度，pc_high為一個大于pc_low且取值在0到1之間的固定常數(shù)，pc_low為一個小于pc_high且取值在0到1之間的固定常數(shù)，當(dāng)f_max等于f_avg時，就意味著整個種群此時已經(jīng)收斂或者接近收斂，這時pc_temp會被賦予一個非常小的值pc_low；當(dāng)f_max不等于f_avg且f小于f_avg時，就意味著該個體較差，更需要進(jìn)化，這時pc_temp會被賦予pc_high；當(dāng)f_max不等于f_avg且f大于等于f_avg時，就意味著該個體較好，更需要保護(hù)，這時pc_temp會按照一個特定的概率計算公式被賦值；在公式(20)中，e為自然對數(shù)函數(shù)的底數(shù)，T為總迭代次數(shù)，t為當(dāng)前迭代次數(shù)；

交叉方式采用傳統(tǒng)的單點交叉；

2.6變異算子；采用一種新的自適應(yīng)變異概率，既考慮種群中個體之間的關(guān)系，又考慮個體與迭代次數(shù)之間的關(guān)系；

新的自適應(yīng)變異概率公式如下：

在公式(21)中，pm_temp是公式(22)中的一個參數(shù)，f是被選中個體的適應(yīng)度值，f_max是整個種群中的最大適應(yīng)度，f_avg是整個種群的平均適應(yīng)度，pm_high為一個大于pm_low且取值在0到1之間的固定常數(shù)，pm_low為一個小于pm_high且取值在0到1之間的固定常數(shù)；當(dāng)f_max等于f_avg時，就意味著整個種群此時已經(jīng)收斂或者接近收斂，這時pm_temp會被賦予pm_high，用于嘗試能否得到更好的解；當(dāng)f_max不等于f_avg且f小于f_avg時，就意味著該個體較差，更需要進(jìn)化，這時pm_temp會被賦予pm_high；當(dāng)f_max不等于f_avg且f大于等于f_avg時，就意味著該個體較好，更需要保護(hù)，這時pm_temp會按照一個特定的概率計算公式被賦值；在公式(22)中，e為自然對數(shù)函數(shù)的底數(shù)；T為總迭代次數(shù)，t為當(dāng)前迭代次數(shù)；

變異方式采用傳統(tǒng)的單點變異；

所述步驟四中冗余路徑點的確定方法為：由路徑上的相鄰路徑點形成若干路徑段，假設(shè)所述若干路徑段均不經(jīng)過障礙物，嘗試將其中一個中間路徑點去掉，直接連接分別與中間路徑點相鄰的兩個路徑點形成相隔路徑段，判斷相隔路徑段是否經(jīng)過障礙物，若相隔路徑段不經(jīng)過障礙物，則所述中間路徑點就為冗余路徑點，若相隔路徑段經(jīng)過障礙物，則所述中間路徑點就不為冗余路徑點。