@inproceedings{488b3d6d404646a08ab1504ba4ce0c5f,
title = "A Reinforcement Learning Agent for Obstacle-Avoiding Rectilinear Steiner Tree Construction",
abstract = "This paper presents a router, which tackles a classic algorithm problem in EDA, obstacle-avoiding rectilinear Steiner minimum tree (OARSMT), with the help of an agent trained by our proposed policy-based reinforcement-learning (RL) framework. The job of the policy agent is to select an optimal set of Steiner points that can lead to an optimal OARSMT based on a given layout. Our RL framework can iteratively upgrade the policy agent by applying Monte-Carlo tree search to explore and evaluate various choices of Steiner points on various unseen layouts. As a result, our policy agent can be viewed as a self-designed OARSMT algorithm that can iteratively evolves by itself. The initial version of the agent is a sequential one, which selects one Steiner point at a time. Based on the sequential agent, a concurrent agent can then be derived to predict all required Steiner points with only one model inference. The overall training time can be further reduced by applying geometrically symmetric samples for training. The experimental results on single-layer 15x15 and 30x30 layouts demonstrate that our trained concurrent agent can outperform a state-of-the-art OARSMT router on both wire length and runtime.",
keywords = "monte carlo tree search, obstacle-avoiding rectilinear steiner tree, reinforcement learning, steiner point prediction",
author = "Chen, {Po Yan} and Ke, {Bing Ting} and Lee, {Tai Cheng} and Tsai, {I. Ching} and Kung, {Tai Wei} and Lin, {Li Yi} and Liu, {En Cheng} and Chang, {Yun Chih} and Li, {Yih Lang} and Chao, {Mango C.T.}",
note = "Publisher Copyright: {\textcopyright} 2022 ACM.; 31st ACM International Symposium on Physical Design, ISPD 2022 ; Conference date: 27-03-2022 Through 30-03-2022",
year = "2022",
month = apr,
day = "13",
doi = "10.1145/3505170.3506721",
language = "English",
series = "Proceedings of the International Symposium on Physical Design",
publisher = "Association for Computing Machinery",
pages = "107--115",
booktitle = "ISPD 2022 - Proceedings of the 2022 International Symposium on Physical Design",
}