A Heuristic Scaling Strategy For Multi- Robot Cooperative 3D Printing

Journal of Computing and Information Science in EngineeringLiaison method [19]. M. Gombolay et al. developed a centralized algorithm Terico togenerate a fast schedule with simple temporospatial constraints for a multi-robotsystem, which could perform near-optimal task assignments and schedules for up to 10robots and 500 tasks in less than 20 seconds on average [20]. A. T. Rashid et al.demonstrated a new method of collision-free navigation of multiple robots in a dynamicenvironment based on reciprocal orientation [21].While these studies have made notable advances in MRS planning, they are notdirectly applicable to 3D printing because 3D printing is a continuous process wherematerials are continuously deposited in space-time until the desired part is completed,which poses new challenges for realizing cooperative 3D printing with many robots. Noexisting methods can take a digital model (e.g., an STL file) and directly do planning for3D printing with multiple robots in the continuous space-time. To overcome thechallenge, we developed a chunk-based approach that divides the digital model intochunks and thus discretizes the continuous process into a multi-stage process, asillustrated in Figure 2. However, the discretization does not turn this continuousproblem into a regular discrete problem studied in existing MRS literature because thereare inherent inter-dependencies between the multiple stages resulted from thecontinuous nature of the problem, as represented by the double arrows in Figure 2. Tobe specific, chunking does not only depend on the geometry of the digital model, butalso the number of available robots, the scheduling strategy, and the path planning, tomake sure the printing process is physically feasible. Similarly, the geometric constraintsare dynamically changing in space-time with a strong dependency not only on thegeometry of the digital model, but also on the chunking, scheduling, and path planningstrategies. These unique challenges distinguish cooperative 3D printing from existingMRS research in terms of planning strategies.Figure 2 Flowchart showing the discrete stages of cooperative 3D printing5JCISE-19-1132, Zhou

Journal of Computing and Information Science in EngineeringCompared to other existing 3D printing methods, cooperative 3D printingprevails in many areas. First, it offers one of the most flexible manufacturing platformsbecause it can be easily deployed (by placing the mobile robots in the dedicated area),scaled up and down (adding or removing robots), and re-configured (adding or changingthe type of robots). Second, it is more robust than the centralized manufacturingsystems because malfunctions of individual robots can be kept local and will not breakdown the entire platform. In addition, the print size is not limited by the size of theprinter since the mobile robots can roam over the entire factory floor. Also, the use ofmultiple robots allows multi-color and multi-material printing, the cooperation betweenmultiple processes (e.g., inkjet and extrusion), and the integration of pre-manufacturedcomponents to bridge the gap between traditional manufacturing and 3D printing. Theresearch, in fulfilling these promises of cooperative 3D printing, is still in its infancy. Inthis paper, we present the first working scaling strategy for enabling many robotsprinting together. The key contributions are summarized below.1. First, it presents a new method of 3D printing – cooperative 3D printing, in whichmultiple mobile 3D printing robots work together to complete a print job.2. Second, it presents a new method in discretizing the continuous 3D printing process,where the desired part is discretized into chunks, resulting in the multi-stage 3Dprinting process.3. Third, this paper presents the first working scaling strategy that enables thecooperation of many mobile 3D printers.3. SCALABLE PARALLEL ARRAY OF ROBOTS FOR 3D PRINTING (SPAR3) STRATEGYIn C3DP, a printing strategy is composed of two separate, yet related stages:chunking and scheduling. The chunking stage includes dividing a digital model at largeinto chunks (or printing tasks in more general terms) so that each chunk can be printedby a single printing robot. The scheduling stage deals with the assignment of the dividedchunks to individual robots and generating a print sequence for each robot in order toachieve a collision-free printing. In our previous work, we demonstrated this processwith a two-robot system [1]. Due to the inherent complexity of the printing process andthe lack of an existing mathematical formulation of the printing strategy, the logical firststep is to search for a working strategy based on simple heuristics instead of seeking anoptimal printing strategy. In this section, we present a heuristic-based scaling strategy –Scalable Parallel Arrays of Robots for 3DP (SPAR3).3.1ChunkingGiven a printing object, a chunking strategy is used to divide the part into smallerchunks. In this paper, we adopt the chunking strategy with a sloped interface becausethis strategy has previously been studied and has been proven to maintain sufficientlystrong adhesion between chunks for FDM process [22]. In the sloped interface chunking,a part is divided first vertically and then horizontally such that each of these chunks hasan either positive or negative slope on each side, as shown in Figure 3. The positive6JCISE-19-1132, Zhou

