王 磊，王 毓，孫力帆

（1. 河南科技大學(xué) 國(guó)際教育學(xué)院，洛陽 471023；2. 河南科技大學(xué) 信息工程學(xué)院，洛陽 471023）

人工智能時(shí)代的機(jī)器人已不再充當(dāng)簡(jiǎn)單的指令執(zhí)行角色，而是朝著智能化、高效化的方向發(fā)展，它代表了高科技的發(fā)展前沿，已經(jīng)在各行各業(yè)中得到廣泛應(yīng)用。路徑規(guī)劃是移動(dòng)機(jī)器人研究領(lǐng)域的熱點(diǎn)，具有重要的理論與現(xiàn)實(shí)意義，其主要任務(wù)是使機(jī)器人能夠成功避開環(huán)境中的各種障礙，并沿著最低代價(jià)的路徑到達(dá)終點(diǎn)。依據(jù)機(jī)器人對(duì)地圖信息的掌握情況可將算法分為全局路徑規(guī)劃與局部路徑規(guī)劃。其中，A*（A-Star）[1-3]是一種經(jīng)典的全局路徑規(guī)劃算法，它是Dijkstra算法[4-6]與寬度優(yōu)先搜索（Breadth First Search,BFS）算法[7]的結(jié)合，是一種啟發(fā)式搜索算法。A*算法利用啟發(fā)函數(shù)指導(dǎo)尋路過程，通過計(jì)算柵格地圖各結(jié)點(diǎn)的代價(jià)值，選取待擴(kuò)展的最佳結(jié)點(diǎn)，直至找到最終目標(biāo)點(diǎn)位置，該算法以超強(qiáng)的環(huán)境適應(yīng)能力獲得了非常廣泛的應(yīng)用，但缺點(diǎn)是隨著地圖規(guī)模的擴(kuò)大，待搜索結(jié)點(diǎn)數(shù)量大幅增加，路徑規(guī)劃時(shí)間變得過于漫長(zhǎng)。

為了解決A*算法在大場(chǎng)景地圖中的搜索時(shí)間問題，前人進(jìn)行了各種改進(jìn)。雙向A*（Bidirectional A-Star）算法[8]采用正反向交替機(jī)制，分別從起點(diǎn)和終點(diǎn)朝著相對(duì)方向進(jìn)行搜索，最終在起點(diǎn)、終點(diǎn)連線的中點(diǎn)區(qū)域匯合，可找到最短路徑，提升搜索效率。加權(quán)A*（The weighted A-Star）算法[9]通過尋找權(quán)重和啟發(fā)項(xiàng)之間的關(guān)系選擇最佳權(quán)重值，后來又提出了基于起點(diǎn)和目標(biāo)點(diǎn)之間長(zhǎng)度與權(quán)重集相關(guān)聯(lián)的動(dòng)態(tài)加權(quán)方法，還有基于路徑成本與權(quán)重集相關(guān)聯(lián)的方法，這些方法雖能提升尋路效率，但結(jié)果不穩(wěn)定，不能很好地平衡路徑代價(jià)與搜索時(shí)間之間的關(guān)系。Theta*[10]是一種任意角度的尋路算法，可以找到比A*更短的路徑，它在A*基礎(chǔ)上增加了結(jié)點(diǎn)之間的可見性檢測(cè)，每擴(kuò)展一個(gè)結(jié)點(diǎn)都要先計(jì)算該結(jié)點(diǎn)與相關(guān)結(jié)點(diǎn)是否可見，因而增加了計(jì)算量，比A*耗時(shí)更長(zhǎng)。松弛A*（Relaxed A-Star）算法[11]用到達(dá)結(jié)點(diǎn)n的第一條路徑成本來近似從起點(diǎn)到n的所有路徑成本，即g(n)只被計(jì)算一次，省略了原A*算法多次比較g(n)、更新g(n)的步驟，因此搜索時(shí)間縮短，但不能保證找到最優(yōu)解。Harabor D等人于2011年提出了跳點(diǎn)搜索（Jump Point Search, JPS）算法[12-15]，該算法改進(jìn)了A*的無差別擴(kuò)展規(guī)則，只擴(kuò)展有代表性的特殊柵格點(diǎn)，從而大大降低了結(jié)點(diǎn)訪問量，使算法效率得到大幅提升。以上算法僅在A*算法的規(guī)則層面進(jìn)行了改進(jìn)，并未考慮到障礙物在地圖中的整體分布情況，仍然處于盲目搜索階段。為了降低搜索過程的盲目性，本文提出了一種障礙物登陸點(diǎn)檢測(cè)方法，利用障礙物分布信息尋找登陸點(diǎn)，將結(jié)點(diǎn)擴(kuò)展范圍縮小至障礙物邊緣區(qū)域，從而減少結(jié)點(diǎn)訪問數(shù)量，再利用改進(jìn)的Dijkstra算法搜索最短路徑，進(jìn)一步提高路徑規(guī)劃效率。

