2020, Vol. 41
为了取代ISO(international organization for standardization，ISO) 6983，国际标准化组织ISO正在研究和制定一个面向对象的新型NC编程数据接口国际标准STEP-NC[1].该标准独立于机床，能够提供零件加工所需的全部信息，支撑零件设计和制造信息的双向流动，支持零件加工NURBS插补，为刀具路径规划的智能化提供了条件.因此，基于STEP-NC的刀具路径规划成为智能制造领域研究热点之一.
国内外学者对刀具路径规划进行了很多有意义的研究.Dhanik等[2]基于快速行进方法实现刀具路径的生成；王利智[3]采用“最大深度法”对刀具轨迹规划进行了研究；Manav等[4]提出基于多准则优化的刀具路径规划方法；王家斌等[5]提出一种螺旋刀具路径生成方法.上述方法虽然一定程度上解决了刀具路径规划问题，但与STEP-NC不兼容.在基于STEP-NC的刀具路径规划研究方面，Laguionie等[6]基于轮廓平行铣和双向铣削策略，提出一种用于STEP-NC简单制造特征加工的摆线铣削策略；Du等[7]提出一种基于多智能体的STEP-NC制造特征刀具路径规划方法；Cuenca等[8]从硬件角度出发，提出一种精度高、鲁棒性强的STEP-NC制造特征刀具轨迹生成解决方案；Liang等[9]开发一个与STEP-NC兼容的CNC系统，该系统具有刀具路径规划、刀位点计算、刀具偏移和逆运动学变换的功能；齐明[10]开发了用于电路板加工的STEP-NC CAM模块，该模块采用基于像素的方法实现了STEP-NC制造特征刀具路径的生成；Ahmad等[11]构建一种基于知识库的STEP-NC数控系统，该系统能够自动规划STEP-NC制造特征的刀具路径.
综上所述，虽然国内外学者对刀具路径规划进行了很多有意义的研究，但是大多数研究或者与STEP-NC不兼容，或者主要集中在STEP-NC简单制造特征的刀具路径生成，对于STEP-NC复杂型腔(带有岛屿的型腔)的刀具路径生成方法研究很少.因此，本文提出了一种基于图论和改进Dijkstra算法的STEP-NC复杂型腔最短刀具路径生成方法.
1 STEP-NC数据模型为了提供一种高级的产品数控数据描述的中性机制，国际标准化组织ISO提出了一种新型的NC编程数据接口国际标准STEP-NC[12].如图 1所示，STEP-NC标准是以基于制造特征的方式描述加工对象，描述加工的是什么，而不是和ISO 6983一样描述怎么加工，包含零件加工所需的全部信息，而且支持设计信息和制造信息之间的双向流动，支持NURBS插补，这种结构化的数据模型可以清楚全面地描述工件的所有几何信息和工艺信息，为刀具路径的自动生成提供了条件.
|
图 1 简化的STEP-NC数据模型 Fig.1 Simplified STEP-NC data model |
针对STEP-NC复杂型腔，本文提出一种基于图论和改进Dijkstra算法的STEP-NC复杂型腔最短刀具路径生成方法.该方法包括STEP-NC复杂型腔封闭等距环生成、基于图论的封闭等距环赋权有向图生成和基于改进Dijkstra算法的STEP-NC复杂型腔最短刀具路径生成.
2.1 STEP-NC复杂型腔封闭等距环生成STEP-NC复杂型腔封闭等距环的生成包括走刀行距计算、基本元素等距偏置和封闭等距环生成.
2.1.1 走刀行距计算走刀行距的计算应在满足加工残留高度要求的情况下，尽量减少加工时间，其计算表达式为
|
(1) |
式中：d为走刀行距；R为刀具半径；r为刀尖圆弧半径；h为残留高度.
2.1.2 基本元素等距偏置复杂型腔的轮廓环由直线和圆弧基本元素组成，这些基本元素的等距偏置过程如下(本文规定型腔轮廓向内等距，岛屿轮廓向外等距)：
1) 直线段等距偏置.假设R(Rx，Ry)和E(Ex，Ey)分别为直线段的起点和终点矢量，则直线段的等距偏置法向矢量N为
|
(2) |
等距后的直线段起点矢量a和终点矢量b分别为
|
(3) |
|
(4) |
2) 圆弧段等距偏置.假设C(Cx，Cy)为圆弧的圆心，R(Rx，Ry)，E(Ex，Ey)分别为其起点和终点矢量，则圆弧段起点等距偏置法向矢量Ns和终点等距偏置法向矢量Ne分别为
|
(5) |
|
(6) |
等距后的圆弧段起点矢量a和终点矢量b分别为
|
(7) |
|
(8) |
基本元素经过等距偏置后，相邻等距线之间可能出现相交或者分离.为了生成1条连续的加工路径，相邻等距线之间需要进行过渡连接，即生成封闭等距环.封闭等距环生成的基本方法是：轮廓在进行等距之后，若生成的等距线相交，则添加直线连接，如图 2所示；若生成的等距线分离，则添加圆弧过渡，过渡圆弧的圆心是等距偏置前两直线的公共端点，半径等于走刀行距，圆弧与两直线相切，如图 3所示.
|
图 2 等距线相交的过渡连接 Fig.2 Transitional connection between isometric intersecting lines |
|
图 3 等距线分离的过渡连接 Fig.3 Transitional connection between isometric separate lines |
为了快速生成刀具路径，基于图论[13]将封闭等距环表示为带约束的赋权有向图，主要步骤如下：
1) 标记赋权有向图中的节点vi及连接弧am：赋权有向图的节点vi为封闭等距环中的直线段端点、圆弧段端点以及它们的交点；赋权有向图的连接弧am为封闭等距环中相邻节点间的直线段或圆弧段；
2) 确定赋权有向图中连接弧am的方向：根据型腔轮廓等距环的方向为逆时针，岛屿轮廓等距环的方向为顺时针，确定封闭等距环的赋权有向图中各连接弧am的方向；
3) 标记赋权有向图中转向约束标志σv：为了防止生成无效路径，需要在节点vi处设置转向约束标志σv；
4) 确定赋权有向图中连接弧am的权值：相邻节点vi和vj之间的连接弧am对应的权值为弧长wij.
根据以上步骤得到带约束的赋权有向图D=(V，A，Σ，W)，其中V为节点集合，A为弧集合，Σ为约束集合，W为权值集合.
2.3 基于改进Dijkstra算法的STEP-NC复杂型腔最短刀具路径生成根据上文得到的封闭等距环赋权有向图，采用改进的Dijkstra算法生成STEP-NC复杂型腔最短刀具路径.传统Dijkstra算法[14]是一种贪心算法，能够寻找最短路径.由于该算法中节点只能访问一次，因此该算法不能直接用于STEP-NC复杂型腔最短刀具路径的生成.针对上述问题，本文通过增设待选择节点集合T(通过节点集合T可实现节点处最短路径选择)对传统Dijkstra算法进行了改进(如图 4所示)，进而实现STEP-NC复杂型腔最短刀具路径生成，主要步骤如下：
|
图 4 基于改进Dijkstra算法的STEP-NC复杂型腔最短刀具路径生成算法流程图 Fig.4 Flow chart of the shortest tool path generation method for STEP-NC complex pockets based on improved Dijkstra algorithm |
1) 令已访问节点集合S=Ø，未访问节点集合U=Vl(Vl为第l次等距计算得到的封闭等距环赋权有向图中的节点集合，l=1，2，…，k，k为能够进行等距操作的次数，令l的初始值为1)，待选择节点集合T=Ø.
2) 令U中节点vj的初始标号为[vi，uj](vi为最短路径上节点vj的前一节点，初始的vi为任意节点M；uj是起点到节点vj的距离，其初始值为∞); 若节点vj被选为起点，则令其标号为[vj，uj](vj为节点vj的本身；uj是节点vj到其本身的距离，其值为0).
3) 从U中选出任意一节点vj为起点和终点(为了说明方便，起点用vi表示，终点用vi*表示)，并从U中删除vj.将vi加入到S中，将vi*存入U中，确定vi的标号为[vi，0].
4) 判断U中是否存在与vi的直接连接的节点vj.若是，则执行步骤5)；否则，得到1条无效路径，将该路径的终点从U中删除，并执行步骤10).
5) 对于U中与vi直接连接的节点vj，若uj>ui+wij，则令uj=ui+wij，并更新其标号[vi，uj].
6) 若节点vi不是起点且设置转向约束标志σv，在U中满足条件(节点vj与节点vi之间的连接弧的方向应不同于节点vi与其上一节点的连接弧方向)的节点vj中选取uj(uj>0)最小的；否则，直接从U中找出uj最小的节点vj.
7) 将被选取节点vj记为vi，加入到S中，确定vi的标号为[vi′，ui](vi′为最短路径上节点vi的前一节点；ui是起点到节点vi的距离)，并将vj从U中删除.另外，若vi为交点，同时加入T中.
8) 判断vi是否为终点vi*.若是，则得到1条最短路径，并执行步骤9)；若否，则返回步骤4).
9) 判断得到的最短路径对应的环是否为逆时针环.若是，则判定该路径为最短刀具路径，并用向量path记录该路径中节点的标号，执行步骤11)；否则，判定该路径为无效路径，并将赋权有向图中属于该无效路径的连接弧的弧长设置为∞，执行步骤10).
10) 将S中属于该无效路径且为交点的节点vi删除，并将T中的节点存入U中.
11) 判断U是否为空集.若是，则得到第l个封闭等距环的全部最短刀具路径；否则，令T=Ø，执行步骤2).
3 实例研究图 5给出了一个包含STEP-NC复杂型腔的零件模型.基于所提出的刀具路径生成方法，对该STEP-NC复杂型腔进行了刀具路径规划.
|
图 5 零件三维模型 Fig.5 3-D model of a part |
本实例中刀具半径R为2 mm，刀尖圆弧半径r为0.3 mm，允许的残留高度h为3.2 μm.由于封闭等距环的相似性，图 6给出了该复杂型腔第4次等距偏置得到的封闭等距环.然后，基于图论得到图 6对应的赋权有向图，如图 7所示.在此基础上，基于改进的Dijkstra算法得到4条最短刀具路径，如图 8所示.进一步，得到该STEP-NC复杂型腔的全部最短刀具路径，刀具路径总长度为2 926.1 mm，如图 9所示.在Windows7操作系统、CPU为2.70 GHz和内存为4 GB的计算机环境下，刀具路径生成耗时0.1 s.
|
图 6 第4个封闭等距环 Fig.6 The fourth closed equidistant ring |
|
图 7 第4个封闭等距环的赋权有向图 Fig.7 Weighted digraph of the fourth closed equidistant ring |
|
图 8 第4个封闭等距环的最短刀具路径 Fig.8 The shortest tool paths of the fourth closed equidistant ring |
|
图 9 STEP-NC复杂型腔的全部最短刀具路径 Fig.9 All the shortest tool paths of STEP-NC complex pockets |
当型腔轮廓和岛屿轮廓的等距偏置次数不同时，生成的STEP-NC复杂型腔刀具路径总长度为2 974.7 mm，如图 10所示.在相同计算机环境下，其刀具路径生成耗时0.14 s.而采用等距法生成的STEP-NC复杂型腔刀具路径总长度为3 027.3 mm，如图 11所示.在相同计算机环境下，其刀具路径生成耗时0.2 s.因此，本文所提出的刀具路径生成方法更好、更高效.该零件模型刀具路径规划界面如图 12所示.
|
图 10 等距偏置次数不同时生成的STEP-NC复杂型腔的最短刀具路径 Fig.10 The shortest tool path generated with different offsets for STEP-NC complex pockets |
|
图 11 基于等距法得到STEP-NC复杂型腔的最短刀具路径 Fig.11 The shortest tool path generated for STEP-NC complex pockets based on the isometric method |
|
图 12 STEP-NC复杂型腔刀具路径规划界面 Fig.12 Interface of tool path planning for STEP-NC complex pockets |
1) 提出了基于图论的封闭等距环赋权有向图生成方法，为STEP-NC复杂型腔最短刀具路径的快速生成奠定了基础.
2) 提出了基于改进Dijkstra算法的STEP-NC复杂型腔最短刀具路径生成方法，并与图论有机结合，为自动生成STEP-NC复杂型腔的最短刀具路径提供了一个有效的解决方案，也为实现基于STEP-NC的智能数控系统提供了有力的技术支撑.
接下来，将对STEP-NC复杂型腔刀具过渡路径规划和STEP-NC自由曲面特征的刀具路径规划进行研究.
| [1] |
Um J, Rauch M, Hascoët J Y, et al. STEP-NC compliant process planning of additive manufacturing:remanufacturing[J]. The International Journal of Advanced Manufacturing Technology, 2017, 88(5/6/7/): 1215-1230. |
| [2] |
Dhanik S, Xirouchakis P. Contour parallel milling tool path generation for arbitrary pocket shape using a fast marching method[J]. The International Journal of Advanced Manufacturing Technology, 2010, 50(9/10/11/12): 1101-1111. |
| [3] |
王利智.二维数控铣切复合加工轨迹规划与路径优化研究[D].武汉: 华中科技大学, 2013. (Wang Li-zhi.Research on path planning and optimization for combined machining of two-dimensional milling and cutting[D].Wuhan: Huazhong University of Science and Technology, 2013. ) |
| [4] |
Manav C, Bank H S, Lazoglu I. Intelligent toolpath selection via multi-criteria optimization in complex sculptured surface milling[J]. Journal of Intelligent Manufacturing, 2013, 24(2): 349-355. |
| [5] |
王家斌, 王炫润, 李劭晨, 等. 含孤岛型腔铣削加工的螺旋刀轨生成算法[J]. 航空学报, 2016, 37(5): 1689-1695. (Wang Jia-bin, Wang Xuan-run, Li Shao-chen, et al. Spiral tool path generation algorithm for milling pocket with island[J]. Acta Aeronautica et Astronautica Sinica, 2016, 37(5): 1689-1695.) |
| [6] |
Laguionie R, Rauch M, Hascoët J Y. Toolpaths programming in an intelligent STEP-NC manufacturing context[J]. Physics, 2009, 19(7): 941-942. |
| [7] |
Du J, Yan X G, Chen Z. A multi-agent based tool path planning method for STEP-NC compliant milling[J]. Advanced Materials Research, 2010, 97/98/99/100/101(4): 3382-3386. |
| [8] |
Cuenca S, Jimeno-Morenilla A, Martínez A, et al. Hardware approach to tool path computation for STEP-NC enabled CNC:a case study of turning operations[J]. Computers in Industry, 2011, 62(5): 509-518. |
| [9] |
Liang H B, Li X. Five-axis STEP-NC controller for machining of surfaces[J]. The International Journal of Advanced Manufacturing Technology, 2013, 68(9/10/11/12): 2791-2800. |
| [10] |
齐明.基于STEP-NC的刀具路径规划方法研究[D]济南: 山东大学, 2013. (Qi Ming.Study on the tool path planning based on STEP-NC[D].Jinan: Shandong University, 2013.) ) |
| [11] |
Ahmad R, Tichadou S, Hascoët J Y. A knowledge-based intelligent decision system for production planning[J]. The International Journal of Advanced Manufacturing Technology, 2016, 89(5/6/7/8): 1717-1729. |
| [12] |
Zhang Y, Zeng Q F, Mu G D, et al. A design for a novel open, intelligent and integrated CNC system based on ISO10303-238 and PMAC[J]. Technical Gazette, 2018, 2(25): 470-478. DOI:10.17559/TV-20170419111243 |
| [13] |
Gross J L, Yellen J, Zhang P. Handbook of graph theory[M]. 2nd ed. Boca Raton: CRC Press, 2013: 164-195.
|
| [14] |
Huang Y.Research on the improvement of Dijkstra algorithm in the shortest path calculation[C]//Advances in Engineering Research.Paris: Atlantis Press, 2017: 745-749.
|