面向車身數字化工藝開發(fā)的多機器人避障算法

曾 賀

（上汽大通汽車有限公司 制造工程部，上海 200082）

機器人路徑規(guī)劃是指對于給定的任務，機器人尋覓一條從初始位置抵達目標點后的無碰撞最優(yōu)路徑的過程。

單機器人無碰撞路徑規(guī)劃是多機器人協(xié)調運動的基礎，傳統(tǒng)單機器人無碰撞運動規(guī)劃方法包括自由空間法、人工勢場法、概率地圖和快速擴展隨機樹等基于采樣的規(guī)劃方法，LI T G等人提出了一種改進的Q-Learning自主學習算法來解決空間操縱器在未知環(huán)境中的自適應路徑規(guī)劃問題，根據Q-table的自主學習，操縱器可以指導其后續(xù)的動作選擇和路徑規(guī)劃，使機器人自由空間內尋找一條最優(yōu)的機械臂無碰撞路徑。焦嵩鳴等對A*的啟發(fā)函數進行改進，以減少路徑規(guī)劃過程中的計算量，從而提高規(guī)劃效率，設計障礙懲罰函數，進而實現提前避開行進路徑上的障礙物，避免陷入局部最優(yōu)。陳滿意等人采用低振蕩人工勢場法進行路徑搜索，當人工勢場法陷入局部極小時采用自適應快速搜索樹方法進行路徑搜索，最終對于搜索到的冗余路徑節(jié)點采用四次貝塞爾曲線進行擬合優(yōu)化。何啟嘉等人基于深度學習，預先學習競爭網絡中的狀態(tài)價值層，使狀態(tài)價值參數根據環(huán)境狀態(tài)進行初始化，減少了首次接觸目標點所需要的步數；其次，通過改進競爭網絡中的貪婪搜索算法，使環(huán)境探索與利用的轉變更為合理；最后通過改進動作選擇策略，使機器人路徑規(guī)劃不易陷入局部極小值，進一步加快了算法收斂的速度。孫靈碩提出改進的RRT- Connect算法用于焊接機器人的避障路徑規(guī)劃，對位于凹形障礙區(qū)域的樹節(jié)點及其附近區(qū)域進行標記，并將標記的區(qū)域從自由狀態(tài)空間中剔除，避免隨機樹再次陷入標記的凹形障礙區(qū)域。

上述方法雖然可以搜索到較優(yōu)的無碰撞路徑，但是對于車身等大尺寸、結構復雜的產品對象，其構型空間的建模過程復雜、計算量大，因此，如何面向機器人無碰撞檢測路徑最優(yōu)的目標，有效降低環(huán)境建模的計算量、提高搜索效率是多機器人系統(tǒng)路徑規(guī)劃的重點。

針對現有機械臂在復雜多障礙物環(huán)境中局部路徑規(guī)劃時間長的問題，本文提出一種改良的APF-RRT*的機器人避障措施，縮短算法的運行時間，減少局部路徑的長度，提升無碰路徑的搜索效率。

1 方法概述

目前已有許多避障的算法用于解決機器人和靜態(tài)環(huán)境中的運動規(guī)劃問題，例如人工勢場法、基于采樣的規(guī)劃和基于網格的方法。上述方法大多在機器人自由位形空間內進行路徑搜索，實現機器人局部路徑規(guī)劃。然而，實際工程應用中，由于車身曲面結構復雜且所占空間巨大，導致機器人與車身所產生的位形空間建模難度高，且在高維位形空間內搜索較優(yōu)路徑極其費時費力。針對這一問題，本文利用改進APF-RRT*的避障算法在笛卡爾坐標系內搜索機器人可行路徑節(jié)點，以關節(jié)角運動范圍最小為約束條件對生成的路徑節(jié)點下的機器人關節(jié)角進行優(yōu)化，以保證機器人關節(jié)角變化的連續(xù)性。為進一步保證局部路徑最優(yōu)，減少由于RRT*算法搜索導致的路徑冗余現象，本文采用貝塞爾曲線對產生的局部路徑進行二次優(yōu)化。

本文提出的機器人避障策略流程如圖1所示。

2 傳統(tǒng)避障算法

