Circuit Routing Using Monte Carlo Tree Search and Deep Neural Networks
  Circuit routing is a fundamental problem in designing electronic systems such
as integrated circuits (ICs) and printed circuit boards (PCBs) which form the
hardware of electronics and computers. Like finding paths between pairs of
locations, circuit routing generates traces of wires to connect contacts or
leads of circuit components. It is challenging because finding paths between
dense and massive electronic components involves a very large search space.
Existing solutions are either manually designed with domain knowledge or
tailored to specific design rules, hence, difficult to adapt to new problems or
design needs. Therefore, a general routing approach is highly desired. In this
paper, we model the circuit routing as a sequential decision-making problem,
and solve it by Monte Carlo tree search (MCTS) with deep neural network (DNN)
guided rollout. It could be easily extended to routing cases with more routing
constraints and optimization goals. Experiments on randomly generated
single-layer circuits show the potential to route complex circuits. The
proposed approach can solve the problems that benchmark methods such as
sequential A* method and Lee's algorithm cannot solve, and can also outperform
the vanilla MCTS approach.
