障礙條件下串聯(lián)機械手運動規(guī)劃設(shè)計

韓慧軒 周順 周海波

摘要：

障礙條件下機械手運動規(guī)劃問題是機器人技術(shù)的研究熱點，可分為路徑規(guī)劃、軌跡規(guī)劃和軌跡優(yōu)化等三部分，運動規(guī)劃的優(yōu)劣影響著機械手的工作質(zhì)量和效率。基于障礙條件下系統(tǒng)設(shè)計了機械手運動規(guī)劃算法框架，即路徑規(guī)劃用于有效避障，軌跡規(guī)劃保證運動連續(xù)平滑，軌跡優(yōu)化達到高效運行，以此來滿足不同工況需求。同時闡述了運動規(guī)劃涉及到的相關(guān)算法，針對其優(yōu)缺點、適用場景、研究進展進行對比分析，為機械手運動規(guī)劃設(shè)計提供參考依據(jù)。

關(guān)鍵詞：

機械手;路徑規(guī)劃;軌跡規(guī)劃;軌跡優(yōu)化;運動規(guī)劃算法

中圖分類號：TP241.2 ? ? ? ? 文獻標志碼：A

收稿日期：2021-01-11

基金項目：國家重點研發(fā)計劃項目（批準號：2018YFB1308900）資助;天津市自然科學(xué)基金（批準號：17JCZDJC30400）資助。

通信作者：周海波，男，博士，教授，主要研究方向為智能機器人技術(shù)，智能制造。E-mail：haibo_zhou@163.com

機械手運行的穩(wěn)定性、可靠性和準確性等特性，是代替工業(yè)生產(chǎn)、農(nóng)業(yè)生產(chǎn)和服務(wù)等行業(yè)重復(fù)單調(diào)的人工作業(yè)的友好選擇。機器人的廣泛應(yīng)用使得機械手自動或者自主運動問題成為研究熱點，所涉及的運動規(guī)劃算法需要針對不同的需求升級改進，以適應(yīng)復(fù)雜障礙工作環(huán)境，滿足不同的工作需求。在工業(yè)生產(chǎn)中，Zhang等[1]結(jié)合裝配或搬運類工業(yè)機械手，采用改進的RRT算法，主要實現(xiàn)了路徑規(guī)劃，顯著的提高了機械手的執(zhí)行效率;李小為等[2]采用3-5-3多項式插值和改進的遺傳算法，主要實現(xiàn)了軌跡規(guī)劃與優(yōu)化，實現(xiàn)了機械手的快速運行。在農(nóng)業(yè)生產(chǎn)中，Cheng等[3]采用改進的人工勢場法和包絡(luò)球法來躲避樹枝、未成熟果實等障礙物，主要實現(xiàn)了路徑規(guī)劃問題，以此來提高蘋果采摘機器人的生產(chǎn)率。在服務(wù)行業(yè)，Zhou等[4]為解決機械手在障礙環(huán)境下的撿拾任務(wù)，使用改進的人工勢場法、五次多項式插值法和提出的遺傳自適應(yīng)算法，主要實現(xiàn)了路徑規(guī)劃、軌跡規(guī)劃和軌跡優(yōu)化，使撿拾機械手在工作空間中不與障礙物發(fā)生碰撞，并減少機械手的運行時間，提高了運行效率。由此可見，路徑規(guī)劃[5]、軌跡規(guī)劃和軌跡優(yōu)化[6]作為機器人運動規(guī)劃的核心技術(shù)，其運動規(guī)劃的質(zhì)量將直接影響到機器人的人機環(huán)境友好、運動精度和工作效率等性能。為此，本文系統(tǒng)設(shè)計了機器人運動規(guī)劃算法框架，并結(jié)合近年關(guān)于運動規(guī)劃的研究成果，闡述了相關(guān)算法的工作原理，并進行了對比分析。

1 算法架構(gòu)

障礙條件下機械手運動規(guī)劃算法架構(gòu)如圖1所示，主要包括路徑規(guī)劃、軌跡規(guī)劃和軌跡優(yōu)化。從連接起點位置到終點位置的端點序列或曲線稱為路徑，把構(gòu)成路徑的策略稱為路徑規(guī)劃，即利用路徑規(guī)劃相關(guān)算法找出路徑點，利用碰撞檢測算法判斷機械手是否與障礙物發(fā)生碰撞，以此來判斷路徑點是否可用，得出的一系列可用路徑點組成機械手在障礙條件下的路徑。在關(guān)節(jié)空間或者笛卡爾空間內(nèi)，采用多項式、樣條等插補算法，在路徑規(guī)劃基礎(chǔ)上插入中間序列點，得到連續(xù)平滑的運動軌跡稱為軌跡規(guī)劃。為了實現(xiàn)省時、高精度和節(jié)能等優(yōu)化目標，需要對軌跡規(guī)劃做到進一步改善，達到軌跡優(yōu)化的目的。

2 路徑規(guī)劃

2.1 路徑規(guī)劃算法

近年來研究人員運用相關(guān)算法解決路徑規(guī)劃問題，大致分為傳統(tǒng)算法、基于仿生學(xué)算法和基于圖的搜索算法。傳統(tǒng)算法有人工勢場法、禁忌搜索算法、模擬退火算法，基于仿生學(xué)算法有蟻群算法、遺傳算法、粒子群算法、貪心算法，基于圖的搜索算法有A*算法、RRT算法、PRM法、D*算法。

