基于方向A*算法的溫室機器人實時路徑規(guī)劃

張 文 劉 勇 張超凡 張 龍 夏營威

(1．中國科學院合肥物質(zhì)科學研究院應用技術研究所，合肥230031;2．中國科學技術大學，合肥230026)

基于方向A*算法的溫室機器人實時路徑規(guī)劃

張 文1，2劉 勇1張超凡1，2張 龍1夏營威1

(1．中國科學院合肥物質(zhì)科學研究院應用技術研究所，合肥230031;2．中國科學技術大學，合肥230026)

針對復雜環(huán)境下的溫室機器人路徑規(guī)劃問題，重點研究了生成路徑的平滑設計、碰撞檢測和算法實時性，提出一種方向A*算法。首先采用“視野線”平滑原則優(yōu)化路徑，消除鋸齒效應并避免部分碰撞;其次應用“圓弧—直線—圓弧”轉(zhuǎn)彎策略，避免機器人本體寬度影響;最后基于二叉堆加速算法，提升算法計算效率。仿真實驗結(jié)果表明，方向A*算法滿足平滑要求且能有效避免碰撞，加速算法平均提速4～7倍。同時，機器人在真實實驗環(huán)境下能實現(xiàn)安全自主導航，跟蹤誤差小于0.15m，驗證了所提方法的可行性。

溫室機器人;路徑規(guī)劃;方向A*算法;二叉堆

引言

路徑規(guī)劃是溫室機器人實現(xiàn)自主導航的核心問題，指在具有障礙物的環(huán)境下，按照一定的評價標準，搜索一條從起始狀態(tài)(位置和姿態(tài))到目標狀態(tài)的最優(yōu)或次優(yōu)的安全無碰撞路徑［1－3］。根據(jù)環(huán)境感知信息的不同程度，目前路徑規(guī)劃方法主要分為兩類:一是基于已知環(huán)境信息的全局路徑規(guī)劃方法(人工勢場法［4］、柵格法［5］、A*算法);二是基于實時傳感器數(shù)據(jù)的局部路徑規(guī)劃方法(D*算法［6］、遺傳算法［7］、蟻群算法［8］)。

A*算法是一種基于啟發(fā)式函數(shù)的全局路徑規(guī)劃方法，適用于二次規(guī)劃［9］。但傳統(tǒng)A*算法忽略了動態(tài)環(huán)境變化和機器人本體信息，易舍棄部分點而生成次優(yōu)結(jié)果，造成拐點多、路徑長，不利于運動控制及路徑跟蹤［10］。BOISSONNAT等［11］最早采用直線—圓弧平滑算法消除跳變，路徑在一定程度上得到平滑。TROCATO等［12］利用微分改進A*算法，大大減少轉(zhuǎn)折次數(shù)，然而由于涉及大量數(shù)學計算及推導，未能兼顧算法實時性。王殿君［13］基于柵格編碼信息，動態(tài)獲取旋轉(zhuǎn)方向及角度，但未考慮未知障礙物信息和機器人本體寬度。

本文在分析傳統(tǒng)A*算法的基礎上，重點研究生成路徑的平滑設計、碰撞檢測和算法實時性，提出一種方向A*算法，并應用于中國科學院貝貝機器人本體，旨在實現(xiàn)復雜溫室環(huán)境下的自主導航功能。

1 基于方向A*算法的路徑規(guī)劃

本文提出的方向A*算法主要涉及A*算法的后處理方法，首先對生成路徑進行“視野線”平滑，在消除鋸齒效應的同時兼顧碰撞問題;其次應用“圓弧—直線—圓弧”轉(zhuǎn)彎策略，避免機器人本體寬度影響;最后基于二叉堆提高數(shù)據(jù)交互效率，以滿足機器人實時計算要求。

1.1 傳統(tǒng)A*算法分析

傳統(tǒng)A*算法結(jié)合BFS算法和Dijkstra算法的優(yōu)點，通過定義估價函數(shù)來評估代價而確定最優(yōu)路徑。估價函數(shù)為

式中 n——待擴展的節(jié)點

g(n)——起始點到當前節(jié)點的實際代價值

h(n)——當前點到目標點的估計代價值，即啟發(fā)函數(shù)