1 障礙物登陸點(diǎn)檢測(cè)算法實(shí)現(xiàn)

1.1 障礙物登陸點(diǎn)檢測(cè)算法主要思想

在地圖中規(guī)劃最短路徑，路徑轉(zhuǎn)折點(diǎn)一般位于障礙物的邊緣區(qū)域，如能夠檢測(cè)出起點(diǎn)至終點(diǎn)所有可能經(jīng)過的障礙物邊緣區(qū)域，不僅覆蓋了最短路徑的拐點(diǎn)，而且極大縮小了路徑規(guī)劃范圍，可減少冗余結(jié)點(diǎn)數(shù)量，提高算法效率。本文首先引入一個(gè)概念，在柵格地圖中相鄰的障礙柵格點(diǎn)組成一個(gè)整體區(qū)域，稱為障礙物塊[16]。當(dāng)起點(diǎn)、終點(diǎn)連線被障礙物塊阻擋時(shí)，最短路徑一定經(jīng)過該障礙物塊的某一邊緣點(diǎn)附近，本文將這一邊緣點(diǎn)定義為登陸點(diǎn)，該點(diǎn)由起點(diǎn)、終點(diǎn)的連線與相交障礙物塊的位置關(guān)系共同決定。

定義1：如圖1所示，連接起點(diǎn)S與終點(diǎn)E，直線SE與障礙物塊B1碰撞于A點(diǎn)，以起點(diǎn)S作為定點(diǎn)，將A點(diǎn)向障礙物塊 B1的兩側(cè)移動(dòng)，當(dāng)角度θ1與θ2最大時(shí)，對(duì)應(yīng)柵格點(diǎn)O1L與O1R即為障礙物塊 B1的左、右登陸點(diǎn)。

圖1 登陸點(diǎn)分布圖Fig.1 Distribution diagram of landing nodes

圖1 中，檢測(cè)到點(diǎn)O1L與O1R是障礙物塊B1的登陸點(diǎn)，再將O1L作為起點(diǎn)，E作為終點(diǎn)，直線O1LE與障礙物塊 B2發(fā)生碰撞，通過計(jì)算θ3與θ4的最大值可得到障礙物塊 B2的登陸點(diǎn)是O2L與O2R，再將O1R作為起點(diǎn)，E作為終點(diǎn)，直線O1RE與障礙物塊 B3發(fā)生碰撞，通過計(jì)算θ5與θ6的最大值可檢測(cè)到障礙物塊B3的登陸點(diǎn)是O3L與O3R，如此可計(jì)算出相關(guān)障礙物塊的登陸點(diǎn)O1L、O1R、O2L、O2R、O3L、O3R，使用遞歸算法檢測(cè)所有障礙物登陸點(diǎn)，流程圖如圖2所示。

圖2 登陸點(diǎn)遞歸檢測(cè)流程圖Fig.2 Flow chart of landing nodes recursive detection

1.2 構(gòu)建障礙物塊

遍歷地圖中所有柵格點(diǎn)，將上下左右相鄰的障礙物柵格標(biāo)記到同一個(gè)集合中，直到完成所有障礙物柵格的分類，最終形成多個(gè)障礙物塊，如圖3所示。具體操作步驟如下：

圖3 障礙物塊示意圖Fig.3 Diagram of obstacle blocks

Step1:建立柵格地圖對(duì)應(yīng)的二維數(shù)組G、存放待檢測(cè)結(jié)點(diǎn)列表 Lobstacle、當(dāng)前障礙物塊 Bobstacle以及障礙物塊列表LOB；

Step2:檢測(cè)當(dāng)前柵格點(diǎn)，如果是障礙物，則將當(dāng)前柵格點(diǎn)存入列表 Lobstacle中，并將當(dāng)前柵格點(diǎn)在數(shù)組G的相應(yīng)位置寫入true；

