Tensorflow based autorouter

Layout Footprints
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).

2 Likes
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:

RouteGuide_18.gif800×512 1.38 MB

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

1 Like
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:

https://www.electronicdesign.com/what-s-difference-between/what-s-difference-pcb-routing-then-and-now

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”.

11 Likes
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.

4 Likes
16

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

3 Likes
17

I love too help with my spear time.

18

I want to help if I can :slight_smile:

1 Like
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.

3 Likes
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.

1 Like
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.

2 Likes
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!

26

for autoplacement, the smartest way you could probably begin it would be singling out what groups of components have the most unique interconnections, pretty much if an IC has 40 passives that mostly connect to this IC and 2 voltage rails, you can begin clustering those components to reduce the total amount of traces that will have to traverse the rest of the board.

27

the behaviour from your Pads video is very close to the CERN efforts for interactive push and shoove. Pads PCB is the small sister from Mentors Xpedition PCB. The push & shoove algorithm is from a russian programmer who sold the code to Veribest in about 1996. Veribest integrated this in a product called “advanced router” what nothing did but interactive routing. Later the complete tools kicked out the Bentley Microstation universal CAD (what was required for that plugin) to build the Xpedition toolsuite. In first years the interactive push & shoove was awfull instable and caused crashes all few minutes probably becouse of heap/stack allocation bugs. From about 2003 the feature went stable and PCB sold as Pinnacle without Microstation. Later Mentor aqcuired PADs becouse of the shocking license fees for the big toolset and finally it copied the interactive push and shoove also to the small sister.

I am going to make a video from further push and shoove capabilities with components and traces. Even todays Altium cannot shoove traces by pushing components and vice versa. Moving a component like balls on the billiard table is still a missing interactive feature more worth than any autorouter (and autoplacement) feature. In comparison to chess algorithms, routing algorithms seems less developed. I am using high end routers for over 30 years but prefer interactive routing for best results. Most time I do the joke: When design finished 100% by interactive routing, I delete all traces and start the autorouter. There is rarely over 80% when autorouter ends. All autorouters I know, depend from preferable trace direction per layer. With interactive routing, most time I do not respect that rules, mainly at boards edge. For time critical projects a good attempt is finishing up to over 90% or less than 50 open traces, then start the autorouter for finishing. Most time autorouters finish the remaining lines much faster than interactive routing. The lower quality of those lines (e.g. more vias used) does not hurt much for the end stage of design but blocks progress in early stages

I doubt that AI helps for routing becouse rules for routing are well known in comparison to typical AI things like face recognition or music track separation. Learning a neuronal net would required to feed too much sucessfull layouts and too much associated electronics and functional background knowledge for the design what even human cannot recognize only watching the board. Best way to practice routing for humans is to start with a single layer design only using variable length wire jumpers. This sharpens view for the problems with lower complexity. Later moving to double layer design will finish most things using the new layer. Thats what we did former times with pencil and paper. What todays autorouters seems missing, is a continiued weighting of existing rules in dependance of several complex but well described environement situations of the board. There are certain situations where the efforts to solve next open line increase by square instead linear. From this moment it can bee foreseen that nothing ends successfull and strategy should be changed.

Efforts for autoplace seems futil. There are too much rules to announce e.g. for connectors or poti and more mechanical restraints. High end tools have this but I never used. Maybe AI is a good trick to sell any licenses to unexperienced pcb desingers but that feature seems not useful for Kicad. Good interactive features will be much faster until I see something commercial to convice me

5 Likes
28

Very much agree on this one, if is placed well, routing will be made much easier. Space is usually the constraint to allowing a good functional placement. Some rules need to break and bend to allow things to happen.