基于離散灰狼算法的噴涂機器人路徑規(guī)劃方法

梅 偉，趙云濤，毛雪松，李維剛

（冶金自動化與檢測技術(shù)教育部工程研究中心（武漢科技大學），武漢 430081）

（?通信作者電子郵箱1739710730@qq.com）

0 引言

機器人在噴涂領(lǐng)域的應用，不僅解放了人工，而且通過提高噴涂質(zhì)量和效率極大地提高了產(chǎn)品競爭力。隨著噴涂機器人運用到更多行業(yè)，產(chǎn)品結(jié)構(gòu)變得復雜多樣，對機器人自動噴涂技術(shù)提出了更高的要求。路徑規(guī)劃作為機器人自動噴涂技術(shù)的關(guān)鍵步驟，決定了涂層的厚度和均勻性、完成噴涂工作的時間、機器人在工作空間的運動過程等。因此，研究噴涂機器人的路徑規(guī)劃方法對于提高噴涂質(zhì)量和效率、降低成本、提高安全性等具有重要意義。

對于表面結(jié)構(gòu)類型單一的物體，直接采用基于切片技術(shù)或輪廓線連續(xù)偏置的方法就能規(guī)劃出滿足要求的路徑。文獻［1］運用高斯博納定理來選擇最優(yōu)起始線和偏置線規(guī)劃噴涂路徑，從而提高了涂層均勻性和噴涂效率；文獻［2-3］則分別給出了自由曲面、平面、柱面、錐面和球面等常見類型的曲面路徑規(guī)劃方法，但對于表面結(jié)構(gòu)復雜多樣的物體，需要對每個區(qū)域進行路徑規(guī)劃，然后將區(qū)域間路徑規(guī)劃問題簡化成廣義旅行商問題（Generalized Traveling Salesman Problem，GTSP），最后運用智能算法規(guī)劃全局路徑；文獻［4-5］為了提高蟻群優(yōu)化（Ant Colony Optimization，ACO）算法求解該問題的速度和精度，將蟻群算法改進后運用到了其中的區(qū)域間路徑規(guī)劃問題；文獻［6-7］將粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法改進為離散粒子群算法，并運用到該問題，規(guī)劃了最短區(qū)域間過渡路徑；文獻［8］則考慮到多種算法可以求解該問題，分別運用遺傳算法（Genetic Algorithm，GA）、粒子群算法和蟻群算法求解了區(qū)域間路徑規(guī)劃問題，結(jié)果顯示粒子群算法求解的路徑最短。上述方法有效提高了噴涂質(zhì)量和效率，但將區(qū)域內(nèi)路徑規(guī)劃問題與區(qū)域間路徑規(guī)劃問題分開考慮，規(guī)劃的路徑仍有不足：1）路徑仍較長，效率低；2）路徑存在碰撞且不平滑；3）三維到二維的坐標映射不適用于復雜結(jié)構(gòu)實體；4）未考慮機器人能耗。本文不同于目前的研究僅考慮區(qū)域路徑連接順序，還要將每個區(qū)域內(nèi)路徑規(guī)劃的多個決策變量考慮進來以解決這些問題，因此具有顯著的多層決策特性，目前的方法都不適用。

灰狼算法是Mirjalili 等［9］在2014 年基于灰狼群體捕食行為提出的一種新的智能算法，由于其卓越的性能，在機器學習［10］、工業(yè)控制［11］等領(lǐng)域得到了較好的應用。目前將灰狼算法改進為離散域的灰狼算法的探索也有很多，文獻［12］與文獻［13］提出將離散灰狼算法運用于車輛路徑問題和旅行商問題（Traveling Salesman Problem，TSP），但兩者均屬于常規(guī)離散域問題，只能求解僅有順序類決策變量的問題，且未考慮原始算法平衡全局性能和局部性能的策略，沒有發(fā)揮灰狼算法的特性，因此不適用于多層決策GTSP。文獻［14］則采用兩段式編碼方式解決了多決策層GTSP的編碼問題，但當決策層和決策變量增多時，過長的向量難以表示序列類決策變量與其配置決策變量的對應關(guān)系，不易算子操作，而且還需要通過復雜的轉(zhuǎn)換機制將實數(shù)編碼轉(zhuǎn)換為離散值，影響算法效率。