2.1.1 傳統(tǒng)算法 1986年，Khatib[7]提出人工勢場法。將機器人假設(shè)在力場中運動，目標點周圍存在引力場對機器人有引力作用，障礙物周圍存在斥力場對機器人有排斥作用，將兩者的合力作為機器人的動力。通過實驗，得出的軌跡平滑，收到很好的效果，但存在局部極小值、目標不可達兩大問題。

在比較簡單的環(huán)境中，人工勢場法能規(guī)劃出質(zhì)量較好的路徑。但在相對比較復(fù)雜的環(huán)境中，障礙物和目標點的位置變得復(fù)雜多變，機器人所受斥力和引力大小相等、方向相反時，導(dǎo)致機器人所受合力為零，此時陷入局部最小值點。當目標點附近存在障礙物時，機器人受斥力場作用不能到達目標點，稱目標不可達問題。

Zhang等[8]不考慮旋轉(zhuǎn)關(guān)節(jié)對機械手路徑規(guī)劃的影響，通過構(gòu)造新的重力勢場函數(shù)和斥力函數(shù)來代替?zhèn)鹘y(tǒng)人工勢場法的路徑規(guī)劃，采用添加虛擬障礙物，設(shè)置較大的虛擬障礙物排斥范圍和排斥系數(shù)的方法逃離局部最小值，得到無碰撞路徑。Wang等[9]針對復(fù)雜表面的拋光，拋光輪構(gòu)成的斥力場和拋光輪上目標點構(gòu)成的引力場相互影響，導(dǎo)致軌跡達不到預(yù)定的位置，通過在原斥力場的基礎(chǔ)上，加上目標位置和末端執(zhí)行器位置的影響來修正斥力勢場，最終到達目標點;并針對局部極小值問題，構(gòu)造部分勢場虛擬障礙物確定機械手的逃離方向，最終生成可使用軌跡。Gai等[10]針對多障礙物環(huán)境，考慮到機械臂高度耦合，各個關(guān)節(jié)障礙物的排斥向量會影響到其他關(guān)節(jié)，采用人工勢場法，對于機械臂末端執(zhí)行器和手臂的排斥向量都視為關(guān)節(jié)的排斥向量，通過雅可比矩陣將單個關(guān)節(jié)的排斥向量傳遞給其他關(guān)節(jié)，得出整個機械臂的運動趨勢，提高了系統(tǒng)運行效率。

2.1.2 基于圖的搜索算法 （1） A*算法。A*算法是一種啟發(fā)式搜索方法，其原理可表示為從初始節(jié)點經(jīng)由節(jié)點n到目標節(jié)點距離估計f（n）等于初始節(jié)點到節(jié)點n的實際距離g（n）加上節(jié)點n到目標節(jié)點的最佳路徑的估計距離h（n），設(shè)d（n）為節(jié)點n到目標節(jié)點的距離，比較h（n）和d（n）的大小關(guān)系，可以知道當前路徑是否為最優(yōu)解。A*算法有著擴展節(jié)點少、魯棒性好、運行高效的優(yōu)點，但當算法存在多個最小值時，不能保證路徑最優(yōu)，忽略了實際應(yīng)用中本體大小帶來的限制。

賈慶軒等[11]利用A*算法搜索路徑，并根據(jù)啟發(fā)式信息進行了對關(guān)節(jié)角的尋優(yōu)，實現(xiàn)了機械臂的無碰撞路徑規(guī)劃。汪首坤等[12]針對算法在尋路過程中存在擴展步長較小或較大時，造成搜索死循環(huán)或路徑不光滑現(xiàn)象，提出一種基于A*算法的變步長分段搜索法，即先設(shè)定較大的擴展步長進行搜索得到路徑和一組保證在Z軸方向上到障礙物中心軸距離之和最小的點，依據(jù)這些點將路徑劃分為幾段，再設(shè)定較小的擴展步長，在每段路徑中搜索，從而減小了障礙物的阻礙程度和搜索的數(shù)據(jù)量，提高了搜索效率。

（2） 快速擴展隨機樹（RRT）法?？焖贁U展隨機樹算法是一種基于采樣的單一查詢算法，由Lavalle[13]于1998年提出。其原理為構(gòu)建一棵隨機樹，以初始點為樹根，從初始點開始，迅速的向外擴展尋找可行區(qū)域，并在尋找可行區(qū)域過程中留下隨機樹節(jié)點，直至隨機樹擴展至目標點，再從最后一個節(jié)點向起點回溯，得出路徑。RRT算法有著很強的搜索能力，其建模時間短，方便添加非完整約束，但在狹窄的環(huán)境下難以找到路徑，節(jié)點計算量大，內(nèi)存消耗大。

