基于离散点的曲面喷涂路径规划研究

Research on Path Planning of Curved Surface Spraying Based on Discrete Points

摘要: 机械臂在自由曲面上的喷涂，难点在于弧度对喷涂质量的影响。现阶段，曲面喷涂仍依赖人工示教法来贴合喷枪在表面的运动，需要的人工操作较多，无法实现完全自动化。针对这一现状，提出一种针对小弧度曲面的基于离散点的喷涂路径规划研究，并结合计算机技术得以实现。将曲面沿平均法向量向地面投影，得到投影面后进行网格化离散，利用k-means聚类算法对离散点进行随机分类，获得大小近似的子片喷涂区域；利用寻路优先级在每个区域内进行回字形路径规划，生成子片喷涂路径；利用改进的蚁群算法解决子片之间的过渡路径组合规划问题，得到子片喷涂顺序；实验结果表明，该方法能够生成所有子片内部及子片之间的喷涂路径，在效率和精度上具有一定优势，并且实现完全自动化。

Abstract: The difficulty of spraying robot arm on free surface is the influence of radian on spraying quality. At this stage, curved surface spraying still relies on manual teaching method to fit the movement of the spray gun on the surface, which requires more manual operations and cannot be fully automated. In view of this situation, a research on spray path planning based on discrete points for small radian surfaces is proposed and realized with computer technology. The surface is projected to the ground along the average normal vector, and then the projection surface is grid discretized. The k-means clustering algorithm is used to randomly classify the discrete points to obtain the sub patch spray-ing area of similar size. Using the priority of path finding, the zigzag path planning is carried out in each region to generate the sub chip spraying path. The improved ant colony algorithm is used to solve the combination planning problem of transition paths between sub patches, and the spraying sequence of sub patches is obtained. The experimental results show that this method can generate the spraying paths within and between all sub slices, and has certain advantages in efficiency and accuracy, and can achieve complete automation.

1. 引言

机械臂作为现代工业流水线中的重要一环，承担着多种加工任务，对表面的喷涂就是机械臂的重要功能之一 [1]。其中，自由曲面上的喷涂由于其表面的不规则性，导致其加工难度大 [2]，若采用传统的平面喷涂方法，必然会导致涂层的不均匀甚至不完全覆盖 [3]，而人工示教法 [4] 在操作上具有较高的复杂度 [5]，且自动化程度低。目前，相关领域多采用分片处理、逐片加工 [6] [7] [8] 的方法改善这一状况，同时运用智能算法进行自动寻路，规划出机械臂喷枪的喷涂路径。但目前的研究大多只停留在理论，没有结合计算机技术进行系统地运行、验证，也没有进行相关改良，无法使算法发挥更大作用。

在工作时，当喷枪在一个子片喷涂完成后需要转移到下一个子片，此过程中经过的路径称为过渡路径。为节省工作时间，过渡路径的选取应遵循最短原则且经过的位置不重复，求解该问题的大多数做法是转化为旅行商问题 [9] (TSP)，再利用蚁群算法搜索出一条最短路径 [10]，沿此路径可得到子片的喷涂顺序。蚁群算法由意大利学者Dorigo M. [11] 提出，它包括自适应与种群协作两个部分 [12]。蚁群算法虽能较好地解决TSP问题，但传统蚁群算法存在着一些不足，如收敛速度较慢 [13]、易陷入局部最小等，因此众多学者对该算法做出了改进。Gambardella [14] 等人提出的改进策略可以缩短搜索时间，调整蚂蚁的转移概率，避免陷入局部最小。张川 [15] 提出蚁群–蜂群分层递阶方法，先用蚁群算法给出较优的初始路径，再用蜂群算法对这一路径加以改进，在保证求解精度的前提下加快了算法的收敛速度。王沛栋，冯祖洪 [16] 等人基于栅格法提出一种蚁群改进策略，使蚁群进行折返式迭代，加大蚂蚁的利用率。卜新苹，苏虎 [17] 等人将MMAS和ACS算法融合，提出从路径选择与信息素更新方面进行优化的蚁群算法改进策略。杨北辰，余粟 [18] 提出一种归档更新策略和路径补偿机制，降低信息素对最优解的干扰，解决不可行路径的修正问题。赵天亮，张小俊 [19] 等人提出将A*算法的搜索策略融入蚁群算法，加入选择概率因子和信息素调节机制，提高了算法的性能。王原，陈名 [20] 等人在组合优化问题上提出用蚁群算法与深度学习法进行混合求解，并证实了该方法在解决旅行商问题时的效能。