Step3:檢測(cè)列表 Lobstacle，如 Lobstacle為空，進(jìn)入Step4，否則檢測(cè) Lobstacle中第一個(gè)結(jié)點(diǎn)的8鄰域柵格點(diǎn)，如檢測(cè)到障礙物且該障礙物在數(shù)組G中的對(duì)應(yīng)值為false，則將該障礙物插入列表 Lobstacle中，并將數(shù)組G的對(duì)應(yīng)位設(shè)置為 true，同時(shí)將 Lobstacle的第一個(gè)結(jié)點(diǎn)加入Bobstacle中，然后刪除 Lobstacle中第一個(gè)結(jié)點(diǎn)，循環(huán)執(zhí)行Step3；

Step4:將 Bobstacle插入列表LOB，如數(shù)組G中所有值均為true，則程序結(jié)束，否則進(jìn)入Step2。

1.3 障礙物碰撞檢測(cè)

如何快速檢測(cè)直線與障礙物的碰撞點(diǎn)是尋找登陸點(diǎn)的第一步?？衫闷瘘c(diǎn)與終點(diǎn)坐標(biāo)，依據(jù)兩點(diǎn)式直線方程實(shí)現(xiàn)碰撞檢測(cè)。首先通過起點(diǎn)與終點(diǎn)坐標(biāo)建立直線方程，然后從起點(diǎn)開始向終點(diǎn)進(jìn)行碰撞檢測(cè)。設(shè)起點(diǎn)為 D1，終點(diǎn)為 D2，移動(dòng)步長(zhǎng)為λ，在直線D1D2上由起點(diǎn)向終點(diǎn)方向移動(dòng)檢測(cè)，檢測(cè)直線上的點(diǎn)( xn, yn)是否位于障礙物柵格內(nèi)，如位于障礙物柵格內(nèi)部，則發(fā)生碰撞，如移動(dòng)到終點(diǎn) D2仍未發(fā)現(xiàn)障礙物柵格，則稱點(diǎn) D1與 D2可直達(dá)。如圖4所示，柵格坐標(biāo)即為柵格中心點(diǎn)，其中黑色柵格(3,3)為障礙物，從起點(diǎn) D1(1,0)（黃色柵格）到終點(diǎn) D2(5,5)（紅色柵格）檢測(cè)障礙物，設(shè)置步長(zhǎng)λ=0.1，利用直線D1D2方程計(jì)算對(duì)應(yīng)柵格坐標(biāo)如式(1)所示：

圖4 障礙物碰撞檢測(cè)Fig.4 Obstacle collisiontest

其中，D1x為點(diǎn) D1的X軸坐標(biāo)，D1y為點(diǎn) D1的Y軸坐標(biāo)，D2x為點(diǎn) D2的X軸坐標(biāo)，D2y為點(diǎn) D2的Y軸坐標(biāo)。當(dāng) xi? [3,3.5]時(shí)，可計(jì)算出 yi? [2.5,3]，即直線D1D2上的點(diǎn)(xi,yi)位于障礙物柵格(3,3)區(qū)域內(nèi)，因而檢測(cè)到直線D1D2與障礙物柵格(3,3)發(fā)生碰撞，依據(jù)此方法可快速判斷出地圖中的任意兩點(diǎn)是否可直達(dá)。

1.4 計(jì)算障礙物映射角

圖5 中，連接起點(diǎn)S與終點(diǎn)E，則直線SE與灰色障礙物塊發(fā)生碰撞，然后分別連接起點(diǎn)與障礙物塊所有可直達(dá)邊緣點(diǎn)。設(shè)向量與的夾角為θ，由點(diǎn)積公式可知，且

圖5 障礙物映射角Fig.5 Mapping angles of obstacles

定義2：以SE為基準(zhǔn)線，S為支點(diǎn)，分別向障礙物塊的兩側(cè)移動(dòng)，形成夾角∠iOSE即為障礙物映射角。

隨著地圖中障礙物數(shù)量的增加，需要計(jì)算映射角的障礙柵格點(diǎn)變得越來越多，使得算法計(jì)算量增大，效率降低。為了避免出現(xiàn)這種問題，本文依據(jù)起點(diǎn)S與障礙物塊的位置關(guān)系僅選取某一方向上的邊緣障礙物柵格點(diǎn)，可大幅降低待計(jì)算結(jié)點(diǎn)數(shù)量。以圖5為例，起點(diǎn)位于障礙物塊的X軸負(fù)方向以及Y軸正方向，因而只選取障礙物塊X負(fù)方向的邊緣點(diǎn)與Y正方向的邊緣點(diǎn)即可，則待計(jì)算的障礙柵格點(diǎn)為 O1、O2、 O3、 O4、 O5、 O6、 O7、 O8、 O9、O10，在此方向上計(jì)算障礙物映射角，可有效節(jié)約系統(tǒng)資源，保證算法的高效性。具體操作步驟如下：

