基于人工勢場法的移動機(jī)器人路徑規(guī)劃研究現(xiàn)狀與展望*

石志剛，梅松，邵毅帆，萬如，宋志禹，謝銘露，李燕

(1.寧夏農(nóng)林科學(xué)院枸杞工程技術(shù)研究所，銀川市，750002；2.農(nóng)業(yè)農(nóng)村部南京農(nóng)業(yè)機(jī)械化研究所，南京市，210014；3.南京理工大學(xué)機(jī)械工程學(xué)院，南京市，210094；4.泰興市知識產(chǎn)權(quán)服務(wù)中心，江蘇泰興，225400)

0 引言

據(jù)估計，2050年世界總?cè)丝趯⑦_(dá)到90億，當(dāng)前農(nóng)業(yè)活動受限于生產(chǎn)效率而無法顯著提升。為提升生產(chǎn)效率，在過去幾十年中機(jī)械化和自動化生產(chǎn)模式已廣泛應(yīng)用于農(nóng)業(yè)生產(chǎn)中，一批多領(lǐng)域?qū)Ｓ弥悄苻r(nóng)業(yè)機(jī)器被開發(fā)，針對不斷提高農(nóng)業(yè)機(jī)械的生產(chǎn)效率以滿足日益增長的農(nóng)業(yè)生產(chǎn)需求問題，農(nóng)業(yè)機(jī)器人如何高效率行走問題，成為當(dāng)前的研究熱點，而農(nóng)業(yè)機(jī)器人的路徑規(guī)劃技術(shù)是關(guān)鍵，這也是中國“十四五”智能農(nóng)機(jī)和智慧農(nóng)業(yè)要求下的必然發(fā)展趨勢。

路徑規(guī)劃是提升移動機(jī)器人運行效率并保證其運行穩(wěn)定性的核心技術(shù)之一[1]，學(xué)者們對路徑規(guī)劃技術(shù)做了大量研究。移動機(jī)器人的路徑規(guī)劃就是在依照工作能耗最小、行走路線最短、行走時間最短等指標(biāo)，在工作空間內(nèi)找到一條從運行開始到運行結(jié)束可以避開環(huán)境障礙物滿足工作指標(biāo)的最優(yōu)路徑，該種算法是實現(xiàn)農(nóng)業(yè)機(jī)器人遠(yuǎn)程化運行的基礎(chǔ)。

經(jīng)過幾十年的發(fā)展，國內(nèi)外學(xué)者對許多具有優(yōu)良運行效率及運行穩(wěn)定性的路徑規(guī)劃方法進(jìn)行研究，如A*算法[2]、Dijstar算法、人工勢場法[3]、蟻群算法[4]、粒子群算法[5]、RRT算法[6]等。A*算法、Dijstar算法、蟻群算法、遺傳算法等能在機(jī)器人處于靜態(tài)時得到較好路徑，但因移動機(jī)器人自身算力限制及工況實時性的要求，對路徑進(jìn)行實時計算修正仍是一個問題。

人工勢場法是一種啟發(fā)式搜索算法，具有算法簡單，實時性好的優(yōu)點，因此廣泛的應(yīng)用于移動機(jī)器人的路徑規(guī)劃之中，并能在大部分移動機(jī)器人路徑規(guī)劃問題中能夠取得較好的結(jié)果，但是也存在局部最小值和目標(biāo)不可達(dá)的問題。針對這些問題，許多學(xué)者對人工勢場法的運行機(jī)制和原理進(jìn)行了深入研究，并提出了改進(jìn)方案及應(yīng)對對策。

本文分析了國內(nèi)工業(yè)機(jī)器人路徑規(guī)劃的研究現(xiàn)狀，對人工勢場法在農(nóng)業(yè)中的應(yīng)用進(jìn)行詳細(xì)描述，介紹人工勢場法的工作機(jī)制，并對人工勢場法存在的問題以及解決方法進(jìn)行原理分析和方法總結(jié)，并對效果較好的算法融合進(jìn)行原理分析。最后對基于算法融合的人工勢場法在農(nóng)業(yè)機(jī)器人上應(yīng)用研究方向進(jìn)行展望。

