利用兩階段遺傳算法的機械手最優(yōu)軌跡控制仿真

龔暢，王華君，李榮，徐平平

?

利用兩階段遺傳算法的機械手最優(yōu)軌跡控制仿真

龔暢，王華君，李榮，徐平平

針對大多數(shù)機器人最優(yōu)軌跡規(guī)劃控制算法成本較高的問題，提出了一種兩階段分析-進化算法，分析算法基于間接開環(huán)最優(yōu)控制問題，進化算法基于遺傳算法。首先，利用遺傳算法產(chǎn)生最優(yōu)控制；然后，新的次優(yōu)軌跡通過最優(yōu)控制生成，計算每個最優(yōu)解的成本函數(shù)，并為下一個步驟選擇最優(yōu)解做準備；最后，遺傳算法使用獲得的軌跡產(chǎn)生新一代起始點，迭代直到實現(xiàn)最小成本值。算法的驗證由兩個仿真系統(tǒng)組成：具有完整約束的兩關(guān)節(jié)機械手和具有非完整約束的移動機械手。運用本文算法后，第一個仿真系統(tǒng)的成本降低了92.3%，第二個仿真系統(tǒng)獲得的最優(yōu)成本明顯低于只使用最優(yōu)控制時的成本，表明其算法可應(yīng)用于實際機器人軌跡規(guī)劃控制系統(tǒng)。

機器人；移動機械手；最優(yōu)軌跡控制；分析-進化；兩階段遺傳算法

0 引言

機器人最優(yōu)軌跡規(guī)劃控制[1,2]在越來越發(fā)達的人工智能和制造業(yè)等領(lǐng)域占有重要地位，但通常需要花費較高的成本，因此，找到一種能夠降低成本的軌跡規(guī)劃算法顯得非常重要[3,4]。

已經(jīng)有很多學(xué)者對機器人最優(yōu)規(guī)劃控制進行了研究。文獻[5]考慮機器人各關(guān)節(jié)速度、加速度和力矩約束，在末端執(zhí)行器和任給軌跡下進行時間最優(yōu)規(guī)劃，采用遺傳算法和動力學(xué)方程縮短了規(guī)劃時間，然而，動力學(xué)方程和遺傳算法簡單的結(jié)合并不能保證結(jié)果大多數(shù)情況下正確。

文獻[6]引入了一種方法，使用路徑參數(shù)的三階導(dǎo)數(shù)確定機械手的平滑和時間最優(yōu)路徑，通過在轉(zhuǎn)矩率上施加限制得到軌跡所需的光滑度，使用可變?nèi)莶罘ㄇ蠼庾顑?yōu)問題。雖然該方法可以返回一個局部最小值，但不適用于整個系統(tǒng)。

文獻[7]為二階欠驅(qū)動機械系統(tǒng)提出了一種利用運動學(xué)可控概念的軌跡規(guī)劃，可以獲得一個最佳的時間解，然而，卻忽略了其他路徑參數(shù)。

本文提出一種兩階段分析-進化算法，可分析動力學(xué)方程，采用最優(yōu)控制，搜索所有可能的起始點，實現(xiàn)具有最小成本的軌跡。進化過程基于遺傳算法[8]，定義新選擇算子來為交叉運算選擇合適的軌跡，實現(xiàn)了全局最優(yōu)控制，具有非完整約束的系統(tǒng)適用性。

1 算法架構(gòu)

根據(jù)導(dǎo)致兩點邊值問題的間接最優(yōu)控制，提出兩階段迭代算法以獲得全局最優(yōu)軌跡，為了啟動該算法，使用初始猜測有兩個目的：（a）作為起始點求解最優(yōu)控制，（b）作為GA的第一個種群。算法的整體架構(gòu)如圖1所示：

定義成本函數(shù)之后，得到最優(yōu)控制的必要條件，采用這些必要條件來尋找最佳控制輸入[9]。

2 算法詳細設(shè)計

提出的軌跡規(guī)劃控制算法的詳細流程如圖2所示：

