崔迎超，汪志鋒，徐潔，任明

改進HS算法在碼垛機器人軌跡規(guī)劃中的應(yīng)用

崔迎超，汪志鋒，徐潔，任明

（上海第二工業(yè)大學(xué)，上海 201209）

解決碼垛機器人在抓取目標(biāo)物時需要滿足最大速度約束條件、較短運行時間以及運行平穩(wěn)性等問題。以Func200id六軸工業(yè)機器人為研究對象，通過機器人的各關(guān)節(jié)尺寸關(guān)系計算其DH參數(shù)，并建立仿真模型。對改進的HS算法通過增加變異因子VF來改變算法的搜索策略，使得算法中的每個個體不但有機會參與到迭代的過程之中，而且有概率向最優(yōu)個體學(xué)習(xí)，加快算法的收斂速度。通過對4種算法在6種不同測試函數(shù)下分別運行30次的對比實驗可知，改進后的HS算法相較于其他3種算法的尋優(yōu)能力更強，收斂速度更快。改進后的HS算法能夠明顯縮短碼垛機器人的工作時間，且運行連續(xù)平穩(wěn)，在其他工業(yè)場景下也具有一定的應(yīng)用價值。

碼垛機器人；軌跡規(guī)劃；HS算法；時間優(yōu)化；3-5-3多項式插值

在工業(yè)生產(chǎn)過程中，碼垛機器人的自動化、高效化的優(yōu)點已逐漸替換傳統(tǒng)的人力操作。碼垛型關(guān)節(jié)式機器人由于其具有結(jié)構(gòu)簡單、操作精度高以及工作場景適應(yīng)性強的特點，已廣泛應(yīng)用在產(chǎn)品包裝、設(shè)備制造、倉庫儲存等眾多場景中[1]。在對機器人運動規(guī)劃過程中，研究其時間優(yōu)化方法，對提高工業(yè)制造過程中的生產(chǎn)效率具有顯著意義。

在機械臂軌跡規(guī)劃中，根據(jù)規(guī)劃的位置不同，分為笛卡爾空間規(guī)劃和關(guān)節(jié)空間規(guī)劃2種類型。由于笛卡爾空間規(guī)劃針對機器人末端執(zhí)行器，需要對位姿實時逆向求解，計算量龐大，且存在機械臂奇異的現(xiàn)象[2]，所以本文采用關(guān)節(jié)空間規(guī)劃進行實驗研究。

在擬合機械臂運動曲線的方法中，多項式插值算法計算簡單，使用范圍最廣，但是單一的多項式函數(shù)不能區(qū)分分段點的速度或加速度[3]。B樣條插值算法雖然具有局部性和連續(xù)性的特點，但是無法保證運動曲線的光滑性[4]。樣條插值算法是將運動曲線分為若干段，每段的運動曲線都使用多項式進行擬合。由于多項式系數(shù)是在分段點前后相同狀態(tài)下得出，故而能夠保證分段點處各分段的連續(xù)性和平滑性。徐鵬飛等[5]使用4-3-4分段多項式對工業(yè)碼垛機器人進行軌跡規(guī)劃，提高了碼放貨物過程的流暢性、穩(wěn)定性和連續(xù)性。郭鑫鑫等[2]使用3-5-3分段多項式對改進的螢火蟲算法進行優(yōu)化軌跡設(shè)計，縮短了機械臂的運行時間。

啟發(fā)式算法通常是模擬現(xiàn)實世界的物理規(guī)則，因其結(jié)構(gòu)簡單的特點，已廣泛應(yīng)用于工業(yè)機器人。Wang等[6]利用改進鯨魚優(yōu)化算法，楊星濤等[7]使用改進遺傳算法進行最優(yōu)時間計算。為解決蟻群算法的不確定搜索、搜索效率較低的問題，魏立新等[8]提出了將蟻群算法與DWA算法相結(jié)合的融合算法。米根鎖等[9]通過改變步長因子來提高布谷鳥算法尋優(yōu)效率，使工業(yè)機器人具有更好的魯棒性。

1 關(guān)節(jié)空間規(guī)劃問題

