楊旭海，周文皓，李育峰，戚小琛，張茜

(石河子大學(xué)機(jī)械電氣工程學(xué)院,新疆石河子,832003)

0 引言

隨著我國農(nóng)業(yè)技術(shù)不斷發(fā)展,傳統(tǒng)農(nóng)業(yè)、林果業(yè)采摘作業(yè)逐漸面臨人工成本上漲,勞動(dòng)力短缺等問題,以往的人工采收模式已經(jīng)很難滿足現(xiàn)代農(nóng)業(yè)的需求,同時(shí),隨著機(jī)器人技術(shù)的快速發(fā)展與普及,高性能機(jī)械臂被設(shè)計(jì)用來替代人工從事沉重、單調(diào)的勞作,在農(nóng)業(yè)采摘領(lǐng)域有著巨大的應(yīng)用前景。

作為采摘機(jī)械臂控制算法的核心,路徑規(guī)劃的目標(biāo)是在最短時(shí)間和距離代價(jià)下,在有限的作業(yè)范圍內(nèi)找到一條從起點(diǎn)到終點(diǎn)的安全無碰撞路徑,其根本目的是利用最小工作空間和最優(yōu)耗能達(dá)到最高的工作效率,其設(shè)計(jì)的先進(jìn)程度直接關(guān)系到采摘機(jī)械臂的作業(yè)效率、耐用性和采收精度。

首先對比了目前在農(nóng)產(chǎn)品采摘領(lǐng)域應(yīng)用較為廣泛的機(jī)械臂路徑規(guī)劃算法,然后詳細(xì)分析了各類算法的技術(shù)特點(diǎn)以及國內(nèi)外學(xué)者提出的改進(jìn)方案,最后引出現(xiàn)有算法存在問題,局限性以及各類算法的適用場景,并對采摘機(jī)械臂路徑規(guī)劃技術(shù)未來發(fā)展趨勢進(jìn)行深入探討。

1 路徑規(guī)劃算法研究現(xiàn)狀與分類

根據(jù)采摘機(jī)械臂路徑規(guī)劃算法的規(guī)劃方式可以將其分為局部路徑規(guī)劃和全局路徑規(guī)劃(表1),其中局部路徑規(guī)劃主要針對機(jī)械臂當(dāng)前作業(yè)的局部空間信息,這類算法具有良好的避障能力和動(dòng)態(tài)規(guī)劃性能,但對于機(jī)械臂硬件要求較高,同時(shí),局部路徑規(guī)劃對環(huán)境誤差和噪聲有較高的魯棒性,能對規(guī)劃結(jié)果進(jìn)行實(shí)時(shí)反饋與重規(guī)劃,但是因?yàn)槿狈θ汁h(huán)境信息,規(guī)劃結(jié)果可能不是最優(yōu)的,而全局路徑規(guī)劃是在已知的環(huán)境中,給機(jī)械臂規(guī)劃一條路徑,路徑規(guī)劃的精度取決于周圍環(huán)境獲取的精確性,全局路徑規(guī)劃可以找到最優(yōu)解,但是需要預(yù)先知道環(huán)境的準(zhǔn)確信息,但是面對動(dòng)態(tài)路徑,無法做出相應(yīng)的校正。

表1 局部路徑規(guī)劃與全局路徑規(guī)劃對比Tab. 1 Comparison between local path planning and global path planning

基于局部路徑與全局路徑規(guī)劃的概念,采摘機(jī)械臂路徑規(guī)劃算法又可以分為基于群優(yōu)化理論的遺傳算法、粒子群算法、蟻群算法等;基于最優(yōu)化理論的人工勢場算法;基于圖搜索法的A*算法和Dijkstra算法以及基于采樣法的快速擴(kuò)展隨機(jī)數(shù)算法(RRT)。

2 機(jī)械臂路徑規(guī)劃算法

2.1 群優(yōu)化算法

群優(yōu)化算法的原理是在空間內(nèi)設(shè)置多個(gè)個(gè)體,將這些個(gè)體組成一個(gè)群體進(jìn)行搜索,得到最優(yōu)解,遺傳算法中的種群設(shè)定、蟻群算法中的螞蟻種群、粒子群算法的粒子群都體現(xiàn)了群優(yōu)化算法的思想。其對比情況見表2。

表2 群優(yōu)化算法對比Tab. 2 Comparison of group optimization algorithms

2.1.1 遺傳算法

20世紀(jì)70年代,美國學(xué)者John holland基于達(dá)爾文生物進(jìn)化論提出了一種生物進(jìn)化過程搜索最優(yōu)解的方法——遺傳算法,該算法將問題的求解過程轉(zhuǎn)換成類似生物的進(jìn)化、變異過程,在求解復(fù)雜的組合優(yōu)化問題時(shí),可以融合其他優(yōu)化算法,得到更加優(yōu)質(zhì)的優(yōu)化結(jié)果。

