基于改進(jìn)D*算法的室內(nèi)移動(dòng)機(jī)器人路徑規(guī)劃

王帥軍，胡立坤，王一飛

(廣西大學(xué) 電氣工程學(xué)院，廣西 南寧 530004)

0 引 言

路徑規(guī)劃是移動(dòng)機(jī)器人實(shí)現(xiàn)自主導(dǎo)航的關(guān)鍵技術(shù)之一[1]，國(guó)內(nèi)外學(xué)者做了大量的研究，多種算法被應(yīng)用到路徑規(guī)劃中。傳統(tǒng)的路徑規(guī)劃方法例如人工勢(shì)場(chǎng)法[2]，但是容易出現(xiàn)局部最優(yōu)的缺點(diǎn)產(chǎn)生抖動(dòng)和震蕩現(xiàn)象從而無(wú)法完成任務(wù)。智能算法在路徑規(guī)劃上也得到了充分的應(yīng)用[3-5]，以及傳統(tǒng)算法和智能算法相結(jié)合的混合算法[6-8]，但智能算法普遍存在著收斂速度慢、搜索空間大、控制變量多等不足等缺陷。而后兩種啟發(fā)式算法：A*[9]和D*[10]算法由于原理簡(jiǎn)單、容易實(shí)現(xiàn)受到關(guān)注。D*算法與A*算法類(lèi)似，不同在于是從終點(diǎn)到起點(diǎn)進(jìn)行反向搜索。基于文獻(xiàn)[11]可知，基于動(dòng)態(tài)窗口法，將全局規(guī)劃A*算法和局部規(guī)劃D*算法結(jié)合，最大程度確保路徑精確度，與此同時(shí)，還應(yīng)使算法實(shí)時(shí)性在一定程度上有所提高。根據(jù)文獻(xiàn)[12]可知，為了使路徑長(zhǎng)度有所縮減，并實(shí)現(xiàn)盡可能提升路徑質(zhì)量的目的，對(duì)D*算法進(jìn)行了一系列改進(jìn)，主要表現(xiàn)于3個(gè)方面：①在此算法中加入了視線算法；②引入懶惰更新思想；③此算法引入了距離變換。基于文獻(xiàn)[13]的相關(guān)內(nèi)容可知，以D*算法所得路徑為基準(zhǔn)，采取有效方式獲得特征點(diǎn)路徑，并有效利用遺傳算法的特定功能，得知最優(yōu)路徑。文獻(xiàn)[14]中明確指出，以遍歷路徑中的全部節(jié)點(diǎn)為基礎(chǔ)，對(duì)于某兩個(gè)節(jié)點(diǎn)，若兩者間并無(wú)任何障礙物存在，則可對(duì)其中間節(jié)點(diǎn)采取特殊操作(即，刪除之)，并使前后節(jié)點(diǎn)銜接在一起，從而實(shí)現(xiàn)平滑路徑模型的基本構(gòu)建。基于上述幾篇文獻(xiàn)可知，對(duì)于D*算法，文獻(xiàn)中的方法均在一定程度上改進(jìn)了其搜索效率，但依然存在一些弊端，例如①所得路徑與障礙物之間具有相對(duì)較近的距離，現(xiàn)實(shí)生活中，機(jī)器人行走過(guò)程中，應(yīng)時(shí)刻與障礙物留有相對(duì)適中的距離；②若突然改變目標(biāo)點(diǎn)，則已有算法無(wú)法應(yīng)用，應(yīng)再次規(guī)劃算法。

對(duì)于以上兩個(gè)問(wèn)題，提出改進(jìn)D*算法的啟發(fā)函數(shù)和子節(jié)點(diǎn)選取方式，使生成的路徑與障礙物保持適當(dāng)?shù)木嚯x。基于格柵法構(gòu)建地圖信息，通過(guò)沃羅諾伊圖[15]得到局部最佳目標(biāo)點(diǎn)，關(guān)閉無(wú)關(guān)區(qū)域節(jié)點(diǎn)，提升算法計(jì)算能力。將改進(jìn)D*算法和沃羅諾伊路線圖法相結(jié)合進(jìn)行路徑仿真，解決終點(diǎn)改變時(shí)計(jì)算量大的問(wèn)題，同時(shí)考慮在機(jī)器人行進(jìn)過(guò)程中突然遭遇障礙物的情形。