1 人工勢場法的工作原理及缺陷分析

1.1 人工勢場法的工作原理

人工勢場法(Artificial Potential Field Method)是由Khatib[3]首先提出將障礙物及目標(biāo)抽象為虛擬勢場，通過建立對應(yīng)勢能場函數(shù)解決機(jī)械臂避障問題的一種算法。其中，虛擬勢場源分為兩類：引力場和斥力場。勢能場函數(shù)將機(jī)器人進(jìn)入?yún)^(qū)域中的障礙物視為斥力極，目標(biāo)視為引力極。抽象定義引力極產(chǎn)生引力為參考位置(即移動機(jī)器人位置)指向目標(biāo)位置的距離相關(guān)函數(shù)；斥力極產(chǎn)生的斥力為障礙物指向參考位置的距離相關(guān)函數(shù)。通過目標(biāo)位置引力和環(huán)境中障礙物斥力的疊加，即可得移動機(jī)器人運行至該點時的合力大小及方向，如圖1所示。

圖1 人工勢場法示意圖Fig.1 Schematic diagram of artificial potential field method

假設(shè)移動機(jī)器人所在位置為X=(x,y)，X為移動機(jī)器人位置向量，XT=(xT,yT)為目標(biāo)位置向量，Katt為引力勢場常量，則目標(biāo)位置與移動機(jī)器人之間引力場

(1)

式中：ρ(X,XT)——移動機(jī)器人至目標(biāo)位置相對距離。

引力勢場負(fù)梯度方向為移動機(jī)器人所受引力方向，即

Fatt(X)=-Uatt=-Katt|X-XT|

(2)

由于移動機(jī)器人與障礙物間距離對規(guī)劃路徑會產(chǎn)生不同程度影響，因此設(shè)置以障礙物為中心的斥力場影響半徑ρ0，移動機(jī)器人與障礙物間距離ρ。當(dāng)ρ>ρ0時，移動機(jī)器人不再受斥力場的影響，此時受斥力為0；當(dāng)ρ≤ρ0時，障礙物移動機(jī)器人間距離ρ與斥力場Urep成線性，可得引力場

(3)

式中：ρ(i)(X)——機(jī)器人與障礙物i間的歐氏距離；

Krep——斥力勢場常量。

斥力勢場負(fù)梯度方向為移動機(jī)器人所受斥力方向，即

(4)

通過將所受引力和所有斥力求取矢量和可得機(jī)器人所受合力

(5)

式中：n——障礙物的個數(shù)。

人工勢場法對每個障礙物的斥力都進(jìn)行考慮計算，能夠很好的保證移動機(jī)器人規(guī)劃路徑不會與障礙物發(fā)生碰撞，但由于算法本身具有缺陷，存在無法到達(dá)目標(biāo)位置或是最終軌跡不夠平滑等問題。

1.2 人工勢場法的缺陷分析

人工勢場法在移動機(jī)器人路徑靜態(tài)規(guī)劃和動態(tài)規(guī)劃中得到廣泛應(yīng)用，但存在陷入局部最小點、目標(biāo)不可達(dá)、路徑易出現(xiàn)震蕩等問題，主要缺陷分析如下。

1)陷入局部最小點。人工勢場法通過式(2)和式(4)對勢能場求取負(fù)梯度，利用得到的引力和斥力根據(jù)式(5)求合力為移動機(jī)器人路徑規(guī)劃提供驅(qū)動力。當(dāng)F(X)=0時，移動機(jī)器人在該點處陷入局部極小值[7]，處于靜止?fàn)顟B(tài)。該問題在多障礙物復(fù)雜環(huán)境中尤為常見。通過啟發(fā)式算法可以在一定程度上解決局部最小值問題，但最終得到的規(guī)劃路徑可能非最優(yōu)解且需要消耗大量時間運算，導(dǎo)致算法效率低下。

