一種基于地圖預(yù)處理識(shí)別凹點(diǎn)優(yōu)化路徑規(guī)劃效率的方法

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

關(guān)鍵詞： 路徑段； 搜索效率； 地圖預(yù)處理； 凹點(diǎn)； 搜索方向； 安全問(wèn)題

中圖分類號(hào)： TN911.73?34； TP242"""""""""""""""" 文獻(xiàn)標(biāo)識(shí)碼： A""""""""""""""""""" 文章編號(hào)： 1004?373X（2024）09?0182?05

0" 引" 言

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

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

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

1.1" 障礙物權(quán)重表

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

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

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

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

1.2" 凹點(diǎn)識(shí)別判斷值表預(yù)處理

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

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

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

1.3" 凹點(diǎn)判斷值表預(yù)處理

由障礙物權(quán)重值表得到凹點(diǎn)識(shí)別判斷值表之后，根據(jù)凹點(diǎn)識(shí)別判斷值表和障礙物權(quán)重值表對(duì)凹點(diǎn)的地形特征進(jìn)行識(shí)別如圖3所示。因?yàn)樾枰谌珗D范圍內(nèi)判斷凹點(diǎn)地形的位置，凹點(diǎn)識(shí)別判斷值表可以賦予障礙物節(jié)點(diǎn)之外的可通行節(jié)點(diǎn)權(quán)重值，通過(guò)凹點(diǎn)識(shí)別判斷值表能夠解決凹點(diǎn)識(shí)別范圍的問(wèn)題。

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

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

凹點(diǎn)標(biāo)準(zhǔn)判斷條件還要求在凹點(diǎn)方向中存在凹點(diǎn)轉(zhuǎn)折點(diǎn)。凹點(diǎn)轉(zhuǎn)折點(diǎn)表示在凹點(diǎn)方向且不超過(guò)目標(biāo)節(jié)點(diǎn)坐標(biāo)的情況下存在向目標(biāo)節(jié)點(diǎn)進(jìn)一步計(jì)算的可通行節(jié)點(diǎn)。凹點(diǎn)轉(zhuǎn)折點(diǎn)的具體計(jì)算方法是由凹點(diǎn)識(shí)別位置來(lái)對(duì)目標(biāo)節(jié)點(diǎn)方向的路徑進(jìn)行計(jì)算，通過(guò)對(duì)當(dāng)前凹點(diǎn)的前進(jìn)方向中的節(jié)點(diǎn)進(jìn)行計(jì)算分析，判斷在偏向于目標(biāo)節(jié)點(diǎn)的一側(cè)是否存在可通行節(jié)點(diǎn)，或者在偏向于目標(biāo)節(jié)點(diǎn)的一側(cè)的節(jié)點(diǎn)是否存在凹點(diǎn)識(shí)別判斷值表中的值，且與當(dāng)前計(jì)算節(jié)點(diǎn)偏向目標(biāo)節(jié)點(diǎn)一側(cè)的的節(jié)點(diǎn)權(quán)重值不同的可通行節(jié)點(diǎn)。例如，當(dāng)前凹點(diǎn)方向?yàn)闄M向時(shí)，需要檢測(cè)在凹點(diǎn)方向偏向于目標(biāo)節(jié)點(diǎn)的一側(cè)是否存在一個(gè)可通行節(jié)點(diǎn)，當(dāng)計(jì)算到下一個(gè)節(jié)點(diǎn)為障礙物節(jié)點(diǎn)，并在此計(jì)算過(guò)程中不存在凹點(diǎn)轉(zhuǎn)折點(diǎn)的情況，那么這個(gè)凹點(diǎn)會(huì)被認(rèn)為不符合要求，將這個(gè)凹點(diǎn)進(jìn)行刪除。在識(shí)別凹點(diǎn)轉(zhuǎn)折點(diǎn)的過(guò)程中只會(huì)記錄凹點(diǎn)方向第一個(gè)能夠向目標(biāo)節(jié)點(diǎn)進(jìn)一步計(jì)算的節(jié)點(diǎn)，將這個(gè)節(jié)點(diǎn)設(shè)置為凹點(diǎn)轉(zhuǎn)折點(diǎn)，并記錄轉(zhuǎn)折點(diǎn)的坐標(biāo)到對(duì)應(yīng)的凹點(diǎn)判斷值表中，如圖6所示。

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

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

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

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

在評(píng)估階段通過(guò)如下公式計(jì)算每個(gè)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的估計(jì)距離和實(shí)際距離，并進(jìn)行比較。

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

式中：[h（x）]是啟發(fā)式函數(shù)，通過(guò)當(dāng)前節(jié)點(diǎn)對(duì)終點(diǎn)距離進(jìn)行預(yù)估計(jì)；[g（x）]是從起始節(jié)點(diǎn)到目前節(jié)點(diǎn)的實(shí)際距離；[f（x）]是起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的預(yù)計(jì)消耗。

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

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

2.2" 對(duì)A*算法進(jìn)行安全性改進(jìn)

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

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

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

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

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

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

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

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

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

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

3" 算法測(cè)試

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

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

4" 結(jié)" 語(yǔ)

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

參考文獻(xiàn)

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

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

[3] 田茹，曹茂永，馬鳳英，等.基于改進(jìn)A*算法的農(nóng)用無(wú)人機(jī)路徑規(guī)劃[J].現(xiàn)代電子技術(shù)，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ù)字地圖預(yù)處理的實(shí)時(shí)航跡規(guī)劃[J].南京航空航天大學(xué)學(xué)報(bào)，2002，34（4）：382?385.

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

[7] 傅夢(mèng)穎，王培曉，張恒才，等.一種室內(nèi)導(dǎo)航網(wǎng)絡(luò)眾包構(gòu)建方法[J].測(cè)繪科學(xué)技術(shù)學(xué)報(bào)，2019，36（1）：100?104.

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

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

[10] 余文凱，章政，付雪畫(huà)，等.基于地圖預(yù)處理及改進(jìn)A*算法的路徑規(guī)劃[J].高技術(shù)通訊，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] 周敬東，楊磊，張超.改進(jìn)A*算法的室內(nèi)機(jī)器人路徑規(guī)劃[J].現(xiàn)代電子技術(shù)，2022，45（8）：181?186.

[13] 楊光永，戈一航，晏婷，等.基于調(diào)和A*算法在移動(dòng)機(jī)器人中的研究[J].現(xiàn)代電子技術(shù)，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ù)處理識(shí)別凹點(diǎn)優(yōu)化路徑規(guī)劃效率的方法[J].現(xiàn)代電子技術(shù)，2024，47（9）：182?186.

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

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

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

作者簡(jiǎn)介：陳文博（1998—），男，蒙古族，內(nèi)蒙古錫林浩特蘇尼特右旗人，碩士，研究方向?yàn)閷?dǎo)航定位技術(shù)。

趙云峰（1978—），男，河南開(kāi)封人，碩士，副教授，研究方向?yàn)閷?dǎo)航定位技術(shù)。

趙世鵬（2000—），男，河北承德人，碩士，研究方向?yàn)閷?dǎo)航定位技術(shù)。