minimize maximum travel time

[ghost]

In general, it seems that retraction allows a limited amount of oozeless travel time, and the amount of ooze/error then starts increasing proportionally (but not linearly) with travel times beyond that.

Is it possible for cura to minimize the maximum travel time (precisely: minimize total travel time once maximum travel time has been minimized) within layers or (ideally) within layer pairs?

[Ghostkeeper]

No, this is proven to be impossible unless P=NP (which is arguably the largest open problem in computer science).

The problem of minimising travel time is a variant of the non-metric travelling salesman problem. It is non-metric because we're printing lines, not points, and each line segment has two endpoints. The actual printing time is not penalised here. Effectively you could see each line segment as being a worm hole that instantly transports the nozzle to the other side. Since that breaks the metric distances (specifically the rule that the distance from A to B is equal to or less than the distance from A to B via C), this makes our problem a non-metric travelling salesman problem.

Your feature request would turn that problem into the bottleneck travelling salesman problem.

Both travelling salesman and the bottleneck variant are NP-hard. That means that there is currently no known algorithm that solves this problem in a reasonable amount of time. The best known algorithms are exponential, meaning that some bad cases will last longer than the current age of the universe to solve and so on. It's not desirable to put those in CuraEngine for a user to wait on.

For the current non-metric TSP problem we have an approximation. A rather simplistic one: Nearest neighbour. Simply put, after printing each line, Cura will look for the next closest line to print. This is quadratic in running time; not ideal but doable.

However it has been proven that for the non-metric case, no polynomial approximation algorithm is possible for the bottleneck variant of TSP unless P=NP. See the last sentence of this segment here: https://en.wikipedia.org/wiki/Bottleneck_traveling_salesman_problem#Metric_approximation_algorithm or its source paper.

Since we need a polynomial algorithm, but not even an approximation algorithm is known in polynomial time by science, we'll close this ticket as a won't-fix.

[ghost]

I'm not sure I understand.

• Printing and travel might occur at different speeds, but they do both occur at finite speeds, so giving up all hope of a reasonable metric seems a bit premature.

• Nearest neighbour searching needn't be quadratic - and if it weren't, presumably even simple heuristics could yield better results?

• For any practical application heurstics are required (vanilla TSP is NP-hard), so the bottleneck variants are unlikely in practice to be difficult: just solve once, and then sequentially bisect to find the minimum maximum travel length (with respect to your heuristic)

Finally, it seems that bottleneck TSPs are in practice readily solved to optimality even for cases with ~10000 points, which I am guessing is far in excess of the size of the TSPs that Cura would need to solve in practice?

I'm not sure it's worth giving up on this effort. If I were to implement this, where in the codebase would you recommend I look/start?

[Ghostkeeper]

Printing and travel might occur at different speeds, but they do both occur at finite speeds, so giving up all hope of a reasonable metric seems a bit premature.

The problem is not that the print speeds are different. The problem is that we only want to minimise the travel time, not the time spent extruding. The time spent extruding is fixed and can't be changed. It shouldn't be counted along in the minimisation. You could count it though; since it is fixed that is just a +c to your optimised printing time. However that means that you still need to ensure that certain edges of the graph are always included in the result. Eventually that just boils down to the same problem, a non-metric graph.

Nearest neighbour searching needn't be quadratic - and if it weren't, presumably even simple heuristics could yield better results?

It's quadratic in the total runtime to find the path, because we iterate over the nodes we need to pass (O(N)) and for each of these iterations we iterate again over the possible choices for the next node to select (O(N) again). The second iteration can be sped up in common cases by using a grid data structure. CuraEngine does this with a grid of 2x2mm. That makes the algorithm linear in the best case, or O(N²) in the worst case. After all, if there is no nearby node you're going to have to expand the grid search to more distance cells. This grid does help a lot with high-density patterns though, like skin.

For any practical application heurstics are required (vanilla TSP is NP-hard), so the bottleneck variants are unlikely in practice to be difficult: just solve once, and then sequentially bisect to find the minimum maximum travel length (with respect to your heuristic)

Heuristics are ubiquitous in vanilla TSP, but that doesn't mean that this variant of it can be solved with a heuristic. As it said in the article I linked: "Without the assumption that the input is a metric space, no finite approximation ratio is possible." They don't mention there that the finite approximation ratio is possible with exponential algorithms. Polynomial is implied. But in layman's terms, they basically say: You can't give an algorithm that guarantees reasonable results in reasonable time. What you could do is randomly try 3 solutions and pick the one with the lowest maximum or something.

