LaserWeb
Using TSP on gcode?
@tbfleming how do you see the possibility of using Travelling Salesman on the generated GCODE?
Here is way to do using WEBGL acceleration! https://amoffat.github.io/held-karp-gpu-demo/?gpu=1
That demo limits the GPU solver to 16 nodes. We'd need hundreds. If it can solve hundreds in short time then it'd be worth considering. I suspect (I haven't checked for certain) that GPU code can't run on workers.
Yes, I've been looking for a ready-to-use lib but I found nothing. The most promising in my opinion are (non-gpu) http://parano.github.io/GeneticAlgorithm-TSP/ and http://francisshanahan.com/tsa/tsaGAworkers.htm
Something to watch out for: we don't have a pure TSP formulation. Instead of nodes we have:
- Open paths: 2 endpoints. TSP has to decide which endpoint to enter and which to exit.
- Closed paths: TSP has to decide which point on the loop should be the entry point. It will also be the exit point.
A fully optimized TSP approach might have no obvious way to extend it to handle our case.
We can use a predefined coordinate (like homing location) as the origin? It's naive but maybe good for a first approach?
Hmm there's some work done on gcodes http://xyzbots.com/gcode-optimizer/
Some months ago I wrote a simple but very effective gcode optimizer that in my case drastically cutted the useless G0 move. I implemented this in LaserWeb3, but I've never pushed it to upstream (https://github.com/Biondilbiondo/LaserWeb3). If you like it I'll be happy to implement it in laserweb 4. In my work i don't use the a real solution to the TSP problem that is quite complicate and CPU (or GPU) intensive (also in euristhic approach, see as example one of the best program to solve the tsp as far as I know http://www.math.uwaterloo.ca/tsp/concorde.html) task but I simply apply a nearest neighbor search that gives a path that is not the optimal one but is much better then default one (at least in laserweb3, that just takes the paths in the same order as in the svg file). If you like this kind of work please help me to find the place where the optimizer should be implemented ( i suppose somwhere in the cut function of cam.js?) Biondilbiondo
@Biondilbiondo thanks for your support! But seems there's a NN algorithm indeed as @tbfleming says.
I've found another one https://github.com/lovasoa/salesman.js and looks promising.
@tbfleming can you take a look on this? https://github.com/alsliahona/gcode-optimizer
@jorgerobles https://github.com/alsliahona/gcode-optimizer does nearest neighbor.