1 問(wèn)題描述

1.1 地圖建立

構(gòu)建地圖模型時(shí)，本設(shè)計(jì)運(yùn)用的方法主要是格柵法，具體構(gòu)建階段，任何一個(gè)格柵均與現(xiàn)實(shí)生活中的環(huán)境位置存在一一對(duì)應(yīng)的關(guān)系。在格柵地圖中，最具關(guān)鍵性的一項(xiàng)參數(shù)便是分辨率，若其具有相對(duì)較高的分辨率，則意味著環(huán)境具有更高的精準(zhǔn)性；反之，則精準(zhǔn)性會(huì)有所降低。本設(shè)計(jì)主要基于室內(nèi)環(huán)境而研究，故基于格柵法實(shí)現(xiàn)地圖模型的合理構(gòu)建具有較好的合理性。

如圖1所示，白色格柵是自由空間，黑色格柵是不可達(dá)區(qū)域。假設(shè)不考慮高度約束，且機(jī)器人行進(jìn)方向只有8個(gè)。將地圖信息存放在二維矩陣G(i,j) 中，矩陣可表示如下

(1)

圖1 仿真地圖模型

1.2 D*算法分析

1.2.1 距離表現(xiàn)形式

對(duì)于二維空間中任意兩點(diǎn)(x1,y1)、(x2,y2)， 可通過(guò)不同方式進(jìn)行間距的度量，主要如歐幾里德距離、曼哈頓距離和切比雪夫距離，這些度量標(biāo)準(zhǔn)相應(yīng)的表達(dá)式分別如下

(2)

DManhattan=|x2-x1|+|y2-y1|

(3)

DChebyshev(x,y)=max(|x2-x1|,|y2-y1|)

(4)

對(duì)比分析可知后兩個(gè)標(biāo)準(zhǔn)不進(jìn)行平方項(xiàng)處理，這樣處理速度顯著提高。

1.2.2 啟發(fā)函數(shù)

D*算法在分析時(shí)一般用到估價(jià)函數(shù)，其表達(dá)式如下

f(n)=g(n)+h(n)

(5)

其中，n為當(dāng)前節(jié)點(diǎn)；g(n) 是基本項(xiàng)，對(duì)應(yīng)于兩個(gè)節(jié)點(diǎn)的實(shí)際成本；h(n) 表示啟發(fā)項(xiàng)，表示兩點(diǎn)最小成本估計(jì)值。對(duì)這種函數(shù)而言，D*算法的選用主要基于一點(diǎn)，即歐氏距離，首先展開(kāi)的操作是以各個(gè)節(jié)點(diǎn)為基準(zhǔn)，分別對(duì)其實(shí)行平方根運(yùn)算，該操作在一定程度上拉低了處理速度，此外，由于啟發(fā)函數(shù)基于歐氏距離而確定，因此，角度的限制并未納入考慮的范圍內(nèi)，且該距離主要指任意兩點(diǎn)的實(shí)際距離，而本設(shè)計(jì)在地圖模型的構(gòu)建中，運(yùn)用的方法主要是格柵法，并不能實(shí)現(xiàn)對(duì)兩個(gè)格柵間距的詳細(xì)描述，使得圖2仿真路徑小范圍內(nèi)具有相對(duì)比較高的轉(zhuǎn)彎頻率，且造成了相對(duì)較大的轉(zhuǎn)彎角度。

圖2 D*路徑

1.2.3 D*算法流程