West等[1]基于遺傳算法開發(fā)了一種針對機(jī)械臂單一關(guān)節(jié)參數(shù)測量進(jìn)而推廣到其他關(guān)節(jié)參數(shù)的機(jī)制,具有動(dòng)態(tài)參數(shù)估計(jì)能力,對機(jī)械臂建模過程進(jìn)行了優(yōu)化,Tang等[2]利用Matlab遺傳算法優(yōu)化工具箱對機(jī)械臂進(jìn)行優(yōu)化,在考慮機(jī)械臂結(jié)構(gòu)強(qiáng)度和軸承安裝空間的同時(shí)為機(jī)械臂路徑規(guī)劃過程提供了有效幫助。王懷江等[3]提出了一種基于改進(jìn)遺傳算法的機(jī)械臂路徑優(yōu)化方法,與傳統(tǒng)算法相比,改進(jìn)算法的收斂速度提高了46.15%,路徑縮短了45.99%,系統(tǒng)運(yùn)行時(shí)間減少了25.80%,有效提高了系統(tǒng)效率,這些應(yīng)用遺傳算法的優(yōu)化方案,對采摘領(lǐng)域機(jī)械臂路徑規(guī)劃優(yōu)化具有一定的參考價(jià)值。

為了提高果蔬采摘機(jī)器人的避障和路徑規(guī)劃能力,實(shí)現(xiàn)機(jī)器人智能化、輕量化的設(shè)計(jì),熊瓊等利用遺傳算法對路徑規(guī)劃進(jìn)行優(yōu)化,實(shí)現(xiàn)復(fù)雜環(huán)境中的路徑搜索功能,障礙物識別率高達(dá)99%以上,路徑規(guī)劃的準(zhǔn)確率也在95%以上。李濤等[4]針對矮化密植果園采摘機(jī)器人多臂協(xié)同問題,將任務(wù)規(guī)劃問題歸納為異步重疊訪問域的多旅行商問題,基于遺傳算法尋找求解方法,用3種水果作為采摘對象,相較于順序規(guī)劃法和隨機(jī)遍歷法,該方法的作業(yè)遍歷時(shí)長分別縮短10.69%和27.18%、20.45%和23.33%以及12.94%和21.69%。

為了提升遺傳算法在采摘機(jī)械臂路徑規(guī)劃過程中求解優(yōu)化的性能,宋瑩瑩等將一種改進(jìn)的遺傳算法應(yīng)用在油茶果采摘機(jī)械臂中,改進(jìn)后的算法能夠明顯優(yōu)化機(jī)械臂的工作空間,整體指標(biāo)提升了63.49%,為后續(xù)路徑規(guī)劃算法改進(jìn)提供了數(shù)據(jù)參考。

2.1.2 粒子群算法

粒子群(PSO)算法作為群優(yōu)化算法的熱門研究點(diǎn)之一,最早由Kenned和Eberhart于1995年提出,與其他群優(yōu)化算法類似,也采用“群體”和“進(jìn)化”的概念。

在此領(lǐng)域,國內(nèi)學(xué)者基于粒子群算法對機(jī)械臂路徑規(guī)劃提出了諸多優(yōu)化方案,因其規(guī)劃精度高,在采摘領(lǐng)域有較為廣闊的應(yīng)用前景。

穩(wěn)定、高效、無損的采摘要求一直制約著自動(dòng)化采摘技術(shù)的發(fā)展,為解決這些難題,國內(nèi)外學(xué)者進(jìn)行了諸多研究,Cao等[5]提出了一種改進(jìn)的多目標(biāo)粒子群優(yōu)化算法,其規(guī)劃的路徑能夠有效完成水果采摘,平均采摘時(shí)間為25.5 s,成功率為96.67%,驗(yàn)證了PSO算法在機(jī)械臂采摘領(lǐng)域的有效性。國內(nèi)學(xué)者袁蒙恩等[6]針對復(fù)雜靜態(tài)背景下具有多約束條件的機(jī)械臂路徑規(guī)劃問題,提出了基于單目視覺的多種群粒子群算法,根據(jù)目標(biāo)物體位置演化出機(jī)械臂最優(yōu)路徑。同時(shí),為進(jìn)一步提高機(jī)械臂路徑控制精度,羅予東等[7]基于粒子群算法,采用小波神經(jīng)網(wǎng)絡(luò)算法進(jìn)行優(yōu)化,并采用群體智能對路徑進(jìn)行跟蹤,對機(jī)械臂實(shí)現(xiàn)精準(zhǔn)控制,有效提高了機(jī)械臂的路徑跟蹤性能。朱文琦提出了一種基于粒子群的控制系統(tǒng)優(yōu)化算法,以提高采摘機(jī)械臂的控制效率,研究團(tuán)隊(duì)以青椒為作業(yè)對象,通過比對采用與不采用粒子群算法時(shí)機(jī)械臂末端路徑規(guī)劃距離和采摘精度,證明了采用粒子群算法可以有效提高果實(shí)采摘的定位精度,縮短移動(dòng)距離,對提高采摘效率作用顯著。龐國友等[8]為了提高油茶果采摘機(jī)械臂的綜合性能,將粒子群算法與退火算法相融合,并利用改進(jìn)后的算法進(jìn)行油茶果采摘機(jī)械臂參數(shù)優(yōu)化,為后續(xù)采摘機(jī)械臂及其算法優(yōu)化提供了數(shù)據(jù)支持。

2.1.3 蟻群算法

