A星算法在移動(dòng)機(jī)器人路徑規(guī)劃中的優(yōu)化策略

［摘 要］文章介紹了A 星算法的原理及傳統(tǒng)應(yīng)用，分析了路徑規(guī)劃中的挑戰(zhàn)，并提出針對(duì)性的優(yōu)化措施。試驗(yàn)結(jié)果表明，優(yōu)化后的A 星算法顯著提高了其在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用效果。

［關(guān)鍵詞］A 星算法；移動(dòng)機(jī)器人；路徑規(guī)劃；優(yōu)化策略

［中圖分類號(hào)］TP242 ［文獻(xiàn)標(biāo)志碼］A ［文章編號(hào)］2095–6487（2024）09–0012–03

在自動(dòng)化技術(shù)飛速進(jìn)步的今天，移動(dòng)機(jī)器人已經(jīng)被廣泛應(yīng)用于眾多行業(yè)與領(lǐng)域。其中，作為實(shí)現(xiàn)精確操作的關(guān)鍵技術(shù)，路徑規(guī)劃受到了極大關(guān)注，A 星算法作為路徑探尋領(lǐng)域里的經(jīng)典方法，憑借其高效性能和精確查找等優(yōu)勢(shì)，獲得了普遍的贊同與廣泛的應(yīng)用。但面對(duì)越來(lái)越復(fù)雜的場(chǎng)景和不斷變化的障礙，經(jīng)典A星算法逐漸顯示出了其不足。針對(duì)算法改進(jìn)方法進(jìn)行深入研究，使其在動(dòng)態(tài)應(yīng)用場(chǎng)景中提高效率，滿足現(xiàn)代自動(dòng)化行業(yè)對(duì)機(jī)器人移動(dòng)能力的苛刻要求，成為當(dāng)前迫切需要解決的問(wèn)題。

1 A星算法概述

1.1 算法原理

A 星算法的核心理念在于借助信息引導(dǎo)方法，對(duì)起點(diǎn)至終點(diǎn)的距離進(jìn)行準(zhǔn)確估算。在算法運(yùn)算過(guò)程中，計(jì)算每個(gè)計(jì)算單元的實(shí)際費(fèi)用（即起點(diǎn)至節(jié)點(diǎn)的代價(jià)，稱之為g），加上一個(gè)預(yù)估費(fèi)用（即節(jié)點(diǎn)至終點(diǎn)的預(yù)估代價(jià)，稱作h），即可得到總費(fèi)用。在A 星算法搜索過(guò)程中，需要維護(hù)待考察的節(jié)點(diǎn)“候選節(jié)點(diǎn)列表”及已考察的節(jié)點(diǎn)“歷史節(jié)點(diǎn)列表”。從起點(diǎn)出發(fā)，計(jì)算方法會(huì)不斷挑選出候選列表里評(píng)估值最低的單元進(jìn)行拓展，直到到達(dá)預(yù)設(shè)的目標(biāo)單元。

1.2 傳統(tǒng)應(yīng)用評(píng)析

在常規(guī)使用場(chǎng)景里，A 星算法因其高效率和精確性，被視為路徑規(guī)劃的首選技術(shù)，特別是在情況相對(duì)安定、障礙物確定的的情況下，其能快速確定高效路徑。在需求不斷上升的當(dāng)下，尤其是在千變?nèi)f化的場(chǎng)景中，算法成效通常受到限制諸多因素。身處于多變的城市環(huán)境，頻繁的障礙物變動(dòng)要求計(jì)算方法必須隨時(shí)刷新路徑信息，進(jìn)而使得整體運(yùn)算速度有所放緩。一般來(lái)說(shuō)，傳統(tǒng)的啟發(fā)式方法通常是針對(duì)某種特定地圖設(shè)計(jì)的，如歐氏距離或曼哈頓準(zhǔn)則，這樣的設(shè)計(jì)讓算法在應(yīng)對(duì)其他類型的環(huán)境時(shí)，普適性和適應(yīng)性就會(huì)受到影響。

2 路徑規(guī)劃中的挑戰(zhàn)

2.1 環(huán)境復(fù)雜性對(duì)算法的影響