A*算法的運(yùn)用具有一定的局限性，例如，僅用于靜態(tài)地圖的處理。而對(duì)于D*算法，從某種程度而言，可視為A*算法的進(jìn)一步改進(jìn)與拓展，是一種動(dòng)態(tài)逆向扇形搜索算法，主要是以地圖為基礎(chǔ)，采取一系列有效措施與手段實(shí)現(xiàn)其格柵建模操作，并完成最小成本路徑的尋找過(guò)程。D*算法具有以下幾種特點(diǎn)，即：①以目標(biāo)點(diǎn)為核心，擴(kuò)展單個(gè)節(jié)點(diǎn)周?chē)?jié)點(diǎn)；②以全局地圖為核心，即便局部發(fā)生一定的改變，也并不會(huì)過(guò)多影響路徑；③一般而言，到達(dá)終點(diǎn)的路徑成本均是固定的；④計(jì)算成本相對(duì)較低。正是基于D*算法的這些特點(diǎn)，使其表現(xiàn)出了自身的獨(dú)特優(yōu)勢(shì)。D*算法在處理時(shí)對(duì)應(yīng)的流程為：首先，Process-State()路線規(guī)劃階段；其次，Modify-Cost()成本更改及傳播階段，見(jiàn)表1。h、k代表的含義均僅有一個(gè)，具體含義依次是終點(diǎn)到當(dāng)前節(jié)點(diǎn)、當(dāng)前節(jié)點(diǎn)到終點(diǎn)路徑的最短路徑。此外，該算法的集合同樣涉及兩個(gè)，分別為OPEN和CLOSED集合。

表1 D*算法偽代碼

基于D*路徑仿真結(jié)果如圖2所示，起點(diǎn)終點(diǎn)分別為(20,10)和(80,80)，特別地將地圖成本信息轉(zhuǎn)化為地圖高度信息，高度表示到目標(biāo)的距離，可以更直觀的看出D*算法流程。從仿真圖可以看出，D*算法拐彎角度大，部分路段和障礙物距離較近，這對(duì)機(jī)器人在實(shí)際環(huán)境中行走時(shí)是不利的。D*雖然支持地圖成本改變后進(jìn)行增量式規(guī)劃，但與之前算法一樣，也不支持終點(diǎn)的臨時(shí)改變，因此引入沃羅諾伊路線圖法來(lái)解決該問(wèn)題。

1.3 沃羅諾伊圖基本思想

沃羅諾伊路線圖法是一種全局路徑規(guī)劃方法，這種方法解決了在路徑規(guī)劃和生成中的成本差異，同時(shí)也支持動(dòng)態(tài)的起點(diǎn)和終點(diǎn)。這樣，路徑規(guī)劃問(wèn)題就類(lèi)似于在地圖中建立一個(gè)避開(kāi)障礙物的鐵路網(wǎng)，只需要一次計(jì)算就可以從任意起點(diǎn)去到任意終點(diǎn)。

沃羅諾伊圖是一種關(guān)于空間劃分的數(shù)據(jù)結(jié)構(gòu)。這種圖中含有一定量沃羅諾伊單元，其中黑色五角星表示站點(diǎn)，幾個(gè)站點(diǎn)組合形成網(wǎng)格，中心站點(diǎn)Pi對(duì)應(yīng)的多邊形就是沃羅諾伊域Vi， 當(dāng)前站點(diǎn)距這種區(qū)域中全部點(diǎn)的距離小于到其它點(diǎn)的。此多邊形的邊到相鄰站點(diǎn)Pi和Pj間距相同。假設(shè)一個(gè)集合Q?R2中的節(jié)點(diǎn)q={q1,q2,…,qn}，Vi可基于如下表達(dá)式確定

(6)

沃羅諾伊圖是一種關(guān)于空間劃分的數(shù)據(jù)結(jié)構(gòu)，如圖3所示。

圖3 沃羅諾伊

在MATLAB中對(duì)地圖環(huán)境進(jìn)行見(jiàn)表2處理，map變量為原始地圖信息矩陣。

表2 制作沃羅諾伊路線

