改進A^*算法在機器人室內路徑規(guī)劃中的應用

陳若男 文聰聰 彭玲 尤承增

摘 要：傳統(tǒng)A*算法在面向機器人室內多U型障礙的特殊場景下規(guī)劃路徑時，容易忽略機器人實際大小，且計算時間較長。針對這個問題，提出一種改進A*算法。首先引入鄰域矩陣進行障礙搜索以提升路徑安全性，然后研究不同類型和尺寸的鄰域矩陣對算法性能的影響，最后結合角度信息和分區(qū)自適應距離信息對啟發(fā)函數(shù)進行改進以提高計算效率。實驗結果表明，改進A*算法可以通過更改障礙搜索矩陣的尺寸來獲得不同的安全間距，以保證不同機器人在不同地圖環(huán)境下的安全性;而且在復雜大環(huán)境中與傳統(tǒng)A*算法相比尋路速度提高了28.07%，搜索范圍縮小了66.55%，提高了機器人在遇到動態(tài)障礙時二次規(guī)劃的靈敏性。

關鍵詞：?A*算法;室內路徑規(guī)劃;移動機器人;啟發(fā)函數(shù)

中圖分類號：TP242.6

文獻標志碼：A

Abstract： For indoor path planning for mobile robot in particular scenario with multiple U-shape obstacles， traditional A* algorithm has some problems such as ignoring the actual size of robot and long computational time. An improved A* algorithm was proposed to solve these problems. Firstly， a neighborhood matrix was introduced to perform obstacle search， improving path safety. Then， the effects of different types and sizes of neighborhood matrices on the performance of the algorithm were studied and summarized. Finally， heuristic function was improved by combining the angle information and the distance information （calculated in different expressions when situation changes） to improve the calculation efficiency. The experimental results show that the proposed algorithm can obtain different safety spacing by changing the size of obstacle search matrix to ensure the safety of different types of robots in different environments. Moreover， in the complex environment， compared with traditional A* algorithm， path planning speed is improved by 28.07%， and search range is narrowed by 66.55%， so as to improve the sensitivity of the secondary planning of robot when encountering dynamic obstacles.

Key words： A* algorithm; indoor path planning; mobile robot; heuristic function

0?引言

這些年，受機器人帶來的影響，人們的生活生產(chǎn)方式發(fā)生了革命性的轉變。機器人產(chǎn)業(yè)在市場需求以及國家政策扶持下，得到了迅速發(fā)展[1]，被廣泛應用到工業(yè)、服務業(yè)、安防，甚至醫(yī)療等領域中，對機器人要求也從原來的單一化和機械化向智能化和人性化的需求轉變[2]，激發(fā)了社會各界人士對機器人的研究興趣。其中，路徑規(guī)劃是機器人智能化的關鍵技術，是指移動機器人按照某一性能指標搜索一條從起始狀態(tài)到目標狀態(tài)的最優(yōu)或次最優(yōu)的無碰撞路徑[3]。

基于柵格法地圖，常用的路徑規(guī)劃算法[4-7]有Dijkstra算法、最佳優(yōu)先算法、啟發(fā)式搜索算法。Dijkstra算法是典型的廣度優(yōu)先算法，優(yōu)點在于總是可以找到最優(yōu)化路徑;但搜索效率低，難以滿足快速規(guī)劃路徑的需求。最佳優(yōu)先算法BFS（Best-First-Search）與Dijkstra算法最大的差異是以與目標節(jié)點之間的距離作為評估，這種算法能夠快速引導向目標節(jié)點搜索，大幅度提高算法搜索效率;但往往不能獲取合理的最短路徑。A*算法[8-10]是結合上述兩種算法優(yōu)勢提出的一種啟發(fā)式搜索算法。它利用啟發(fā)信息來引導搜索方向，從而減小搜索范圍，提高搜索效率。

繼A*算法之后，還有諸多新算法的提出，如D*算法（又稱動態(tài)A*算法）[11]，該算法遇到動態(tài)環(huán)境時無需重新規(guī)劃，但是針對環(huán)境復雜的大區(qū)域地圖，存儲量會激增，且動態(tài)障礙頻繁出現(xiàn)時仍要重新規(guī)劃。還有諸多智能生物算法，如遺傳算法模擬進化論觀點，執(zhí)行效率較高;缺點在于占用存儲空間大，個體編碼方式和初始種群的確定難度高[12-13]。