本文重新定義編碼方式、初始化方式和種群更新策略，提出一種用于求解多層決策問題的離散灰狼算法（Discrete Grey Wolf Optimizer for Multilayer Decision Problem，MDPDGWO）。在運用該算法規(guī)劃路徑時，首先運用圖論建立簡化模型；然后，建立碰撞問題的數(shù)學模型作為約束條件，建立路徑長度的數(shù)學模型作為目標函數(shù)；最后，利用該算法求解滿足避碰約束和路徑最短目標的最優(yōu)區(qū)域間連接順序、區(qū)域內(nèi)路徑規(guī)劃切片方向、區(qū)域內(nèi)路徑連接順序和區(qū)域內(nèi)路徑起止點選擇，從而規(guī)劃路徑，且其中運用圓弧過渡提高路徑的平滑性。

1 求解多層決策問題的離散灰狼算法

1.1 基本灰狼算法

灰狼算法［9］是基于灰狼群體捕食行為提出的一種新的智能算法，灰狼種群中存在等級制度和分工制度。適應度評價最好的前三頭狼分別命名為α、β、δ，其余命名為ω。ω 狼在α、β 和δ 狼的帶領(lǐng)下搜索獵物，其狩獵過程主要為以下3 個步驟：

1）包圍。當狼群發(fā)現(xiàn)獵物時，通過式（1）包圍獵物。

其中：t 為當前迭代次數(shù)，Xp為獵物位置，|C ?Xp(t)-X(t)|為當前狼位置X(t)與獵物位置Xp的距離，A與C為系數(shù)向量，分別由式（2）與式（3）計算得來：

其中：r1、r2為［0，1］范圍內(nèi)的隨機向量，a 的每個分量隨著迭代次數(shù)的增加由2線性遞減到0。

2）捕獵。當狼群包圍獵物時，狼群根據(jù)式（4）～（7）更新位置實施捕獵行為，且由3只頭狼引導。

其中：Xα(t)、Xβ(t)、Xδ(t)為三只頭狼的當前位置；Dα、Dβ、Dδ為三只頭狼與其對應獵物的距離；X(t)為當前灰狼的位置；X(t+1)為當前狼更新后的位置。

3）攻擊。攻擊獵物完成狩獵。在算法前期，|A|＞1，狼群相對分散，進行全局搜索，找到獵物所在區(qū)域；隨著a 的每個分量遞減，|A|≤1，算法進入局部搜索階段，狼群攻擊獵物，找到最優(yōu)解。

1.2 求解多層決策GTSP的矩陣編碼方法

求解多層決策GTSP 時，每個節(jié)點具有多種配置，即節(jié)點具有隨配置決策的不同而變化的權(quán)重。因此，提出一種矩陣編碼方式，順序（序列）類型決策層和具有多種選擇的決策層仍采用整數(shù)編碼，如節(jié)點順序部分的決策層和每個節(jié)點具有多個配置選擇的決策層，而僅具有兩種選擇的決策層采用二進制編碼，最后組合成矩陣編碼。如圖1，共有6個節(jié)點，編號為1～6，第一行為節(jié)點順序決策層，節(jié)點所在的列數(shù)即為該節(jié)點的順序；第二、三行為節(jié)點多選擇決策層，共有3 種可選配置，則用1～3編碼；第四、五行為雙選擇決策層，用0和1編碼，最終編碼為如式（8）的矩陣形式。這種矩陣編碼方式與實際問題的決策映射關(guān)系簡單，每個節(jié)點與其配置決策變量對應關(guān)系很直觀，易于編解碼，也易于算法算子的計算。

圖1 矩陣編碼方法示意圖Fig.1 Schematic diagram of matrix coding method

1.3 基于先驗知識和隨機選擇的混合初始化方法

不同于多數(shù)連續(xù)域優(yōu)化問題具有太強的盲目性，求解GTSP得到的最優(yōu)解往往是一定鄰域內(nèi)的節(jié)點連接在一起，且每個節(jié)點的配置選擇也具有一定的經(jīng)驗認識。因此，考慮加入一定比例的基于先驗知識的初始解，避免算法前期盲目搜索消耗時間，也給后期局部搜索提供很多優(yōu)質(zhì)片段，當然，仍保留一定比例的隨機選擇是為了保證初始種群的多樣性，防止過早陷入局部最優(yōu)。

在利用先驗知識初始化時，非序列類決策以較大概率選擇經(jīng)驗值即可，節(jié)點序列部分的初始化可以使用k 鄰域（k 為較小的正整數(shù)）隨機選擇。如圖2，首個節(jié)點（編號為3 的節(jié)點）通過隨機選擇得到，之后每次選擇下一個節(jié)點，都通過在距離該節(jié)點（如編號為9的節(jié)點）最近的k個節(jié)點（k=3，編號為2、7、8的節(jié)點）中隨機選擇一個，直到所有節(jié)點都被選擇。