所得沃羅諾伊圖詳見(jiàn)圖4，形成流程主要基于視障礙物為熱源，當(dāng)受到一定溫度后，自由格柵會(huì)迅速發(fā)生膨脹，并以同等的速度將所得熱能迅速傳遞出去[16]。此前，由自由空間轉(zhuǎn)變?yōu)榫W(wǎng)絡(luò)的過(guò)程中，涉及的曲線具有與障礙物等同的距離，基于此，采取一系列有效措施使路線圖完成相應(yīng)地平滑性處理，從而得到最終的沃羅諾伊路線圖，由此可知，從安全系數(shù)角度而言，路線圖中的概括性路徑已充分具備此條件，然而，具有相對(duì)而言比較多的轉(zhuǎn)角、且有相對(duì)而言比較長(zhǎng)的路徑，路線圖的核心點(diǎn)在于將地圖分區(qū)以及在目標(biāo)點(diǎn)改變后視為臨時(shí)路徑來(lái)應(yīng)用。對(duì)于D*算法，為了在一定程度上提高其搜索效率，本設(shè)計(jì)詳細(xì)劃分了仿真環(huán)境，涉及的局部環(huán)境共有8個(gè)，如圖4所示。

圖4 沃羅諾伊路線

2 算法改進(jìn)與融合

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

通過(guò)切比雪夫距離來(lái)取代原算法中的歐氏距離來(lái)解決該問(wèn)題，在二維空間中，切比雪夫距離即為棋盤(pán)距離

DChess(Goal,n)=max(|xGoal-xn|,|yGoal-yn|)

(7)

式(7)可確定出當(dāng)前格柵n到終點(diǎn)的步數(shù)最小值，本文在研究中設(shè)置垂直水平方向成本為10，對(duì)角線方向的為14，不進(jìn)行開(kāi)方運(yùn)算，而提高算法的實(shí)時(shí)性。在這種圖形中，對(duì)角線方向機(jī)器人可移動(dòng)。這樣可通過(guò)如下關(guān)系式確定出當(dāng)前節(jié)點(diǎn)到目標(biāo)點(diǎn)的間距

Dchess(Goal,n)=hdiagonal+hstraight

(8)

其中，h1、h2分別為

hdiagonal=min(|xGoal-xn|,|yGoal-yn|)

(9)

hstraight=|yGoal-yn|-|xGoal-xn|

(10)

將直行、斜行成本代入，得到

h(n)=10hstraight+14hdiagonal=
10|yGoal-yn|-|xGoal-xn|+
14min[|yGoal-yn|,|xGoal-xn|]

(11)

2.2 子節(jié)點(diǎn)選取改進(jìn)

類(lèi)似于A*算法，D*算法也是以當(dāng)前節(jié)點(diǎn)為基準(zhǔn)，采取有效方式使其8個(gè)鄰居子節(jié)點(diǎn)完成擴(kuò)展操作，并確保其以混亂順序狀態(tài)加入open list中，當(dāng)然，此中可能涉及障礙物。然而，這也存在一定的問(wèn)題，即：部分路徑在具體的行進(jìn)過(guò)程中，與障礙物有所貼近，若基于D*算法，則會(huì)在一定程度上對(duì)機(jī)器人構(gòu)成威脅。本設(shè)計(jì)對(duì)D*算法做出了相應(yīng)的改進(jìn)，尤其體現(xiàn)于子節(jié)點(diǎn)的選取問(wèn)題上。如圖5所示，對(duì)于一級(jí)優(yōu)先節(jié)點(diǎn)的選取，主要選定了垂直水平方向的子節(jié)點(diǎn)(2、4、6和8)，而對(duì)于二級(jí)優(yōu)先節(jié)點(diǎn)，則主要選取了對(duì)角線方向的子節(jié)點(diǎn)(1、3、5和7)。對(duì)于擴(kuò)展節(jié)點(diǎn)，主要確定為一級(jí)優(yōu)先節(jié)點(diǎn)，然后基于此，通過(guò)下述內(nèi)容選定二級(jí)優(yōu)先節(jié)點(diǎn)：①若2為障礙物格柵，其中節(jié)點(diǎn)1、3不可選擇。這樣也排除路徑0-1、0-3；②若4為此類(lèi)格柵，則節(jié)點(diǎn)3、5不可選，排除路徑0-3、0-5；③6為此類(lèi)格柵情況下，則節(jié)點(diǎn)5、7不可選擇，排除路徑0-5、0-7；④若8為此類(lèi)格柵，節(jié)點(diǎn)7、1不可選擇，因而可排除路徑0-7、0-1。