因此，A*作為經(jīng)典算法，以其實用性至今被廣泛應用，并且對不同場景具有很強的擴展性和適應性。研究學者們針對不同應用場景，作出不同改進。在移動機器人路徑規(guī)劃方面，王殿君[14]解決了傳統(tǒng)A*算法路徑包含過多冗余點的問題，并得到拐點處的最小轉折角度，明確機器人轉向;辛煜等[15]提出無限鄰域的A*算法思想解決了運動方向被限定為π/4的倍數(shù)問題，但搜索速度會降低;顧辰[16]通過采用優(yōu)先級的子節(jié)點生成策略來避免了生成穿過障礙物柵格頂點的路徑，但路徑依然存在較大安全問題;Botea等[17]提出了HPA*（Hierarchical Path-finding A*）算法，該算法通過減少搜索空間來提高速度，但往往不能獲取最優(yōu)路徑;Goldberg等[18]通過提高啟發(fā)函數(shù)的準確度來提高效率，但空間復雜度高;高民東等[19]提出了一種雙向時效A*算法尋找路徑，并采用多近鄰柵格距離計算方案，以達到提高效率、平滑路徑的效果，但不適合大尺寸復雜地圖。

從以上分析可看出，雖然不少研究人員針對A*算法進行了改進，但仍未能很好地解決以下問題：忽略了機器人大小而造成的安全性問題;多U型障礙的室內環(huán)境中算法效率不高的問題。

為解決上述問題，本文主要對傳統(tǒng)A*算法進行兩方面的改進：1）采用鄰域矩陣的方式來進行障礙搜索，以此達到通過選擇矩陣大小來適應機器人實際大小的目的，解決傳統(tǒng)A*算法規(guī)劃路徑過于緊貼障礙物的問題。

2）設計新啟發(fā)函數(shù)，以分區(qū)加權方式來表達距離信息，以叉積距離來表達角度信息，提高大地圖復雜環(huán)境下的算法效率，縮短遇到動態(tài)障礙再次規(guī)劃耗費的時間。

1?環(huán)境模型

路徑規(guī)劃依賴地圖，常見的地圖構建方法有可視圖法、拓撲圖法、柵格法。其中柵格法簡潔有效，易于維護，應用廣泛[20-22]，所以，本文采用柵格法來建立移動機器人工作環(huán)境靜態(tài)二維地圖，以存儲機器人工作環(huán)境的基本情況，并在此基礎上進行全局路徑規(guī)劃工作。通常室內環(huán)境由于被分割成多個相鄰空間，并散落分布家居等障礙物，存在多個U型類障礙。為保證本文算法的可靠性和穩(wěn)定性，將多個U型障礙和簡單矩形障礙拼接，構建了比真實室內場景復雜度更高的模擬環(huán)境，地圖尺寸為600×600像素，如圖1所示。圖1中：深灰色區(qū)域為障礙，淺灰區(qū)域為自由可通行區(qū)域，黑色圓點為起點，白色原點為終點。

2?傳統(tǒng)A*算法

A*算法是一種典型的啟發(fā)式搜索算法，其結合了Dijkstra和BFS兩種算法各自的優(yōu)勢，在保證搜索效率的同時，可以得到最優(yōu)的路徑規(guī)劃[23]。傳統(tǒng)A*算法的核心思想體現(xiàn)在綜合考慮了起始點到當前節(jié)點的真實代價和當前節(jié)點到終點的估計代價，因此可以引導搜索方向。

基本規(guī)劃路徑思路是以起點為第一個計算點，計算其八鄰域中每個節(jié)點的代價值f（n），若某個節(jié)點被占用即為障礙物則不入棧。然后取其中f（n）值最小的節(jié)點作為下一個計算點，并存儲其父節(jié)點，直到搜索到終點，最后從終點追溯其父節(jié)點獲取規(guī)劃路徑。圖2為傳統(tǒng)A*算法尋路的計算過程示例（此處假定障礙物頂點不可穿越）。

在上述計算路徑過程中，忽略了機器人實際大小，將其看作質點，只有障礙物所占用的節(jié)點不可通行，其相鄰節(jié)點均在可通行范圍內，所以最終獲取的路徑將會如圖2所示，緊貼障礙物，此類規(guī)劃路徑不適合機器人運動，容易發(fā)生碰撞。

