基于改進(jìn)A*算法與動(dòng)態(tài)窗口法的移動(dòng)機(jī)器人能耗優(yōu)化路徑規(guī)劃

關(guān)鍵詞：A*算法；動(dòng)態(tài)窗口法；能耗模型

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2024）26-0028-03開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID） ：

0 引言

移動(dòng)機(jī)器人路徑規(guī)劃是機(jī)器人實(shí)現(xiàn)自主移動(dòng)的關(guān)鍵技術(shù)之一。通過(guò)合理的路徑規(guī)劃，機(jī)器人能夠找到從起點(diǎn)到終點(diǎn)的最優(yōu)或近似最優(yōu)路徑，從而減少移動(dòng)時(shí)間，提高整體工作效率。路徑規(guī)劃能夠幫助機(jī)器人避開障礙物和危險(xiǎn)區(qū)域，確保機(jī)器人在移動(dòng)過(guò)程中的安全性。然而，機(jī)器人需要在各種復(fù)雜環(huán)境中進(jìn)行移動(dòng)，包括動(dòng)態(tài)變化的環(huán)境、未知環(huán)境等，這對(duì)路徑規(guī)劃算法的實(shí)時(shí)性和魯棒性提出了很高的要求。針對(duì)上述問(wèn)題，本文提出一種基于改進(jìn)A*算法和動(dòng)態(tài)窗口法的能耗優(yōu)化路徑規(guī)劃方法，旨在降低機(jī)器人的能耗，提高運(yùn)動(dòng)效率。

1 能耗模型建立

移動(dòng)機(jī)器人的能耗受地面坡度、摩擦系數(shù)、電機(jī)效率等多種因素影響[1]。為了準(zhǔn)確描述機(jī)器人的能耗情況，本文建立了基于這些因素的能耗模型。該模型將機(jī)器人的運(yùn)動(dòng)軌跡劃分為多個(gè)局部目標(biāo)點(diǎn)，并計(jì)算從當(dāng)前軌跡運(yùn)動(dòng)到預(yù)定軌跡的能量消耗。能量消耗包括變狀態(tài)能耗和穩(wěn)定狀態(tài)能耗兩部分，分別用于描述機(jī)器人運(yùn)動(dòng)狀態(tài)的改變和克服地面摩擦力所需的能量[2]。

在考慮移動(dòng)機(jī)器人的運(yùn)動(dòng)模型時(shí)，基于其當(dāng)前的位置、航向角以及選定的速度和角速度來(lái)預(yù)測(cè)下一時(shí)刻的位置。給定機(jī)器人當(dāng)前的位置為（x，y），航向角為θ，以及選取的評(píng)分最高的速度v和角速度ω，利用這些參數(shù)和短采樣時(shí)間間隔Δt來(lái)建立機(jī)器人的運(yùn)動(dòng)模型。

由于采樣時(shí)間間隔Δt很短，可以合理地假設(shè)機(jī)器人在這個(gè)時(shí)間段內(nèi)做勻速直線運(yùn)動(dòng)（同時(shí)考慮其航向的變化，即旋轉(zhuǎn)）。這個(gè)假設(shè)允許使用簡(jiǎn)單的線性方程來(lái)近似機(jī)器人在Δt內(nèi)的運(yùn)動(dòng)。

2 融合改進(jìn) A* 算法與動(dòng)態(tài)窗口法的路徑規(guī)劃方法

2.1 A* 算法原理及分析

A*算法是一種經(jīng)典的啟發(fā)式圖搜索算法，用于尋找圖中起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑。它結(jié)合了Dijkstra算法的確保性（保證找到一條最短路徑）和貪心算法的高效性（快速找到目標(biāo)）。A算法通過(guò)評(píng)估函數(shù)f（n） = g（n） + h（n）來(lái)工作，其中f（n）為總代價(jià)，g（n）是從起始點(diǎn)到任何頂點(diǎn)n的實(shí)際成本，而h（n）是從頂點(diǎn)n 到目標(biāo)的估計(jì)最低成本[3]。

相較于其他搜索算法，A算法以其較快的搜索速度脫穎而出，這主要得益于其采用的啟發(fā)式函數(shù)。通過(guò)啟發(fā)式函數(shù)，A算法能夠智能地評(píng)估每個(gè)搜索節(jié)點(diǎn)的潛在價(jià)值，從而有效減少不必要的路徑搜索，極大地縮短了搜索路徑的數(shù)量。這一特性使得A*算法在處理大規(guī)模搜索問(wèn)題時(shí)展現(xiàn)出極高的效率，能夠迅速找到從起始點(diǎn)到目標(biāo)點(diǎn)的最短路徑[4]。