2)目標(biāo)不可達(dá)問題。由于環(huán)境中障礙物的位置隨不同工程問題而改變，因此當(dāng)環(huán)境中的障礙物恰好分布在目標(biāo)位置附近時，可能會導(dǎo)致移動機(jī)器人無法達(dá)到目標(biāo)位置。在一般的路徑規(guī)劃問題中，障礙物不會恰好分布在目標(biāo)位置周圍，斥力不斷減小，引力逐漸增大直至抵達(dá)目標(biāo)位置。

在實際工作環(huán)境中，會出現(xiàn)如圖2的情況。當(dāng)目標(biāo)位置的附近存在相隔很近的障礙物時，引力不斷增加，斥力也隨著移動機(jī)器人不斷靠近目標(biāo)位置而逐漸增大，根據(jù)式(5)，此時移動機(jī)器人所受斥力可能遠(yuǎn)大于引力而無法抵達(dá)目標(biāo)位置。

圖2 目標(biāo)不可達(dá)問題示意圖Fig.2 Schematic diagram of unreachable target problem

3)路徑震蕩問題。移動機(jī)器人在狹窄的走廊中運行時，會同時受到來自兩邊的斥力。由于障礙物位置的突然變化使機(jī)器人產(chǎn)生不穩(wěn)定振動，最終導(dǎo)致移動機(jī)器人與障礙物發(fā)生碰撞，這種情況隨著速度的增加而格外明顯。

2 人工勢場法的改進(jìn)研究

許多學(xué)者對上述的缺陷進(jìn)行了深入研究，以增加人工勢場法的適用范圍及運行可靠性。

2.1 局部最小點解決方案

針對人工勢場法局部極小值的問題許多學(xué)者對算法進(jìn)行改進(jìn)，其中主要的思想是對勢能場函數(shù)進(jìn)行優(yōu)化，通過優(yōu)化勢能場函數(shù)以滿足跳出局部極小點。

1)障礙物連結(jié)法。在傳統(tǒng)的人工勢場法中，由于勢場函數(shù)需要對每個障礙物的斥力進(jìn)行合成，極大地增加了出現(xiàn)局部最小點的可能性。黃興華[8]提出采用障礙物連結(jié)算法。通過對工作范圍內(nèi)的障礙物進(jìn)行連結(jié)(圖3)，使其簡化成一整個障礙物，便于運算并能在一定程度上減少局部最小點情況的出現(xiàn)。通過設(shè)定移動機(jī)器人的可視角度為α，可視范圍半徑為Rd，當(dāng)兩個障礙物滿足距離閾值Ds時，則將兩個障礙物連結(jié)，而其他可視范圍外的不可見障礙物則假設(shè)其對移動機(jī)器人無斥力影響，與傳統(tǒng)人工勢場法中設(shè)置ρ0有相似之處。

圖3 障礙物連結(jié)法示意圖Fig.3 Schematic diagram of obstacle linkage method

2)Follow-Wall算法。雖然障礙物連結(jié)算法能夠在一定程度上減少局部最小點情況的出現(xiàn)，但是出現(xiàn)斥力方向和引力方向處于同一條直線上時，移動機(jī)器人仍有可能陷入局部最小點而靜止無法到達(dá)目標(biāo)位置。

溫素芳等[9]在傳統(tǒng)人工勢場法基礎(chǔ)上，對障礙物影響范圍進(jìn)行二次分層。傳統(tǒng)人工勢場法中，障礙物與移動機(jī)器人間距離設(shè)為ρ，影響范圍設(shè)為ρ0，當(dāng)距離超過影響范圍ρ0時，障礙物對移動機(jī)器人無斥力影響(如圖4(a))，反之則考慮障礙物斥力影響。溫素芳通過增設(shè)一個接近距離ρ1，當(dāng)0<ρ<ρ1時，表示移動機(jī)器人即將碰撞障礙物，設(shè)置引力方向垂直于斥力(如圖4(c))，再通過傳統(tǒng)人工勢場法求合力的方式得到運動方向以逃離局部最小點。

(a)當(dāng)ρ>ρ0時