李季等[14]在RRT算法中加入權(quán)重系數(shù)使節(jié)點趨近于目標節(jié)點，判斷節(jié)點是否處在目標點鄰域內(nèi)，設(shè)置不同的距離增量，以此避免節(jié)點在目標點之間震蕩;對節(jié)點二次處理，從規(guī)劃好的起始節(jié)點開始，依次向每個節(jié)點再進行障礙物檢測，當檢測到的節(jié)點與起始點連線與障礙物發(fā)生碰撞，將此節(jié)點之前的節(jié)點作為新的節(jié)點，并將起始節(jié)點與新節(jié)點之間的節(jié)點全部剔除，然后以新節(jié)點作為起始節(jié)點，重復(fù)上述操作，直至到達終點，經(jīng)過節(jié)點二次處理，可以篩選出最優(yōu)節(jié)點并舍棄冗余節(jié)點。Liu等[15]提出一種PT-RRT算法，利用目標偏差和目標引力策略指導(dǎo)隨機節(jié)點的擴展，首先將隨機概率采樣的閾值設(shè)置為擴展模式的選擇標準，如果隨機采樣值在設(shè)定的閾值內(nèi)，將目標點設(shè)定為隨機點，否則利用目標偏差和目標引力共同作用下擴展新節(jié)點，此方法可以有效減少路徑規(guī)劃時間和路徑長度。馬慧麗等[16]在RRT*算法的基礎(chǔ)上引入目標引力，讓隨機樹朝著目標點方向生長，提出自適應(yīng)步長策略，即在產(chǎn)生碰撞時，按照隨機采樣策略進行擴展，不產(chǎn)生碰撞時采用目標引力策略進行擴展，減少了路徑搜索的隨機性，提高了算法的運行效率。

（3） 隨機路標圖（PRM）法。20世紀90年代初期，Kavraki等[17]提出這一啟發(fā)式節(jié)點增強策略算法。算法將連續(xù)空間轉(zhuǎn)換成離散空間，即在給定圖的自由空間里自定義隨機撒點，從而構(gòu)建出一個路徑網(wǎng)格圖，然后利用A*等搜索算法，在地圖中尋找路徑，以此來提高路徑搜索效率。其復(fù)雜度較低不需精準建模，尋優(yōu)方式簡單，但無法覆蓋全部路徑，導(dǎo)致路徑不易最優(yōu)，對于復(fù)雜情況運算效率會降低。

Sharma等[18]提出一種基于障礙的概率路線圖法，基于障礙的PRM算法生成均勻的節(jié)點分布在障礙物表面上，增加了在障礙物附近的采樣，解決了機械臂在障礙物周圍運動時的路徑最優(yōu)問題，針對機械臂在通過狹窄通道時，PRM算法生成路徑的概率較低的問題。Yang等[19]提出一種節(jié)點調(diào)整方法，在預(yù)處理階段增加隨機生成的節(jié)點，選取隨機節(jié)點，并指定在其鄰域內(nèi)生成新節(jié)點的數(shù)量，選取符合約束條件下的最優(yōu)節(jié)點來取代之前選取的隨機節(jié)點，增加了PRM算法的實用性。

2.1.3 基于仿生學(xué)算法 （1） 蟻群算法。20世紀90年代，Dorigo等[20]首先提出。研究發(fā)現(xiàn)，單只螞蟻在覓食中行為比較簡單隨意，而螞蟻群在覓食中卻表現(xiàn)出相互協(xié)作的行為。進一步研究發(fā)現(xiàn)，螞蟻可以釋放一種信息素的物質(zhì)，螞蟻可以通過對信息素濃度的感知，選擇信息素濃度高的路線，進而得出最短路徑。蟻群算法具有良好的全局優(yōu)化能力，且易于實現(xiàn)，但計算量大，容易陷入局部最優(yōu)。

趙華東等[21]為降低搜索空間的復(fù)雜程度，將機械臂末端執(zhí)行器運動簡化為x、y、z三軸的運動，并限定最大移動距離，以此來構(gòu)成一個區(qū)域，當螞蟻對下一路徑點搜索時會被限制限制在這一區(qū)域內(nèi)，提高了算法的搜索效率，設(shè)置信息素濃度的上下限，避免算法的早熟和局部最優(yōu)，并采用信息素的揮發(fā)系數(shù)自適應(yīng)調(diào)節(jié)策略來提高算法的全局搜索能力和算法的收斂速度。Shen[22]在蟻群算法中加入遺傳算法，使每次迭代過程中利用遺傳算法的快速收斂優(yōu)勢，通過比較遺傳算法與蟻群算法最優(yōu)解，將兩者最優(yōu)解作為蟻群算法新的最優(yōu)解進行信息素更新，加速蟻群算法的收斂速度，利用遺傳算法的突變機制使得蟻群算法跳出局部最優(yōu)區(qū)域，解決了路徑規(guī)劃收斂速度及優(yōu)化之間的沖突問題。Li等[23]在改進了蟻群算法中螞蟻的步幅長度，減少了電機的啟動頻率，提高了機械臂的執(zhí)行效率和定位精度。Zhao等[24]根據(jù)啟發(fā)式函數(shù)計算每個關(guān)節(jié)角度的選擇概率，并為減少機械臂運動過程中產(chǎn)生的位置誤差，改進了過渡概率，在高度約束下找到最優(yōu)解，減少了機械臂運行時間。

（2） 遺傳算法。從達爾文生物進化論衍生而來，模擬其自然選擇和遺傳學(xué)機理的生物進化過程的計算模型，是通過模擬自然進化過程搜索最優(yōu)解的方法，利用遺傳算法求解最優(yōu)問題是通過選擇交叉變異算子不斷迭代來實現(xiàn)的。該算法能夠在自身的迭代優(yōu)勢的同時，與其他算法很好地融合，簡單且容易實現(xiàn)，并且具有較強的全局搜索能力，很強的靈活性，但遺傳算法容易過早收斂，進化過程容易停滯不前，運行效率低。

