NeuroEscape: Ordered Escape Routing via Monte-Carlo Tree Search and Neural Network

Zhiyang Chen, Tsung Yi Ho, Ulf Schlichtmann, Datao Chen, Mingyu Liu, Hailong Yao, Xia Yin

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

Abstract

Ordered escape routing is a critical stage for printed circuit board design. State-of-the-art solutions to ordered escape routing are either heuristic and non-optimal, or trapped in exponential time complexity. In this work, for the first time, we prove that ordered escape routing is not only NP-hard, but also hard to approximate in polynomial time, indicating the limitation of optimal algorithms. We further present NeuroEscape, an efficient ordered escape routing method, which is based on reinforcement learning with a Monte-Carlo tree search (MCTS) and heuristic rollouts for design space exploration. A neural policy model is incorporated to further enhance the MCTS process. Theoretical results show that the number of samples required to train the model is upper bounded by a polynomial. Experimental results show that NeuroEscape solves 69% more testcases, with an average acceleration of 19.4x compared with state-of-the-art methods.

Original languageEnglish
Title of host publication2023 42nd IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2023 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9798350315592
DOIs
StatePublished - 2023
Event42nd IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2023 - San Francisco, United States
Duration: 28 Oct 20232 Nov 2023

Publication series

NameIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
ISSN (Print)1092-3152

Conference

Conference42nd IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2023
Country/TerritoryUnited States
CitySan Francisco
Period28/10/232/11/23

Keywords

  • Monte-Carlo tree search
  • Neural network
  • Ordered escaped routing

Fingerprint

Dive into the research topics of 'NeuroEscape: Ordered Escape Routing via Monte-Carlo Tree Search and Neural Network'. Together they form a unique fingerprint.

Cite this