圖2 k鄰域初始化方法示意圖Fig.2 Schematic diagram of k neighborhood initialization method

1.4 種群更新策略的離散化

在連續(xù)域的灰狼算法中，算法根據(jù)式（2）～（6）求當前灰狼與三只頭狼的歐氏距離，然后根據(jù)式（7）更新當前灰狼的位置，其中參數(shù)A 和C 用于平衡算法的勘探能力和開發(fā)能力，參數(shù)A 的遞減保證前期有較強的勘探能力，后期有較強的開發(fā)能力；參數(shù)C的隨機性保證算法始終維持一定的種群多樣性。因此，本文借鑒遺傳算法中的交叉變異算子來重新定義灰狼算法的種群更新策略，同時保留原算法對勘探能力和開發(fā)能力的平衡策略。

定義如圖3 的產(chǎn)生新解的交叉算子與兩級變異算子。如圖3（a），交叉算子為使用頭狼中的優(yōu)質(zhì)片段替代當前灰狼的片段，且片段中節(jié)點的對應配置的決策變量跟隨其進行交叉，片段的起止點隨機產(chǎn)生，重復元素通過交叉片段中的對應關(guān)系消除。如圖3（b），一級變異算子為當前灰狼兩元素交換位置，且片段中節(jié)點的對應配置的決策變量跟隨其進行交換，兩元素位置隨機產(chǎn)生。如圖3（c），二級變異算子為當前灰狼除去序列決策層的決策變量更新算子，即任取幾個元素替換成取值范圍內(nèi)的其他值，如二進制部分直接取反。

圖3 種群更新算子示意圖Fig.3 Schematic diagram of population update operators

另外，定義式（9）的新解接受度θ 概念，并設(shè)定接受度閾值參數(shù)θthreshold遵循式（10）的變化規(guī)律，當新解接受度滿足θ ≥θthreshold時，接受使用產(chǎn)生的新解更新當前灰狼位置，該策略使得算法隨著迭代過程不斷降低對劣解的接受程度，平衡算法前后期的勘探能力和開發(fā)能力。

其中：r 為［0，1］范圍內(nèi)的隨機數(shù)，t 為當期迭代次數(shù)，T 為迭代總次數(shù)。

1.5 MDP-DGWO算法

本文提出的求解多層決策問題的離散灰狼算法（MDPDGWO）偽代碼如下：

算法 MDP-DGWO。

2 基于MDP-DGWO 算法的噴涂機器人全局路徑規(guī)劃方法

2.1 問題分析與建模

復雜結(jié)構(gòu)實體的噴涂路徑規(guī)劃方法關(guān)鍵步驟如圖4（a），其中區(qū)域內(nèi)路徑規(guī)劃過程涉及多次決策，如切片方向可以選擇橫向或者縱向，每個區(qū)域最終會出現(xiàn)8 種路徑結(jié)果。目前所有的方法均將區(qū)域內(nèi)路徑規(guī)劃與區(qū)域間路徑規(guī)劃獨立考慮，但實際上，區(qū)域內(nèi)路徑規(guī)劃會產(chǎn)生多種結(jié)果，其選擇的結(jié)果和區(qū)域間連接順序同樣會影響最終的路徑長度等。本文將后兩個步驟聯(lián)合考慮規(guī)劃全局路徑，將區(qū)域間連接順序、區(qū)域內(nèi)切片方向、路徑連接順序和起止點的選擇均納入決策變量，所有過渡路徑均采用圓弧過渡，并將區(qū)域間過渡路徑與實體不能產(chǎn)生碰撞作為約束，規(guī)劃最短路徑。

如圖4（b），將該問題簡化為節(jié)點具有多種配置的GTSP問題，采用圖論建立簡化模型。假設(shè)被噴涂實體有n 個區(qū)域，每個區(qū)域有m 種可選路徑配置，將每個區(qū)域定義為賦權(quán)圖G中的節(jié)點V（vertex），則每個節(jié)點具有m 種權(quán)重ωv（該區(qū)域?qū)嶋H路徑長度），將區(qū)域間過渡路徑定義為賦權(quán)圖中的邊E（edge），則每兩個節(jié)點連接的邊具有m2種權(quán)重ωe，其大小取決于兩個節(jié)點所選擇的路徑配置的起止點坐標，因此，賦權(quán)圖G=（V，E，ωv，ωe），問題簡化為求解在賦權(quán)圖G中的一條非閉合通路，使得權(quán)重之和最小，且該非閉合通路由所有節(jié)點連接順序和每個節(jié)點選擇的路徑配置表示。