Journal of Computing and Information Science in Engineeringslope refers to a slope with an angle 𝜃𝑐 smaller than 90 whereas the negative sloperefers to the one with an angle larger than 90 . For example, the chunk in Figure 3(d),shows a central chunk with all four positive slopes. The shape of the chunk differs basedon the sloped surfaces it has on each side. Due to this reason, the chunk located atcoordinate 23 (row 2 and column 3 in Figure 3(a)) has a different shape (positive slopeon both horizontal ends whereas, a negative slope on inside and positive on outside invertical ends) than the central chunk. The exploded top view in Figure 3(a) shows theshape of each chunk at a different row and column location whereas, the dimetric viewin Figure 3(b) shows the boundary lines on a part at which the division takes place. Thedimension associated with the chunks are depicted in Figure 3(d).Figure 3(a) Top exploded view of a part showing individual chunks (both rows and columns arenumbered). (b) Dimetric view of the part showing chunk’s boundary. (c) Dimetric exploded view. (d)Dimension of a center chunkTo ensure the printability of a chunk, the following constraints need to be satisfied.1. As shown in Figure 4(a), if 𝜃𝑐 is the angle of the sloped bonding interface betweenthe chunks, 𝜃𝑒 is the angle of the exterior of the extruder nozzle from the vertical,and h is the tallest height of the chunk, and the overall depth of each chunk is 𝐷𝑐 ,then 𝜃𝑐 is guided by the following equations (1) and (2).𝜃𝑐 90 𝜃𝑒𝜃𝑐 tan 1(1)ℎ(0.5𝐷 )(2)𝑐Equation (1) must be satisfied, otherwise the nozzle, in Figure 4(a), willinterfere with the printed part of the chunk; however, if the angle is too small, thewheels of the robots will interfere with the printed chunk as the robot moves toprint the other end of the chunk (right edge of the chunk in Figure 4(a)). Thus, the7JCISE-19-1132, Zhou

Journal of Computing and Information Science in Engineeringminimum value for slope angle that can be used for sloped surface chunking strategyis given by equation (2), which is bounded by the maximum value of 𝐷𝑐 .2. If the reach of the printhead arm is 𝐷𝑒 , which is the lateral distance between thepoint of material extrusion and the nearest part of the wheels and/or chassis of therobot, and the overall depth of each chunk is 𝐷𝑐 , the following equation must holdtrue.𝐷𝑐 𝐷𝑒(3)Figure 4(a) Illustration of chunk’s dimension and printing limitations on the slope, (b) Comparisonof chunk width with the width of the robot, (c) Dimension of the top base of center chunk and distancebetween the nozzle and the hardware end and, (d) scenario showing collision between the hardware whenthe top base of the chunk is too narrow to fit the hardware while printers are working on opposite rows ofcenter chunk row.3. If the width of the robot is 𝑊𝑟 and the width of the chunk is 𝑊𝑐 as illustrated inFigure 4(b), the following should be true in order to avoid potential collision8JCISE-19-1132, Zhou