Zhang等[25]改進了遺傳算子的選擇方式，避免遺傳算子較小時陷入局部最優(yōu)，較大時計算量大的問題;改進了交叉操作，使后代在交叉操作之后具有較高的適應(yīng)度值，改進后的遺傳算法可以提高算法的運行效率。Ramirez等[26]采用精英主義選擇遺傳算子使算法獲得良好的性能，采用輪盤賭作為選擇方法，實現(xiàn)了機械臂的路徑規(guī)劃。

（3） 粒子群算法。粒子群算法也稱鳥群覓食算法，通過研究鳥群搜索食物，在捕食行為中通過集體協(xié)作使搜索效率達到最高的優(yōu)化算法，是Eberhart等[27]于1995年等開發(fā)的一種新的進化算法。具體實現(xiàn)從隨機解出發(fā)，通過迭代尋找最優(yōu)解，通過適應(yīng)度來評價解的品質(zhì)，但是由于粒子群算法沒有遺傳算法中的交叉和變異操作，使得規(guī)則更為簡單，有實現(xiàn)容易、精度高、收斂快等優(yōu)點，在數(shù)據(jù)處理、聚類分析和多維復(fù)雜空間優(yōu)化問題中有著廣泛的應(yīng)用，但存在后期收斂速度慢，容易陷入局部最優(yōu)等缺陷。

袁蒙恩等[28]采用多種群優(yōu)化算法，與傳統(tǒng)粒子群算法相比，在進行全局演化過程中，當粒子找尋到最優(yōu)區(qū)域時，各種群間相互分享信息及經(jīng)驗，多種群優(yōu)化算法的選擇與交互機制保證了精英種群粒子可以在初始化和演化過程中一直保持最優(yōu)，有助于改善傳統(tǒng)粒子群算法容易陷入局部最優(yōu)問題，并提高了算法運行效率。L等[29]在PSO算法中增加一個種群交換項，表示局部最優(yōu)粒子與通過當前迭代獲得的全局最優(yōu)粒子之間的信息交換，用于平衡粒子的勘探和開發(fā)能力，引入最后消除原則到PSO算法中，避免種群局部最優(yōu)，提高種群的全局搜索能力。

關(guān)于路徑規(guī)劃算法和避障檢測算法只列舉了近年來相關(guān)學(xué)者使用頻率較多的算法，對于路徑規(guī)劃算法中沒有介紹禁忌搜索算法、模擬退火算法、貪心算法、D*算法不適用于機械手在障礙條件下的路徑規(guī)劃，表1為上述算法優(yōu)缺點比較及適用場景。

2.2 碰撞檢測

碰撞檢測，即判斷機械臂連桿是否與障礙物發(fā)生碰撞，碰撞檢測可分為人工示教法和碰撞檢測算法，碰撞檢測可以分為層次包絡(luò)盒法和空間分割法，針對機械臂的碰撞檢測基本采用層次包絡(luò)盒法。

2.2.1 人工示教法 針對較簡單的路徑，人為使用示教器或遙控器等規(guī)劃機械手的每個關(guān)節(jié)，以此來躲避障礙物，方便運動實現(xiàn)的同時能避免機械結(jié)構(gòu)本身帶來的誤差，但針對運動精度要求較高時，由于其精度由人眼決定，加上環(huán)境復(fù)雜導(dǎo)致時間過長，人工示教避障則顯得的力不從心。

2.2.2 層次包絡(luò)盒法 層次包絡(luò)盒法指用簡單的幾何體來近似地表示復(fù)雜對象，將碰撞檢測問題轉(zhuǎn)化為機械臂連桿和包絡(luò)體表面位置關(guān)系問題，常用的層次包絡(luò)盒法主要有包圍球法、AABB包圍盒法和OBB包圍盒法。其中，包圍球法指將用球體包絡(luò)物體，其效率較高，但精度較低;OBB包圍盒始終沿著物體的主成分方向生成一個最小的包圍盒，可用于較精準的碰撞檢測，但計算量大使得效率較低;AABB包圍盒指用平行于坐標軸的邊構(gòu)成最小的長方體包絡(luò)物體，當障礙物旋轉(zhuǎn)時，包絡(luò)盒不能隨之旋轉(zhuǎn)，使包圍盒外形不斷變化，精度和效率都很一般。Shen等[30]基于包圍盒理論，用圓柱體和長方體來表示機械臂，用球體、圓柱體、長方體及其組合構(gòu)成環(huán)境中的障礙物，以此來簡化機械臂的碰撞檢測問題，并通過仿真證實了算法的有效性。

3 軌跡規(guī)劃

針對于路徑規(guī)劃得出的軌跡，用直線、圓弧、多項式等對軌跡擬合，其目的是滿足每段路徑的速度、加速度連續(xù)，以保證規(guī)劃出的路徑的平滑。主要介紹插值法軌跡規(guī)劃，插值法是利用函數(shù)f（x）在某一個區(qū)間內(nèi)已知的若干個點的函數(shù)值，用特定的函數(shù)逼近它，使得特定的函數(shù)的值與函數(shù)f（x）上的函數(shù)值近似相等，得出最接近原函數(shù)f（x）的特定函數(shù)。插值法分為基本插值算法和樣條曲線插值算法，基本插補算法主要有單一多項式插值法、分段式多項式插值法，樣條曲線插值算法包括B樣條曲線方程算法，NURBS曲線方程算法。

3.1 多項式插值算法