這種算法與Follow-Wall算法有著相似的思想。Follow-Wall算法是由Yun等[10]首先提出用于解決移動機(jī)器人陷入局部最小值問題。Follow-Wall算法通過設(shè)定5個運動方向，對每個運動方向上障礙物的距離與障礙物安全距離進(jìn)行比較。如果存在某個方向上的距離大于安全距離，且滿足上述條件中最小方向，則沿著該方向運行，并保持最大速度；如果所有方向距離都小于安全距離則使移動機(jī)器人靜止，使移動機(jī)器人轉(zhuǎn)動一個固定的角度。這種算法通過不斷修正移動機(jī)器人路徑，緊貼著障礙物的外沿不斷運行，當(dāng)面遇障礙物時通過不斷改變運動方向來最終繞過障礙物達(dá)到目標(biāo)位置，算法流程如圖5所示。

圖5 Follow-Wall算法流程圖Fig.5 Flow chart of Follow-Wall algorithm

由于Follow-Wall算法使移動機(jī)器人沿著障礙物不斷的運行，為使得移動機(jī)器人能夠進(jìn)入和退出算法，黃興華[8]通過設(shè)定局部最小值影響范圍，通過判斷單位時間之后，移動機(jī)器人的坐標(biāo)是否在以t秒前坐標(biāo)位置為圓心，半徑為Rl的圓內(nèi)，若在即可判斷移動機(jī)器人已陷入局部穩(wěn)定狀態(tài)即可使用跳出局部最小點算法以實現(xiàn)達(dá)到目標(biāo)點位置。通過這個方法可以極大減少算法的復(fù)雜程度，為局部最小點算法提供基礎(chǔ)。王麗[11]通過判斷移動機(jī)器人與障礙物和目標(biāo)點之間的角度來知曉運行方向以及障礙物存在位置，以開始Follow-Wall算法；當(dāng)目標(biāo)點位置位于移動機(jī)器人正面180°內(nèi)且正前方不存在障礙物時，則退出Follow-Wall算法。

3)虛擬目標(biāo)點。設(shè)置虛擬目標(biāo)點在遇到U型和C型障礙物時能如Follow-Wall算法一樣逃離局部最小點[12]，但具有更高的運行效率。程志等[13]首先對移動機(jī)器人附近的障礙物進(jìn)行判定，設(shè)置安全距離R0，通過對障礙物的兩個端點Xo1和Xon間距離是否小于2R0來確定是否屬于同一個障礙物。然后通過移動機(jī)器人與障礙物的相對位置來判斷機(jī)器人是否處于障礙物影響范圍中，其中分為兩種情況。第一種情況如圖6(a)所示，點X處于Xo1和Xon連線所圍區(qū)域內(nèi)，則認(rèn)為處于障礙物影響范圍內(nèi)；第二種情況如圖6(b)所示，當(dāng)δ<φ時，則認(rèn)為處于障礙物影響范圍內(nèi)。由此做X關(guān)于Xon的對稱點X*，通過傳統(tǒng)人工勢場法的勢場函數(shù)與虛擬目標(biāo)點的不斷更新，最終就能實現(xiàn)逃離局部最小點到達(dá)目標(biāo)點位置。

(a)機(jī)器人在障礙物內(nèi)

4)其他算法。(1)牛頓型勢場[14]。N.Ahuja采用了一種牛頓型場，將障礙物簡化成具有均勻密度的線段，線段上的每一個微元在整個環(huán)境中產(chǎn)生的勢場類似于一個點電荷產(chǎn)生的電場，如果環(huán)境中有多個線段障礙物，則用迭加法將對應(yīng)的勢場相加以此勢場為基礎(chǔ)L形機(jī)器人規(guī)劃了避障路徑。(2)調(diào)和場(Harmonic Potential Filed)。Kim等[15]采用了一種調(diào)和場方法來消除勢場中的局部極小點，但是它是以不能保證最后能避開障礙物為代價的。(3)基于速度勢場。高升等[16]提出一種基于速度勢場的局部在線避障方法，以速度勢場的形式充分利用了相對速度的信息，得到了較好的局部在線避障效果。

2.2 目標(biāo)不可達(dá)問題