圖5 格柵

2.3 改進(jìn)算法流程

為了使上述問(wèn)題得到有效改進(jìn)，本文基于相應(yīng)上述改進(jìn)，而給出相關(guān)算法流程，具體如下：

(1)加載地圖信息map(100,100)， 初始化起始格柵、目標(biāo)格柵： start(20,10)、 goal(80,80)；

(2)基于沃羅諾伊路線圖，采取特定的方式與操作獲得地圖的概括性路徑，對(duì)仿真環(huán)境作出詳細(xì)劃分，共涉及8個(gè)局部環(huán)境，在TriplePoint集合中置入關(guān)鍵節(jié)點(diǎn)。無(wú)論是哪間房室，均應(yīng)在入口及出口設(shè)定相應(yīng)的關(guān)鍵節(jié)點(diǎn)，關(guān)鍵節(jié)點(diǎn)的位置主要定于兩端障礙物的中端；

(3)以目標(biāo)格柵為核心，采取有效方式評(píng)估其與起點(diǎn)格柵所處的局部環(huán)境是否相一致，若相一致，則通過(guò)改進(jìn)D*算法進(jìn)行規(guī)劃，確定出最優(yōu)路徑。若不一致，則進(jìn)入下一步；

(4)設(shè)置起點(diǎn)和目標(biāo)點(diǎn)為中心，根據(jù)兩種局部環(huán)境相關(guān)情況，選擇特定方式而得到相關(guān)的概括性路徑；

(5)以起點(diǎn)為核心，將其相關(guān)的關(guān)鍵節(jié)點(diǎn)視為局部目標(biāo)點(diǎn)；然后以終點(diǎn)為基準(zhǔn)，將其相關(guān)的關(guān)鍵節(jié)點(diǎn)視為局部起始點(diǎn)，采取有效手段展開(kāi)路徑規(guī)劃操作，并將所得的局部最優(yōu)路徑加以保存。以改進(jìn)后的D*算法為核心，詳細(xì)規(guī)劃途徑區(qū)域，并遍歷所有路徑點(diǎn)，以節(jié)點(diǎn)ni為基準(zhǔn)，當(dāng)其前后節(jié)點(diǎn)連線不存在任何障礙物時(shí)，對(duì)節(jié)點(diǎn)ni采取刪除操作，然后進(jìn)行平滑處理。最后完成全部路徑的合并；

(6)如果目標(biāo)點(diǎn)已非原有目標(biāo)點(diǎn)，則應(yīng)將處于關(guān)閉狀態(tài)的節(jié)點(diǎn)打開(kāi)，明確新目標(biāo)的具體位置，對(duì)機(jī)器人加以操作控制，使其尋找到最近的沃羅諾伊邊，并以已有的概括性路徑為基準(zhǔn)，尋找新的關(guān)鍵節(jié)點(diǎn)，此后，由步驟(4)繼續(xù)向下操作。

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

為了對(duì)改進(jìn)D*算法的性能進(jìn)行驗(yàn)證，而在同一臺(tái)計(jì)算機(jī)(Win10，英特爾 i7，內(nèi)存16 GB)上仿真分析，總共5組。對(duì)比分析：簡(jiǎn)單地圖下：①S1=[20,10]，G1=[80,80]； ②S2=[80,20]，G2=[25,50] 和復(fù)雜地圖下3種算法生成路徑、臨時(shí)遭遇障礙物相關(guān)情況。在MATLAB r2016b平臺(tái)編譯運(yùn)行。