第一階段優(yōu)化控制所用狀態(tài)的起始點由GA生成，然后通過最優(yōu)控制，完成優(yōu)化的第二階段，并產(chǎn)生具有低成本函數(shù)的新路徑。由于最優(yōu)控制可能會陷入局部最優(yōu)解，產(chǎn)生的路徑發(fā)送到GA，用于生成起始點，并開始迭代新步驟，這個過程一直持續(xù)到實現(xiàn)最低成本函數(shù)。本文算法包括4個主要步驟：（1）推導(dǎo)動力學(xué)方程；（2）求解最優(yōu)控制，并開發(fā)TPBVP；（3）由GA生成最優(yōu)控制起始點，反之亦然；（4）停止條件（最低成本并不隨著迭代周期變化）。

2.1 最優(yōu)控制

（2）

（4）

最優(yōu)控制解(此處由*表示)必須滿足必要條件如公式（6）-（9）：

（6）

（8）

（9）

因此，根據(jù)式（8），最優(yōu)條件可通過相對于狀態(tài)、合作狀態(tài)和控制微分哈密頓函數(shù)得到，如公式（11）~（13）：

（11）

（13）

2.2 利用GA產(chǎn)生起點

為了滿足上述問題，采用遺傳算法來產(chǎn)生最優(yōu)控制方法中合適的起點。邊值問題（Boundary Value Problem，BVP）[10]可用不同軟件包的有效命令求解，數(shù)據(jù)包用數(shù)值方法來解決這個問題，數(shù)值方法需要起始點（或初始解），但由于對起始點敏感，導(dǎo)致邊值問題不可靠，它可能會陷于局部最小值[11]，GA提供起始點，檢查起始點，并選擇最佳起始點。起始點由下式給出公式（15）：

2.3 編碼

即每行表示每個狀態(tài)，正比于時間，如公式（17）、（18）

（17）

系數(shù)可以包含任意位數(shù)，這里系數(shù)由8位數(shù)字表示，第一組4位用作系數(shù)的整數(shù)部分，第二組用作系數(shù)的小數(shù)部分。為了操作這些數(shù)字，以位定位每個數(shù)字，第九位表示正或負，如果數(shù)字為正，該位將是“1”，如果數(shù)字為負，該位將是“0”。編碼示例如圖3所示：

2.4 選擇算子

選擇算子是用于交叉操作的適合染色體的選擇，越合適的染色體，選擇它的概率就越大。為了選擇配對染色體，首先選擇一些低成本染色體，假設(shè)選擇了個染色體，每個染色體的重復(fù)數(shù)對應(yīng)于式（19）。由于最低成本非常重要，新成本函數(shù)根據(jù)式（20）定義，如公式（19）、（20）：

（20）

現(xiàn)在，虛擬空間有50l個房間，每個染色體復(fù)制自身重復(fù)數(shù)次，并占據(jù)房間。假設(shè)交叉數(shù)等于n，則隨機選擇2n個房間，從而，選擇房間中的2n個染色體進行交叉操作。應(yīng)當指出的是，因子“50”只是為了提高選擇數(shù)，從而提高染色體選擇的精確度，它可以為任意數(shù)。例如，假設(shè)n=2，l=4，每個染色體的成本和索引如表1所示：

表1 重復(fù)函數(shù)示例

根據(jù)圖4所示：

考慮到每個染色體的重復(fù)函數(shù)的數(shù)目，從房間中選擇4（或2）個，最后，如表2所示：

表2 選擇的配對染色體

2.5 交叉

使用兩點交叉，以便選擇點的整數(shù)和小數(shù)部分，點隨機選擇。通過選擇算子選擇兩個染色體后，一起替代選擇的染色體的全部系數(shù)的位，從第一點到第二點。交叉運算的示例如圖5所示：

2.6 突變

突變意味著33%的染色體應(yīng)用于交叉，選擇每個染色體33%的狀態(tài)，然后，選擇多項式的兩個系數(shù)，從系數(shù)中選擇一個數(shù)字，改變?yōu)榱硪粋€，所有選擇隨機進行。突變的示例如圖6所示：

3仿真實驗

3.1 仿真系統(tǒng)1：2關(guān)節(jié)機械手

第一個系統(tǒng)是2關(guān)節(jié)機械手如圖7所示：

物理參數(shù)由文獻[5]給出，如表3所示：

表3 兩關(guān)節(jié)機械手的物理參數(shù)

這個例子中，不存在對控制輸入的任何約束，文獻[5]是能量最優(yōu)軌跡規(guī)劃，最終時間=1秒，初始條件是，最終條件是。權(quán)重為，（限制權(quán)重）=1，且=1。雖然該系統(tǒng)有完整約束，哈密頓定義為公式（31）：

