時間:2022-12-28 13:35:19來源:混沌無形
01
引言
移動機器人運動行為是由自主導(dǎo)航系統(tǒng)決定的,自主導(dǎo)航系統(tǒng)主要包含感知、規(guī)劃、控制與定位四個模塊,感知模塊是連接機器人與環(huán)境的橋梁,其作用是“閱讀、提取”環(huán)境內(nèi)容;規(guī)劃模塊是連接感知與控制的橋梁,其作用是“分析、理解”環(huán)境內(nèi)容,根據(jù)用戶目標(biāo)及需求輸出可執(zhí)行控制命令,因此感知、規(guī)劃模塊是決定導(dǎo)航系統(tǒng)智能程度的關(guān)鍵。
圖 1.1 運動規(guī)劃示意圖(圖片來源:http://wiki.ros.org/navigaTIon)
運動規(guī)劃一直是機器人領(lǐng)域非常經(jīng)典的研究熱點之一,諸多學(xué)者和研究機構(gòu)針對運動規(guī)劃中的科學(xué)問題進行了深入研究。運動規(guī)劃算法針對不同的應(yīng)用場景有著不同的研究側(cè)重點,比如游戲領(lǐng)域,游戲任務(wù)從A點運動到B點的運動規(guī)劃需求是計算消耗內(nèi)存小、計算實時性好,路徑質(zhì)量要求可能需要太高;而在全局規(guī)劃領(lǐng)域,如百度地圖等應(yīng)用,則側(cè)重研究如何快速找到一條從起點到終點的可行的路徑,并不會關(guān)注整條路徑的細節(jié)問題;而在機器人運動過程中,就需要側(cè)重關(guān)注軌跡曲線的質(zhì)量。
細心讀者可能發(fā)現(xiàn)了,這里的規(guī)劃都是依賴于地圖的,路徑是依托于地圖的,不同的地圖使用的規(guī)劃算法是有區(qū)別的,這可以在《機器人環(huán)境感知研究現(xiàn)狀簡述》中獲知不同類型的地圖及其對應(yīng)的特點、適用場景。
此外,路徑規(guī)劃中也包含路徑搜索這塊方向,路徑搜索不僅僅是用于搜索路徑,還可以用于搜索目標(biāo),比如藥物結(jié)構(gòu)的搜索,采用智能算法,給定初始條件和篩選條件,讓算法在指定區(qū)域搜索藥物分子結(jié)構(gòu)。
為提升機器人在不同場景下的自主運動能力,適用于不同環(huán)境的運動規(guī)劃算法層出不窮,本文將根據(jù)算法原理分類、研究時間排序,整理概述該研究領(lǐng)域的進展及成果。
02規(guī)劃算法研究分析
在分析之前需要先補充點概念:運動規(guī)劃、軌跡規(guī)劃和路徑規(guī)劃之間是什么關(guān)系?
路徑規(guī)劃指的是在地圖上生成一條連接起點和終點的路徑曲線,該路徑曲線不會與地圖中的障礙物相交,且均在可行區(qū)域,路徑曲線Path可以用離散的點序列表示:
式中,(xk, yk)表示地圖坐標(biāo)系下的路徑點位置。
軌跡規(guī)劃顧名思義就是在地圖上生成一條連接起點和終點的軌跡曲線,而軌跡曲線是路徑曲線和速度曲線相耦合的復(fù)合曲線,換句話說,就是軌跡曲線Traj包含了位置、速度和時間等信息,離散化后可表示為:
式中,(xt, yt)表示地圖坐標(biāo)系下的t時刻路徑點位置,而(vt, wt)表示t時刻機器人的運動速度。
運動規(guī)劃狹義上和軌跡規(guī)劃的概念非常接近,區(qū)別在于不同的機器人的運動學(xué)/動力學(xué)模型是不一樣的,比如多軸機械臂、移動機器人等,運動規(guī)劃需要做的事情是需要先規(guī)劃出上述軌跡曲線,接著結(jié)合動力學(xué)模型,將軌跡曲線轉(zhuǎn)化為每個電機的運動控制曲線,控制電機沿著該控制曲線運動,以實現(xiàn)機器人沿著規(guī)劃的目標(biāo)軌跡曲線運動。
<回歸正題>
如圖 2.1所示,運動規(guī)劃的研究主要是對多目標(biāo)多變量多約束耦合的規(guī)劃模型優(yōu)化求解,目標(biāo)需求非常多,包括模型硬約束,如軌跡曲線需要滿足機器人運動學(xué)和動力學(xué)模型約束,同時還需要滿足避障約束,也就是說該軌跡曲線的最基礎(chǔ)要求就是機器人實際上能夠跟隨運動且不會發(fā)生碰撞;而規(guī)劃需求軟約束則包實時性好、動態(tài)適應(yīng)性好、計算成本低等,這些約束根據(jù)不同的應(yīng)用場景是不一樣的,用戶體驗也是存在差異的,故而稱為軟約束。
圖 2.1 運動規(guī)劃通用模型
此外,對于具有非完整約束的移動機器人而言(見《兩輪差速驅(qū)動機器人運動模型及應(yīng)用分析》),在分布有障礙物的環(huán)境中求解最優(yōu)路徑是NP-hard問題,即對于任意場景無法保證在多項式時間內(nèi)求得最優(yōu)解,因此大部分規(guī)劃算法追求次優(yōu)解或局部最優(yōu)。
運動規(guī)劃研究歷史長久、算法相當(dāng)多,除了上述提到的約束多外,當(dāng)前運動規(guī)劃的研究難點是什么呢?
筆者認為難點之一是如何處理存在耦合關(guān)系的路徑與速度曲線的優(yōu)化問題,常用方式有三種:
1)路徑-速度完全脫離處理:僅單純生成平滑路徑,再使用曲線跟蹤算法控制機器人運動,該方法動態(tài)避障性能偏弱。
2)路徑-速度循環(huán)迭代優(yōu)化:先生成無碰撞路徑(靜態(tài)避障),再基于該路徑生成穩(wěn)定好的無碰撞速度曲線(動態(tài)避障),并通過循環(huán)迭代優(yōu)化算法生成最佳軌跡曲線,該方法降低優(yōu)化維度,提升了優(yōu)化效率。
3)路徑-速度“捆綁”優(yōu)化:綜合考慮所有的約束關(guān)系及優(yōu)化目標(biāo),生成最優(yōu)軌跡曲線,該方法生成的軌跡效果很好,但存在優(yōu)化模型構(gòu)造難度大、優(yōu)化效率不高等問題。
諸多學(xué)者針對不同應(yīng)用場景和需求,設(shè)計、改進了非常多的運動規(guī)劃算法,筆者將常見的運動規(guī)劃算法主要分為四類:圖規(guī)劃算法、空間采樣算法、曲線插值擬合算法和仿生智能算法。
接下來,筆者將從逐一介紹這四個子類規(guī)劃算法的概況。
2.1 圖規(guī)劃算法
圖規(guī)劃算法多數(shù)將環(huán)境模型離散化表達,如柵格圖等,其離散節(jié)點描述相應(yīng)狀態(tài),建立節(jié)點間聯(lián)系,并求解最優(yōu)路徑。
如圖 2.2所示,圖規(guī)劃算法根據(jù)路徑生成方式的不同分為三類,其中以圖搜索算法為主,以及BUG算法和勢場力算法。
具體相關(guān)分析可閱讀《機器人圖規(guī)劃算法研究現(xiàn)狀簡述》。
(請橫屏看圖)
圖 2.2 圖規(guī)劃算法發(fā)展路線概況
2.2 空間采樣算法
空間采樣算法按照采樣空間不同,可分為:狀態(tài)空間采樣和運動空間采樣。
如圖 2.3所示,基于狀態(tài)空間采樣的算法能夠在大面積、高緯度的空間中快速生成路徑,包括RRT和PRM類算法等,具有概率完備性,其主要步驟包括隨機采樣、度量連接、碰撞檢測和路徑查詢。
基于運動空間采樣的算法則在速度空間等距采樣,通過評價函數(shù)選擇最佳控制指令,驅(qū)動機器人運動,主要包括CVM類算法及DWA類算法等。
具體相關(guān)分析可閱讀《機器人空間采樣算法研究現(xiàn)狀簡述》。
(請橫屏看圖)
圖 2.3 空間采樣算法發(fā)展路線概況
2.3 曲線插值擬合算法
上述大部分《圖規(guī)劃算法》和《空間采樣算法》生成的路徑存在折點、急彎等曲率不連續(xù)的情況,影響了機器人運動平穩(wěn)性,因此需要綜合考慮模型硬約束與實際規(guī)劃軟需求,以提升路徑平滑度。
圖 2.4 CHOMP規(guī)劃算法
如圖 2.4所示,曲線插值擬合算法在曲線平滑控制及優(yōu)化方面有顯著的優(yōu)勢,按照曲線生成方式及其種類可分為:基于插值的規(guī)劃算法、基于特殊曲線的規(guī)劃算法及基于優(yōu)化的規(guī)劃算法三類,該類算法在自動駕駛等領(lǐng)域有著廣泛的應(yīng)用。
具體相關(guān)分析可閱讀《機器人曲線插值擬合算法研究現(xiàn)狀簡述》。
2.4 仿生智能算法
針對機器人運動規(guī)劃問題,除上述基于經(jīng)典模型的規(guī)劃算法外(《圖規(guī)劃算法》、《空間采樣算法》和《曲線插值擬合算法》),還有神經(jīng)網(wǎng)絡(luò)、模糊邏輯及基于自然靈感的算法(遺傳算法、粒子群算法、蟻群算法等),并逐漸成為研究熱點。
如圖 2.5所示,與經(jīng)典算法相比,智能算法能夠較好適應(yīng)復(fù)雜動態(tài)環(huán)境中的不確定、不完整的信息,但需要前期學(xué)習(xí)階段和較高計算成本,適用于大型機器人,如無人車等。
具體相關(guān)分析可閱讀《機器人智能仿生路徑規(guī)劃算法研究現(xiàn)狀簡述》。
圖 2.5 路徑規(guī)劃模糊系統(tǒng)架構(gòu)
03
規(guī)劃算法特性討論
在表 3-1中,筆者總結(jié)對比了不同類型算法的主要優(yōu)缺點,其應(yīng)用場景也存在差異。
圖規(guī)劃算法與空間采樣算法已經(jīng)能夠在諸多場景下的規(guī)劃生成一條無碰撞路徑,實時性和動態(tài)適應(yīng)性逐漸提升,但多數(shù)算法仍存在路徑質(zhì)量差、未考慮動力學(xué)約束等問題。
而曲線插值擬合算法正好與之配合,能夠容易生成連續(xù)性好的軌跡曲線。
多數(shù)仿生智能算法處理動態(tài)環(huán)境下的規(guī)劃問題時存在實時性、收斂性均不穩(wěn)定等問題,實際應(yīng)用較少。
從目前研究思路來看,多是先采用圖規(guī)劃算法、空間采樣算法生成全局路徑或初始路徑,再使用曲線插值擬合算法,綜合考慮系統(tǒng)軟硬約束,優(yōu)化生成質(zhì)量好的軌跡。
表 3 -1 運動規(guī)劃算法優(yōu)缺點對比(點擊或原文查看大圖)
備注:相關(guān)參考文獻可對照《類車機器人集成感知與規(guī)劃系統(tǒng)設(shè)計研究》
04
結(jié)論與展望
本文根據(jù)規(guī)劃算法特點將常見規(guī)劃算法劃分為四類,并從實時性、計算成本、模型復(fù)雜度、環(huán)境適應(yīng)能力、路徑曲線質(zhì)量、軌跡長度等方面綜合對比分析了上述四個子類規(guī)劃算法。
運動規(guī)劃算法種類繁多,應(yīng)用場景各不相同,而本文僅從移動機器人視角對部分運動規(guī)劃算法進行了分析概述,只能算是窺探運動規(guī)劃這一領(lǐng)域的冰山一角。
后續(xù)會逐漸深入討論分析一些經(jīng)典的算法。
上一篇:工業(yè)機器人基本組成及分類
中國傳動網(wǎng)版權(quán)與免責(zé)聲明:凡本網(wǎng)注明[來源:中國傳動網(wǎng)]的所有文字、圖片、音視和視頻文件,版權(quán)均為中國傳動網(wǎng)(m.u63ivq3.com)獨家所有。如需轉(zhuǎn)載請與0755-82949061聯(lián)系。任何媒體、網(wǎng)站或個人轉(zhuǎn)載使用時須注明來源“中國傳動網(wǎng)”,違反者本網(wǎng)將追究其法律責(zé)任。
本網(wǎng)轉(zhuǎn)載并注明其他來源的稿件,均來自互聯(lián)網(wǎng)或業(yè)內(nèi)投稿人士,版權(quán)屬于原版權(quán)人。轉(zhuǎn)載請保留稿件來源及作者,禁止擅自篡改,違者自負版權(quán)法律責(zé)任。