f(n)——從起始點經(jīng)過節(jié)點n到達目標點的最優(yōu)代價解的估計代價［14－15］

A*算法的基本思想是通過設置合適的啟發(fā)函數(shù)，全面評估各擴展搜索節(jié)點的代價值，通過比較各擴展節(jié)點的代價值，選取代價最小節(jié)點加以擴展，直至到達目標點。針對柵格化環(huán)境地圖的路徑搜索，一般選用曼哈頓距離或歐幾里得距離作為啟發(fā)函數(shù)［16］。

1.2 “視野線”平滑準則

由于傳統(tǒng)A*算法依據(jù)8鄰域搜索節(jié)點，必然會產(chǎn)生鋸齒效應，造成路徑折線長、拐點多(圖1a)。常規(guī)平滑算法常在轉(zhuǎn)彎時采取懲罰機制，會減少部分拐點(圖1b)，但依然會存在45°斜坡，欠平滑且導航耗時。

圖1 不同方法下的鋸齒效果對比圖Fig．1 Contrast of zigzag images after differentmethods

為獲取圖1c中的最優(yōu)路徑，提出一種“視野線”平滑算法:對當前節(jié)點，視野范圍所能到達的最遠節(jié)點直接連通并舍棄中間節(jié)點，依此繼續(xù)分析直至掃描路徑結(jié)束。具體實施步驟如下:

(1)傳統(tǒng)A*算法處理后，沿生成路徑依次分析各節(jié)點。

(2)路徑起始點為startpos，startpos－＞next為currentpos。

(3)如果currentpos的子節(jié)點存在，則繼續(xù)，否則跳至步驟(7)。

(4)GoThrough(startpos，currentpos－＞next)得返回值，若為真值則繼續(xù)，否則跳至步驟(6)。

(5)將currentpos賦值為currentpos－＞next并刪除currentpos之前指向的節(jié)點，跳至步驟(3)。

(6)startpos賦值為 currentpos，currentpos賦值為currentpos－＞next，跳至步驟(3)。

(7)路徑平滑結(jié)束。

其中，函數(shù)GoThrough(posA，posB)在posA和posB之間按照固定間隔(通常1/5柵格長度)采樣，依次檢查各樣本點:機器人以當前點為質(zhì)心，1/2機器人寬為探索范圍，判斷其4鄰域是否碰撞障礙柵格，若沒有則返回真值，反之為假。根據(jù)“視野線”平滑路徑后，圖1a中多余的紅圈拐點予以消除，得到圖1c所示路徑。

1.3 “圓弧—直線—圓弧”轉(zhuǎn)彎策略

1.3.1 增加合理的轉(zhuǎn)彎

“視野線”平滑準則固然能優(yōu)化路徑，但當機器人本體過大或遭遇拐點柵格時，往往無法通過。因此，本文將引入合理的轉(zhuǎn)彎方法，避免突然變向和碰撞，這種思想最早用于處理游戲地圖中的人工智能問題。

首先，應理解轉(zhuǎn)彎半徑概念。假如機器人向右后行駛時，一般主動輪會先向右或向左旋轉(zhuǎn)到限制位，行進時將產(chǎn)生一段圓弧，此圓的半徑即轉(zhuǎn)彎半徑。倘若機器人處于圖2的某起始點(Origin)并具有方向，需前行至目標點(Destination)，最短路徑有且僅有2種(圖2綠線部分):按轉(zhuǎn)彎半徑右轉(zhuǎn)，直到“視野線”看到目標點，然后繼續(xù)前進;同理得左轉(zhuǎn)方式。

圖2 兩種最短路徑規(guī)劃圖Fig．2 Planning image of two shortest paths

圖3 右轉(zhuǎn)路徑長度計算示意圖Fig．3 Schematic diagram of calculating length of right turn path

為計算路徑長度，將右轉(zhuǎn)路線表示為圖3，并根據(jù)幾何關系說明。圖3中，r為轉(zhuǎn)彎半徑，P為轉(zhuǎn)彎時的圓心。若起始點按圖示方向右轉(zhuǎn)，P的方向和位置為

式中 dP——P相對于起始點的方向角

dO——起始點的方向角

xP、yP——點P的橫坐標和縱坐標

