金 何，王烈準

(六安職業(yè)技術(shù)學院 汽車與機電工程學院，安徽 六安，237000)

機器人路徑規(guī)劃是指在含有障礙物的環(huán)境中，按照某些指標要求，尋找一條從起始狀態(tài)到目標狀態(tài)的無碰撞路徑[1]。動態(tài)環(huán)境中，對運動障礙物的動態(tài)避碰是機器人運動規(guī)劃的一個基本問題。常見的路徑規(guī)劃方法有人工勢場法、遺傳算法、模糊邏輯算法等。人工勢場法原理簡單，計算量小，容易規(guī)劃出一條無碰撞的路徑。但是也存在局部最小值等缺點。為此，徐飛[2]通過增加虛擬中間目標點從而使機器人成功逃脫局部極小點。劉硯菊[3]提出了一種修改斥力方向和自主建立虛擬目標牽引點相結(jié)合的算法。丁家如[4]首先通過幾何拓撲學思想得到可行解域，對威脅的連通性進行分析，然后在可行解域內(nèi)進行航跡點預規(guī)劃，彌補人工勢場法易陷入局部最小而無法找到可行路徑的不足。

然而以上路徑規(guī)劃算法只考慮在反應性系統(tǒng)中，機器人在下一步的路徑規(guī)劃。缺少對整個工作環(huán)境中機器人路徑選擇的全局考慮，且沒有考慮到整個規(guī)劃周期中隨著時間的變化，每個位置的可達性。針對這些問題，文中提出的算法結(jié)合了路徑規(guī)劃系統(tǒng)和反應性系統(tǒng)的優(yōu)點。在機器人出發(fā)前，利用路徑規(guī)劃系統(tǒng)進行全局考慮，計算出每個位置的勢場值，但并不規(guī)劃出具體的路徑。在反應性系統(tǒng)中，機器人用計算出的勢場值避碰，并到達目標點。為了避免“跟蹤問題”，障礙物和目標點的勢場值被描述成時間的函數(shù)。勢場值的大小表明了機器人從當前的位置和時間，向前隨機的行進一步，撞上障礙物的概率，勢場值的大小決定了機器人的行進方向。值越小，表示碰撞的概率越小。

1 環(huán)境描述與定義

1.1 工作環(huán)境

常用工作環(huán)境包括柵格地圖[5]、拓撲地圖[5]、特征地圖[5]等。文中通過構(gòu)建三維柵格地圖，每個維度大小為9，即創(chuàng)建9*9*9個柵格作為機器人的工作環(huán)境。忽略機器人、障礙物和目標點的大小。對于每個柵格，計算各個時刻該柵格的勢場值。如果該柵格被障礙物占據(jù)，用1表示，同理用0表示該位置被目標點占據(jù)，用-1表示該位置是可行位置。

1.2 對角線原則

圖1 構(gòu)建對角線Fig.1 Building the diagonal line

創(chuàng)建另一個三維柵格地圖環(huán)境，和機器人工作環(huán)境大小一致，且含有相同的障礙物個數(shù)。將起始點置于立方體工作環(huán)境底面的四個頂點,即A1(1,1,1),A2(9,1,1),A3(9,9,1),A4(1,9,1),將目標點置于此隨機環(huán)境頂面的四個頂點上，即B1(9,9,9),B2(1,9,9),B3(1,1,9),B4(9,1,9)。依次連接這8個點形成4條對角線，如圖1所示。此時，機器人和目標點的距離最遠，則機器人到達目標點所經(jīng)歷的時間步長相對最大，取其中最大的值作為先行值。

1.3 勢場值

人工勢場法[6]由Khatib提出，把機器人的工作環(huán)境看成一個抽象的勢場，在這個勢場中，目標點產(chǎn)生引力場，障礙物產(chǎn)生斥力場，機器人在這兩個場的合力作用下避開障礙物，朝著目標點行進。人工勢場法存在局部最小值問題[6]，為此可引入調(diào)和函數(shù)[7]，沿著調(diào)和函數(shù)的梯度形成的光滑曲線沒有局部最大值和最小值。將機器人工作環(huán)境的構(gòu)型空間建模成調(diào)和函數(shù)，機器人沿著梯度向量下降方向就可以避開障礙物并到達目標點[8]。勢場值的大小和時間有關(guān)[9]，表明了機器人從當前的位置和時間，向前隨機的行進一步，和障礙物發(fā)生碰撞的概率。機器人在路徑規(guī)劃過程中，每一個時間步長都朝著最小勢場值的方向行進，表示發(fā)生碰撞的概率最小。對于任意柵格在t時刻的勢場值可用下式表示：

