Scalable and Probabilistically Complete Planning for Robotic Spatial Extrusion

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