Deep reinforcement learning on 1-layer circuit routing problem

Abstract

In VLSI design, routing is the step that determines the paths for circuit nets and interconnections. While routing can be a very complex process involving time, congestion and space information, the problem can be modelled as a maze routing problem. In specific, given a 2d array and a set of start nodes and end nodes, the agent is trying to optimize the solution by connectivity and path length. Traditionally, the routing problem is solved using graph search techniques such as Lee’s algorithm. The result produced by graph search algorithms relies heavily on the order of routing. While some simple heuristics are available, the result is not stable because simple heuristics take greedy approaches and neglect the long-term reward. The recent development of deep learning, especially deep reinforcement learning, can be a good approach to finding better ordering on attacking the routing problem. We introduce a reinforcement learning approach to the traditional 2-point nets in 1-layer maze routing problem.