蟻群算法作為一種概率型算法。由意大利學(xué)者M(jìn)arco Dorigo于1992年提出,靈感源于蟻群在覓食過程中的路徑搜索行為,是最為成功的群體智能算法之一。原艷芳等[9]使用蟻群算法進(jìn)行名優(yōu)茶采摘機(jī)械臂的路徑規(guī)劃,通過改變自適應(yīng)調(diào)節(jié)信息素濃度值和迭代終止條件,可改善基本蟻群算法搜索時(shí)間較長、易陷入局部最優(yōu)等問題,有效提高機(jī)械臂采摘過程中全局搜索能力和計(jì)算效率。Baghli等[10]利用蟻群算法作為優(yōu)化工具,利用其魯棒搜索性,在機(jī)械臂運(yùn)動(dòng)過程中,規(guī)劃出最優(yōu)路徑。黃玲等基于改進(jìn)的蟻群算法規(guī)劃了果蔬采摘機(jī)器人三維路徑,大大地提高了路徑質(zhì)量,說明改進(jìn)蟻群算法穩(wěn)定性強(qiáng),可靠性高。

采摘機(jī)械臂常常需要作業(yè)于障礙物密集的果園中,王江華等[11]針對狹窄空間中機(jī)械臂的路徑規(guī)劃問題,提出了一種改進(jìn)型蟻群優(yōu)化算法,通過對傳統(tǒng)蟻群算法概率分布、路徑二次優(yōu)化、淘汰機(jī)制等方面進(jìn)行改進(jìn),增強(qiáng)了系統(tǒng)的魯棒性,能夠明顯提高機(jī)械臂在復(fù)雜環(huán)境下的適應(yīng)能力。

為提高蟻群算法采摘時(shí)的路徑規(guī)劃效率,提高采摘速度,苑嚴(yán)偉等[12]對蟻群算法進(jìn)行了相應(yīng)的改進(jìn),改進(jìn)后的算法迭代次數(shù)僅為基本算法的25.3%,而路徑長度是基本算法的94.3%,為后續(xù)蟻群算法在采摘領(lǐng)域的改進(jìn)提供了理論依據(jù)。陳鑫等[13]以柑橘為采摘對象,引入了隨時(shí)間改變的自適應(yīng)信息素濃度更新機(jī)制,提出了蟻群算法的一種改進(jìn)方案,有效縮短了采摘路徑長度。

當(dāng)機(jī)械臂路徑是離散狀態(tài)時(shí),更適合采用遺傳算法,但是該算法在求解路徑過程中存在著漢明懸崖問題,粒子群算法適算法結(jié)構(gòu)簡單,計(jì)算方便,求解速度快,但是存在局部最優(yōu)問題。蟻群算法適合解決圖上搜索路徑問題,運(yùn)算量龐大,對設(shè)備硬件要求高。

2.2 人工勢場算法

人工勢場算法是由Khatib提出的一種虛擬力場法。核心思想是將機(jī)械臂在作業(yè)環(huán)境中的運(yùn)動(dòng),抽象成在人工引力場中運(yùn)動(dòng),該種算法規(guī)劃路徑的優(yōu)勢在于路徑平滑、安全,具有良好的魯棒性,但該方法也存在局部最優(yōu)問題。

針對采摘機(jī)械臂在野外作業(yè)環(huán)境中,面臨采摘任務(wù)數(shù)量多,目標(biāo)與障礙物位置隨機(jī)性強(qiáng)等問題,熊俊濤等[14]引入人工勢場算法,利用目標(biāo)吸引、障礙排斥的思想建立獎(jiǎng)懲函數(shù),優(yōu)化路徑長度,提高了采摘效率,通過仿真測試,采摘任務(wù)成功率達(dá)96.7%以上。

針對采摘機(jī)器人在果園作業(yè)時(shí),果樹較大冠層障礙物易影響機(jī)械臂路徑規(guī)劃等問題,胡廣銳等[15]改進(jìn)了人工勢場算法,優(yōu)化后的路徑將障礙物識別最短距離由0.156 m提高至0.863 m,該優(yōu)化方法具備實(shí)時(shí)優(yōu)化路徑的功能,這種規(guī)劃方法同樣為采摘機(jī)械臂的路徑優(yōu)化提供了思路。姬偉等[16]針對非結(jié)構(gòu)化環(huán)境下采摘機(jī)械臂的實(shí)時(shí)避障問題,提出了一種基于改進(jìn)人工勢場算法的避障策略,該方法在保留傳統(tǒng)人工勢場算法易于實(shí)現(xiàn)、結(jié)構(gòu)簡單的基礎(chǔ)上,針對其存在的局部極小點(diǎn)、陷進(jìn)區(qū)等問題,結(jié)合果樹生長環(huán)境中障礙物的特點(diǎn),通過引入虛擬目標(biāo)點(diǎn)使搜索過程跳出局部最優(yōu)的極小點(diǎn),從而有效提高了機(jī)械臂路徑規(guī)劃的質(zhì)量。Park等[17]為了解決未知環(huán)境下機(jī)械臂路徑實(shí)時(shí)規(guī)劃問題,提出了一種基于雅可比矩陣與修正勢場相結(jié)合的算法。這種算法可以更加便捷的進(jìn)行機(jī)械臂路徑規(guī)劃。曹博等[18]針對傳統(tǒng)人工勢場算法應(yīng)用于機(jī)械臂避障時(shí)無法約束各關(guān)節(jié)位姿、易陷入局部極小值等問題,提出一種改進(jìn)算法,采用線段球體包絡(luò)盒模型進(jìn)行碰撞檢測,在關(guān)節(jié)空間內(nèi)求解虛擬目標(biāo)角度并采用高斯函數(shù)建立虛擬引力勢場處理局部極小問題,改進(jìn)算法可以引導(dǎo)機(jī)械臂逃離局部極小值點(diǎn)并完成避障,同時(shí)提高避障結(jié)束時(shí)各關(guān)節(jié)的定位精度,該方法可以有效應(yīng)用于采摘機(jī)械臂路徑規(guī)劃算法的改進(jìn)中。Wang等[19]提出了一種改進(jìn)的人工勢場避障方法,在避障過程中考慮了機(jī)械臂的姿態(tài),無論初始姿態(tài)和目標(biāo)姿勢之間的差異如何,機(jī)械臂都能以合理速度到達(dá)目標(biāo)位姿,Zhou等[20]針對障礙物環(huán)境中的碰撞問題,將改進(jìn)的人工勢場算法應(yīng)用于機(jī)械臂碰撞檢測與路徑規(guī)劃中,并通過仿真驗(yàn)證了該方法可以有效提高采摘效率,這兩種對人工勢場改進(jìn)的策略可以為采摘過程中機(jī)械臂如何規(guī)避枝干、葉片到達(dá)最優(yōu)作業(yè)點(diǎn)提供改進(jìn)思路。

