Fractal Tool Path Connection Technology Based on Improved Ant Colony Algorithm

Abstract

Abstract:

To solve the problems of numerous empty trips and tool-retraction in fractal tool path, the fractal path segments were connected by border crop profiles. To determine the shortest overall connection path, an ant colony algorithm was applied to initially connect the scattered fractal path segments on the same layer of slice. Afterwards, according to the principles of the path planning, the validity of the connection path was judged, and the bad forming quality that was affected by the unreasonable connection path was removed. Selection strategy and pheromone evaporation coefficient were dynamically adjusted to improve the basic ant colony algorithm, which converged slowly and was easy to get stuck in a local optimal solution. The experimental results demonstrate that the method can effectively reduce empty trips and tool-retraction on the same layer of slice, and the improved ant colony algorithm shows good convergence and global search capabilities.

Key words: fractal tool path, empty trip, tool-retraction, ant colony algorithm, path connection

摘要：

为了解决分形刀轨中存在的大量空行程和跳刀问题，使用部分边界裁剪轮廓对分形路径段进行了连接。首先采用蚁群算法对同一切片层面上的分形路径段进行初步连接，确定整体最短连接路径。然后依据扫描路径规划原则，对连接路径进行有效性判断，消除了不合理连接路径对成形质量的影响。针对基本蚁群算法存在的收敛慢、易陷入局部最优解等缺陷，采用动态调整选择策略和信息素挥发系数对蚁群算法进行了改进。试验结果表明，该方法有效减少了同一切片层面上的空行程和跳刀次数，且改进的蚁群算法具有很好的收敛效果和全局搜索能力。

关键词: 分形刀轨, 空行程, 跳刀, 蚁群算法, 路径连接

CLC Number:

TP391

Wu Changyou, Dai Ning, Liu Hao, Chen Xiaosheng, Li Dawei, Shen Zhenhong, Sun Dengguang. Fractal Tool Path Connection Technology Based on Improved Ant Colony Algorithm[J]. China Mechanical Engineering, 2016, 27(01): 58-65.

吴长友, 戴宁, 刘浩, 程筱胜, 李大伟, 沈振宏, 孙登广. 基于改进蚁群算法的分形刀轨连接技术[J]. 中国机械工程, 2016, 27(01): 58-65.

References

[1]刘征宇，宾鸿赞，张小波，等. 生长型制造中分形扫描路径对温度场的影响[J]. 华中理工大学学报，1998，26(8):32-34.
Liu Zhengyu，Bin Hongzan，Zhang Xiaobo，et al. The Influence of the Fractal Scanning Pat on the Temperature Field of the Layer in Material Increase Manufacturing[J]. Journal of Huazhong University of Science and Technology，1998，26(8):32-34.
[2]Cox J J，Takezaki Y，Ferguson H R P，et al. Space Filling Curves in Tool Path Applications[J]. Computer Aided Design，1994，26(3)：215-224.
[3]Yang J，Bin H，Zhang X，et al. Fractal Scanning Path Generation and Control System for Selective Laser Sintering(SLS)[J]. International Journal of Machine Tools and Manufacture，2003，43(3)：293-300.
[4]李德信，焦俊鹏. Hilbert填充曲线用于刀具路径生成的算法及改进研究[J]. 中国机械工程，2011，22(22)：2739-2743.
Li Dexin，Jiao Junpeng. Research on Tool Path Generation Algorithm and Improvement Based on Hibert Space-filling Curves[J].China Mechanical Engineering，2011，22(22)：2739-2743.
[5]Stutzle T，Hoos H. Max-min Ant System and Local Search for the Traveling Salesman Problem[C]//Proceedings of the 4th IEEE International Conference on Evolutionary Computation. Indianapolis，1997：309-314.
[6]Bullnheimer B，Hartl R F，Strauss C. A New Rank-based Version of the Ant System: A Computational Study[J]. Central European Joural for Operations Research and Economics，1999，7(1)：25-38.
[7]朱庆保, 杨志军. 基于变异和动态信息素更新的蚁群优化算法[J]. 软件学报，2004，15(2)：185-192.
Zhu Qingbao, Yang Zhijun. An Ant Colony Optimization Algorithm Based on Mutation and Dynamic Pheromone Updating[J]. Journal of Software，2004，15(2)：185-192.
[8]柳长安，鄢小虎，刘春阳，等. 基于改进蚁群算法的移动机器人动态路径规划方法[J]. 电子学报，2011，39(5)：1220-1224.
Liu Chang'an, Yan Xiaohu, Liu Chunyang, et al. Dynamic Path Planning for Mobile Robot Based on Improved Ant Colony Optimization Algorithm[J]. Acta Electonica Sinica，2011，39(5): 1220-1224.
[9]王占锋，杜海莲，安素芳，等. 求解车辆路径问题的改进蚁群算法[J]. 华侨大学学报，2013，34(1)：36-39.
Wang Zhanfeng, Du Hailian, An Sufang, et al. An Improved Ant Colony Algorithm Based on Vehicle Routing Problem[J]. Joural of Huaqiao University(Natural Science)，2013，34(1)：36-39.
[10]黄小毛. 熔丝沉积成形若干关键技术研究[D]. 武汉：华中科技大学，2009.
[11]Yuan Y，Wang D W. Path Selection Model and Algorithm for Emergency Logistic Mangement[J]. Computers & Industrial Engineering，2009，56(3)：1081-1094.
[12]Jin Y A，He Y，Fu J Z. Optimization of Tool-path Generation for Material Extrusion-based Additive Manufacturing Technology[J]. Additive Manufacturing，2014(1/4)：32-47.
[13]Liu F，Zeng G Z. Study of Genetic Algorithm with Reinforcement Learning to Solve the TS-P[J]. Expert Systems with Aplications，2009，36(3)：6995-7001.
[14]雷伟军，程筱胜，戴宁，等. 基于改进遗传算法的多模型加工路径规划[J]. 机械工程学报，2014，50(11)：153-161.
Lei Weijun，Cheng Xiaosheng，Dai Ning，et al. Multi-model Machining Path Planning Based on Improved Genetic Algorithm[J]. Journal of Mechanical Engineering，2014，50(11)：153-161.
[15]Marco D，Thomas S. Ant Colony Optimization: Overview and Recent Advances[J]. Handbook of Metaheuristics，2010，146：227-263.
[16]刘新华，张旭堂，刘文剑. 基于改进最大最小蚂蚁系统的多工艺线路决策方法[J].计算机集成制造系统，2008，14(12)：2414-2420.
Liu Xinhua，Zhang Xutang，Liu Wenjian. Multi-process Routes Decision-making Methodology Based on Improve Max-min Ant System[J]. Computer Integrated Manufacturing Systems，2008，14(12)：2414-2420.