在三維環(huán)境中，機器人每一個時間步長可達的位置可能性有7種：向上(N)，向下(S)，向左(W)，向右(E)，向前(F)，向后(B)以及停止不動(T)。機器人位置移動如圖2所示。

圖2 t時刻勢場值計算Fig.2 Calculation of potential field value at time t

2 三維空間中機器人路徑規(guī)劃算法

2.1 確定先行值

創(chuàng)建另一個隨機的環(huán)境，大小和機器人工作環(huán)境相同，且含有相同的障礙物個數(shù)。考慮到若時間步長很小，則從起始點出發(fā)后不能到達目標點，設起始時間步長T=10，每次增加5，推算出當?shù)竭_時間步長時，障礙物所在的位置。若機器人沒有到達目標點，則依次增加時間步長值。若到達目標點，則記錄此時的時間步長并退出程序。創(chuàng)建9*9*9*T四維矩陣，并初始化矩陣中每個位置元素都為-1，并通過對角線原則將起始點和目標點分別置于立方體工作環(huán)境的頂點上，使得兩者相距最遠。對于每一個障礙物，它所在的位置設為1，下一個時間步長，它所能到達的位置也為1，且任意時刻兩個障礙物不能相碰。對于目標點，它所在的位置設為0，下一個時間步長，它所能到達的位置也為0。障礙物和目標點在同一時刻不能占有相同的位置，即不會發(fā)生碰撞。障礙物位置推算流程如下圖3所示。

圖3 障礙物位置推算流程圖Fig.3 The flow chart of position calculation of obstacles

首先推算出從1至先行值時，障礙物和目標點在空間中的位置情況，然后推算出機器人從起始點到達目標點的時間步長，具體步驟如下：

1)創(chuàng)建一個空節(jié)點隊列，并將起始點位置入隊。

2)取出隊列中的首元素，若和目標點重合，則返回此時的時間步長，否則轉(zhuǎn)入3。

3)若時間步長t>T，則返回失敗的信息。若t

4)根據(jù)圖4推算出隊列中的隊首元素在下個時刻可能到達的位置，若該位置被障礙物所占據(jù)，則放棄該位置。否則將這些可能的位置放進隊列的尾部。

5)若隊列中仍然有元素則轉(zhuǎn)入2，若沒有則退出程序。

通過對角線原則獲得4個時間步長，取最大的作為先行值。然后推算出從1至先行值時刻，障礙物和目標點的位置。

2.2 勢場值的計算

勢場值的計算是從先行值時刻起，向前計算，每次減1，直到時間為1。在先行值時刻，強制使得空間中所有位置勢場值均為1，目標點所在位置的勢場值為0。從(先行值-1)時刻，若某位置不是可行位置，說明此位置被障礙物或目標點占據(jù)，則停止計算。若某位置是可行位置，則t時刻該位置的勢場值等于(t+1) 時刻可能到達該位置的所有位置勢場值的平均值。機器人從起始點出發(fā)，在下個時間步長到達勢場值最低的位置，重復不斷，直到到達目標點。勢場值計算流程見圖4。

圖4 勢場值計算Fig.4 Calculation of potential field value

3 仿真結(jié)果

將文中提出的算法在MATLAB平臺上進行仿真。產(chǎn)生9*9*9個柵格，作為機器人的三維工作環(huán)境。機器人起始點坐標(2,1,1),目標點坐標(8,9,8)，速度大小5，空間中含有17個障礙物，它們的速度和方向隨機。圖5表示當時間步長為19時，障礙物和目標點在三維空間環(huán)境中的位置情況。其中障礙物用黑色小圓點表示，目標點用黑色方格表示。黑色大圓點表示機器人在每個時刻的位置，將這些黑色大圓點用線段連接，表示機器人的行進路線。當機器人行進到先行值為19時，機器人到達目標點。

圖5 機器人行進路線Fig.5 Path traversed by the robot

在機器人工作環(huán)境增加障礙物密度，采用文中提出的算法進行仿真，結(jié)果如表1所示?？梢娬系K物的密度會對本算法產(chǎn)生影響。若障礙物的密度過大，則會增加程序運行時間，且程序有可能陷入死循環(huán)。

表1 障礙物密度影響

4 結(jié)語

文中通過量化空間中各個位置在每個時刻的勢場值來進行機器人路徑規(guī)劃，勢場值大小表明了機器人從當前的位置和時間，向前隨機的行進一步，撞上障礙物的概率。文中所采用的仿真算法，只是在計算機中通過軟件MATLAB和函數(shù)模擬，雖然仿真結(jié)果表明了該算法的有效性，但今后需要進一步的實踐論證。機器人如何在高密度障礙物環(huán)境中進行路徑規(guī)劃，以及如何面對環(huán)境信息突然改變，將是下一步研究的重點。