目標(biāo)不可達(dá)問題是人工勢場法中的重點問題，已經(jīng)有許多學(xué)者提出了一些相應(yīng)的改進(jìn)辦法。郭梟鵬[17]對傳統(tǒng)人工勢場法中式(3)的勢能函數(shù)進(jìn)行改進(jìn)，增加調(diào)節(jié)因子ρc(X,XT)=|(x-xT)c|+|(y-yT)c|，可得新的勢能場函數(shù)

(6)

式中：ρ(X,XT)——移動機(jī)器人與目標(biāo)點間距離；

c——斥力修正因子。

通過對勢能場函數(shù)的修正使得移動機(jī)器人在接近目標(biāo)點位置時，斥力能夠根據(jù)與引力極間距離的不斷減小，規(guī)劃出不碰撞障礙物的路徑，直至斥力為0，達(dá)到目標(biāo)點。為解決斥力修正因子c取值問題，徐小強(qiáng)等[18]對修正因子的取值進(jìn)行分別討論。分別對c>1，c=1和0

于光金[19]通過在以移動機(jī)器人為圓點的一定半徑的圓上均勻選取16個點，通過計算每個點處的勢能函數(shù)，判斷其中勢能最小的點，使移動機(jī)器人以較小步長移動至該點，重復(fù)更新移動位置，直至到達(dá)目標(biāo)點位置。

2.3 基于算法融合的人工勢場法改進(jìn)研究

1)與RRT算法融合。快速拓展隨機(jī)數(shù)算法[17](Rapidly-exploring Random Tree algorithm,RRT)是一種適用于二維以及更高維度的搜索算法，常應(yīng)用于機(jī)械臂等復(fù)雜空間環(huán)境的路徑規(guī)劃。RRT算法的基本思想就是快速擴(kuò)張樹杈結(jié)構(gòu)形成路徑來搜索尚未到達(dá)的空間，以找到合適的可行路徑。

算法融合主要通過人工勢場法進(jìn)行路徑規(guī)劃，再利用RRT算法的擴(kuò)展樹結(jié)構(gòu)以實現(xiàn)逃離局部極小值區(qū)域。當(dāng)通過定量的判斷確定已陷入局部極小點時，將路徑規(guī)劃算法切換為RRT算法。通過判斷移動機(jī)器人與逃離后的障礙物的距離判斷是否要切換為傳統(tǒng)人工勢場法，直到抵達(dá)目標(biāo)點。既解決了移動機(jī)器人在運行空間的局部極小值問題，也解決RRT算法路徑規(guī)劃中存在的隨機(jī)性大的問題。

2)與模擬退火算法融合。模擬退火(Simulated Annealing)[20]算法最早由Metropolis等于1953年提出。模擬退火算法是通過賦予搜索過程一種實時變換且最終趨于零的概率突跳性，從而可有效避免陷入局部極小并最終趨于全局最優(yōu)的串行結(jié)構(gòu)的優(yōu)化算法，算法的流程如圖7所示。

圖7 基于模擬退火的人工勢場法流程圖Fig.7 Flow chart of artificial potential field method based on simulated annealing

模擬退火與人工勢場法算法融合，既能解決移動機(jī)器人局部極小值問題，并能通過模擬退火能夠跳出極小值的優(yōu)勢解決目標(biāo)不可達(dá)問題[21]。

3)與粒子群算法融合。粒子群算法(Particle Swarm Optimization，PSO)是一種模擬鳥群覓食行為的群智能算法，算法的基本思想是模擬鳥群在尋找食物時所表現(xiàn)出來的協(xié)作和信息共享。其具有參數(shù)少，運算快，局部搜索能力強(qiáng)的優(yōu)點，但也存在全局搜索能力差，易陷入局部最小值的缺點。因此在與人工勢場法進(jìn)行算法融合時，多將其應(yīng)用于多障礙物分布于目標(biāo)附近的目標(biāo)不可達(dá)問題和在障礙物前出現(xiàn)振蕩的問題[22]，通過該種算法融合能夠規(guī)劃出平滑且魯棒性強(qiáng)的路徑。

3 人工勢場法的總結(jié)與展望

許多學(xué)者對上述的缺陷進(jìn)行研究，以增加人工勢場法的適用范圍及運行可靠性。

3.1 人工勢場法的總結(jié)