1.1 3-5-3多項式插值函數(shù)

在機械臂軌跡規(guī)劃過程中，若使用單一的多項式插值函數(shù)，會使得機械臂在運行過程中，某些路徑點會出現(xiàn)速度和加速度突然變化的現(xiàn)象。若使用單一的高次多項式，隨著次數(shù)的增加，除了計算成本的提高，插值的過程中還會引起“龍格現(xiàn)象”，影響機械臂運行的穩(wěn)定性和使用壽命。采用分段低次插值的思想，不僅可以避免插值曲線突變的現(xiàn)象，也可以在滿足計算要求的情況下，獲得高次插值的效果。本文采用3-5-3多項式插值函數(shù)來擬合曲線，該多項式第1段為三次多項式，第2段為五次多項式，第3段為三次多項式。具體公式見式（1）—（3）。

第1段曲線：

第2段曲線：

第3段曲線：

其中：

1.2 優(yōu)化目標(biāo)函數(shù)的選取

2 改進HS算法后的軌跡規(guī)劃

2.1 HS算法的基本思想

韓國學(xué)者Geem等[11]于2001年根據(jù)音樂劇場中樂師不斷調(diào)節(jié)手中樂器的音調(diào)來實現(xiàn)優(yōu)美的和聲提出了HS算法。該算法將不同樂器的音調(diào)作為變量，改變變量的過程來模擬樂師利用經(jīng)驗來調(diào)節(jié)音調(diào)的過程，最終使樂曲達到完美和聲狀態(tài)來找到最優(yōu)解[12]。HS算法相較于其他傳統(tǒng)的啟發(fā)式優(yōu)化算法，其操作簡單、參數(shù)較少、易實現(xiàn)尋優(yōu)策略等優(yōu)點被大量應(yīng)用在多目標(biāo)求解的應(yīng)用場景[13]。

2.2 改進的HS算法

在標(biāo)準(zhǔn)的HS算法中，每次即興創(chuàng)作只是修改群體中某個個體的信息，忽略了其他個體對群體的影響，尤其是較差的和聲個體，因此算法在迭代過程中極其依賴初始庫中最優(yōu)和聲代表。文獻[14]中提出將適應(yīng)度低的和聲與適應(yīng)度高的和聲在對稱區(qū)間內(nèi)生成新和聲的方法。雖然可以使和聲能夠更快地向好的和聲收斂，但是求解結(jié)果容易產(chǎn)生局部最優(yōu)值。

為了增加其他和聲與最優(yōu)和聲的關(guān)聯(lián)度，提高算法的全局搜索能力。改進HS算法采用每個和聲都有機會參與迭代的策略，增加變異因子VF（Variation Factor）。參數(shù)VF用來判斷是否對和聲進行修改，VF值較高時有利于加快算法的收斂速度，但是會增加程序的運行時間；VF值較低時雖然會提高和聲修改的輪空次數(shù)，但是不利于算法的快速收縮。

基本和聲算法中參數(shù)HMCR用來判斷被選中的和聲是擾動調(diào)節(jié)還是整體修改，在改進HS算法中HMCR被用來區(qū)分和聲修改范圍的大小，即一部分用于和聲整體修改的策略，可增加全局搜索的概率。一部分用于和聲中單個變量的修改，提高收斂速度。整體修改策略下新生成的和聲變量見式（10）。

當(dāng)HMCR值設(shè)置較小時，單個和聲從解析空間中隨機生成新的和聲概率提高，雖然有利于避免局部最優(yōu)解的現(xiàn)象發(fā)生，但是不利于提高算法的運行時間。當(dāng)設(shè)置的值較大時，最優(yōu)解可以在已有的和聲搜索庫中迅速收斂，但是可能會陷入局部最優(yōu)。

新變量擾動調(diào)節(jié)公式見式（12）。

參數(shù)PAR值的更改使得所有和聲都有機會向最優(yōu)和聲學(xué)習(xí)，能夠提高算法的收斂能力。但是如果PAR值設(shè)置得較大，會提高求得局部最優(yōu)的風(fēng)險。如果值設(shè)置的較小，單個和聲變量只能以帶寬（BW）的步長向最優(yōu)解移動，會增加算法的迭代次數(shù)。