Step1：檢測(cè)起點(diǎn)S與障礙物塊的相對(duì)位置，并選取此方向上的障礙物塊邊緣柵格點(diǎn)組成集合G，計(jì)算G中所有柵格點(diǎn)的映射角；

Step2：依據(jù)障礙物邊緣柵格點(diǎn)與起點(diǎn)、終點(diǎn)連線的左右位置關(guān)系，將G中所有柵格點(diǎn)分為兩類，記作集合 GL與GR；

Step3：若 GL中最大的障礙物映射角唯一，則對(duì)應(yīng)柵格為左登陸點(diǎn)，若 GR中最大的障礙物映射角唯一，則對(duì)應(yīng)柵格為右登陸點(diǎn)，程序結(jié)束；若不唯一，進(jìn)入下一步；

Step4：刪除 GL與GR中非最大映射角的柵格點(diǎn)，分別計(jì)算 GL與GR中所有柵格點(diǎn)到起點(diǎn)S的直線距離，距離最短者即為登陸點(diǎn)。

1.5 擴(kuò)展登陸點(diǎn)

無障礙物阻擋時(shí)，直線是兩點(diǎn)之間最短路徑；受到障礙物阻擋時(shí)，最短路徑轉(zhuǎn)折點(diǎn)一定位于障礙物邊緣附近，如將登陸點(diǎn)向鄰近的非障礙柵格擴(kuò)展，則能夠覆蓋最短路徑轉(zhuǎn)折點(diǎn)。以8鄰域?yàn)槔?，在每一個(gè)登陸點(diǎn)8鄰域內(nèi)進(jìn)行擴(kuò)展，找到所有自由柵格點(diǎn)，作為路徑規(guī)劃的搜索空間。

如圖6所示，柵格點(diǎn)O是障礙物塊BLOCK的一個(gè)登陸點(diǎn)，在其8鄰域范圍內(nèi)進(jìn)行擴(kuò)展，擴(kuò)展出7個(gè)自由柵格點(diǎn)OE1、OE2、OE3、OE4、OE5、OE6、OE7。依此類推，對(duì)地圖中所有登陸點(diǎn)進(jìn)行擴(kuò)展，擴(kuò)展出的柵格點(diǎn)組成了路徑規(guī)劃搜索空間，從而實(shí)現(xiàn)地圖規(guī)模的有效縮減，然后利用搜索空間中的柵格點(diǎn)構(gòu)建賦權(quán)圖，以圖7為例，賦權(quán)圖由起點(diǎn)、終點(diǎn)以及所有黃色結(jié)點(diǎn)與紅色邊組成。

圖6 8鄰域登陸點(diǎn)擴(kuò)展Fig.6 Landing node expansion in 8 neighborhoods

圖7 非負(fù)賦權(quán)圖Fig.7 Non-negative graph with weight

2 改進(jìn)Dijkstra算法

Dijkstra是一種很有代表性的最短路徑算法，它是計(jì)算機(jī)科學(xué)家Edsger W. Dijkstra于1956年提出的，可用于搜索非負(fù)賦權(quán)圖的單源最短路徑。Dijkstra算法要求每條邊都有一個(gè)非負(fù)的代價(jià)值，算法從起點(diǎn)開始，遍歷圖中每一個(gè)結(jié)點(diǎn)，它從未遍歷的結(jié)點(diǎn)集中選取與當(dāng)前結(jié)點(diǎn)最近的結(jié)點(diǎn)進(jìn)行擴(kuò)展，當(dāng)搜索到目標(biāo)結(jié)點(diǎn)時(shí)結(jié)束，該算法邏輯簡(jiǎn)單，搜索速度快，常作為其他圖算法的子模塊使用，圖8是Dijkstra算法流程圖。

圖8 Dijkstra算法流程圖Fig.8 Flow chart of Dijkstra algorithm