圖1 人工勢場算算法示意圖

2.3 圖搜索算法

2.3.1 Dijkstra算法

Dijkstra算法解決兩個(gè)點(diǎn)之間最短路徑的問題十分有效,Sunita等[21]對Dijkstra算法進(jìn)行動(dòng)態(tài)化處理,有助于提高算法的有效性,在規(guī)劃時(shí)間和內(nèi)存占用方面進(jìn)行了優(yōu)化。Tan等[22]提出了一種基于Dijkstra算法的改進(jìn)算法,該算法在全局最優(yōu)路徑規(guī)劃具有優(yōu)異的性能。Rafael等[23]提出了Dijkstra最短路徑搜索算法的一種改進(jìn)算法,與啟發(fā)式算法相比,采用該方法可以在相似甚至更短的時(shí)間內(nèi)獲得最優(yōu)路徑。Ji等[24]針對蘋果收獲機(jī)械臂實(shí)時(shí)避障路徑規(guī)劃問題,在動(dòng)態(tài)非結(jié)構(gòu)環(huán)境下,利用改進(jìn)的Dijkstra算法用于蘋果采摘機(jī)械臂初始路徑規(guī)劃,再用改進(jìn)的蟻群算法用于優(yōu)化初始路徑,并通過實(shí)驗(yàn)證明該方法簡單易行,具有較好的實(shí)用價(jià)值,機(jī)械臂可以在較短的時(shí)間內(nèi)避開樹枝成功采摘蘋果。

Dijkstra算法的改進(jìn)趨勢是加入啟發(fā)式算法的循跡策略以減少最短路徑搜索的運(yùn)行時(shí)間。Dijkstra算法雖然經(jīng)典的最短路徑搜索算法之一,但是該算法并不適用于大型圖中的最短路徑搜索。

2.3.2 A*算法

A*算法是求解靜態(tài)環(huán)境中最短路徑最為有效的方法之一,傳統(tǒng)的A*算法在機(jī)械臂的路徑規(guī)劃過程中可能存在無限循環(huán)和搜索數(shù)據(jù)量龐大等問題。針對這些問題Wang等[25]提出了一種改進(jìn)的A*算法,即在搜索過程中應(yīng)用可變步段搜索,基于對碰撞檢測的分析,可以實(shí)現(xiàn)自由空間,使機(jī)械臂能夠避免與障礙物的碰撞。與傳統(tǒng)的A*相比,改進(jìn)后的算法搜索點(diǎn)較少,執(zhí)行效率更高。

(a) 第一次循跡

(b) 第二次循跡

(c) 第三次循跡

根據(jù)機(jī)械臂和障礙物的幾何特征,賈慶軒等[26]利用A*算法實(shí)現(xiàn)了機(jī)械臂的無碰撞路徑規(guī)劃。張?jiān)S有等[27]基于位置代價(jià)設(shè)計(jì)了針對機(jī)械臂避障路徑規(guī)劃的A*算法的,該算法運(yùn)算量小且計(jì)算效率高。Chen等[28]提出一種基于差分進(jìn)化和改進(jìn)的A*的智能尋徑方法算法。該方法通過對異常條件的精確濾波實(shí)現(xiàn)快速路徑搜索,以達(dá)到較高的收斂性率。Xu等[29]提出了一種基于A*算法的路徑規(guī)劃方法,對機(jī)械臂的運(yùn)動(dòng)性能進(jìn)行了定量分析和優(yōu)化,上述幾種算法優(yōu)化方案為基于A*算法的采摘機(jī)械臂路徑規(guī)劃提供了改進(jìn)思路。

2.4 概率地圖算法(PRM)