改進的HS算法的操作步驟如下：

1）初始化參數(shù)。設(shè)置和聲記憶庫大?。℉MS）、最大迭代次數(shù)max、變異因子（VF）、和聲記憶庫取值范圍概率（HMCR）、音調(diào)微調(diào)方式概率（PAR）以及音調(diào)微調(diào)帶寬（BW）。

2）初始化種群HM。在可行域內(nèi)生成初始種群HM，其矩陣見式（13）。

3）即興創(chuàng)作產(chǎn)生新和聲，偽代碼如下所示：

for j=1:Tmax %即興創(chuàng)作開始

if rand < VF %對和聲記憶庫進行操作

if rand < HMCR %區(qū)分是否整體調(diào)節(jié)

if rand < PAR %選擇調(diào)節(jié)方式

xjnew= xjr+ rand×(xjbest–xjr)

end if

xjnew=xjr± rand × bw %擾動調(diào)節(jié)

end if

xjnew=xjL+ rand×(xjU–xjL)

end if

end for

改進HS算法的流程如圖1所示。

圖1 改進HS算法流程

圖1中自生成隨機數(shù)0開始到是否滿足停止條件為止，為步驟3即興創(chuàng)作產(chǎn)生新和聲的迭代過程。其中0、1和2均為隨機數(shù)，分別與VF值、HMCR值和PAR值進行比較，用來更新和聲庫。當(dāng)生成一組新的和聲成員后，將該和聲成員的優(yōu)化目標(biāo)函數(shù)值與現(xiàn)有和聲庫中最差成員進行對比，若優(yōu)于最差成員，將其替換，若弱于最差成員，則原有和聲庫不變。

3 仿真模型的建立

3.1 模型的建立

表1 Func200id機器人D-H參數(shù)

Tab.1 D-H parameters of Func200id robot

表2 各關(guān)節(jié)約束

Tab.2 Each joint constraint

表3 各關(guān)節(jié)運行路徑插值點

Tab.3 Interpolation points for each joint running path

根據(jù)上述條件，在Matlab中構(gòu)建機器人運動模型。設(shè)置改進HS算法的初始個體數(shù)HMS值為5，樂器數(shù)量為3，創(chuàng)作的次數(shù)max為200，HMCR值設(shè)置為0.95，PAR值為0.7，BW值為0.2，max范圍為[3, 3, 3]，min范圍為[0, 0, 0]。

3.2 VF值選取

由于VF值決定了程序的運行速度和函數(shù)的收斂速度，合適的VF值設(shè)定有助于系統(tǒng)更快地求解合適時間?？紤]到計算機的配置、運行環(huán)境以及隨機數(shù)生成的隨機性等因素，本文對不同VF值分別進行了10次求解的對比性實驗，其參數(shù)設(shè)置參考3.1節(jié)，對VF值求平均值，結(jié)果如表4所示。

表4 不同VF值求解結(jié)果平均值

Tab.4 Average solution results of different VF values

表4中，從整體來看，當(dāng)VF取值增大時，程序的運行時間也會增加。當(dāng)VF取值為0.1～0.5時，其程序的運行時間雖然較短，但所求解的變量并不是最優(yōu)解。當(dāng)VF值取0.8和0.9時程序的運行時間高于VF值取0.6和0.7時程序的運行時間，但所求解的變量值并非最優(yōu)解。從求解結(jié)果來看，VF值取0.7是優(yōu)于0.6的，故本文中VF值確定為0.7。

4 仿真結(jié)果與分析

4.1 改進HS算法仿真結(jié)果分析

為驗證改進HS算法的魯棒性和有效性，本文將HS、IHS、改進GA[7]等3種算法在約束函數(shù)（式（8）—（9））和5種經(jīng)典測試函數(shù)下優(yōu)化求解。表5中給出了5個經(jīng)典測試函數(shù)的表達式、搜索范圍、維度和最優(yōu)值。其中F1和F2為單峰函數(shù)，F(xiàn)3和F4為多峰函數(shù)，F(xiàn)5函數(shù)為二維的定維函數(shù)。