Journal of Computing and Information Science in Engineeringbetween adjacent active robots in a row. This chunking constraint is only applicableto chunking strategy if used in conjunction with SPAR3.𝑊𝑐 𝑊𝑟(4)The SPAR3 strategy divides the object into columns and rows. After printing thecenter row, the robots on both sides of the center row retreat to print more rows. Thenumber of columns 𝑛𝑐𝑜𝑙𝑠 directly determines how many robots can be used on eachside of the center row for SPAR3 strategy (i.e., 2 columns for 1 robot on each side of thecenter row). Based on the chunking constraints presented above and the number ofrobots available for printing, the total number of chunks can be determined with thefollowing procedure.1. Number of chunk columns (𝑛𝑐𝑜𝑙𝑠 ): The maximum number of chunk columns canbe determined by dividing the entire length of the part by smallest chunk width,which is equal to the width of the robot. Thus, if the length of a part is 𝐿 and thewidth of the robot is 𝑊𝑟 , then,𝑚𝑎𝑥𝑀𝑎𝑥𝑖𝑚𝑢𝑚 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑐ℎ𝑢𝑛𝑘𝑠 𝑐𝑜𝑙𝑢𝑚𝑛 (𝑛𝑐𝑜𝑙𝑠) 𝐿(5)1𝑊𝑟Once the upper bound is calculated, the ideal number of chunk columnsfor given number of robots (𝑁) can be calculated using equation below:𝑚𝑎𝑥𝑁𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑐ℎ𝑢𝑛𝑘𝑠 𝑐𝑜𝑙𝑢𝑚𝑛 (𝑛𝑐𝑜𝑙𝑠 ) 𝑚𝑖𝑛(𝑁, 𝑛𝑐𝑜𝑙𝑠)(6)2. Number of chunk rows (𝑛𝑟𝑜𝑤𝑠 ): The number of chunks rows on the other hand isguided by the constraints related to the chunk depth (Equation 3). Using thedepth constraint, we calculate the minimum number of chunk rows for the partby dividing the width of the part by the largest chunk depth permitted, which isequal to the reach of the printhead arm of the robot. Thus, if the width of thepart is 𝑊 and the reach of the printhead arm is 𝐷𝑒 , then,𝑚𝑖𝑛𝑀𝑖𝑛𝑖𝑚𝑢𝑚 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑐ℎ𝑢𝑛𝑘 𝑟𝑜𝑤𝑠 (𝑛𝑟𝑜𝑤𝑠) 𝑊𝐷𝑒(7)1The ideal number of chunk rows is not dependent on the total number ofrobots available for printing. For SPAR3 strategy, smaller number of chunk rowis desirable in order to avoid unnecessary travel between the print sequences.Although, if the number of chunk rows is less than three, only half of the printingrobots can be utilized for printing which diminishes the printing efficiency. Onthe other hand, it also needs to be ensured that the top base of the center chunk(𝐷𝑡 ) is twice as wide as the distance between the nozzle and the end of thehardware (𝐷ℎ ). This is to avoid collision between the different printheads of therobots working on either side of center chunk as shown in Figure 4(d).1If the result is non-integer, it is rounded up to next larger integer9JCISE-19-1132, Zhou

Journal of Computing and Information Science in EngineeringOnce the number of chunk columns and number of chunk rows are calculated, the totalnumber of chunks can be calculated using the following equation,𝑇𝑜𝑡𝑎𝑙 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑐ℎ𝑢𝑛𝑘𝑠 𝑛𝑐𝑜𝑙𝑠 𝑛𝑟𝑜𝑤𝑠3.2(8)SchedulingThe output of chunking, the chunks, along with the number of available robots aretaken as input for print scheduling. Scheduling consists of two main aspects: chunkassignment and chunk scheduling.a. Chunk assignment: An example of chunking outcome is depicted in Figure 3(a),which has five rows and four columns of chunks. Each chunk is assigned to anindividual robot. Each adjacent pair of chunks in a row is assigned to a single robot,such that there is a gap between the active robots (robots that are printing) at anygiven time to prevent collision between them. For example, as illustrated in Figure 5(a) and (b), chunks 31 and 32 (represented in Figure 3(a)) are assigned to the samerobot and chunks 33 and 34 are assigned to the second robot. Doing so wouldprevent collision between the first and the second robot while they are working inparallel. Additionally, each row of chunks is assigned to only one of the rows of therobots so that there is no inter-row collision between them. For example, the row ofchunks containing chunks 51, 52, 53 and, 54 (represented in Figure 3(a)) is assignedonly to robots at the bottom in Figure 5.b. Chunk scheduling: After the completion of chunk division and chunk assignment, aprint sequence is generated based on the dependency relationship between chunks.Based on the dependency, the chunks can be divided into three types:1. Seed Chunk: Seed chunks are the chunks that are printed first in a print job andhave positive bonding slope on all sides unless they are an end chunk. In Figure3, the chunk located at the third row and the third column (location 33) andchunk 31, in the top view, are the seed chunks.2. Parent Chunk: Parent chunks are the chunks that need to be printed prior toprinting any other chunks. In Figure 3, the seed chunks located at 33 and 31 areparent chunks of chunks 32 and 34.3. Daughter Chunk: Daughter chunks are those that cannot be printed until aftertheir respective parent chunks are completed. Daughter chunk could either be agap chunk or dependent end chunk. In Figure 3, the chunk located at 34(dependent end chunk) is an example of a daughter chunk of the seed chunklocated at 33. If a daughter chunk is located in between two parent chunks, inthe horizontal direction, we refer to it as a gap chunk. In Figure 3, the chunklocated at 32 is referred to as a gap chunk.Using the printing object shown in Figure 3 as an example, the SPAR3 strategy inconjunction with the sloped surface chunking method is depicted in Figure 5. Chunksare assigned to four 3D printing robots and printing begins at the center of the printingarea and then expands into two opposing rows of robots. First, one row of robots prints10JCISE-19-1132, Zhou

