，，，，

(中國科學技術大學精密機械與精密儀器系，安徽 合肥 230027)

LIAO Yuxiang，LU Siliang，ZHANG Haibin，ZHANG Shangbin，KONG Fanrang

(Department of Precision Machinery and Precision Instrumentation，University of Science and Technology of China，Hefei 230027，China)

高爾夫收球機器人路徑規(guī)劃研究

廖雨翔，陸思良，張海濱，張尚斌，孔凡讓

(中國科學技術大學精密機械與精密儀器系，安徽 合肥 230027)

LIAOYuxiang，LUSiliang，ZHANGHaibin，ZHANGShangbin，KONGFanrang

(Department of Precision Machinery and Precision Instrumentation，University of Science and Technology of China，Hefei 230027，China)

機器人的路徑規(guī)劃問題一直是機器人研究的核心內(nèi)容之一。在路徑規(guī)劃問題中，一般需要按照某一評價標準(如最短路徑長度和最短行進時間等)來規(guī)劃一條路徑。提出一個能使工作效率(單位時間工作量)最高的評價標準，并將其應用于高爾夫撿球機器人的路徑規(guī)劃?；谠摌藴?，并結合場地的特性和動態(tài)規(guī)劃方法中的2個經(jīng)典問題(01背包問題和數(shù)字金字塔問題)，提出一個新的機器人路徑規(guī)劃算法。該算法按照一定的條件枚舉多種可行的方案，通過計算最大單次工作量和路徑長度得到每種方案的效率值，最后選擇效率值最高的方案作為最優(yōu)方案。

機器人；高爾夫球；路徑規(guī)劃；動態(tài)規(guī)劃

0 引言

隨著中國經(jīng)濟快速的發(fā)展，人民生活水平的快速提高，國民的健康意識在不斷提升。高爾夫球作為休閑娛樂的一種方式，無疑將會越來越廣地被人們所接受。通常來說，一個高爾夫練習場占地約為100畝，有60～80個擊球位。每天從開館到閉館都會有絡繹不絕的人前來練習高爾夫球，因此，回收打出去的高爾夫球成為了每一個高爾夫練習場所要完成的工作。

現(xiàn)階段傳統(tǒng)的高爾夫球場的撿球方式，主要都局限在人工驅動的領域，比如高爾夫撿球器[1-2]、兩或三聯(lián)撿球機等。但諸如此類的撿球設備，都是需要人工來操作進行，這就不可避免地帶來了一個問題，即高爾夫球的回收工作與擊打高爾夫球存在矛盾。在正常營業(yè)過程中，每一個擊球位都會時刻不停擊打出高速行進的高爾夫球，因此，如果在此時派人回收散落在球場上的高爾夫球，一定會對收球人員造成傷害，為此每一個高爾夫練習場都不得不在閉館的時候才對高爾夫球進行回收工作，這就造成了效率低下及高昂的人工成本。智能高爾夫收球機器人[1]的出現(xiàn)，無疑在這一領域會有很大的應用價值，其不但可以解放人們辛勞煩瑣的體力勞動，也可為高爾夫球場帶來巨大的經(jīng)濟利益。

1 路徑規(guī)劃

高爾夫收球機器人定位為智能服務機器人，應用于高爾夫球場收集散落的高爾夫球。機器人通過自帶的多傳感綜合定位以及相關的路徑規(guī)劃算法進行收球。

路徑規(guī)劃問題[3]是移動類型機器人的熱點也是重點問題。對于高爾夫收球機器人的路徑規(guī)劃，主要解決3個問題，即使機器人能從初始點在球場中運動后回到初始點；用一定的算法使機器人能繞開障礙物；在完成以上任務的前提下，盡量優(yōu)化機器人的工作效率。為了解決這些問題，還需要相對應的3個技術:傳感技術；自定位技術；規(guī)劃與決策。

高爾夫球場的障礙物較少，并且不是時刻變動的。算法應該充分利用環(huán)境信息的已知性，以優(yōu)化工作效率為重點來規(guī)劃路徑。一個好的路徑規(guī)劃應滿足以下指標[4]：

