Scalable and Probabilistically Complete Planning for Robotic Spatial Extrusion

Caelan Garrett , Yijiang Huang , Tomás Lozano-Pérez , Caitlin Mueller


There is increasing demand for automated systems that can fabricate 3D structures. Robotic spatial extrusion has become an attractive alternative to traditional layer-based 3D printing due to a manipulator's flexibility to print large, directionally-dependent structures. However, existing extrusion planning algorithms require a substantial amount of human input, do not scale to large instances, and lack theoretical guarantees. In this work, we present a rigorous formalization of robotic spatial extrusion planning and provide several efficient and probabilistically complete planning algorithms. The key planning challenge is, throughout the printing process, satisfying both stiffness constraints that limit the deformation of the structure and geometric constraints that ensure the robot does not collide with the structure. We show that, although these constraints often conflict with each other, a greedy backward state-space search guided by a stiffness-aware heuristic is able to successfully balance both constraints. We empirically compare our methods on a benchmark of over 40 simulated extrusion problems. Finally, we apply our approach to 3 real-world extrusion problems.

Live Paper Discussion Information

Start Time End Time
07/16 15:00 UTC 07/16 17:00 UTC

Virtual Conference Presentation

Supplementary Video

Paper Reviews

Review 1

This paper addresses a problem of growing interest in 3D printing and proposes a comprehensive planning framework for the spatial extrusion of models with robotic manipulators. The paper is well written, exposes the challenges in the application domain, and proposes an effective method to address them. Good results are presented. One interesting aspect of the work is that it addresses the underlying motion planning problem while taking into account the stiffness of the model being built, such that the structure is always stable and undergoes no deformation while being built. The treatment of avoiding “dead-end” states is clearly needed and the proposed method successfully avoids such states leading to the successful completion of multiple prints. The submitted video demonstrates the robotic arm printing real physical models correctly and efficiently. One comment for improvement of Figure 1-left is that the shown model should be clearly indicated to be a real physical one given that the image gives the impression to have a virtual model displayed on top of the image of the physical robot. The work includes a theoretical analysis of the proposed algorithm with details included in the submitted supplementary material. Since the overall method involves several components and the paper proposes probabilistic complete algorithms, it would be useful to state since the beginning in the introduction expected real performance with given real problem instances, for example with respect to Figure 7 which indicates that not all instances tested were solved. The work has multiple components, and as expected, details are sometimes not commented or cited to follow previous work. For instance, one point that is not commented is if edge subdivision could transform unsolvable cases into solvable ones. Edge refinement is a typical strategy to augment decision resolution in a discretized problem instance. The extrusion of material in edges is governed by equation 4, which seems to enforce that edges in the model can only be straight line segments, however, it should be possible to follow generic curves. The arm trajectory generation depends on PlanConstrained, which is referenced to come from previous work, and it would be useful to have an overview of how the straight segments are achieved. The restriction of the orientation of the end-effector to the mentioned hemisphere, while it makes sense, could perhaps have an impact in preventing a feasible problem to be solved in special cases requiring extreme end-effector maneuvers. It is however understandable that not all details can be explored in the paper. Overall the paper presents a comprehensive solution that successfully addresses the stable spatial extrusion of models.

Review 3

***************** Specific comments ***************** (*) III.A - this section is the hardest to read and contains multiple variables that were not introduced. My take home message from this section was "I have no idea how stiffness can be computed but I believe it can...." (*) A figure describing the set of orientations opposite to the direction of pn -> pn' would be helpfull (*) Algorithm 1 - why do we need to sample an endpoint? One endpoint is connected to the already-extruded structure. Shouldn't we always extrude from that point? (*) I found the discussion at the end of VII.A meaningless since it is only related to the proof that is only provided in the supplumentary material and is not part of the paper. (*) Fig 6 is hard to understand, the values are in fonts so small that they are useless ***************** Typos ***************** (*) page 2, left column: "might is a lower-dimensional submanifold" -> "might be a lower-dimensional submanifold" (*) page 2, right column: "element element" -> "element" (*) Section W, Figure X, Algorithm Y, Definition Z should have a capital S, F, A and D, respectively. (*) Definition 3 has an extra period. (*) Page 5 left column: "moving in a forward direction proves to advantageous for satisfying the stiffness constraint." -> "moving in a forward direction proves to be advantageous for satisfying the stiffness constraint." (*) Page 7 left column: "extrusion planning simply requires a identifying a totally-ordered subset" -> "extrusion planning simply requires identifying a totally-ordered subset" (*) Last sentence of first paragraph in section VIII - missing period before "We". ***************** References ***************** (*) Sometimes hyperlinks are embedded and sometimes they are given as urls. (*) Sometimes conference names are given with and sometimes without abbreviations (29 vs 45) (*) Ref 29, {RRT-Connect} -> RRT-Connect (*) Sometimes ISBN and / or doi values are provided and sometimes they are not.