3.1 改進(jìn)D*仿真與對(duì)比

由圖6知：A*算法的缺陷主要體現(xiàn)于下述幾點(diǎn)，即：具有相對(duì)較高的轉(zhuǎn)彎頻率，相對(duì)較大的轉(zhuǎn)彎角度，同時(shí)，某些路徑與障礙物之間的距離相對(duì)較近，并不具有較高的路徑安全性；在節(jié)點(diǎn)擴(kuò)展方面，D*算法與上述算法具有一定的相似性，故依然存在上述問(wèn)題；如圖6(c)所示，對(duì)于改進(jìn)后的D*算法，主要基于優(yōu)先級(jí)子領(lǐng)域的選定準(zhǔn)則確定了最優(yōu)路徑，使上述問(wèn)題有了明顯的改進(jìn)，并在較大程度上提高了路徑安全性。此中，路徑長(zhǎng)度的識(shí)別是基于圖像處理技術(shù)來(lái)完成，即，而整個(gè)操作中確保具有等同的像素比例尺下(簡(jiǎn)單地圖：589×523，復(fù)雜地圖：955×698)。由表3能夠得知，相比于A*算法，D*算法在地圖分區(qū)時(shí)，做出了相應(yīng)的改進(jìn)，主要以沃羅諾伊圖為基準(zhǔn)，某些無(wú)用節(jié)點(diǎn)首先放入CLOSED LIST中，且D*算法規(guī)劃循環(huán)迭代次數(shù)在已有基礎(chǔ)上有所增加，增加了11%，已提高至76%；且其它方面的性能均有所提升。表4可以得知，第二組起訖點(diǎn)下路徑長(zhǎng)度有一定幅度增加，另3組數(shù)據(jù)取得較好優(yōu)化效果。在一些特定狀況下，為了使路徑安全性在一定程度上有所提升，本文算法會(huì)以路徑長(zhǎng)度的犧牲為代價(jià)[17]。

圖6 簡(jiǎn)單地圖下兩組起訖點(diǎn)3種算法路徑仿真

表3 第一組

表4 第二組

在復(fù)雜地圖模型下，A*算法的轉(zhuǎn)角次數(shù)明顯減少，然而，具有相對(duì)而言比較長(zhǎng)的路徑，盡管D*算法對(duì)此做出了相應(yīng)的優(yōu)化處理，但卻導(dǎo)致轉(zhuǎn)角次數(shù)在原有基礎(chǔ)上有所增加。根據(jù)表5可以得知，相比于上述兩種算法，本文的改進(jìn)主要體現(xiàn)于迭代次數(shù)和處理時(shí)間方面。在圖7前兩圖對(duì)應(yīng)的圓圈標(biāo)記區(qū)，兩種算法規(guī)劃的路徑與障礙物間距較近，都穿過(guò)圖中的桌椅，圖7(c)對(duì)應(yīng)的規(guī)劃路徑和障礙物距離適中，同時(shí)也避開(kāi)桌椅，因而在路徑安全性方面相對(duì)高。

本文建立的改進(jìn)D*算法可有效的避免A*和D*算法的實(shí)時(shí)性差，轉(zhuǎn)彎次數(shù)多的缺陷，在路徑長(zhǎng)度方面，優(yōu)化不顯著，不過(guò)安全性顯著高于傳統(tǒng)算法的，有效提高了路徑質(zhì)量。

圖7 復(fù)雜地圖下3種算法路徑仿真

表5 第三組

3.2 臨時(shí)遭遇障礙物

某些狀況下，有可能突然碰到未知的障礙物，據(jù)此，本文的改進(jìn)D*算法則可對(duì)其進(jìn)行較好的處理。以D*算法為基礎(chǔ)，在其現(xiàn)有優(yōu)勢(shì)的基礎(chǔ)上，根據(jù)現(xiàn)有的信息，在圖8所示的狀況中，極大地縮減了二次規(guī)劃的迭代次數(shù)，并將具體次數(shù)縮減至83次。