本文针对机器人喷枪在自由曲面上的喷涂问题，根据分片处理的思想，提出一种新的路径规划方法。首先，在Matlab中构造一块点阵作为喷涂区域，使用k-means聚类算法对离散点进行随机划分，得到大小相近的区域，完成喷涂区域分片规划；其次，利用寻路优先级对每个子喷涂区域内部进行路径规划，得到子片的喷涂路径；最后，针对每个子片之间的过渡路径的组合问题，利用改进的蚁群算法及改进的TSP规则，求出最短的过渡路径。最终将子片路径与过渡路径整合，得到完整喷涂路径。

2. 喷涂区域分片规划

在路径规划之前，需要获得可用的喷涂区域。如图1所示，将待喷涂表面沿平均法向量向XOY平面进行投影，得到投影面，可采用矩形或三角网格等形式将图形离散化。本研究针对小弧度曲面，为简化规划操作，忽略弧度对离散点分布的影响。本文根据矩形网格的特征，利用Matlab编程，构造出两块矩形点阵并使之交错，形成一块均匀点阵，并以此作为规划场所，网格与离散点如图2、图3所示。

Figure 1. Surface and projection

图1. 曲面与投影

Figure 2. Rectangular grid

图2. 矩形网格

Figure 3. Uniform discrete points

图3. 均匀离散点

鉴于快速划分的目的，采用k-means聚类算法来自动随机生成各个子片喷涂区域。该算法通过输入k个点作为初始聚类中心，将每个点划分到距离最近的聚类中心，对坐标求取均值来获取新的聚类中心，经过反复迭代，形成各个大小相似的子片喷涂区域。其中，输入的k值若过大将造成运算时间较长，过小则会导致划分的区域数量少，进而导致每个区域的面积过大，无法达到改善曲面喷涂质量的目的。此处采用ISODATA算法对所取的k值做验证，确认合适的k值并输入，子片喷涂区域形成过程如图4所示。

(a) (b) (c) (d)

Figure 4. Running process of clustering algorithm

图4. 聚类算法运行过程

由图可知，由于随机产生的初始点分布不均，导致刚开始划分时的区域大小差距明显，在后面的迭代中差距逐渐缩小，最终各区域大小趋于近似，实现喷涂区域分片规划。

3. 子片内部路径规划

3.1. 寻路优先级的定义

如图5所示，设位于第三象限的A点为喷涂路径的出发点，喷枪移动采取逆时针回旋，B为喷涂路径的终点。红色圆圈为区域离散点的聚类中心，以这个点为交点作正交直线，划分出I、II、III、IV四个象限，每个象限都设置9个方向作为当前可供选择的点的所在方向，即每次选择下一路径点都有9个点可供选择。为这9个方向设定优先级，如图中的第三象限所示，选择下一路径点的优先级为1~9，数字越小，算法就越优先考虑这条路径，图中1号线条(红)代表最优先考虑的路径，逆时针方向上路径的优先程度依次降低。

Figure 5. Priority of pathfinding

图5. 寻路优先级

3.2. 子片路径规划原理

将最外圈的某一点设置为起始点，建立禁忌表以记录到达过的点。当开始寻路后，算法会按照优先级进行逐个排除，依据当前禁忌表及区域内离散点集合，由外向内对路径点进行判断，将选定的路径点加入禁忌表，这个点在之后的寻路中将不参与搜索。在区域内所有点都加入禁忌表后，该区域规划结束。考虑到某些点位置的特殊性，算法给位于坐标轴上的离散点也建立了优先级，同时在最后加入区域内离散点的整体遍历，找出遗漏的点加入相应路径表。回字形规划程序框图如图6所示。

Figure 6. Program block diagram of planning with surround shape

图6. 回字形规划程序框图

根据上述规划流程，利用Matlab进行仿真，获得的子片路径结果如图7所示。

Figure 7. Path in sub slices

图7. 子片路径

