基于改進A* 算法的智能倉庫移動機器人的路徑規(guī)劃

王海玲*

（廈門大學(xué)嘉庚學(xué)院，福建廈門，363105）

引言

機器人路徑規(guī)劃是滑動機器人研究的熱點問題，可描述為在有障礙物的環(huán)境下，尋找一條從給定起點到指定終點的運行路徑，在整個過程中必須安全、無碰撞地繞過所有障礙物，且盡量使所走路徑最短（或者所花費時間最小、成本最少等）。目前，應(yīng)用于機器人運動規(guī)劃的方法有Dijkstra算法、A*算法等傳統(tǒng)算法及遺傳算法等智能算法。Dijkstra算法可保證搜索到全局最優(yōu)路徑，但是具有一定的盲目性，當節(jié)點增多時，該算法所搜索到的節(jié)點很多，效率低。遺傳算法在尋找全局最優(yōu)解的過程中，是一個隨機搜索的過程，當節(jié)點增多時，搜索時間較長，且易出現(xiàn)早熟的現(xiàn)象。A*算法是一種啟發(fā)式搜索算法，搜索具有一定的方向性，實現(xiàn)簡單，搜索效率高，已被廣泛應(yīng)用，詳見參考文獻[1-5]。顧辰[6]考慮到現(xiàn)實機器人的體積，采用基于優(yōu)先級的子節(jié)點生成策略得到了機器人行走時突遇未知障礙物時路徑規(guī)劃問題，但是并沒有考慮到轉(zhuǎn)彎角度和方向。李偉光等[7]有合轉(zhuǎn)彎因素，采用刪除邊的方法研究了AGV路徑規(guī)劃問題，但是計算實際路徑時還是用直線段代替。王殿君[8]考慮了旋轉(zhuǎn)方向和旋轉(zhuǎn)角度研究了室內(nèi)機器人路徑規(guī)劃問題，但是并沒有減少機器人的路徑長度及轉(zhuǎn)折角度。王紅衛(wèi)等[9]提出了一種平滑 A*算法，減少了不必要的路徑節(jié)點并減少了路徑長度和轉(zhuǎn)折角度，但是只是在原有的路徑點上處理，路徑長度和轉(zhuǎn)折角度減少量有有。孫煒等[10]提出了另一種改進的A*算法，進一步減少滑動機器人總的路徑長度和轉(zhuǎn)折角度，但是沒有進行平滑處理。本文在前面文獻基礎(chǔ)上，通過修改評價函數(shù)，既考慮轉(zhuǎn)彎因素又考慮轉(zhuǎn)折次數(shù)，使得規(guī)劃出的路徑更優(yōu)化、更平滑。

1 系統(tǒng)建模

眾所周知，滑動機器人工作環(huán)境的信息建立是路徑規(guī)劃中十分重要的一步。圖1是智能倉庫系統(tǒng)簡圖（一個方格代表一個貨架，空白箭頭處表示機器人行駛路線）。本文采用棋盤式環(huán)境建模，首先將每一個貨架視為棋盤的一個方格，方格大小一致，將不規(guī)則區(qū)域填充為障礙物，使其成為標準的棋盤。然后以貨架、機器人所在空閑區(qū)域、障礙物為方格，構(gòu)造棋盤如圖2（以11行11列為例）。假設(shè)同一行或同一列的機器人，若他們之間沒有障礙物，則可按原計劃執(zhí)行的線路行走。若突遇障礙物，則會發(fā)生碰撞導(dǎo)致失去原來的行駛路線。于是產(chǎn)生如下問題：（1）突遇障礙物時如何行駛？（2）如何規(guī)劃一條從起點到終點的最優(yōu)路徑？

圖1 智能倉庫簡圖

圖2 棋盤式地圖模型

假設(shè)如下：

（1）S，T分別為起點和終點,i為中間節(jié)點（為障礙物），加粗邊框方格為障礙物所在方格，白色方格為無障礙物方格；

（2）障礙物邊界是在實際邊界的基礎(chǔ)上加一個滑動機器人安全距離得到的，即把機器人看作一個質(zhì)點；

（3）機器人滑動方向的任意的。

本文的目的是找到一條從起點S到終點T的最優(yōu)無碰撞路徑。

2 突遇障礙物時行駛路線規(guī)劃

按原計劃執(zhí)行的線路在i處突遇障礙物，傳統(tǒng)的 A*算法在生成與其相鄰的 8個子節(jié)點時并沒有考慮優(yōu)先行走順序，本文考慮優(yōu)先級的子節(jié)點生成策略，把所有與當前節(jié)點i相鄰的水平、豎直、對角線的8個節(jié)點按照先水平，后豎直，再對角線分為三級（如圖2）。

（1）如A為障礙物節(jié)點，則不生成包含iF，iH的路徑；

（2）如B為障礙物節(jié)點，則不生成包含iE，iG的路徑；

（3）如C為障礙物節(jié)點，則不生成包含iE，iF的路徑；

（4）如D為障礙物節(jié)點，則不生成包含iG，iH的路徑。

在原始計劃S-O-i-T的路徑過程中，若到i為障礙物，認為機器人當前位置i及當前朝下的位置A為

未知障礙物，則根據(jù)子節(jié)點優(yōu)先級，在B處優(yōu)先選擇E，再E到N，依次進行，最后到終點T。

3 轉(zhuǎn)彎因素及轉(zhuǎn)折角度計算

