轮廓加工可以通过反复地将建筑材料分层下来，自动构建定制设计的结构。轮廓加工（CC）是一种增材制造技术，它使用计算机控制来利用镘工的卓越表面成型能力，以便从挤出的材料中创造出平滑和精确的平面和自由形状的表面。CC的一些重要方面是较低的建筑成本、卓越的施工速度、建筑设计的灵活性、安全性和对环境的友好性。在过去的几年里，已经进行了广泛的实验，以配置CC工艺来生产各种小型和全尺寸的物体。
具有方形、凸形和凹形曲线特征的中小型2.5D和3D部件已经用各种热塑性材料和陶瓷材料制造出来，如图所示。
更大的轮廓加工机器，已经被开发出来用于建造更大的结构。这些机器将形成物体表面的挤压过程和建立物体核心的填充过程（通过浇注或挤压）结合在一起。
使用CC机器已经建造了几个墙体样本，可以生产具有波纹状内部结构的空心墙。这种设计有望成为混凝土墙体建设的良好初始候选方案，因为它在某种程度上等同于在各种建筑应用中被广泛使用。CC机器重量轻，可以由一个小团队快速组装、拆卸和运输。施工操作可以完全自动化，只需要最少的监督。
轮廓加工中的流程和优化分析操作规划和优化在提高CC系统的整体效率方面起着重要作用，它为给定的结构设计生成最佳的喷嘴/风口路径。多喷嘴或多龙门系统适用于建造大型社区和多住宅结构，以减少施工时间和成本。本研究中考虑了两种类型的多机CC系统：悬挂式多喷嘴和多龙门式。在这两种情况下，具体的时间表和工作量将被分配给各个喷嘴或龙门架进行协同作业。应避免喷嘴之间的碰撞，以免严重影响整体施工效率。
报告的工作旨在通过以下步骤，开发和验证一种系统的工艺规划和优化方法，以便在单机和多机情况下，通过轮廓加工最有效地建造复杂的大型结构：1、描述系统特征并定义轮廓加工的工具路径要素；2、为单喷嘴CC系统开发实用的工具路径规划和优化方法；3、在单喷嘴情况下的优化方法基础上，为多喷嘴系统开发实用的工具路径规划和优化方法。
如果考虑到技术的所有方面，优化问题的规模可能太大。应该根据系统的限制和特点来确定操作事实。以下是该系统的操作事实：
1、这里的重点是寻找2.5D结构的最佳工具路径。各层之间是相似的，除了门窗的开口点。一般来说，喷嘴将尝试在每层的同一地点开始和结束。
2、在施工过程中，一个或多个喷嘴必须完全完成一个层，然后再进入下一个层。
3、对于每一层，CC喷嘴在开始新的墙段之前必须完全完成一个墙段的沉积，这样它就只能在每个墙段的端点之间移动。
4、为了避免喷嘴和先前沉积的墙体之间的碰撞，喷嘴在端点之间行驶时应被抬起（至少一个层高）。
5、喷嘴在穿越有门窗的地方时将处于空闲状态。这种穿越时间被称为“空气时间”。
6、沉积流速可以在任何时候得到完美控制（即混凝土流可以开始和停止）。
7、在优化分析中，系统的加速和减速时间被认为是固定延迟。
8、重点是开发一种实用的优化方法来生成一般结构的工具路径。一个结构布局中的最大顶点数量将小于10,000，这允许处理相当大和复杂的结构。
9、在多喷嘴的情况下，喷嘴总是在同一层上工作。假设允许喷嘴同时在不同的层上工作，不会提高系统的效率。
一旦定义了工具路径，就可以对其进行评估。建筑模型首先被切成几层，然后将单层的布局转换成由边和顶点组成的模型。边代表墙，顶点代表墙段的交叉点、角或端点。
图中展示了所示结构的轮廓加工工具路径的一个样本。一个特定结构的轮廓加工的工具路径必须描述喷嘴在整个施工期间的位置、方向、速度和沉积率。这些信息被转换为机器任务序列，然后输入到轮廓加工机器中。如果在每个机器任务（如沉积、喷嘴移动或喷嘴旋转）上花费的时间或能量被定义为施工成本，那么过程优化意味着找到一个与每个机器任务相关的总成本最小的路径。因此，为了计算与工具路径相关的总成本，需要定义沉积、移动和旋转的成本。
沉积的成本取决于沉积的流速和机器的速度。然而，由于喷嘴必须沿着所有的沉积边缘穿越一次，而且只有一次，一旦给出一个结构，整个沉积时间是固定的。因此，沉积的成本并不影响工具路径优化的结果。一旦机器参数已定义，每个墙段的沉积成本可以根据其几何信息进行计算。边缘之间的移动成本与顶点之间的移动成本和沿边缘的旋转成本有关。这个成本可以根据边的相关位置来估计。
每条边有两个端点，因此，从一条边到另一条边总共有四个可能的旅行成本。由于轮廓加工机器的喷嘴必须确定自己的方向，以便与墙段的切线垂直，喷嘴在边缘之间移动时可能需要重新确定方向。例如，为了建造一个角，喷嘴必须在两个墙段的建造之间旋转90°。
图中显示了一个正在建造的墙角的俯视图。图中显示了建造墙角的四种可能方案。在左上角的选项中，喷嘴首先建造一个墙段，同时向墙角移动。在拐角处，喷嘴转了一个90°，然后完成另一个墙段。在右上角的选项中，喷嘴从墙角开始，建造一个墙段，在旋转90°的同时斜向移动到另一个墙段的起点，并在向墙角移动的同时建造该墙段。在下图中左侧方案中，喷嘴在向拐角方向移动时开始建造一个墙段，然后在旋转90°时到达另一个墙段的起点，在向拐角方向移动时开始建造该墙段。在右下角的选项中，喷嘴从墙角开始，在远离墙角的同时建造一个墙段，然后在旋转90°的同时回到墙角，然后在远离墙角的同时建造另一个墙段。为了选择最佳的工具路径方案，必须计算行走的成本、移动的成本（欧几里得距离）和旋转的成本。
一旦知道两点之间的距离和机器的速度，就可以确定在端点之间移动的成本。有时，为了避开障碍物，如先前沉积的墙段，喷嘴必须被抬起和放下。在这种情况下，抬起和放下的成本也需要包括在移动成本中。边缘之间的旋转成本可以根据两个边缘的相对方向进行评估。然而，喷嘴的旋转程度是有限的，因为在实际系统中，有电缆和电线连接到喷嘴，以传递信号和动力来移动喷嘴部件（镘工、阀门、振动器等）。
图中显示了实际的CC喷头和喷头旋转机构。如果允许喷嘴无限制地旋转，电缆和电线可能会纠缠在一起并被损坏。出于这个原因，在旋转接头上安装了一个机械止动器，以防止喷嘴的旋转。在任何方向旋转超过360°。如果止动器影响了喷嘴在特定方向上的重新定位过渡，则需要调整喷嘴的旋转方向和旋转程度。因此，旋转的成本不仅取决于旋转的程度，还取决于旋转联盟上挡板的起点和终点位置。
图中显示了旋转度和旋转联合体上的塞子位置之间的关系。在顺时针和逆时针方向上旋转相同度数的成本可能不同，这是因为挡板对旋转联盟的限制。为了找到旋转成本，需要考虑喷嘴的开始和结束方向。任意度的旋转成本可以根据挡板的相对起始和结束位置来计算。一旦知道两条边的欧几里得距离和方向，就可以通过计算移动和旋转所花的时间来估计两点之间的旅行成本。如果允许喷嘴在从一个点到另一个点的过程中旋转，那么旅行成本就会增加。两条边之间的成本将等于移动或旋转时间的最大值，否则它将是两个成本的总和。
除了喷嘴沉积和旅行的成本，在整个建造过程中还需要考虑以下物理限制：
1、喷嘴空闲时间不能太长，否则混凝土可能凝固。喷嘴的空闲时间成本等于在两个墙段之间旅行的成本。因此，如果在任何墙段之间旅行的成本都短于喷嘴中的混凝土凝固所需的时间，这个约束的要求就得到了满足。
2、下层必须能够支持上层，因此沉积后续层的时间间隔不能短于临界极限。
3、后续层必须能够粘附，因此，沉积后续层之间的间隔不应超过标准限制。约束条件2和3都与沉积后续层的时间间隔有关。这个时间间隔等于构建一个层的总时间，一旦生成了该层的工具路径就可以计算出来。如果生成的时间短于约束条件2中要求的时间间隔，机器必须在沉积下一层之前等待。如果这个时间比约束条件3中要求的时间间隔长，那么这表明该结构太大，一个喷嘴无法建造，因此需要更多的喷嘴或门架来建造。
4、当图层累积时，下面的图层必须凝固到足以支持上面多个图层的整体重量。一层的整体重量与它上面的层数成正比。因此，它与构建一个层的整体时间成正比。一旦计算出每层的施工时间，就可以用显示上层重量和施工时间之间关系的图表来验证这一约束。
5、喷嘴在行进时不应与先前的沉积层发生碰撞。有其他方法可以避免喷嘴与先前沉积的墙段之间的碰撞。当在墙段的端点之间移动时，喷头为了避开障碍物，可能必须以非直线方式行驶。
然而，尽管喷嘴可以绕行以避开墙段，但其路径取决于结构布局和施工顺序。在某些情况下，绕道可能很复杂，并可能需要太多的行驶时间。因为在本研究中，假设一个喷嘴在开始另一层之前必须完成一层，所以一旦喷嘴到达一个障碍物（前一个墙段）站在其行进路径上，它可以被提升一层。在开始沉积新墙段的材料之前，它将被放下来。在工具路径规划中，已经考虑到了提升和降低喷嘴的成本。
单喷嘴系统的最佳工具路径一旦不同机器任务的成本和物理约束的成本，可以进行优化，以找到最合适的方案。单喷嘴系统的有效工具路径。工具路径优化是其他一些技术的关键问题，如层状物体制造（LOM）、激光切割和其他分层制造。在这项研究中，寻找最佳工具路径的方法是将CC路径模型转换为标准的TSP。这种方法考虑了所有可能的施工方案，如果TSP模型得到精确的解决，就能提供最佳的解决方案。启发式TSP求解器可用于解决大规模的问题（例如，结构有超过10,000个墙段）。TSP试图找到最短的路线，至少访问一个城市集合并返回到起始城市。在标准的TSP概率中，顶点代表城市，而弧是城市之间的路径。TSP的解决方案必须返回代表城市和路径的最便宜的汉密尔顿循环。
汉密尔顿循环是图形中包含每个顶点的简单路径。一个不对称的TSP问题可以被表述如下：如果边（i,j）在最佳旅游中，定义Xiy=1（当ij是顶点的索引时）；否则Xiy=0，Dij-=d(ij)，当d是顶点i和j之间的旅行费用：
建筑布局图不能直接表述为一个标准的TSP问题。在CC施工过程中，图中的一些边必须由喷嘴穿过，以便为建筑墙体注入混凝土，这意味着CC工具路径必须包含一些特定的边。然而，任何边都可以包括在TSP的最优路径中，因为任何边都代表两个城市之间的路径。另外，结构布局中的一个顶点可能有几条边与之相连，这意味着在施工过程中，CC机器的喷嘴会多次访问同一个顶点。
然而，在TSP中，每个顶点只能被访问一次。对于轮廓加工，一个特定结构的整体施工时间是混凝土沉积的整体时间和喷嘴的整体空气时间的总和，其中喷嘴停止沉积材料，在两个沉积边缘之间移动。无论如何产生最佳路径，喷嘴都应该穿越所有沉积边缘一次，而且只有一次。一旦给定了结构，整个沉积时间就确定了。整体的喷嘴空闲时间是决定不同工具路径的整体施工时间的因素。最佳工具路径是具有最小的整体喷嘴空闲时间的路径。由于机器的喷嘴可以在三维空间自由移动，它可以在任何顶点之间直行。
该问题寻找最佳工具路径的方法可以表述如下：给出布局上的一组边，找到最佳的顺序和方向，其中：(1)每条边正好被穿越一次，(2)行驶的空中时间（两条边的两端点之间的运动）是一条直线。最佳方案是使整个空中时间最小化。制定该问题的方法是忽略沉积边缘（墙），而只考虑边缘之间的行进路径（喷嘴的空气时间）。在这种情况下，墙壁缩小为顶点（实体），此时顶点之间的路径代表了在墙壁之间旅行的成本。
图中显示了这种方法背后的概念。由于每条边有两个顶点，把边缩成一个点的方法将有四种可能性从一条边走到另一条边。正如上一节所定义的，从一个墙段到另一个墙段的旅行成本取决于移动和旋转喷嘴的时间。旋转的成本取决于两个边缘的位置、行进顺序和旋转联合体上挡板的起始位置。即使旋转程度相同，相反方向的旋转成本也可能不同。因此，在进行优化之前不能确定旋转的成本。为了将该问题表述为TSP，需要做一些修改。
在各种自动化系统中都采用了多机配置，如汽车的机器人组装。许多机器系统成功的核心是通过实施系统的任务分配和协调机制，对各个自动化机器（如机器人）的活动进行无冲突和有效的协调。任务分配机制解决了哪个机器执行哪个任务的问题。协调机制使每台机器执行的行动能够考虑到其他机器连贯的行动。最近对多机器系统的研究也涉及到各种方法，如潜力和联盟形成，这些方法将多台机器组织成临时子群，以完成指定的任务，否则就无法完成。
多机器轮廓加工系统可用于建造多个较小的结构或一个大型复杂结构，以减少整个施工时间。使用更多的机器意味着节省更多的时间和成本。此外，目前的CC系统是安装在轨道上的，以确保施工精度，允许多台机器在同一对轨道上合作也可以降低安装成本。有两种多机器的轮廓加工系统：高架多喷嘴和多龙门。
高架多龙门系统有一个高架平台作为几个喷嘴的载体。喷嘴的运动受到高架结构的限制。架空结构中承载喷嘴的门架不能相互交叉。整个高架结构必须上下移动，以便喷嘴建造不同的层。多门架系统比高架多喷嘴系统更灵活。它由不同的门架组成，可以独立操作。不同的喷嘴在不同的在不同的层面上，门架可以同时工作。这两种系统都有其优点和缺点。多门架系统可用于大多数建筑应用。建筑项目中使用的龙门架数量取决于工作量和期望的完成时间。许多龙门架可以合作完成一个大型建筑项目，但几台龙门架甚至一台就可以处理小型项目。尽管高架桥系统不像多门架系统那样灵活（由于配置固定），但它可能会节省更多的能源。对于高架系统，应该对每一层进行工具路径规划和优化，因为高架结构承载的所有喷嘴都在同一高度运行。
然而，在多龙门系统的情况下，工具路径规划和优化可以对在不同高度上同时建造的层进行。然而，在本文提出的方法中，假定所有的喷嘴在任何时间点上都在同一高度上工作，而这两种机器配置。如果正在建造的结构的宽度不大于高架平台机器的宽度（即如果大型单一龙门架不必在其轨道上往复运动），那么工具路径规划对两种机器配置都是一样的。
研究总结此处报告的研究旨在为CC机器的操作规划和优化提供一种系统的方法，以便通过使用单台或多台机器和其他硬件配置的轮廓加工系统有效地建造复杂的大型结构。2.5D建筑结构已被考虑。结构模型首先被水平地切成不同的层，然后对结构的每一层的布局进行工具路径规划和优化。要求CC喷嘴在移动到下一层之前完成每一层的施工。
在这些前提下，边和顶点被定义为轮廓加工工具路径的基本元素，边代表墙段，顶点代表墙段的交叉点、转角或终点。该技术的物理约束被纳入到施工中考虑到定义其他工具路径要素，如拆卸成本、移动成本、移动成本和旋转成本。通过定义工具路径元素，工具路径规划问题被转化为典型的图问题。该方法是通过给每条边的每两个端点分配一个负值，使问题符合TSP（旅行推销员问题）的结构，从而使最佳工具路径包括原始结构的每条边。
Lin-Kernighan启发式算法被用来寻找TSP解决方案。使用启发式TSP求解器是因为它可以找到一个不比精确解差5%的解决方案。即使是大规模的TSP问题（少于10000个顶点），也能在合理的时间内找到解决方案。一般来说，与最近点算法相比，CCTSP算法找到的解决方案节省了45%的喷嘴空气时间。当结构复杂度增加时，可以节省更多的时间。基于单喷嘴系统的优化方法，引入了一个两步程序，以便为多机器的轮廓加工系统生成无碰撞的工具路径。
在第一步中，首先根据使用的喷嘴数量将原始结构均匀地划分为不同的部分。每个部分所包含的喷嘴的工作量被平均分配，以便使每个喷嘴移动到下一层的等待时间最小。在第二步，引入缓冲区和路径循环的概念，在各部分之间建立无碰撞的工具路径。