另外，在評價函數(shù)中，啟發(fā)函數(shù)h（n）對A*算法起主要影響作用：h（n）估值越小，A*算法需要計算的節(jié)點就越多，此時算法效率就會降低，逐步趨近Dijkstra算法;但如果h（n）估值很大，甚至遠大于g（n），此時g（n）的作用便會失效，逐步趨于BFS算法，只追求速度無法獲取合理路徑。因此在設計啟發(fā)函數(shù)時，h（n）和g（n）必須要單位相對一致，保證兩者對f（n）的貢獻相對平等。

本文針對傳統(tǒng)A*算法忽略物體本身大小問題，提出一種面向機器人的障礙鄰域搜索方法。同時，針對室內環(huán)境，構建新的啟發(fā)函數(shù)，提高遇到動態(tài)障礙時再次規(guī)劃的敏銳度。

3?本文算法

3.1?障礙搜索方式的改進

本文提出一種基于鄰域矩陣的障礙搜索方式，在實際應用中，需要根據(jù)機器人自身尺寸及地圖分辨率選擇合適尺寸的搜索矩陣，來確定路徑與障礙物的間距，保證機器人運行過程中的安全問題。

鄰域矩陣搜索對路徑規(guī)劃的影響主要與類型和尺寸有關，本文將通過實驗分析這兩方面對路徑產(chǎn)生的具體影響。

3.1.1?鄰域矩陣類型選擇

本文中鄰域搜索矩陣是指以矩陣中1的個數(shù)命名的。以12鄰域搜索矩陣（S12）為例，判斷當前節(jié)點是否可通行的依據(jù)是：矩陣中心點（3，3）對應當前節(jié)點，此時標識為1的位置對應節(jié)點若均為自由節(jié)點（非障礙），則認為當前節(jié)點可通行;反之認為不可通行。根據(jù)鄰域搜索方向分布可分為十字搜索和米字搜索兩類。兩者的區(qū)別是后者搜索矩陣四個頂點上值也為1。

基于前文構建的地圖環(huán)境，分別對兩類搜索矩陣進行測試，圖3是兩類方法規(guī)劃路徑的對比。表1是兩類方法規(guī)劃效率的對比，以搜索范圍、搜索時間、路徑長度為評價標準。其中搜索范圍是指搜索過程中所涉及計算的節(jié)點柵格總數(shù)，搜索時間是指搜索總過程耗費的時長，路徑長度是指從起點到終點規(guī)劃路徑的柵格節(jié)點總數(shù)。

圖3表明在矩陣大小相同的情況下，兩種搜索方式獲取的路徑與障礙物的最小間隔一致且不影響基本路徑走勢。從定性角度分析，兩種方法的搜索范圍（深灰色區(qū)域）差距不明顯。

表1定量地對比了相同間隔時，不同搜索矩陣類型對算法效率和規(guī)劃路徑的影響。表1中間隔為路徑與障礙物間的空閑節(jié)點數(shù)，根據(jù)實驗對比可知：在三組實驗中，從搜索效率分析只有間隔為1個節(jié)點時，米字搜索范圍比十字搜索少42個節(jié)點，略占優(yōu)勢，但由于米字搜索中每一單元格都比十字多四個節(jié)點的計算量，因此即使搜索范圍較小，耗費的總搜索時間卻依然相對更長。且隨著間隔的擴大，米字搜索對搜索范圍的縮小能力逐漸弱于十字搜索。從路徑角度分析，米字搜索法獲取的路徑始終比十字搜索要長?？偟膩砜?，十字障礙搜索法比米字效率更高，規(guī)劃路徑更優(yōu)，因此采用十字障礙搜索鄰域。

3.1.2?鄰域矩陣大小的選擇

在確定十字障礙搜索法后，需要選取合適鄰域矩陣的大小，矩陣大小決定了障礙物與路徑之間的間隔，對計算效率也有相應影響。圖4為鄰域變化與路徑、障礙間隔大小間的關系。隨著鄰域的增大，規(guī)劃路徑與障礙物的最小間隔增大，如在傳統(tǒng)A*算法中，規(guī)劃路徑緊貼障礙物，即忽略了機器人大小。而利用36鄰域搜索障礙得到的路徑與障礙物間保有明顯的間隔，從而大幅降低了移動機器人在執(zhí)行命令時的碰撞概率。

