Distance/cost calculation for TravellingSalesman use in JobProcessor

[Jan]

Hi Mark!
Long time ago
(https://groups.google.com/g/openpnp/c/LyHnt_BmlZU/m/zn_N_L8gAwAJ) we
discussed the cost/distance calculation as part of the first multi
nozzle optimizations for the JobProcessor. In the mentioned post, you
suggested to use the square root of the distance as approximation or
even better use data from the backlash calibration. I'd like to
understand a) why the default cost calculation in the TravellingSalesman
class uses linear distance when we agree, that square root of distance
would provide a more realistic option for all our use cases and b) why
you suggested to use backlash calibration data when there seems to be
the Motion class providing even better results using just configured values?
For me it seems it's time to add a better distance/cost metric to the
JobProcessor for better multi nozzle optimizations. While preparing
that, I came across the Motion class, which is used by the motion planer
diagnostics to provide planed/expected cost/time. This seems like the
best choice to me as it provides quite comprehensive math taking
everything relevant into account.
In addition, the new/better cost metric would be primarily used via the
TravellingSalesman class (initially). So I'm wondering whether it would
be fair to add it there and just making it the default.
Finally the current TravellingSalesman implementation uses simulated
annealing to find the best path. It is called using maxIterations =
1000*size + 10000000 where size is the number of cities to visit. As far
as I can see, the TravellingSalesman class is only used for small
numbers of cities (size << 10), which would make a brute force solver
more efficient. Unfortunately I'm not big java guru to implement it
myself from scratch and did not found any useful hints on the net. Do
you by change have a brute force solver or a hint where to search that
could get me started?

Jan

[mark maker]

Hi Jan,

You could use the motion planner for estimates, but it becomes quite complicated that way and I seriously doubt it would be practical or even worthwhile.

You must realize how the solver works! It tries "gazillions" of mutations , each requiring a before and after cost estimate. So I doubt you can run the motion planner for each and every one of these mutations.

Note, that even the computation cost of the motion planner in normal operation is not trivial, especially if you use simulation 3rd order motion control. It is very easy to create a situation where takes longer to compute, than what it saves. I've seen some hefty times in your logs! And some of those times can't be assumed to happen while the machine still moves (i.e. in the background).

However, you could perhaps prepare a look-up-table with the motion planner (per axis). Make a table of distances, and interpolate between the two nearest values. You could also make such a table from the backlash calibration data.

Or you could content with the square root. Realize that the absolute times are not relevant, it just needs relative comparison. Yes, the square root would underestimate very long moves, but I don't see how this could realistically undermine a good planner result in the end.

>  In addition, the new/better cost metric would be primarily used via the TravellingSalesman class (initially). So I'm wondering whether it would be fair to add it there and just making it the default.

Not sure what you mean. Where the Java code resides? Then yes.

> Finally the current TravellingSalesman implementation uses simulated annealing to find the best path. It is called using maxIterations = 1000*size + 10000000 where size is the number of cities to visit. As far as I can see, the TravellingSalesman class is only used for small numbers of cities (size << 10), which would make a brute force solver more efficient.

For your nozzle move calculations, yes. But elsewhere, no. 

See also my other mail about sort order, where you would add each feeder pick location, or see the global BlindsFeeder fiducial vision calibration and cover opening, or the global PushPullFeeder vision calibration and OCR/QR part detection  😉. There could be many, many feeders to visit. Brute force computation goes up with the factorial:

0     1
1     1
2     2
3     6
4     24
5     120
6     720
7     5040
8     40320
9     362880
10     3628800
11     39916800
12     479001600
13     6227020800
14     87178291200
15     1307674368000
16     20922789888000
17     355687428096000
18     6402373705728000
19     121645100408832000
20     2432902008176640000

Also note that the "default heuristics" are just that. You can override them, or you can invest more brain power into better formula for the default (when I made it for the BlindsFeeder cover opening, it was not that important). For very small paths, I guess you can reduce that number drastically, without having to resort to a real brute force solver.

_Mark