圖4 路徑規(guī)劃問題示意圖Fig.4 Schematic diagram of path planning problem

2.2 路徑長度模型

為了提高噴涂過程的效率，則要求噴涂路徑的長度盡可能短，而噴涂路徑的長度主要包含n 個區(qū)域內(nèi)的路徑長度ωv和n -1條區(qū)域間過渡路徑的長度ωe，建立如下路徑長度的優(yōu)化目標函數(shù)：

2.3 路徑碰撞模型

復雜結(jié)構(gòu)實體的噴涂路徑在規(guī)劃時要考慮到區(qū)域間過渡路徑與被噴涂實體的碰撞問題，即路徑要與被噴涂實體保持一定的安全距離dsafe。本文被噴涂實體模型為三維點云數(shù)據(jù)，即一個表示該物體輪廓的點集PC，對于任一過渡路徑線段AB，其滿足不存在碰撞約束的充分條件為：對于?P ∈PC，都有點P到線段AB的最短距離d ＞dsafe。為了減少計算量，本文首先采用點云庫（Point Cloud Library，PCL）中的體素化下采樣［15］將點云數(shù)據(jù)精簡為數(shù)據(jù)量小且均勻的點集，然后對每一條過渡路徑進行碰撞檢測時先濾掉PC 中不滿足如式（12）～（14）條件的點，最后根據(jù)式（15）判斷是否碰撞。

3 實驗與結(jié)果分析

為了選擇最優(yōu)初始化比例因子r，從而充分發(fā)揮混合初始化策略對MDP-DGWO算法性能提升的作用，以及驗證用于規(guī)劃噴涂機器人全局路徑的MDP-DGWO 算法是否解決了目前的研究所未考慮到的問題，以如圖5 所示的實體曲面點云模型設(shè)計實驗。

3.1 最優(yōu)初始化比例因子選擇實驗

啟發(fā)式算法的初始解往往很大程度影響算法的速度和精度，選取最優(yōu)比例因子才能保證算法初始解的質(zhì)量。為此，本文以0.1為步長，從0.0～1.0調(diào)節(jié)算法初始化比例因子r，并在對應參數(shù)下重復20 次路徑規(guī)劃實驗，記錄并統(tǒng)計算法收斂時的路徑長度和迭代次數(shù)，得到表1 的統(tǒng)計數(shù)據(jù)，并將在各項統(tǒng)計值中表現(xiàn)較好的若干項標粗。

表1 不同比例因子下路徑規(guī)劃的結(jié)果比較Tab.1 Comparison of path planning results under different scaling factors

圖5 實體曲面點云模型Fig.5 Point cloud model of entity surface

表1 中，算法在比例因子達到一定水平（r≥0.4）時比在較低的比例因子（0≤r＜0.4）下最優(yōu)值整體表現(xiàn)更好；算法在比例因子達到一定水平（r≥0.3，除r=0.7）時比在較低的比例因子（0≤r＜0.3）下收斂需要的迭代次數(shù)更少；比例因子在為0.6、0.8、0.9 時算法整體性能表現(xiàn)最好。因此，加入一定比例的基于先驗知識的初始解后，給算法求解提供了較多的優(yōu)質(zhì)片段，避免了算法搜索時的盲目性，使得算法能夠更快求解出更優(yōu)的解，保留一定比例的隨機選擇的初始解，能夠保證初始種群的多樣性，避免陷入局部最優(yōu)。

3.2 算法對比實驗與分析

為了驗證路徑碰撞、過渡路徑較長導致效率不高，路徑不平滑等問題是否解決，設(shè)計如下實驗。分別用比例因子為0.8 的MDP-DGWO 算法、PSO 算法［6-7］、GA［8］和ACO 算法［4-5］重復20 次路徑規(guī)劃實驗，記錄并統(tǒng)計算法收斂時的路徑長度、迭代次數(shù)和路徑碰撞次數(shù)，得到表2 的數(shù)據(jù)。為了進一步分析算法表現(xiàn)出的動態(tài)性能，以及規(guī)劃的路徑實際情況，繪制如圖6 的各算法迭代過程中的路徑長度變化曲線和圖7 中各算法實際規(guī)劃出的路徑。

圖6 路徑長度變化曲線Fig.6 Change curves of path length