a.合理性。返回的任何路徑都是合理的，或者說任何路徑對控制機器人運動都是可執(zhí)行的。

b.完備性。如果客觀上存在一條從起點到達終點的無碰路徑，該算法一定能找到；如果環(huán)境中沒有路徑可通行，會報告規(guī)劃失敗。

c.最優(yōu)性。 算法規(guī)劃的結果路徑在某個測度(如時間、距離和能量消耗等)上是最優(yōu)的。

d.實時性。 規(guī)劃算法的復雜度(時間需求和存儲需求等)能滿足機器人運動的需要。

e.環(huán)境變化適應性。 算法具有適應環(huán)境動態(tài)改變的能力，隨著環(huán)境改變，不必全部重新計算。

f.滿足約束。 支持移動機器人運動時的完整性和非完整性運動約束。

2 動態(tài)規(guī)劃[5-6]

2.1 01背包

現(xiàn)有一個背包，容積為m。n個物品，每個物品的體積為V[i]。請問，最多能放下多少個物品。

此問題的動態(tài)為f(i，j)，表示第i個物品到第n個物品，這n-i+1個物品放在容積為j的空間里，最多能放下多少個。

狀態(tài)轉移方程為：

f(i，j)=max{f(i+1，j)，f(i+1，j-V[i])+1}

(1)

2.2 數(shù)字金字塔

規(guī)定從最頂層走到最底層，每一步可沿左斜線向下或右斜線向下走。求解從最頂層走到最底層的一條路徑，使得沿著該路徑所經(jīng)過的數(shù)字總和最大。

此問題的動態(tài)為f(i，j)，表示從點(i，j)往下走能得到的數(shù)字最大總和。d(i，j)表示點(i，j)的數(shù)值。

狀態(tài)轉移方程為：

f(i，j)= max {f(i+1，j)，f(i+1，j+1)}+

d(i，j)

(2)

2.3 動態(tài)規(guī)劃的計算方法

動態(tài)規(guī)劃的計算方法依賴于狀態(tài)與狀態(tài)轉移方程。以01背包為例，問題的動態(tài)為f(i，j)，背包的總容量為m。f(1，m)就是01背包問題的解。利用式(1)將問題轉換求f(2，m)與f(2，m-V[i])的值，算法的時間復雜度為o(2n)，這個時間復雜度是不能接受的。實際上對于任一個狀態(tài)f(i，j)，它都是獨立的，在狀態(tài)轉移過程中，會重復訪問某一個狀態(tài)f(p，q)，當訪問過一次后，將其值記錄，待再次訪問時，可以直接調用其值。而f(i，j)的狀態(tài)只有n×m個，所以算法的時間復雜度實際為o(n×m)。

3 動態(tài)規(guī)劃在機器人中的應用

3.1 路徑規(guī)劃方法描述

高爾夫球場中有幾種區(qū)域是不能通行的，即洼地，周圍有欄桿保護，不可通行；指示牌或廣告牌，不可觸碰。如果S為機器人起始點狀態(tài)；X為當前機器人的狀態(tài)；M為網(wǎng)格地圖表示的環(huán)境地圖；T為機器人單次工作的總量。那么提出的路徑規(guī)劃方法可表示為：

a.枚舉一個目標點G，基于環(huán)境信息M，規(guī)劃出從S到G的全局最優(yōu)路徑L和此路徑的工作量TL。

b.基于M和L，得到一個新的環(huán)境信息ML(L路徑上點的值變?yōu)?)。

c.基于環(huán)境信息ML，規(guī)劃出從G到S的全局最優(yōu)路徑LB和此路徑的工作量TB，使得TB+TL

d.計算效率值EG，記TG=TL+TB，記LG為路徑L和LB的總長度，則EG=TG/LG。

e.找出效率值最高的點Gmax和路徑Lmax，令X=Gmax，并按照路徑Lmax執(zhí)行。