Finally, it seems that bottleneck TSPs are in practice readily solved to optimality even for cases with ~10000 points, which I am guessing is far in excess of the size of the TSPs that Cura would need to solve in practice?

Yeah, Cura's problems are in the range of up to 2000 or so vertices. I don't know who solved those TSP problems you mentioned, but we have to keep in mind that we don't have access to GPU accelerators here (yet), and we have to solve these multiple times per layer. ~1000 layers are not uncommon. If they managed to solve this with a computer cluster or something, in a timespan of several days, that is not really a solution for Cura. We need to be thinking in the range of 100ms or so per graph (which would add like 3 minutes to the slicing time for a big model of 1000 layers, assuming 2 graphs per layer). I'm not sure if users would even want to wait 3 minutes for it to give possibly a shorter maximum travel distance for some of the layers though.

If you want to look into this, you need to look at the PathOrderOptimizer class. I'm curious for ideas to improve the results, even if it doesn't completely solve the problem. We're looking for a solution that marginally impacts performance (though some performance hit is probably acceptable), improves print quality (even a little) and is not too complex to maintain.

[ghost]

The time spent extruding is fixed and can't be changed. It shouldn't be counted along in the minimisation. You could count it though; since it is fixed that is just a +c to your optimised printing time. However that means that you still need to ensure that certain edges of the graph are always included in the result. Eventually that just boils down to the same problem, a non-metric graph.

I understand, but that's not what I was getting at - while there's no efficient constant-factor approximation for non-metric TSP, that statement is very strong. For example, if we insist that edge lengths are non-zero integers, any algorithm that gives a valid tour is automatically optimal to within a factor of the maximum edge length, because no solution can have a cost greater than the maximum edge length along each path. (Note how that if zero weights are permitted then this argument fails, because now even knowing whether or not a zero-cost tour exists is equivalent to Hamiltonian Cycle.) I don't mean to suggest that Sahni and Gonzalez's result is useless, just that I don't think it is as relevant to something as firmly embedded euclidean space as Cura is.

Yeah, Cura's problems are in the range of up to 2000 or so vertices. I don't know who solved those TSP problems you mentioned, but we have to keep in mind that we don't have access to GPU accelerators here (yet), and we have to solve these multiple times per layer. ~1000 layers are not uncommon. If they managed to solve this with a computer cluster or something, in a timespan of several days, that is not really a solution for Cura.

My recollection (it was another of Gonazles' papers I think) is that the largest problems were solved on a desktop over hours, but instances of 2000 vertices were solved in seconds. And I think there's another opportunity here: presumably some kind of incremental approach could be of practical benefit because\ adjacent layers are likely to be similar to each other.

We need to be thinking in the range of 100ms or so per graph (which would add like 3 minutes to the slicing time for a big model of 1000 layers, assuming 2 graphs per layer). I'm not sure if users would even want to wait 3 minutes for it to give possibly a shorter maximum travel distance for some of the layers though.

That's fair enough, though I think that for big, complex prints the time saving in travel alone is likely to be far in excess of 100ms/layer.

If you want to look into this, you need to look at the PathOrderOptimizer class. I'm curious for ideas to improve the results, even if it doesn't completely solve the problem. We're looking for a solution that marginally impacts performance (though some performance hit is probably acceptable), improves print quality (even a little) and is not too complex to maintain.

Thanks. I think the first step would be to add a headless regression test on a common set of STLs to work out just how bad the problem is and track progress over time. Is there something like that already?

[Ghostkeeper]

though I think that for big, complex prints the time saving in travel alone is likely to be far in excess of 100ms/layer.

We consider active user time (like waiting for a slice to complete) to be 2 orders of magnitude more important than inactive user time (like waiting for a print to complete).

I think the first step would be to add a headless regression test on a common set of STLs to work out just how bad the problem is and track progress over time. Is there something like that already?

We have some tooling in place within the Cura team that does this; analyse g-code with a build and get statistical information about the command density, printing times and material usage. That way we get notified of statistical anomalies. However it is not a tool that is made to be shared outside of Ultimaker I'm afraid. (And we have also yet to automate calling it.)

A Python port of the time estimation algorithm is here: https://github.com/Ultimaker/Cura/blob/master/scripts/check_gcode_buffer.py (or see the C++ implementation in CuraEngine). However it is embedded in a different script. To get the time estimation of e.g. only travel moves you'd need to extract those and only count those. We know from experience that travel moves are usually 0-2% of the total printing time, sometimes up to 5% for extreme prints. I don't really know any statistics of the longest travel move in a print or layer.