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

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

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

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

0 引言

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

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

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

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

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

1.1 基本灰狼算法

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

1）包圍。當狼群發現獵物時，通過式（1）包圍獵物。

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

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

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

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

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

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

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

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

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

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

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

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

1.4 種群更新策略的離散化

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

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

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

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

其中：r 為［0，1］范圍內的隨機數，t 為當期迭代次數，T 為迭代總次數。

1.5 MDP-DGWO算法

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

算法 MDP-DGWO。

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

2.1 問題分析與建模

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

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

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

2.2 路徑長度模型

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

2.3 路徑碰撞模型

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

3 實驗與結果分析

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

3.1 最優初始化比例因子選擇實驗

啟發式算法的初始解往往很大程度影響算法的速度和精度，選取最優比例因子才能保證算法初始解的質量。為此，本文以0.1為步長，從0.0～1.0調節算法初始化比例因子r，并在對應參數下重復20 次路徑規劃實驗，記錄并統計算法收斂時的路徑長度和迭代次數，得到表1 的統計數據，并將在各項統計值中表現較好的若干項標粗。

表1 不同比例因子下路徑規劃的結果比較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）下最優值整體表現更好；算法在比例因子達到一定水平（r≥0.3，除r=0.7）時比在較低的比例因子（0≤r＜0.3）下收斂需要的迭代次數更少；比例因子在為0.6、0.8、0.9 時算法整體性能表現最好。因此，加入一定比例的基于先驗知識的初始解后，給算法求解提供了較多的優質片段，避免了算法搜索時的盲目性，使得算法能夠更快求解出更優的解，保留一定比例的隨機選擇的初始解，能夠保證初始種群的多樣性，避免陷入局部最優。

3.2 算法對比實驗與分析

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

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

比較表2 中的路徑長度的最優值數據，20 次實驗中PSO、GA 和ACO 求解得到的路徑長度波動幅度分別為0.6 m、0.48 m、0.68 m，而MDP-DGWO 求解得到的路徑長度波動幅度僅為0.4 m，且MDP-DGWO比其他三種算法的標準差都小，MDP-DGWO 更為穩定。主要是因為啟發式優化算法的魯棒性不僅取決于算法的種群更新策略，而且受初始解的質量影響很大，本文除了引入新解接受度概念來平衡算法的勘探與開發能力，還提出了通過在初始解中加入基于先驗知識的解以提高初始解的質量，從而提高了算法的魯棒性。20 次實驗中PSO、GA 和ACO 求解得到的最短路徑長度為11.63 m，而MDP-DGWO 求解得到的最短路徑長度僅為11.10 m，因此，MDP-DGWO 算法的多層決策策略考慮到了區域內路徑規劃結果對全局路徑規劃的影響，使得規劃的全局路徑長度突破了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 中求解迭代次數數據，MDPDGWO 算法求解過程迭代次數相對少很多，證明了混合初始化等策略加速了算法的求解過程。比較表2 中碰撞次數數據，在20 次全局路徑規劃實驗中，PSO、GA、ACO 算法超過10次實驗規劃的路徑存在碰撞，路徑不可用，而MDP-DGWO 因為建立了碰撞模型，存在碰撞的解會因為適應度較差，不會被選擇為頭狼，完全避免了碰撞的可能性。

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

表2 四種算法路徑規劃結果比較Tab.2 Comparison of path planning results of four algorithms

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

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

4 結語

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

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

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

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