f.按照傳感器信息和路徑Lmax信息更新M，跳轉到a步。

3.2 動態(tài)規(guī)劃部分算法描述

高爾夫球場上僅有一些簡單的障礙物，規(guī)定機器人由出發(fā)點S向目標點G行進的過程中，機器人只按照圖 1中所示的2種方案前進(在網(wǎng)格中，只能向上或者向左移動，參照2.2節(jié)數(shù)字金字塔)。此方法在一般的機器人移動問題中是不可取的，如圖 2所示(斜線為此方法不可到達的地方)。但是在如此寬闊的高爾夫球場中，幾乎是不存在此類陷阱區(qū)域，僅有極其特殊的情況會出現(xiàn)圖 2情況。如果存在，可以先通過寬度優(yōu)先搜索找到這些地方，在算法中對這些節(jié)點進行特殊處理(測試場地不包括圖 2中斜線所示陷阱區(qū)域，系統(tǒng)算法不包含對此類節(jié)點的特殊處理)。

圖1 行進方案 圖2 特殊情況

定義一個動態(tài)f1(i，j)表示從出發(fā)點S(1，1)到目標點G(i，j)的最大工作量。由上述行進方案和式(2)可得如下狀態(tài)轉移方程，即

f1(i，j)=max{f1(i-1，j)，f1(i，j-1)}+m(i，j)

(3)

m(i，j)為環(huán)境信息M中點(i，j)的值。將G點代入式(3)可得f1(G)的值(也就是路徑的工作量TL)和路徑L。

規(guī)定機器人由目標點G向出發(fā)點S行進的過程中，機器人只按照圖 3所示2種方案前進。此方法必然有一條路徑能到達S(按照f1(i，j)所求路徑L返回)。

圖3 由目標點向出發(fā)點行進方案演示

定義一個動態(tài)f2(i，j)，表示從點G(i，j)出發(fā)到出發(fā)點S(1，1)的最大工作量。參照式(3)，基于環(huán)境信息ML，規(guī)劃出從G到S的全局最優(yōu)路徑LB和此路徑的工作量TB，使得TB+TL

f2(i，j，k)=max {f2(i-1，j，k1)+ml(i-1，j)，

f2(i，j-1，k2)+ml(i，j-1)}

(4)

ml(i，j)為環(huán)境信息ML中點(i，j)的值；k1=k-ml(i-1，j)，k2=k-ml(i，j-1)。將G點和f2(G)代入式(4)，可得TB和路徑LB。

綜上可得效率值EG為：

(5)

3.3 整體算法描述

算法流程如圖 4所示。

圖4 算法流程

算法中，均依賴環(huán)境信息M運算，若環(huán)境信息M不能建立并及時更新，算法就會失效。機器人配置有攝像頭，拍攝圖像后做圖像二值化處理。但是單個攝像頭拍攝圖像不能獲得深度信息，并不能有效地更新環(huán)境信息M，在實際測試中，不能滿足算法的要求，必須引進其他技術進行改進。雙目視覺技術模仿人的雙眼，利用2個攝像機同時采集同一場景的圖像，由于2臺攝像機位置不同，采集的圖像存在視差，利用這一視差可以直接獲取空間物體的深度信息[7-8]，使得算法可以有效地更新環(huán)境信息M。

4 仿真過程與結果

因測試球場范圍較大，按照一定規(guī)格劃分為二維網(wǎng)格后運算量也較大，所以算法仿真過程中模擬一個小的二維圖，如圖 5所示。仿真過程中只對其中的幾個方案計算效率值，并不直接求出效率值最高的方案。

圖5中白色區(qū)域為可通行區(qū)域，黑色區(qū)域為洼地、指示牌或廣告牌等不可通行區(qū)域，右下角S代表機器人出發(fā)位置，其余數(shù)值代表環(huán)境信息M中點(i，j)的值。

圖5 環(huán)境信息

枚舉點G，這里取2個點來計算EG，如圖 6所示。

圖6 枚舉方案