在現(xiàn)實(shí)世界的使用場(chǎng)合里，環(huán)境經(jīng)常是復(fù)雜且不斷變化的，這對(duì)路徑規(guī)劃算法提出了考驗(yàn)。在城鎮(zhèn)的交通網(wǎng)絡(luò)、室內(nèi)空間或戶外自然景觀中，阻礙物分布和構(gòu)造參差不齊，復(fù)雜的地形與障礙物數(shù)量眾多，如高樓大廈、茂密林木、崎嶇山脈等，這種混亂局面使得傳統(tǒng)路徑規(guī)劃技術(shù)難以準(zhǔn)確預(yù)測(cè)與應(yīng)對(duì)，經(jīng)常造成局部最優(yōu)解或路徑受阻的困境。

在移動(dòng)機(jī)器人行業(yè)，應(yīng)對(duì)不斷變化的環(huán)境難題是關(guān)鍵，這包括行人往來(lái)、車輛行駛等活動(dòng)障礙，這類活動(dòng)的阻礙物要求導(dǎo)航系統(tǒng)必須及時(shí)更新行程路線信息，規(guī)避障礙或重新規(guī)劃路徑，否則可能會(huì)導(dǎo)致碰撞或交通堵塞。

此外，還有眾多環(huán)境因素，如天氣多變、道路封閉、人群擁擠等，這些都會(huì)對(duì)出行路線的準(zhǔn)確性和穩(wěn)定性造成沖擊，這要求計(jì)算方法必須具備良好的適應(yīng)性和穩(wěn)定的可靠性。

2.2 實(shí)時(shí)數(shù)據(jù)處理的需求

在即時(shí)路線設(shè)計(jì)的應(yīng)用場(chǎng)景里，算法效能關(guān)鍵在于數(shù)據(jù)處理速度和效率。

搭載了激光雷達(dá)、攝像頭等多樣感知設(shè)備的自動(dòng)化移動(dòng)裝置，能夠?qū)χ苓叚h(huán)境進(jìn)行即時(shí)監(jiān)控，這些設(shè)備不斷搜集周邊信息（如阻礙物位置、運(yùn)動(dòng)速度等），然后把所收集的數(shù)據(jù)傳送至路徑規(guī)劃的算法進(jìn)行處理。面對(duì)大量的數(shù)據(jù)處理工作，計(jì)算方法必須具備高效的數(shù)據(jù)處理能力，保證信息的實(shí)時(shí)更新和準(zhǔn)確性。

在不斷更新的環(huán)境里，障礙位置及狀態(tài)可能隨時(shí)改變，因此路徑規(guī)劃方法需要實(shí)時(shí)更新路徑數(shù)據(jù)，以適應(yīng)環(huán)境變動(dòng)的速度，要讓機(jī)器人靈活繞過(guò)阻礙，即時(shí)調(diào)整行進(jìn)軌跡，計(jì)算方法必須快速處理新信息，重新設(shè)計(jì)最優(yōu)路線。

3 優(yōu)化策略

3.1 啟發(fā)式函數(shù)的改進(jìn)

要想讓A 星算法在復(fù)雜環(huán)境下表現(xiàn)更佳，關(guān)鍵在于對(duì)啟發(fā)式函數(shù)進(jìn)行革新。在A 星算法中，用于衡量從起始點(diǎn)到目標(biāo)點(diǎn)的間距的簡(jiǎn)便算法，是影響此算法效能的重要因素，如曼哈頓算法和歐幾里得算法所使用的距離度量這類經(jīng)典啟發(fā)式算法，在開(kāi)放且障礙較少的場(chǎng)景下表現(xiàn)尚可，但在復(fù)雜多變或不可預(yù)測(cè)的場(chǎng)景中，未必能精確計(jì)算成本，這會(huì)對(duì)算法性能及尋路效率帶來(lái)負(fù)面影響。

在改進(jìn)啟發(fā)式算法時(shí)，應(yīng)將實(shí)時(shí)環(huán)境數(shù)據(jù)與全方位評(píng)估準(zhǔn)則相結(jié)合進(jìn)行衡量，納入時(shí)間精力及能源消耗因素，構(gòu)造出一個(gè)更精細(xì)的評(píng)價(jià)模型，其不僅測(cè)算兩點(diǎn)空間間隔，同時(shí)也將行進(jìn)時(shí)間和能源消耗計(jì)入衡量之內(nèi)。針對(duì)實(shí)際應(yīng)用中遇到的障礙物多變性，優(yōu)化后的智能算法應(yīng)具備即時(shí)調(diào)整環(huán)境變動(dòng)、動(dòng)態(tài)調(diào)整費(fèi)用預(yù)計(jì)的能力。

