REST: Constructing Rectilinear Steiner Minimum Tree via Reinforcement Learning

Rectilinear Steiner Minimum Tree (RSMT) is the shortest way to interconnect a net’s n pins using rectilinear edges only. Constructing the optimal RSMT is NP-complete and nontrivial. In this work, we design a reinforcement learning based algorithm called REST for RSMT construction. After training, REST constructs RSMT of $\leq 0.36\%$ length error on average for nets with $\leq 50$ pins. The average time needed for one net is fewer than 1.9 ms, and is much faster than traditional heuristics of similar quality. This is also the first successful attempt to solve this problem using a machine learning approach.