人工智能3D打印完全遍历路径规划技术研究★

李 荣 帅

(上海建工集团工程研究总院，上海　201114)



·计算机技术及应用·

人工智能3D打印完全遍历路径规划技术研究★

李 荣 帅

(上海建工集团工程研究总院，上海201114)

在系统总结3D打印技术、人工智能以及路径规划技术发展的基础上，在建筑3D打印领域中提出进行打印头完全遍历路径规划研究，并分析了其必要性和紧迫性,同时，构建了打印头完全遍历路径规划的数学模型，提出了评价打印头完全遍历路径规划性能的评价指标，最后展望了通过人工智能算法进行建筑3D打印完全遍历路径规划的研究方向。

3D打印，建筑，人工智能，完全遍历，路径规划

0　引言

3D 打印(3D printing，又称三维打印)是一种快速成形技术，它以数字化模型为基础，运用可粘合材料，通过逐层打印的方式构造物体。目前，随着技术的发展，3D打印技术相继应用于很多行业，2010年开始，各国研究人员相继在建筑3D打印领域开展了相关的研究和应用，取得了一定的成果，但是在建筑3D打印领域的研究和应用更多的是一种应用探索，而缺乏相关的系统研究。目前应用于建筑3D打印领域的3D打印装置基本上均基于熔融沉积式(Fused Deposition Modeling，FDM)成形原理。基于FDM技术的建筑用3D打印装置示意图如图1所示，俯视角度观察，建筑3D打印机平面如图2所示。

相对于一般的3D打印物品，建筑结构体量巨大，带来的一个直接问题就是打印头如何进行打印路径规划，以达到效率与精度的优化平衡。而对打印头路径规划问题进行数学描述，建模，引入人工智能算法进行求解与优化就成了必须面对和解决的问题[1-4]。

1　遍历路径规划及人工智能的发展

1.1人工智能的发展

人工智能(AI)是21世纪科技领域最为前沿的技术之一，是意图通过了解智能的实质，进而生产出一种智能机器，而且使其能按照人的智能相类似的方式做出相应的反应，这一领域的研究主要有语言与图像识别、自然语言的处理、智能机器人以及专家系统等。我们通常将人工智能划分为三个阶段，分别为计算智能、感知智能和认知智能。

图1　建筑用3D打印机示意图

图2　建筑3D打印机平面示意图

目前人工智能的发展还处于最初的计算智能阶段,从广义上讲，计算智能就是通过借鉴基于生物体系的物种进化、免疫、神经网络等某些生物体智能机制,而用数学语言将其进行抽象描述，进而形成的计算方法。其特点是不需要建立精确模型对问题本身进行描述。目前，发展比较迅速且被实践证明比较有效的主要计算智能方法包括免疫算法、进化计算、进化神经网络、模糊进化计算、DNA计算人工神经网络等[17-20]。

1.2遍历路径规划的发展

目前，在3D打印领域，打印头路径规划技术一般还沿用数控切削加工中的路径规划方法。但是原有的数控加工技术是基于去除原理，而3D打印技术是基于离散堆积原理的快速成形技术，这两者在理论上就有很大的不同，同时由于在建筑3D打印中，采用混凝土等非即时固化材料，导致建筑体或构件成形速度比较低，而且出料精度差，这样的特点使得针对一些其他快速成形技术比较有效的路径规划技术并不适用于建筑3D打印。与此同时，先前研究[13-20]中都没有针对建筑3D打印的特点给出路径规划技术完整的数学模型，也没有给出路径遍历策略及简化的定理和证明，将路径间排序问题简化为以路径原始起点为单元的TSP，忽略了其他潜在起点对此问题的影响；所使用算法寻优能力和效率不高，对于大规模问题只能得到一般可行解[9-12]。

1.3建筑3D打印完全遍历路径规划的核心问题

环境建模和路径搜索是打印头完全遍历路径规划的核心问题。环境建模有三方面表示：1)可打印空间表示；2)目标表示；3)不可打印空间表示。在打印头路径规划问题中，第一步需要解决的就是环境建模，因为每一种路径规划算法都是为了针对某一个环境建模而构建的，它们是一一对应的，所以环境建模方法的好坏直接影响到路径规划的策略和效率及其完成度。环境模型划分为静态模型和动态模型两大类。静态模型是固定模型，环境是固定不变的。动态模型是不断变化的模型。静态路径规划是目前研究的热点，关于静态已知环境的研究和建模技术研究较成熟，但是随着科技的发展，动态的路径规划问题也引起越来越多人们的注意。在解决部分未知或者完全未知环境的路径规划问题方面存在一定的困难，这其中主要原因是因为难以建立有效的环境模型。合理的环境建模有利于减少规划中的搜索量，提高打印效率[13-16]。