在實(shí)際操作中，可以借助機(jī)器學(xué)習(xí)技術(shù)模擬退火啟發(fā)式算法函數(shù)，通過(guò)對(duì)歷史數(shù)據(jù)的分析，預(yù)測(cè)在特定環(huán)境中，哪條路徑的損耗最小化。采用此法，啟發(fā)式算法不再僅是固定距離計(jì)算，而轉(zhuǎn)化為能夠?qū)W習(xí)并適應(yīng)環(huán)境變動(dòng)的動(dòng)態(tài)體系。

3.2 數(shù)據(jù)結(jié)構(gòu)的優(yōu)化

為了更好地優(yōu)化A 星算法在路線查找方面的表現(xiàn)，數(shù)據(jù)組織方式的恰當(dāng)使用成了另一個(gè)重要考量。

在A 星算法技術(shù)的常規(guī)實(shí)施過(guò)程中，常用到的數(shù)據(jù)處理工具（如優(yōu)先級(jí)隊(duì)列）雖然能夠很好地幫助管理節(jié)點(diǎn)按照費(fèi)用進(jìn)行排序，但在面對(duì)大數(shù)據(jù)處理或經(jīng)常性更新的情形時(shí)，其效能通常會(huì)受到限制，采用更為高效的數(shù)據(jù)組織方式，對(duì)于提高計(jì)算速度和提升數(shù)據(jù)處理的功能至關(guān)重要。

在具體操作時(shí)，可采納斐波那契堆或配對(duì)堆等高效率的數(shù)據(jù)結(jié)構(gòu)，以取代傳統(tǒng)二叉堆。采用斐波那契堆這種數(shù)據(jù)結(jié)構(gòu)，在進(jìn)行數(shù)據(jù)的插入和合并操作時(shí)，能以攤還常數(shù)時(shí)間完成，同時(shí)在執(zhí)行移除最小元素的操作時(shí)，其效率也相對(duì)較好。借助斐波那契數(shù)列堆這種數(shù)據(jù)組織形式，算法能夠高效地對(duì)動(dòng)態(tài)列表中的元素進(jìn)行插入和刪除操作，進(jìn)而快速地重新排序節(jié)點(diǎn)，當(dāng)面臨節(jié)點(diǎn)眾多或頻繁變更的情形時(shí)，這一優(yōu)勢(shì)尤為突出。

采用配對(duì)堆算法，不僅易于構(gòu)建，而且運(yùn)行高效，特別適用于頻繁調(diào)整關(guān)鍵字和刪除最小值元素的場(chǎng)景，在實(shí)際應(yīng)用中，配對(duì)堆的制作相較斐波那契數(shù)列堆簡(jiǎn)單易行，其在處理大量數(shù)據(jù)時(shí)，通常與斐波那契數(shù)列堆的表現(xiàn)相當(dāng)，在某些情況下甚至表現(xiàn)得更加優(yōu)秀。

在A 星算法中結(jié)合這些高效數(shù)據(jù)結(jié)構(gòu)，不僅有助于提升算法處理復(fù)雜路徑尋優(yōu)時(shí)的效率，而且能有效減少對(duì)計(jì)算資源的倚重。經(jīng)過(guò)優(yōu)化的數(shù)據(jù)結(jié)構(gòu)，讓計(jì)算方法能更快地適應(yīng)環(huán)境變化，迅速刷新行進(jìn)軌跡，從而高效支撐變化環(huán)境中的路徑規(guī)劃。

3.3 多目標(biāo)優(yōu)化

在路徑規(guī)劃難題上，只聚焦于一個(gè)目標(biāo)的優(yōu)化通常不足以應(yīng)對(duì)多變的應(yīng)用環(huán)境，尤其是在移動(dòng)式機(jī)器人等自動(dòng)化設(shè)備的應(yīng)用領(lǐng)域，統(tǒng)籌兼顧眾多性能參數(shù)顯得格外關(guān)鍵。因此，采取多元目標(biāo)優(yōu)化方法，是提升A 星算法運(yùn)用成效的關(guān)鍵手段之一，融合時(shí)間利用效率、節(jié)能減排、安全保障措施等多方面的評(píng)價(jià)準(zhǔn)則，能夠達(dá)到全面提升效果。