為了更好地闡述本文提出的避障策略，首先對傳統(tǒng)的RRT*算法及人工勢場法進行簡要闡述。

2.1 傳統(tǒng)RRT＊算法

RRT*算法是一種基于增量采樣的路徑搜索算法，通過多次采樣的方法實現搜索路徑的最優(yōu)，RRT算法的前幾步和RRT算法相同，RRT算法具體的算法步驟如下：

步驟1：從機器人初始位置建立根節(jié)點。

步驟2：利用隨機采樣的方式在機器人運動空間內進行搜索，確定隨機采樣點。

步驟4：判斷是否與障礙物發(fā)生碰撞，若無碰撞，則確定為新節(jié)點，返回步驟2。

RRT算法中存在搜索路徑非最優(yōu)解的現象，為了解決此問題，RRT*算法父節(jié)點選擇和重布線兩個操作進一步對機器人運行路徑進行優(yōu)化。

RRT*算法父節(jié)點選取的示意圖如圖2所示，所產生的新節(jié)點搜尋所定義半徑范圍內潛在的父節(jié)點，依次計算→→的總路徑，若此路徑小于→→路徑的長度，則將的父節(jié)點進行更新，最終迭代選取路徑最短的節(jié)點作為的父節(jié)點。

為進一步減少機器人局部路徑的長度對鄰域內的節(jié)點進行重布線的操作，RRT*算法重布線示意圖如圖3所示，在無碰撞的前提下，重布線函數分別計算→→，→→，路徑長度分別為，。若<，則將父節(jié)點更改為。最終，不斷迭代上述步驟，直到新產生的節(jié)點尋找到目標點為止。

2.2 人工勢場算法

人工勢場法是利用虛擬勢場中梯度下降引導機器人進行路徑搜索的方法，該方法根據機器人所處的環(huán)境建立虛擬勢場及勢場力，機器人下一個運動的目標點對機器人產生引力，一般情況下引力勢函數和引力函數為

車身等障礙物對機器人產生斥力，引力和斥力合力的方向即為機器人運行的方向。則斥力函數通?？杀硎緸?/p>

機器人在所構建勢力場下受到總勢能和勢場力分別為

當機器人所受到勢能不為0時，機器人下一時刻的位置為

其中，為所設點的步長，為/||。重復上述步驟直到勢能為0或找到檢測特征為止。

3 基于APF-RRT＊算法的機器人避障策略

RRT*算法通過父節(jié)點的選取和重布線兩個步驟解決了RRT算法中路徑冗余的問題，但上述算法中機器人父節(jié)點的選取及重布線均需要重新進行大量的計算，且節(jié)點的產生均基于隨機采樣導致RRT*算法的時間效率較低。而采用人工勢場法進行路徑搜索時易于出現搜索結果陷入最優(yōu)的現象。針對上述問題本文引入人工勢場的思想進行新節(jié)點的產生，使得機器人新節(jié)點的產生不僅受到隨機性的影響，還受到人工勢場力的影響，則機器人新節(jié)點產生的公式為

式中，為權重系數；為機器人在處受到的合力；為機器人搜索的步長；當>時，隨機采樣性較高，機器人能夠搜索到任意的無碰撞工作區(qū)間，為路徑最優(yōu)提供優(yōu)化條件，同時增加搜索時間。當<時，機器人采樣點搜索更具有目的性。但當機器人工作環(huán)境較為復雜時，易于出現機器人無法到達目標點的現象。因此，為了保證機器人能夠搜索到目標點，提高搜索概率的完備性，此處應略大于，本文選取=0.6，=0.4。

基于上述新節(jié)點產生策略能夠使節(jié)點向目標搜索，同時面對障礙物時能基于人工勢場的斥力作用繞開障礙物，為節(jié)點搜索提供有效的隨機采樣點，從而提高路徑規(guī)劃的效率。然而，對于笛卡爾空間內確定的節(jié)點位姿，機器人利用逆運動學可以求解得到最多八組解，因此，為了保障機器人前后節(jié)點關節(jié)角的連續(xù)性，需滿足每個關節(jié)的角度變化最小，可根據式（6）對于新產生節(jié)點關節(jié)角進行確定，即