概率地圖是一種可以進(jìn)行快速路徑規(guī)劃的自由空間表示方法。在得到概率地圖后,路徑規(guī)劃的問題隨即轉(zhuǎn)變?yōu)樵诟怕实貓D中尋找一條從起點(diǎn)到達(dá)終點(diǎn)的合適路徑問題。

機(jī)械臂在采摘果蔬的過程中常常需要在狹小的作業(yè)空間內(nèi)規(guī)劃最優(yōu)路徑,在面對復(fù)雜環(huán)境,尤其是構(gòu)型空間存在狹長的通道時(shí),傳統(tǒng)運(yùn)動(dòng)規(guī)劃算法性能大大下降,規(guī)劃時(shí)間長而且失敗率高,孫明鏡等[30]針對這些難題提出了一種面向狹窄空間的機(jī)械臂快速穩(wěn)定路徑規(guī)劃算法,采用示教路徑為啟發(fā)項(xiàng),結(jié)合非均勻采樣和均勻采樣,離線生成PRM隨機(jī)路圖,通過在線圖搜索查找最終可執(zhí)行路徑。蔡健榮等[31]針對動(dòng)態(tài)非結(jié)構(gòu)化環(huán)境下的柑橘采摘機(jī)器人實(shí)時(shí)路徑規(guī)劃問題,利用雙目立體視覺技術(shù)獲取柑橘及障礙物的三維信息,對采摘作業(yè)區(qū)域進(jìn)行虛擬重建,并在此基礎(chǔ)上采用單次查詢、雙向采樣與延遲碰撞檢測相結(jié)合的SBL-PRM算法對柑橘采摘機(jī)械臂進(jìn)行避障路徑規(guī)劃,該方法適用于動(dòng)態(tài)非結(jié)構(gòu)化環(huán)境下的采摘機(jī)械臂實(shí)時(shí)避障。鄒宇星等[32]針對采摘機(jī)械臂在不確定的環(huán)境中進(jìn)行采摘作業(yè)的要求,提出了一種基于改進(jìn)概率地圖PRM算法的機(jī)械臂避障路徑規(guī)劃方法。相比傳統(tǒng)PRM算法,改進(jìn)算法速度提高22.2%,能夠有效地實(shí)現(xiàn)機(jī)械臂無碰撞路徑規(guī)劃。

2.5 快速擴(kuò)展隨機(jī)數(shù)算法(RRT)

快速擴(kuò)展隨機(jī)樹(Rapidly-exploring Random Tree,RRT),是基于數(shù)據(jù)結(jié)構(gòu)的單一查詢式算法,主要用于路徑規(guī)劃、虛擬現(xiàn)實(shí)等方向的研究?？焖贁U(kuò)展隨機(jī)樹采用一種特殊的增量方式進(jìn)行構(gòu)造,因此,該算法在采摘機(jī)械臂路徑規(guī)劃領(lǐng)域應(yīng)用前景廣闊。

Cao等[33]為了實(shí)現(xiàn)采摘機(jī)械臂在動(dòng)態(tài)和非結(jié)構(gòu)化環(huán)境中的避障問題,提出了改進(jìn)的快速探索隨機(jī)樹(RRT)算法,此設(shè)計(jì)采用目標(biāo)重力的思想,加速了路徑搜索的速度,試驗(yàn)表明,該算法規(guī)劃的無碰撞路徑可以成功地將機(jī)械臂驅(qū)動(dòng)到作業(yè)位置,而不發(fā)生任何碰撞,路徑實(shí)現(xiàn)時(shí)間0.47 s,成功率100%,其路徑的長度優(yōu)化后縮短20%,Ye等[34]針對RRT算法在高維環(huán)境下存在的隨機(jī)性、轉(zhuǎn)換速度慢等缺點(diǎn),引入了目標(biāo)重力概念和自適應(yīng)系數(shù)調(diào)整方法無碰撞拾取姿態(tài),改進(jìn)后的算法平均路徑搜索時(shí)間為4.24 s,實(shí)驗(yàn)室環(huán)境下路徑確定成功率為100%,所提出的無碰撞運(yùn)動(dòng)規(guī)劃方法可以有效使采摘機(jī)械臂避開工作空間中的障礙物,高效完成采摘任務(wù)。Schuetz等[35]以甜椒作為采摘對象,引入了一種基于RRT算法的全局離線優(yōu)化方案,該方案能夠在極短時(shí)間內(nèi)尋找到最優(yōu)路徑。劉頓等[36]針對目前采摘機(jī)械臂采摘多次行程規(guī)劃效率低、耗時(shí)長、路徑非最優(yōu)的問題,提出一種基于Informed-RRT*改進(jìn)的柑橘采摘機(jī)械臂運(yùn)動(dòng)規(guī)劃算法,在算法中引入了啟發(fā)性的節(jié)點(diǎn)采樣策略,提高了最優(yōu)路徑的收斂速度,改進(jìn)算法路徑搜索時(shí)間縮短了88%,節(jié)點(diǎn)數(shù)縮短42%,平均迭代次數(shù)下降64%,路徑規(guī)劃成功率約為96%,算法平均規(guī)劃時(shí)間0.81 s,規(guī)劃成功率提高11%,路徑成本優(yōu)化16%。