在物流與救援等行業(yè)，節(jié)約時(shí)間通常是關(guān)鍵考慮因素，這對(duì)路徑規(guī)劃極為重要，特別是在需要立即作出響應(yīng)的情境中，只圖最快抵達(dá)，很可能造成能源消耗增加或途中安全隱患增加。針對(duì)這一難題，可以通過(guò)采用改進(jìn)算法來(lái)改善，引入能量消耗模型，對(duì)各個(gè)選擇路徑進(jìn)行耗能計(jì)算，在諸多使用場(chǎng)景里，如電動(dòng)機(jī)械裝置，能源耗費(fèi)是影響工作時(shí)長(zhǎng)和減少能源費(fèi)用的重要條件。

對(duì)于路徑安全問(wèn)題，絕不能掉以輕心。在復(fù)雜多變的環(huán)境中，規(guī)避潛在風(fēng)險(xiǎn)區(qū)域和不穩(wěn)定地形，是保障機(jī)器人完好運(yùn)轉(zhuǎn)與任務(wù)完成的重要前提。在進(jìn)行多目標(biāo)優(yōu)化工作中，須兼顧路徑的安全評(píng)估，保障設(shè)計(jì)的路徑既高效快速又可靠安全。

在推進(jìn)多目標(biāo)優(yōu)化任務(wù)中，可以通過(guò)對(duì)不同目標(biāo)分配不同的重要性比重，來(lái)達(dá)成各目標(biāo)間的協(xié)調(diào)一致。依據(jù)任務(wù)緊急性與重要性層次，妥善安排時(shí)間、能源消耗與安全保障的優(yōu)先級(jí)，從而令算法按照不同應(yīng)用場(chǎng)景的具體需求進(jìn)行調(diào)整，靈活適配搜索策略。借助如遺傳算法和粒子群優(yōu)化算法等現(xiàn)代優(yōu)化技術(shù)來(lái)進(jìn)行復(fù)雜決策問(wèn)題，能夠在短時(shí)間內(nèi)尋找到一個(gè)滿足所有衡量因素的理想解決方案。

4 試驗(yàn)設(shè)計(jì)與評(píng)估

4.1 試驗(yàn)設(shè)置

針對(duì)優(yōu)化后的A 星算法，設(shè)置了各類實(shí)驗(yàn)環(huán)境，目的是模擬實(shí)際應(yīng)用情境，以此驗(yàn)證算法性能和適用性。實(shí)驗(yàn)環(huán)境包括3 種典型場(chǎng)景：城市開(kāi)闊區(qū)域、繁密路網(wǎng)及充滿難度的障礙條件，每一種場(chǎng)景設(shè)置都經(jīng)過(guò)細(xì)心打造，旨在重現(xiàn)現(xiàn)實(shí)環(huán)境中多種挑戰(zhàn)。

主要研究目標(biāo)是各種配置的自驅(qū)式移動(dòng)機(jī)器人，這些機(jī)器人配備了必需的導(dǎo)航和感知設(shè)備，能夠精確記錄行進(jìn)路徑數(shù)據(jù)，并遵循由A 星算法生成的行進(jìn)路線。為了使試驗(yàn)效果具備更廣泛的適用性，對(duì)各類機(jī)器人進(jìn)行了嚴(yán)格測(cè)試，包括滾輪型與步足型機(jī)器人，旨在包含更多樣化的移動(dòng)方法及更多元化的應(yīng)用環(huán)境。

試驗(yàn)步驟分為3 個(gè)階段：①環(huán)境設(shè)置和機(jī)器人布署。涵蓋各試驗(yàn)場(chǎng)地設(shè)置障礙物和導(dǎo)航標(biāo)志，同時(shí)激活智能機(jī)器人的操作系統(tǒng)設(shè)置；②路徑規(guī)劃執(zhí)行。機(jī)器人將遵循改進(jìn)后的A 星算法軌跡執(zhí)行行走任務(wù)，邊行動(dòng)邊收集行程時(shí)間、能源消耗及路徑精準(zhǔn)度等重要信息；③數(shù)據(jù)收集和初步分析。全面收集所有機(jī)器人執(zhí)行任務(wù)的數(shù)據(jù)，并比較分析其在不同環(huán)境和不同類型中的表現(xiàn)差異。

4.2 結(jié)果分析