人工勢場法在移動機(jī)器人路徑規(guī)劃中得到了廣泛的應(yīng)用。許多學(xué)者提出了有效的改進(jìn)措施，并對上述內(nèi)容進(jìn)行總結(jié)，如表1所示。

表1 改進(jìn)的人工勢場法的優(yōu)缺點比較Tab.1 Comparison of advantages and disadvantages of improved artificial potential field method

3.2 人工勢場法的展望

人工勢場法在工業(yè)中主要用于AGV小車的路徑規(guī)劃問題，現(xiàn)如今在農(nóng)業(yè)中也有著很廣泛的應(yīng)用場景。在中國“十四五”智能農(nóng)機(jī)和智慧農(nóng)業(yè)要求下，一批能夠利用計算機(jī)和傳感器技術(shù)的自動駕駛算法，已經(jīng)逐漸實現(xiàn)在農(nóng)業(yè)生產(chǎn)中的應(yīng)用，利用這種實時可視化的展示技術(shù)，能夠?qū)崿F(xiàn)農(nóng)業(yè)生產(chǎn)的遠(yuǎn)程管控。人工勢場法作為自動駕駛算法中應(yīng)用較廣的技術(shù)，與同類的路徑規(guī)劃算法相比具有計算量小，實時性強(qiáng)，適應(yīng)性好等優(yōu)點，更加適用于具有一定規(guī)模的設(shè)施蔬菜生產(chǎn)領(lǐng)域的裝備機(jī)器人；相比于常規(guī)的手動控制方法，人工勢場法具有更好的運行穩(wěn)定性以及運行的精確性，并且能在一定程度上降低對人工操控機(jī)器人的依賴并提高效率。

相比于其他路徑規(guī)劃算法，人工勢場法在農(nóng)業(yè)領(lǐng)域的研究較少，可供參考的適用于農(nóng)業(yè)場景的改進(jìn)方法較少。算法融合是現(xiàn)階段提高算法效率及提高算法可行性最好的辦法。但現(xiàn)存的融合算法中的融合策略和算法運行選擇機(jī)制缺乏深入的研究，因此需要對該方向進(jìn)一步的探索。

4 結(jié)論

本文首先介紹了人工勢場法的工作機(jī)制，將障礙與目標(biāo)分別看成引力和斥力，利用計算合力的方式實現(xiàn)對路徑的實時規(guī)劃，但人工勢場法較容易出現(xiàn)局部最小點位置問題而無法得出下一步移動位置，因此根據(jù)出現(xiàn)的局部極小值和目標(biāo)不可達(dá)問題進(jìn)行了改進(jìn)方法的原理分析和總結(jié)。

其中，針對局部極小點問題可以通過障礙物連接法、Follow-Wall算法和虛擬目標(biāo)點的方式解決；針對目標(biāo)不可達(dá)問題采用設(shè)置修正參數(shù)和進(jìn)行局部最優(yōu)搜索的方式解決。然后根據(jù)現(xiàn)有的算法融合方式，對人工勢場法與RRT算法、模擬退火算法、粒子群算法的融合進(jìn)行分析，并闡述其適用情況。人工勢場法作為自動駕駛算法中應(yīng)用較廣的技術(shù)，與同類的路徑規(guī)劃算法相比具有計算量小，實時性強(qiáng)，適應(yīng)性好等優(yōu)點，更加適用于具有一定規(guī)模的設(shè)施蔬菜生產(chǎn)領(lǐng)域的農(nóng)業(yè)裝備機(jī)器人。

最后通過對多種改進(jìn)方法進(jìn)行比較，對農(nóng)業(yè)機(jī)器人路徑規(guī)劃所需滿足的實時性以及障礙物的多變性進(jìn)行應(yīng)用展望，可以利用現(xiàn)有的算法融合研究，結(jié)合農(nóng)業(yè)生產(chǎn)的實際情況，對不同農(nóng)業(yè)生產(chǎn)應(yīng)用場合的融合算法選擇機(jī)制進(jìn)行深入研究，以滿足現(xiàn)代農(nóng)業(yè)生產(chǎn)中對機(jī)器人路徑規(guī)劃的需求。