針對多自由度果蔬采摘機(jī)械臂運(yùn)動(dòng)路徑規(guī)劃速度慢、效率低、路徑成本高的問題,張勤等[37]提出了一種柯西目標(biāo)引力雙向RRT*算法,相比于傳統(tǒng)RRT*-connect算法,改進(jìn)算法的路徑成本縮短5.5%,運(yùn)行時(shí)間降低71.8%,采樣節(jié)點(diǎn)數(shù)下降64.2%,單次搜索時(shí)間0.33 s,相比于原始算法,路徑成本降低12.6%,運(yùn)行時(shí)間減少了69.2%,擴(kuò)展節(jié)點(diǎn)數(shù)減少76.3%。

為提升機(jī)械臂在非結(jié)構(gòu)性環(huán)境中進(jìn)行避障采摘作業(yè)的要求,陽涵疆等[38]采用RRT算法提出了一種基于關(guān)節(jié)構(gòu)形空間的混聯(lián)采摘機(jī)械臂避障路徑規(guī)劃算法,所提出的算法搜索的避障路徑能夠驅(qū)動(dòng)采摘機(jī)械臂避開工作空間內(nèi)的障礙物,到達(dá)作業(yè)目標(biāo)點(diǎn),使串聯(lián)機(jī)械臂擁有全局避障路徑規(guī)劃的能力,體現(xiàn)了實(shí)時(shí)避障的設(shè)計(jì)思路。

在采摘過程中機(jī)械臂有時(shí)需要深入樹冠內(nèi)部進(jìn)行采摘,而在樹冠內(nèi)眾多枝干往往構(gòu)成一個(gè)個(gè)封閉的多邊形通道,比起單個(gè)枝條的障礙物,封閉多邊形障礙物更加難以避開,需要更長的時(shí)間進(jìn)行規(guī)劃。針對此問題,馬冀桐等[39]通過對構(gòu)型空間的離線構(gòu)建,分析了封閉多邊形障礙物在構(gòu)型空間的拓?fù)浣Y(jié)構(gòu)性質(zhì),根據(jù)這一性質(zhì),對雙向快速擴(kuò)展隨機(jī)樹算法(RRT-connect)進(jìn)行改進(jìn),提出了一種基于構(gòu)型空間先驗(yàn)知識引導(dǎo)點(diǎn)的RRT-connect算法與傳統(tǒng)RRT-connect算法相比規(guī)劃時(shí)間分別縮短了51%、86%,該算法對封閉障礙物和未封閉障礙物均有較好的避障效果,平均路徑規(guī)劃時(shí)間為1.263 s,成功率為91%,可以為柑橘采摘機(jī)器人在不同環(huán)境的運(yùn)動(dòng)規(guī)劃問題提供參考。

3 路徑規(guī)劃算法比較分析

不同的路徑規(guī)劃算法針對不同的采摘環(huán)境其收斂速度和多樣性能方面的表現(xiàn)各有利弊,單一算法或者固定的路徑規(guī)劃模式已經(jīng)很難適應(yīng)現(xiàn)代農(nóng)業(yè)自動(dòng)化采摘面臨的問題。本文主要就多種采摘機(jī)械臂路徑規(guī)劃算法,重點(diǎn)分析各類規(guī)劃算法的優(yōu)缺點(diǎn),局限性以及適用場景(表3),最后對采摘機(jī)械臂路徑規(guī)劃技術(shù)未來改進(jìn)提出建議。

表3 路徑規(guī)劃算法對比Tab. 3 Comparison of path planning algorithms

1) 群優(yōu)化算法。該類算法適應(yīng)性強(qiáng)、易于重構(gòu),具有較強(qiáng)的魯棒性并且隱含負(fù)反饋機(jī)制,在采摘機(jī)械臂路徑規(guī)劃過程中,群優(yōu)化算法需要依賴較為完善動(dòng)態(tài)環(huán)境評估機(jī)制,運(yùn)算量大,這就對機(jī)械臂控制系統(tǒng)乃至整個(gè)采摘機(jī)器人的環(huán)境感知性能提出了較高的要求,間接性提高了采摘機(jī)器人的普及成本,在機(jī)械臂的實(shí)時(shí)控制,特別是動(dòng)態(tài)路徑規(guī)劃中優(yōu)勢不明顯。因此,針對果實(shí)采摘過程中的動(dòng)態(tài)路徑規(guī)劃是未來研究的方向。

2) 人工勢場算法。人工勢場算法在數(shù)學(xué)描述上簡潔、美觀,人工勢場算法結(jié)構(gòu)簡單,能夠有效提高路徑規(guī)劃的實(shí)時(shí)性,然而傳統(tǒng)人工勢場算法在規(guī)劃路徑時(shí),存在障礙物邊界勢場不完善的問題,無法約束采摘機(jī)械臂的整體位姿,容易引起局部最小值,使算法最終收斂性出現(xiàn)問題,較為有效的解決方案是建立統(tǒng)一的勢能函數(shù),人工勢場算法要求在路徑上的障礙物都必須是規(guī)則的,因?yàn)闊o規(guī)則障礙物會(huì)導(dǎo)致的運(yùn)算量龐大,但這樣對作業(yè)環(huán)境就有嚴(yán)格的要求,降低了適用性,因此,這也是目前國內(nèi)外學(xué)者對人工勢場算法改進(jìn)的熱門方向。