RRT*搜索得到的路徑為直線時，機器人在通過奇異點附近時，機器人關節(jié)速度將極速增加，導致不可達現象。因此，為了保證搜索路徑的平滑性及可達性，需要對RRT*搜索到的路徑進行平滑處理。在工業(yè)機器人應用中，五次貝塞爾曲線滿足機器人軌跡對于平滑、速度可導、加速度連續(xù)等要求而被廣泛應用于機器人控制系統(tǒng)。因此，為保證所規(guī)劃的軌跡更接近于機器人運動軌跡，本文采用五次貝塞爾曲線對新產生節(jié)點進行擬合。五次貝塞爾曲線方程為

式中，為控制點，即為搜索到的節(jié)點；()為伯恩斯坦基函數；=5。

五次貝塞爾曲線最多可對六個控制節(jié)點進行曲線擬合，因此，需要多段貝塞爾曲線進行擬合。值得注意的是，擬合后的曲線進一步進行碰撞檢測以防止新擬合的軌跡發(fā)生碰撞等現象。可通過以下步驟進行曲線擬合。

步驟1：依次選取六個節(jié)點作為控制點進行貝塞爾曲線擬合。

步驟2：對生成的節(jié)點進行碰撞檢測。若不發(fā)生碰撞，對剩余節(jié)點進行曲線擬合；若發(fā)生碰撞，則轉到步驟3。

步驟3：找出碰撞點前后的節(jié)點、，在、節(jié)點中間選取4個過渡節(jié)-點使得→→…→擬合得到的曲線不發(fā)生碰撞。

4 基于APF-RRT＊算法的機器人避障應用驗證

機器人局部路徑規(guī)劃是在機器人發(fā)生碰撞時獲取無碰撞局部檢測路徑的重要手段，局部路徑的長度及算法實現的效率影響整個車身檢測路徑的質量及全局路徑規(guī)劃的時間。為驗證本文提出的APF- RRT*算法的有效性，本節(jié)將基于薄板件模型，分別采用RRT、RRT*、APF、RRT*及所提出的改進APF- RRT*算法進行避障驗證。

薄板件由自由曲面和平面連接而成，其CAD數模如圖4(a)所示，圖4(b)中的灰色部分是其三角面片化后的網格化數據。在薄板件表面隨機選取兩個關鍵尺寸特征，其檢測視點位置分別為Start以及Goal。機器人需從視點Start運動到視點Goal完成機器人的局部無碰撞路徑。

本節(jié)分別采用RRT、改進APF、RRT*和所提出的改進APF- RRT*分別對進行Start、Goal視點之間路徑進行避障，最終的機器人末端點運動軌跡如圖5所示。

為了更直觀地反映所提出方法的有效性，以下分別從算法運行時間、迭代次數及最終路徑總長度進行分析。不同避障策略的優(yōu)化參數對比如表1所示，基于人工勢場算法的運行時間為33.17 s，算法迭代次數僅為369次，其算法運行時間及迭代次數最少，但其優(yōu)化后的總路徑長度最長，約為536.65 mm。而本文提出算法路徑總長度僅為118.1 mm，比人工勢場算法路徑長度減少約77.93%，比RRT*和RRT算法的局部優(yōu)化分別提高35.31%和55.96%。

從運行時間看，基于本文提出的APF-RRT*算法的運行時間為115 s，相比于傳統(tǒng)的RRT*算法提升了83.2%，且迭代次數縮短至536次，縮短了73.2%。綜上所述，經典人工勢場法搜索時間較短，但是在路徑優(yōu)化方面的不足；傳統(tǒng)的RRT*、RRT算法優(yōu)化后路徑較短，但是搜索時間較長。而本文提出的APF-RRT*不僅提升了算法搜索效率，同時縮短優(yōu)化后路徑長度，避障效果較好。

5 結論

本文詳細闡述了獲取任意兩個特征之間無碰撞局部檢測路徑的方法，提出了基于APF-RRT*的機器人局部避障策略，改進后的RRT算法在一定程度上縮短了算法的運行時間，迭代次數以及路徑的總長度，實現局部路徑的優(yōu)化，提高局部避障算法的搜索效率。