關(guān)節(jié)扭矩如圖8所示：

（a）關(guān)節(jié)扭矩

（b）末端執(zhí)行器的軌跡

（c）每一次迭代中的最小成本

圖8 關(guān)節(jié)機械手仿真結(jié)果

圖8（a）所示為關(guān)節(jié)扭矩，扭矩比文獻[5]算法少，表明了本文算法的有效性。圖8（b）表示軌跡上機械手配置，圖8（c）表示每一次迭代中的最小成本，如第一次迭代中最小成本約為1180，最后一次迭代為721，停止條件是50次迭代下最低成本不改變。

3.2 仿真系統(tǒng)2：非完整約束移動機械手

第二個仿真系統(tǒng)是3關(guān)節(jié)(PUMA)機械手[12]，環(huán)境中有障礙物，如圖9所示：

表4 WMM參數(shù)和慣性特性

狀態(tài)向量定義如公式(32)：

（a）中心軸線相對于平臺的角位置

（b）機械手關(guān)節(jié)扭矩

（c）車輪扭矩

（d）軌跡內(nèi)移動機械手

（e）每次迭代中的最低成本

圖10 -關(guān)節(jié)移動機械手仿真結(jié)果

10（a），關(guān)節(jié)和車輪隨時間的關(guān)節(jié)扭矩值如圖10（b）和10（c）所示。最優(yōu)控制模式中轉(zhuǎn)矩值非常大，不能與組合最優(yōu)控制模式相媲美。圖10（d）是環(huán)境中機器人的軌跡，說明本文算法適用于有障礙的環(huán)境。圖10（e）是每次迭代的最小成本。結(jié)果表明，由最優(yōu)控制生成的軌跡不唯一收斂于全局最佳軌跡，但本文算法在86次迭代后得到全局最小值。

在仿真系統(tǒng)2中，本文算法獲得的最優(yōu)成本是5.5e-4，而僅最優(yōu)控制獲得的成本為1.8e-3。該算法可以用于包括障礙物的環(huán)境，還可用于具有完整和/或不完整約束的系統(tǒng)。

3.3 時間復(fù)雜度分析

GA搜索所有可能解以獲得最優(yōu)路徑。本文使用進化和分析方法的優(yōu)點，提出雙階迭代公式。引入遺傳算法新算子，以減少所需要的時間。第一階段優(yōu)化控制所用狀態(tài)的起始點由GA生成，然后通過最優(yōu)控制，完成優(yōu)化的第二階段，并產(chǎn)生具有低成本函數(shù)的新路徑。這個過程涉及迭代次數(shù)和GA算法的變量，其時間復(fù)雜度大約為，其中和分別為多項式階次和狀態(tài)數(shù)，k為達到要求的迭代次數(shù)或最高迭代次數(shù)，仿真實驗中，對于兩機械手k=50，對于三機械手，k=86。

4 總結(jié)

本文提出了尋找全局最優(yōu)軌跡規(guī)劃的新算法，即基于遺傳算法和間接最優(yōu)控制，同時考慮了動力學(xué)方程。最優(yōu)控制的分析屬性允許動力學(xué)方程具有適當接口，利用GA搜索所有可能解獲得最優(yōu)軌跡。本文使用進化和分析方法的優(yōu)點，提出新的雙階迭代公式。此外，引入遺傳算法新算子，以減少所需要的時間。仿真結(jié)果表明，本文算法明顯降低了最低成本，即使在有障礙物的情況下依然表現(xiàn)良好，該算法可以應(yīng)用于實際的機器人軌跡規(guī)劃控制系統(tǒng)，因為兩關(guān)節(jié)和三關(guān)節(jié)機械手是機器人的必要裝置，而且處理有障礙物和較低的軌跡規(guī)劃時間也是實際機器人軌跡控制系統(tǒng)的特點。

參考文獻：

[1] 彭建盛, 李興, 秦志強等. 智能機器人仿真系統(tǒng)設(shè)計[J]. 計算機仿真, 2013, 30(5): 358-361.

[2] 徐文福, 李成, 梁斌等. 空間機器人捕獲運動目標的協(xié)調(diào)規(guī)劃與控制方法[J]. 自動化學(xué)報, 2009, 35(9): 1216-1225.