比較表2 中的路徑長度的最優(yōu)值數(shù)據(jù)，20 次實驗中PSO、GA 和ACO 求解得到的路徑長度波動幅度分別為0.6 m、0.48 m、0.68 m，而MDP-DGWO 求解得到的路徑長度波動幅度僅為0.4 m，且MDP-DGWO比其他三種算法的標準差都小，MDP-DGWO 更為穩(wěn)定。主要是因為啟發(fā)式優(yōu)化算法的魯棒性不僅取決于算法的種群更新策略，而且受初始解的質(zhì)量影響很大，本文除了引入新解接受度概念來平衡算法的勘探與開發(fā)能力，還提出了通過在初始解中加入基于先驗知識的解以提高初始解的質(zhì)量，從而提高了算法的魯棒性。20 次實驗中PSO、GA 和ACO 求解得到的最短路徑長度為11.63 m，而MDP-DGWO 求解得到的最短路徑長度僅為11.10 m，因此，MDP-DGWO 算法的多層決策策略考慮到了區(qū)域內(nèi)路徑規(guī)劃結(jié)果對全局路徑規(guī)劃的影響，使得規(guī)劃的全局路徑長度突破了11.63 m 的限制，使得可能達到的最短路徑減小為11.10 m。20 次實驗中PSO、GA 和ACO 求解得到的路徑長度平均值分別為11.84 m、11.90 m、12.04 m，而MDP-DGWO 求解得到的路徑長度平均值僅為11.25 m，相對于其他三種算法路徑長度分別減小了5.0%、5.5%和6.6%，長度明顯減小，證明了算法采用的多層決策策略、混合初始化策略以及新的種群更新策略明顯提高了算法的求解性能，對于提高噴涂效率具有顯著效果。比較表2 中求解迭代次數(shù)數(shù)據(jù)，MDPDGWO 算法求解過程迭代次數(shù)相對少很多，證明了混合初始化等策略加速了算法的求解過程。比較表2 中碰撞次數(shù)數(shù)據(jù)，在20 次全局路徑規(guī)劃實驗中，PSO、GA、ACO 算法超過10次實驗規(guī)劃的路徑存在碰撞，路徑不可用，而MDP-DGWO 因為建立了碰撞模型，存在碰撞的解會因為適應度較差，不會被選擇為頭狼，完全避免了碰撞的可能性。

圖7 四種算法規(guī)劃的路徑結(jié)果比較Fig.7 Comparison of path planning results of four algorithms

表2 四種算法路徑規(guī)劃結(jié)果比較Tab.2 Comparison of path planning results of four algorithms

圖6 中，MDP-DGWO 算法在初始化時已存在了與其他三種算法最終求解得到的最優(yōu)值相近的解，很明顯避免了算法初期搜索的盲目性，而且由于碰撞模型，MDP-DGWO 算法很快就將具有碰撞的路徑轉(zhuǎn)化為無碰撞路徑，其他算法則因為僅考慮路徑更短而出現(xiàn)了穿越實體模型的路徑，引起碰撞。

從圖7 的中各算法規(guī)劃的實際路徑可以看出，MDPDGWO規(guī)劃的路徑更平滑、有序且沒有碰撞，而其他三種算法規(guī)劃的路徑存在碰撞、轉(zhuǎn)彎陡峭與路徑雜亂等情況，不適用于實際情況，證明了MDP-DGWO規(guī)劃的噴涂路徑具有更強的安全性和適用性。

4 結(jié)語

本文提出一種用于解決多層決策問題的離散灰狼算法，并運用提出的算法規(guī)劃噴涂機器人全局路徑，得到如下結(jié)論：

1）對于解決GTSP的算法，在初始化時加入一定比例的基于先驗知識的初始解能夠提高算法求解精度和效率，本文提出的MDP-DGWO 算法在初始化比例因子為相對較高的水平（0.6、0.8、0.9）時能表現(xiàn)出較好的性能；

2）對于噴涂機器人路徑規(guī)劃問題，將區(qū)域內(nèi)路徑規(guī)劃與區(qū)域間路徑規(guī)劃問題聯(lián)合考慮，可以規(guī)劃出更優(yōu)的路徑，本文提出的MDP-DGWO算法相對于目前的算法，規(guī)劃出的路徑效率更高、過渡更平滑且與被噴涂實體沒有碰撞。

本文未從機器人角度深入考慮，將機器人在路徑上的能耗問題考慮在內(nèi)能夠降低成本，下一步將考慮基于機器人逆運動學建立能耗模型，并將算法改進為多目標優(yōu)化算法，用于求解能耗最優(yōu)與路徑最短的多目標優(yōu)化問題。