PathPlanningofAutomaticOpticalInspectionMachinesforPCBAssemblySystemsTae-HyoungPark,Hwa-JungKimPCB缺陷自动光学检测系统中路径规划策略的研究Tae-HyoungPark,Hwa-JungKim摘要：本文提出了一种路径规划算法，运用在PCB(印刷电路板)装配线AOI(自动光学检测)平台上，提高机器的效率。在考虑摄像机的FOV(field-of-view)前提下，为了最小化总体的工作时间，检测窗和摄像机的检测次序应该最优化。本文提出了一种新方法，应用一种混合的遗传算法来解决这个高度复杂的最优化问题，同时实现检测窗和检测路径的最优化。通过仿真比较，证明算法的有效性。关键词：路径规划，最优化，遗传算法，AOI，PCB检测概述当今在电子制造行业中，SMT（surfacemounttechnology表面贴装技术）是最流行的PCB装配技术。SMT技术极大地提高了安装密度，替代了传统的插件元件技术。图1所示是一条完整的采用SMT技术的PCB生产线。在该生产线上，AOI用于元件和焊盘的检测。随着图像处理技术的发展，AOI技术在PCB装配生产线上得到大规模应用，已经成为一种减少产品成本和提高竞争力的有效手段。本文提出的算法，正是为了减少AOI机器整体工作时间，提高效率。AOI的路径规划问题，就是找到最合理的摄像机移动路径，使得检测时间最少。摄像机能采集到的图像大小由它的FOV限制。PCB板上所有的元件和焊盘应该被归为不同的检测聚类。摄像机应该访问获取所有检测聚类，获取图像以用于检测。检测聚类的数量和摄像机的移动路径，对整体的工作时间有很大影响。因此路径规划问题就是最小化检测聚类数量和检测路径问题。这类问题属于NP难题，因此，要想在合理时间内找到最优化的解决方案是十分困难的。在本文中，我们提出了一种方法来获得路径规划问题的近似最优解。至今为止，AOI方面的研究大多集中在图像处理方面[1][2][3]。要想使用典型的聚类算法[4][5]来解决我们的问题是非常困难的，因为我们的问题和聚类算法问题在决策方法和最优化标准上有很大的不同。用于解决TSP(travellingsalesmanproblem旅行商问题)[6]的最优化方法只能用于解决我们的问题部分方面。因此，设计出新的方法来结局整个路径规划问题就变得十分必要了。我们可以把路径规划问题分为两个子问题：检测聚类数量问题和检测路径问题。聚类算法可以用来解决前者，TSP算法可以用来解决后者。这种分布解决方案可以在短时间内得出好的解决方法，但效率往往很低，因为检测聚类数量问题和检测路径问题不是彼此独立的不相关问题。为了提高解决方法的有效性，我们设计出一元化的方法，同时解决检测聚类数量和检测路径问题。这种方法采用混合的遗传算法。最后，我们在一台商用机器上通过仿真证明了算法的有效性。2路径规划问题图2所示为由移动平台和相机组成的AOI机器。移动平台在Y轴方向移动，摄像机在X轴方向上移动。X方向和Y方向上能同时移动。因为摄像机的视野受其自身限制，因此摄像机通过需要移动来获得整体的图像。图3所示为检测窗、摄像机的视野和摄像机的移动路径。检测窗是摄像机需要访问的长方形的区域，每个区域都包含许多元件和焊盘。一块PCB板中往往被划分为成百的检测窗区域。FOV是一台摄像机一次照相能够达到的最大摄像范围。因此摄像机的视野往往是固定的，大约在几十毫米。检测聚类是能够被在摄像机FOV范围内的一系列检测窗。检测聚类的大小受摄像机的视野限制。摄像机从图3的等待点开始，然后访问每个检测聚类以获得图像数据。摄像机的路径就是检测聚类的访问路径。待检测元件集合的数量就是摄像机拍照的次数，因此，如果我们减少集合的数量，就可以减少AOI机器图像获取的时间。另外，总的工作时间还包括摄像机在各个检测窗之间的移动时间。因此，检测窗数量和检测路径都需要实现最优化来减少总体的处理时间。AOI中的路径规划问题，就是如何决定元件集合数量和检测路径的问题。我们首先把路径规划问题数学化。W表示检测窗,C表示待检测聚类。W={1,...,m}(1)C={1,...,n}(2)n是需要确定的待检测的元件聚类的数量，定义集合变量:定义次序变量:因此，路径规划问题数学化为以下的问题：（3）为获取一个检测聚类的图像的时间，可以认为是常数。为摄像机从聚类i移动到聚类j所用的时间，由变量决定。所以公式(3)是总的工作时间。约束(4)表示每个检测窗应该在一个检测聚类当中。约束(5)表示每个检测聚类至少包含一个个检测窗中。和代表一个检测聚类j在X轴上的最大值和最