  The most widely used methods for toolpath planning in fused deposition 3D
printing slice the input model into successive 2D layers in order to construct
the toolpath. Unfortunately slicing-based methods can incur a substantial
amount of wasted motion (i.e., the extruder is moving while not printing),
particularly when features of the model are spatially separated. In recent
years we have introduced a new paradigm that characterizes the space of
feasible toolpaths using a dependency graph on the input model, along with
several algorithms to search this space for toolpaths that optimize objective
functions such as wasted motion or print time. A natural question that arises
is, under what circumstances can we efficiently compute an optimal toolpath? In
this paper, we give an algorithm for computing fused deposition modeling (FDM)
toolpaths that utilizes Monte Carlo Tree Search (MCTS), a powerful
general-purpose method for navigating large search spaces that is guaranteed to
converge to the optimal solution. Under reasonable assumptions on printer
geometry that allow us to compress the dependency graph, our MCTS-based
algorithm converges to find the optimal toolpath. We validate our algorithm on
a dataset of 75 models and show it performs on par with our previous best local
search-based algorithm in terms of toolpath quality. In prior work we
speculated that the performance of local search was near optimal, and we
examine in detail the properties of the models and MCTS executions that lead to
better or worse results than local search.