3.1.1 單一多項式插值法 單一多項式插值法包括三次、五次及更高次多項式插值法。三次多項式插值是空間中最簡單的插值算法，一般給定初末位置的關(guān)節(jié)角度和角速度，不能保證加速度等連續(xù)，容易產(chǎn)生沖擊和震動，只適用于普通的點到點的簡單運動。而五次多項式插值在三次多項式插值的基礎(chǔ)上，增加了對初末位置的角加速度約束，保證了關(guān)節(jié)的加速度連續(xù)，相較三次多項式插值軌跡更平滑?？讘c博等[31]提出一種五次多項式插值和B樣條插值相融合的方法，在求解出的五次多項式軌跡中合理選取控制點，采用B樣條插值減小曲線的曲率，以此來消除突變現(xiàn)象，優(yōu)化后的關(guān)節(jié)軌跡曲線更加光滑平穩(wěn)。

用更高次項的多項式函數(shù)逼近原函數(shù)，使得關(guān)節(jié)角度、加速度、加加速度、以及更高階次的速度都得到了保證，階次越高，機器人受到的震動和沖擊就越小，但是過高的階次會增加更多的計算量，適用于較高精度的軌跡規(guī)劃。

3.1.2 分段多項式插值法 為了減少高次多項式求解的復(fù)雜運算，又不影響軌跡規(guī)劃的精度，采用分段多項式插值法，在不同的階段采用不同階次的多項式進行插值，但每段多項式的連接處的平滑性得不到保證，適用于路徑復(fù)雜且路徑需要經(jīng)常調(diào)整的環(huán)境，保證了多點連續(xù)的簡單運動，但不適用對平穩(wěn)性和精度要求更高的場合。Li等[32]針對位置曲線上算法切換帶來跳躍點附近的抖動區(qū)域，改進了5-7-5分段多項式插值法，在切換點附近截取一段曲線，并利用二次函數(shù)在一定區(qū)間內(nèi)具有的單調(diào)性和凹凸性進行軌跡再處理。鄭濤等[33]提出一種新的軌跡規(guī)劃插值算法B-5-B分段多項式插值法，B即5次B樣條曲線，并做了與3-5-3算法的比對實驗，實驗證明新算法提高了機械臂在運動過程中的角速度與角加速度曲線平滑性，降低了角加速度突變引起的機械系統(tǒng)沖擊力。

3.2 樣條曲線插值算法

B樣條曲線方程法屬于一種參數(shù)化的曲線表達，能局部修改控制點造成相鄰曲線的變化，但不會影響曲線的整體，可以更好地適用于各種實際軌跡的要求，具有幾何不變性、局部支撐性等優(yōu)點，適用于多段軌跡的軌跡規(guī)劃。NURBS是B樣條曲線方程法的擴展，是一種非均勻B樣條曲線，可以任意分布控制點的間距，NURBS樣條函數(shù)的節(jié)點向量沿參數(shù)軸非均勻分布，形成的基函數(shù)各不相同，且算法中加入了基函數(shù)權(quán)因子，其目的是反應(yīng)節(jié)點對軌跡的影響程度，用來改變控制頂點對軌跡的貢獻，使得速度、加速度、加加速度連續(xù)。董甲甲等[34]為了使擬合樣條曲線過控制頂點附近增加更多的控制頂點，以此來使曲線經(jīng)過之前的控制頂點，由于經(jīng)過已知頂點，所以使得計算變得簡單，運算更加快捷。針對機械手在狹窄的環(huán)境中，運動路徑和障礙物很近，必須嚴格通過控制點，而三次B樣條只能通過路徑點控制曲線的形狀，不能通過指定的路徑點，Wan等[35]在控制點周圍新增共線的控制頂點來實現(xiàn)軌跡經(jīng)過路徑點，使得最終軌跡成功的通過了起始點和控制頂點。

關(guān)于軌跡規(guī)劃介紹了幾種有代表性的軌跡規(guī)劃算法，對各類算法做了歸納，表2為上述算法優(yōu)缺點比較及適用場景。

4 軌跡優(yōu)化

軌跡規(guī)劃任務(wù)保證了軌跡的連續(xù)、平滑，但考慮到實際工作要求，進一步考慮沖擊、能量、時間等要求，需要對所得軌跡進一步的優(yōu)化和改善?？偨Y(jié)了關(guān)于軌跡優(yōu)化的算法，有粒子群優(yōu)化算法、模擬退火算法、差分進化算法、遺傳算法，遺傳算法和粒子群算法原理已在2.1節(jié)介紹，不再贅述其原理。

4.1 傳統(tǒng)算法

4.1.1 差分進化算法 由Storn等[36]在1995年首次提出，是一種簡單而有效的基于種群的全局優(yōu)化算法。在尋優(yōu)過程中，先從父代個體中選擇兩個個體做差，得到差分矢量，選擇一個個體與差分矢量求和得到實驗個體，其次與對父代個體與相應(yīng)實驗個體進行交叉操作，產(chǎn)生新的個體，最后在父代和子代中選擇符合要求的個體，逐次迭代，直到尋優(yōu)結(jié)束。差分進化算法有很強的語用性、并行性及魯棒性，但容易出現(xiàn)搜索停滯，容易陷入早熟收斂。

王君等[37]提出一種多種群移民差分進化算法，移民操作指在完成兩個種群內(nèi)的變異、交叉和競爭操作后，交換兩個種群中的一定數(shù)量的個體，采用一種帶有邊界約束條件求極值問題的方法，并將其應(yīng)用于工業(yè)機器人的軌跡規(guī)劃中增加了算法的全局搜索能力。韓敏等[38]將混沌映射引入到差分進化算法當中去，具體將混沌映射運用到了群體初始化和子代重構(gòu)兩個方面，使得全局搜索能力和局部搜索能力得以平衡，改善了早熟現(xiàn)象，實現(xiàn)了在線優(yōu)化。