從另一方面考慮，隨著鄰域的增大，可達到與建圖時“障礙膨脹”相同的效果，所以搜索鄰域越大，認為是不可通行的節(jié)點數(shù)就會增加，相應地減少了需要計算的節(jié)點，總體上會提高規(guī)劃速度。與此同時，為了遠繞障礙，規(guī)劃的路徑長度會有所增加。圖5量化了路徑長度、搜索時間與鄰域變化的關系，可看出鄰域增大對算法確實有雙向影響，一方面提高搜索效率，但另一方面卻會使路徑長度增加。

在應用中，需要結合機器人的尺寸以及室內地圖的分辨率，計算出安全間隔對應的柵格數(shù)，然后選擇一個能滿足安全性前提且路徑較短的鄰域矩陣。

由于障礙搜索的改進方式側重路徑的安全性與最優(yōu)性，效率的提升是下一步啟發(fā)函數(shù)的側重點，所以在選擇矩陣時，路徑長度短比搜索時間短優(yōu)先級高。

3.2?啟發(fā)函數(shù)的改進

結合距離信息和角度信息本文設計的新啟發(fā)函數(shù)如下：

3.2.1?距離信息表達

常用的距離估算方式有曼哈頓距離、切比雪夫距離、歐幾里得距離。曼哈頓距離是標準A*的啟發(fā)函數(shù)，以X、Y方向上的距離差的絕對值之和作為估計距離，意味著只允許向上下左右四個格網(wǎng)運動;切比雪夫距離取X、Y方向距離差中較大的為距離估算值，即允許對角線運動，且對角線運動和水平垂直運動的代價一致;歐幾里得距離則是最常見的兩點一線距離計算方式，可用于沿任意角度移動的情況，其比前兩種距離都短，在有障礙的情況下這種計算方式和實際距離會有較大差距。因為歐幾里得距離和切比雪夫距離在障礙復雜環(huán)境下與真實代價的偏差較大，所以本文選擇在多障礙環(huán)境下距離估計更準的曼哈頓距離更為合適。

為避免鄰域中代價相同而造成的路徑不確定性和抖動現(xiàn)象，將坐標差加權后再求和。通過設置十組權值比{1∶9， 2∶8，…，9∶1}進行路徑搜索，最后確定權值比6∶10效率最高，即p=6，q=10。

而分區(qū)加權是為了起到一定的方向引導作用。分區(qū)加權對引導作用的體現(xiàn)如圖6所示，以終點為坐標原點，以X=Y作為分割線，左下方區(qū)域中當前點到終點在X方向距離差大于在Y方向距離差，此時定義Y1的權重為大系數(shù)，由于在選擇計算點時優(yōu)先選擇代價小的節(jié)點，故將會引導搜索方向朝Y1小的方向前進（箭頭標識），同理分割線右上方的區(qū)域則會朝X1小的方向前進（箭頭標識），從而引導搜索方向朝起止最短連線靠近。分析起止線左偏的情況同樣適用。

3.2.2?角度信息表達

在式（3）中還加入了角度信息，它是兩個向量叉積結果的模，這兩個向量分別是起點到終點的向量和當前點到終點的向量。

其中：角度信息表達cross是依據(jù)叉積計算獲取的;通常情況下起止點距離|AB|是常量;而|CD|是隨著兩向量夾角變化而變化的量，當兩者平行時|CD|達最小值，當兩者垂直時|CD|達最大值，它很好地以距離的形式反映了兩者間的角度關系。

因此，在啟發(fā)函數(shù)中加入角度信息變量cross可誘導A*算法偏向拓展分布在起始點到目標點連線附近的節(jié)點。

此外，因為cross的量綱是距離的平方，前文提及過，g（n）和h（n）必須要保持量綱平衡，不然可能會導致g（n）或h（n）的失效。本該對cross作開方然后疊加到h（n）中，考慮到開方對計算機而言是高復雜度的計算方式，所以選擇乘上系數(shù)m來達到近似開方的效果。m*cross=cross，即m=1/cross 本文實驗地圖為600×600像素， 故本文實驗crossmax=360000經(jīng)計算預估m(xù)≈0.0017。由于m是遞減函數(shù)，隨著L增大而縮小。且cross最大值位于100000～1000000，根據(jù)單調遞減函數(shù)特性，可知對應m閾值為[0.001，0.003]。