然而，值得注意的是，盡管A算法在求解最短路徑問(wèn)題上表現(xiàn)出色，但它也面臨著一定的局限性。具體而言，傳統(tǒng)的A算法主要聚焦于尋找最短路徑，而未能充分考慮到諸如能耗這樣的額外優(yōu)化目標(biāo)[5]。在實(shí)際應(yīng)用中，僅僅追求路徑最短可能并不足以滿足所有需求，特別是當(dāng)能耗成為重要考量因素時(shí)。因此，傳統(tǒng)A算法在能耗最優(yōu)規(guī)劃方面的表現(xiàn)就顯得力不從心了。為了克服這一局限，研究者們提出了多種改進(jìn)策略，旨在將能耗等額外優(yōu)化目標(biāo)融入A算法的搜索過(guò)程中，以實(shí)現(xiàn)更加全面和高效的路徑規(guī)劃[6]。

2.2 融合算法設(shè)計(jì)

2.2.1 融入機(jī)器人尺寸考量

在傳統(tǒng)的動(dòng)態(tài)窗口法（DWA） 中，路徑規(guī)劃往往忽視了移動(dòng)機(jī)器人的實(shí)際尺寸，僅依據(jù)軌跡與障礙物之間的最近距離作為避碰依據(jù)，這可能導(dǎo)致在實(shí)際行駛過(guò)程中機(jī)器人與障礙物發(fā)生碰撞。為克服這一缺陷，本文提出了一種優(yōu)化策略，即引入移動(dòng)機(jī)器人的尺寸信息。具體而言，根據(jù)機(jī)器人的幾何中心坐標(biāo)及其尺寸參數(shù)（如長(zhǎng)度、寬度），計(jì)算出機(jī)器人4個(gè)頂點(diǎn)的坐標(biāo)，進(jìn)而構(gòu)建出一個(gè)矩形輪廓。隨后，對(duì)該輪廓進(jìn)行離散化處理，生成一系列輪廓點(diǎn)集。在評(píng)估路徑時(shí)，計(jì)算這些點(diǎn)集內(nèi)各點(diǎn)與最近障礙物之間的距離D（v，ω），并將該距離進(jìn)行歸一化處理后，替換原有的距離度量d（v，ω）融入評(píng)價(jià)函數(shù)中。這樣，評(píng)價(jià)函數(shù)便能夠基于移動(dòng)機(jī)器人輪廓與障礙物之間的實(shí)際間隙來(lái)評(píng)估路徑的優(yōu)劣，有效避免了因忽略機(jī)器人尺寸而導(dǎo)致的碰撞風(fēng)險(xiǎn)。如圖1所示，當(dāng)機(jī)器人尺寸較小時(shí)，算法可能允許其通過(guò)狹窄通道；而當(dāng)機(jī)器人尺寸較大時(shí)，則會(huì)傾向于選擇繞行路徑，以確保安全通行。

2.2.2 轉(zhuǎn)彎半徑約束的加強(qiáng)

鑒于移動(dòng)機(jī)器人的機(jī)械結(jié)構(gòu)限制，其路徑規(guī)劃還需滿足特定的最小轉(zhuǎn)彎半徑要求。為此，在評(píng)價(jià)函數(shù)中加入了轉(zhuǎn)彎半徑作為新的約束條件。轉(zhuǎn)彎半徑r 可由速度v 與角速度ω 的比值計(jì)算得出（r=v/ω） 。通過(guò)將這一約束條件歸一化后并入評(píng)價(jià)函數(shù)，能夠在評(píng)估軌跡時(shí)充分考慮到機(jī)器人的轉(zhuǎn)彎能力，從而避免生成超出其物理限制的路徑。這一改進(jìn)不僅提升了路徑的可行性，還進(jìn)一步增強(qiáng)了評(píng)價(jià)函數(shù)的全面性和準(zhǔn)確性。

結(jié)合上述優(yōu)化策略，構(gòu)建了如下的優(yōu)化評(píng)價(jià)函數(shù)：

G（v，ω）=σ（α?h（v，ω）+β?D（v，ω）+γ?o（v，ω）+δ?r（v，ω））