4.1.2 遺傳算法 周小燕等[39]針對時間最優(yōu)，提出一種基于種群集散狀態(tài)的改進自適應(yīng)遺傳算子，采用優(yōu)勝劣汰選擇策略，動態(tài)的補充子代新個體，先變異后交叉，以此來避免早熟，收斂速度更快，擁有更強的尋優(yōu)能力。Yu等[40]以時間最優(yōu)為目標，對一般的自適應(yīng)遺傳算法中的交叉概率和變異概率作余弦調(diào)整，交叉概率及突變概率不為固定值，滿足種群進化的客觀規(guī)律，并采用算法優(yōu)化每個關(guān)節(jié)在插補點的時間間隔，大大縮短了每個關(guān)節(jié)的運行時間。李小為等[2]提出自適應(yīng)參數(shù)調(diào)節(jié)機制對遺傳算法進行改進，進化前期，設(shè)置較大的交叉概率以保證更新速度加快、搜索范圍增大，進化后期，減小較優(yōu)個體的交叉概率，使得適應(yīng)度較大的個體保持最優(yōu)、并使較差個體向較優(yōu)個體靠近，并在遺傳操作中，將父代最優(yōu)個體替換掉子代最差個體，改進后的遺傳算法有效的解決了遺傳算法收斂速度慢、精度低、易陷入局部最優(yōu)等問題，用改進后的遺傳算法來優(yōu)化3-5-3多項式插值，在滿足限制速度的情況下，機械手可以按照軌跡快速的運行，以此來實現(xiàn)時間最優(yōu)。

4.2 基于仿生學(xué)算法

4.2.1 粒子群算法 馮斌等[41]以時間最優(yōu)為優(yōu)化目標提出一種改進的粒子群算法，在選擇粒子過程中，首先驗證粒子是否符合約束條件，然后計算出符合約束條件粒子的適應(yīng)度值，選取一系列適應(yīng)度值最小的作為全局最優(yōu)粒子，從而得到最優(yōu)解，即符合時間最優(yōu)軌跡規(guī)劃;針對多目標優(yōu)化問題，由于多目標優(yōu)化問題中不存在最優(yōu)解，符合最優(yōu)解條件的是一個最優(yōu)解集合，這個最優(yōu)解集合是綜合不同目標函數(shù)之后得到的。施祥玲等[42]基于對時間、能量、脈動三種參數(shù)求解最優(yōu)軌跡，提出多目標粒子群優(yōu)化算法，是以五次NEURBS曲線為基礎(chǔ)，構(gòu)建了歸一化權(quán)重目標函數(shù)法，進行期望解的選取，得到優(yōu)化軌跡。Gao等[43]提出了一種基于CRP-S80機器人的粒子群算法對4-3-4多項式插值優(yōu)化，首先給初始粒子分配均勻的數(shù)值;其次在關(guān)節(jié)多項式插值的時間搜索空間中，隨機生成粒子，并設(shè)置粒子群初始值的范圍，通過求解4-3-4多項式的三個周期的系數(shù)，得出速度和加速度，進而求得適應(yīng)度函數(shù)的值;最后，通過更新粒子群的速度和位置獲得新粒子，如果不滿足速度和加速度的約束，則返回第三步獲得新粒子，直至滿足條件為止。

4.2.2 模擬退火算法 模擬退火算法思想起源于人類對于固體退火原理的認知，研究發(fā)現(xiàn)固體中的粒子在高溫環(huán)境下的自身的能量較高，活動隨意無序，但隨著時間推移，固體漸漸降溫，導(dǎo)致粒子的能量減小，活力降低。根據(jù)這一研究衍生出模擬退火算法，將固體的內(nèi)能對應(yīng)于優(yōu)化目標，將固體分子在空間的排列狀態(tài)對應(yīng)于自變量，算法實現(xiàn)的目標為一個使系統(tǒng)的能量達到最小組合狀態(tài)。模擬退火算法使用靈活、描述簡單、運行效率高、初始條件限制少，但收斂速度慢，且容易陷入最優(yōu)解。

Yao等[44]在模擬退火算法中加入了適應(yīng)度懲罰函數(shù)用來求解非線性約束最優(yōu)解問題，通過模擬退火算法和適應(yīng)度懲罰函數(shù)縮短了機器人到達預(yù)定位置所用的時間，并保證了機器人運行的平穩(wěn)性。Chen等[45]以時間最優(yōu)為目標，在搜索過程中引入隨機因子，在搜索過程中，避免陷入局部最優(yōu)。

針對軌跡優(yōu)化問題具體介紹了四種算法，表3為四種算法優(yōu)缺點比較。

5 結(jié)論

本文設(shè)計了機械手的路徑規(guī)劃、軌跡規(guī)劃、軌跡優(yōu)化等運動規(guī)劃技術(shù)的算法框架，總結(jié)歸納了所涉及到的相關(guān)算法，并對其原理、利弊及適用場景進行了對比分析。結(jié)合各類算法的優(yōu)缺點和適用場景，實現(xiàn)機械手運動規(guī)劃設(shè)計，更好滿足機械手的人機環(huán)境友好、運動精度和工作效率等性能，為機械手運動規(guī)劃設(shè)計提供了參考依據(jù)。例如遺傳算法與蟻群算法相結(jié)合，可以改進蟻群算法局部極小值路徑規(guī)劃的缺陷。

