{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T16:37:05Z","timestamp":1771519025743,"version":"3.50.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T00:00:00Z","timestamp":1755734400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"},{"start":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T00:00:00Z","timestamp":1755734400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"}],"funder":[{"DOI":"10.13039\/100014718","name":"Innovative Research Group Project of the National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62372109"],"award-info":[{"award-number":["62372109"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003392","name":"Natural Science Foundation of Fujian Province","doi-asserted-by":"publisher","award":["2024J01984"],"award-info":[{"award-number":["2024J01984"]}],"id":[{"id":"10.13039\/501100003392","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J. King Saud Univ. Comput. Inf. Sci."],"published-print":{"date-parts":[[2025,9]]},"DOI":"10.1007\/s44443-025-00227-8","type":"journal-article","created":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T13:46:44Z","timestamp":1755784004000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Multi-layer obstacle-avoiding rectilinear steiner minimal tree algorithm based on deep reinforcement learning"],"prefix":"10.1007","volume":"37","author":[{"given":"Xing","family":"Huang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuhan","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yanbo","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yajun","family":"Xie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3099-4371","authenticated-orcid":false,"given":"Genggeng","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,8,21]]},"reference":[{"issue":"1","key":"227_CR1","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1109\/2.976921","volume":"35","author":"L Benini","year":"2002","unstructured":"Benini L, De Micheli G (2002) Networks on chips: a new SoC paradigm. Computer 35(1):70\u201378","journal-title":"Computer"},{"key":"227_CR2","doi-asserted-by":"crossref","unstructured":"Chen L-T, Kuo H-R, Li Y-L, Chao MC-T (2024) Arbitrary-size multi-layer OARSMT RL router trained with combinatorial monte-carlo tree search. In: Proceedings of the ACM\/IEEE design automation conference, pp 1\u20136","DOI":"10.1145\/3649329.3656500"},{"key":"227_CR3","doi-asserted-by":"crossref","unstructured":"Chen P-Y, Ke B-T, Lee T-C, Tsai I-C, Kung T-W, Lin L-Y, Liu E-C, Chang Y-C, Li Y-L, Chao MC-T (2022) A reinforcement learning agent for obstacle-avoiding rectilinear Steiner tree construction. In: Proceedings of the international symposium on physical design, pp 107\u2013115","DOI":"10.1145\/3505170.3506721"},{"key":"227_CR4","doi-asserted-by":"crossref","unstructured":"Chen T-C (2024) Introduction to the panel on EDA challenges at advanced technology nodes. In: Proceedings of the international symposium on physical design, pp 61\u201361","DOI":"10.1145\/3626184.3639694"},{"issue":"1","key":"227_CR5","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/j.vlsi.2013.08.001","volume":"47","author":"W-K Chow","year":"2014","unstructured":"Chow W-K, Li L, Young EF, Sham C-W (2014) Obstacle-avoiding rectilinear Steiner tree construction in sequential and parallel approach. Integration 47(1):105\u2013114","journal-title":"Integration"},{"key":"227_CR6","doi-asserted-by":"crossref","unstructured":"Chuang J-W, Wu Z-H, Huang B-Y, Chang Y-W (2024) Redistribution layer routing with dynamic via insertion under irregular via structures. In: Proceedings of the ACM\/IEEE design automation conference, pp 1\u20136","DOI":"10.1145\/3649329.3657371"},{"key":"227_CR7","doi-asserted-by":"crossref","unstructured":"Clarkson K, Kapoor S, Vaidya P (1987) Rectilinear shortest paths through polygonal obstacles in $$o(n \\log n)$$ time. In: Proceedings of the third annual symposium on computational geometry, pp 251\u2013257","DOI":"10.1145\/41958.41985"},{"key":"227_CR8","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"2022","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C (2022) Introduction to algorithms. MIT Press"},{"issue":"9","key":"227_CR9","doi-asserted-by":"publisher","first-page":"7366","DOI":"10.1016\/j.jksuci.2022.03.013","volume":"34","author":"BB Elallid","year":"2022","unstructured":"Elallid BB, Benamar N, Hafid AS, Rachidi T, Mrani N (2022) A comprehensive survey on the application of deep and reinforcement learning approaches in autonomous driving. J King Saud Univ-Comput Inf Sci 34(9):7366\u20137390","journal-title":"J King Saud Univ-Comput Inf Sci"},{"issue":"4","key":"227_CR10","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey MR, Johnson DS (1977) The rectilinear Steiner tree problem is NP-complete. SIAM J Appl Math 32(4):826\u2013834","journal-title":"SIAM J Appl Math"},{"key":"227_CR11","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1016\/j.apm.2019.10.027","volume":"78","author":"W Guo","year":"2020","unstructured":"Guo W, Huang X (2020) Pora: a physarum-inspired obstacle-avoiding routing algorithm for integrated circuit design. Appl Math Model 78:268\u2013286","journal-title":"Appl Math Model"},{"key":"227_CR12","doi-asserted-by":"crossref","unstructured":"Huang T, Young EF (2010) Obstacle-avoiding rectilinear Steiner minimum tree construction: An optimal approach. In: Proceedings of the IEEE\/ACM international conference on computer-aided design, pp 610\u2013613","DOI":"10.1109\/ICCAD.2010.5654220"},{"issue":"1","key":"227_CR13","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1137\/0130013","volume":"30","author":"FK Hwang","year":"1976","unstructured":"Hwang FK (1976) On Steiner minimal trees with rectilinear distance. SIAM J Appl Math 30(1):104\u2013114","journal-title":"SIAM J Appl Math"},{"issue":"2","key":"227_CR14","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1145\/322123.322124","volume":"26","author":"FK Hwang","year":"1979","unstructured":"Hwang FK (1979) An $$o(n \\log n)$$ algorithm for rectilinear minimal spanning trees. J ACM 26(2):177\u2013182","journal-title":"J ACM"},{"issue":"3","key":"227_CR15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jksuci.2024.102006","volume":"36","author":"C Jisi","year":"2024","unstructured":"Jisi C, Roh B-H, Ali J (2024) Reliable paths prediction with intelligent data plane monitoring enabled reinforcement learning in sd-iot. J King Saud Univ-Comput Inf Sci 36(3):102006","journal-title":"J King Saud Univ-Comput Inf Sci"},{"key":"227_CR16","doi-asserted-by":"crossref","unstructured":"Kahng AB, Lienig J, Markov IL, Hu J (2011) Vlsi physical design: from graph partitioning to timing closure. Springer 312","DOI":"10.1007\/978-90-481-9591-6"},{"key":"227_CR17","doi-asserted-by":"crossref","unstructured":"Kahng AB, M\u0103ndoiu II, Zelikovsky AZ (2003) Highly scalable algorithms for rectilinear and octilinear Steiner trees. In: Proceedings of the Asia and South Pacific design automation conference, pp 827\u2013833","DOI":"10.1109\/ASPDAC.2003.1195132"},{"key":"227_CR18","doi-asserted-by":"crossref","unstructured":"Kamat RK, Shinde SA, Gaikwad PK, Guhilot H (2011) Harnessing VLSI system design with EDA tools. Springer Science & Business Media","DOI":"10.1007\/978-94-007-1864-7"},{"issue":"4","key":"227_CR19","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1109\/TCAD.2008.917583","volume":"27","author":"C-W Lin","year":"2008","unstructured":"Lin C-W, Chen S-Y, Li C-F, Chang Y-W, Yang C-L (2008) Obstacle-avoiding rectilinear Steiner tree construction based on spanning graphs. IEEE Trans Comput-Aided Des Integr Circ Sys 27(4):643\u2013653","journal-title":"IEEE Trans Comput-Aided Des Integr Circ Sys"},{"issue":"11","key":"227_CR20","doi-asserted-by":"publisher","first-page":"2007","DOI":"10.1109\/TCAD.2008.2006095","volume":"27","author":"C-W Lin","year":"2008","unstructured":"Lin C-W, Huang S-L, Hsu K-C, Lee M-X, Chang Y-W (2008) Multilayer obstacle-avoiding rectilinear Steiner tree construction based on spanning graphs. IEEE Trans Comput-Aided Des Integr Circ Syst 27(11):2007\u20132016","journal-title":"IEEE Trans Comput-Aided Des Integr Circ Syst"},{"issue":"4","key":"227_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3177878","volume":"23","author":"K-W Lin","year":"2018","unstructured":"Lin K-W, Lin Y-S, Li Y-L, Lin R-B (2018) A maze routing-based methodology with bounded exploration and path-assessed retracing for constrained multilayer obstacle-avoiding rectilinear Steiner tree construction. ACM Trans Des Autom Electron Syst 23(4):1\u201326","journal-title":"ACM Trans Des Autom Electron Syst"},{"issue":"7","key":"227_CR22","doi-asserted-by":"publisher","first-page":"2711","DOI":"10.1109\/TCAD.2024.3523429","volume":"44","author":"Z Lin","year":"2025","unstructured":"Lin Z, Liu G, Huang X, Lin Y, Zhang J, Liu W-H, Wang T-C (2025) A unified deep reinforcement learning approach for constructing rectilinear and octilinear Steiner minimum tree. IEEE Trans Comput-Aided Des Integr Circ Syst 44(7):2711\u20132724","journal-title":"IEEE Trans Comput-Aided Des Integr Circ Syst"},{"key":"227_CR23","doi-asserted-by":"crossref","unstructured":"Li L, Qian Z, Young EF (2009) Generation of optimal obstacle-avoiding rectilinear Steiner minimum tree. In: Proceedings of the international conference on computer-aided design, pp 21\u201325","DOI":"10.1145\/1687399.1687405"},{"key":"227_CR24","doi-asserted-by":"crossref","unstructured":"Liu C-H, Yuan S-Y, Kuo S-Y, Weng J-H (2009) Obstacle-avoiding rectilinear Steiner tree construction based on Steiner point selection. In: Proceedings of the international conference on computer-aided design, pp 26\u201332","DOI":"10.1145\/1687399.1687406"},{"issue":"7","key":"227_CR25","doi-asserted-by":"publisher","first-page":"1050","DOI":"10.1109\/TCAD.2012.2185050","volume":"31","author":"C-H Liu","year":"2012","unstructured":"Liu C-H, Kuo S-Y, Lee D, Lin C-S, Weng J-H, Yuan S-Y (2012) Obstacle-avoiding rectilinear Steiner tree construction: a Steiner-point-based algorithm. IEEE Trans Comput-Aided Des Integr Circ Syst 31(7):1050\u20131060","journal-title":"IEEE Trans Comput-Aided Des Integr Circ Syst"},{"issue":"12","key":"227_CR26","doi-asserted-by":"publisher","first-page":"1928","DOI":"10.1109\/TCAD.2014.2363390","volume":"33","author":"C-H Liu","year":"2014","unstructured":"Liu C-H, Lin C-X, Chen I-C, Lee D, Wang T-C (2014) Efficient multilayer obstacle-avoiding rectilinear Steiner tree construction based on geometric reduction. IEEE Trans Comput-Aided Des Integr Circ Syst 33(12):1928\u20131941","journal-title":"IEEE Trans Comput-Aided Des Integr Circ Syst"},{"key":"227_CR27","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2021.107215","volume":"104","author":"G Liu","year":"2021","unstructured":"Liu G, Chen X, Zhou R, Xu S, Chen Y-C, Chen G (2021) Social learning discrete particle swarm optimization based two-stage X-routing for IC design under intelligent edge computing architecture. Appl Soft Comput 104:107215","journal-title":"Appl Soft Comput"},{"key":"227_CR28","doi-asserted-by":"crossref","unstructured":"Liu G, Zhu Y, Xu S, Chen Y-C, Tang H (2022) PSO-based power-driven X-routing algorithm in semiconductor design for predictive intelligence of IoT applications. Appl Soft Comput 114:108114","DOI":"10.1016\/j.asoc.2021.108114"},{"issue":"9","key":"227_CR29","doi-asserted-by":"publisher","first-page":"5627","DOI":"10.1109\/TSMC.2024.3407960","volume":"54","author":"G Liu","year":"2024","unstructured":"Liu G, Zhu Y, Zhuang Z, Pei Z, Gan M, Huang X, Guo W (2024) A robust multilayer X-architecture global routing system based on particle swarm optimization. IEEE Trans Syst Man Cybernet Syst 54(9):5627\u20135640","journal-title":"IEEE Trans Syst Man Cybernet Syst"},{"key":"227_CR30","doi-asserted-by":"crossref","unstructured":"Liu J, Chen G, Young EF (2021) Rest: constructing rectilinear Steiner minimum tree via reinforcement learning. In: Proceedings of the ACM\/IEEE design automation conference, pp 1135\u20131140","DOI":"10.1109\/DAC18074.2021.9586209"},{"issue":"12","key":"227_CR31","doi-asserted-by":"publisher","first-page":"2169","DOI":"10.1109\/TCAD.2008.2006098","volume":"27","author":"J Long","year":"2008","unstructured":"Long J, Zhou H, Memik SO (2008) Eboarst: an efficient edge-based obstacle-avoiding rectilinear steiner tree construction algorithm. IEEE Trans Comput-Aided Des Integr Circ Syst 27(12):2169\u20132182","journal-title":"IEEE Trans Comput-Aided Des Integr Circ Syst"},{"key":"227_CR32","volume-title":"Chip war: the fight for the world\u2019s most critical technology","author":"C Miller","year":"2022","unstructured":"Miller C (2022) Chip war: the fight for the world\u2019s most critical technology. Simon and Schuster"},{"key":"227_CR33","doi-asserted-by":"crossref","unstructured":"Mohamed KS (2025) Next generation eda flow: motivations, opportunities, challenges and future directions. Springer Nature","DOI":"10.1007\/978-3-031-88435-1"},{"key":"227_CR34","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2023.110773","volume":"147","author":"A Sonny","year":"2023","unstructured":"Sonny A, Yeduri SR, Cenkeramaddi LR (2023) Q-learning-based unmanned aerial vehicle path planning with dynamic obstacle avoidance. Appl Soft Comput 147:110773","journal-title":"Appl Soft Comput"},{"issue":"1","key":"227_CR35","doi-asserted-by":"publisher","first-page":"250424229315","DOI":"10.2174\/0126662558289880240418073738","volume":"18","author":"G Thakur","year":"2025","unstructured":"Thakur G, Jain S (2025) Role of artificial intelligence in VLSI design: a review. Recent Adv Comput Sci Commun 18(1):250424229315","journal-title":"Recent Adv Comput Sci Commun"},{"issue":"5","key":"227_CR36","doi-asserted-by":"publisher","DOI":"10.1016\/j.jksuci.2024.102052","volume":"36","author":"Y Ullah","year":"2024","unstructured":"Ullah Y, Roslee M, Mitani SM, Sheraz M, Ali F, Osman AF, Jusoh MH, Sudhamani C (2024) Reinforcement learning-based unmanned aerial vehicle trajectory planning for ground users\u2019 mobility management in heterogeneous networks. J King Saud Univ-Comput Inf Sci 36(5):102052","journal-title":"J King Saud Univ-Comput Inf Sci"},{"issue":"8","key":"227_CR37","doi-asserted-by":"publisher","DOI":"10.1016\/j.jksuci.2023.101723","volume":"35","author":"Q Wang","year":"2023","unstructured":"Wang Q, Zhang C, Tang C (2023) Discovering lin-kernighan-helsgaun heuristic for routing optimization using self-supervised reinforcement learning. J King Saud Univ-Comput Inf Sci 35(8):101723","journal-title":"J King Saud Univ-Comput Inf Sci"},{"issue":"9","key":"227_CR38","doi-asserted-by":"publisher","DOI":"10.1016\/j.jksuci.2023.101787","volume":"35","author":"Q Wang","year":"2023","unstructured":"Wang Q, Hao Y, Zhang J (2023) Generative inverse reinforcement learning for learning 2-opt heuristics without extrinsic rewards in routing problems. J King Saud Univ-Comput Inf Sci 35(9):101787","journal-title":"J King Saud Univ-Comput Inf Sci"},{"key":"227_CR39","unstructured":"Wolf W (2008) Modern vlsi design: Ip-based design. Pearson Education"},{"key":"227_CR40","doi-asserted-by":"crossref","unstructured":"Wong Y-C, Chu C (2008) A scalable and accurate rectilinear Steiner minimal tree algorithm. In: Proceedings of the IEEE international symposium on vlsi design, automation and test, pp 29\u201334","DOI":"10.1109\/VDAT.2008.4542405"},{"issue":"5","key":"227_CR41","doi-asserted-by":"publisher","first-page":"2927","DOI":"10.1109\/TSMC.2024.3353534","volume":"54","author":"Y Zhu","year":"2024","unstructured":"Zhu Y, Liu G, Lu R, Huang X, Gan M, Guo W (2024) Timing-driven obstacle-avoiding X-architecture Steiner minimum tree algorithm with slack constraints. IEEE Trans Syst Man Cybern Syst 54(5):2927\u20132940","journal-title":"IEEE Trans Syst Man Cybern Syst"}],"container-title":["Journal of King Saud University Computer and Information Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s44443-025-00227-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s44443-025-00227-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s44443-025-00227-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,17]],"date-time":"2025-09-17T12:42:50Z","timestamp":1758112970000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s44443-025-00227-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,21]]},"references-count":41,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["227"],"URL":"https:\/\/doi.org\/10.1007\/s44443-025-00227-8","relation":{},"ISSN":["1319-1578","2213-1248"],"issn-type":[{"value":"1319-1578","type":"print"},{"value":"2213-1248","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,21]]},"assertion":[{"value":"21 April 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 August 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 August 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"195"}}