Tensorflow based autorouter


#6

Interesting… I’ve had an idea for a while to augment a classical expansion room-based autorouter (google: Alan Finch’s paper on autorouting) where topology and via locations are picked by a neural network trained on human-drawn layouts. Except I know next to nothing about tensorflow :wink: Anybody here willing to help?

Tom


#7

Well if they pulled it off they would no longer have a job!


#8

Ah, so they can do it, they are just courteously waiting for someone else to put them out of a job and get all the money while doing it. Out of kindness of their hearts, I presume.

In all seriousness, I’m not bashing on the idea. Using AI probably has potential and there is a good chance that it’s not done yet because the AI only recently became widely adopted and not because it just doesn’t work well for routing.
Good luck to you, just be prepared that this is not an easy problem.


#9

I don’t think auto routing would put any one out of a job. I spend most of my time setting the schematic up.


#10

Based on my experience with various autorouters and with the latest in automated manual routing (sometimes called “intelligent routing”), I think the latter approach is way more interesting to pursue. Humans are just too good at figuring out roughly how things should flow around, so the ideal tool (in my opinion) allows the humans to guide the system, and the software can fill in the details and do all the detail work.

For an example of where high-end proprietary tools are going along these lines, check out this video from Xpedition. The high-end ECAD vendors are doing a lot of R&D into these algorithms because the productivity gain and quality is way higher than with a traditional autorouter (which typically requires lots of careful tuning to get results anywhere near as good as a human could do).


#11

Even simple things like smarter hug routing or gloss/retracing would be fantastic to assist hand routing - it really is a sliding scale where there is a lot more intelligent help from the software in reducing labour. (That was a cool video :slight_smile: )


#12

If your training an AI, don’t forget you will need a very good scoring system in place, this tends to be what hurts to programmers the most,

Then there is the fact Kicad at present does not expose easy ways to define things like track current or impedance, e.g. this track is 50 ohms, this other track is very sensitive to signals, and this track is carrying a pulsed 8A signal,

Its actually quite easy to calculate structures like a 50 ohm via feed to the other side of the board, its hard if it doesnt have ways to nudge it so more stuff can fit later,

The human method will tend to be group parts into clusters with the least unique nets between them, then begin routing out those groupings, then figuring out how to nudge them to fit into the whole board, or atleast thats is how I approach it most times,

By having the least unique nets between groupings and knowing what traces are to be treated specially, its generally just nudging and rotating to make it join up with the surrounding segments

Heck if you want PM me and I can share some very cramped layouts that I would love to see how a competent auto router could manage.


#13

This looks like a neat way:

From here https://www.altium.com/documentation/18.0/display/ADES/((ActiveRoute))_AD


#14

I researched the topic a bit and also concluded that interactive auto-routing tools should be the most useful ones for practice. There is a nice article about that topic:

Some example how the Sketch Router works for example:


I did some literature research, and it seems there are two main domains where active research in this direction is done: escape routing and length-matching routing. Basically the escape router ensures that there are no crossings of wires, and the length-matching router ensures that the two components are connected (without track crossing) and signal-delays are enforced.

I found already some literature. Be warned, many of those links are behind a paywall (unless you are at a university)

Some general literature

Specific algorithms

this is the interesting part, to gather a number of recent algorithms and look which of them are easy to implement / powerful / fast,…

Escape Routing

Length-matching Router

Layer assignment

Bus-Planner

Net ordering

Topological Router


Personally, I would like to see some bigger literature research and a classification of those algorithm, to find out which of them could be useful for inclusion when someone steps in implementing an “autorouter”.


#15

Routing a design is a relatively easy job. It turns out that placing the components is much harder and a job that experienced humans are much better at than software.


#16

I would love to write a sketch router for KiCad. Anybody willing to help? :smiley:


#17

I love too help with my spear time.


#18

I want to help if I can :slight_smile:


#19

Choosing the machine learning library you want to use (because it’s cool and shiny) before understanding the nature of the problem is a classic X-Y situation. I work every day with people who build AI systems and the hard problems are not the code, they are designing the features, scoring, training, and evaluating the results. Even using a neural net which derives its own features only addresses one aspect of the problem.

Combined with the points made above about KiCad not having information about the constraints, this would be a very challenging project.


#20

Auto router is a lot like symbol and footprint libraries. Their main (but clearly not only) function is to take the stress off of newbies learning the software because it is a steep learning curve. No way around that. That isn’t an insignificant consideration though as open source projects life blood is new users. I spent way too much time figuring out how to get freeroute to work only to turn around and never use it.

In short, I’d implement a reliable, easy to use version as a first goal.


#21

I would love to write a sketch router for KiCad.

Very nice feature. What’s your ideas on how to fit it in the existing UI?

Maybe the simplest starting implementation for this feature would by to find pads/vias within some distance from starting and ending points of sketched line, then intersect two sets of nets and try to connect them so that it would resemble the line drawn.

Tricky part here is if one tries to route a bus (for example SPI) from MCU to several slave nodes the traces might start twisting all over the pcb like crazy, probably need to limit traces length difference somehow.


#22

This aspect might become easier with the planned implementation of smarter busses in Eeschema. Once that gets hammered out, make room in the PCBnew data model for that information for a bus based autorouter to recognize similar grouping and apply impedance matching and line length rules.


#23

@davidsrsb I agree in part; the auto-routing problem isn’t just the routing part, it is placement + routing. The problem I have with “experienced humans are much better at…” is that this is a true statement considering the current state of the art, not the future state. Most (all?) inventions started out rather humbly and did not greately enhance ones abilities or comfort. But it is the continuously nibbling away at the hard edges that makes the big difference.

In my opinion, placement and routing is a boring boring job. Yes, for small designs and if not done too often it can feel therapeutic but repetion boredom sets in quickly. Additionally, mistakes can be costly. That combo is an ideal job for an algorithm. All such problems eventually are done automatically. So therefore, I’d say this is teritory for development.

However, I cannot quite agree with @threelegs to use Tensorflow. It might be the right tool, or it might not; the tool should not pick the problem. I think it would be great to work on clearly working out the problem domain, stating the most ideal outcome and working how to get from a to b. I dont think this is a “lets throw Tensorflow at it and look its solved” problem.


#24

I have put a lot of thought into it and I think what I really want is a vertically integrated system between the PCB layout and the schematic. I get the best layouts when I move the pin configuration around on MCUs and other components with generic pins. What we need is a “sticky” label that you can toggle if it can be moved to another pin on the component depending on the placement of the components on the PCB. This would vastly improve any auto routers performance.


#25

Thanks for your detailed post!