工業(yè)機(jī)器人運(yùn)動(dòng)規(guī)劃研究進(jìn)展

01引言工業(yè)機(jī)器人運(yùn)動(dòng)規(guī)劃是指在無(wú)人參與示教的情況下，通過(guò)算法搜索出一條符合約束的無(wú)碰撞路徑，是實(shí)現(xiàn)工業(yè)機(jī)器人智能化的關(guān)鍵技術(shù)。傳統(tǒng)運(yùn)動(dòng)規(guī)劃方法需要建立機(jī)器人構(gòu)型和障礙物的位姿空間模型，計(jì)算復(fù)雜度隨著機(jī)器人自由度增加成指數(shù)增長(zhǎng)，難以解決在復(fù)雜環(huán)境與高維構(gòu)型空間下的運(yùn)動(dòng)規(guī)劃問(wèn)題。針對(duì)上述問(wèn)題，研究人員提出了隨機(jī)采樣方法，可避免在位形空間中復(fù)雜的障礙物建模運(yùn)算，能夠快速求解高維度運(yùn)動(dòng)規(guī)劃問(wèn)題。其中最著名的兩種算法是：隨機(jī)路圖法（PRM）和快速隨機(jī)搜索樹(shù)（RRT），兩種算法都能快速獲得可行解，但由于采樣過(guò)程引入了隨機(jī)性，使求解結(jié)果極不穩(wěn)定，難以運(yùn)用于實(shí)際場(chǎng)景，因此如何最大程度提高運(yùn)動(dòng)規(guī)劃算法的搜索效率和可行解質(zhì)量成為極具挑戰(zhàn)的任務(wù)。為了提高可行解質(zhì)量，研究人員嘗試將強(qiáng)化學(xué)習(xí)與隨機(jī)采樣算法相結(jié)合，以保證求解速度并不斷提高求解質(zhì)量，為解決運(yùn)動(dòng)規(guī)劃問(wèn)題提供了新思路，但該算法的性能取決于策略函數(shù)和獎(jiǎng)勵(lì)函數(shù)的優(yōu)劣。因此，如何利用強(qiáng)化學(xué)習(xí)良好的自適應(yīng)和自學(xué)習(xí)特性，將其與隨機(jī)采樣算法相結(jié)合成為了近年的研究熱點(diǎn)。本文針對(duì)工業(yè)機(jī)器人高維構(gòu)型空間的運(yùn)動(dòng)規(guī)劃問(wèn)題，詳細(xì)介紹了快速隨機(jī)搜索樹(shù)算法的基本原理，并分析其改進(jìn)方法的特點(diǎn)。在此基礎(chǔ)上，重點(diǎn)闡述了基于強(qiáng)化學(xué)習(xí)的隨機(jī)采樣算法，并對(duì)工業(yè)機(jī)器人運(yùn)動(dòng)規(guī)劃未來(lái)的研究方向進(jìn)行了展望。02基于隨機(jī)采樣的運(yùn)動(dòng)規(guī)劃算法由于工業(yè)機(jī)器人的運(yùn)動(dòng)規(guī)劃所面臨的任務(wù)環(huán)境往往是高維復(fù)雜的，傳統(tǒng)搜索算法計(jì)算復(fù)雜度隨著構(gòu)型空間維度的增加成指數(shù)增長(zhǎng)，無(wú)法解決高維運(yùn)動(dòng)規(guī)劃問(wèn)題。而隨機(jī)采樣算法可避免高維空間復(fù)雜環(huán)境的建模運(yùn)算，能夠快速求解高維度、復(fù)雜環(huán)境下的運(yùn)動(dòng)規(guī)劃問(wèn)題，已成為解決這類規(guī)劃問(wèn)題的主流算法。2.1快速隨機(jī)搜索樹(shù)算法及其擴(kuò)展為解決在復(fù)雜非完整約束與動(dòng)態(tài)系統(tǒng)中的規(guī)劃問(wèn)題，提出基于隨機(jī)采樣的快速擴(kuò)展隨機(jī)樹(shù)（Rapidly-exploringRandomTree,簡(jiǎn)稱為RRT）算法，該算法避免了對(duì)空間的建模，不需要任何預(yù)處理，具有高效的搜索特性，為多自由度機(jī)器人復(fù)雜約束下的運(yùn)動(dòng)規(guī)劃問(wèn)題提供了一種快速求解方法。同時(shí)也證明了該算法具有概率完備性，即只要保證足夠的搜索時(shí)間，就一定能找到可行解。由于隨機(jī)采樣的RRT算法隨機(jī)性強(qiáng)、盲目性高，為了提高該算法在運(yùn)動(dòng)規(guī)劃上的表現(xiàn)，借鑒啟發(fā)式算法的思想，在隨機(jī)擴(kuò)展樹(shù)的生長(zhǎng)過(guò)程中引入一個(gè)目標(biāo)概率偏置參數(shù)，使隨機(jī)采樣偏向目標(biāo)節(jié)點(diǎn)，減少隨機(jī)性，提高運(yùn)動(dòng)規(guī)劃效率。在無(wú)障礙或障礙較少的環(huán)境中，引入目標(biāo)偏置可以使規(guī)劃出來(lái)的路徑更接近于理想路徑。但環(huán)境中障礙物較多時(shí)，上述方法的避障效果明顯下降。為了解決此問(wèn)題，王道威[8]等人提出一種動(dòng)態(tài)步長(zhǎng)技術(shù)，用于平衡目標(biāo)導(dǎo)向性并保證避碰效果。另外，提出將RRT與人工勢(shì)場(chǎng)法結(jié)合，利用人工勢(shì)場(chǎng)法進(jìn)行局部規(guī)劃，當(dāng)陷入局部最小點(diǎn)時(shí)，使用改進(jìn)的RRT算法自適應(yīng)選擇臨時(shí)目標(biāo)點(diǎn)，使搜索過(guò)程跳出局部最小值。而則將滾動(dòng)規(guī)劃與RRT相結(jié)合，依靠滾動(dòng)規(guī)劃法實(shí)時(shí)探測(cè)到的局部信息生成優(yōu)化子目標(biāo)。由于規(guī)劃問(wèn)題壓縮至滾動(dòng)窗口內(nèi)，計(jì)算量與全局規(guī)劃相比大幅下降。2.2RRT-Connect算法及其擴(kuò)展由于單向搜索的RRT算法在擴(kuò)展節(jié)點(diǎn)具有很強(qiáng)的隨機(jī)性，即使在標(biāo)準(zhǔn)RRT基礎(chǔ)上進(jìn)行引導(dǎo)修正，算法的效率依然低下。因此，提出了RRT-Connect算法，通過(guò)增加搜索樹(shù)數(shù)目提高路徑生成速度。算法分別以起始節(jié)點(diǎn)x_start和目標(biāo)節(jié)點(diǎn)x_goal作為兩棵隨機(jī)擴(kuò)展樹(shù)的根節(jié)點(diǎn)，設(shè)計(jì)啟發(fā)函數(shù)引導(dǎo)兩棵樹(shù)的搜索?；谏鲜鏊悸罚谔摂M人雙臂運(yùn)動(dòng)規(guī)劃問(wèn)題上使用雙向平衡的RRT規(guī)劃算法，以一種近乎平衡的方式引導(dǎo)兩棵樹(shù)交替朝向?qū)Ψ娇焖贁U(kuò)展。而提出的JT-RRT將RRT在位姿空間的探索與工作空間的偏置結(jié)合起來(lái)，高效地解決了在復(fù)雜環(huán)境中的規(guī)劃問(wèn)題。此外，將雙向RRT與JT-RRT結(jié)合，提出一種同時(shí)在位姿空間和工作空間進(jìn)行擴(kuò)展的雙向RRT算法，該算法位于工作空間的擴(kuò)展樹(shù)可以給位姿空間的擴(kuò)展樹(shù)提供啟發(fā)式信息，避免了整個(gè)位姿空間的搜索，極大提升了規(guī)劃效率。而則提出在不考慮機(jī)器人運(yùn)動(dòng)學(xué)的情況下，工作空間樹(shù)在目標(biāo)工作空間中尋找最近集合，而狀態(tài)空間樹(shù)則在考慮運(yùn)動(dòng)學(xué)和動(dòng)態(tài)約束下生成機(jī)器人路徑的雙樹(shù)形結(jié)構(gòu)。2.3RRT*算法及其擴(kuò)展RRT算法雖然具有概率完備性，能處理高維復(fù)雜環(huán)境中的問(wèn)題，但無(wú)法保證算法所得到的可行解質(zhì)量，即由RRT算法所規(guī)劃出來(lái)的路徑往往都是非最優(yōu)的。針對(duì)這一問(wèn)題，一系列基于RRT的最優(yōu)運(yùn)動(dòng)規(guī)劃方法被提出。根據(jù)RRT算法的表現(xiàn)情況，指出，其收斂到最優(yōu)的概率基本為零。同時(shí)，他們提出一種基于RRT且具有漸進(jìn)最優(yōu)性的算法：RRT*。該算法在每一次拓展時(shí)都進(jìn)行優(yōu)化處理：取拓展點(diǎn)附近的所有點(diǎn)逐一比較代價(jià)值，從而選取最小代價(jià)值的父節(jié)點(diǎn)。雖然該算法具有漸近最優(yōu)的特性，但每次增加新節(jié)點(diǎn)時(shí)都要進(jìn)行遍歷以達(dá)到優(yōu)化的目的，導(dǎo)致了搜索時(shí)長(zhǎng)大幅增加。在此基礎(chǔ)上，指出，用于提升解決方案的狀態(tài)子集可以被描述成扁長(zhǎng)的超球體，InformedRRT*可以通過(guò)直接采樣這個(gè)子集來(lái)提升RRT*算法的效率，快速返回鄰近的最優(yōu)方案。而P-RRT*-connec則是將雙向人工勢(shì)場(chǎng)結(jié)合到RRT*中，兩棵樹(shù)按照采樣點(diǎn)的人工勢(shì)場(chǎng)法生成的引力場(chǎng)和斥力場(chǎng)同時(shí)相互前進(jìn)直到二者相遇，該算法特別適用于窄通道問(wèn)題。另外，提出了一個(gè)基于RRT*的生物啟發(fā)路徑規(guī)劃算法：TropisticRRT*。該算法使用高斯混合模型來(lái)模仿植物的自然生長(zhǎng)，減小抽樣空間，提高了運(yùn)動(dòng)規(guī)劃效率，但同時(shí)也導(dǎo)致了采樣分布不均。而在雙向RRT和InformedRRT*的基礎(chǔ)上，提出HybridRRT，其將規(guī)劃過(guò)程分為三個(gè)部分，基于雙樹(shù)搜索初始解，并將兩棵樹(shù)合并成一棵，再采用InformedRRT*優(yōu)化路徑。該方法用非最優(yōu)搜索來(lái)發(fā)現(xiàn)初始解，不僅比最優(yōu)規(guī)劃速度更快，還能返回臨近最優(yōu)解。2.4其他相關(guān)擴(kuò)展算法為了從各個(gè)方面更好地解決各式各樣的機(jī)器人運(yùn)動(dòng)規(guī)劃問(wèn)題，研究人員在RRT變體的基礎(chǔ)上做了廣泛的嘗試與結(jié)合。如BIT*通過(guò)在RRT中加入表搜索，將圖表法與基于抽樣的規(guī)劃技術(shù)相結(jié)合，提升了返回初始解的速度。為解決低效率和易陷入局部最小的問(wèn)題，在RRT的基礎(chǔ)上提出使用衰退機(jī)制來(lái)避免過(guò)度搜索位姿空間，另外，算法通過(guò)優(yōu)化關(guān)節(jié)空間的邊界節(jié)點(diǎn)來(lái)持續(xù)地提升可到達(dá)的空間信息，避免重復(fù)搜索已擴(kuò)展節(jié)點(diǎn)。而MT-RRT則是利用四個(gè)不同的多線程策略進(jìn)行改進(jìn)，減少了計(jì)算時(shí)間。除此之外，則在RRT基礎(chǔ)上提出CODES3算法，用以解決在高度受限的環(huán)境中的規(guī)劃問(wèn)題，此外，他們還提出了基于雙向樹(shù)搜索的6模型結(jié)構(gòu)，每個(gè)模型中包含多個(gè)備選策略，根據(jù)環(huán)境背景信息從中尋找到最好的搭配來(lái)靈活地解決不同問(wèn)題。2.5總結(jié)到目前為止，從RRT的總體發(fā)展脈絡(luò)來(lái)看，學(xué)者們主要是在規(guī)劃效率與結(jié)果最優(yōu)性兩個(gè)方面對(duì)原始的RRT進(jìn)行改進(jìn)與提高。主要的改進(jìn)手段是利用增加隨機(jī)擴(kuò)展樹(shù)數(shù)目提升搜索效率的RRT-Connect和通過(guò)改進(jìn)每次拓展方式來(lái)達(dá)到算法漸進(jìn)最優(yōu)性的RRT*。因此，如何在此基礎(chǔ)上繼續(xù)提升算法性能也成為研究人員陸續(xù)關(guān)注的熱點(diǎn)。此外，結(jié)合其他技術(shù)或在算法結(jié)構(gòu)上進(jìn)行調(diào)整，也是工業(yè)機(jī)器人運(yùn)動(dòng)規(guī)劃領(lǐng)域未來(lái)的研究方向。03基于強(qiáng)化學(xué)習(xí)的運(yùn)動(dòng)規(guī)劃算法強(qiáng)化學(xué)習(xí)的基本思想是智能體在與環(huán)境交互的過(guò)程中根據(jù)環(huán)境反饋得到獎(jiǎng)勵(lì)，并不斷調(diào)整自身的策略以實(shí)現(xiàn)最佳決策，適用于現(xiàn)實(shí)中無(wú)法提供大量標(biāo)簽數(shù)據(jù)的決策優(yōu)化類問(wèn)題。由于其具有自學(xué)習(xí)性與自適應(yīng)性等優(yōu)點(diǎn)，受到各領(lǐng)域?qū)＜覍W(xué)者們的廣泛關(guān)注，近年來(lái)，也有不少學(xué)者們將強(qiáng)化學(xué)習(xí)應(yīng)用在機(jī)器人運(yùn)動(dòng)規(guī)劃問(wèn)題上，為解決這一類問(wèn)題提供了新思路。3.1基于傳統(tǒng)強(qiáng)化學(xué)習(xí)的方法提高機(jī)器人的自主決策與學(xué)習(xí)能力，僅依靠設(shè)計(jì)者的經(jīng)驗(yàn)和知識(shí)是很難獲得對(duì)復(fù)雜不確定環(huán)境的良好適應(yīng)性。因此，如何在機(jī)器人的運(yùn)動(dòng)規(guī)劃中引入學(xué)習(xí)機(jī)制，成為研究人員關(guān)注的熱點(diǎn)。如提出將動(dòng)作基本體與隨機(jī)策略梯度學(xué)習(xí)相結(jié)合，并證明了在強(qiáng)化學(xué)習(xí)中用動(dòng)作基本體來(lái)生成參數(shù)化控制策略的合理性。而提出一種基于具有路徑積分的隨機(jī)優(yōu)化控制結(jié)構(gòu)的強(qiáng)化學(xué)習(xí)參數(shù)化控制策略PI2，該方法中用于學(xué)習(xí)的更新式既不需要矩陣的逆解也不需要梯度學(xué)習(xí)率，因此從數(shù)學(xué)的角度而言其有簡(jiǎn)單且穩(wěn)定的特點(diǎn)。在此基礎(chǔ)上，使用動(dòng)覺(jué)示范初始化機(jī)器人的初始位置控制策略，且利用PI2算法通過(guò)優(yōu)化一個(gè)價(jià)值函數(shù)來(lái)學(xué)習(xí)末端感知器所需要的力、轉(zhuǎn)矩等信息，從而在轉(zhuǎn)動(dòng)把手開(kāi)門和拾取桌上的筆兩個(gè)環(huán)境的實(shí)驗(yàn)中取得了良好的效果。另外，則將強(qiáng)化學(xué)習(xí)應(yīng)用在多機(jī)器人協(xié)作的任務(wù)上，解決每個(gè)機(jī)器人與所要操縱的物體之間未知的動(dòng)力學(xué)問(wèn)題。3.2基于深度強(qiáng)化學(xué)習(xí)的方法雖然傳統(tǒng)的強(qiáng)化學(xué)習(xí)在機(jī)器人運(yùn)動(dòng)規(guī)劃問(wèn)題上有所應(yīng)用，但大多難以克服高維復(fù)雜環(huán)境，解決的規(guī)劃問(wèn)題也略為簡(jiǎn)單。隨著深度強(qiáng)化學(xué)習(xí)的發(fā)展，通過(guò)龐大且深層的神經(jīng)網(wǎng)絡(luò)與強(qiáng)化學(xué)習(xí)結(jié)合，以一種通用的形式將深度學(xué)習(xí)的感知能力與強(qiáng)化學(xué)習(xí)的決策能力相結(jié)合，并通過(guò)端對(duì)端的學(xué)習(xí)方式實(shí)現(xiàn)從原始輸入到輸出的直接控制，在眾多需要感知高維度原始輸入數(shù)據(jù)和決策控制任務(wù)中取得實(shí)質(zhì)性的突破。沿著深度網(wǎng)絡(luò)與強(qiáng)化學(xué)習(xí)結(jié)合的這一研究思路，也有許多經(jīng)典的深度強(qiáng)化學(xué)習(xí)算法被陸續(xù)提出，如TRPO，DDPG，NAF等，雖然受現(xiàn)實(shí)系統(tǒng)中的采樣復(fù)雜度影響，其能否靈活適用在現(xiàn)實(shí)環(huán)境中仍不明確，但這些算法的提出使機(jī)器人在人為操作很少的前提下學(xué)習(xí)復(fù)雜的技巧成為可能。在此基礎(chǔ)上，提出利用一個(gè)7層、92,000個(gè)參數(shù)的深度卷積神經(jīng)網(wǎng)絡(luò)進(jìn)行策略學(xué)習(xí)。策略學(xué)習(xí)過(guò)程中不再需要全部的狀態(tài)信息即可掌握未知的位姿信息，并可使用隨機(jī)梯度下降等的常規(guī)方法進(jìn)行訓(xùn)練。而指出，由于高采樣復(fù)雜度，深度強(qiáng)化學(xué)習(xí)的應(yīng)用僅限于仿真與簡(jiǎn)單的實(shí)際任務(wù)中，因此他們提出一個(gè)適用于復(fù)雜3D機(jī)器人任務(wù)的基于深度Q網(wǎng)絡(luò)的離線策略訓(xùn)練方法。實(shí)驗(yàn)證明該方法可以在不需要先驗(yàn)示范或人為設(shè)計(jì)的情況下學(xué)習(xí)一系列復(fù)雜的3D機(jī)器人運(yùn)動(dòng)技能。李廣創(chuàng)與程良倫[41]則以點(diǎn)焊機(jī)器人為研究對(duì)象，將機(jī)器人在三維空間的自動(dòng)點(diǎn)焊轉(zhuǎn)化為機(jī)器人的避障路徑規(guī)劃問(wèn)題，使用一個(gè)三層的DNN網(wǎng)絡(luò)，經(jīng)過(guò)離線訓(xùn)練后，自行訓(xùn)練出一條接近于最優(yōu)的運(yùn)動(dòng)軌跡，成功地避開(kāi)障礙物到達(dá)目標(biāo)點(diǎn)。3.3強(qiáng)化學(xué)習(xí)與基于隨機(jī)采樣的方法結(jié)合鑒于強(qiáng)化學(xué)習(xí)的自學(xué)習(xí)性與自適應(yīng)性，以及隨機(jī)采樣方法的高效搜索與概率完備等優(yōu)點(diǎn)，近年來(lái)，將二者結(jié)合應(yīng)用在機(jī)器人運(yùn)動(dòng)規(guī)劃問(wèn)題上的全新思路開(kāi)始涌現(xiàn)。沿著這一研究方向，將RRT所生成的路徑作為強(qiáng)化學(xué)習(xí)的范例，指導(dǎo)其快速學(xué)習(xí)及收斂，且引入一個(gè)由淺入深的總課程學(xué)習(xí)模式來(lái)解決稀疏回報(bào)下訓(xùn)練困難的問(wèn)題，該方法在6自由度機(jī)器人裝配電腦部件的復(fù)雜實(shí)驗(yàn)環(huán)境下取得了良好效果。而提出RL-RRT算法，使用深度強(qiáng)化學(xué)習(xí)來(lái)學(xué)習(xí)避障策略，將其作為局部?jī)?yōu)化器，再采用可達(dá)性估算器作為距離函數(shù)對(duì)樹(shù)的生長(zhǎng)方向進(jìn)行偏置。另外，提出PRM-RL算法，使用強(qiáng)化學(xué)習(xí)來(lái)處理小范圍內(nèi)點(diǎn)到點(diǎn)的規(guī)劃，再用PRM提供連接著機(jī)器人位姿的路標(biāo)，成功解決了機(jī)器人遠(yuǎn)距離規(guī)劃導(dǎo)航問(wèn)題。而則提出先由RRT搜索初始可行解，再利用強(qiáng)化學(xué)習(xí)進(jìn)行優(yōu)化的R3L算法。該方法減少了算法的收斂時(shí)間，并且克服了稀疏回報(bào)下未獲得第一個(gè)正回報(bào)前的盲目探索問(wèn)題。除此之外，在處理高維狀態(tài)-動(dòng)作空間問(wèn)題上，通過(guò)學(xué)習(xí)以前的經(jīng)驗(yàn)來(lái)解決新的規(guī)劃問(wèn)題的一種神經(jīng)探索利用樹(shù)NEXT。相比起一些已有的基于學(xué)習(xí)的規(guī)劃器，NEXT更加通用，并且可以在探索與利用之間找到平衡。3.4總結(jié)隨著強(qiáng)化學(xué)習(xí)技術(shù)的不斷發(fā)展，專家學(xué)者們利用這個(gè)技術(shù)在工業(yè)機(jī)器人運(yùn)動(dòng)規(guī)劃領(lǐng)域做了許多有價(jià)值的嘗試。但無(wú)論是通過(guò)傳統(tǒng)的強(qiáng)化學(xué)習(xí)或是結(jié)合深度網(wǎng)絡(luò)的強(qiáng)化學(xué)習(xí)，要么難以克服高維復(fù)雜環(huán)境，要么需要利用非常龐大且復(fù)雜的網(wǎng)絡(luò)，具有很強(qiáng)的不穩(wěn)定性，難以應(yīng)用在現(xiàn)實(shí)環(huán)境中。于是，研究人員開(kāi)始把目光轉(zhuǎn)向結(jié)合強(qiáng)化學(xué)習(xí)的自學(xué)習(xí)、自適應(yīng)性與基于隨機(jī)采樣方法的高效搜索性、概率完備性的新思路上。這個(gè)方法不僅可以保證求解的速度，還可以逐步提高規(guī)劃結(jié)果的質(zhì)量，是一個(gè)值得深入發(fā)掘的方向。04目前存在問(wèn)題及研究展望根據(jù)目前工業(yè)機(jī)器人運(yùn)動(dòng)規(guī)劃算法存在的不足和目前研究的現(xiàn)狀，本文認(rèn)為未來(lái)研究方向主要有：（