但由于式（3）中距離信息中進行了加權操作，為了保持角度信息和距離信息貢獻量一致，取距離權值6，10的平均值8對角度信息進行操作，即w=8*m。故w預估值為0.0136，閾值為[0.008，0.024]。通過二分法，進行實驗，最終確定w為0.014，與預估值相近。

4?實驗與結果分析

為了驗證本文算法的可行性和有效性，基于Matlab2017a環(huán)境進行仿真實驗。將本文算法與傳統(tǒng)A*算法、雙向時效A*算法[19]以及提升安全性的文獻[16]算法進行對比，分析定性和定量結果。實驗中本文算法的障礙搜索方式采用12鄰域十字搜索矩陣（S12）。

圖8是本文算法與傳統(tǒng)A*算法路徑效果的定性對比：傳統(tǒng)A*算法路徑緊貼障礙物，規(guī)劃搜索范圍大;改進其障礙搜索方式后，路徑與障礙物間有了安全間隔（淺灰色區(qū)域），且搜索范圍（深灰色區(qū)域）有所縮減，主要縮減量體現(xiàn)在靠近障礙物的區(qū)域。在此基礎上，進一步改良啟發(fā)函數(shù)后獲取的路徑，在無障時基本走兩點間最短直線，在遇障時以小短折線形式繞過障礙，與原先隨機轉向相比，更加契合人類思維。與此同時，發(fā)現(xiàn)搜索范圍明顯縮小了，表明新啟發(fā)函數(shù)的導向能力更強。

表2是算法改進前后規(guī)劃效率的定量對比。與傳統(tǒng)A*算法相比，本文路徑長度增加了6.63%，這主要消耗在保證路徑安全性上（增加了6.16%），是為了避開障礙物才產(chǎn)生的路徑長度增加效應。除此項性能降低外，搜索柵格范圍縮小66.55%，體現(xiàn)了本文算法搜索方向聚攏效果增強;操作總次數(shù)減少了37.93%，體現(xiàn)出搜索方向的引導效果好，減少了需要比較計算的節(jié)點數(shù);搜索耗費時間降低了28.07%。

本文算法最大的特點是保證了路徑安全性，目前A*優(yōu)化算法中少有研究考慮路徑安全性問題，而這對機器人導航來說這至關重要。

文獻[16]提出了一種采用優(yōu)先級的子節(jié)點生成策略來避免路徑穿過障礙物柵格頂點，效果如圖9（b）所示。該算法得到的路徑所在柵格依然與障礙物為相鄰單元格，并無間隔。

在實際應用中，真實地圖的分辨率往往遠小于機器人的實際體積，因此依然存在很大的安全隱患。且文獻[16]提出的優(yōu)先級策略從一定程度上加大了一些計算量：當前點N的上下左右為一級節(jié)點，對角線為二級節(jié)點。二級節(jié)點是否擴展除了要判斷其自身是否為障礙物外，還需要考慮相鄰一級節(jié)點是否為障礙物。

而本文算法不僅能夠保證路徑整體與障礙物間有空閑單元格（如圖9（c）），還減少了算法的擴展節(jié)點。此外，間格的多少可以通過改變障礙鄰域搜索矩陣大小來控制。因此可以滿足不同機器人尺寸和不同柵格地圖分辨率的應用需求。

此外，本文算法的效率在復雜大地圖環(huán)境下有一定的優(yōu)勢。文獻[19]提出了一種雙向時效A*算法，并采用多近鄰柵格距離計算方案，以達到提高效率、平滑路徑的效果。表3是雙向時效A*算法和本文算法分別與傳統(tǒng)A*算法效率對比的結果。文獻[19]中設立了5個實驗場景（表3中的實驗1～5），分析表3可知該算法相對傳統(tǒng)A*算法，計算效率顯著提高，但也有一定的局限性。首先對比實驗1～3，發(fā)現(xiàn)該算法對橢圓障礙的搜索效率遠大于對矩形障礙。對比實驗3和4，發(fā)現(xiàn)隨著地圖尺寸增大，算法效率提升效果降低。說明該算法的高效率特性需要建立在一定的前提下，對障礙類型和地圖尺寸有一定的要求。

在實驗5中，以大地圖和中等復雜程度的障礙物為實驗環(huán)境，文獻[19]算法計算速度比傳統(tǒng)A*算法提高36.11%。

