Adventures in Autorouting (2017)
wp.josh.com
wp.josh.com
The reason this is very interesting problem is that basic version of the problem is fairly easy to specify: You are given bunch of polygons, each with few fixed points on it. You are also given series of sets, each containing list of points that must be connected together. Can you come up with connections that has minimum crossing with each other (see Wikipedia [1] for more formal statement of routing problem).
The more practical version of the problem will include more constraints to make sure the design meets timing, has no crosstalk problems, meets any metal density requirements, does not suffer from antenna effects, and so on.
Recently Travelling Salesman Problem was attacked using reinforcement learning[2] and that could be a good start to attack routing problem. I'll be definitely looking in to this!
[1] https://en.wikipedia.org/wiki/Routing_(electronic_design_aut...
Also, for some sensitive designs (boost, buck, high speed clock, memory interface etc) you definitely don't want and autorouter doing it, at least the ones that are available to hobbyists.
Would it be a time saver, sure. But for a board like that, we're talking ~15 minutes of saved time. There are much better optimizations to be made (standardized parts libraries) that would save way more time.
The author makes a strong point in comparing the autorouting problem to the milestone achieved by Alpha Go in defeating some of the strongest human players. These problems are similar enough that the same insights are likely applicable to both.
The first time I ever heard the phrase "Monte Carlo tree search," it took me about five seconds for me to start wondering if it might be applicable to PCB routing.
Sure, but if a tool can't route a trivial board like the author had, what hope does it have for doing complex designs?
On a related note, pick up an old arcade game board from the 70's or 80's made by Atari. They're all double sided and are very cleanly routed. The Cinematronic CPU made from 74xx series parts is also double sided and very cleanly routed. In both cases though there is a lot of area not covered by components, but they're still works of art.
He's complaining about how autorouters have trouble with trivial boards like the one he was working with. He's pointing out that this is costing the industry a lot of time and money. He's asking why the problem remains largely unaddressed, at a time when computers running relatively generic tree-search algorithms with minimal prior training are beating 9-dan Go players like rented mules.
By trying to call the attention of ML/AI researchers to the issue, he's doing a good thing IMO. No one disputes that a well-routed PCB is a work of art, whether it was done with Altium or rubylith. But it shouldn't be.
I applaud him for pointing out how bad most of them are and asking the question why they suck when machines can play GO now.
That's the point of the article. It should be worth the time. The author feels that after layout it shouldn't take any time to layout the board. Single click and done.
Double sided PCBs costs almost same as single sided however going from 2 layer to 4 layer literally doubles the cost. Going from 4 layers to 6 layers increases cost by 50%. For boards like Raspberry Pi or Arduino, this could make massive difference if you doing production at scale.
So the problem is very real.
Professional tools like Altium, Allegro, etc. have really good interactive routing tools, and some pretty cool semi-automatic routing tools where you select groups of nets, plot an approximate routes, and it works out the finer details. This can make routing busses and stuff almost as fast as routing single tracks.
Secondly, sometimes dropping layers isn't an option - given EMI/EMC requirements you're going to need a ground plane in almost all high speed designs (anything over a couple of hundred hundred MHz). So for a lot of designs, four layers is the minimum. Add in impedance control, or RF, and you might need to go to eight (RF microstrip always needs to be next to a ground plane, or stripline needs one above and one below. So you can end up needing a lot of layers especially once you add in power planes).
At the end of the day, it's a trade-off between lots of different factors, and I don't think (for any skilled professional) that the quality of the route would really come into it much...
Autorouters meet all physical rules, while violating all electrical rules. Manual routing with the application of push and hug (semi-auto) routing is the way to go. No one just pushes an autoroute button.
My current project uses a physically large but relatively simple board, and I've spent probably a total of two weeks' worth of time hand-routing all of the various iterations in KiCad. It's not difficult once you come up with some basic heuristics, but I sure wouldn't object to having those two weeks back. Even something as simple as the EagleCAD autorouter I used back in the early '00s would have been fine for most of it.
Then, once the autorouter has successfully routed everything, I tear it up and do hand routing. There's still a few placement tweaks that happen at this stage (considering things like analog vs. digital traces, EMC for clocks/high speed data lines, etc) but I know I'm starting from a reasonable base.
BTW nobody professional uses curved traces (except very rare cases), have a look at any electronics PCB
When traces where done by hand, they used to be curved and flowing, and frequently looked very elegant. And occasionally you see a super high speed design that’s a bit curvy today.
I think curved traces were used make layout easier when running tape. Bending the tape is easier than doing a cut to shift the trace over.
And safer, a problem with old tape layouts is it's easy enough to knock off a small section of tape. Old draftsman I worked with would check the layout against a blue print on a light table to make sure nothing was amiss before making mods. He also got really antsy if anyone was rummaging around in the drawers holding PCB layouts.
But there are good autorouters. Back in the 90s I had a license to PADS, so I had access to Specctra and then Blaze. I still use the version of Blaze I bought then (originally for Windows-98) today. It used for my relay computer:
http://relaysbc.sourceforge.net/
It routes the entire board in about two minutes.
Unfortunately these tools are now very expensive ($6000).
Comparing to other routers, Topor gives results almost instantaneously. This is really useful when placing parts: you try something, autoroute (no more than tens of seconds), see result, tweak here and there then repeat.
idk about seriously big boards, but they have examples with mammoth BGA on their site, so at least it is capable of routing those boards.
I think, the first show-stopper for 100% autorouted designs are power nets (of course, not only power, there are a lot of other corner cases, like thermals, but power is what you encounter right out of the door).
Router should know which nets handle (somewhat)high currents. And which direction the current flows. You do not want your power amp supply rail routed sequentially. And on the other side, not all power nets should be routed as stars (sometimes there is only small power draw, and sometimes it is only voltage sensing).
I keep wanting to design PCBs pretty much just so I can do the routing! That's for small, two-layer PCBs, though. If you had to do eight layers on a huge PCB, I can see how you wouldn't want to be bothered.
I used it as a 'first pass' routing, imported the result, deleted anything I didn't like and manually did the rest. Still saves a bundle of time!
But, given the autorouting problem's NP hardness, especially when there are extra constraints like above, I expect that manual routing for anything beyond trivial layouts will continue to be the norm.