一種基于地圖預處理識別凹點優化路徑規劃效率的方法

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

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

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

0" 引" 言

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

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

1" 對地圖數據進行預處理

1.1" 障礙物權重表

室內導航網絡的構建工作不需要對地圖數據中的節點進行復雜的優先級排序或者權重計算，它主要通過識別并解析不同特殊節點之間的拓撲關系以及其他相關聯的空間特性來進行構建。

在導航路徑規劃算法的實際執行過程中，針對每一個參與路徑規劃的節點，系統會根據其所處工作環境的具體特性和任務要求，分配不同的權重參數。

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

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

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

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

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

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

1.3" 凹點判斷值表預處理

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

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

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

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

圖6 凹點轉折點識別圖

2" 改進路徑規劃算法

2.1" 傳統A*算法

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

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

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

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

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

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

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

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

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

2.3" 利用凹點判斷值表對A*算法優化

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

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

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

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

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

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

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

3" 算法測試

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

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

4" 結" 語

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

參考文獻

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

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

[3] 田茹，曹茂永，馬鳳英，等.基于改進A*算法的農用無人機路徑規劃[J].現代電子技術，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] 胡志忠，沈春林.基于數字地圖預處理的實時航跡規劃[J].南京航空航天大學學報，2002，34（4）：382?385.

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

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

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

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

[10] 余文凱，章政，付雪畫，等.基于地圖預處理及改進A*算法的路徑規劃[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*算法的室內機器人路徑規劃[J].現代電子技術，2022，45（8）：181?186.

[13] 楊光永，戈一航，晏婷，等.基于調和A*算法在移動機器人中的研究[J].現代電子技術，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

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

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

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

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

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

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

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