3) 圖搜索算法。圖搜索類算法主要利用已知的環(huán)境地圖和地圖中障礙物的信息,構(gòu)建出起始點(diǎn)到終點(diǎn)的路徑,包括深度優(yōu)先和廣度優(yōu)先兩個(gè)方向,該類算法搜索能力強(qiáng),其中Dijkstra算法采用廣度優(yōu)先搜索,是解決有向圖和無向圖的單源最短路徑的有效方法,研究的主要方向在于如何提升搜索效率,減少不必要的搜索,同時(shí)提高搜索的準(zhǔn)確性。A*算法則利用啟發(fā)該類算法能夠有效提高路徑的搜索效率,但需要對全局路徑進(jìn)行在線建模,難以滿足動(dòng)態(tài)采摘環(huán)境下機(jī)械臂作業(yè)的避障要求。Dijkstra算法能得出最短路徑的最優(yōu)解,但遍歷節(jié)點(diǎn)較多,所以效率相對低。由于Dijkstra是層層向外擴(kuò)展的,因此搜索區(qū)域很大,時(shí)間較慢,但準(zhǔn)確度較高,可以保證得到的路徑一定是最短的,因此,Dijkstra算法更適用于對采摘機(jī)器所在區(qū)域進(jìn)行完整搜索,再結(jié)合其他算法進(jìn)行局部路徑規(guī)劃,但是Dijkstra算法不能有負(fù)權(quán),因此只能單向?qū)ぴ?相比Dijkstra算法,A*算法搜索效率較高,且能得到最優(yōu)解,相應(yīng)的A*算法的缺點(diǎn)在于其拓展節(jié)點(diǎn)的隨機(jī)性,沒有關(guān)于全局的位置信息。因此它搜索的節(jié)點(diǎn)數(shù)量會(huì)較多,這種方法犧牲了一定的空間代價(jià)達(dá)到了速度與完備兼得的優(yōu)勢。

4) 概率地圖法(PRM)。概率地圖法的思路是建立柵格地圖生成離散空間,能用相對少的隨機(jī)采樣點(diǎn)來找到一個(gè)解,動(dòng)態(tài)規(guī)劃性能優(yōu)秀,對多數(shù)采摘作業(yè)而言,其采樣點(diǎn)足以覆蓋大部分可行的空間,在算法機(jī)理上可以確保一定找到一條路徑,但是,由于采樣點(diǎn)是均勻產(chǎn)生的,因此可能造成某些狹窄區(qū)域采樣點(diǎn)數(shù)較少,狹窄區(qū)域無法聯(lián)通,導(dǎo)致路徑搜索失敗,長時(shí)間路徑搜索會(huì)造成路徑規(guī)劃的不穩(wěn)定,由于采摘作業(yè)多在枝干、葉片等多種障礙物的狹窄空間內(nèi)循跡,這樣就極大限制了PRM算法在采摘機(jī)械臂路徑規(guī)劃算法的應(yīng)用,因此,PRM算法更多的是應(yīng)用于搭載機(jī)械臂的負(fù)載平臺(tái)在農(nóng)場或果園中的路徑規(guī)劃,但隨著高性能計(jì)算機(jī)、處理器等硬件設(shè)備的升級,通過增加采樣點(diǎn)密度,狹窄區(qū)域中節(jié)點(diǎn)數(shù)量會(huì)相應(yīng)增加,可以一定程度上提高循跡的成功概率。

5) 快速擴(kuò)展隨機(jī)數(shù)算法(RRT)。RRT算法及其改進(jìn)算法,因其概率完備,只要路徑存在,有足夠長的規(guī)劃時(shí)間,就能確定得到一條路徑的解,此類算法不僅適用于二維搜索,也適用于高維度動(dòng)態(tài)規(guī)劃,且不會(huì)存在局部最小值的問題,具有高效的隨機(jī)擴(kuò)展性,可快速生成可行路徑,為高維且復(fù)雜的機(jī)器人路徑規(guī)劃問題提供了一種新的解決方案,因?yàn)镽RT算法的種種優(yōu)勢,在采摘機(jī)械臂路徑規(guī)劃領(lǐng)域應(yīng)用前景廣泛。

4 采摘機(jī)械臂路徑規(guī)劃研究展望

雖然采摘機(jī)械臂路徑規(guī)劃算法在采收作業(yè)過程中已經(jīng)取得了顯著的科研成果,并廣泛應(yīng)用于農(nóng)業(yè)、林果業(yè)中,但隨著相關(guān)產(chǎn)業(yè)應(yīng)用場景愈發(fā)復(fù)雜,自動(dòng)化程度的不斷提高,對機(jī)械臂的應(yīng)用需求也更加智能化,本文對具有代表性和實(shí)用性的采摘機(jī)械臂路徑規(guī)劃算法進(jìn)行了綜述,并對今后采摘機(jī)械臂路徑規(guī)劃技術(shù)研究與改進(jìn)提出3點(diǎn)展望。

1) 多算法融合。隨著采摘機(jī)械臂路徑規(guī)劃算法應(yīng)用范圍日益廣泛,作業(yè)環(huán)境日益復(fù)雜,任何單一算法都無法滿足所有工作環(huán)境。各類路徑規(guī)劃算法各自具有優(yōu)點(diǎn)與特性,但都有其局限性。為滿足復(fù)雜工況下的避障要求,利用不同算法的優(yōu)勢互補(bǔ)解決不同情況下的機(jī)械臂路徑規(guī)劃問題將成為未來研究的熱點(diǎn)。