[3] 張雨濃, 陳錦浩, 勞穩(wěn)超等. 多類單輸入多項式神經(jīng)網(wǎng)絡(luò)預(yù)測能力比較[J]. 系統(tǒng)仿真學(xué)報, 2014, 26(1): 1047-1053.

[4] Nayl T, Nikolakopoulos G, Gustafsson T. Real-Time Bug-Like Dynamic Path Planning for an Articulated Vehicle[C]//Informatics in Control, Automation and Robotics. Springer International Publishing, 2015: 201-215.

[5] Ulusoy A, Smith S L, Belta C. Optimal Multi-robot path planning with LTL constraints: guaranteeing correctness through synchronization[C]//Distributed Autonomous Robotic Systems. Springer Berlin Heidelberg, 2014: 337-351.

[6] Saijo H, Kuroki Y. Articulated robot and method of controlling the motion of the same[D]. US, 2001.

[7] Shiriaev A S, Freidovich L B, Spong M W. Controlled Invariants and Trajectory Planning for Underactuated Mechanical Systems[J]. IEEE Transactions on Automatic Control, 2014, 59(9):2555 - 2561.

[8] 于海璁, 陸鋒. 一種基于遺傳算法的多模式多標準軌跡規(guī)劃方法[J]. 測繪學(xué)報, 2014, 27(1): 89-96.

[9] Zhou Z, Zhang Z, Luo X. A Fuzzy Path Preview Algorithm for the Rice Transplanting Robot Navigation System [J]. Journal of Software, 2014, 9(4): 881-888.

[10] 周文卷. 復(fù)雜環(huán)境下自主移動機器人軌跡規(guī)劃方法的研究[D]. 吉林大學(xué), 2014.

[11] 李國勇, 閆芳, 郭曉峰. 基于遺傳算法的灰色神經(jīng)網(wǎng)絡(luò)優(yōu)化算法[J]. 控制工程, 2013, 20(5): 934-937.

[12] Gregory J, Olivares A, Staffetti E. Energy-optimal trajectory planning for robot manipulators with holonomic constraints [J]. Systems & Control Letters, 2012, 61(2): 279-291.

Simulation of Optimal Trajectory Planning Controlling for Moving Manipulator Using Two-stage Analysis-evolutionary Algorithm

Gong Chang1, Wang Huajun1, Li Rong1, Xu Pingping2

(1. School of Engineering, Taihu University of Wuxi, Wuxi 214064, China;2. School of Information Science and Engineering, Southeast University, Nanjing 211189, China)

As the problem of high cost in optimal manipulator trajectory planning algorithm, a two-stage analysis-evolutionary algorithm is proposed. The analysis algorithm is based on indirect open-loop optimal control problem. The evolutionary algorithm is based on Genetic algorithm (GA). Firstly, the starting point of optimal control problems results from the optimal solution by GA. Then, a new sub-optimal path is generated by the optimal control, and the cost function of every optimal solution is calculated, preparing for the next step to choose the optimal solution. Finally, the new starting point is obtained by the new generation of the path using GA. The iteration is ended until the minimum cost value can be obtained. Verification algorithm simulation system consists of two components, a system is a two-joint mobile manipulator with a complete constraint, and the other is a mobile manipulator with a non-complete constraint. By using the proposed algorithm, the cost of the first simulation system reduces 92.3%, and the optimal cost of a second simulation system is clearly less than that of only using optimal controlling. Simulation results show that the algorithm can be applied to any robot path planning.

Robot; Moving Manipulator; Optimal Trajectory Control; Analysis-evolutionary; Two-stage Genetic Algorithm

1007-757X(2016)04-0018-05

TP242.2

A

（2015.09.11）

江蘇省高校自然科學(xué)研究項目（14KJB520036）

龔 暢（1981-），女（漢），海門人，無錫太湖學(xué)院，工學(xué)院，講師，碩士，研究方向：機器人、人工智能等，無錫，214064

王華君（1979-），男（漢），宜興人，無錫太湖學(xué)院，工學(xué)院，講師，碩士，研究方向：機器人、模式識別等，無錫，214064

李 榮（1978-），女（漢），江蘇淮安人，無錫太湖學(xué)院，工學(xué)院，講師，碩士，研究方向：機器人控制、人工智能等，無錫，214064

徐平平（1957-），女（漢），南京人，東南大學(xué)，信息科技與工程學(xué)院，教授，博導(dǎo)，博士，研究方向：機器人控制、物聯(lián)網(wǎng)等，南京，211189