由图可知，上述规划步骤在所有子片内部都实现了近似的回字形路径，表明该算法可达到要求。但从每个子片的结果来看，部分子片路径的转折次数较多，不利于机械臂运动，可考虑增加可选路径的数量，但整体地增加会使算法长度大大加长，导致运算耗时明显延长。因此可设置阈值φ，记录每条子片路径的转折次数，当转折次数超过阈值时，增加该区域规划时的寻路优先级数量，如此可减少该区域路径的转折次数。

4. 子片间的过渡路径组合规划

喷枪在子片间需要进行过渡，求解此过程中的全局最短过渡路径，可看作子片路径的组合问题，本文将其转化为TSP问题并用改进的蚁群算法来解决，在此主要做两点工作：一是针对基本蚁群算法存在的缺陷，进行影响因素优化、路径选取及信息素更新优化、寻优效率优化；二是针对子片之间的过渡路径组合规划问题，对传统TSP的形式加以变动，并利用改进的蚁群算法准确地解决路径组合问题。

4.1. 基本蚁群算法与影响因素优化

信息素在蚁群算法中起到关键作用，初始时刻任意两城市间的信息素设为：

${\tau }_{i,j}\left(0\right)=c$ (1)

c为常数。

假设在t + n时刻某只蚂蚁完成一次周游并经过了城市i和j，则在t + n时刻城市i, j之间的信息素含量可以表示为：

${\tau }_{i,j}\left(t+n\right)=\left(1-\rho \right)\cdot {\tau }_{i,j}\left(t\right)+\Delta {\tau }_{i,j}^{\min }$ (2)

其中，ρ表示挥发系数，用于减小前代蚂蚁留下的信息素的影响。 $\Delta {\tau }_{i,j}$ 表示某只蚂蚁在此次周游中于城市i和j之间留下的信息素，当本代蚂蚁周游结束，其累计计算式为：

$\Delta {\tau }_{i,j}={\displaystyle \underset{k=1}{\overset{m}{\sum }}\Delta {\tau }_{i,j}^k}$ (3)

k为蚂蚁序号，m为蚂蚁总数。关于 $\Delta {\tau }_{i,j}^k$ 计算，可由常数Q除以距离得到。此处的计算式，采用的是以全局信息来更新信息素的ant-cycle模型。