參考文獻

[1]ZHANG H， WANG Y， ZHENG J， et al. Path planning of industrial robot based on improved RRT algorithm in complex environments[C]// IEEE Access. IEEE，2018：53296-53306.

[2]李小為，胡立坤，曾憲金.基于改進遺傳算法的機器人時間最優(yōu)軌跡規(guī)劃[J].廣西大學(xué)學(xué)報（自然科學(xué)版）， 2014，39（5）：1020-1026.

[3]CHENG F， JI W， ZHAO D， et al. Apple picking robot obstacle avoidance based on the improved artificial potential field method[C]//2012 IEEE Fifth International Conference on Advanced Computational Intelligence （ICACI）， Nanjing，2012：909-913.

[4]ZHOU H， ZHOU S， JIA Y， et al. Trajectory optimization of pickup manipulator in obstacle environment based on improved artificial potential field method[J]. Applied Sciences， 2020，10（3）：935.

[5]OU L， LIU W， YAN X， et al. A review of representation， model， algorithm and constraints for mobile robot path planning[C]//2018 IEEE 4th Information Technology and Mechatronics Engineering Conference（IEOEC）. Chongqing，2018：563-569.

[6]SAVSANI P， JHALA R L， SAVSANI V J. Comparative study of different metaheuristics for the trajectory planning of a robotic arm[J]. IEEE Systems Journal，2016，10（2）：697-708.

[7]KHATIB O. Real-time obstacle avoidance for manipulators and mobile robots[J]. The International Journal of Robotics Research. 1986，5（1）：90-98.

[8]ZHANG N， ZHANG Y， MA C， et al. Path planning of six-DOF serial robots based on improved artificial potential field method[C]//2017 IEEE International Conference on Robotics and Biomimetics（ROBIO）. Macau，2017：617-621.

[9]WANG X， XI Y， GU C， et al. An improved potential field method of the manipulator obstacle avoidance planning based on polishing path[C]//2019International Conference on Advances in Construction Machinery and Vehicle Engineering（ICACMVE）. Changsha，2019：143-147.

[10] GAI S N， SUN R， CHEN S J， et al. 6-DOF robotic obstacle avoidance path planning based on artificial potential field method[C]//2019 16th International Conference on Ubiquitous Robots（UR）. Jeju，2019：165-168.

[11] 賈慶軒， 陳鋼， 孫漢旭， 等.基于A*算法的空間機械臂避障路徑規(guī)劃[J].機械工程學(xué)報， 2010，46（13）：109-115.

[12] 汪首坤， 邸智， 王軍政， 等.基于A*改進算法的機械臂避障路徑規(guī)劃[J].北京理工大學(xué)學(xué)報， 2011，31（11）：1302-1306.

[13] LAVALLE S M. Rapidly-exploring random trees： A new tool for path planning[J].Computer Science Dept， 1998，98.

[14] 李季， 史晨發(fā)， 邵磊， 等.基于改進RRT算法的6-DOF機器人路徑規(guī)劃[J].計算機應(yīng)用與軟件， 2020，37（9）：221-226.

[15] LIU Y， ZUO G. Improved RRT path planning algorithm for humanoid robotic arm[C]//2020 Chinese Control And Decision Conference（CCDC）.Hefei，2020：397-402.

[16] 馬慧麗，魯照權(quán)，王壽庭.基于改進RRT算法的機械臂路徑規(guī)劃研究[J].機械設(shè)計與研究， 2020，36（4）：42-46.

[17] KAVRAKI L E， SVESTKA P， LATOMBE J， et al. Probabilistic roadmaps for path planning in high-dimensional configuration spaces[C]// IEEE Transactions on Robotics and Automation.1996：566-580.

[18] SHARMA P， GENTILINI I， SHIMADA K. Optimizing path for kinematically redundant robotic inspection system using obstacle based probabilistic roadmap and genetic algorithm[C]//2016 IEEE Region 10 Conference（TENCON）. Singapore，2016：2716-2721.

[19] YANG J， DYMOND P， JENKIN M. Practicality-based probabilistic roadmaps method[C]//2011 Canadian Conference on Computer and Robot Vision. IEEE，2011：102-108.

[20] DORIGO M， MANIEZZO V， COLORNI A. Ant system： Optimization by a colony of cooperating agents[C]// IEEE Transactions on Systems，1996：29-41.

[21] 趙華東，雷超帆，江南.基于改進蟻群算法的六自由度機械臂路徑規(guī)劃[J].鄭州大學(xué)學(xué)報（理學(xué)版）， 2020，52（1）：120-126.

[22] SHEN H. A study of welding robot path planning application based on Genetic ant colony hybrid algorithm[C]//2016 IEEE Advanced Information Management， Communicates， Electronic and Automation Control Conference （IMCEC）. Xi′an，2016：1743-1746.

[23] LI F， ZHAO J， SONG X， et al. Path planning of 6-DOF humanoid manipulator based on improved ant colony algorithm[C]//2012 24th Chinese Control and Decision Conference（CCDC）. Taiyuan，2012：4158-4161.

[24] ZHAO J， ZHAO L， LIU H. Motion planning of hyper-redundant manipulators based on ant colony optimization[C]//2016 IEEE International Conference on Robotics and Biomimetics（ROBIO）. Qingdao， 2016：1250-1255.