打印头路径规划问题，关键就是要寻找一条安全路径，来保证打印头在指定的区域内从起始位置越过不可打印区域移动到目标位置。合理的通过设计环境模型、表达方法与数据结构来反映打印头处于某一个位置时可能发生偏离可打印区域的概率，这样构成了一个状态空间。在此基础上，建立各个子区域的连通回路，连通回路的构成主要依靠搜索功能，搜索完成后即在起点与终点间得到一条路径，将通路上的各个节点全部在模型中表示出来，所构成的路径就是打印头的遍历路径[17-20]。

2　建筑3D打印中完全遍历规划的数学描述与评价指标

2.1数学描述

假设：V={x,y|x,y特定的点，打印头移动范围}。

定义1：路径区间VΩ={x，y|ocup(x,y)=0}⊆V,其中，ocup(x,y)为占有函数，如下式所示。

定义2：不可达区域VΔ={x,y|ocup(x,y)=1}⊆V，显然VΩ∩VΔ=0，且VΩ∪VΔ=1。

打印头在移动过程中将其看成一个质点，质点运动就会形成连续的运动轨迹。可行遍历轨迹是指打印头移动过程产生的运动轨迹，在一个平面内可以产生多条路径，该路径均为可能路径，这些路径构成一个集合，称之为遍历轨迹，可以用下式表示:

首先，政府在宏观层面的战略部署能够促进一国文化产业的蓬勃发展，甚至成为一国经济的主要支撑点。以拥有相似文化底蕴的文化大国韩国为例，1998年韩政府出台“文化立国”战略，随后又紧跟着出台了一系列政策，使韩国影视文化行业迸发活力。时至今日，韩国影视剧出口值屡获新高，文化产业成为国民经济的支柱产业，真正做到了“文化强国”、“文化立国”。其次，国家文化企业实力强大离不开有力的文化监管。如今很多文化企业存在偷税漏税、抄袭、恶意竞争等问题，影视文化行业需要政府对法律的完善和对违法行为的严厉处罚，只有保证文化氛围的文明和谐才能更好地进行文化产业体制改革。

L∑={li(x,y,xs,ys,xg,yg)}。

其中,(xs,ys),(xg,yg)分别为打印头起点和终点坐标值，(x,y),(xs,ys),(xg,yg)⊆V。

2.2性能指标

打印头遍历区域的性能可以用路径总长度、转弯次数、遍历重叠率、遍历覆盖率来衡量。假设用V,VΩ,Vhc以及Vcc依次表示打印头的整个工作空间、可打印空间、已遍历的面积和重复遍历面积，可得到以下四个性能指标：

1)路径总长度。

路径总长度是指打印头完成遍历路径规划后，得出的打印头移动距离。在统一换进地图下，相同的遍历完成率，路径总长度越小，控制打印头的算法越好。

2)转弯次数。

转弯次数是指打印头在移动过程中运动方向发生改变的次数，通常打印头在运动过程中，转弯次数越少，越能说明控制打印头的算法越好。

3)遍历完成率。

遍历完成率指在进行规划路径时，打印头所走过路径的覆盖面积和全部可能到达面积的比例，最后表示结果是一个百分比，具体如下式所示：

Dhc=Vhc/VΩ。

遍历完成率表示了打印头完成任务的百分比，百分比越高，越能说明该算法的优秀。

4)遍历重叠率。

在路径规划时，打印头所有的遍历中出现的重叠面积总和与可达区域面积的比值，如下式所示：

Dcc=Vcc/VΩ。

遍历相邻区域时，尽量要将整个区域遍历完全，但是不可避免的在遍历过程中可能会存在一定的交叉。从算法的角度讲，交叉的区域应尽可能小，此时打印头性能会比较高。但是打印头本身就存在一定的系统误差和定位误差，遍历重叠的区域不会像理想的那么小。此外，根据该比例还可计算出没有被遍历过的面积所占有的百分比，可以表示成：

Duc=1-Dhc。

该比例是指打印头没有遍历过的面积所占总的可以到达的面积的比例。打印头性能越高，其各项指标会越优。

上述给出了打印头完全遍历路径规划的性能评价指标，可以根据这个指标来评判一个算法的优越程度。

3　结论与展望

在目前3D打印技术、人工智能技术及路径规划技术都取得了长足发展的情况下，针对建筑结构体量巨大，打印效率与精度的矛盾愈发突出，有必要开展基于人工智能的建筑3D打印完全遍历路径规划技术研究，通过研究，取得大体量建筑直接进行3D打印的效率与精度的优化平衡。未来，本方面的主要研究方向包括：

