search

storborg / axibot

Headless control software for the AxiDraw pen plotter.
http://axibot.readthedocs.io/
GNU General Public License v2.0
31 stars 8 forks source link

Integrate networkx TSP solver for pen-up travel optimization #24

Open storborg opened 7 years ago

storborg commented 7 years ago

I played around with this a bit and it doesn't seem worth it. On most files (particularly those with long plot times) the opportunity to optimize pen-up travel time is insignificant compared to other things, namely pen servo move time and the pen-down speed calculation. I'm going to punt this.

nornagon commented 7 years ago

I've been playing with the TSP solver in Google's or-tools and I've been finding ~50% plot time improvements. Could you share more about your process? I'm curious why we find such different results!

storborg commented 7 years ago

At first glance, I suspect that has to do with the specific SVG artwork. An improvement of 50% in plot time must mean that that the pen-up travel time is somewhat over 50% of the total time, which is somewhat surprising. For example, here's some of the "travel time" percentages I grabbed from my axibot scratch directory:

If you've found some good results, though, I'd be excited to see if we could integrate that without making the dependency situation difficult, so I'm going to re-open this for now.

nornagon commented 7 years ago

https://dl.dropboxusercontent.com/u/2894623/voronoi-circles-explode.svg

Without TSP optimization (just svg.sort_paths):

INFO:axibot.planning:Loading ../plotter/control/voronoi-circles-explode.svg...
INFO:axibot.planning:Extracting paths...
INFO:axibot.planning:Planning segments...
INFO:axibot.planning:Adding pen-up moves...
INFO:axibot.planning:Converting inches to steps...
INFO:axibot.planning:Planning speed limits...
INFO:axibot.planning:Planning actions...
INFO:axibot.cmd:Number of moves: 95332
INFO:axibot.cmd:Expected time: 1 hour, 34 minutes, 49 seconds
INFO:axibot.cmd:  Pen servo: 40 minutes, 12 seconds
INFO:axibot.cmd:  XYMove (pen up): 24 minutes, 47 seconds
INFO:axibot.cmd:  XYMove (pen down): 29 minutes, 49 seconds

With TSP optimization:

INFO:axibot.planning:Loading ../plotter/control/voronoi-circles-explode.svg...
INFO:axibot.planning:Extracting paths...
[10:11:28] src/constraint_solver/search.cc:240: Start search (memory used = 111.46 MB)
[10:11:43] src/constraint_solver/search.cc:240: Root node processed (time = 14501 ms, constraints = 48073, memory used = 1474.04 MB)
[10:14:15] src/constraint_solver/search.cc:240: Solution #0 (151365, time = 166461 ms, branches = 9648, failures = 1, depth = 33, memory used = 1479.96 MB, limit = 100%)
[10:14:18] src/constraint_solver/search.cc:240: Finished search tree (time = 169544 ms, branches = 9648, failures = 35, memory used = 1479.97 MB)
[10:14:18] src/constraint_solver/search.cc:240: End search (time = 169768 ms, branches = 9648, failures = 35, memory used = 765.45 MB, speed = 56 branches/s)
INFO:axibot.planning:Planning segments...
INFO:axibot.planning:Adding pen-up moves...
INFO:axibot.planning:Converting inches to steps...
INFO:axibot.planning:Planning speed limits...
INFO:axibot.planning:Planning actions...
INFO:axibot.cmd:Number of moves: 44619
INFO:axibot.cmd:Expected time: 39 minutes, 23 seconds
INFO:axibot.cmd:  XYMove (pen up): 5 minutes, 33 seconds
INFO:axibot.cmd:  Pen servo: 7 minutes, 4 seconds
INFO:axibot.cmd:  XYMove (pen down): 26 minutes, 45 seconds

I also added a call to svg.join_segments, because with TSP optimization, many pen_up/pen_down pairs are unnecessary (since there's no actual movement between the up and the down), which is why the pen servo time is cut by 3x also.

nornagon commented 7 years ago

https://www.youtube.com/watch?v=tgtn-JcRSYM is an example of some nice paths it came up with for a different file, too :)

nornagon commented 7 years ago

I found additional gains from allowing the solver to draw each path in either direction (start->end or end->start), by the AddDisjunction feature in or-tools's Routing library.

Code snippet: https://gist.github.com/nornagon/0a027561d0d7d0d2c319722e247e02f4

nornagon commented 7 years ago

or-tools a complete beast to install, though. It took me a couple of hours to get anything working, and I had to build from source because there's no binary distribution for modern OS X. I'm not sure how to tackle that for axibot. Perhaps it could test-import or-tools and use if available?