[25] ZHANG W， LU H， MA M， et al. The manipulator path planning of bolt disassembly based on improved genetic algorithm and A* algorithm[C]//2019 6th International Conference on Systems and Informatics（ICSAI）. Shanghai， 2019：176-182.

[26] RAMIREZ V A， GARCIA A P， PUENTE F J M， et al. Path planning using genetic algorithms for mini-robotic tasks[C]//2004 IEEE International Conference on Systems， Man and Cybernetics. Hague，2004：3746-3750.

[27] EBERHART R， KENNEDY J. A new optimizer using particle swarm theory[C]//Proceedings of the Sixth International Symposium on Micro Machine and Human Science.Nagoya，1995：39-43.

[28] 袁蒙恩，陳立家，馮子凱.基于單目視覺的多種群粒子群機械臂路徑規(guī)劃算法[J].計算機應(yīng)用， 2020，40（10）：2863-2871.

[29] LV X， YU Z， LIU M， et al. Direct trajectory planning method based on IEPSO and fuzzy rewards and punishment theory for Multi-Degree-of freedom manipulators[C]// IEEE Access. IEEE，2019：20452-20461.

[30] SHEN Y， JIA Q， CHEN G， et al. Study of rapid collision detection algorithm for manipulator[C]//2015 IEEE 10th Conference on Industrial Electronics and Applications（ICIEA）. Auckland，2015：934-938.

[31] 孔慶博，袁亮，蔣偉等.一種改進的工業(yè)機器人軌跡規(guī)劃方法研究[J].機械傳動， 2019，43（2）：30-36.

[32] LI C， QU Y， SHAN L， et al. Research on path optimization algorithm of the 6-DOF manipulator[C]//2019 Chinese Automation Congress（CAC）.Hangzhou，2019：3135-3140.

[33] 鄭濤，劉滿祿.一種機械臂分段插值軌跡規(guī)劃方法[J].機械設(shè)計與制造， 2020 （3）：261-264.

[34] 董甲甲，王太勇，董靖川，等.改進B樣條曲線應(yīng)用于6R機器人軌跡優(yōu)化[J].中國機械工程， 2018，29（2）：193-199.

[35] WAN N， XU D， YE H. Improved cubic B-spline curve method for path optimization of manipulator obstacle avoidance[C]//2018 Chinese Automation Congress（CAC）. Xi′an，2018：1471-1476.

[36] STORN R，PRICE K. Differential evolution-a simply and efficient adaptive scheme for global optimization over continuous spaces[J].Technical report International Computer Science Institute， 1995， 23（1）： .

[37] 王君，陳智龍，楊智勇，等.基于改進DE算法的工業(yè)機器人時間最優(yōu)軌跡規(guī)劃[J].組合機床與自動化加工技術(shù)， 2018（6）：42-46.

[38] 韓敏，王明慧，范劍超.基于改進差分進化算法的在線軌跡優(yōu)化[J].控制與決策， 2012，27（2）：247-251.

[39] 周小燕，高峰，鮑官軍.基于IAGA的機械手時間最優(yōu)軌跡規(guī)劃[J].機電工程， 2009，26（8）：1-3.

[40] YU H， MENG Q， ZHANG J， et al. Time-optimal trajectory planning of robot based on improved adaptive genetic algorithm[C]//2018 Chinese Control And Decision Conference（CCDC）. Shenyang，2018：6379-6402.

[41] 馮斌，劉峰，鄭飂默.基于粒子群算法的機器人關(guān)節(jié)空間最優(yōu)運動軌跡規(guī)劃[J].組合機床與自動化加工技術(shù)， 2018（5）：1-4.

[42] 施祥玲，方紅根.工業(yè)機器人時間—能耗—脈動最優(yōu)軌跡規(guī)劃[J].機械設(shè)計與制造， 2018（6）：254-257.

[43] GAO M， DING P， YANG Y. Time-optimal trajectory planning of industrial robots based on particle swarm optimization[C]//2015 5th International Conference on Instrumentation and Measurement， Computer， Communication and Control（IMCCC）. Qinhuangdao，2015：1934-1939.

[44] YAO J， SUN C， ZHANG L， et al. Time optimal trajectory planning based on simulated annealing algorithm for a train uncoupling robot[C]//2017 29th Chinese Control And Decision Conference（CCDC）. Chongqing，2017：5781-5785.

[45] CHEN Z， MA L， SHAO Z. Path planning for obstacle avoidance of manipulators based on improved artificial potential field[C]//2019 Chinese Automation Congress（CAC）. Hangzhou，2019：2991-2996.

Abstract： Robot motion planning under obstacle condition is a research hotspot of robot technology. It can be divided into three parts： namely path planning， trajectory planning and trajectory optimization. The pros and cons of motion planning affect the work quality and efficiency of robot. In this paper， a robot motion planning algorithm framework is designed based on obstacle conditions， that is， path planning is used to effectively avoid obstacles， trajectory planning ensures continuous and smooth motion， and trajectory optimization achieves efficient operation， so as to meet the needs of different working conditions. At the same time， the related algorithms involved in motion planning are described， and their advantages and disadvantages， applicable scenarios and research progress are compared and analyzed， so as to provide reference for manipulator motion planning and design.

Keywords：

manipulator; path planning; trajectory planning;trajectory optimization; motion planning algorithm