其中， pi表示從起點(diǎn)S到結(jié)點(diǎn)i的最短路徑中，i點(diǎn)的前一個(gè)結(jié)點(diǎn)；dt表示從起點(diǎn)S到結(jié)點(diǎn)t的最短路徑長(zhǎng)度，Count是初始值為1的計(jì)數(shù)器，VNUM為圖的頂點(diǎn)數(shù)量，w(t,m)表示從結(jié)點(diǎn)t到結(jié)點(diǎn)m的路徑長(zhǎng)度。

Dijkstra從起點(diǎn)出發(fā)，搜索最近結(jié)點(diǎn)并逐步向外擴(kuò)展，在機(jī)器人路徑規(guī)劃問題中，終點(diǎn)往往是距離起點(diǎn)最遠(yuǎn)的結(jié)點(diǎn)，當(dāng)結(jié)點(diǎn)規(guī)模較大時(shí)，利用Dijkstra算法尋找最短路徑效率太低，于是結(jié)合賦權(quán)圖結(jié)構(gòu)特點(diǎn)對(duì)Dijkstra算法進(jìn)行改進(jìn)，進(jìn)一步提高本文算法的路徑規(guī)劃效率。為更好地展示賦權(quán)圖特點(diǎn)，將圖7轉(zhuǎn)換為圖9，由于圖9中結(jié)點(diǎn)為平面坐標(biāo)點(diǎn)，各結(jié)點(diǎn)間代價(jià)均為坐標(biāo)點(diǎn)的直線距離，因而符合“三角形兩邊之和大于第三邊”定理，例如 SN1＜ SN15+ N15N1，則圖中結(jié)點(diǎn)N15非最短路徑覆蓋點(diǎn)；同理，N3N10＜ N3N25+ N25N10，N3N10＜ N3N16+ N16N10，則結(jié)點(diǎn)N25與N16非最短路徑覆蓋點(diǎn)。以此類推，圖9中只有結(jié)點(diǎn) N1、N2、N3、N4、N5、N6、N7、N8、N9、N10、N11、N12可能位于最短路徑之上，其余結(jié)點(diǎn)與最短路徑無關(guān)且會(huì)增加算法計(jì)算量，于是對(duì)Dijkstra算法進(jìn)行改進(jìn)，詳細(xì)描述如下：

圖9 非負(fù)賦權(quán)圖結(jié)構(gòu)Fig.9 The structure of non-negative graph with weight

Step1：初始化賦權(quán)圖結(jié)點(diǎn)集合U ={S, N1, N2...Nn-2,G}，集合T=? ，V=? ，W = {q|q ∈ U 且q? V}，結(jié)點(diǎn)P=S；

Step2：利用碰撞檢測(cè)法檢測(cè)結(jié)點(diǎn)P與W中每個(gè)結(jié)點(diǎn)是否可直達(dá)，如可直達(dá)，則將W中對(duì)應(yīng)結(jié)點(diǎn)插入集合T；

Step3：比較T中每個(gè)結(jié)點(diǎn)的障礙物映射角，如小于對(duì)應(yīng)登陸點(diǎn)映射角，則從T中刪除該結(jié)點(diǎn)，同時(shí)刪除U中該結(jié)點(diǎn)；如大于或等于登陸點(diǎn)映射角，則保留；

Step4：計(jì)算結(jié)點(diǎn)P到集合T中所有結(jié)點(diǎn)之間的代價(jià)

St ep5：計(jì)算dS,Tk=dP,Tk=|P-Tk|，同時(shí)將P結(jié)點(diǎn)加入集合V進(jìn)行標(biāo)記；，令P=Tk，T=?。如P是終點(diǎn)G，則算法結(jié)束；否則進(jìn)入Step2。

其中：Tk是集合T中第k個(gè)結(jié)點(diǎn)，dP,Tk是結(jié)點(diǎn)P到Tk的直線距離，n為賦權(quán)圖中所有結(jié)點(diǎn)的個(gè)數(shù)。

3 實(shí)驗(yàn)分析

通過對(duì)比實(shí)驗(yàn)觀察不同算法的路徑規(guī)劃效果。在Windows 10平臺(tái)上利用C#語言開發(fā)一套算法實(shí)驗(yàn)平臺(tái)，如圖10所示。

圖10 算法實(shí)驗(yàn)平臺(tái)Fig.10 Algorithms experiment platform

