AMS Spring 2023

MIT: New Algorithms for Robotic Spatial Extrusion Planning

6K SmarTech

Share this Article

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.

[Source / Images: ‘Scalable and Probabilistically Complete Planning for Robotic Spatial Extrusion’]

Share this Article


Recent News

3D Printing News Unpeeled: VulcanForms, HoPro3D and Fortius

NextFlex Announces $8.45M in Funding for Semiconductors and Electronics 3D Printing



Categories

3D Design

3D Printed Art

3D Printed Food

3D Printed Guns


You May Also Like

Featured

Nano Dimension Leadership Struggles for Control over Electronics 3D Printing Company

According to a report from Israeli site CTech, leadership at Nano Dimension (Nasdaq: NNDM) may be fighting for control over the electronics 3D printing company. CEO Yoav Stern has requested...

Featured

BMW Begins Production of Hydrogen-Powered iX5 Vehicle with 3D Printed Parts

BMW Group announced that the auto giant has begun small-scale production of the iX5, touted by the company as the world’s first “sports activity vehicle” powered by hydrogen fuel cells....

Featured

Ursa Major and EOS to Disrupt Space Production with 3D Printed Copper

“Let’s build some engines!” That’s essentially what Ursa Major is doing. Based in Colorado, this space technology business is racing to improve humanity’s quest to explore the universe – several...

Art Basel Visitors Can Purchase Zero-Waste 3D Printed Furnishings

Art fairs are getting creative and launching new experiences for visitors. For example, during the 20th edition of Art Basel Miami Beach – the centerpiece of the city’s widely acclaimed...