MIT: New Algorithms for Robotic Spatial Extrusion Planning

MIT scientists are researching new ways to improve automated systems, outlining their findings in the recently published ‘Scalable and Probabilistically Complete Planning for Robotic Spatial Extrusion.’ Exploring new ways to integrate robotics into production, the authors have created a new concept for robotic spatial extrusion, accompanied by complete planning algorithms.

Focusing on an alternative to the traditional 3D printing layering method, the researchers sought to overcome current challenges in robotic extrusion like collision and kinematic geometric constraints, along with stiffness constraints. This method has only been used in limited measures, which the researchers attribute to planning constraints during larger builds.

Left: Klein bottle (246 elements). Right: Duck (909 elements).

The algorithm created for this study is based on mathematical form, allowing the research team to connect ‘satisfying geometric and structural constraints,’ as stiffness is critical in construction initially, with collisions limiting actions at the end. The mathematical formulas are meant to plan for both stiffness and geometric constraints, ‘globally performing a greedy backward search, using forward reasoning to bias the search towards stiff structures.’ The scientists also offer prioritization heuristics for leading stiffness and geometric decision-making.

The scientists began formulations without a robot present, creating a frame structure with an undirected geometric graph hN, Ei embedded within R 3:

“Let the graph’s vertices N be called nodes and the graph’s edges be called elements E ⊆ N2 where m = |E|. Each node n ∈ N is the connection point for one or more elements at position pn ∈ R 3. Each element e = {n, n0} ∈ E occupies a volume within R 3 corresponding to a cylinder of revolution about the straight line segment pn → pn0. A subset of the nodes G ⊆ N are rigidly fixed to ground and thus experience a reaction force.

“Each element e = {n, n0} can either be extruded from n → n 0 or n 0 → n. Let directed element ~e = hn, n0 i denote extruding element e = {n, n0} from n → n 0. We will use the set P ⊆ E to refer to a set of printed elements, representing a partially extruded structure. Let NP = G ∪ {n, n0 | {n, n0} ∈ P} ⊆ N be the set of nodes spanned by ground nodes G and elements P. Extrusion planning requires first finding an extrusion sequence, an ordering of directed elements ψ~ = [~e1, …, ~em]. We will use ψ to denote the undirected version of ψ~. Let ψ~ 1: i = [~e1, …, ~ei ] give the first i elements of ψ~ where i ≤ m.”

Transition, retraction, and extrusion motions for two elements.

Extrusion planning was meant to be completed by one articulated robot manipulator adhering to joint limits and avoiding collisions with itself, the environment, and items just printed.

“Let Q : P → Q be a function that maps a set of printed elements P ⊆ E to the collision-free configuration space of the robot Q(P) ⊆ Q. When no elements have been printed, Q(∅) is the collision-free configuration space of the robot when only considering environment collisions, self-collisions, and joint limits. Each additionally printed element weakly decreases the collision-free configuration space…”

The authors worked on 41 different extrusion problems in this study, featuring up to 909 elements, and combinations of the PROGRESSION, FORWARDCHECK, and REGRESSION algorithms, as well as four heuristics: Random, EuclideanDist, GraphDist, and StiffPlan. Four trials were performed for each algorithm, with one-hour timeouts.

PyBullet assisted in collision checking, forward kinematics, and rendering. Structures were preprocessed using one static axis-aligned bounding box (AABB) bounding volume hierarchy (BVH) with each robot link and then the following solutions were used:

• PLANMOTION using RRT-Connect
• SAMPLEIK using IKFast
• PLANCONSTRAINED using Randomized Gradient Descent (RGD)

From left to right: 1) the unassigned substructure at the first state where REGRESSION-Random backtracks. 2) the first state where REGRESSION-EuclideanDist backtracks. The element deflection is colored from white to pink. The five most deformed nodes are red and their translational displacements are annotated in meters 3) the first state where REGRESSION-GraphDist backtracks 4) REGRESSION-StiffPlan finds a solution without backtracking.

The PROGRESSION and REGRESSION algorithms exhibited improved performance, showing that the heuristics did offer stiffness and geometric guidance. FORWARDCHECK offered better accuracy for problem-solving than PROGRESSION, ‘indicating that it is able to avoid some dead ends.’ In the end though, the researchers noted that REGRESSION was the best performer in comparison to the others, shining in both success rate and runtime. The highest-performing algorithms solved 92 percent of the problems, with an average runtime of about 15 minutes.

The runtime of each algorithm when using the EuclideanDist heuristic. The x-axis ticks denote the distribution of problem sizes.

“We experimented on two extrusion problems considered by Choreo. Choreo solves the ‘3D Voronoi’ and ‘Topopt beam (small)’ problems in 4025 and 3599 seconds whereas REGRESSION-EuclideanDist solves the problems in 742 and 2032 seconds. Our planner outperforms Choreo despite the fact that Choreo had access to additional, human-specified information (section II). We validated our approach on three real-world extrusion problems. The largest of the three is the Klein bottle, which took about 10 minutes to plan for and 6 hours to print.

“Future work involves extending our approach to general-purpose construction tasks,” concluded the researchers.

Automated systems and robots continue to play a large role in the world of 3D printing, from experimentation with microrobots to ongoing NASA projects to studies meant to improve scalability, What do you think of this news? Let us know your thoughts! Join the discussion of this and other 3D printing topics at 3DPrintBoard.com.

Left: The first state where PROGRESSION-EuclideanDist backtracks (black elements are unprinted). Right: REGRESSION-EuclideanDist finds a solution without backtracking.

Left: the first state where PROGRESSION-GraphDist backtracks (black elements are unprinted). Right: FORWARDCHECK detects that printing the element indicated by the pink sphere prevents the diagonal black element from being safely extrudable.