在對(duì)改進(jìn)后的A 星算法與傳統(tǒng)算法比照測(cè)試的過(guò)程中，數(shù)據(jù)解析環(huán)節(jié)關(guān)注兩者在多種樣本情境中的效能高低。借助收集到的數(shù)據(jù)，得以深入評(píng)估兩種路線規(guī)劃算法在效能、成本效益、節(jié)省能源及適應(yīng)性等方面的差異性。具體見(jiàn)表1。

數(shù)據(jù)表明，在自由空間環(huán)境里，改良后的計(jì)算方式相較于傳統(tǒng)算法，在路徑長(zhǎng)度和任務(wù)完成時(shí)長(zhǎng)上都表現(xiàn)出顯著改善，能源消耗也有所減少。該研究指出，在相對(duì)無(wú)阻的環(huán)境里，優(yōu)化后的智能搜索策略配合先進(jìn)的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)，顯著增強(qiáng)了程序的執(zhí)行效率。

在城市交通境中，由于路徑選擇的復(fù)雜性增加，兩種算法的效能高下比較更加突出，在尋求最短路徑的同時(shí)，改進(jìn)算法能巧妙應(yīng)對(duì)途中的各種意外狀況，如突如其來(lái)的障礙物或高峰期的車輛增多。

在復(fù)雜障礙區(qū)環(huán)境中，優(yōu)化算法展現(xiàn)出更強(qiáng)的適應(yīng)性和準(zhǔn)確度，面對(duì)多重障礙，計(jì)算軟件需持續(xù)優(yōu)化路徑，保證穩(wěn)妥避開(kāi)這些障礙。在這方面，經(jīng)過(guò)優(yōu)化的數(shù)據(jù)結(jié)構(gòu)讓計(jì)算方法能夠快速調(diào)整路線。

這些數(shù)據(jù)明確地揭示了優(yōu)化后的A 星算法在各種環(huán)境中相對(duì)于原有算法的優(yōu)異表現(xiàn)，特別是在應(yīng)對(duì)復(fù)雜或不可預(yù)測(cè)的環(huán)境時(shí)，其改善效果特別明顯。

5 結(jié)束語(yǔ)

本研究對(duì)A 星算法進(jìn)行了深度革新與全方位的精細(xì)化處理，有效提高了自動(dòng)化移動(dòng)機(jī)器人在復(fù)雜場(chǎng)景中進(jìn)行路徑搜索過(guò)程的速度與精準(zhǔn)度。策略改進(jìn)不僅聚焦于算法本身，更融合了對(duì)實(shí)際應(yīng)用需要的深入洞察，如采用多目標(biāo)優(yōu)化策略，綜合考慮了時(shí)間效益、能源耗費(fèi)與確保安全。實(shí)際測(cè)試數(shù)據(jù)證實(shí)，這些新提出的方案在各種不同環(huán)境中的成效較佳，特別是在變化無(wú)常和復(fù)雜多變的使用場(chǎng)景中，其表現(xiàn)格外出色，這些成就不僅促進(jìn)了路徑規(guī)劃技術(shù)的進(jìn)步，還為移動(dòng)機(jī)器人的廣泛應(yīng)用提供了有力支撐，展示了現(xiàn)代算法在處理實(shí)際問(wèn)題方面的優(yōu)秀能力。

參考文獻(xiàn)

[1] 李春軒. 移動(dòng)機(jī)器人路徑規(guī)劃及避障方法研究[D]. 西安：西安建筑科技大學(xué)，2023.

[2] 周成瑞，楊玲玲. 基于A 星算法的全向移動(dòng)機(jī)器人仿真研究[J]. 電腦與信息技術(shù)，2023，31（3）：29-31.

[3] 馬鵬程. 移動(dòng)機(jī)器人路徑規(guī)劃智能算法研究[D]. 長(zhǎng)春：長(zhǎng)春工業(yè)大學(xué)，2023.

[4] 楊帆. 基于ROS 的室內(nèi)移動(dòng)機(jī)器人路徑規(guī)劃研究[D]. 西安：西安工業(yè)大學(xué)，2023.

[5] 王永成，楊明漾，張國(guó)輝. 基于改進(jìn)A 星算法對(duì)自動(dòng)導(dǎo)引小車路徑規(guī)劃研究[J]. 火力與指揮控制，2021，46（8）：130-138，144.

基金項(xiàng)目： 宿遷市指導(dǎo)性科技計(jì)劃（Z2022102） ；宿遷學(xué)院人才引進(jìn)科研啟動(dòng)基金（2023XRC004） ；宿遷市科技計(jì)劃（K202348）