表5 5種經(jīng)典測試函數(shù)

Tab.5 Five classic test functions

5個經(jīng)典測試函數(shù)對應(yīng)的參數(shù)設(shè)置如表6所示。其中算法搜索范圍和變量數(shù)量參考表5，迭代次數(shù)統(tǒng)一設(shè)定200次，運行環(huán)境為Matlab2020a。

表6 4種算法參數(shù)設(shè)置

Tab.6 Parameter setting of four algorithms

在6個不同函數(shù)情況下，4種算法的尋優(yōu)曲線對比見圖2—7，其求解結(jié)果精度越高，曲線收斂速度越快，表示該算法的性能越好。

圖2為4種算法在本文機械臂時間優(yōu)化軌跡規(guī)劃過程中的優(yōu)化曲線。圖3—7為表5所對應(yīng)的測試函數(shù)優(yōu)化曲線。從圖2—7中可以看出，改進HS算法相較于其他2種HS算法，具有更優(yōu)秀的全局尋優(yōu)能力和更快的收斂速度；相較于改進GA算法，雖然改進GA算法的收斂速度更快，但是其求解結(jié)果常在最優(yōu)值附近徘徊，精度難以保證。在較大的目標(biāo)值時，如圖3和圖4所示，改進的HS算法和改進GA算法的性能明顯優(yōu)于其他2種算法。在較小的目標(biāo)值時，如圖5和圖7所示，4種算法都能較快地求解最優(yōu)值，但是改進HS算法和改進GA算法的速度更快。

圖2 式（8）—（9）的函數(shù)優(yōu)化曲線

圖3 F1函數(shù)優(yōu)化曲線

圖4 F2函數(shù)優(yōu)化曲線

圖5 F3函數(shù)優(yōu)化曲線

圖6 F4函數(shù)優(yōu)化曲線

為更好地理解實驗數(shù)據(jù)、更準(zhǔn)確地對改進HS算法和改進GA算法的性能進行對比，在保持表5和表6中參數(shù)不變的條件下，對4種算法在6個函數(shù)下，分別運行30次。對比30次結(jié)果的離散程度來判斷算法的穩(wěn)定性，結(jié)果如表7所示。其中MEAN表示30次運行最優(yōu)值的平均值，SD表示30次運行的標(biāo)準(zhǔn)差。

圖7 F5函數(shù)優(yōu)化曲線

從表7中可以看出，改進HS算法相較于改進GA算法，求解結(jié)果精度更高，且標(biāo)準(zhǔn)差更低，算法的穩(wěn)定性優(yōu)于改進GA算法。但是在維度較低的F5函數(shù)中，改進GA算法的性能明顯優(yōu)于改進HS算法的，表現(xiàn)出了更好的穩(wěn)定性和收斂性。相較于其余2種HS算法，改進HS算法的性能在6個函數(shù)中都表現(xiàn)得更優(yōu)秀，其精度值均控制在2位小數(shù)點以上，且標(biāo)準(zhǔn)差也在2位小數(shù)以上，而其余算法求解的結(jié)果離散程度較高，系統(tǒng)穩(wěn)定性較差。從總體上來看，改進HS算法收斂速度較快，算法穩(wěn)定性較高，能夠提高系統(tǒng)的魯棒性。

4.2 3-5-3多項式插值函數(shù)結(jié)果分析

表7 4種算法運行30次結(jié)果

Tab.7 Results of 4 algorithms running for 30 times

注：表中數(shù)據(jù)為MEAN±SD。

圖8 未優(yōu)化的3-5-3多項式插值的各關(guān)節(jié)速度曲線

圖9 改進HS算法優(yōu)化后的各關(guān)節(jié)位置曲線

圖10 改進HS算法優(yōu)化后的各關(guān)節(jié)速度曲線

圖11 改進HS算法優(yōu)化后的各關(guān)節(jié)加速度曲線

5 結(jié)語

