0 引言
由于巨大的市場(chǎng)需求以及廣闊的應(yīng)用前景，移動(dòng)機(jī)器人廣泛應(yīng)用于工業(yè)制造、生活服務(wù)、交通運(yùn)輸、醫(yī)療健康等領(lǐng)域，路徑規(guī)劃是提升移動(dòng)機(jī)器人功能性能的關(guān)鍵技術(shù)之一。路徑規(guī)劃的主要目的是在有障礙物的環(huán)境下尋找到一條從起始位置到目標(biāo)位置、不發(fā)生碰撞的最優(yōu)路徑。根據(jù)對(duì)環(huán)境信息的了解程度不同，傳統(tǒng)路徑規(guī)劃算法可以分為全局路徑規(guī)劃和局部路徑規(guī)劃兩類，目前，常用的全局路徑規(guī)劃算法包括Dijkstra算法"、A*算法2、D*算法等，局部路徑規(guī)劃算法包括動(dòng)態(tài)窗口法、人工勢(shì)場(chǎng)法等。
全局路徑規(guī)劃算法中，A*算法是廣泛應(yīng)用于路徑規(guī)劃的經(jīng)典算法，其計(jì)算簡(jiǎn)單、規(guī)劃路徑短，但仍存在拐點(diǎn)冗余、搜索效率低、運(yùn)行時(shí)間長(zhǎng)等問(wèn)題，難以在短時(shí)間內(nèi)規(guī)劃出最優(yōu)路徑。對(duì)此，諸多學(xué)者針對(duì)傳統(tǒng)A*算法的改進(jìn)展開研究。搜索策略優(yōu)化方面，文獻(xiàn)[6]提出一種可搜索24鄰域的A*算法，通過(guò)將傳統(tǒng)A*算法的8鄰域搜索策略更改為24鄰域搜索策略，解決傳統(tǒng)A*算法中路徑長(zhǎng)度不優(yōu)和轉(zhuǎn)折點(diǎn)過(guò)多的問(wèn)題；文獻(xiàn)[7]進(jìn)一步將傳統(tǒng)A*算法的搜索鄰域擴(kuò)展到48鄰域，優(yōu)化搜索角度并去除同方向上的多余子節(jié)點(diǎn)，增強(qiáng)規(guī)劃路徑質(zhì)量。評(píng)價(jià)函數(shù)優(yōu)化方面，文獻(xiàn)[8]在評(píng)價(jià)函數(shù)的設(shè)計(jì)中加入路徑曲率的影響代價(jià)，減少路徑中方向變化較大的轉(zhuǎn)彎點(diǎn)，提高路徑平滑度；文獻(xiàn)[9]引入障礙率作為評(píng)價(jià)函數(shù)的影響因子，避免計(jì)算資源的浪費(fèi)，提高算法的檢索速度。路徑平滑優(yōu)化方面，文獻(xiàn)[10]使用貝塞爾曲線對(duì)規(guī)劃后的路徑進(jìn)行平滑，分別對(duì)規(guī)劃后路徑中曲折較大的部分使用二階貝塞爾曲線進(jìn)行平滑，提高路徑平滑度；文獻(xiàn)[11]使用動(dòng)態(tài)窗口法對(duì)規(guī)劃后的路徑進(jìn)行平滑，考慮移動(dòng)機(jī)器人的運(yùn)動(dòng)條件，提升路徑的平滑度和移動(dòng)機(jī)器人的安全性。上述改進(jìn)算法都在一定程度上提高了A*算法規(guī)劃路徑的質(zhì)量，但對(duì)算法降低運(yùn)算時(shí)間和減少關(guān)鍵節(jié)點(diǎn)方面效果有限。
局部路徑規(guī)劃中較為常用的是動(dòng)態(tài)窗口法，其模型簡(jiǎn)單、具有良好的局部避障能力，但存在運(yùn)動(dòng)狀態(tài)單一、容易陷入局部最優(yōu)等缺點(diǎn)。對(duì)此，一些學(xué)者對(duì)動(dòng)態(tài)窗口法的評(píng)價(jià)函數(shù)進(jìn)行優(yōu)化，文獻(xiàn)[12]對(duì)動(dòng)態(tài)窗口法評(píng)價(jià)函數(shù)中速度評(píng)價(jià)的權(quán)值進(jìn)行動(dòng)態(tài)調(diào)整，獲得更加合理的路徑，使機(jī)器人移動(dòng)更加安全可靠；文獻(xiàn)[13]向動(dòng)態(tài)窗口法評(píng)價(jià)函數(shù)中引入規(guī)則評(píng)價(jià)函數(shù)，即避讓障礙物幅度越大越好，減少碰撞風(fēng)險(xiǎn)，提高路徑安全性。上述改進(jìn)算法對(duì)路徑的安全性有一定的提升，但缺乏對(duì)陷入局部最優(yōu)問(wèn)題的考慮。針對(duì)動(dòng)態(tài)窗口法和全局路徑規(guī)劃算法的融合，文獻(xiàn)[14]針對(duì)傳統(tǒng)A*算法在柵格數(shù)量較多時(shí)存在折點(diǎn)多、耗時(shí)長(zhǎng)，以及動(dòng)態(tài)窗口法在復(fù)雜環(huán)境下靈活性差的問(wèn)題，提出一種融合改進(jìn)A*算法和優(yōu)化動(dòng)態(tài)窗口法的路徑規(guī)劃算法；文獻(xiàn)[15]將A*算法和動(dòng)態(tài)窗口法相結(jié)合，將A*算法規(guī)劃后的路徑作為動(dòng)態(tài)窗口法的全局路徑指引，避免動(dòng)態(tài)窗口法容易陷入局部最優(yōu)的問(wèn)題。
基于上述研究，針對(duì)復(fù)雜環(huán)境下移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題，傳統(tǒng)A*算法存在拐點(diǎn)冗余、搜索效率低、運(yùn)行時(shí)間長(zhǎng)等不足，傳統(tǒng)動(dòng)態(tài)窗口法存在運(yùn)動(dòng)狀態(tài)單一、容易陷入局部最優(yōu)等不足。結(jié)合現(xiàn)有文獻(xiàn)對(duì)A*算法和動(dòng)態(tài)窗口法的改進(jìn)思路分析，本文提出一種將改進(jìn)A*算法與改進(jìn)動(dòng)態(tài)窗口法相結(jié)合的融合路徑規(guī)劃算法。
1 改進(jìn)A*算法
1.1 傳統(tǒng)A*算法
A*算法相較于Dijkstra算法，其優(yōu)勢(shì)在于引入啟發(fā)式函數(shù)，有效避免了盲目搜索，大大提高了搜索效率。其評(píng)價(jià)函數(shù)通常為
式中：F(n)為從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的預(yù)估總代價(jià)；G(n)為起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的實(shí)際代價(jià)；H(n)為當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的預(yù)估代價(jià)。
常用的H(n)計(jì)算方法有曼哈頓距離、歐幾里得距離和切比雪夫距離。為了更符合機(jī)器人移動(dòng)時(shí)的實(shí)際距離，本文采用歐幾里得距離進(jìn)行路徑計(jì)算，歐幾里得距離計(jì)算公式為
式中：x1、y1和x2、y2分別為當(dāng)前節(jié)點(diǎn)的坐標(biāo)和目標(biāo)節(jié)點(diǎn)的坐標(biāo)。
A*算法主要通過(guò)更新OpenList表和CloseList表來(lái)實(shí)現(xiàn)節(jié)點(diǎn)的篩選，OpenList表中存儲(chǔ)著待擴(kuò)展節(jié)點(diǎn)以及相應(yīng)的代價(jià)值和父節(jié)點(diǎn)信息，CloseList表中存儲(chǔ)著已經(jīng)擴(kuò)展過(guò)的節(jié)點(diǎn)以及相應(yīng)的代價(jià)值和父節(jié)點(diǎn)信息。
1.2 改進(jìn)A*算法
1.2.1 5鄰域搜索策略
傳統(tǒng)A*算法的搜索方式如圖1所示，采用8鄰域搜索方式來(lái)搜索下一個(gè)擴(kuò)展節(jié)點(diǎn)。為了避免算法運(yùn)算資源的浪費(fèi)，本文將傳統(tǒng)8鄰域搜索方式更改為5鄰域搜索方式，如表1所示，根據(jù)當(dāng)前節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的連線與節(jié)點(diǎn)p,指向的夾角，假設(shè)夾角為θ，順時(shí)針?lè)较驗(yàn)檎较?，根?jù)夾角θ的范圍，選擇其中5個(gè)方向進(jìn)行探索，減少冗余節(jié)點(diǎn)，提高算法效率。
1.2.2 自適應(yīng)評(píng)價(jià)函數(shù)
傳統(tǒng)A*算法的評(píng)價(jià)函數(shù)是由起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的實(shí)際移動(dòng)成本G(n)和當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的估計(jì)移動(dòng)成本H(n)組合而成，兩者的占比從路徑規(guī)劃開始到路徑規(guī)劃結(jié)束都不會(huì)改變。本文根據(jù)地圖規(guī)格和位置信息在傳統(tǒng)A*算法啟發(fā)函數(shù)基礎(chǔ)上加入動(dòng)態(tài)加權(quán)因子W，當(dāng)前節(jié)點(diǎn)遠(yuǎn)離目標(biāo)節(jié)點(diǎn)時(shí)，加權(quán)因子較大，H(n)占比較大，加快搜索速度；當(dāng)前節(jié)點(diǎn)接近目標(biāo)節(jié)點(diǎn)時(shí)，加權(quán)因子較小，H(n)占比較小，提高搜索精度。
式中：W為根據(jù)地圖的長(zhǎng)寬之和以及當(dāng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的曼哈頓距離計(jì)算的加權(quán)因子。
式中：x1，，y1，和x2，，y2，為待求曼哈頓距離的當(dāng)前節(jié)點(diǎn)和待求節(jié)點(diǎn)的坐標(biāo)；m、n為柵格地圖的長(zhǎng)和寬。
圖1.節(jié)點(diǎn)擴(kuò)展方向示意圖
表1.節(jié)點(diǎn)方向選擇表
1.2.3關(guān)鍵節(jié)點(diǎn)提取策略
針對(duì)傳統(tǒng)A*算法在規(guī)劃得到最優(yōu)路徑之后，最優(yōu)路徑仍然存在拐點(diǎn)冗余的問(wèn)題，本文對(duì)規(guī)劃后的路徑采用關(guān)鍵節(jié)點(diǎn)提取算法，通過(guò)判斷節(jié)點(diǎn)之間的連線是否經(jīng)過(guò)障礙物，有效去除無(wú)效拐點(diǎn)。關(guān)鍵節(jié)點(diǎn)提取如圖2所示，算法的具體實(shí)現(xiàn)步驟如下。
步驟1：連接p1和p3節(jié)點(diǎn)，計(jì)算p1和p3的連接線是否穿過(guò)障礙物，如未穿過(guò)障礙物，則將規(guī)劃后路徑中的p2節(jié)點(diǎn)刪除；
步驟2：連接p1和p4節(jié)點(diǎn)，計(jì)算p1和p4的連接線是否穿過(guò)障礙物，如果p1和p4的連接線穿過(guò)障礙物，則p3為關(guān)鍵拐點(diǎn)，不可刪除；
步驟3：將p3作為關(guān)鍵路徑選擇的新起始節(jié)點(diǎn)，重復(fù)計(jì)算步驟1和步驟2，直到遍歷完規(guī)劃后路徑中的所有節(jié)點(diǎn)為止；
步驟4：將刪除冗余拐點(diǎn)后的路徑作為規(guī)劃后的最終路徑。
圖2.關(guān)鍵節(jié)點(diǎn)提取
2 改進(jìn)動(dòng)態(tài)窗口法
動(dòng)態(tài)窗口法是一種局部路徑規(guī)劃算法，通過(guò)對(duì)機(jī)器人速度信息進(jìn)行采樣，得到在規(guī)定速度區(qū)間內(nèi)的各個(gè)速度值，然后針對(duì)每個(gè)速度值生成對(duì)應(yīng)的預(yù)測(cè)軌跡。通過(guò)軌跡評(píng)價(jià)函數(shù)進(jìn)行軌跡評(píng)估，從所有采樣的預(yù)測(cè)軌跡中選擇出一條最優(yōu)的軌跡來(lái)指導(dǎo)機(jī)器人移動(dòng)。針對(duì)該算法缺乏全局指引容易陷入局部最優(yōu)的問(wèn)題，向傳統(tǒng)動(dòng)態(tài)窗口法的評(píng)價(jià)函數(shù)中引入偏離距離函數(shù)，使機(jī)器人移動(dòng)時(shí)更加貼近全局最優(yōu)路徑。
2.1 機(jī)器人運(yùn)動(dòng)軌跡模型
動(dòng)態(tài)窗口模型是一種模擬機(jī)器人運(yùn)動(dòng)軌跡的方法，它基于機(jī)器人的初始位姿和速度信息，通過(guò)設(shè)定一段時(shí)間間隔△t內(nèi)的勻速運(yùn)動(dòng)，生成機(jī)器人可能的動(dòng)作軌跡信息。
式中：xn、yn、θn,為機(jī)器人在下一時(shí)刻的位姿信息；xn-1、yn-1、θn-1為機(jī)器人在當(dāng)前時(shí)刻的位置信息；ω、ν為機(jī)器人的線速度和角速度，△t為維持勻速運(yùn)動(dòng)的時(shí)間。
2.2 速度采樣
在速度環(huán)境中，有多組可以選擇的線速度和角速度，由于機(jī)器人存在自身的性能和周圍環(huán)境的限制，需要對(duì)采樣速度的范圍進(jìn)行限制。
(1）機(jī)器人自身速度約束
式中：νmin、,νmax為機(jī)器人最小線速度和最大線速度；ωmin、ωmax為機(jī)器人最小角速度和最大角速度。
(2）機(jī)器人電機(jī)性能加減速約束
(3）機(jī)器人安全制動(dòng)約束
式中：dist(ν,ω)為在當(dāng)前速度(ν,ω)時(shí)距離障礙物的最小距離。
最終動(dòng)態(tài)窗口的采樣速度需要滿足集合V，即滿足上述3種約束的集合：
基于對(duì)線速度和角速度樣本數(shù)量的考量，對(duì)連續(xù)速度矢量空間進(jìn)行離散化處理，以獲得離散采樣點(diǎn)(ν,ω)。在獲得這些采樣點(diǎn)之后，利用機(jī)器人運(yùn)動(dòng)學(xué)模型對(duì)每個(gè)采樣點(diǎn)進(jìn)行分析，以預(yù)測(cè)機(jī)器人在下一個(gè)時(shí)刻的運(yùn)動(dòng)軌跡，如圖3所示。
圖3.軌跡預(yù)測(cè)
2.3 優(yōu)化評(píng)價(jià)函數(shù)
在速度信息采樣預(yù)測(cè)的軌跡中，除去已經(jīng)與障礙物發(fā)生碰撞的軌跡，還存在許多可選的運(yùn)動(dòng)軌跡，需要通過(guò)評(píng)價(jià)函數(shù)對(duì)這些軌跡進(jìn)行計(jì)算，篩選出評(píng)價(jià)指標(biāo)最高的運(yùn)動(dòng)軌跡，傳統(tǒng)的評(píng)價(jià)函數(shù)為
式中：heading(ν,ω)為方位角評(píng)價(jià)函數(shù)，表示在當(dāng)前選擇的速度組模擬的軌跡末端朝向與目標(biāo)點(diǎn)位置航向角之間的角度偏差，角度偏差越小取值越大；dist(ν,ω)為障礙物評(píng)價(jià)函數(shù)，表示在當(dāng)前選擇的速度組模擬的軌跡距離障礙物的最小距離，距離越大取值越大；velocity(ν,ω)為速度評(píng)價(jià)函數(shù)，表示在當(dāng)前選擇的速度組模擬的軌跡的速度大小，速度越大取值越大；σ為平滑系數(shù)，α、β、γ為加權(quán)系數(shù)。
針對(duì)傳統(tǒng)動(dòng)態(tài)窗口法容易陷入局部最優(yōu)，易產(chǎn)生偏離全局路線的現(xiàn)象，為確保路徑的平滑性和安全性，本文在其原有評(píng)價(jià)函數(shù)的基礎(chǔ)上，引入偏離距離評(píng)價(jià)函數(shù)，即計(jì)算軌跡路線與全局路線之間的距離，將評(píng)價(jià)函數(shù)修改為
式中：dist_off(ν,ω)為在當(dāng)前選擇的速度組模擬的軌跡路線與全局路線之間的距離，距離越小取值越大。
2.4 改進(jìn)A*算法與改進(jìn)動(dòng)態(tài)窗口法融合
本文將改進(jìn)A*算法與改進(jìn)動(dòng)態(tài)窗口法相結(jié)合，使用改進(jìn)A*算法進(jìn)行全局路徑規(guī)劃，得到最優(yōu)路徑；對(duì)最優(yōu)路徑使用關(guān)鍵點(diǎn)提取策略進(jìn)行關(guān)鍵點(diǎn)提取，剔除不必要的冗余拐點(diǎn)；將提取后的關(guān)鍵節(jié)點(diǎn)作為改進(jìn)動(dòng)態(tài)窗口法的全局指導(dǎo)，在規(guī)定的速度區(qū)間內(nèi)按采樣頻率進(jìn)行采樣，得到預(yù)測(cè)軌跡，利用改進(jìn)評(píng)價(jià)函數(shù)選擇出最優(yōu)的軌跡，達(dá)到局部路徑優(yōu)化的效果，具體流程如圖4所示。
圖4.融合算法流程圖
3 仿真與實(shí)驗(yàn)
3.1 實(shí)驗(yàn)環(huán)境
本次仿真環(huán)境由操作系統(tǒng)Windows10、顯卡NVIDIA GeForce RTX 3060、處理器 Intel(R) Core(TM）[email protected]、仿真軟件MATLABR2021a組成。使用MATLAB建立路徑規(guī)劃區(qū)域和柵格地圖，初始化移動(dòng)機(jī)器人屬性以及動(dòng)態(tài)窗口法初始屬性如表2所示。
表2.移動(dòng)機(jī)器人屬性以及動(dòng)態(tài)窗口法初始屬性
3.2 改進(jìn)A*算法仿真實(shí)驗(yàn)及分析
為了驗(yàn)證改進(jìn)A*算法的有效性，采取不同環(huán)境進(jìn)行仿真實(shí)驗(yàn)，將本文改進(jìn)A*算法與傳統(tǒng)A*算法、文獻(xiàn)[16]改進(jìn)A*算法進(jìn)行對(duì)比；仿真實(shí)驗(yàn)環(huán)境為二維柵格地圖，黑色柵格為障礙物節(jié)點(diǎn)、白色柵格為可通過(guò)節(jié)點(diǎn)、綠色三角形為起始節(jié)點(diǎn)、紅色圓圈為目標(biāo)節(jié)點(diǎn)。仿真實(shí)驗(yàn)分別設(shè)置了2組障礙率為20%但規(guī)格不同的地圖，仿真實(shí)驗(yàn)結(jié)果如圖5所示，數(shù)據(jù)對(duì)比如表3所示。
圖5不同A*算法路徑對(duì)比
表3改進(jìn)算法結(jié)果對(duì)比
分析表3數(shù)據(jù)可以得到以下結(jié)論：在柵格規(guī)模為20×20的環(huán)境下，在路徑長(zhǎng)度方面，相比傳統(tǒng)A*算法文獻(xiàn)[16]中改進(jìn)A*算法減少0.21%，本文改進(jìn)A*算法減少1.07%；在算法運(yùn)算時(shí)間方面，相比傳統(tǒng)A*算法文獻(xiàn)[16]改進(jìn)A*算法減少16%，本文改進(jìn)A*算法減少36%。在柵格規(guī)模為30×30的環(huán)境下，路徑長(zhǎng)度方面，文獻(xiàn)[16]中改進(jìn)A*算法減少0.13%，本文改進(jìn)A*算法減少0.69%；在算法運(yùn)算時(shí)間方面，文獻(xiàn)[16]改進(jìn)A*算法減少34%，本文改進(jìn)A*算法減少67%。綜上所述，本文改進(jìn)A*算法隨著地圖柵格規(guī)模的增加，雖然在最優(yōu)路徑長(zhǎng)度方面的減少百分比并沒(méi)有逐漸增加，但在算法運(yùn)算時(shí)間方面的減少百分比增加更加明顯，可以有效提高路徑規(guī)劃的運(yùn)行效率。
3.3 融合算法仿真實(shí)驗(yàn)及分析
為驗(yàn)證本文改進(jìn)動(dòng)態(tài)窗口法以及本文融合算法的有效性，將本文改進(jìn)A*算法分別與傳統(tǒng)動(dòng)態(tài)窗口法、文獻(xiàn)[17]中改進(jìn)動(dòng)態(tài)窗口法、本文改進(jìn)動(dòng)態(tài)窗口法相融合，并分別在不同的實(shí)驗(yàn)環(huán)境下進(jìn)行實(shí)驗(yàn)對(duì)比。仿真實(shí)驗(yàn)環(huán)境為二維柵格地圖，黑色柵格為障礙物節(jié)點(diǎn)、白色柵格為可通過(guò)節(jié)點(diǎn)、綠色三角形為起始節(jié)點(diǎn)、紅色圓圈為目標(biāo)節(jié)點(diǎn)。仿真實(shí)驗(yàn)設(shè)置的地圖為有效障礙率為20%的20×20規(guī)格地圖和有效障礙率為30%的30×30規(guī)格地圖。仿真實(shí)驗(yàn)結(jié)果如圖6所示，數(shù)據(jù)對(duì)比如表4所示。
圖6不同融合動(dòng)態(tài)窗口算法路徑對(duì)比
表4融合算法結(jié)果對(duì)比
由于改進(jìn)A*算法規(guī)劃后的路徑依然不是很平滑，故使用動(dòng)態(tài)窗口法再次進(jìn)行平滑操作。融合傳統(tǒng)DWA算法和融合文獻(xiàn)[17]改進(jìn)DWA算法均發(fā)生碰撞障礙物情況，融合本文改進(jìn)DWA算法沒(méi)有出現(xiàn)碰撞情況。分析表4數(shù)據(jù)可以得到以下結(jié)論：在柵格規(guī)模為20×20且有效障礙率為20%的環(huán)境下，在路徑長(zhǎng)度方面，融合本文改進(jìn)DWA算法相比于融合傳統(tǒng)DWA算法減少1.35%，相比于融合文獻(xiàn)[17]改進(jìn)DWA算法減少1.22%；在運(yùn)行時(shí)間方面，融合本文改進(jìn)DWA算法相比融合傳統(tǒng)DWA算法增加6.83%，相比融合文獻(xiàn)[17]改進(jìn)DWA算法增加5.4%。在柵格規(guī)模為30×30且有效障礙率為30%的環(huán)境下，路徑長(zhǎng)度方面，融合本文改進(jìn)DWA算法相比于融合傳統(tǒng)DWA算法減少1.98%，相比于融合文獻(xiàn)[17]改進(jìn)DWA算法減少1.93%；在算法運(yùn)行時(shí)間方面，融合本文改進(jìn)DWA算法相比于融合傳統(tǒng)DWA算法增加4.74%，相比于融合文獻(xiàn)[17]改進(jìn)DWA算法增加5.83%。綜上所述，隨著地圖規(guī)模的增加，融合本文改進(jìn)DWA算法雖然在運(yùn)算時(shí)間方面有所增長(zhǎng)，但在路徑長(zhǎng)度方面減少明顯
在物理學(xué)中，姿態(tài)角度、線速度和角速度是描述物體運(yùn)動(dòng)的重要物理量，其方差和標(biāo)準(zhǔn)差反映有關(guān)運(yùn)動(dòng)特性的統(tǒng)計(jì)信息。角度是描述物體朝向或者旋轉(zhuǎn)狀態(tài)的物理量，方差和標(biāo)準(zhǔn)差分別蘊(yùn)含角度均值及其變化的不確定性或穩(wěn)定性信息，方差和標(biāo)準(zhǔn)差越小，表示角度均值和角度變化越小，旋轉(zhuǎn)相對(duì)穩(wěn)定。速度(含線速度和角速度)是描述物體在某一時(shí)間點(diǎn)的位置變化率，方差和標(biāo)準(zhǔn)差可以提供關(guān)于速度均值及其變化的不確定性或穩(wěn)定性信息，方差和標(biāo)準(zhǔn)差越小，表示速度均值和速度變化越小，運(yùn)動(dòng)相對(duì)穩(wěn)定。計(jì)算融合算法移動(dòng)機(jī)器人的姿態(tài)角度、角速度和線速度的方差以及標(biāo)準(zhǔn)差，如圖7所示。
圖7不同融合算法運(yùn)動(dòng)狀態(tài)對(duì)比
通過(guò)在地圖規(guī)格為20×20有效障礙率為20%和地圖規(guī)格為30×30有效障礙率為30%的二維柵格地圖環(huán)境下進(jìn)行實(shí)驗(yàn)，分別計(jì)算融合算法規(guī)劃后機(jī)器人狀態(tài)中的角度、線速度和角速度的方差和標(biāo)準(zhǔn)差，運(yùn)算結(jié)果如表5~7所示。
分析表5~7可得，基于本文所提融合算法規(guī)劃得到的移動(dòng)機(jī)器人角度、線速度和角速度的方差和標(biāo)準(zhǔn)差都更小，說(shuō)明移動(dòng)機(jī)器人運(yùn)動(dòng)過(guò)程中角度、線速度和角速度的總體波動(dòng)幅度更小，運(yùn)動(dòng)更加平穩(wěn)。
表5不同融合算法角度變化
4 結(jié)論
本文介紹一種結(jié)合改進(jìn)A*算法和改進(jìn)動(dòng)態(tài)窗口法的融合算法。首先將傳統(tǒng)A*算法8鄰域搜索策略更改為5鄰域搜索策略，其次向其評(píng)價(jià)函數(shù)的啟發(fā)函數(shù)中添加動(dòng)態(tài)加權(quán)因子，然后對(duì)規(guī)劃得到的路徑進(jìn)行關(guān)鍵節(jié)點(diǎn)提取，去除冗余拐點(diǎn)，得到一條拐點(diǎn)較少的路徑。最后，改進(jìn)動(dòng)態(tài)窗口法的評(píng)價(jià)函數(shù)，將改進(jìn)A*算法得到的路徑作為改進(jìn)動(dòng)態(tài)窗口法的全局路徑指引，得到最優(yōu)平滑路徑。經(jīng)過(guò)仿真實(shí)驗(yàn)分析可得，基于本文所提融合算法得到的規(guī)劃路徑更加平滑、運(yùn)動(dòng)角度和速度變化更加平緩，有效提高移動(dòng)機(jī)器人的運(yùn)動(dòng)穩(wěn)定性和安全性。
然而，論文仍存在以下不足：一方面，加權(quán)因子根據(jù)當(dāng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)間的距離動(dòng)態(tài)調(diào)整，以平衡搜索速度與搜索效率，實(shí)際應(yīng)用中可能導(dǎo)致調(diào)試?yán)щy，未來(lái)將進(jìn)一步探索如何根據(jù)具體問(wèn)題自適應(yīng)確定加權(quán)因子；另一方面，雖然動(dòng)態(tài)窗口法有效提高了路徑平滑度，但可能導(dǎo)致計(jì)算復(fù)雜度增加，擬將對(duì)算法計(jì)算效率進(jìn)行深入分析和優(yōu)化。
參考文獻(xiàn)：
[1] Tang Meiqin, Sheng Jiawen, Sun Shaoyan, A CoverageOptimization Algorithm for Underwater Acoustic SensorNetworks Based on Dijkstra Method[JJ. IEEE/CAAJournal of Automatica Sinica, 2023, 10(8): 1769-1771.
[2]許建民，宋雷,鄧冬冬,等.基于多尺度A*與優(yōu)化DWA算法融合的移動(dòng)機(jī)器人路徑規(guī)劃[J/OL].系統(tǒng)仿真學(xué)報(bào).(2023-11-22) [2024-04-24].https://doi.org/10.16182/j.issn1004731x.joss.23-1089.Xu Jianmin, Song Lei, Deng Dongdong, et al. PathPlanning of Mobile Robot Based on the Integration ofMulti-scaleA'andOptimizedDynamic-windowApproachAlgorithm[J/OL]. Journalof SystemSimulation. (2023-11-22) [2024-04-24]. https://doi.org/10.16182/j.issn1004731x.joss.23-1089.
[3]］黃魯,周非同.基于路徑優(yōu)化D'Lite算法的移動(dòng)機(jī)器人路徑規(guī)劃[J].控制與決策,2020,35(4):877-884.Huang Lu, Zhou Feitong. Path Planning of MovingRobot Based on Path Optimization of D* Lite Algorithm[]. Control and Decision, 2020, 35(4): 877-884.
[4]常路，單梁,戴躍偉,等.未知環(huán)境下基于改進(jìn)DWA的多機(jī)器人編隊(duì)控制[J].控制與決策，2022,37(10):2524-2534.Chang Lu, Shan Liang, Dai Yuewei, et al. Multi-robotFormation Control in Unknown Environment Based onImproved DWA[J]. Control and Decision, 2022, 37(10):2524-2534.
[5］鮮斌，宋寧.基于模型預(yù)測(cè)控制與改進(jìn)人工勢(shì)場(chǎng)法的多無(wú)人機(jī)路徑規(guī)劃[J/OL].控制與決策.(2024-01-02)[2024-02-01]. https://doi.org/10.13195/j.kzyjc.2023.0892.Xian Bin, Song Ning. A Multiple UAVs Path PlanningMethod Based on Model Predictive Control andImproved Artificial Potential Field[J/OL]. Control andDecision.(2024-01-02) [2024-02-01]. https://doi.org/10.13195/j.kzyjc.2023.0892.
[6]】崔寶俠，王淼弛，段勇.基于可搜索24鄰域的A"算法路徑規(guī)劃[J].沈陽(yáng)工業(yè)大學(xué)學(xué)報(bào),2018,40(2)：180-184.Cui Baoxia, Wang Miaochi, Duan Yong. Path Planningfor A" Algorithm Based on Searching 24 Neighborhoods[J]. Journal of Shenyang University of Technology, 2018,40(2): 180-184.
[7]槐創(chuàng)鋒，郭龍，賈雪艷，等.改進(jìn)A*算法與動(dòng)態(tài)窗口法的機(jī)器人動(dòng)態(tài)路徑規(guī)劃[].計(jì)算機(jī)工程與應(yīng)用,2021,57(8): 244-248.Huai Chuangfeng, Guo Long, Jia Xueyan, ct al.Improved A*Algorithm and Dynamic Window Methodfor Robot Dynamic Path Planning[J].ComputerEngineering and Applications, 2021, 57(8): 244-248.[8] Min Haitao, Xiong Xiaoyong, Wang Pengyu, et al.Autonomous Driving Path Planning Algorithm Based onImproved A* Algorithm in Unstructured Environment[J].Proceedings of the Institution of Mechanical Engineers,Part D: Journal of Automobile Engineering, 2021, 235(2/3): 513-526.
[9]姬鵬，張新元,高帥軒，等.融合改進(jìn)A*算法與動(dòng)態(tài)窗口法的路徑規(guī)劃研究[J/OL].系統(tǒng)仿真學(xué)報(bào).(2023-09-07)[2024-03-13]. https://doi.org/10.16182/j.issn1004731x.joss.23-0619.Ji Peng, Zhang Xinyuan, Gao Shuaixuan, et al. PathPlanning Based on Improved A and Dynamic WindowApproach[J/OL]. Journal of System Simulation. (2023-09-07) [2024-03-13]. https://doi.org/10.16182/j. issn1004731x.joss.23-0619.
[10] Lai Rongshen, Wu Zhiyong, Liu Xiangui, et al. FusionAlgorithm of the Improved A Algorithm and SegmentedBézier Curves for the Path Planning of Mobile Robots[J].Sustainability, 2023, 15(3): 2483.[11]王彬，聶建軍，李海洋，等.優(yōu)化A*與動(dòng)態(tài)窗口法的移動(dòng)機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)集成制造系統(tǒng)，2024,30(4):1353-1363.Wang Bin, Nie Jianjun, Li Haiyang, et al. Mobile RobotPath Planning Based on Optimized A* and DynamicWindowAApproach[].ComputerManufacturing Systems, 2024, 30(4): 1353-1363.
[12]王永雄，田永永,李璇，等.穿越稠密障礙物的自適應(yīng)動(dòng)態(tài)窗口法[].控制與決策,2019,34(5):927-936.Wang Yongxiong, Tian Yongyong, Li Xuan, et al. SelfadaptiveDynamicWindow Approach in Dense Obstacles[]. Control and Decision, 2019, 34(5): 927-936.
[13]張偉龍，單梁，常路，等.基于改進(jìn)DWA的多無(wú)人水面艇分布式避碰算法[].控制與決策,2023,38(4):951-962.Zhang Weilong, Shan Liang, Chang Lu, et al. DistributedCollision Avoidance Algorithm for Multiple UnmannedSurface Vessels Based on Improved DWA[J]. Controland Decision, 2023, 38(4): 951-962.
[14]鄒文，韓丙辰，李鵬飛,等.融合改進(jìn)A*算法和優(yōu)化動(dòng)態(tài)窗口法的路徑規(guī)劃[J].計(jì)算機(jī)集成制造系統(tǒng)，2024,30(1): 184-195.Zou Wen, Han Bingchen, Li Pengfei, et al. Path Planningby Integrating Improved A* Algorithm and OptimizedDynamic Window Approach[J]. Computer IntegratedManufacturing Systems, 2024, 30(1): 184-195.
[15]程傳奇，郝向陽(yáng),李建勝，等.融合改進(jìn)A*算法和動(dòng)態(tài)窗口法的全局動(dòng)態(tài)路徑規(guī)劃[].西安交通大學(xué)學(xué)報(bào)，2017, 51(11): 137-143.Cheng Chuanqi, Hao Xiangyang, Li Jiansheng, et al.Global Dynamic Path Planning Based on Fusion ofImproved A* Algorithm and Dynamic Window Approach[]. Journal of Xi'an Jiaotong University, 2017, 51(11):137-143.
[16]張濤，陳璋，李玉梅，等.融合改進(jìn)A*算法與動(dòng)態(tài)窗口法的機(jī)器人避障研究[].儀表技術(shù)與傳感器，2023(4):102-106.Zhang Tao, Chen Zhang, Li Yumei, et al. Research onRobot ObstacleAvoidance Based on Improved A*Algorithm and Dynamic Window Method[J]. InstrumentTechnique and Sensor, 2023(4): 102-106.
[17]郭園園，袁杰，趙克剛.基于改進(jìn)A*算法和動(dòng)態(tài)窗口法的機(jī)器人路徑規(guī)劃[].計(jì)算機(jī)工程與科學(xué),2022,44(7):1273-1281.Guo Yuanyuan, Yuan Jie, Zhao Kegang. Robot PathPlanning Based on an Improved A Algorithm and anImproved DynamicWindow Method[J]ComputerEngineering & Science, 2022, 44(7): 1273-1281.
來(lái)源：系統(tǒng)仿真學(xué)報(bào) 第36卷 第8期
作者：賴榮，竇磊，巫志勇，孫帥 （廈門理工學(xué)院機(jī)械與汽車工程學(xué)院，福建廈門361024)
