智能路径规划算法在鞋底点胶领域的应用研究

郭超 王勇 王瑛

（广东工业大学 广东省广州市 510006）

1 引言

鞋底点胶一直是制鞋业生产的重要工序，点胶的质量好坏直接影响鞋子的质量，传统的制鞋业生产需要进行大量的人工点胶工序，不仅费时费力，成本也居高不下，而且鞋底点胶所用的胶散发出的气味严重影响点胶工人的身体健康。近年来，随着机器人领域的发展，为制鞋业带来了自动化大量生产的机会，目前机器人技术正越来越多地被应用于制鞋行业中，鞋底点胶作为制鞋工艺中的关键工序，工厂实现大规模自动化操作能够大大地提高生产效率及其产品质量，并能改善员工的工作环境。越来越多的路径规划算法被应用在鞋底点胶工业生产中，为制鞋业自动化生产提供了发展的契机，但是随着人们对于鞋的需求量与鞋品种类的日益增多，传统的路径规划算法以及越来越暴露出其弊端，如容易陷入局部最优，规划时间过长等缺陷。

随着时代的进步，人工智能技术发展越来越成熟，被应用在了各个领域，均取得了较好的成果，而在路径规划整体优化的领域，也涌现了许多优秀的处理模型，均表现出了许多优秀的性能，例如MIP 利用混合整数规划的方法建模，再利用求解器求解，得到最优解。SOM 自组织映射神经网络模型竞争学习调整邻域函数的形式获得最优解。基于强化学习的求解组合优化模型RL，应用了强化学习和一个叫structure2vec 的图嵌入（graph embedding）方法，提出了解决这一类问题的一种“元算法”。在本文中，我们将从传统的点胶机控制点胶、传统路径规划算法与建模求解的方向进行比较概述，并在结尾处讨论应用建模方法解决点胶效率问题的未来可能的发展方向。

2 鞋底点胶控制概述

2.1 鞋底点胶封装定义

鞋底点胶封装是一个典型的二维点滴喷射系统，点胶头相对于待加工元件或基板需要做大量的往返运动，通过完成点胶过程固定电子元件，材料等操作的过程。点胶头运动的控制属于组合优化问题的一个典型代表，如何合理的规划点胶头的运动路径直接影响生产的效率。

2.2 鞋底点胶控制系统的工作流程

鞋底点胶机所使用的点胶控制系统基本流程如图1 所示，点胶过程通常是先由单目或双目摄像头识别待点胶产品并进行点云扫描建模，控制系统接收点云数据建立二维点胶地图，算法规划点胶路径，输出机械手点胶头移动控制地图并进行点胶作业。

2.3 鞋底点胶效率评价标准

点胶路径规划问题是组合优化问题的一个典型代表，可能出现的点胶路径数目与待加工点数目呈指数型增长关系，因此，衡量一个点胶路径规划算法效率的评价标准就是判断点胶规划所需的时间T 与点胶规划的路径L，一个优秀的点胶路径规划算法求解应能在较短的时间T 内规划出能遍历点胶地图上所有的点且每个点只访问一次的较短的路径L 长度。

3 传统鞋底点胶手段

3.1 手动或半自动点胶控制

传统的点胶方法有人工手动点胶，不仅效率低，而且还会导致产品质量问题以及工作环境恶劣导致的工人身体健康问题。直到左力等发明了一种鞋大底自动点胶机，推动了半自动化鞋底点胶的进展，但是依然缺乏自动化点胶的点胶路径指引，无法真正实现自动化，KWON 等提出了一种基于鞋底轮廓生成喷胶轨迹的办法，解决了鞋底边缘点胶的问题，但是随着鞋品种类的发展，鞋底功能性的发展，点胶不再局限于鞋底边缘，因此该方法无法针对个性化制鞋的复杂点胶产生效果，KIM 提出了一种基于鞋底三视图和鞋帮的三维扫描数据自动提取喷胶轨迹的方法，然而该三维扫描技术成本较高，且操作复杂，规划效率低，无法控制精度。

4 传统路径规划算法控制点胶

4.1 蚁群算法控制系统

蚁群算法是一种模拟蚂蚁觅食行为的模拟优化算法，其基本原理是每一个蚂蚁在走过的路径上释放信息素，遇见未知路口则随机选择并释放与路径长度有关的信息素，信息素浓度与路径长度成反比，后面的蚂蚁再次碰到该路口则会优先选择信息素浓度较高的路径，如此迭代会存在最优路径上的信息素浓度越来越大，从而形成最优路径。其中，每一只蚂蚁选择目标点的概率取决于目标点之间的距离和当前连接支路所含的信息素余量有关，设置禁忌表控制蚂蚁遍历所有目标点以实现非重复遍历。