$\Delta {\tau }_{i,j}^k=\{\begin{array}{ll}\frac{Q}{L_k}\left(k=1,2,3,\mathrm{...},m\right),\hfill & 当经过i,j时\hfill \\ 0,\hfill & 其他\hfill \end{array}$ (4)

其中L_k为本只蚂蚁的周游距离。

在进行下一城市的选择时，t时刻蚂蚁k从城市i转移到城市j的概率可由以下公式得到：

$p_{i,j}^k\left(t\right)=\{\begin{array}{ll}\frac{{\left[{\tau }_{i,j}\left(t\right)\right]}^{\alpha }\cdot {\left[{\eta }_{i,j}\left(t\right)\right]}^{\beta }}{\sum {\left[{\tau }_{i,s}\left(t\right)\right]}^{\alpha }\cdot {\left[{\eta }_{i,s}\left(t\right)\right]}^{\beta }},\hfill & j\in J_k\left(i\right)\hfill \\ 0,\hfill & 其他\hfill \end{array}$ (5)

其中 ${\eta }_{i,j}$ 代表蚂蚁k由城市i转移到城市j的期望程度，与距离成反比，它通常计算为：

${\eta }_{i,j}=\frac{1}{d_{i,j}}$ (6)

$J_k\left(i\right)$ 表示在城市i处蚂蚁k可选择的未拜访城市集合。α、β分别为信息启发式因子和期望启发式因子。

蚁群算法寻优过程受α，β，ρ，m，G，Q六个因素影响，其中α和β影响转移概率的大小，进而影响路径的选择，通常选取1~5；ρ决定信息素保留程度，取值在0~1之间；常数Q影响信息素更新程度，在[10, 10000]区间内取值；蚂蚁数量m与最大迭代次数G都是寻优精度的保证，而二者数值过大会造成无为的冗余迭代，增加非必要运算时间；鉴于以上因素的存在，并确定因素间无交互，进行六因素五水平正交试验与极差分析，根据正交试验表L₂₅(56)设计试验方案，由于数据众多，此处不作展示。

根据试验求得的最短路径，计算各因素各水平的总和、均值以及均值的极差。由试验得到的最优组合为：α = 2；β = 5；ρ = 0.3；m = 40；G =50；Q = 6 × 10³。

4.2. 路径选取及信息素更新改良

在式(5)中，算法计算出了蚂蚁k转移到剩余城市的概率，在基本算法中通常选择概率最大的城市，这样一来其他城市几乎被排除。这样的选取规则将导致寻优范围狭隘，易陷入局部最优。为了提高找到最优解的可能性，在此规则上进行改良，将概率最大的选取方式改为采用轮盘赌注法则。具体实现方法为：根据转移概率产生各区间，在区间的交界处计算累积概率，程序中生成0到1之间的的随机数，随机数落到哪个区间则位于哪个区间的城市就被选取，如图8所示。

Figure 8. Schematic diagram of section

图8. 区间示意图

另外在试验中发现，受限于运算法则，期望程度η对概率的影响p通常更大。在基本算法每次迭代的结尾，算法将对本代所有蚂蚁周游的路径进行信息素更新，此处改为只对每代的最短路径进行信息素更新，此举的目的在于突出信息素τ的影响，避免在计算p时受η影响过大而陷入局部最优，即：

${\tau }_{i,j}\left(t+n\right)=\left(1-\rho \right)\cdot {\tau }_{i,j}\left(t\right)+\Delta {\tau }_{i,j}^{\min }$ (7)

$\Delta {\tau }_{i,j}^{\min }=\frac{Q}{\min \left(L_k\right)}\left(k=1,2,3,\cdots ,m\right)$ (8)

4.3. 寻优效率优化

蚁群算法依赖于集体功能，在求解精度上较可靠，但运算速度较慢，而遗传算法的运算效率则优于前者。针对两种算法的各自特点，提出一种改进方案，将遗传算法与蚁群算法进行混合，克服各自缺陷，优势互补，运算效率上优于蚁群算法，求解精度上优于遗传算法，产生一种兼顾效率与精度的全局启发式算法。混合算法程序框图如图9所示。

Figure 9. Block diagram of hybrid algorithm

图9. 混合算法程序框图

由图可知，将遗传算法应用到寻路问题的步骤可设计为：将各城市编号随机地组成无重复数字的编码作为个体，将路径距离作为个体适应值，设置种群数量和期望适应值，计算种群平均适应值，判断该种群的适应值是否达到期望值，若达不到则对编码进行一系列“进化”操作，产生新一代种群后重复上述步骤，直到获得符合条件的种群为止，最后在该种群所有个体所代表的路径上加入一定程度的信息素，从而加快蚁群算法寻优的效率。

4.4. 对比试验

为检验4.2与4.3中的改进措施是否有效，输入五组数据，参数采用4.1中正交试验获得的最优组合，基本蚁群算法的某次试验的路径显示如图10所示(横竖轴为位置坐标轴，刻度单位为mm)，记录基本蚁群算法、改良的蚁群算法、混合算法的求解结果，制成折线图如图11所示。并统计基本蚁群算法与混合算法后半程的迭代次数，结果如表1所示，其中一组的迭代曲线如图12、图13所示。

Figure 10. Image of path display

图10. 路径显示图像

Figure 11. Line graph of solution result

图11. 求解结果折线图

Figure 12. Iteration curve of basic algorithm

图12. 基本算法迭代曲线

Figure 13. Second half iteration curve of hybrid algorithm

图13. 混合算法后半程迭代曲线

Table 1. Iterations

表1. 迭代次数

由上述结果可知，经改良后的算法在求解精度上有了明显提高，在此基础上的混合算法在收敛速度上又有了提升，证明上述改进的蚁群算法有效改善了算法的求解精度与收敛速度。

4.5. 路径组合原理及对比试验

在一个区域喷涂完毕后，喷枪需要过渡到下个区域，此过程中经过的路径称为过渡路径，求解最短过渡路径的问题，实际上是过渡路径的组合问题，目的是找到最佳的子片喷涂顺序。将该问题视为TSP来解决，而传统的TSP模式只能将相互独立的点作为输入，例如各区域中心点，而将中心点间的距离作为寻找最短过渡路径的依据并不准确，因而需要对传统TSP的形式加以改动。

在子片内部规划结束后，会得到每个子片路径的两个端点。路径组合问题，需要将被连接的两区域端点间的距离考虑在内，而子片路径的长度已规划好为固定值，所以子片路径不在搜索范围内，此处只考虑过渡路径的长度。如图14所示，共有四个子片路径e₁、e₂、e₃、e₄，每个子片路径有两个端点A₁B₁、A₂B₂、A₃B₃、A₄B₄，子片路径之间的连接方式有四种，即四种过渡路径，分别是A_iB_j，A_iA_j，B_iA_j，B_iB_j，其中 $i=\text{1},\text{2},\cdots ,n$ ； $j=\text{1},\text{2},\cdots ,n$，n = 4 (由子片个数确定)，图上虚线为其中一种过渡路径。将每条子片路径的两端点绑定，当一条子片路径的某端点确定为起点后，另一点则确定为终点，采用改进的算法在终点与其他子片路径的端点之间展开搜索，所连接到的下一条子片路径的端点作为该子片路径的起点，再重复之前的步骤。经过反复迭代、更替，算法最终会找到全局最优的组合方式，即最短过渡路径。

Figure 14. Schematic diagram of connection between pathinsub slices

图14. 子片路径连接示意图

为检验上述路径组合方案是否有效，输入相同数据，显示各端点及它们之间的过渡路径，并计算路径总长，采用传统TSP模式与采用优化方案的过渡路径如图15、图16所示(横竖轴为位置坐标轴，刻度单位为mm)。

由图可知，经路径组合优化后，端点之间的组合方式更加多样，这表明喷涂方向也不仅限于指定的起点至终点，而是根据优化目标进行调整。设置五组数据，分别用两种方案求解区域间最短过渡路径长度，试验结果如表2所示。

由结果可知，经路径组合优化后，算法所得最短过渡路径长度明显缩短，证明该方案在求解该问题上比传统TSP模式更加准确。

Figure 15. Transition path in traditional TSP mode

图15. 传统TSP模式下的过渡路径

Figure 16. Transition path in optimization scheme

图16. 优化方案下的过渡路径

Table 2. Result of test

表2. 试验结果

5. 仿真试验研究

(a) (b)

Figure 17. Path in rectangular projection plane

图17. 矩形投影面下的路径

(a) (b)

Figure 18. Path in wing like projection plane

图18. 机翼状投影面下的路径

(a) (b)

Figure 19. Path in hull like projection plane

图19. 船体状投影面下的路径

将所有子片路径与过渡路径同时显示，产生完整路径。经传统TSP模式处理后与路径组合优化处理后的总路径如图17(a)和图17(b)所示(横竖轴为位置坐标轴，刻度单位为mm，下图同上)。为检验算法适用性，增加两种不同轮廓的规划场所，经两种处理后的总路径如图18(a)和图18(b)、图19(a)和图19(b)所示。

由图可知，试验在每个规划场所都生成了包含子片路径和过渡路径的完整喷涂路径，子片路径遍历了所有离散点，未发现遗漏，且优化后的过渡路径可看出其总体长度的缩短，表明本文提出的规划方法可以实现预定的目标，且具有一定的广泛适用性。

6. 结论

本文依据分片处理的思想，提出了一种基于离散点的曲面喷涂路径规划方法。以离散点为场所，利用k-means聚类算法进行区域划分，实现自动分片，得到大小近似的子片喷涂区域。采取划分象限与设置寻路优先级的方式，通过程序实现所有喷涂区域的自动路径生成，且无遗漏的离散点。针对蚁群算法的各影响因素进行正交试验，得到最优参数组合；对算法部分规则加以改进，改善单一的选取模式，并突出信息素的作用，避免了局部最优，提高了求解精度；再结合遗传算法与前者的特点进行算法混合，又提高了收敛速度。针对过渡路径的组合问题，对算法的输入类型与搜索范围进行变动，使TSP解决模式能更好地适配该问题。将两种路径整合为完整路径：为检验算法适用性，在不同轮廓的场所下进行试验，均得到理想效果，并展现了在路径组合问题上的优化成果。

基金项目

辽宁省教育厅科学研究项目(J2020107)。

NOTES

^*第一作者。

^#通讯作者。