An optimized 3D Astar algorithm for multi-layer PCB automatic routing

Printed circuit board (PCB) automatic routing is a multi-objective optimization problem that involves higher routability, shorter wire length, less via count, and so on. Some algorithms have been proposed for PCB automatic routing. However, existing methods cannot meet the various electrical constraints in industry. In this work, we propose an optimized 3D Astar algorithm which takes real constraints into account for multi-layer PCB automatic routing. Our 3D Astar algorithm extends the search dimension of traditional Astar algorithm to 3D and improve the distance function. To verify the performance of the proposed algorithm, experiments are carried out on the benchmark based on real PCB designs. Experimental results show that our proposed algorithm achieves more than 95% routability and has a significant improvement in terms of via count compared with traditional 3D Astar algorithm.