2) 提高路徑重規(guī)劃與動(dòng)態(tài)規(guī)劃性能。目前采摘機(jī)械臂路徑規(guī)劃算法研究領(lǐng)域的大多數(shù)算法只能在理想化的實(shí)驗(yàn)室環(huán)境中進(jìn)行,在實(shí)際采摘過程中,路徑規(guī)劃的狀態(tài)不再是靜態(tài)環(huán)境,因此,提高算法的環(huán)境適應(yīng)性也是目前研究的重點(diǎn)問題。針對機(jī)械臂愈發(fā)復(fù)雜的工作環(huán)境,可采用經(jīng)典算法和智能算法的混合方式,靜態(tài)環(huán)境使用傳統(tǒng)算法規(guī)劃,動(dòng)態(tài)環(huán)境和極小值問題則使用智能算法局部規(guī)劃的方式來實(shí)現(xiàn)整體路徑規(guī)劃,提高系統(tǒng)穩(wěn)定性?，F(xiàn)階段機(jī)器人技術(shù)要真正地得到廣泛應(yīng)用到復(fù)雜的農(nóng)林采摘作業(yè)中就必須提高路徑規(guī)劃技術(shù)的環(huán)境普適性,其核心問題是解決路徑的重規(guī)劃問題,加強(qiáng)動(dòng)態(tài)搜索率。

3) 局部路徑與全局路徑融合。全局路徑規(guī)劃算法是在預(yù)知的地圖環(huán)境中搜尋最優(yōu)路徑,因此多數(shù)只能應(yīng)用于預(yù)知地圖的靜態(tài)環(huán)境中,無法避開環(huán)境中的動(dòng)態(tài)障礙物。而在機(jī)械臂實(shí)際應(yīng)用中,除了特定的靜態(tài)場景,大多數(shù)室外環(huán)境都是動(dòng)態(tài)變化的,尤其是作物采收領(lǐng)域。在動(dòng)態(tài)場景中機(jī)械臂需要對同一環(huán)境內(nèi)的特征進(jìn)行反復(fù)觀測采樣,不斷地更新地圖表示,以避免地圖誤差的不斷積累,并且會(huì)讓機(jī)器人內(nèi)存資源高度消耗,勢必會(huì)影響路徑規(guī)劃的質(zhì)量,這就使得為了適應(yīng)多樣化的地圖環(huán)境,機(jī)器人必須考慮新的地圖表示方法,基于學(xué)習(xí)、采樣或者“記憶”的新型地圖表示方法為動(dòng)態(tài)環(huán)境中的全局路徑規(guī)劃算法的發(fā)展提供了有力支撐。隨著路徑規(guī)劃技術(shù)的不斷深入,采摘機(jī)械臂的應(yīng)用環(huán)境逐漸從靜態(tài)的封閉環(huán)境變化到半靜態(tài)的室外場景再變化到高度動(dòng)態(tài)的公共場所,單純以柵格圖、拓?fù)鋱D、幾何特征圖等基于局部或者全局地圖都無法滿足機(jī)械臂對環(huán)境特征的更新,因此將局部路徑與全局路徑相融合將是未來機(jī)械臂路徑規(guī)劃的熱門方向之一。

3) 雙/多機(jī)械臂協(xié)同規(guī)劃。多機(jī)械臂智能采摘路徑規(guī)劃技術(shù)有著高靈活性、易部署、高協(xié)調(diào)性,具有環(huán)境自適應(yīng)。多機(jī)械臂規(guī)劃各自最優(yōu)路徑的同時(shí)又要考慮到其他采摘機(jī)械臂的位置,這對算法的實(shí)時(shí)性、準(zhǔn)確性以及數(shù)據(jù)的交互都是不小的挑戰(zhàn),多機(jī)械臂協(xié)同作業(yè)具有多任務(wù)適用,最優(yōu)匹配、自由協(xié)同、更好的系統(tǒng)冗余度及魯棒性等特點(diǎn),未來將廣泛應(yīng)用于采摘作業(yè)的實(shí)際場景中。

5 結(jié)語

路徑規(guī)劃作為采摘機(jī)械臂控制算法的核心,從根本上決定了機(jī)械臂作業(yè)性能。雖然目前許多的路徑規(guī)劃算法取得了豐碩的研究成果,因?yàn)椴烧獧C(jī)械臂作業(yè)工況復(fù)雜,目前,尚不存在適用于所有作業(yè)環(huán)境的通用路徑規(guī)劃方案,因此,機(jī)械臂的通用性低,只能根據(jù)不同作物的采收要求和作業(yè)環(huán)境進(jìn)行算法設(shè)計(jì)與結(jié)構(gòu)適配,間接性提高了采摘機(jī)械臂的普及成本。

隨著智慧農(nóng)業(yè)的興起、機(jī)器人技術(shù)的普及、控制技術(shù)與算法的革新,未來采摘機(jī)械臂應(yīng)用的前景廣闊,相應(yīng)的路徑規(guī)劃算法也將有著良好的發(fā)展前景。