而本文以600×600的大地圖和高復雜程度的障礙為實驗環(huán)境（圖8），較傳統(tǒng)A*算法，效率提高28.07%。因此，而文獻[19]算法在簡單小地圖環(huán)境里表現(xiàn)突出，而本文算法更合適復雜大地圖的應用場景。

綜合評價，本文算法雖然在路徑長度上有所犧牲，但保證了路徑的安全性，能夠在一定程度上避免機器人運行過程中發(fā)生碰撞;與此同時，算法的效率得到了提升，適用于室內多U型障礙的應用場景，使得機器人在遇到動態(tài)障礙時再次規(guī)劃實時性更好。

5?結語

本文針對傳統(tǒng)A*算法在室內機器人路徑規(guī)劃應用中的問題進行改進：首先，采用十字多鄰域矩陣搜索障礙解決原先忽略機器人大小造成的安全性問題;然后，設計新啟發(fā)函數(shù)，引入分區(qū)加權距離信息和角度信息，提高復雜多U型障礙的室內環(huán)境下的搜索效率，以縮短遇到動態(tài)障礙再次規(guī)劃所耗費的時間。

仿真實驗結果表明：本文算法可通過選擇不同尺寸的搜索矩陣來自定義路徑與障礙物的間距，方便地解決了不同尺寸機器人安全路徑的問題;且在復雜大環(huán)境下計算效率得到提高，使得遇到動態(tài)障礙時再次規(guī)劃的靈敏度提升。下一步工作將會考慮刪除路徑中的冗余節(jié)點，以進一步提高機器人運行效率。

參考文獻（References）

[1] 王麗蘋. 機器人技術變遷及產(chǎn)業(yè)發(fā)展戰(zhàn)略研究[D]. 天津， 天津大學， 2016： 1. （WANG L P. The study of development strategy and technological change of robot industry [D]. Tianjin： Tianjin University， 2016： 1.）

[2] 康凱. 基于機器視覺的移動機器人定位與三維地圖重建方法研究[D]. 哈爾濱： 哈爾濱工業(yè)大學， 2017： 1-2. （KANG K. Research on localization and mapping of mobile robot based on machine vision [D]. Harbin： Harbin Institute of Technology， 2017： 1-2.）

[3] JEDDISARAVI K， ALOTAPPEH R J， PIMEMTA L C A， et al. Multi-objective approach for robot motion planning in search tasks [J]. Applied Intelligence， 2016， 45（2）： 305-321.

[4] 彭利民. 基于廣度優(yōu)先搜索的虛擬網(wǎng)絡映射算法[J]. 四川大學學報（工程科學版）， 2015， 47（2）： 117-122. （PENG L M. Virtual network embedding algorithm based on breadth-first search [J]. Journal of Sichuan University （Engineering Science Edition）， 2015， 47（2）： 117-122.）

[5] 劉艷麗， 樊曉平， 張恒. 基于啟發(fā)式搜索的移動機器人主動定位[J]. 機器人， 2012， 34（5）： 590-595. （LIU Y L， FAN X P， ZHANG H. Heuristic search assisted active localization for mobile robot [J]. Robot， 2012， 34（5）： 590-595.）

[6] 房佳， 杜震洪， 張豐， 等. 應用于城市道路網(wǎng)的啟發(fā)式深度優(yōu)先有向搜索算法[J]. 浙江大學學報（理學版）， 2013， 40（4）： 469-474. （FANG J， DU Z H， ZHANG F， et al. Heuristic depth-first directional algorithm for shortest path searching in traffic networks[J]. Journal of Zhejiang University （Science Edition）， 2013， 40（4）： 469-474.）

[7] BURNS E， LEMONS S， ZHOU R， et al. Best-first heuristic search for multi-core machines [J]. Journal of Artificial Intelligence Research， 2010， 39（1）： 689-743.

[8] FRANTISEK D， ANDREJ B. Path planning with modified a star algorithm for a mobile robot [J]. Procardia Engineering， 2014， 96（1）： 59-69.

[9] UTTENDORF S， EILERT B， OVERMEYER L. Combining a fuzzy inference system with an A* algorithm for the automated generation of roadmaps for automated guided vehicles [J]. at-Automatisierungstechnik， 2017， 65（3）： 189-197.