如果把鞋底点胶任务抽象为二维旅行商问题，则有如下的问题模型： 给出待点胶点组合V=v1,v2,v3,…,vn。代表点vi 与vj 的欧式距离，M 代表该组合问题的解集，则必然存在一个最优解M*，使得：

蚁群算法模型经过多次的文献优化改进，国内外对离散问题的蚁群改进算法成果很多，其中在点胶领域以该领域点胶规模不确定等情况多使用自适应蚁群优化算法，自适应蚁群优化算法其最基本的改进方法是对蚁群模型的关键因素进行自适应调整，主要包括对：对蚁群算法状态转移概率，信息素挥发因子，信息量等自适应调整。

智能点胶领域相关文献采用蚁群优化系统解决的点胶效率优化问题采用协调的α 与β 做控制信息素与可见度的参数应用，降低算法因参数不当而导致的过度随机性从而复杂度过高与较快收敛导致的陷入局部最优的情况，并且为提高点胶规划路径的效率，避免因点胶问题规模过大导致的算法复杂度过大，使得算法规划效率过低，采用根据问题规模设定最大迭代次数，路径解长度质量满足条件范围，或者设定的最大规划时间。

图1：点胶控制系统基本流程

4.2 蚁群，粒子群算法控制系统

蚁群算法在解决大规模的点胶问题也暴露出了许多缺点，并且要解决这些问题需要不断的对参数进行改进，而蚁群算法参数过多，优化比较困难，基于该问题，有学者提出使用蚁群与粒子群融合的解决方法。使用粒子群算法的全局搜索能力强，收敛速度快的特点，拟合蚁群算法的搜索能力差，难收敛，易陷入局部最优的缺陷，同时，以蚁群算法的较强的局部搜索能力以及信息反馈能力弥补粒子群算法的局部搜索能力的缺陷，互相采取优势，构建出了ACO-PSO 算法模型，即首先以蚁群算法的一次遍历探索的候选解做初始最优解，再通过粒子群算法进行局部搜索更新，提高收敛速度，后期利用蚁群算法的信息素对搜索方向的影响避免粒子群算法搜索收敛速度慢的缺陷，既提高了算法高效性，又增加了寻找全局最优解的能力。

在研究的最后该方法也对比了TSP 标准数据库TSPLIB 中的Hopfield10、Eil51、Berlin52、rat99 四种实例进行测试。对于同一个TSP 问题分别对粒子群，蚁群，ACO-PSO 算法单独运行，最后无论是平均路径、最优路径长度，误差率等均有长足的改进。

5 神经网络模型算法控制点胶

5.1 人工神经网络模型

人工神经网络(Artificial Neural Network, 简称ANN)，又称神经网络（Neural Network，简称NN），是启发于应用类似于大脑神经突触联接的结构进行信息处理的数学模型，它的构筑理念是受到生物神经网络功能的运作启发而产生的，试图模拟大脑神经网络处理、记忆信息的方式进行信息处理，与其余基础优化算法相比，主要有三大优势：具有自学习能力，反馈网络具有联想存储功能，高速寻优化解的能力。神经网络最早应用于TSP 组合优化的模型是1985年Hopfield 和Tank 的Hopfield 神经网络模型，其主要改进就是使用能量函数替代TSP 问题中的目标函数, 通过能量函数确定神经元之间的相互连接权限, 随着网络状态的逐渐变化, 当能量达到平衡时, 就可以得到局部最优解。

5.2 Hopfiled神经网络的点胶路径轨迹优化

Hopfiled 神经网络是一种递归神经网络，结合存储系统和二元系统的神经网络。它保证了向局部极小的收敛，但收敛到错误的局部极小值(local minimum)，而非全局极小(global minimum)的情况也可能发生。

用Hopfiled 求解TSP 问题的基本思路是：设待点胶任务地图存在N 个点胶点，建立一个拥有N2 个神经元、带反馈的神经网络，首先给网络设置一组初始权值，然后经过多次迭代计算，改变网络能量和神经元状态。当网络能量不再降低时, 神经元的输出矩阵即为问题的解。求解点胶问题的Hopfiled 神经网络为了精确性一般采用连续型而不是离散型，则其神经元阈值函数可以设置为双曲正切函数，一般形式为：

