Monte Carlo Tree Search: Optimizing Toolpath Planning in FDM 3D Printing

Share this Article

Authors Chanyeol Yoo, Samuel Lensgraf, Samuel Lensgraf, Lee M. Clemon, and Ramgopal Mettu detail their research for improvements in FDM 3D printing, outlined in the recently published ‘Toward Optimal FDM Toolpath Planning with Monte Carlo Tree Search.’

Most toolpath planning in FDM 3D printing consists of input models sliced into layers; however, this can lead to a lack of efficiency in motion at times, especially when the extruder may still be moving but not actually printing. In this study, the researchers set out to compute an efficient and optimal toolpath via a new algorithm using the Monte Carlo Tree Search (MCTS).

“A powerful general-purpose method for navigating large search spaces that is guaranteed to converge to the optimal solution,” the MCTS was analyzed within this study regarding its ability to improve searches.

“To our knowledge, this is the first algorithm for toolpath planning with any guarantees on global optimality,” stated the researchers.

Example model of ‘four nuts’ (a) image, (b) labelled dependency graph, and (c) clustered dependency graph from (b)

Previously MCTS has been useful for solving problems in robotics applications, yielding the desired, greater efficiency in toolpath planning.

“Monte Carlo tree search algorithm is based on biased search algorithm for finding an optimal solution asymptotically. Starting at an initial condition, a tree grows at every iteration. The algorithm finds the next best node in a tree to expand using upper confidence bound (UCB), where UCB balances between exploitation and exploration. Intuitively, the node with higher likelihood of finding a better solution will be selected. Once a node is selected for expansion, one or a number of complete sequences is randomly generated from the node until reaching the end (e.g., end of time horizon),” explained the authors.

“In order to make our algorithm efficient, we also introduce a novel clustering algorithm on the dependency graph for the input model.”

An example illustrating clustering algorithm in Alg. 1. (1) 16 raw contours are clustered into three highly dependent subgraphs (HDS) as shown in (b).

With a dataset comprised of 75 models, use of the MCTS method did demonstrate ‘substantial reduction’ in wasted motion. The authors noted that MCTS performance was like that of their current local search toolpath planner, but overall made it easier for them to investigate difficult in planning with some models.

‘Four nuts’ model. Toolpath for building the part by (a)(d) typical layerwise planner, (b)(e) local search from [6], and (c)(f) proposed MCTS, with red indicating non-printing motion. The solution toolpath for each method is shown in red. Extrusionless distances (in mm) are 16737, 12220 and 11057, respectively.

‘Twisty’ model. Toolpath for building the part by (a) typical layerwise planner, (b) local search from [6], and (c) proposed MCTS, with red indicating
non-printing motion. Solution toolpath for each method is shown in red. Extrusionless distances (in mm) are 25021, 11423 and 11306, respectively.

“A natural question is why one would use MCTS over local search for a given model. Using our empirical studies, it appears that the output of the clustering step and subsequent composition of HDS components of the dependency graph provide guidance as to whether MCTS can achieve convergence,” concluded the researchers.

“As we saw in our empirical analysis if there enough HDS components with respect to the size of the dependency graph then it is highly likely that MCTS will converge to an optimal toolpath. If the number of HDS components is too large, or the average size is too small, then MCTS will have difficulty exploring the toolpath space and may perform worse than local search.”

Colored clusters for example parts

Researchers around the world continue to study ways to refine and use FDM 3D printing, from experimenting with new materials to fabricating innovative medical devices. 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.

[Source / Image: ‘Toward Optimal FDM Toolpath Planning with Monte Carlo Tree Search’]

Share this Article


Recent News

3D Printing Startup Markforged to Go Public via SPAC Merger with Blank-Check Firm

Mantle Comes out of Stealth with Hybrid Bound Metal 3D Printing Technology



Categories

3D Design

3D Printed Art

3D Printed Food

3D Printed Guns


You May Also Like

3D Printing News Briefs, February 24, 2021: Auburn University, Vector Photonics, Siemens Energy, Omegasonics, Bugatti, Hackaday

We’re starting with some business in 3D Printing News Briefs today, talking about Auburn University’s Additive Manufacturing Accelerator and Vector Photonics leading the BLOODLINE consortium, which I promise isn’t as...

Sponsored

The Future of Bound Metal 3D Printing for ExOne

Bound metal 3D printing is becoming one of the most productive metal additive manufacturing (AM) technologies for creating high-performance parts on-site. One of the few firms pioneering this emerging technology...

Sponsored

Studio System 2: Desktop Metal is excited to announce the second generation of the Studio System.

With a simplified, two-step process, the Studio System 2 is the easiest way to print complex, high-quality metal parts in your office.1 Origins of the Studio System When it was...

Featured

ExOne (XONE) Releases Office-Friendly Bound Metal 3D Printer

The competition in Binder Jet is heating up. Just a week ago, Desktop Metal (NYSE: DM) announced the two-step bound metal Studio 2 System. By eliminating one step of the...


Shop

View our broad assortment of in house and third party products.