面向建筑作业3D打印的双机协作任务分配算法.pdf

第 35 卷 第 6 期 计算机辅助设计与图形学学报 Vol.35 No.6 2023 年 6 月 Journal of Computer-Aided Design&Computer Graphics Jun.2023 收稿日期:2021-11-10;修回日期:2022-03-25.基金项目:国家重点研发计划(2018YFB1306901);NSFC-深圳市联合基金(U1913603).王小龙(1989),男,博士研究生,主要研究方向为 3D 打印、建筑机器人;曹建福(1963),男,博士,教授,博士生导师,主要研究方向为数控装备控制与智能化、建筑机器人;曹晔(1992),女,博士,讲师,主要研究方向为机器人非线性控制.面向建筑作业 3D 打印的双机协作任务分配算法 王小龙1),曹建福1),曹晔1,2)1)(西安交通大学机械制造系统工程国家重点实验室 西安 710049)2)(星际(重庆)智能装备研究院 重庆 400030)()摘 要:建筑 3D 打印通常将对象模型做人工划分后交由多机并行工作,模型划分优劣直接影响打印效率和外观效果.为了提高分块质量,提出一种双机协作任务分配算法.首先依据待打印体支撑关系粗略分块,并由分块特征识别模型中支撑柱、短墙、装饰等不宜分割部位;然后以提高并行效率为目的建立分块几何聚集指标和任务均衡指标,并由此构建任务分配多目标优化模型;最后由求解所得的任务子集将原模型切割输出.所提算法针对双机协作模式,但可通过参数调整推广至多机协作.与常见几何均分、按墙体连接划分的分割实验结果对比表明,该算法可避免切割对特征的破坏,且分配任务不均衡度低,能够有效地提高建筑 3D 打印效率.关键词:3D 打印;任务分配;双机协作;STL 模型处理 中图法分类号:TP391.73 DOI:10.3724/SP.J.1089.2023.19462 Task Allocation Algorithm for Dual 3D Printing Devices Cooperation in Construction Industry Wang Xiaolong1),Cao Jianfu1),and Cao Ye1,2)1)(State Key Laboratory for Manufacturing Systems Engineering,Xian Jiaotong University,Xian 710049)2)(Star Institute of Intelligent System,Chongqing 400030)Abstract:Building 3D printing objects are usually divided manually in blocks and printed parallel.The model division directly affects the printing efficiency and overall appearance.In order to improve the dividing quality,a task allocation algorithm for dual devices cooperation is proposed.Firstly,the original model is roughly sliced according to its support relationship,and block features are identified to avoid dividing of support col-umns,short walls or decorations which are not fit for parting.Secondly,to improve printing efficiency,geo-metric aggregation index and task balance index are set,and a multi-objective optimization model of printing task allocation is established.Finally,based on the solution of optimization problem,the original model is cut into two STLs to output.The method focuses on dual devices pattern,but can extend for multi-devices from parameters adjustment.This paper compared the results of the proposed method with that of common geomet-ric equalization and partition by wall connection.It showed that this method is superior in task balance,which can promote the efficiency of building 3D printing,and the key features of original model are retained from dividing.Key words:3D printing;task allocation;dual devices cooperation;STL model processing 858 计算机辅助设计与图形学学报 第 35 卷 3D 打印又称增材制造,具有工艺简单、灵活快捷的特点.目前,该技术已日臻完善,在机械、医疗、食品等多个领域广泛应用,并逐步推广至建筑行业1-2.建筑 3D 打印利用普通 3D 打印中的沉积成型技术,使用改性混凝土、陶土、塑料等建材制造大型建筑构件,甚至实现整体建筑物的一体化成型建造3.典型的建筑 3D 打印实践有南加州大学的“轮廓工艺”4,Apis 公司 3D 打印的迪拜政府建筑5、清华大学的混凝土 3D 打印步行桥6等,这些案例提供了新的建筑设计和建造方法,为建筑业转型升级带来新的机遇.通常,建筑 3D 打印的目标具有尺寸大、支撑困难等典型特征7,不能简单地沿用普通 3D 打印方法.一般在设计时就需根据模型尺寸以及其构件上下层支撑关系进行人工分块8,随后分别对分块模型修补、分层和填充9,使用单台设备顺序打印或多台设备并行打印,最后使用结构固定材料组合或浇筑连接为最终建筑产品10.上述过程的核心是模型分块,但该过程存在以下局限:(1)设计上需反复进行,易出错.受施工现场条件限制,打印设备可能无法预先布置,模型分块可能与设备工作范围不适配,需反复修改设计.(2)施工上分块模型打印工作量不统一,总打印时间长.人工划分的各分块模型打印时间难以一致或具体把握,造成部分打印设备空闲,增加总打印时间,降低打印效率.为了应对上述问题,本文针对建筑并行打印模式,提出一种建筑 3D 打印的任务分配算法,通过对立体光刻(stereo lithography,STL)文件直接划分避免设计上反复试凑,提高分块模型在打印任务量上的一致性,从而提升效率,减少总打印时间;同时,避免在设计层面反复,可减少计算机辅助设计系统重复布尔、分层等操作,减少出错概率11.本文算法面向预制构件分割打印组装和现场并行打印 2 种模式,其中,预制构件分割打印组装模式涵盖桥梁、结构件、装饰块等,现场并行打印模式为大型屋宇的一体化打印.该算法基于普通3D 打印分割12,充分结合建筑构件特点,划分结果可保证分块任务量相对均衡,满足各台打印机工作范围约束,并可减少划分对模型关键特征的破坏;针对基本的双机协作模式设计同时预留了充分的扩展空间,通过参数调整可推广至一般的多设备协作模式.1 建筑 3D 打印分块模型 建筑体几何尺寸较大的特点决定了对其打印需分块进行,本节首先建立待打印体的分块模型,为后续任务分配奠定基础.1.1 并行打印模式 将大型建筑体或构件分块后,使用多台设备同时打印,将有效地提高整体建造速度13.对于一些跨度较大建筑(如 3D 打印桥梁),需对桥身做分段处理,以适应打印设备工作空间限制14,这种必要的分段为并行打印模式提供了自然的实现基础.建筑 3D 打印的并行模式如图 1 所示,按施工方式可分为预制构件分割打印并组装模式(图 1a)和建筑施工现场并行打印模式(图 1b).图 1 中,预制构件的分割打印模式采用分段方式打印,可规避单一设备工作范围不足的问题,同时若分段合理,则在多设备并行工作下可极大提高整体建造速度.该模式要求找到合适的构件分割线,但对分割接口则无需过多处理.图 1 建筑 3D 打印的并行模式 第 6 期 王小龙,等:面向建筑作业 3D 打印的双机协作任务分配算法 859 大型建筑施工现场的并行模式直接由多台打印设备联动工作.为了避免复杂的交互避碰规划问题,对 2 台打印机工作范围交错面进行划分,即垂直地将STL模型分割为2份文件,分别供打印设备 1 和打印设备 2 独立施工.交界处,为避免打印时连接部分造成干涉,在墙体分界处预留间隔,通过浇筑等手段完成连接.本节首先建立模型分块与打印任务量之间的对应关系,通过任务分配方式处理上述2种场景中的STL文件分割.显然,任务分配的合理性直接影响打印外观效果及总打印时间.1.2 分块模型表示 为实现任务分配算法,首先建立模型分块与任务量之间的关系.设集合 jT b表示待打印体STL 文件对应的总打印任务集合,其中,元素T,jjjxyb表示待打印体在几何上切分的任务子块,jx和jy分别表示任务子块在XY面(水平面)上的位置坐标.设 F T表示总任务量,则任务分配问题可描述为将T拆分为子集12,NT TT,使得拆分后各子集任务量满足 iF T,1,2,iN相对一致或符合给定的比例关系,以使并行工作总打印时间较短.任务子块jb与模型实体的划分对应,为避免分割线破坏模型原几何特征,任务子块的产生采用网格切分和复杂形体整体切分相结合的方式,以在灵活进行任务分配的同时保证支撑柱、装饰纹路等部位的完整.任务子块的2种切分模式如图 2 所示.图 2 任务子块的网格切分和整体切分 3D 打印使用的 STL 文件是待打印体表面三角形的集合,为将其转化为任务集合T,对其做切片和结构化处理,得到如图 3 所示的分块数据模型.其中,切片采用等厚分层算法,由水平面切割三角面片得到.记模型的所有切片组成集合为 lL,某片切片lL所含轮廓记为mlP,将轮廓表示为多边形顶点的集合,ml kv.得到切片数据后,基于各层轮廓的支撑关系将整体模型粗略划分为若干分块IB的集合,其中,I表示分块序号,B1,2,IN.将切片、轮廓等数据按该序号分别归入分块模型,并依据位置关系记录分块的下层基块序号bI和上层承载块序号uI.最后,根据块切片集IlL计算该块的网格化任务量矩阵IG,并依据块轮廓集ImlP确定的特征数目是否达到阈值计算块覆盖矩阵IC,以决定将分块IB作为整体任务子块jb或经过网格切分得到的任务子块集合 jb计入总任务集合T中.图 3 模型分块处理数据结构 1.3 模型分块方法 1.3.1 依支撑关系的模型分块结构 建筑体质量很大,为保证打印的柱、短墙等的可靠性,应避免任务分界线在其上通过;同时,由于建筑打印挤出材料较粗,更宜在打印体的底部基础部分做出划分,从而保持顶部装饰块的美观.本文依据模型支撑关系识别此类模型分块.待打印建筑体的几何形态决定了打印时支撑的复杂程度15,将分块类型简单归纳为基块和承载块2类.每个基块按负载关系可对应单个或若干承载块,依据这一关系将各分块组织为树形结构模型(如图 4 所示).分块IB在模型结构中的位置由其块序号I、基块序号bI和承载块序号uI共同确定,若分块是基块,则其基块序号bI记为 0.860 计算机辅助设计与图形学学报 第 35 卷 图 4 基于支撑关系的模型分块 上述分块方法与体素构造法类似,但分块体现的是模型的承载关系,以便随后将分块IB划分为更具体的任务子块jb.1.3.2 同层切片数据整理 为识别并区分模型分块,将切片数据集 lL整理为IlL,数据整理的依据是切片内轮廓的包含关系,如图 5 所示.图 5 同层轮廓包含关系处理 建筑 3D 打印挤出材料较宽,构件尺寸较大,其切片上的轮廓只存在包含或不包含2种关系,将互不包含的轮廓划分为不同的块切片数据;而对于存在包含关系的轮廓,则根据包含其轮廓的数目判定为几何体内部轮廓(孔洞)或外部轮廓16.具体做法为两两判断轮廓1mlP和2mlP的包含关系,将包含者作为父节点,被包含者作为子节点,按照块切片最多含有 1 条外部轮廓和若干互不包含的内部轮廓组织整理.1.3.3 上下层切片承载关系处理 对于某分块IB的第l层切片IlL和1l 层切片1IlL,将切片轮廓投影至XY平面后,所得单条轮廓线存在包含、不包含和相交 3 种情况.其中,相交又可分为重叠、单点相交和多点相交等情况.严格的上下层承载关系为轮廓重叠,但在实际 3D 打印中允许上层轮廓超出下层一定范围,在满足材料支撑的情况下实现曲面的打印17.为判断实际打印中上下层切片的支撑关系,对于下层切片IlL中的某条轮廓ImlP,将其向外扩张得到扩大的偏置轮廓ex,ImlP,向内收缩得到缩小偏置轮廓re,ImlP.具体的轮廓偏置通过轮廓线段依正反法线方向平移实现,如图 6 所示.图 6 轮廓的扩张与收缩偏置处理 若某轮廓对应的上层切片轮廓1ImlP被包夹在ex,ImlP和re,ImlP之间,则认为该 2 层切片轮廓具有完全的支撑关系,将其划分至同一分块IB中;否则,根据具体情况新建承载块或基块,如图 7 所示.图 7 上下层切片承载关系分类 第 6 期 王小龙,等:面向建筑作业 3D 打印的双机协作任务分配算法 861 若上下层切片完全支撑,则将1l 层切片归入分块IB中;若上层切片超出下层切片支撑范围,即超出支撑的情形,则新建基块1IB,并将1l 层切片归入新建分块;而对于部分支撑情形,则建立新的承载块1IB并将1l 层切片归入该分块.在对 STL 文件进行切片的过程中,重复进行块切片数据整理和承载关系判断,即可由原始输入得到初步的模型分块结果.1.4 任务子块建立和任务量估算 在将 STL 模型转化为分块模型集IB后,为得到任务划分所需的总任务集T,需针对每一分块IB,决定将其进一步切分为网格任务子块jb或作为整体任务子块加入任务集合T.1.4.1 任务子块类型判定 为了避免任务分割线经过特征较多的形体部分(如柱体、复杂装饰块等),将分块轮廓的特征数目和投影面积之比作为度量值,在未达到预定阈值c时将其网格化切分.采用弦长比尖点检测法18计算轮廓特征值,即 1111kkkkkkkvvvvv v(1)其中,ijv v表示 2 个点iv与jv间的长度;kv表示块轮廓ImlP中的具体顶点,Iml kv.当k达到尖点判定值时记录点kv为一个特征点.计算分块IB中的特征点密度为 LL11=IINNIIIllllnSL(2)其中,Iln表示分块IB第l层切片的特征点个数,LIN表示该分块的切片数量,IlSL表示第l层切片的面积.若计算结果大于判定值,即cI时,将分块IB作为整体任务子块加入任务集合T;否则,对其做网格划分后,将得到的网格任务子块集合加入总任务集合.1.4.2 任务子块工作量计算 3D 打印的工作量集中体现在打印头按规划路径运动并挤出打印材料上,其路径规划包括轮廓填充和内部填充 2 类.对于建筑 3D 打印,其外轮廓通常为单层或用轮廓偏置法打印数层,而内轮廓常用分形几何法按围成面积的一定比例填充.本文根据分块切片的轮廓穿过网格长度,及其所包围网格的面积计算该网格任务子块的打印工作量,在计算时根据实际模型内部填充比进行调节.设某网格切分的任务子块jb对应中心坐标为,jjxy,边长为d的正方形,则其任务量计算公式为 LL,11NNjl jl jllFESb(3)其中,表示调节系数;表示内部填充比,可根据实际选择的填充算法仿真得到;,l jE表示分块的第l层轮廓被网格正方形截取的长度;,l jS表示该层轮廓被网格截取的面积.网格化任务子块的任务量计算如图 8 所示.图 8 网格化任务子块的任务量计算 网格任务子块jb在几何上与水平面中点集,jjxy对应,给定正方形边长和整体模型起始坐标后将其写为矩阵形式,即得到块网格化任务量矩阵IG.对于整体纳入任务集合T的整体任务子块jb,同样按照上述方法计算jF b,但不再将其分解为网格任务子块;同时,为了在XY平面上区分这2种任务子块,将整体任务子块所占范围按类似方法表示为块覆盖矩阵IC,该矩阵中用 1 表示整体任务子块所占位置.2 双机协作任务分配 在得到任务集合T的基础上建立了双机任务分配模型,并设计求解算法将其划分为2个任务量均衡的子集,完成任务分配.2.1 任务分配优化模型 双机任务分配是在第 1 节所得 3D 打印分块模型的基础上,将任务集合T分为子集1T和2T,即决定1jTb或2jTb(1,2,jM),最后将2子集分别逆向映射为 STL 文件输出.建筑 3D 打印目标物体体积较大,打印时间较长,且打印设备拆装费工费时,因此本文在任务划分时设置 2 个分配目标:(1)双机任务量均衡.对于 2 台相同的打印设备,所分配的任务量 1F T和2F T应尽可能相等.862 计算机辅助设计与图形学学报 第 35 卷 对打印能力不同的2台设备,其所分配任务量应与设备能力成正比,以减少单台设备的空闲时间.(2)打印任务子块在几何上聚集.任务子集1T和2T所代表的几何体在XY平面上的投影图形是连通的,且投影图形最大尺寸尽量小,以便将打印工作量集中在设备最佳工作范围内.设任务子块jb在计算上表示其对应几何体中心位置坐标的列向量.设ja表示jb对1T或2T的从属,其中1,2,jM,若1jTb,则规定1ja;否则,2jTb且规定1ja ,并设下标集1|1jAj a及2|1jAj a.则任务分配的任务量均衡指标可表示为 12equ12jjj Aj AIFFbb(4)其中,1和2为任务量比例系数,在打印设备相同时这 2 个系数相等.几何聚集性指标可表示为 1122agg112211 jjjj Aj Ajjjj Aj AIFMFMbbbpbbbp(5)其中,1M与2M分别表示任务集合1A与2A中的元素个数;1p与2p表示 2 台打印设备位置坐标列向量,若无法事先确定均取零向量;表示调节系数;表示向量的模运算.则双机任务分配的优化模型可表示为多目标规划问题 objequaggmin ,fII(6)12s.t.jjj Aj AaaM(7),jkkjkrTbpb(8)其中,k取1或2,表示2台打印机;kr表示打印机k的最大工作半径;其他符号同前所述.优化问题中,约束条件式(7)确保总任务集合T被完全划分为1T和2T这2 个子集,即12TTT,且任意一个任务子块jb仅被包含在其中一个子集中.约束条件式(8)确保划分的任务在打印设备工作范围内,对于最大打印范围为矩形的设备,则通过限定T,jjjxyb的坐标范围加以约束,即对 jkTb,设定min,max,kjkXxX和min,max,kjkYyY.2.2 模型求解 2.2.1 模型简化 式(6)中,决策变量1,1ja 为离散形式,且优化目标equI和aggI直接用决策变量表示后的目标函数形式复杂,不宜直接求解.为此,本文通过将部分优化目标转化为约束条件的方法实现该优化问题的简化19.忽略打印设备工作范围约束.在实际问题中,若不回避在特征处分界,则总可以找到一条分界线,使得划分后的 2 个 STL 模型的打印任务量相等.因此在任务子块jb被划分得足够细时,指标equI可趋近于零.事实上,从指标1j 开始,按如下迭代规则对jb分配(对ja赋值)1212,1,if 1,otherwiseiiij i Aij i AjFFabb(9)则第j次分配前均衡指标值1equjI与分配后的值 equjI满足关系 1equequ*jjjIIFb(10)其中,*根据ja赋值结果取1或2.由式(9)可知,首次划分时,1equm1maxjjMIFb.其中,m12max,.再将式(10)放缩得到 11equequmeqummax,jjjjjIIFIFbb 则 有 21equequmm1max,maxjjjMIIFFbb;于是取1,2,jM,重复上述过程,可得 equjI m1maxjjMF b.令jM,则有 equequm1maxMjjMIIFb (11)由此可见,当任务子块被划分得足够小时,均衡指标也将趋于 0.但在实际中无需做如此细小的划分,考虑回避在特征处的划分,根据式(11)可将equI的最大值设定为约束条件,将多目标优化问题式(6)转化为单目标约束问题,即 objaggmin fI(12)12s.t.jjj Aj AaaM(13)equI(14)第 6 期 王小龙,等:面向建筑作业 3D 打印的双机协作任务分配算法 863 其中,约束条件式(13)确保任务分配的唯一性,约束条件式(14)中为依据m1maxjjMFb 设定的任务量不均衡度最大允许值.在考虑打印机工作范围约束时,设1jRb和2jRb表示任务子块处于打印机 1 和打印机 2 的工作范围内,设112|jjjTRRbbb,和2T 21|jjjRR,bbb表示任务子块的集合,则显然应有11TT以及22TT.设12TTTT,则T内元素均满足上述忽略打印范围约束的情况,可按模型式(12)实现分配.记12FF TF TF T,当 满 足0F时,2 台打印设备交叠部分任务量T可弥补因范围约束造成的不均衡,因此用T替代T作为式(12)的总任务量输入.若0F,此时aggI至少为F,可在模型中取不均衡度最大允许值mmax max,jjTFFbb.2.2.2 迭代求解 式(12)简化了目标函数,但约束条件变得更加复杂,解析求解仍然困难.由于第 2.2.1 节中迭代规则式(9)保证了约束条件的满足性,因此可利用迭 代 算 法,按 照aggI减 小 方 向 调 整 决 策 变 量1,1ja 的取值,直至式(12)的优化目标达到最小或者局部最小.按 照 式(9)进 行 首 次 任 务 划 分 后,若 此 时1122F TF T(即1212jjj Aj AFFbb),则在1A中寻找某一下标*j,满足 1T*121argmaxjjj AjFbbccc(15)其中,1111jj AMcbp,2222jj AMcbp.改变*jb的从属,即令*1ja(使得*2jTb),忽略1c,2c的微小改变,则近似有 *aggagg12jjjIIFbbcbc(16)其中,aggI表示该次修正后聚集性指标的更新值.此时,若选取*jb使得*12jjbcbc,则由式(16)可得aggaggII,即实现了通过调整减小优化目标值的目的.类似地,对于1122F TF T的情况,可在2A中寻找某一下标*j,使得 2T*212argmaxjjj AjFbbccc(17)并改变*jb的从属,即令*1ja(使得*1jTb).对于上述解法,应当注意运用了计算上的近似,并且加强了*j应满足的条件.其中,迭代初始阶段任务子块分布较为随机,按距离最大化求取的*jb对1c与2c影响较大;而在迭代结束阶段,2个任务集的聚集性较高,求取的*jb处于其交界位置,可能不满足加强条件.为了简化对其讨论,忽略前M次迭代,后续迭代中按式(15)或式(17)得到*j并修正后,重新利用定义式(5)计算修正后指标 值aggI,与 修 正 前 值aggI作 比 较,若 满 足aggaggII,接受本次调整;否则,结束调整过程,输出结果.2.3 双机任务分配算法 综上所述,任务分配算法分为 STL 文件模型分块处理和双机任务分配 2 步.算法 1.STL 文件分块模型化.输入.STL 文件.输出.任务集合T.Step1.读入待打印体 STL 文件,通过等厚分层获得切片集 iL.Step2.遍历切片集 iL,对每层切片执行同层块切片整理和上下层切片承载关系判断,得到分块模型数据集IB.Step3.按式(1)计算分块特征点,并由式(2)判断任务子块类型,根据类型计算块覆盖矩阵IC.Step4.按式(3)计算任务量网格化矩阵IG.Step5.由IC和IG得jb 几何中心和任务量jF b,并将jb 作为元素加入任务集合T,直至所有任务子块分配完毕.算法 2.双机协作任务划分算法.输入.任务集合T.输出.STL1,STL2 文件.Step1.根据打印设备工作范围约束,由任务集合T计算出可分配集合T,设置,并按式(9)对任务集T进行初步划分.Step2.若 1122F TF T,按式(15)得到*j,并令*2jbT;否则,按式(17)计算*j,并令*1jbT.Step3.若迭代次数小于M,转 Step2;否则,按式(5)计算修正指标值aggI.若满足aggaggII,则接受修正,并在达到最大迭代次数前转 Step2 循环运行;否则,864 计算机辅助设计与图形学学报 第 35 卷 丢弃修正结果,执行下一步.Step4.将得到的任务子集1T和2T按其子块的覆盖矩阵IC指示的几何坐标计算几何分界线,将 STL 模型据该分界线切分为 STL1 和 STL2 文件输出.2.4 多机协作任务分配 以双机协作的任务分配为目标,本文设计模型及其求解算法均以双机为基本假设,不能直接扩展至多机协作场景.但式(4)的设计允许 2 个任务子集的任务量 1F T和2F T按照参数2和1的比例进行配置,为本文算法扩展至多机的任务划分奠定了基础.对于将任务集合T划分为多个子集12,NT TT的情况,首先将集合T按双机任务分配模式划分为子集112NTTT和1NNTT这 2 个子集;然后重复对每个子集做上述二分解,由于任务量比例1和2可设定,则最终可得到N个分解后的子集;最后依据划分后子集对应的几何块将 STL 文件分割输出,以提供多台打印设备实现并行工作.3 实验结果和讨论 分别选用复杂建筑构件和大型整体建筑 2 种模型作为待测输入,对本文算法进行实验.图 9 和图 10 所示为带纹路装饰的建筑构件的任务划分过程及结果,分别对应算法 1 和算法 2 的运行过程.其中,图 9a 和图 9b 分别为待打印体及其 STL 模型,经过切片分层、同层切片整理和上下层承载关系处理后,得到如图 9c 所示的分块模型1B7B.对分块模型进一步计算图 9d 所示覆盖矩阵及图 9e 所示总任务量矩阵,并据此得到任务集合T.本例中得到的任务集合T共包含10 883M 个任务子块jb,任务量计算式(3)中选取参数=5,=1.图 9f 所示为依据打印机工作范围对任务子块做出的预分配.图 10a所示为迭代求解算法的计算过程,可以看出,随着迭代的进行,2 个任务子集所含任务子块由初始较为随机的分布逐步聚集,最终在满足截止条件时将构件划分为满足任务量均衡约束的2 部分(最终结果的任务量均衡指标值 Iequ为 0.056,式(14)中设置约束阈值139.059,该模型的总任 图 9 建筑构件 STL 文件分块模型化过程 图 10 建筑构件任务划分过程 注.M为任务集合T中子块的个数 第 6 期 王小龙,等:面向建筑作业 3D 打印的双机协作任务分配算法 865 务量()388 170F T).求解后2个任务子集1T和2T在几何上的交界线将原构件划分为 2 个 STL 模型(如图 10b 所示),且分割线不穿过特征较多的星形花纹部分,避免了该部分打印后拼接时造成的特征损失.本例中输入的是建筑构件 STL 文件,输出的是可直接提供 2 台打印机使用的 STL1 和 STL2 文件,避免了设计和施工阶段的重复人工分割.同时,划分结果保障了双机任务量均衡和任务子块几何上聚集的要求,在一定程度上提高了整体打印效率.图 11 所示为整体建筑模型的任务划分情况,该算例整体尺寸较大,但模型纹理复杂度较低.图11c 所示为按算法 1 分块后的分块模型,每个分块通过不同颜色进行区分,与建筑构件不同,由这种整体建筑模型得到的分块尺寸大、特征少,算法将其作为网格任务子块加入任务集T.图 11d 所示为算法 2 的划分结果,最终由该划分将模型分割为 2个 STL 文件输出,如图 11e 所示.图 11 整体建筑的任务划分 优化目标值在迭代过程中的变化如图12所示,可以看出,算法 2 实现了优化模型的求解,并在满足截止条件时算法实际上已收敛至最优或局部最优值(如图 12 中蓝色虚线所示,该虚线是在取消截止条件后继续运行产生的迭代趋势,实线是算法正常迭代过程).由于带装饰纹路的建筑构件存在较多整体任务子块,其调整过程对指标参数浮动影响较大,因此优化目标的调整曲线较建筑构件指标迭代曲线平滑.图 12 中,聚集性指标归一值指聚集性指标与其迭代中最大值的比值,迭代步数归一值指迭代步数与任务子块数的比值.相对于本文算法,传统分块方式需根据打印体的材料、轮廓、结构特性进行人工划分14.在传统分块方式下,因本例模型横向、纵向尺寸相近,可采取2个方向均分或考虑在墙体交界处划分,得到的划分结果如图 13 所示.图 12 迭代过程优化目标值变化曲线 a.横向均分 b.横向墙体分割 c.纵向均分 d.纵向墙体分割 图 13 4 种人工划分结果(以任务量表示)图 13 中,人工划分与本文算法划分结果对比如表 1 所示.可以看出,无论聚集指标aggI还是任务量均衡指标equI,本文算法均优于常见人工分割方式;同时,人工划分具有很强的主观性,其划分结果的优劣有较强的偶然性.表 1 本文算法与人工划分结果对比 任务划分算法图号aggagg1II/%equIF T/%本文 11d 100.00 0.00 横向均分 13a 100.57 2.37 横向墙体分割13b 100.67 3.02 纵向均分 13c 114.23 14.40 纵向墙体分割13d 112.08 4.44 注.为便于对比,聚集性指标与本文算法结果值agg1I对比.以上2个算例验证了本文算法在2类典型建筑3D 打印作业(建筑构件和整体结构打印)任务分配中的有效性,其中,2 台打印机可交叠工作范围较大,使得分配后任务量达到均衡.为了验证算法对打印机工作范围约束的满足性,本文设计了较为狭长的待打印模型算例,其受范围限制的算法划分情况如图 14 所示.本例中,2 台打印机在待打印模型上的可交叠打印区域较小(图 14a),图 14b 所示为不考虑范围约束的划分结果,此时虽然得到均衡的划分效果(不均衡度为 0%),但方案实际不可行.考虑工作范围的完整算法结果如图 14c 所示,可以看出,其划分结果满足打印机的范围约束,但此时划分结果的不均衡程度为总任务量的866 计算机辅助设计与图形学学报 第 35 卷 29.41%.事实上,随着 2 台打印机交叠范围的逐步减小,为满足工作范围约束条件,本文算法将逐步退化为完全依据打印设备工作范围的划分,这也符合实际问题的需要.图 14 打印范围约束对任务划分的影响 4 结 语 建筑 3D 打印的分块并行工作是提高其效率的关键技术,本文的核心是将待打印建筑 STL 模型划分为任务量均衡的子模型,以便打印设备并行联动工作,提高建造效率.本文算法是在传统 3D 打印基础上针对建筑3D 打印特点所做的改进,针对建筑体支撑关系对整体打印模型进行初步分块处理,避免了分割线穿过支撑柱体、短墙或装饰造型等支撑部件或复杂纹理;在任务划分过程中建立几何聚集性指标和任务量均衡性指标,并在考虑打印设备工作范围约束下建立了任务分配优化模型;最后使用迭代算法递推求解后得到分割后的子模型文件.本文算法针对双机协作的任务分配设计,但同时讨论了扩展到多机协作场景中的方法.针对2种并行打印模式的实验结果表明,本文提出的任务分配算法是可行的,验证了迭代算法对优化模型求解的有效性;所得划分结果不破坏原模型特征密集区域,符合实际打印设备范围约束;经与人工划分对比,本文算法的结果具有较优的指标值,可有效地提高建筑 3D 打印的并行工作效率,具有实际应用价值.本文算法还存在改进空间,例如,针对整体建筑打印模式下分割处的接缝问题,可通过本文算法进行无缝整体分割,并在连接处考虑切片层级任务均衡的打印规划;向多机并行打印拓展时,可针对不同性能的打印机讨论设备的布置和规划问题,以发展和完善任务分配算法,进一步提高 3D打印建造效率.参考文献(References):1 Tay Y W D,Panda B,Paul S C,et al.3D printing trends in building and construction industry:a reviewJ.Virtual and Physical Prototyping,2017,12(3):261-276 2 Zhang Y,Lu H Q,Chen H W,et al.Application design of 3D printing technology in the field of architectureC/Proceedings of the Chinese Control and Decision Conference.Los Alamitos:IEEE Computer Society Press,2019:3511-3515 3 Paolini A,Kollmannsberger S,Rank E.Additive manufacturing in construction:a review on processes,applications,and digital planning methodsJ.Additive Manufacturing,2019,30:Article No.100894 4 Khoshnevis B,Hwang D,Yao K T,et al.Mega-scale fabrica-tion by contour craftingJ.International Journal of Industrial and Systems Engineering,2006,1(3):301-320 5 Pessoa S,Guimares A S,Lucas S S,et al.3D printing in the construction industry-a systematic review of the thermal per-formance in buildingsJ.Renewable and Sustainable Energy Reviews,2021,141:Article No.110794 6 Siddika A,Mamun M A A,Ferdous W,et al.3D-printed con-crete:applications,performance,and challengesJ.Journal of Sustainable Cement-Based Materials,2020,9(3):127-164 7 Vaitov M,Jendele L,ervenka J.3D printing of concrete structures modelled by FEMJ.Solid State Phenomena,2020,309:261-266 8 Wu P,Wang J,Wang X Y.A critical review of the use of 3-D printing in the construction industryJ.Automation in Con-struction,2016,68:21-31 9 Sakin M,Kiroglu Y C.3D printing of buildings:construction of the sustainable houses