其中xi 代表第i 个点胶点，且x 与i 均满足区间[1,N]，解矩阵约束条件为：每行有且仅有一个点胶点被访问即标记为1，每列有且仅有一个点胶点被访问标记为1，分别保证每个点都被访问，且仅被访问一次。

判断解的合法性除了满足上述的约束，还要满足在一定的迭代次数的范围内完成路径的寻找，但是实验发现如果没有选用合适的模型参数组合很容易导致Hopfiled 容易出现局部最优的情况，而且求解较为不稳定，在最大迭代次数内无法完成。因此，对Hopfiled神经网络模型的应用应针对求解问题的特点进行参数的尝试，才能更好的发挥模型的规划能力得到较为满意的结果。

5.3 SOM神经网络的点胶路径轨迹优化

SOM（Self-Organizing Maps，SOM）神经网络模型是由Teuvo Kohonen 教授于1998年提出，是一种无监督学习的聚类方法，受人类大脑神经元的自组织和侧抑制现象启发。不同外部刺激引起大脑皮层各个区域的反应是不同的，因此该模型以一种低维的方式来反应高维问题，生物神经元之间存在侧抑制现象，临近的神经元相互激励，较远的神经元相互抑制。响应最强的神经元即获胜神经元，以它为中心，会形成一个区域，距离中心越远激励越弱，这个区域就是“优胜邻域”，而SOM 神经网络针对组合优化的TSP 问题的求解重点就是对邻域函数的修改，通常求解此类二维点胶问题是通过以鞋底边缘为边界把神经元排列成类圆形，通过竞争学习策略使得每个点只与其前后神经元进行进行调整，同时通过学习率α 控制收敛，学习率曲线应该是一个递减的曲线，其基本形式应该是：

这里α 是随学习时间变化的特定时间的学习速率，g 是以获胜神经元为中心、具有领域分散h 的高斯函数。衰减函数中分别乘以两个给定的值γ，分别代表学习速率和邻近距离。

以上述方法，通过把鞋底点胶任务扫描转化成二维点胶地图任务，即2D的TSP问题，利用SOM神经网络模型，通过竞争学习策略，从任意一点开始按照获胜神经元出现的顺序把获胜神经元与点胶点相连，以此就构建出一个全局最优路径。

6 神经网络模型的挑战与点胶应用的展望

在神经网络模型日益发展多样化的今天，诞生了许许多多优秀的模型，也推动了不同领域对神经网络方法的探索与应用，特别是在模式识别，智能控制领域都有非常吸引人的应用前景。以其具有独特的高度复杂的非线性动力学习系统而被广泛应用，但是其最大的特点在于具有大规模并行、分布式存储和处理、自组织、自适应和自学能力，特别适合处理需要同时考虑许多因素和条件的、不精确和模糊的信息处理问题。尽管当今神经网络技术获得了飞速的发展，在组合优化问题领域有着比较卓越的效果，但是仍然面临一系列的挑战，如黑盒性，开发难度，训练数据量需求大，计算代价高昂等缺陷。接下来，针对工业鞋底点胶生产的应用背景，我们讨论一些可能的发展方向。

6.1 无监督学习或半监督学习

无监督学习是当一个应用缺乏足够的先验知识，难以人工标注类别或进行人工类别标注的成本太高，而让模型能根据类别未知(没有被标记)的训练样本解决模式识别中的各种问题，半监督学习则是使用大量的未标记数据，以及同时使用标记数据，来进行模式识别工作。鞋底点胶领域以其大量存在各式各样的鞋底型号的无标签数据，而导致人工标注类别训练模型变得极为困难，而且由于不同品种，不同生产线的生产任务不同，鞋底模型也大相径庭，逐一标注训练非常耗费人工成本，不具有普适性。因此，无监督或半监督学习将会是日后点胶应用领域的重点研究方向。

6.2 通用性

构建通用型神经网络模型解决鞋底点胶组合优化问题能大大节约运行成本，由于不同生产线，不同型号的鞋点胶需求也各不相同，算法运行的性能也变得不可控，因此，处理各种不同程度组合优化问题的高性能模型仍是一个研究热点，迁移学习是解决此问题的一种趋势。

6.3 特征结合规划点胶

针对鞋底特征提取进行重点点胶能有效提高点胶效率，以多任务规划合并的点胶形式是高性能规划点胶的一大趋势，针对鞋底通用特征进行固定化点胶路径，仅对具有不同特征的点胶任务进行规划能有效提高规划效率，以多规划任务并行的方法换取时间效率是目前最主流的高效点胶模式。