3.3 目標(biāo)點(diǎn)改變

無(wú)論是使用哪種傳統(tǒng)算法，若路徑規(guī)劃的目標(biāo)點(diǎn)與原有目標(biāo)點(diǎn)不一致，則這些算法均不能較好地完成后續(xù)的工作。對(duì)于這種改進(jìn)D*算法，在實(shí)際應(yīng)用過(guò)程中可基于沃羅諾伊路線圖，而有效的避免了上述問(wèn)題，有較高的應(yīng)用價(jià)值。假定機(jī)器人運(yùn)行過(guò)程中，到達(dá)某位置(70,41)時(shí)，基于內(nèi)部操作可定義新目標(biāo)點(diǎn)位置，并由此生成沃羅諾伊路線圖，以此為基礎(chǔ)，機(jī)器人會(huì)以最適合的路徑運(yùn)行至合適的路線圖，并由內(nèi)部特定的操作確定合適的臨時(shí)目標(biāo)點(diǎn)。目前，目標(biāo)點(diǎn)則由(80,80)發(fā)生了相應(yīng)的改變，轉(zhuǎn)變?yōu)?25,80)，如圖9所示，將A*和D*算法及改進(jìn)后的D*算法均列于圖中。仿真數(shù)據(jù)結(jié)果對(duì)比如下：在機(jī)器人行進(jìn)到(70,41)，目標(biāo)點(diǎn)發(fā)生了相應(yīng)的轉(zhuǎn)變，變換為(25，80)，對(duì)應(yīng)時(shí)間依次是：TA*=4.998s、TD*=5.706s、TID*=2.974s。 相比之下，改進(jìn)D*算法的規(guī)劃時(shí)間在較大程度上有所縮短。由此可知，這種路徑規(guī)劃下，機(jī)器人運(yùn)行過(guò)程中駛向最近的沃羅諾伊邊，并沿路線圖相關(guān)路徑不斷前進(jìn)一直到目標(biāo)區(qū)對(duì)應(yīng)的局部節(jié)點(diǎn)，使運(yùn)行速度在較大程度上有所提升。

圖8 遭遇障礙物

圖9 目標(biāo)點(diǎn)改變后3種算法路徑仿真

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

A*算法、D*算法所得路徑并不能滿足具體的需求。因此，本文對(duì)D*算法進(jìn)行了相應(yīng)的改進(jìn)，基于格柵地圖模型，結(jié)合沃羅諾伊圖得到一條具有相對(duì)較高安全性、高質(zhì)量性的路徑。以已知環(huán)境為基礎(chǔ)，采取有效措施對(duì)其展開(kāi)局部分解，并選定相應(yīng)的局部關(guān)鍵節(jié)點(diǎn)，關(guān)閉局部區(qū)域，這樣可提高算法的處理速度，更好滿足實(shí)時(shí)性要求。同時(shí)，針對(duì)啟發(fā)函數(shù)的選取方式，本文也做出了相應(yīng)的改進(jìn)，并改進(jìn)了本有的子節(jié)點(diǎn)選取方式，引入優(yōu)先級(jí)概念，使各方面的性能均有所提升，例如，路徑長(zhǎng)度有所減小、處理時(shí)間極大地縮短等?；谖至_諾伊圖，若目標(biāo)點(diǎn)發(fā)生改變，則可在計(jì)算量相對(duì)較小的前提下，實(shí)現(xiàn)機(jī)器人到達(dá)新目標(biāo)點(diǎn)的目的。最后，在MATLAB上完成了相應(yīng)的仿真處理，結(jié)果可知，無(wú)論是對(duì)于生成路徑質(zhì)量的改善方面，還是安全性的提升方面，本文提出的改進(jìn)D*算法均發(fā)揮了一定的優(yōu)勢(shì)，且此項(xiàng)改進(jìn)工作使室內(nèi)移動(dòng)機(jī)器人可更加出色地完成工作內(nèi)容，對(duì)于多數(shù)室內(nèi)環(huán)境有較好的適用性。