xO、yO——起始點的橫坐標和縱坐標

然后計算點P到目標點的距離

式中 dx——點P和目標點橫坐標之間的差值

dy——點P和目標點縱坐標之間的差值

xD、yD——起始點的橫坐標和縱坐標

l——點P和目標點的距離

判斷l(xiāng)與半徑r的大小，若l小于半徑r，則目標點在圓內(nèi)，永遠無法到達。Q為離開圓弧開始直線距離的點，根據(jù)三角關系，可以獲取Q到目標點的距離及l(fā)和r的夾角

式中 d——Q到目標點的距離

θ——l與r的夾角

最后，計算點Q的方向和位置

xQ、yQ——點Q的橫坐標和縱坐標

同理，左轉(zhuǎn)路線可依此計算，但有2處區(qū)別:一是P的方向加上90°，二是計算點Q坐標時，用θ－取代。計算完成后，比較2種轉(zhuǎn)彎方式路徑長度，短的路徑即最終選取路徑。

1.3.2 “圓弧—直線—圓弧”策略

應用方向A*算法規(guī)劃最短路徑時，僅已知起始點方向、位置和轉(zhuǎn)彎半徑顯然不足，為防止碰撞及獲取下次起始點的方向，還需考慮到達目標點時的方向。因此，擴展上述轉(zhuǎn)彎方法，提出一種“圓弧—直線—圓弧”轉(zhuǎn)彎策略。

增加確定的到達方向后，出現(xiàn)圖4中4種可能的路徑方式。可以看出，到達目標點時，也有類似出發(fā)點一樣的圓弧來保證方向的正確性。此時，各路徑方案中都有固定的3段:第1段圓弧、中間直線段和第2段圓弧，故為“圓弧—直線—圓弧”策略。

圖4 具有固定方向的4種轉(zhuǎn)彎路徑Fig．4 Four turning pathswith a fixed direction

對于圖4的情況，采取類似圖3同樣的計算方法能夠較易得到起始點和目標點的位置，但關鍵是如何獲取離開第1段圓弧和到達第2段圓弧時各點的方位和角度。一般，需考慮兩種情況。第1種是離開起始點和到達目標點轉(zhuǎn)彎時，繞圓心旋轉(zhuǎn)在同一方向，例如圖5中都是順時針方向。此時，P1到P2的藍色連線與其正下方的綠線具有相同的長度和斜率，可以得到

式中 lP1P2——點P1到P2的距離

lAB——點A到點B的距離

kP1P2——直線P1P2的斜率

kAB——直線AB的斜率

θarc1——離開第1段圓弧時的角度

θarc2——到達第2段圓弧時的角度

圖5 路徑搜索時以相同方向轉(zhuǎn)彎示意圖Fig．5 Traveling around both circles in the same direction

第2種是離開起始點和到達目標點轉(zhuǎn)彎時，方向是相對的，例如圖6中離開是順時針方向，到達是逆時針方向。為簡化計算，相對目標圓作相同圓(圓心P3)與其正切于點B，此時第3圓與起始圓的關系就演變成第1種情況。在△P1P2P3中，可得

式中 lP2P3——點P2到P3的距離

θ1——P2P3與P2P1的夾角

圖6 路徑搜索時以相對方向轉(zhuǎn)彎示意圖Fig．6 Traveling around both circles in opposite direction

θAB——直線AB與x坐標軸夾角至此，可以獲取離開第1段弧和到達第2段弧的角度。

綜上所述，對于已知位置和方向的起始點和目標點，能夠?qū)崟r計算4種可能路徑來獲取最短路徑，并避免機器人本體寬度造成的碰撞。同時，可以獲取當前路徑中任意時刻的位置和方向。

1.4 方向A*平滑算法

為平滑路徑、避免碰撞，本文在上述基礎上擴展為更為復雜的方向A*算法。首先，在傳統(tǒng)的二維柵格地圖基礎上增加方向維度，使得地圖中的各節(jié)點具有潛在的8個羅盤方向(N、S、E、W、NE、NW、SE、SW)，例如某節(jié)點可表示為［X=45，Y=65，Orientation=SE］。同時“視野線”準則中搜索判斷函數(shù)將擴展為 GoThrough(posA，directionA，posB，directionB)，給定相應的起始和最終方向。另外，對相應的數(shù)據(jù)結(jié)構和改進的啟發(fā)函數(shù)作出說明:

(1)算法的數(shù)據(jù)結(jié)構:轉(zhuǎn)彎策略使用的結(jié)構體LineSegment將包含3種離散線段，即1.3.2節(jié)中提到的第1段圓弧、中間直線段和第2段圓弧，結(jié)構體包含3個成員變量，分別為圓弧標志位、線段長度及起始位置坐標。如果線段是直線，則記錄角度;如果線段是圓弧，則記錄轉(zhuǎn)彎圓的圓心、圓弧所包含的弧度、圓弧開始角度或結(jié)束角度。

(2)改進的啟發(fā)函數(shù):傳統(tǒng)A*算法中采用曼哈頓距離作為啟發(fā)函數(shù)，易造成目標點各方向權值相同而增加搜索時間。因此，采用1.3節(jié)中所述的最短曲線路徑來替換，從而保證目標方向的權值最大化。

方向A*算法仍以“視野線”平滑步驟順序進行，在步驟(4)時，首先基于改進的啟發(fā)函數(shù)嘗試“圓弧—直線—圓弧”轉(zhuǎn)彎策略的曲線路徑，如果成功則用擴展的GoThrough函數(shù)檢測是否覆蓋障礙柵格，繼續(xù)1.2節(jié)中步驟(5)～(7)直至平滑結(jié)束，最終獲取避免碰撞的最短平滑路徑。

1.5 基于二叉堆的加速方法

方向A*算法一般以8鄰域搜索，圖7中，如果轉(zhuǎn)彎半徑過大，不可能在獲取a→b→c→d路徑的同時不碰到障礙柵格，唯一的方法是獲得a→d的直接路徑。所以，必須擴大搜索范圍，采用24鄰域方向A*算法甚至48鄰域。這種擴展方法伴隨的最大問題是耗時，為此本文將采用一種基于二叉堆的加速方法。

方向A*算法中，在OpenList里搜尋式(1)中擁有最小F值的節(jié)點是延緩算法效率的最大問題之一。因此，OpenList中數(shù)據(jù)的存儲方式將直接影響算法速度。二叉堆是完全二叉樹，其最小堆的堆序性始終維持根節(jié)點最小，從而保證本文算法搜索F值的時間復雜度為O(1)［17］。

圖7 8鄰域方向A*算法無法識別的路徑Fig．7 Legal curved path which cannot be found by directional-8 algorithm

一個合格的二叉堆如圖8a所示，為省去指針問題，將其簡化成圖8b中的一維數(shù)組。根節(jié)點位置為1(位置0用于標記)，第n個節(jié)點的子節(jié)點的位置分別為2n+1和2n+2。添加新節(jié)點(位置為m)時將其置于數(shù)組末端，然后與父節(jié)點(位置為(m－1)/2)比較，若小則交換，直至父節(jié)點不再比它大或已到達位置1。刪除數(shù)組第1個節(jié)點，然后把最后一個位置的節(jié)點置頂，依次與子節(jié)點比較直至滿足關系。相較傳統(tǒng)排序算法的O(n)時間復雜度，上述操作壓縮為O(lgn)。

圖8 二叉堆結(jié)構及數(shù)組形式Fig．8 Structures of binary heap and its array form

對于固定尺寸的柵格地圖(假設長m、寬n)，方向A*算法所需的二叉堆數(shù)組OpenList長度最大為m×n，最小節(jié)點為OpenList［1］。該數(shù)組存儲了掃描節(jié)點的F值，但并未給出當前柵格的地圖坐標。為此，用下述方法改進:①每次掃描后，增加nodeChecked變量，存入OpenList數(shù)組。②將真實F值存入相同大小的Fcost數(shù)組，nodeChecked為數(shù)組編號。③當前掃描節(jié)點的坐標值分別用相同大小的openX和openY數(shù)組記錄。

圖9為更改后的存儲結(jié)構。

圖9 改進的二叉堆結(jié)構Fig．9 Structure of improved binary heap