本文以Func200id機器人為研究對象，在滿足機器人運動學(xué)各項約束的條件下，提出基于改進HS算法的3-5-3樣條多項式插值函數(shù)的時間優(yōu)化軌跡規(guī)劃。通過增加變異因子VF來提高HS算法的全局搜索能力，改進HS算法的搜索策略能夠在較少的迭代次數(shù)中更快地收斂，從而獲得最優(yōu)解。經(jīng)過對照試驗，改進HS算法相較于標(biāo)準(zhǔn)HS算法、IHS算法和改進GA算法具有更優(yōu)秀的求解效率，并且規(guī)劃出來的機器人各關(guān)節(jié)位置曲線、速度曲線和加速度曲線均具有連續(xù)性和平滑性的特點，能夠降低機器人的工作時間，提高機器人運行中的系統(tǒng)性能。在后續(xù)的規(guī)劃中，除了針對時間優(yōu)化的軌跡方法外，對沖擊、能量或綜合能力的優(yōu)化設(shè)計依舊是碼垛機器人軌跡規(guī)劃的重點。

[1] 胡春生, 魏紅星, 閆小鵬, 等. 碼垛機器人的研究與應(yīng)用[J]. 計算機工程與應(yīng)用, 2022, 58(2): 57-77.

HU Chun-sheng, WEI Hong-xing, YAN Xiao-peng, et al. Research and Application of Palletizing Robot[J]. Computer Engineering and Applications, 2022, 58(2): 57-77.

[2] 郭鑫鑫, 薄瑞峰, 賈竣臣, 等. 基于改進螢火蟲算法的機械臂時間最優(yōu)軌跡規(guī)劃[J]. 機械設(shè)計與研究, 2021, 37(3): 55-59.

GUO Xin-xin, BO Rui-feng, JIA Jun-chen, et al. Time Optimal Trajectory Planning of Manipulator Based on Improved Firefly Algorithm[J]. Machine Design & Research, 2021, 37(3): 55-59.

[3] YU Xiu-li, DONG Ming-shuai, YIN Wei-ming. Time- Optimal Trajectory Planning of Manipulator with Simultaneously Searching the Opti-Mal Path[J]. Computer Communications, 2022, 181: 446-453.

[4] 任重, 楊燦軍, 陳鷹. 軌跡規(guī)劃中的B樣條插值算法[J]. 機電工程, 2001, 18(5): 38-39.

REN Zhong, YANG Can-jun, CHEN Ying. B-Spline Interpolation Algorithm in Motion Planning[J]. Mechanical & Electrical Engineering Magazine, 2001, 18(5): 38-39.

[5] 徐鵬飛, 羅慶生, 韓寶玲, 等. 新型工業(yè)碼垛機器人軌跡規(guī)劃研究[J]. 組合機床與自動化加工技術(shù), 2012(5): 70-73.