其中，δ 為評(píng)價(jià)函數(shù)的系數(shù)。

為了同時(shí)獲得全局路徑的最優(yōu)性和局部避障的靈活性，本文將A算法與動(dòng)態(tài)窗口法進(jìn)行了有效融合。A算法負(fù)責(zé)在全局范圍內(nèi)搜索出從起點(diǎn)到終點(diǎn)的最優(yōu)路徑，而動(dòng)態(tài)窗口法則在此基礎(chǔ)上進(jìn)行局部調(diào)整，以應(yīng)對(duì)環(huán)境中的動(dòng)態(tài)變化和未知障礙。這種融合策略不僅保留了A*算法的全局規(guī)劃能力，還充分利用了DWA的實(shí)時(shí)避障優(yōu)勢(shì)，從而實(shí)現(xiàn)了更加高效、安全的路徑規(guī)劃。融合改進(jìn)后的路徑規(guī)劃算法流程如圖2所示。

3 仿真實(shí)驗(yàn)與結(jié)果分析

為驗(yàn)證本文改進(jìn)A*算法的可行性和有效性，在空曠和密集2種環(huán)境下分別用傳統(tǒng)A*算法、與本文改進(jìn)A*算法進(jìn)行對(duì)比仿真實(shí)驗(yàn)。其具體數(shù)據(jù)如表1～表2所示。

仿真實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)A*算法相比，本文所提出的融合路徑規(guī)劃方法可降低能耗43.88%，機(jī)器人在動(dòng)態(tài)環(huán)境中能夠有效避障，運(yùn)動(dòng)更加平順。這證明了本文所提出的能耗優(yōu)化路徑規(guī)劃方法的有效性。

分析圖3、表3及表4提供的數(shù)據(jù)，可以明確融合算法在開闊與密集環(huán)境條件下均展現(xiàn)出卓越的路徑規(guī)劃效能。該算法不僅有效克服了傳統(tǒng)A算法路徑不平滑的弊端，還確保了規(guī)劃任務(wù)的圓滿完成。盡管為提升路徑平滑度而稍作調(diào)整，導(dǎo)致能耗較改進(jìn)A算法分別增加了約2.60%和1.52%，但相較于未經(jīng)優(yōu)化的傳統(tǒng)路徑，其能耗節(jié)省效果依然顯著，分別達(dá)到了約43.88%和33.28%，這一成就極為可觀。

在圖4的展示中，（a）與（b）兩組圖像直觀反映了機(jī)器人在面對(duì)首個(gè)及第二個(gè)動(dòng)態(tài)障礙物時(shí)的實(shí)時(shí)情景及其抵達(dá)終點(diǎn)時(shí)的狀態(tài)。在這些挑戰(zhàn)場(chǎng)景下，動(dòng)態(tài)障礙物以不同的速度（0.80 m/s與0.50 m/s） 進(jìn)行往復(fù)移動(dòng)，要求機(jī)器人具備高度的靈活應(yīng)變能力。得益于算法中引入的基于機(jī)器人輪廓至障礙物距離的評(píng)估機(jī)制及轉(zhuǎn)彎半徑的嚴(yán)格約束，機(jī)器人在規(guī)避障礙時(shí)展現(xiàn)出了極高的敏捷度與精確性，路徑偏移得以有效控制且整體保持流暢。與傳統(tǒng)A*算法生成的路徑相比，本算法在空曠與密集環(huán)境中分別實(shí)現(xiàn)了能耗的顯著節(jié)省，具體數(shù)值為42.56%和32.39%。

4 結(jié)論

本文提出了一種能耗優(yōu)化的移動(dòng)機(jī)器人路徑規(guī)劃方法，通過(guò)融合改進(jìn)A*算法與改進(jìn)動(dòng)態(tài)窗口法，實(shí)現(xiàn)了在能量有限的情況下實(shí)現(xiàn)實(shí)時(shí)避障和全局最優(yōu)路徑規(guī)劃。仿真實(shí)驗(yàn)結(jié)果表明，該方法能夠顯著降低機(jī)器人的能耗，提高運(yùn)動(dòng)效率。未來(lái)，將進(jìn)一步研究如何將該方法應(yīng)用于實(shí)際場(chǎng)景中的移動(dòng)機(jī)器人，以推動(dòng)移動(dòng)機(jī)器人領(lǐng)域的發(fā)展。