當需要添加新的節(jié)點到OpenList中時，計算該點F值，遞增NodeChecked和num of OpenList變量，并將已更改的 NodeChecked賦值給數(shù)組 OpenList (num of OpenList)。然后與其父親節(jié)點比較Fcost (OpenList())值，若較大則上濾結(jié)束，否則交換位置并繼續(xù)類似比較，直到上濾至合適位置或位置1。

當路徑優(yōu)化到已經(jīng)搜索的節(jié)點時，需要刪除最小 F值節(jié)點并加入到 CloseList中。將 OpenList (num of OpenList)賦值給OpenList(1)，變量num of OpenList遞減。然后與其 2個子節(jié)點比較 Fcost (OpenList())值，若其值最小則下濾結(jié)束，否則與較小子節(jié)點交換位置，繼續(xù)與新子節(jié)點比較直至循環(huán)結(jié)束。

2 仿真

本文所述算法在計算機(Intel Core i5-4200U處理器，4.00GB RAM)Ubuntu14.04操作系統(tǒng)環(huán)境下，基于ROS框架的Stage仿真環(huán)境中編程實現(xiàn)。假設單元柵格為邊長1m，地圖尺寸為20m×20m，機器人本體最大半徑為0.4 m，轉(zhuǎn)彎半徑為0.5 m，碰撞檢測間隔為0.2 m。模擬規(guī)劃時，起點坐標為(6，15)，終點坐標為(3，17)。

2.1 傳統(tǒng)A*算法與方向A*算法性能對比

在模擬地圖中，分別使用傳統(tǒng)A*算法、“視野線”平滑算法、8鄰域方向A*算法和24鄰域方向A*算法進行路徑規(guī)劃，優(yōu)化效果如圖10所示。

對比搜索結(jié)果可知，“視野線”平滑算法一定程度上減少了路徑拐點和過多折線，但并未根據(jù)機器人本體信息考慮目標方向，造成A*算法中碰撞點(a～e)依然存在。增加轉(zhuǎn)彎策略的方向A*算法避免碰撞的同時，檢測到h點轉(zhuǎn)彎的不合法性，重新規(guī)劃了路徑，從點f出發(fā)繞行，通過點g處的右轉(zhuǎn)彎到達目標點。另外，24鄰域方向A*算法較8鄰域方向A*算法，搜索范圍更廣，優(yōu)化了最短路徑。

2.2 加速方法對效率的影響

24鄰域甚至48鄰域方向A*算法固然能符合平滑特性，但搜索范圍的增加及轉(zhuǎn)彎策略的應用，大大增加了時間消耗。因此，基于本文提出的加速方法，對圖10中的仿真環(huán)境，分別對A*算法、8鄰域方向A*算法、24鄰域方向A*算法和48鄰域方向A*算法進行實驗驗證(表1)。

圖10 不同優(yōu)化方法的路徑規(guī)劃圖Fig．10 Path planning graphs of different optimization methods

表1 不同方法的加速前后效率對比Tab．1 Contrast of algorithm efficiency before and after acceleration ms

表1的實驗結(jié)果表明，基于二叉堆的加速方法能平均提速4～7倍，可以有效提高算法效率，尤其是在方向A*算法擴大鄰域搜索范圍，使得局部搜索節(jié)點大量增加的情況。當前測試地圖尺寸只有20m×20m，若該方法應用于實際環(huán)境中，提速效果將更為顯著。

3 真實環(huán)境下的實時路徑規(guī)劃

為驗證方向A*算法的可行性，將其用于貝貝機器人本體并在溫室模擬地圖中進行路徑規(guī)劃及軌跡跟蹤試驗。機器人貝貝是中國科學院合肥物質(zhì)科學研究院研發(fā)的系統(tǒng)，基于Gmapping方法構建的實際地圖及真實場景如圖11所示。其中，規(guī)劃路徑的起點為溫室入口點A(3.99，－1.38)，目標點為模擬某培養(yǎng)間的點B(－0.99，1.14)。

圖11 實際場景及構建地圖Fig．11 Actual scene and grid map

圖12 實際運行軌跡對比及機器人跟蹤誤差曲線Fig．12 Comparison between path searched and tracking error curve during tracking test

