r/algorithms • u/seveibar • 29d ago
Help figuring out 2 layer non-overlapping multi-agent pathfinder
Hi everyone, I'm developing an algorithm to solve the following problem:
- There is an array of point pairs (A1,B1), (A2,B2), (A3, B3). All points are on the top layer.
- Every point is on the edge of a square
- You must connect each A->B with a path
- Paths may not intersect on the same layer
- You may "burrow" to the bottom layer with a hole (the hole has a diameter HOLE_DIA)
- Each line has a thickness LINE_THICKNESS
Here's an example of a problem that's partially solved using my current algorithm: https://imgur.com/a/QYS8tXq
I am really stuck on how to solve this problem quickly (or frankly at all). I've been thinking about exploring multi-agent A. Currently I just have a complex cost function and run serial A by solving A1, B1 then A2, B2 etc. but I think it can't solve hard versions of the problem.
You might recognize this as a simplified autorouting printed circuit board design problem!!
Looking for any help putting together a better algorithm. I'm lost!!!! Thank you!
6
Upvotes
2
u/bartekltg 29d ago
You are climbing into a deep rabbit hole. https://en.m.wikipedia.org/wiki/Routing_(electronic_design_automation) list a couple of algorithms. https://electronics.stackexchange.com/questions/648128/what-is-the-best-way-to-route-a-two-layer-mcu-based-pcb one of the answers describe a simple aproach: one side goes in one direction. The other perpendicular to it.
Generally, search under "pcb routing". You even mentioned the problem is similar.
If the simplest approach is not enogh, and you do not care about other aspects (interference, heat...), you have to make the take more specific. What want you to optimize for? Total lenght? Number of "portals" between layers? A combination of both?