以路徑長(zhǎng)度和運(yùn)行時(shí)間作為評(píng)價(jià)指標(biāo)，分別在四組100×100的柵格地圖中進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)環(huán)境選取隨機(jī)障礙物分布地圖2組、辦公室走廊區(qū)域地圖1組以及實(shí)驗(yàn)室內(nèi)部地圖1組，通過與傳統(tǒng)A*算法以及JPS算法進(jìn)行對(duì)比，分析本文算法的優(yōu)劣。各算法實(shí)驗(yàn)效果如圖11所示，其中黑色圓形結(jié)點(diǎn)為起點(diǎn)，黑色三角形結(jié)點(diǎn)為終點(diǎn)，黑色柵格為障礙物，淺綠色柵格為A*或JPS算法的擴(kuò)展結(jié)點(diǎn)，紅色柵格為本文算法的擴(kuò)展結(jié)點(diǎn)，紅色折線為最優(yōu)路徑。將三種算法的路徑規(guī)劃數(shù)據(jù)匯總到表1可知，A*算法與JPS算法路徑規(guī)劃距離相同，而本文算法規(guī)劃距離略短，表2對(duì)路徑長(zhǎng)度進(jìn)行了對(duì)比，顯示本文算法比A*算法的路徑長(zhǎng)度縮短了大約2~5個(gè)百分點(diǎn)，這是由于本文算法將擴(kuò)展結(jié)點(diǎn)的連線作為最優(yōu)路徑的一部分，打破了傳統(tǒng)N鄰域擴(kuò)展的角度限制，可規(guī)劃任意角度，因而規(guī)劃路徑的轉(zhuǎn)折次數(shù)更少，路徑更短。表3對(duì)三種算法的運(yùn)行時(shí)間進(jìn)行了比較，可以看到新算法的搜索效率比傳統(tǒng)A*算法有了大幅提升，耗時(shí)約為傳統(tǒng)A*算法的5%~25%，效率提升幅度隨著擴(kuò)展結(jié)點(diǎn)數(shù)量的變化而變化。同時(shí)，本文算法與JPS算法相比，路徑規(guī)劃效率也有提升，在地圖M1、M2和M4中，兩種算法的擴(kuò)展結(jié)點(diǎn)數(shù)量相當(dāng)，耗時(shí)比值約為94%~100%，算法效率提升不明顯，而在地圖M3中，辦公室走廊區(qū)域的障礙物分布集中，所有障礙柵格點(diǎn)共同組成了一個(gè)障礙物塊，使得本文算法擴(kuò)展結(jié)點(diǎn)數(shù)量較少，而JPS算法在障礙物拐點(diǎn)處擴(kuò)展結(jié)點(diǎn)較多，計(jì)算冗余結(jié)點(diǎn)耗費(fèi)了更多時(shí)間，因而本文算法耗時(shí)僅為JPS算法的27.02%，優(yōu)勢(shì)明顯。通過以上數(shù)據(jù)可知，本文算法更適用于障礙柵格點(diǎn)集中或障礙物塊數(shù)量較少的大規(guī)模地圖中。

表1 三種算法運(yùn)行結(jié)果Tab.1 Running results of three algorithms

表2 路徑長(zhǎng)度對(duì)比Tab.2 Comparison of path length

表3 運(yùn)行時(shí)間對(duì)比Tab.3 Comparison of running time

圖11 路徑規(guī)劃結(jié)果Fig.11 Results of path planning

4 結(jié) 論

在移動(dòng)機(jī)器人路徑規(guī)劃過程中，計(jì)算時(shí)間受到地圖規(guī)模的影響較大，實(shí)時(shí)性問題突出。為解決這一問題，本文提出了一種基于障礙物登陸點(diǎn)檢測(cè)的全局路徑規(guī)劃算法，利用障礙物在地圖中的整體分布信息，通過計(jì)算映射角尋找障礙物登陸點(diǎn)，鎖定相關(guān)障礙物的邊緣區(qū)域，有效縮小地圖搜索范圍，再通過改進(jìn)Dijkstra算法優(yōu)化最短路徑搜索過程。最后，以A*算法與JPS算法作為參照進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，本文所提算法可有效提高路徑規(guī)劃效率，尤其是在障礙物比較集中或障礙物塊數(shù)量較少的大規(guī)模地圖中，能更好地解決實(shí)時(shí)性問題。但機(jī)器人不是一個(gè)質(zhì)點(diǎn)，運(yùn)行路線還需考慮其實(shí)際尺寸，下一步還要對(duì)路徑安全性做進(jìn)一步的優(yōu)化。