試驗過程中，機器人系統(tǒng)將實時記錄方向A*算法規(guī)劃的路徑(圖12a中綠色曲線)和實際運行軌跡(圖12a中紅色曲線)。觀察可知，機器人基本按照規(guī)劃路徑成功抵達目標，路線不能重合的地方主要因為機器人轉(zhuǎn)彎時加速度造成的慣性所致。分析實時跟蹤數(shù)據(jù)(圖12b)，機器人的實際跟蹤誤差始終小于0.15m，滿足實際需求。

4 結(jié)論

(1)針對溫室機器人路徑規(guī)劃問題，從生成路徑的平滑設計、碰撞檢測和算法實時性出發(fā)，提出一種方向A*算法，結(jié)合“視野線”平滑原則和“圓弧—直線—圓弧”轉(zhuǎn)彎策略，并輔以二叉堆加速方法。

(2)仿真結(jié)果表明，相較傳統(tǒng)A*算法，方向A*算法的轉(zhuǎn)彎策略及方向性，在平滑路徑的同時兼顧了機器人本體的碰撞問題，更加符合實際需求。同時，增加的加速方法也進一步提高效率，保證了算法的實時性。

(3)通過模擬溫室環(huán)境下的機器人試驗，表明真實機器人的路徑跟蹤誤差保持在0.15m以內(nèi)，驗證了本文提出的方向A*算法在溫室機器人路徑規(guī)劃中的可行性。

1 ZHOU Zhiping，NIE Yunfeng，GAOMin．Enhanced ant colony optimization algorithm for global path planning ofmobile robots［C］∥2013 5th International Conference on Computational and Information Sciences，2013:698－701．

2 陸新華，張桂林．室內(nèi)服務機器人導航方法研究［J］．機器人，2003，25(1):80－87．LU Xinhua，ZHANG Guilin．Summarization on indoor service robot navigation［J］．Robot，2003，25(1):80－87．(in Chinese)

3 ZAMIRIAN M，KAMYAD A V，F(xiàn)ARAHIM H．A novel algorithm for solving optimal path planning problems based on parametrization method and fuzzy aggregation［J］．Physics Letters A，2009，373(38):34－39．

4 張建英，趙志萍，劉暾．基于人工勢場法的機器人路徑規(guī)劃［J］．哈爾濱工業(yè)大學學報，2006，38(8):1306－1309．ZHANG Jianying，ZHAO Zhiping，LIU Dun．A path planningmethod formobile robot based on artificial potential field［J］．Journal of Harbin Institute of Technology，2006，38(8):1306－1309．(in Chinese)

5 祝繼華，周頤，王曉春，等．基于圖像配準的柵格地圖拼接方法［J］．自動化學報，2015，41(2):285－294．ZHU Jihua，ZHOU Yi，WANG Xiaochun，etal．Gridmapmerging approach based on image registration［J］．Acta Automatica Sinica，2015，41(2):285－294．(in Chinese)

6 STENTZ A．Optimal and efficient path planning for partially-known environments［C］∥Proceedings of the IEEE International Conference on Robotics and Automation，1994:3310－3317．

7 HU Yanrong，SIMON X Y．A knowledge based genetic algorithm for path planning of a mobile robot［C］∥Proceedings of the 2004，IEEE international Conference on Robotics＆Automation，2004:4350－4355．

8 MOHD M，MATTHEW W，NICHOLASK T．Ant colony robotmotion planning［C］∥Eurocon 2005，IEEE，2005:213－216．

9 王紅衛(wèi)，馬勇，謝勇，等．基于平滑A*算法的移動機器人路徑規(guī)劃［J］．同濟大學學報:自然科學版，2010，38(11):1647－1650，1655．WANG Hongwei，MA Yong，XIE Yong，et al．Mobile robot optimal path planning based on smoothing A*algorithm［J］．Journal of Tongji University:Natural Science，2010，38(11):1647－1650，1655．(in Chinese)

10 單偉，孟正大．基于改進A*算法的平滑路徑設計［J］．東南大學學報:自然科學版，2010，40(增刊1):155－161．SHANWei，MENG Zhengda．Smooth path design for mobile servise robots based on improved A*algorithm［J］．Journal of Southeast University:Natural Science Edition，2010，40(Supp．1):155－161．(in Chinese)