設單次工作量T=50。分別將G1、G2帶入式(3)，得f1(G1)=28，f2(G2)=48。分別在路徑LG1與LG2下的ML如圖 7所示。LG1與LG2分別為圖 7所示虛線部分。

圖7 路徑LG1和LG2

分別將G1、k1=T-f1(G1)=22與G2、k2=T-f2(G2)=2代入式(4)，可得f2(G1，k1)=10，f2(G2，k2)=1。G1、G2下的LB如圖 8所示實線部分。

圖8 G1、G2下的路徑LB

分別求出TG1、LG1與TG2、LG2，得:

(6)

(7)

由式(5)～式(7)得：

(8)

由式(8)得出結論，選擇G1方案的效率比選擇G2方案的效率要高。

5 結束語

路徑規(guī)劃的方法有很多，基于路徑規(guī)劃的特性，動態(tài)規(guī)劃實際上是不適合路徑規(guī)劃的。但是在特殊情況下，引入動態(tài)規(guī)劃是可以達到解決問題的目的。通過簡單介紹動態(tài)規(guī)劃的一些基本案例，從動態(tài)規(guī)劃得到的經(jīng)驗中加以結合，提出了一種基于動態(tài)規(guī)劃的以工作效率值為評價標準的高爾夫撿球機器人路徑規(guī)劃算法，此算法能有效地提高高爾夫收球機器人的工作效率。

但是，還存在2個需要改進的地方，一是，圖 2中斜線所示陷阱區(qū)域，雖然出現(xiàn)幾率極低并且出現(xiàn)后也對算法影響不大，但是也必須給出一個算法來處理這特殊情況；二是，雖然提出了利用雙目視覺來獲取空間深度信息以便更新環(huán)境信息M，但是具體的方法仍需要探討。

[1] Pereira N，Ribeiro F，Lopes G，et al.Autonomous golf ball picking robot design and development[J].Industrial Robot：An International Journal，2012，39(6)：541-550.

[2] 張韜懿，王田苗，吳耀，等.全地形無人車的設計與實現(xiàn)[J].機器人，2013，35(6):657-664

[3] Ge S S，Cui Y J.New potential functions for mobile robot path planning[J].IEEE Transactions on Robotics and Automation，2000，16(5)：615-620.

[4] 曲道奎，杜振軍，徐殿國，等.移動機器人路徑規(guī)劃方法研究[J].機器人，2008，30(2):97-101.

[5] 李端，錢富才，李力，等.動態(tài)規(guī)劃問題研究[J].系統(tǒng)工程理論與實踐，2007(8):56-64.

[6] Bertsekas D P.Dynamic programming and optimal control[M].Belmont，MA：Athena Scientific，1995.

[7] 邱河波.基于DSP的移動機器人雙目視覺技術研究[D].成都：電子科技大學，2013.

[8] 祝琨，楊唐文，阮秋琦，等.基于雙目視覺的運動物體實時跟蹤與測距[J].機器人，2009，31(4):327-334.

Research on Path Planning for a Golf Ball Picking Robot

Path planning problem for a robot is one of the crucial contents in robotics research.In the path planning problem，a criterion (e.g.，shortest path length，shortest travel time，etc.) is required to plan a path for the robot.In this study，we propose a criterion that can maximize the work efficiency (highest workload in unit time) and apply this criterion to the path planning of a golf ball picking robot.Subsequently，we proposed a new path planning algorithm by considering both the characteristics of the golf course and the two classical problems of the dynamic programming (the 01 knapsack problem and the digital pyramid problem).The proposed algorithm enumerates several solutions according to the certain conditions，and then calculates the corresponding efficiency values by computing the maximal workloads and the maximal path lengths，and finally achieves the optimal solution by selecting the maximal efficiency value.

robot; golf ball; path planning; dynamic programming

2014-08-12

TP242.6

A

1001-2257(2014)12-0077-04

廖雨翔(1990-)，男，四川綿陽人，碩士研究生，研究方向為智能控制，機器人。