摘" 要： 為了減少存在多個無法通行或無法到達終點的路徑段情況下移動機器人路徑的計算節(jié)點數(shù)量，提高算法的搜索效率，文中提出一種地圖數(shù)據(jù)預處理功能，對路徑規(guī)劃算法中的預估計算法進行輔助，通過障礙物權重計算需要地圖中存在的凹點地形，在執(zhí)行路徑算法過程中，通過記錄的凹點約束搜索方向提高搜索效率，同時對路徑規(guī)劃算法的安全問題進行改進。實驗結果表明，改進后的路徑規(guī)劃算法具有較好的路徑規(guī)劃能力來應對多個無法通行或無法到達終點的路徑段，更加符合實際的應用場景。

關鍵詞： 路徑段； 搜索效率； 地圖預處理； 凹點； 搜索方向； 安全問題

中圖分類號： TN911.73?34； TP242"""""""""""""""" 文獻標識碼： A""""""""""""""""""" 文章編號： 1004?373X（2024）09?0182?05

0" 引" 言

路徑規(guī)劃算法是移動機器人確保其在與環(huán)境互動時不發(fā)生碰撞的關鍵技術之一[1]。機器人根據(jù)其工作環(huán)境的需求[2]，通過不同的優(yōu)化指標找到一條從起始節(jié)點到目標節(jié)點的最佳路徑，如路徑長度最短、能量消耗最小或路徑計算時間最短等[3]，但大部分都依賴于針對特殊環(huán)境設定特定的參數(shù)[4]。為了提高路徑規(guī)劃算法的效率，地圖預處理技術能夠識別地圖數(shù)據(jù)中的連通關系，為路徑規(guī)劃算法提供數(shù)據(jù)支持，優(yōu)化規(guī)劃的速度[5]，改善算法的性能。本文通過在路徑規(guī)劃前對地圖數(shù)據(jù)進行處理，利用輔助值表引導算法的搜索方向選擇，從而在實際應用中更加高效地規(guī)劃路徑，確保移動機器人能夠高效的在復雜環(huán)境中導航。

在路徑規(guī)劃的過程中，地圖數(shù)據(jù)中的障礙物節(jié)點可能形成多段無法通行的區(qū)域，這些區(qū)域可能形成復雜的迷宮、障礙物密集區(qū)域或復雜的地形[6]，導致增加了地圖的復雜性和路徑規(guī)劃的難度，當路徑規(guī)劃算法計算到無法通行的區(qū)域時，仍會繼續(xù)進行最近節(jié)點的計算，無法進行有針對性的路徑篩選，如果將這些場景進行實時數(shù)據(jù)分析，將會大大影響路徑規(guī)劃的實時性和效率。因此，本文通過對室內(nèi)導航網(wǎng)絡[7]中的凹點地形、地圖的拓撲結構[8]、障礙物權重計算[9]、時間成本等因素綜合分析，提出了地圖數(shù)據(jù)預處理功能[10]，對復雜地形區(qū)域場景下的凹點進行識別，通過凹點信息對路徑規(guī)劃算法進行優(yōu)化。本文的算法分為預處理階段和路徑規(guī)劃階段[11]，避免了運行路徑規(guī)劃算法的過程中增加計算量，通過對原始地圖數(shù)據(jù)進行凹點的篩選處理，提煉出地圖數(shù)據(jù)中的連通關系和利于到達目標節(jié)點的凹點信息，進而將其整合到路徑規(guī)劃算法的計算過程中，讓算法的搜索更加靈活，并剔除冗余計算[12]。通過改進路徑規(guī)劃算法的安全性問題[13]，保證在斜線移動的過程中不會和障礙物產(chǎn)生碰撞。

1" 對地圖數(shù)據(jù)進行預處理

1.1" 障礙物權重表

室內(nèi)導航網(wǎng)絡的構建工作不需要對地圖數(shù)據(jù)中的節(jié)點進行復雜的優(yōu)先級排序或者權重計算，它主要通過識別并解析不同特殊節(jié)點之間的拓撲關系以及其他相關聯(lián)的空間特性來進行構建。

在導航路徑規(guī)劃算法的實際執(zhí)行過程中，針對每一個參與路徑規(guī)劃的節(jié)點，系統(tǒng)會根據(jù)其所處工作環(huán)境的具體特性和任務要求，分配不同的權重參數(shù)。

本研究在對障礙物權重值表構建的過程中，不會對不同類型的障礙物進行特殊賦值，而是根據(jù)每個障礙物與目標節(jié)點之間的距離進行賦值。首先對地圖數(shù)據(jù)中每個獨立的障礙物節(jié)點相對于目標節(jié)點進行定量的相對權重分析。根據(jù)障礙物與目標節(jié)點之間的相對位置關系，量化其對規(guī)劃路徑的影響程度。本文采用歐氏距離計算公式來衡量障礙物節(jié)點與目標節(jié)點之間的空間距離，確保了計算結果具有一定的普適性。所有的距離計算結果均精確到小數(shù)點后一位，這種計算方法可以將細微的空間差異轉(zhuǎn)化為權重指標，如圖1所示。

通過計算得到的權重值讓障礙物的權重值呈現(xiàn)出一種擴散式的權重增長模式，即隨著障礙物節(jié)點與目標節(jié)點之間距離的增加，其對應的權重值也會逐漸增大，并且因為結果保留小數(shù)點后一位，讓障礙物節(jié)點的權重差異清晰的展示出來，以便在路徑規(guī)劃過程中實現(xiàn)對障礙物優(yōu)先級的有效區(qū)分。

1.2" 凹點識別判斷值表預處理

通過實驗和數(shù)據(jù)分析，本文發(fā)現(xiàn)利用地圖中的凹點信息作為關鍵參考依據(jù)，有助于在復雜環(huán)境中引導路徑規(guī)劃算法選擇搜索方向。由于單純依賴障礙物權重不足以全面識別通向目標節(jié)點的所有凹點地形，尤其是遠距離情況，這可能導致大量計算資源消耗和重復計算。為此，本文將障礙物權重值表轉(zhuǎn)換為凹點識別判斷值表，以減少凹點識別所需的計算量，并確保輔助值的計算和路徑規(guī)劃的搜索方向始終偏向于目標節(jié)點的方向。

在地圖數(shù)據(jù)預處理階段，理論上每一個可通行節(jié)點均可從4個基本方向探尋至目標節(jié)點的潛在凹點路徑。由于對所有方向進行輔助值計算將顯著增加存儲需求及計算成本，并且遠離目標節(jié)點方向的凹點的實際價值相對較低。因此，本研究僅針對明顯偏向于目標節(jié)點的兩個方向進行凹點輔助值計算，而暫時忽略其他方向，從而實現(xiàn)算法整體性能的優(yōu)化提升，如圖2所示。

圖2中目標節(jié)點在計算節(jié)點的東北方向，算法會認為沿著這一方向或者與其相近的方向推進搜索，更有可能快速接近并最終到達目標節(jié)點。因此，算法只關注計算節(jié)點東和北方向的障礙物節(jié)點，在保證搜索效率的同時，能夠充分調(diào)動計算資源，精準識別可以構建凹點的障礙物節(jié)點權重信息。障礙物權重值表的構建與計算方式在此發(fā)揮了重要作用，它量化每一個障礙物節(jié)點對路徑規(guī)劃的影響程度，使得算法能夠準確識別有助于到達目標的凹點地形。

1.3" 凹點判斷值表預處理

由障礙物權重值表得到凹點識別判斷值表之后，根據(jù)凹點識別判斷值表和障礙物權重值表對凹點的地形特征進行識別如圖3所示。因為需要在全圖范圍內(nèi)判斷凹點地形的位置，凹點識別判斷值表可以賦予障礙物節(jié)點之外的可通行節(jié)點權重值，通過凹點識別判斷值表能夠解決凹點識別范圍的問題。

當計算節(jié)點附近可通行節(jié)點中存在判斷值表的輔助值或障礙物值，可以作為在計算節(jié)點偏向于目標節(jié)點的方向中是否存在一個能夠靠近目標節(jié)點的凹點判斷依據(jù)。因此，凹點識別判斷值表能夠讓凹點識別更加簡易，只需要判斷計算節(jié)點附近的節(jié)點中是否存在凹點識別判斷值表中的輔助值或者障礙物節(jié)點，就能判斷這個可通行節(jié)點偏向目標節(jié)點的方向是否存在一個凹點，如圖4所示。

在確認凹點判斷方法后，接下來需要確定凹點值的計算標準。凹點識別過程中要保證能識別出所有類型的凹點。在地圖中如果只通過計算節(jié)點[x]軸或者[y]軸方向上鄰近的兩個節(jié)點進行凹點的判斷，就會導致在某些情況下無法選擇只有單邊存在障礙物節(jié)點或者凹點識別判斷值表中的值的路徑，效率降低到和普通路徑規(guī)劃算法的效率一樣。因此，不能僅僅根據(jù)計算節(jié)點[x]軸或者[y]軸方向上鄰近的兩格判斷中間的可通行節(jié)點是否是凹點，如果一邊是障礙物節(jié)點或者是凹點識別判斷值表中的值且相對于計算節(jié)點更靠近目標節(jié)點，這種類型的地形數(shù)據(jù)也要被識別為凹點地形信息，如圖5所示。

凹點標準判斷條件還要求在凹點方向中存在凹點轉(zhuǎn)折點。凹點轉(zhuǎn)折點表示在凹點方向且不超過目標節(jié)點坐標的情況下存在向目標節(jié)點進一步計算的可通行節(jié)點。凹點轉(zhuǎn)折點的具體計算方法是由凹點識別位置來對目標節(jié)點方向的路徑進行計算，通過對當前凹點的前進方向中的節(jié)點進行計算分析，判斷在偏向于目標節(jié)點的一側是否存在可通行節(jié)點，或者在偏向于目標節(jié)點的一側的節(jié)點是否存在凹點識別判斷值表中的值，且與當前計算節(jié)點偏向目標節(jié)點一側的的節(jié)點權重值不同的可通行節(jié)點。例如，當前凹點方向為橫向時，需要檢測在凹點方向偏向于目標節(jié)點的一側是否存在一個可通行節(jié)點，當計算到下一個節(jié)點為障礙物節(jié)點，并在此計算過程中不存在凹點轉(zhuǎn)折點的情況，那么這個凹點會被認為不符合要求，將這個凹點進行刪除。在識別凹點轉(zhuǎn)折點的過程中只會記錄凹點方向第一個能夠向目標節(jié)點進一步計算的節(jié)點，將這個節(jié)點設置為凹點轉(zhuǎn)折點，并記錄轉(zhuǎn)折點的坐標到對應的凹點判斷值表中，如圖6所示。

圖6 凹點轉(zhuǎn)折點識別圖

2" 改進路徑規(guī)劃算法

2.1" 傳統(tǒng)A*算法

傳統(tǒng)A*路徑規(guī)劃算法是結合dijkstra算法以及貪婪算法而產(chǎn)生的一種導航算法[11]，它通過評估每個節(jié)點到目標節(jié)點的估計距離和實際距離來確定下一個要訪問的節(jié)點。它的核心思想是在每次選擇下一個節(jié)點時，都考慮到當前節(jié)點到目標節(jié)點的最短路徑，以及當前節(jié)點到其他節(jié)點的最短路徑。在初始化階段，需要設置一個優(yōu)先隊列，用于存儲當前節(jié)點和下一個節(jié)點，保證每次取出來的節(jié)點都是最短路徑。在這個隊列中，每個節(jié)點都需要有一個評估值，該評估值表示當前節(jié)點到目標節(jié)點的最短路徑長度。在初始化階段，還需要設置一個棧，用于存儲已經(jīng)訪問過的節(jié)點。

在評估階段通過如下公式計算每個節(jié)點到目標節(jié)點的估計距離和實際距離，并進行比較。

[f（x）=g（x）+h（x）]

式中：[h（x）]是啟發(fā)式函數(shù)，通過當前節(jié)點對終點距離進行預估計；[g（x）]是從起始節(jié)點到目前節(jié)點的實際距離；[f（x）]是起始節(jié)點到目標節(jié)點的預計消耗。

啟發(fā)式函數(shù)是一種估計算法，它通過估算當前節(jié)點到目標節(jié)點的最短估算距離來幫助算法快速找到最短路徑，可以根據(jù)環(huán)境條件因素對函數(shù)的參數(shù)進行調(diào)節(jié)來計算每個節(jié)點到目標節(jié)點的估計距離。啟發(fā)式函數(shù)通常基于節(jié)點的屬性，例如節(jié)點到終點的距離、當前機器人移動速度等，需要使用A*算法來評估每個節(jié)點的評估值，A*算法會根據(jù)節(jié)點的評估值來選擇下一個要訪問的節(jié)點。在評估階段，還需要將每個節(jié)點和它的評估值加入到優(yōu)先隊列中。

A*算法最主要的部分是擴展階段，需要選擇下一個最優(yōu)節(jié)點，并將其加入到路徑中。在這個階段，需要從優(yōu)先隊列中取出最優(yōu)節(jié)點，并將其加入到棧中，將該節(jié)點周圍未訪問過的相鄰節(jié)點加入到優(yōu)先隊列中，并計算它們的評估值。在這個過程中，如果發(fā)現(xiàn)有比當前節(jié)點更短的路徑，就需要更新當前節(jié)點的路徑。在擴展階段，還需要檢查是否已經(jīng)計算到了目標節(jié)點，如果計算到了目標節(jié)點，就需要停止算法，并從閉合隊列中目標節(jié)點的父節(jié)點開始記錄，直到記錄到初始節(jié)點，將中間記錄的節(jié)點返回給用戶。

2.2" 對A*算法進行安全性改進

通常A*算法用來尋找從一個起點到一個目標節(jié)點的最短路徑。在實際應用中，當從當前節(jié)點到周圍的相鄰節(jié)點需要進行斜對角移動時，必須考慮是否存在障礙物節(jié)點。如果允許斜對角移動并且當前節(jié)點周圍的4個相鄰節(jié)點中至少有1個是障礙物節(jié)點，那么斜對角移動可能導致路徑與障礙物碰撞，這在路徑規(guī)劃算法的實際應用中是不被允許的。因此，為了避免碰撞，在這種情況下應該選擇只能進行水平或垂直移動的路徑，從而保證路徑規(guī)劃的正確性和可行性。通過遵循這一原則，能夠更好地處理路徑規(guī)劃問題，特別是在復雜環(huán)境中，確保生成的路徑是可行的和安全的，轉(zhuǎn)變示范如圖7所示。

其中，圖7a）為錯誤的計算方式，圖7b）為經(jīng)過改進后的計算方式，通過此方法可以避免在轉(zhuǎn)彎的過程中與障礙物產(chǎn)生碰撞的問題。

2.3" 利用凹點判斷值表對A*算法優(yōu)化

根據(jù)地圖預處理產(chǎn)生的凹點判斷值表輔助A*算法進行路徑規(guī)劃。在A*算法執(zhí)行路徑規(guī)劃的過程中，每當算法從開放列表中依據(jù)啟發(fā)式函數(shù)選取并移除具有最小代價值函數(shù)值的節(jié)點時，系統(tǒng)將立即執(zhí)行凹點判斷值表檢查工作。這項檢查主要是為了確定當前被提取節(jié)點在預先構建的凹點判斷值表中所對應的坐標輔助值是否存在非0情況。

如果發(fā)現(xiàn)這個輔助值不等于0，那么表明當前節(jié)點所在位置存在著一個可能影響搜索路徑?jīng)Q策的凹點特征。此時，系統(tǒng)會立即將該節(jié)點的相關信息插入到凹點記錄隊列之中，其中包括將當前節(jié)點的具體坐標值作為凹點記錄點的坐標信息予以記錄，并同時保存經(jīng)過計算得出的[g]值。

當算法對當前處理節(jié)點完成一系列分析后，如果確認該節(jié)點在凹點判斷值表中對應位置存在輔助值，并且通過對比發(fā)現(xiàn)其與目前儲存在凹點記錄隊列末端元素所標識的凹點轉(zhuǎn)折點坐標相同，那么算法將僅針對性地更新凹點記錄隊列中最后一條記錄的坐標值，將其替換為當前正在處理的節(jié)點坐標值。

在路徑規(guī)劃算法的實際應用中，遇到頻繁切換目標節(jié)點的情況時，維持搜索過程的連貫性和有效性至關重要。當算法從目標節(jié)點切換至另一個臨時目標節(jié)點時，必須確保到達臨時目標節(jié)點之后的搜索策略不會對路徑規(guī)劃算法的計算過程產(chǎn)生負面影響。這是因為凹點轉(zhuǎn)折點在路徑規(guī)劃中代表了潛在的路徑選項，不能保證它是唯一或最優(yōu)的通向目標節(jié)點的路徑組成部分。

因此在對臨時目標節(jié)點的計算過程中，不能隨意從開放列表中去除任何節(jié)點信息。開放列表作為一個存儲有待進一步檢查節(jié)點的結構，它的完整性直接影響到算法能否全面有效地探尋到可能的最佳路徑。如果將凹點轉(zhuǎn)折點作為臨時目標節(jié)點進行計算，就對開放列表中的值進行消除，那么當凹點記錄隊列中的凹點記錄信息為空之后，算法可能會陷入一種循環(huán)探查已知區(qū)域的狀態(tài)。在這種情況下，由于先前可能通往最終目標節(jié)點的關鍵節(jié)點被提前剔除，算法不得不重新計算這些已被訪問過的節(jié)點，這不僅會引發(fā)大量不必要的重復計算，還會增加不必要的路徑回溯，進而極大地降低了整個路徑規(guī)劃算法的執(zhí)行效率和精度。

當算法在向臨時目標節(jié)點計算時，本算法不同于傳統(tǒng)A*算法的規(guī)則，即在還未計算至臨時目標節(jié)點前，不會對其周圍所有8個相鄰節(jié)點按原算法進行代價值計算。因為在對臨時目標節(jié)點的計算過程中，以臨時目標節(jié)點為導向的節(jié)點代價值明顯低于以原目標節(jié)點為方向的代價值，這意味著當?shù)竭_臨時目標節(jié)點之前，算法會先專注于中間節(jié)點的計算，然后再延伸至臨時目標節(jié)點周圍的節(jié)點。

實驗中采取的計算方法是基于臨時目標節(jié)點與當前計算節(jié)點之間的相對方位關系，針對性地推導出下一個待計算節(jié)點的坐標值，并將當前計算節(jié)點移入閉合隊列中，同時將新節(jié)點添加至開放列表，進行下一輪循環(huán)計算，如圖8所示。

3" 算法測試

仿真實驗基于Core i5 1035G1處理器，內(nèi)存為8 GB。在OpenCV環(huán)境下，利用設計的算法對移動機器人路徑規(guī)劃在19×28的環(huán)境下進行仿真，圖9為仿真對比圖。

其中，圖9a）為傳統(tǒng) A*算法，圖9b）為引入地圖預處理算法后的A*算法。通過對算法的測試，在處理同一幅地圖數(shù)據(jù)時，改進后的A*算法相比于傳統(tǒng)的A*算法，在計算節(jié)點的數(shù)量上有了明顯的下降。傳統(tǒng)A*算法在該地圖環(huán)境下需計算的節(jié)點總數(shù)達到了326個，改進后的A*算法減少了50個計算節(jié)點，計算節(jié)點數(shù)量減少了約15.34%。

4" 結" 語

針對移動機器人路徑規(guī)劃問題，傳統(tǒng)算法搜索效率低，無法針對性地選擇計算方向，在遇到多段無法通行或無法到達終點的路徑段的情況下會導致冗余的計算。本文根據(jù)地圖預處理算法改進A*算法啟發(fā)式函數(shù)進行路徑規(guī)劃，提出了優(yōu)化計算節(jié)點數(shù)量并針對性地選擇搜索方向，提高了算法的搜索效率，通過仿真實驗可知，改進后的A*算法在搜索效率上比傳統(tǒng)A*算法高，并且計算更加安全。因此，采用根據(jù)地圖預處理算法改進A*算法啟發(fā)式函數(shù)能有效地提高路徑規(guī)劃算法的性能，具有良好的應用前景。

參考文獻

[1] 崔煒，朱發(fā)證.機器人導航的路徑規(guī)劃算法研究綜述[J].計算機工程與應用，2023，59（19）：10?20.

[2] 王迪，黎冠，李志偉，等.基于改進A*算法的消防機器人路徑規(guī)劃算法研究[J].華北科技學院學報，2022，19（1）：72?79.

[3] 田茹，曹茂永，馬鳳英，等.基于改進A*算法的農(nóng)用無人機路徑規(guī)劃[J].現(xiàn)代電子技術，2022，45（4）：182?186.

[4] LE A V， NHAN N H K， MOHAN R E， et al. Evolutionary algorithm?based complete coverage path planning for tetriamond tiling robots [J]. Sensors， 2020， 20（2）： 445.

[5] 胡志忠，沈春林.基于數(shù)字地圖預處理的實時航跡規(guī)劃[J].南京航空航天大學學報，2002，34（4）：382?385.

[6] 張明路，沈祺宗，高春艷，等.針對多障礙陸戰(zhàn)場路徑規(guī)劃的改進A*算法研究[J].機械設計與制造，2023（1）：264?267.

[7] 傅夢穎，王培曉，張恒才，等.一種室內(nèi)導航網(wǎng)絡眾包構建方法[J].測繪科學技術學報，2019，36（1）：100?104.

[8] 武星，楊俊杰，湯凱，等.面向復合地圖的移動機器人分層路徑規(guī)劃[J].中國機械工程，2023，34（5）：563?575.

[9] 魯毅，高永平，龍江騰.A*算法在移動機器人路徑規(guī)劃中的研究[J].湖北師范大學學報（自然科學版），2022，42（2）：59?65.

[10] 余文凱，章政，付雪畫，等.基于地圖預處理及改進A*算法的路徑規(guī)劃[J].高技術通訊，2020，30（4）：383?390.

[11] LI C Y， LIU Q J， SONG S， et al. Path planning for mobile robots based on an improved ant colony algorithm with Gaussian distribution [J]. Journal of physics： Conference series， 2022， 2188（1）： 012005.

[12] 周敬東，楊磊，張超.改進A*算法的室內(nèi)機器人路徑規(guī)劃[J].現(xiàn)代電子技術，2022，45（8）：181?186.

[13] 楊光永，戈一航，晏婷，等.基于調(diào)和A*算法在移動機器人中的研究[J].現(xiàn)代電子技術，2022，45（4）：171?176.

A method of concave point identification based on map preprocessing

for optimizing path planning efficiency

CHEN Wenbo， ZHAO Yunfeng， ZHAO Shipeng

（North China Institute of Aerospace Engineering， Langfang 065000， China）

Abstract： To reduce the number of computational nodes in mobile robot path planning when there are multiple unpassable or unreachable segments， and to improve search efficiency， an auxiliary function for the estimated calculation method in the map data preprocessing stage of the path planning algorithm is proposed. The concave terrain that needs to be searched in the map is calculated by the weight of obstacles， and the search direction is constrained by the recorded concave points in the process of executing the path algorithm， so as to improve the search efficiency and enhance the safety of the path planning algorithm. The experimental results show that the improved path planning algorithm has better path planning capability to deal with multiple unpassable or unreachable segments and is more suitable for practical application scenarios.

Keywords： path segment; search efficiency; map preprocessing; concave point; search direction; safety issue

DOI：10.16652/j.issn.1004?373x.2024.09.033

引用格式：陳文博，趙云峰，趙世鵬.一種基于地圖預處理識別凹點優(yōu)化路徑規(guī)劃效率的方法[J].現(xiàn)代電子技術，2024，47（9）：182?186.

收稿日期：2023?12?08"""""""""" 修回日期：2024?01?05

陳文博，等：一種基于地圖預處理識別凹點優(yōu)化路徑規(guī)劃效率的方法

陳文博，等：一種基于地圖預處理識別凹點優(yōu)化路徑規(guī)劃效率的方法

作者簡介：陳文博（1998—），男，蒙古族，內(nèi)蒙古錫林浩特蘇尼特右旗人，碩士，研究方向為導航定位技術。

趙云峰（1978—），男，河南開封人，碩士，副教授，研究方向為導航定位技術。

趙世鵬（2000—），男，河北承德人，碩士，研究方向為導航定位技術。