Journal of Computing and Information Science in Engineeringevery other chunk (seed chunks) as shown in Figure 5(a) while the others standby at thesafe distance to avoid collision with the active robots. So, the robots printing the seedchunks will be the only group of robots that accomplish the center chunks. Once theseed chunks are complete, the same initial robots move over to print the gap chunks inorder to fill the gap between the parent seed chunks (Figure 5(b)). After the completionof the central chunk row, the active robots retreat to begin printing the next row ofchunks. Meanwhile, the robots that were on standby, become active and begin printingthe second row of chunks on the other side of the central row (Figure 5(c)). Both sets ofthe active robots follow the same strategy, i.e., print parent chunks move over to fillthe gap print the daughter chunks move to next row, till the print job is complete,as shown in the snapshots of Figure 5.Figure 5 Illustration of rectangular prism being printed using the SPAR3 strategy with four robots. Printingstarts with the center chunks seed chunks. Chunks that are being worked on at each step are representedin red color whereas the completed ones are represented in blueThus, the heuristic approach, SPAR3 strategy, used in conjunction with slopedinterface chunking strategy can be outlined in the following manner. The first and the11JCISE-19-1132, Zhou

Journal of Computing and Information Science in Engineeringsecond steps are related to the chunking, the third step is related to chunk assignment,while the fourth and the final step are related to chunk scheduling.1. Determine the maximum number of chunk columns using equation (5) andminimum number of chunk rows using equation (7).2. Determine the number of chunks based on number of robots available forprinting along with the values obtained from Step 1 using equation (8). The totalnumber of chunks) along with the total number of robots available for printingare the inputs for the subsequent step, i.e., chunk scheduling.3. The chunks assignment is done based on the proximity of chunks. For example,the robot that prints the center chunk of the center row is also assigned with thechunk next to it in order to minimize unnecessary movements. Alternate parentchunks are assigned to different robots. Their daughter chunks are assigned tothe same robots such that once the parent chunks are printed, the robots canstart working on the adjacent chunks (daughter chunks) without repositioningmoves.4. Chunk scheduling:i. The printing begins with the center seed chunks with half of the total numberof robots available.ii. Once complete, these robots then move to print the daughter chunks in thecenter row.iii. Once center row is complete, the active robots move back to start workingon the second row. The remaining robots become active and start workingon parent chunks on second row on other side of the center row.iv. The printing of daughter chunk follows afterwards. This process continuesuntil the part is complete.4. EVALUATION FRAMEWORKWhile it is possible to illustrate a printing strategy as presented in Section 2, thelack of a formal language to describe a printing strategy makes it difficult to evaluate theperformance of the printing strategy. In this section, we present a graph-based languagebased on directed dependency tree (DDT) to capture the most critical information of aprinting strategy – the dependency relationship between chunks and the sequence of aprinting process. Based on the DDT description, we develop a framework to estimatethe total printing time of a given printing strategy. Based on the insights obtained fromthe SPAR3 strategy, we also formulate a set of constraints that a valid printing strategymust satisfy. If used in conjunction with DDT, these constraints can facilitate thedevelopment of new (and even optimal) printing strategies and meanwhile evaluatingtheir validity and performance.4.1Chunk Dependencies and Directed Dependency TreeOne of the most important aspects of a valid printing strategy is to clarify thedependency relationship between chunks. A tree is a graphical representation that has12JCISE-19-1132, Zhou

Journal of Computing and Information Science in Engineeringbeen widely used

Journal of Computing and Information Science in Engineering 4 JCISE -19 1132, Zhou this paper, we present a working strategy based on a simple heuristic that enables many mobile 3D printers to work cooperatively to finish a printing job without interference. More specifically, we developed a heuristic scaling strategy, called Scalable Parallel