{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/102796"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/102796","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Zhang, Yihao"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Wong, Martin D.F."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2019,"date_issued":"2019-02-07T20:35:58Z","date_published":"2019-02-07T20:35:58Z","updated_at":"2026-07-22T22:24:42Z","subjects":["Maze routing","Reinforcement Learning"],"languages":["en"],"rights":["Copyright 2018 Yihao Zhang"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/102796","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Wong, Martin D.F."]},{"key":"dc:creator","label":"Author","values":["Zhang, Yihao"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2019-02-07T20:35:58Z","2021-02-08T10:15:22Z","2018-11-19","2018-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Maze routing","Reinforcement Learning"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2018 Yihao Zhang"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/102796"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2020-12-01","The student, Yihao Zhang, accepted the attached license on 2018-11-18 at 21:45.","The student, Yihao Zhang, submitted this Thesis for approval on 2018-11-18 at 21:53.","This Thesis was approved for publication on 2018-11-19 at 11:19.","DSpace SAF Submission Ingestion Package generated from Vireo submission #13096 on 2019-02-07 at 14:17:35","Made available in DSpace on 2019-02-07T20:35:58Z (GMT). No. of bitstreams: 2 ZHANG-THESIS-2018.pdf: 1165716 bytes, checksum: b71ab8430810ebde221c29df6a229309 (MD5) LICENSE.txt: 4208 bytes, checksum: f48a24f10be1d5b9a034c7df3e966ca9 (MD5) Previous issue date: 2018-11-19","Embargo set by: Seth Robbins for item 109820 Lift date: 2021-02-07T20:36:09Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 109820 Lift date: 2021-02-07T20:39:46Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 109820 Lift date: 2021-02-07T20:44:35Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 109820 on 2021-02-08T10:15:22Z."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Deep reinforcement learning on 1-layer circuit routing problem"]}]}],"canonical_facts":{"dc:contributor":["Wong, Martin D.F."],"dc:creator":["Zhang, Yihao"],"dc:date":["2019-02-07T20:35:58Z","2021-02-08T10:15:22Z","2018-11-19","2018-12"],"dc:description":["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.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2020-12-01","The student, Yihao Zhang, accepted the attached license on 2018-11-18 at 21:45.","The student, Yihao Zhang, submitted this Thesis for approval on 2018-11-18 at 21:53.","This Thesis was approved for publication on 2018-11-19 at 11:19.","DSpace SAF Submission Ingestion Package generated from Vireo submission #13096 on 2019-02-07 at 14:17:35","Made available in DSpace on 2019-02-07T20:35:58Z (GMT). No. of bitstreams: 2 ZHANG-THESIS-2018.pdf: 1165716 bytes, checksum: b71ab8430810ebde221c29df6a229309 (MD5) LICENSE.txt: 4208 bytes, checksum: f48a24f10be1d5b9a034c7df3e966ca9 (MD5) Previous issue date: 2018-11-19","Embargo set by: Seth Robbins for item 109820 Lift date: 2021-02-07T20:36:09Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 109820 Lift date: 2021-02-07T20:39:46Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 109820 Lift date: 2021-02-07T20:44:35Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 109820 on 2021-02-08T10:15:22Z."],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/102796"],"dc:language":["en"],"dc:rights":["Copyright 2018 Yihao Zhang"],"dc:subject":["Maze routing","Reinforcement Learning"],"dc:title":["Deep reinforcement learning on 1-layer circuit routing problem"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:42Z"}