A Reinforcement Learning Agent for Obstacle-Avoiding Rectilinear Steiner Tree Construction

Po Yan Chen, Bing Ting Ke, Tai Cheng Lee, I. Ching Tsai, Tai Wei Kung, Li Yi Lin, En Cheng Liu, Yun Chih Chang, Yih Lang Li, Mango C.T. Chao

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

9 Scopus citations

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.

Original languageEnglish
Title of host publicationISPD 2022 - Proceedings of the 2022 International Symposium on Physical Design
PublisherAssociation for Computing Machinery
Pages107-115
Number of pages9
ISBN (Electronic)9781450392105
DOIs
StatePublished - 13 Apr 2022
Event31st ACM International Symposium on Physical Design, ISPD 2022 - Virtual, Online, Canada
Duration: 27 Mar 202230 Mar 2022

Publication series

NameProceedings of the International Symposium on Physical Design

Conference

Conference31st ACM International Symposium on Physical Design, ISPD 2022
Country/TerritoryCanada
CityVirtual, Online
Period27/03/2230/03/22

Keywords

  • monte carlo tree search
  • obstacle-avoiding rectilinear steiner tree
  • reinforcement learning
  • steiner point prediction

Fingerprint

Dive into the research topics of 'A Reinforcement Learning Agent for Obstacle-Avoiding Rectilinear Steiner Tree Construction'. Together they form a unique fingerprint.

Cite this