Ranking Cost: Building An Efficient and Scalable Circuit Routing Planner
  with Evolution-Based Optimization
  Circuit routing has been a historically challenging problem in designing
electronic systems such as very large-scale integration (VLSI) and printed
circuit boards (PCBs). The main challenge is that connecting a large number of
electronic components under specific design rules involves a very large search
space. Early solutions are typically designed with hard-coded heuristics, which
suffer from problems of non-optimal solutions and lack of flexibility for new
design needs. Although a few learning-based methods have been proposed
recently, they are typically cumbersome and hard to extend to large-scale
applications. In this work, we propose a new algorithm for circuit routing,
named Ranking Cost, which innovatively combines search-based methods (i.e., A*
algorithm) and learning-based methods (i.e., Evolution Strategies) to form an
efficient and trainable router. In our method, we introduce a new set of
variables called cost maps, which can help the A* router to find out proper
paths to achieve the global objective. We also train a ranking parameter, which
can produce the ranking order and further improve the performance of our
method. Our algorithm is trained in an end-to-end manner and does not use any
artificial data or human demonstration. In the experiments, we compare with the
sequential A* algorithm and a canonical reinforcement learning approach, and
results show that our method outperforms these baselines with higher
connectivity rates and better scalability.