1)建立建筑3D打印路径规划技术的环境模型，针对静态环境模型和动态环境模型的不同开展相应的对比研究。

2)开展人工智能算法在建筑3D打印完全遍历路径规划领域的性能对比研究，选择出一种或几种性能相对较好的人工智能算法。

3)开展基于人工智能的建筑3D打印完全遍历路径规划技术数值模拟研究，检验选定的人工智能算法在设定的环境模型中的适应性及性能。

4)进行实验研究，在实际的建筑3D打印装置中运用人工智能控制打印头的移动路径，对算法的性能进行实际验证。

另外，鉴于建筑3D打印实际是在三维空间下进行的，所以后续应在实现二维空间下基于人工智能的建筑3D打印完全遍历路径规划后，后续还应开展在三维空间下的遍历路径规划技术研究工作。

[1]焦阳.基于模糊PID算法的3D打印后处理系统[J].电子制作,2014(20):44-45.

[2]朱博,邓三鹏,王英飞,等.基于生物激励神经网络的移动机器人遍历路径规划[J].装备制造技术,2014(12):30-32.

[3]史玉升,张李超,白宇,等.3D打印技术的发展及其软件实现[J].中国科学:信息科学,2015(2):197-203.

[4]罗楠,王泉,刘红霞.一种快速3D打印分层方向确定算法[J].西安交通大学学报,2015(5):140-146.

[5]胡瑞珍,黄惠.3D打印启发下的模型实例化优化研究综述[J].计算机辅助设计与图形学学报,2015(6):961-967.

[6]刘利刚,徐文鹏,王伟明,等.3D打印中的几何计算研究进展[J].计算机学报,2015(6):1243-1267.

[7]张淑华.裸眼3D打印中光强矢量化处理算法研究[J].科学技术与工程,2013(30):9083-9088.

[8]王妹婷,齐永锋,陆柳延,等.双向清洗机器人玻璃幕墙完全遍历路径规划[J].机械设计与制造,2013(11):211-213.

[9]李旭东.从仿真看3D打印及其若干问题[J].工业技术创新,2014(1):5-18.

[10]魏潇然,耿国华,张雨禾.3D打印中的模型去支撑划分方法[J].西安电子科技大学学报,2016(2):180-185.

[11]田春颖,刘瑜,冯申坤,等.基于栅格地图的移动机器人完全遍历算法——矩形分解法[J].机械工程学报,2004(10):56-61.

[12]杨竹丰,张赤斌,颜肖龙.基于标点定位的清扫机器人遍历算法研究[J].电子机械工程,2006(1):59-61.

[13]邱雪娜,刘士荣,宋加涛,等.不确定动态环境下移动机器人的完全遍历路径规划[J].机器人,2006(6):586-592.

[14]邱雪娜,刘士荣,俞金寿,等.移动机器人的完全遍历路径规划:生物激励与启发式模板方法[J].模式识别与人工智能,2006(1):122-128.

[15]张赤斌,王兴松.基于蚁群算法的完全遍历路径规划研究[J].中国机械工程,2008(16):1945-1949.

[16]刘奎,张赤斌,易红.在未知环境下完全遍历算法——等单元分解法[J].系统仿真技术,2005(3):136-140.

[17]刘星,张雪峰,蔡勇,等.改进遗传算法求解焊位群完全遍历[J].机械与电子,2011(3):24-26.

[18]李开生,张慧慧,费仁元,等.具有遍历特性的移动机器人规划方法的研究[J].机器人,2001(6):486-492.

[19]郭小勤.未知环境下移动机器人遍历路径规划[J].计算机工程与设计,2010(1):172-174，202.

[20]李一波,张庆涛.室内未知环境遍历路径规划算法综述[J].计算机科学,2012(S3):334-338.

Research of complete coverage path planning of building 3D printing based on artificial intelligence★

Li Rongshuai

(EngineeringGeneralInstituteofShanghaiConstructionGroup,Shanghai201114，China)

Based on the system summary of 3D printing technology, artificial intelligence and development on the basis of path planning technology, research of complete coverage path planning of print head is firstly put forward in the field of building 3D printing, the necessity and urgency is analyzed. At the same time, build the mathematical model of the print head complete coverage path planning, put forward the evaluation of the print head complete coverage path planning performance evaluation indexes, finally, research direction of complete coverage path planning of building 3D printing based on artificial intelligent algorithm is prospected.

3D printing， building， artificial intelligence， complete coverage， path planning

1009-6825(2016)21-0256-03

2016-05-18★:上海市浦江人才计划资助(项目编号：15PJ1434200)

李荣帅(1983- )，男，博士，高级工程师

TP319

A