XU Peng-fei, LUO Qing-sheng, HAN Bao-ling, et al.Research on Trajectory Planning of New Industrial Palletizing Robot[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2012(5): 70-73.

[6] WANG Ting, XIN Zhi-jie, MIAO Hong-bin, et al. Optimal Trajectory Planning of Grinding Robot Based on Improved Whale Optimization Algorithm[J]. Mathematical Problems in Engineering, 2020(4): 1-8.

[7] 楊星濤, 庫祥臣, 趙歡樂, 等. 基于改進遺傳算法的時間最優(yōu)軌跡規(guī)劃[J]. 制造技術(shù)與機床, 2022(3): 74-79.

YANG Xing-tao, KU Xiang-chen, ZHAO Huan-le, et al. Time-Optimal Trajectory Planning Based on Improved Genetic Algorithm[J]. Manufacturing Technology & Machine Tool, 2022(3): 74-79.

[8] 魏立新, 張鈺錕, 孫浩, 等. 基于改進蟻群和DWA算法的機器人動態(tài)路徑規(guī)劃[J]. 控制與決策, 2022, 37(9): 2211-2216.

WEI Li-xin, ZHANG Yu-kun, SUN Hao, et al. Robot Dynamic Path Planning Based on Improved Ant Colony and DWA Algorithm[J]. Control and Decision, 2022, 37(9): 2211-2216.

[9] 米根鎖, 李明. 布谷鳥搜索算法在空間機械臂軌跡規(guī)劃中的應(yīng)用研究[J]. 機械科學(xué)與技術(shù), 2018, 37(12): 1805-1810.

MI Gen-suo, LI Ming. Research on the Application of Cuckoo Search in Trajectory Planning of Space Manipulator[J]. Mechanical Science and Technology for Aerospace Engineering, 2018, 37(12): 1805-1810.

[10] 徐向榮, 秦鋒, 畢文昌. 利用樣條函數(shù)規(guī)劃機器人運動軌跡[J]. 華東冶金學(xué)院學(xué)報, 1996(3): 203-208.

XU Xiang-rong, QIN Feng, BI Wen-chang. Trajectory Planning of Robot Manipulators Using Spline Function[J]. Journal of East China Institute of Metallurgy, 1996(3): 203-208.

[11] GEEM Z W, KIM J H, LOGANATHAN G V. A New Heuristic Optimization Algorithm: Harmony Search[J]. simulation, Sage Publications Sage CA: Thousand Oaks, CA, 2001, 76(2): 60–68.

[12] 王麗萍, 吳月秋, 張驗科, 等. 改進和聲搜索算法在梯級水庫群優(yōu)化調(diào)度中的應(yīng)用[J]. 人民長江, 2021, 52(2): 192-196.

WANG Li-ping, WU Yue-qiu, ZHANG Yan-ke, et al. Improved Harmony Search Algorithm and Its Application in Optimal Operation of Cascade Reservoir Groups[J]. Yangtze River, 2021, 52(2): 192-196.

[13] 李敬花, 閆恒山, 楊博歆, 等. 改進遺傳—和聲搜索算法求解海工裝備制造車間調(diào)度問題[J]. 計算機集成制造系統(tǒng), 2022, 28(12): 3923-3936.

LI Jing-hua, YAN Heng-shan, YANG Bo-xin, et al. Improved Genetic-Harmony Search Algorithm for Solving Workshop Scheduling Problem of Marine Equipment[J]. Computer Integrated Manufacturing Systems, 2022, 28(12): 3923-3936.

[14] AKINTAYO A, SARKAR S. A Symbolic Dynamic Filtering Approach to Unsupervised Hierarchical Feature Extraction from Time-Series Data[C]// Proceedings of the American Control Conference, 2015: 5824-5829.

[15] ABDERRAHMANE M, DJURIC A, CHEN Wen, et al. Study and Validation of Singularities for a Fanuc LR Mate 200iC Robot[C]// IEEE International Conference on Electro/Information Technology, IEEE, 2014: 432-437.

Application of Improved HS Algorithm in Trajectory Planning of Palletizing Robot

CUI Ying-chao, WANG Zhi-feng, XU Jie, RENG Ming

(Shanghai Polytechnic University, Shanghai 201209, China)

The work aims to solve the problems of maximum speed constraint, short running time, and poor operation smoothness of palletizing robots when grasping target objects. With a Func200id six-axis industrial robot as the research object, its DH parameters were calculated by the relationship of each joint size of the robot, and a simulation model was established. The improved HS algorithm changed the search strategy of the algorithm by increasing the variation factor VF so that each individual in the algorithm not only had the opportunity to participate in the iterative process but also had the chance to learn from the optimal individual, which accelerated the convergence of the algorithm. Through a comparison experiment of the four algorithms running 30 times under six different test functions, the improved HS algorithm had stronger search capability and faster convergence than the remaining three algorithms. It can significantly shorten the working hours of the palletizing robot and run continuously and smoothly, which has certain application value in other industrial scenarios as well.

palletizing robot; trajectory planning; harmony search (HS) algorithm; time optimization; 3-5-3 polynomial interpolation

TP242

A

1001-3563(2023)15-0137-09

10.19554/j.cnki.1001-3563.2023.15.018

2022–08–29

崔迎超（1994—），男，碩士生，主攻基于視覺的工業(yè)機器人。

汪志鋒（1970—），男，博士，教授，主要研究方向為工業(yè)過程控制、電子與通信工程。

責(zé)任編輯：曾鈺嬋