第二部分知道，在i處突遇障礙物，在i的前面B處要迫使機器人改應(yīng)原來的行駛方向，按子節(jié)點優(yōu)先級可行駛至 N，但是在N的前方和右方都遇到障礙物，這時如何行駛？是沿著黑色折線行駛到M還是走弧線到M？如有是沿著弧線行駛，則轉(zhuǎn)彎的角度和旋轉(zhuǎn)方向如何？由于機器人在轉(zhuǎn)彎時要減速并調(diào)整姿態(tài)，在實際運行中，轉(zhuǎn)折次數(shù)的多少、轉(zhuǎn)折角度的大小對規(guī)劃出來的路徑起著至關(guān)重要的作用，為此，引入轉(zhuǎn)彎因子及轉(zhuǎn)折角度等參數(shù)。

在圖2中，令NK、MK與水平線的夾角分別記為α1，α2，MK與 NK的延長線夾角記為θ，由θ的值來判拓展節(jié)點是否發(fā)生轉(zhuǎn)向。

若θ=π，則不轉(zhuǎn)向，按原計劃的線路行駛；

若θ≠π，則發(fā)生轉(zhuǎn)向，存在拐點。把拐點及拐點的父節(jié)點提取出來，這樣就得到只剩起點、拐點、終點的曲線，而且旋轉(zhuǎn)的方向及旋轉(zhuǎn)角度大小可以由θ來決定。

設(shè) N、K、M 的坐標依次為（x1,y1）, （x2,y2）, （x3,y3）,令θ=α1-α2，則

當θ＞0, y3≥y2, y2≥y1時，右轉(zhuǎn)θ；

當θ＞0, y3≤y2, y2≤y1時，右轉(zhuǎn)θ；

當θ＞0, y3≥y2, y2≤y1時，左轉(zhuǎn)180°-θ；

當θ＞0，y3≤y2, y2≥y1時，左轉(zhuǎn)180°-θ；

當θ＜0，y3≥y2, y2≥y1時，左轉(zhuǎn)-θ；

當θ＜0，y3≤y2, y2≤y1時，左轉(zhuǎn)-θ；

當θ＜0，y3≥y2, y2≤y1時，左轉(zhuǎn)180°＋θ；

當θ＜0，y3≤y2, y2≥y1時，左轉(zhuǎn)180°＋θ。

通過計算θ，即可判定在行駛過程中有沒有發(fā)生轉(zhuǎn)彎及轉(zhuǎn)彎的角度大小，進而可以得到一條從起點到終點的考慮旋轉(zhuǎn)方向和角度的最優(yōu)路徑。

4 啟發(fā)函數(shù)的構(gòu)造

A*算法是一種典型的啟發(fā)式搜索算法，它從起始點開始，根據(jù)估計代價選擇價值最低的作為下一個拓展節(jié)點，直到將目標點拓展進來為止，獲得最終最優(yōu)路徑。因此 A*算法的關(guān)鍵在于選擇一個合適的啟發(fā)函數(shù)。傳統(tǒng)的A*算法的啟發(fā)函數(shù)一般為：

其中，f(i)是當前節(jié)點i的估計函數(shù)，g(i)是起點到當前節(jié)點 i的實際費用，這個費用是可以算出來的。h(i)是從當前節(jié)點到終點最小費用的估計，一般采用歐幾里得距離、曼哈頓距離、切比雪夫距離等進行計算，但是實際在選擇最優(yōu)路徑時還受到方向的影響，僅以距離作為約束條件顯示不是最優(yōu)的，為此我們加入方向因素來考慮，現(xiàn)修改啟發(fā)函數(shù)為：

g(i)為修改后的當前節(jié)點的實際費用，若θ=π,則沒有轉(zhuǎn)向；若θ≠π，則發(fā)生轉(zhuǎn)向。l,L分別為當前節(jié)點和起始節(jié)點到終點的歐幾里得距離，l,L比值越接近 1，說明當前接近越接近目標點，α分別為當前節(jié)點與后續(xù)節(jié)點的矢量和起始節(jié)點跟終點的矢量的夾角，θ為上文中的夾角，的比值越接近1，說明選取的節(jié)點路徑方向越接近終點方向。

5 算法流程

（1）初始化設(shè)置，設(shè)O為已拓展列表和C為待拓展列表；

（2）令S∈O，C=φ，檢查O是否為φ，若為φ，則搜索失敗，否則轉(zhuǎn)（3）；

（3）選O中最小的f(.)節(jié)點i作為拓展，從O中刪除，放入C中，并判斷i是否為目標點，若是，則轉(zhuǎn)（5），否則轉(zhuǎn)（4）；

（4）判與i相鄰的節(jié)點j是否在O表中。作如下操作：若在，則判j的當前g值是否比原來小，若是，則把i作為j的父節(jié)點，重新計算j的新的f,g,h；否則，不作任何操作。若不在，則把j添加到O中，并將i作為j的父節(jié)點，計算j的f,g,h值，轉(zhuǎn)（3）；

（5）從 j開始，用回溯法輸出起點到目標點的最優(yōu)路徑。

6 有束語

（1）通過棋盤式的建模方式，構(gòu)建了倉儲的環(huán)境模型；

（2）通過障礙物所在節(jié)點的優(yōu)先級，解決了機器人行走時突遇障礙物的行駛路線問題；

（3）通過考慮旋轉(zhuǎn)方向和旋轉(zhuǎn)角度，引入了新的評價函數(shù)計算方法，使規(guī)劃出的路徑更加合理、更加優(yōu)化。