论文标题
使用蒙特卡洛树搜索和深神经网络的电路路由
Circuit Routing Using Monte Carlo Tree Search and Deep Neural Networks
论文作者
论文摘要
电路路由是设计电子系统（例如集成电路（IC）和印刷电路板（PCB）等电子系统的基本问题，这些电路板（PCB）构成了电子和计算机的硬件。就像在位置对之间找到路径一样，电路路由会生成电线的痕迹，以连接电路组件的触点或导线。这很具有挑战性，因为在密集和大规模电子组件之间找到路径涉及一个非常大的搜索空间。现有的解决方案要么是用域知识手动设计的，要么是针对特定设计规则量身定制的，因此很难适应新的问题或设计需求。因此，一般的路由方法是高度期望的。在本文中，我们将电路路由作为顺序决策问题进行建模，并通过蒙特卡洛树搜索（MCT）用深神经网络（DNN）引导的推出来解决它。它很容易扩展到具有更多路由限制和优化目标的路由案例。在随机生成的单层电路上进行的实验表明了路由复杂电路的潜力。所提出的方法可以解决基准方法（例如顺序A*方法）和Lee算法无法解决的问题，并且还可以优于Vanilla MCT方法。
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.