[10] WODZINSKI M， KRZYZANOWSKA A. Sequential classification of palm gestures based on A* algorithm and MLP neural network for quadrocopter control [J]. Metrology and Measurement Systems， 2017， 24（2）： 265-276.

[11] 張曉冉， 居鶴華. 采用改進D*Lite算法的自主移動機器人路徑規(guī)劃[J]. 計算機測量與控制， 2011， 19（1）： 155-157. （ZHANG X R， JU H H. Developed D* Lite algorithm for path planning of autonomous mobile robots [J]. Computer Measurement & Control， 2011， 19（1）： 155-157.）

[12] 徐美清， 孫晨亮. 基于柵格地圖的遺傳算法路徑規(guī)劃[J]. 科技信息， 2011（31）： 76-77. （XU M Q， SUN C L. The occupancy grid map-building with neural network [J]. Science & Technology Information， 2011（31）： 76-77.）

[13] 李天旭， 陳廣大.基于改進遺傳算法的室內移動機器人路徑規(guī)劃[J]. 制造業(yè)自動化， 2015， 37（20）： 31-35. （LI T X， CHEN G D. Indoor mobile robot path planning based on improved genetic algorithm [J]. Manufacturing Automation， 2015， 37（20）： 31-35.）

[14] 王殿君. 基于改進A*算法的室內移動機器人路徑規(guī)劃[J]. 清華大學學報（自然科學版）， 2012， 52（8）： 1085-1089. （WANG D J. Indoor mobile-robot path planning based on an improved A* algorithm [J]. Journal of Tsinghua University （Science and Technology）， 2012， 52（8）： 1085-1089.）

[15] 辛煜， 梁華為， 杜明博， 等. 一種可搜索無限個鄰域的改進A*算法 [J]. 機器人， 2014， 36（5）： 627-633. （XIN Y， LIANG H W， DU M B， et al. An improved A* algorithm for searching infinite neighborhoods [J]. Robot， 2014， 36（5）： 627-633.）

[16] 顧辰.改進的A*算法在機器人路徑規(guī)劃中的應用[J]. 電子設計工程， 2014， 22（19）： 96-98， 102. （GU C. Application of improved A* algorithm in robot path planning [J]. Electronic Design Engineering， 2014， 22（19）： 96-98， 102.）

[17] BOTEA A， MULLER M， SCHAEFFER J. Near optimal hierarchical path-finding [J]. Journal of Game Development， 2004， 1（1）： 7-28.

[18] GOLDBERG A V， HARRELSON C. Computing the shortest path： A*search meets graph theory[C]// Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms. New York： ACM， 2005： 156-165.

[19] 高民東， 張雅妮， 朱凌云. 應用于機器人路徑規(guī)劃的雙向時效A*算法[J]. 計算機應用研究， 2019， 36（3）： 792-795，800. （GAO M D， ZHANG Y N， ZHU L Y. Bidirectional time-efficient A* algorithm for robot path planning [J]. Application Research of Computers， 2019， 36（3）： 792-795，800.）

[20] 余翀， 邱其文. 基于柵格地圖的分層式機器人路徑規(guī)劃算法[J]. 中國科學院大學學報， 2013， 30（4）： 528-538， 546. （YU C， QIU Q W. Hierarchical robot path planning algorithm based on grid map [J]. Journal of University of Chinese Academy of Sciences， 2013， 30（4）： 528-538， 546.）

[21] 程向紅， 祁藝. 基于柵格法的室內指示路徑規(guī)劃算法[J]. 中國慣性技術學報， 2018， 26（2）： 236-240， 267. （CHENG X H， QI Y. Indoor indicator path planning algorithm based on grid method[J]. Journal of Chinese Inertial Technology， 2018， 26（2）： 236-240， 267.）

[22] 朱愛斌， 劉洋洋， 何大勇， 等. 解決路徑規(guī)劃局部極小問題的勢場柵格法[J]. 機械設計與研究， 2017， 33（5）： 46-50. （ZHU A B， LIU Y Y， HE D Y， et al. An improved potential field-grid method for local minimization problem in path planning [J]. Machine Design and Research， 2017， 33（5）： 46-50.）

[23] PETER E， NILSSON J， RAHEAL B. A formal basis for the heuristic determination of minimum cost paths [J]. ACM SIGART Bulletin， 1972， 4（37）： 28-29.