11 BOISSONNAT JD，CEREZO A，LOBLOND J．Shortest paths of bounded curvature in the plane［C］∥Proceedings of the IEEE International Conference on Robotics and Automation，1992:2315－2320．

12 TROCATO K I，DORST L．Differential A*［J］．IEEE Transactions on Knowledge and Data Engineering，2002，14(6):1218－1229．

13 王殿君．基于改進A*算法的室內(nèi)移動機器人路徑規(guī)劃［J］．清華大學學報:自然科學版，2012，52(8):1085－1089．WANG Dianjun．Indoor mobile-robot path planning based on an improved A*algorithm［J］．Journal of Tsinghua University: Science and Technology，2012，52(8):1085－1089．(in Chinese)

14 周文卷．復雜環(huán)境下自主移動機器人路徑規(guī)劃方法的研究［D］．長春:吉林大學，2014．

15 GIUSEPPEE C，MARCELLO F，GIACOMO L．A network flow based heuristic approach for optimising AGV［J］．Journal of Intelligent Manufacturing，2013，24(2):405－419．

16 馬飛，楊皞屾，顧青，等．基于改進A*算法的地下無人鏟運機導航路徑規(guī)劃［J/OL］．農(nóng)業(yè)機械學報，2015，46(7):303－309．http:∥www．j-csam．org/jcsam/ch/reader/view_abstract．a(chǎn)spx?file_no=20150743＆flag=1．DOI:10．6041/j．issn．1000-1298．2015．07．043．MA Fei，YANG Haoshen，GU Qing，et al．Navigation path planning of unmanned underground LHD based on improved A*algorithm［J/OL］．Transactions of the Chinese Society for Agricultural Machinery，2015，46(7):303－309．(in Chinese)

17 楊泳，戶佐安，何金海．路徑誘導系統(tǒng)中雙向啟發(fā)式A*算法研究［J］．計算機工程與應用，2014，50(16):54－56，71．YANG Yong，HU Zuoan，HE Jinhai．Research of bidirectional heuristic A*algorithm in route guide system［J］．Computer Engineering and Applications，2014，50(16):54－56，71．(in Chinese)

Real-time Path Planning of Greenhouse Robot Based on Directional A*Algorithm

ZHANGWen1，2LIU Yong1ZHANG Chaofan1，2ZHANG Long1XIA Yingwei1
(1．Institute of Applied Technology，Hefei Institutes of Physical Science，Chinese Academy of Sciences，Hefei230031，China 2．University of Science and Technology of China，Hefei230026，China)

Because of the existing problems in path planning of greenhouse robot under complex environment，a directional A*algorithm was proposed．Thismethod was focused on the smooth design，collision detection and the algorithm efficiency．Firstly，the“l(fā)ine of sight”solutionswere used to smooth the path for getting rid of the zigzag effect and collisions．Secondly，the“arc-line-arc”turningmethods were applied to avoid thewidth of the greenhouse robot in path finding．At last，some basic optimizations based on the binary heap were carried out to speed up the directional A*algorithm．Simulation and comparison results between the improved A*algorithm and traditional one showed that the proposed method wasmore efficient．It can not only meet the requirements of smooth，but also predict collision after proceeding with turning strategy．At the same time，the accelerating algorithm based on the binary heap made the path finding 4～7 times faster．Moreover，a path planning and tracking test was carried out in laboratory environment，where a simulation greenhouse was built．The results verified that the tracking precision can keep in a small range and the greenhouse robot can run without collision when the navigation path was given by the proposed algorithm，which proved the effectiveness and feasibility of the directional A*algorithm．

greenhouse robot;path planning;directional A*algorithm;binary heap

TP242.6

A

1000-1298(2017)07-0022-07

2016-11-16

2016-12-11

“十二五”國家科技支撐計劃項目(2015BAI01B00)、安徽省科技重大專項計劃項目(15CZZ02019)和安徽省創(chuàng)新型省份建設專項資金項目(15CZJ07008)

張文(1987—)，男，博士生，主要從事機器人視覺研究，E-mail:zhangwen@aiofm．a(chǎn)c．cn

夏營威(1985—)，男，副研究員，博士，主要從事機器視覺及機器人研究，E-mail:xiayw@aiofm．a(chǎn)c．cn

10．6041/j．issn．1000-1298．2017．07．003