Ranking Cost: One-Stage Circuit Routing by Directly Optimizing Global Objective Function
Authors: Shiyu Huang
Bin Wang
Dong Li
Jianye Hao
Jun Zhu
Ting Chen
Venue:  (2021)
Keywords: Evolution Strategy
Circuit Routing
A*
PCB

Abstract: Circuit routing has been a historically challenging problem in designing electronic systems such as very large-scale integration (VLSI) and printed circuit boards (PCBs). The main challenge is that connecting a large number of electronic components under specific design rules and constraints involves a very large search space, which is proved to be NP-complete. 
Early solutions are typically designed with hard-coded heuristics, which suffer from problems of non-optimum solutions and lack of flexibility for new design needs. Although a few learning-based methods have been proposed recently, their methods are cumbersome and hard to extend to large-scale applications. In this work, we propose a new algorithm for circuit routing, named as Ranking Cost (RC),  which innovatively combines search-based methods (i.e., A* algorithm) and learning-based methods (i.e., Evolution Strategies) to form an efficient and trainable router under a proper parameterization. Different from two-stage routing methods ( i.e., first global routing and then detailed routing), our method involves a one-stage procedure that directly optimizes the global objective function, thus it can be easy to adapt to new routing rules and constraints. In our method, we introduce a new set of variables called cost maps, which can help the A* router to find out proper paths to achieve the global object. We also train a ranking parameter, which can produce the ranking order and further improve the performance of our method. Our algorithm is trained in an end-to-end manner and does not use any artificial data or human demonstration. In the experiments, we compare our method with the sequential A* algorithm and a canonical reinforcement learning approach, and results show that our method outperforms these baselines with higher connectivity rates and better scalability. Our ablation study shows that our trained cost maps can capture the global information and guide the routing result to approach global optimum.

Under review as a conference paper at ICLR 2021
RANKING COST: ONE-STAGE CIRCUIT ROUTING BY DIRECTLY OPTIMIZING GLOBAL OBJECTIVE FUNC- TION
Anonymous authors
Paper under double-bling brind review
ABSTRACT
Circuit routing has been a historically challenging problem in designing electronic systems such as very large-scale integration (VLSI) and printed circuit boards (PCBs). The main challenge is that connecting large number of electronic com- ponents under specific design rules and constraints involves a very large search space, which is proved to be NP-complete. Early solutions typically designed with hard-coded heuristics, which suffer from problems of non-optimal solutions and lack of flexibility for design needs. Although few Marning-based meth- ods have been proposed recently, their methods are cumbersome and hard to ex- tend large-scale applications. In this work, we propose a new algorithm for cir- cuit routing, named as Ranking Cost (RC). which innovatively combines search- based methods (i.e., A algorithm) and learning caaring-bbsedd methods (i.e., Evolution Strategies) to form an efficient and trainable router under proper parameteri- zation. Different from two-stage routing methods ( i.e., first global routing and then detailed routing), our method involves an one-stage procedure that directly optimizes the global objective function, thus it can be casy to adapt to new rout- ing rules and constraints. In our method, we introduce new set of variables called cost maps, which can help the A router to find out proper paths to achieve the global objective. We also train ranking parameter, which can produce the ranking order and further improve the performance of our method. Our algo- rithm is trained in end-to-end manner and does use any artificial data human demonstration. In the experiments, we compare with the sequential A algorithm and canonical reinforcement learning approach, and results show that our method outperforms these baselines with higher connectivity rates and better scalability. Our ablation study shows that our trained cost maps can capture the global information and guide the routing result to approach global optima.
INTRODUCTION
As descrihed in Moore's Law (Schaller) 1997), the number of transistors in dense integrated circuit (IC) increases exponentially over time and the complexity of chips and printed circuit boards (PCBs) becomes higher and higher. Such high complexity makes the IC design time-consuming and error- prone work. Thus more capable automatic design systems, such as electronic design automation (EDA) tools, needed to improve the performance. In the flow of IC designs, we need to find proper paths to place wires which connect electronic components on ICs, and these wires need to achieve expected connectivity under certain constraints. One of the most important constraints is that wires on the same layout should not intersect. In addition, to reduce the signal propagation delay, the wire-length should be minimized. This is critical and challenging stage the IC design flow (Hu & Sapatnckar (000I) known circuit routing, which has been studied by lots of researchers (Kramer 1984 Zhang & Chu 2012 He & Bao 2020).
Circuit routing involves large number of nets (a net is a set of vertices with the same electrical property) to be routed, which is computationally expensive and makes manual design extremely time-consuming (Kong et al.] 2009 Coombs & Holden 2001). Even under the simplest setting, where only two pairs of pins need to be routed, it is an NP-complete problem (Kramer 1984). Although lots of circuit routing algorithms have been proposed (Zhang) 2016), there still remain

---

Under review as a conference paper at ICLR 2021
three major challenges: (1) Early solutions (Hu & Sapatnekar 2001) are typically designed with hard-coded heuristics, which suffer from problems of non-optimal solutions Zhang 2016) and lack of flexibility over new design needs. Therefore, more powerful routing method that does not depend on domain knowledge is highly desired.
(2) To reduce the difficulty of complex routing problems, traditional routing algorithms often adopt two-stage procedure
first global routing and then detailed routing (Chen & Chang] 22009; Kahng et al. 2011). The problem is that these two stages do not always coordinate well (Zhang & Chu 2012 Shi & Davoodi 2017). Sometimes a low-congested global routing result may lead to downstream detailed router un un-routable. Hence, an end-to-end algorithm is preferred which can optimize the final global objective (e.g.. the total wire-length) directly. (3) Although few learning-based methods have been proposed (Liao et al.) 2020 He & Bao 2020) recently, their methods are hard to extend to large-scale applications. real settings, there are lots of components and nets on a single chip, which shows greater demand for the scalability of routing algorithms.
To relieve the problems mentioned above, we propose new algorithm, denoted as Ranking Cost (RC), for circuit routing. In this paper, we innovatively combine search-based methods (i.e., A algorithm) and learning- bearning-based methods (i.e., Evolution Strategies (Salimans al. 2017)) form an trainable router with proper parametrization. Our method is flexible for integrating new constraints and rules long as they can be merged into the global objective function. Moreover, our method is an one-stage algorithm, which optimizes the global objective function directly. In our method, we introduce new set of variables called cost maps, which can help the A* routers to find out proper paths to achieve the global objective. We also train a ranking parameter, which can produce the ranking order and further improve the performance of our method. In the experiments, we compare our method with the commonly used A method and canonical reinforcement learning approach, and results show that our method outperforms these baselines with higher connectivity rates. Our ablation study also shows that trained cost maps can capture the global information and guide the routing solution to approach global optimal. Experiments also show that our method scalable to larger applications.
2 RELATED WORK
In this section, we summarize the related work on circuit routing.
2.1 TWO-STAGE ROUTING ALGORITIMMS
The routing problem can be heuristically separated into two stages, the first being the global routing step, followed by detailed routing. On the one hand, there are multiple heuristic- based approaches for global routing including regionwise routing (Hu & Sapatnekar| [200T), force-directed routing (Mo) ett al. [200T). and rip-up and reroute (Cho et al. 2007). On the other hand, the most commonly used detailed routing algorithms are channel routing and its variants (Ho et al., 1991 Mandal et al.) 2020), which decompose the routing region into routing channels and generate wires in these chan- nels (Chen & Chang, 2009p. One main issue of the two-stage methods is that these two stages do not always coordinate well (Shi& & Davoodi 2017). which results in enormous difficulty in joint op- timization. Instead, our method is an one stage algorithm and new design constraints can be simply involved into the objective function without changing the algorithm itself.
2.2 SEQUENTIAL ROUTING ALGORITHS
A more straightforward strategy for circuit routing to select a specific order and then route nets sequentially, c.g., sequential * algorithm and Lees algorithm (Huang et al. 2014 Malavasi & 1993). The major advantage of this type approaches is that the conges- tion information for previously routed nets can be taken into consideration while routing the current one. However, the drawback of these sequential approaches is that the quality of the solution is very sensitive to the orders (Zhang 2016). Moreover, earlier routed paths only focus on finding their own best solutions and are impossible to take into account the situation of subsequent paths. Such greedy strategies may make solvable circuit routing problem insolvable. Figure shows example that the sequential * algorithm will fail to handle. In this example, there are two pairs of points to be routed, i.e., we should connect start vertices S, and end vertices F,, i (1, (), respectively. If we
2

---

Under review as a conference paper at ICLR 2021
(a)
(b)
(c)
S1
S2
S2
S2
Figure I: Yellow vertices are the start vertices, green vertices are the end vertices and black blocks obstacles where paths can not pass through. (a) Examples of maps without obstacle. Examples of maps with obstacles. (c) Circuit routing results derived by our algorithm. (d) and (c) show that sequential algorithm will greedily find shortest path of one pair, and fails to obtain global solution. (f) shows the solution found by our algorithm, which is actually globally optimal.
connect the pair (S1, E1) first in its shortest path, it will make (S2, E2) disconnected as showed in Figure dd) and vice versa (Figure [e)). But this case can be solved easily by our algorithm as showed in Figure which means that our algorithm take into account the global information when generating each path.
2.3 LEARNING-BASED ALGORITIIMS CIRCUIT ROUTING
There learning- baased algorithms for circuit routing (Q et al. Early methods are more focusing on supervised learning, such as learning models to predict routing congestion (Qi et al. 2014) predicting the routability (Zhou al. 2015 Xie et al. 2018). But the performances of these supervised models are constrained by the limits of human knowledge. Recently, [Liao al. (2020) trained deep Q-network (DQN) solve the global routing problem and their method still suffers from the miscoupling problem of two-stage routing algorithms. In addition, He Bao (2020) reform circuit routing to a tree search problem and utilize deep neural network as the rollout policy. However, their rollout policy is trained in supervised manner with artificial data. Instead, our method optimizes the global objective function directly and does not require any artificial data or human demonstration.
2014 Liao et al. 2020).
BACKGROUND AND NOTATIONS
In this section, we will formalize the circuit routing problem first and then give a brief introduction to the OpenAI-ES algorithm (Salimans al. 2017).
3.1 CIRCUIT ROUTING
Circuit routing is path search problem, where the goal is to find non non- iiniiteeseeetin paths that connect an arbitrary number of pairs of vertices. It can be formalized each vertex e V represents an intersection on the grid, and each edge eij E E represents the path between i and its 1-hop neighbors vy V. And the non-routable obstructive vertices form
grid graph G (V, E), where
3

---

Under review as a conference paper at ICLR 2021
obstacle set, denoted O C V. In circuit routing, net N (UN1 Un2.... ...] C V is set of vertices that need to be connected and a multi-vertex net can be decomposed into multiple two-vertex nets via minimum spanning tree (MST) or rectilinear Steiner tree (RST) (de Vincente et al. 1998 Hu & Sapatnekar 200T). Following He & Bao 2020), we simplify this problem by letting each net only contain an end vertex Ve. The net should be connected by path / = [11, U2,.... Un] with v, = U1, Ue = Up and P P need to find set P of paths }Pi} that connect these nets. A reasonable routing plan for given set of nets is that all the paths do not share any vertex. some cases, the routing problem do have solution because such non-intersecting set P does not exist. In circuit routing, the routed paths should satisfy some constraints or achieve some goals. this paper, we choose the most commonly used goal, i.e., minimize the total length of paths. Given solution P, the total length of paths is defined as EpEP! Pl.
vertices, i.e, a two-vertex net is defined N {trs (t) with start vertex vs and
We use [P] to represent the length of the path P. Given set A of nets [Na). we
3.2 EVOLUTION STRATEGIES
Evolution Strategies (ES) is a class of black box optimization methods (Rechenberg 1994 Hansen & Ostermeier 200T). Recently, an evolution strategy variant, referred as the OpenAT-ES (Sali- mans al.j 2017). has attracted attention because it could rival the performance of modern deep reinforcement learning methods on multiple control tasks. In the OpenAI-ES, there is reward function, denoted as F(W), where v is solution vector, which is sampled from a probability dis- tribution function v ~ (bb).. The goal is to maximize the expected value J(f), which is defindd as:
J(0) max Ext-no [F(b)] max / F(t)po(()de.
A straightforward way achieve this is to use the gradient ascent:
+ 0 (o)(O,,
(2)
where is the learning rate. In the OpenAI-ES, score function estimator is used to calculate the gradient, which is similar to REINFORCE (Wiliams 1992):
VeJ (0) Vo [b() Ex [F Vo log (+))).
Usually, Po is an isotropic multivariate Gaussian with mean 0 and fixed covariance I²I. And the ex- pected value can be rewritten Extorpo [F(1) [F( changes to:
Thus the gradient estimator
V (() = VoE.-N(o.) ae)] = E.- [F(0 oe)e].
(4)
where e is sampled from a standard normal distribution. Once we form an objective function J(0), the gradient (6) can be approximated via Equation 4 and parameters 0 can be updated via Equation? 2
4 METHODOLOGY
In this section, we will first introduce the Ranking Learning algorithm and then the Cost-Map Learn- ing algorithm. At last, we give out final algorithm (Ranking Cost) and its training strategy.
4.1 SEQUENTIAL A WITH RANKING LEARNING
The A algorithm can be used to find the shortest path in a two-vertex net N = (v., ve). which is considered more efficient than breadth-firs search. A finds path between start vertex v, and an end vertex Ve, with priority function defined as:
s(v) (vv) + h(v),
where e is a vertex in the graph, (vv) represents the total length from v, to the current vertex v, and (ax) represents the future heuristic cost from the end vertex Ue- The h(x) is often set
4

---

Under review as a conference paper at ICLR 2021
the Euclidean distance (in this work) or Manhattan distance. In circuit routing problem, there are k nets to be routed. Given a specific ranking order R. we can apply the A algorithm to each net sequentially, For example, if there are 3 nets 1N,,,,, N33 to be routed and a ranking order R = (2, 1,3) is given. We can apply A to these 3 nets following the order N₂ + N1 + Na- After the routing procedure, we can get total path length from this ranking order, denoted T.(R). Different ranking orders will result in different total lengths. We can go through all the ranking orders and get their corresponding total lengths. The ranking order with minimum total length can be used as the final solution. However, this is unacceptable in time complexity because routing problem with nets has Okk) different ranking orders.
To relieve the problem of combinatorial explosion of ranking orders, we propose method to learn the ranking order. We define k-dimension ranking parameter 0, = 18,,,8...., Bk.. And the ranking order is determined completely by the ranking parameter. More concretely, the order of values in 0, is exactly the routing order, and the net with largest value will be routed first and the rest may be deduced by analogy. For example, given ranking parameter 0,- {0.5, 0.2, 0.4), we have 31 > 33 > 32 and the corresponding ranking order will be Rg. = (1, 3, 2). And the ranking parameter will determine the final routing result and also the total path length. We define a reward function over the ranking parameter:
F(O.)= = -L
(6)
where L(Rg.) ) is the total length when taking the order Re,, and less length leads to larger reward. As described in Section 3.2, we define the expected value over F-) as:
J J(,)) = Ep F(b) = Ee + aee).
The gradient Ve, ((e,) can be estimated via Equation 4 and 6, can be updated via Equation 2
As mentioned in Section 2.2 a sequential routing algorithm may make a solvable circuit routing problem insolvable. And even a method with a learned ranking order will still suffer from this problem. the following section, we will introduce how our method could overcome this problem by coupling the A algorithm with cost maps.
4.2 CIRCUIT ROUTING WITH COST MAPS
As introduced in previous section, g(v) in 5 the total length from start vertex v, to current vertex v, thus the A algorithm can only search for the shortest path of current net and it can not take into account the information of following paths. Our goal to the A routers so that these routers can cooperate together to achieve their common objective. First, for each net N,, E (l,...,k, we define its cost map as C, {c1, C2) Cm.) } E IR" where m = [V| is the number of vertices in graph G. Therefore, there are total k cost maps, and all the cost maps can be learned with our algorithm. We apply cost-map function C(i, 01) = cj. Cj E C. to simplify the notation. In this way, we can reformulate the A algorithm by adding the cost maps:
add global information
k sc)) = g()) cli,)++(())
(8)
where g(v) and (u(v) are with the same definitions as in Equation 5 The cost-map enhanced A* algorithm reveals two key points: (1) When removing g(v) and h(w) from Equation 8 it will de- generate into pure learning- based algorithm and the path will be determined completely by the cost function. (2) When removing the cost functions or set them to zero (i.e., C(i, 0), it is a pure search-based algorithm. Hence, it is a method which combines the searched- based algorithm and the learning-baat based algorithm and could take advantage of both sides. On the one hand, the A* search makes method easier to find connected path in complex environment, where learning- based methods are hard to find a connected path (Tamar et al. (0066). On the other hand, the global information can be merged into cost maps and the global objective can be approached by tuning the cost maps.
To leam the cost maps, we first define cost-map parameter fg R and the value in cost maps are defined as c, = max(0, (.)i,,)).c e C. Given a ranking order R and cost maps, we can route the nets sequentially using the cost-map enhanced A * and total path length L. will be obtained from
5

---

Under review as a conference paper at ICLR 2021
the routing result. Similar Equation 6 we define reward function over the cost-map parameter and also its the expected value:
F(6.) = - L(R, Co.)
(9)
J(2) = Epppo N0, +c),
where Co. presents the cost maps derived from 8c. and 9g can be updated via Equation 2 By iteratively executing the A search and cost-map learning step, our method could approach the optimal solution in the process of time and solve some problems that sequential routing algorithm can not solve as showed in Figure [ In next section, we will introduce how the cost-map learning can couple with ranking learning and how to train the algorithm efficiently practice.
4.3 RANKING COST ALGORITHM
Our final algorithm, denoted as Ranking Cost (RC), can learn the ranking parameter 8, and cost-map parameter 9. jointly. In Equation 8 all the cost maps are used when calculating the priority function and the ranking order has impact on the cost maps. To learn the cost-map with ranking order, change the priority function to:
8,(0)= = gy( Σ +(i,))+
(10)
where (v) is the priority function for the net whose ranking order is the j-th. This modification reasonable, because the earlier routed nets will use more cost maps and observe more global information. For example, when routing the first net, its ranking index is j 1 and it will use all the rest k: - 1 cost maps. As a result, the first routed path focuses more on impact on other unrouted nets. When routing the last net, its ranking index is le and no cost map will be used. As result, the last net is routed via a normal A algorithm and the searched solution is actually the shortest path current situation. As all the previous nets have been routed, the best way for routing the last net is just to find out the shortest path. Our RC algorithm achieves this naturally and makes it flexible for arbitrary ranking orders. When the ranking order changes, the order and the usage of cost maps change accordingly. In this way, the reward function can be defined as:
F(O,, 0.) = L( Coc),
(11)
and both 8, and 6g can be updated via the OpenAI-ES algorithm. Actually, the reward function F can be integrated with arbitrary metrics, such as the signal latency. Thus the cost maps are free to adapt new constraints and design rules.
In the OpenAI-ES algorithm, we will sample fixed number of Gaussian noises and add them to original parameters to form new parameters. These new parameters are then fed into evaluators (or workers). The evaluator has an independent environment and executes the algorithm based on received parameters. Finally, each evaluator will return scalar reward. To stabilize the training process, we normalize collected rewards fri,..., rn) from all the evaluators:
F (r: (rmeean)/Tst)
(12)
where Tmean and Fetd are the mean and standard deviation of all the rewards. Algorithm | in (eenndxx(Asshwwee the overall training procedure of our RC algorithm. In practice, all the evaluators can execute in parallel as proposed in [Salimans et al. (2017). The source code of Ranking Cost can be found in the supplementary material.
EXPERIMENTS
In this section, we will compare our proposed method with some other baselines. We will also study how the ranking learning and cost maps work in our algorithm. Finally, we further show the scalability of our algorithm for larger applications.
5.1 METHODS EVALUATION
To evaluate our algorithm, we build a grid map simulator as the test environment. We construct 300 maps with three different sizes: 16 16, 32 32 and 64 64. These maps split into two

---

Under review as a conference paper at ICLR 2021
16 x 16 (4 pairs)
32 x 32 (6 pairs)
64 x 64 (10 pairs)
time (s/map)
no obstacle with obstacles no obstacle
with obstacles
no obstacle
with obstacles
Seq A (5)
0.94(37.1)
0.9(37.2)
0.96(114.0)
0.58(116.7)
0.8(459.9)
0.08(393.7)
0.8
Seq A* (200)
0.96(36.7)
0.96(36.9)
1.0(111.3)
0.78(111.1)
0.84(457.2)
0.24(383.0)
41.5
VINS
0.84(37.1)
0.86(37.2)
0.54(129.4)
0.18(122.2)
0.0(-)
0.0(-)
1.4
CL
0.94(38.3)
0.9(37.7)
0.98(114.6)
0.68(118.7)
0.88(485.4) 4)
0. 0.16(408.3)
37.5
RC(ours)
1.0(36.7)
0.98(37.0)
1.0(113.4)
0.82(111.8)
0.86(431.3)
0.32(378.3)
38.3
Table 1: Evaluation results of different algorithms. Two values reported. The first value is the success rate (the higher the better) and the second value in the bracket is the common average length (the lower the better). Ranking Cost achieves the best performance on all the maps. The comparison between CML and RC shows that the ranking parameter learning can improve the performance of algorithm. We also report the wallclock time of different algorithms in the last column. The Ranking Cost algorithm takes more running time, but it is worthy to sacrifice more time to earn better solutions.
types, i.., simple one without obstacle and a more complex one with obstacles. Figure T and Figure [b) show some of the maps used in our experiments. Algorithms will be evaluated on these maps, and the success rates and the average of total lengths will be reported. More details about the maps can be found in Appendix B
Baselines:
Sequential A#: Sequential * is common used search-based algorithm in circuit routing. It routes nets with a specific ranking order and different orders will lead to different results. In the experiments, we randomly sample 5 different ranking orders and run the algorithm 5 times. The best score of runs will be reported. We further randomly sample 200 different ranking orders and the algorithm 200 times. The best score of 200 runs will be reported.
Value Iteration Networks (VINs) (Tamar et al. 2016): The VIN is a learning-based approach for routing grid maps. VINs use the value iteration from reinforcement learning and can achieve better performance compared with supervised models. We apply VINs to the circuit routing problem by sequentially executing on each net. Similar sequential A* algorithm, we randomly sample five different ranking orders and run the VIN five times. The best score of five runs will be reported.
Cost-Map Learning (CML): We construct a Cost-Map Learning algorithm from the Ranking Cost. In the CML, the ranking parameter will not be trained (the ranking order fixed) and only the cost-map will be trained.
The Ranking Cost (RC) presented in Algorithm I is our final method for circuit routing problem and more details about its auper-parametess can be found in Appendix C Table [ shows the eval- uation results of different algorithms all the maps. Two values are reported for each algorithm. The first value is the success rate (the higher the better) and the second value in the bracket is the common average length (the lower the better). Our final algorithm (Ranking Cost) achieves the best performance on all the maps. On the most complex maps (with size 64 x 64, obstacles and 10 pairs of vertices), Ranking Cost outperforms other baselines by large margin, which implies that our method has greater advantage on handling more challenging tasks. The comparison between Cost- Map Learning and Ranking Cost shows that the ranking parameter learning can further improve the performance of our algorithm.
5.2 ABLATION STUDY
In this section, we study how each part of our algorithm works and the scalability of the RC.
5.2.1 IMPACT OF RANKING ORDERS
To show the impact of the ranking learning, we increase the sample number of orders for sequential * and use the Ranking Learning algorithm described in Section 4.1 comparison. Table 2 in ppjendsx(jsshoss the changes success rates with different order sample numbers and Figure ((a) shows the curve of success rates and sample numbers. The result shows that improve the
7

---

Under review as a conference paper at ICLR 2021
0
0
52
0.09
18
(a)
(b)
(c)
Figure 2: (a) The curve of success rates and sample numbers. Our learned ranking order achieves better performance than randomly sampled orders. (b) Trained cost map of the example from Fig- ure ft). There are two larger cost values (the yellow grids) in the cost map, which will give out large cost if the path chooses to go through here. As a result, the first pair ((S1, E1)) will not take its shortest path which will block the second pair((S,, (S2, Ee)), It shows that cost maps can capture the global information and guide routers to approach global optimal. 150 and with 15 pairs, which implies that method
(c) An example of routing results
of our algorithm maps with size of 150 x could be adapted to larger scales of applications.
success rate by increasing the order sample number, it hard to further improve the performance by linearly increasing the sample number as the order complexity is O(k)), where l is the number of pairs (or nets). However, our learned ranking order can achieve much better performance than randomly sampled orders.
5.2.2 IMPACT OF COST MAPS
To study the impact of cost maps, we fix the ranking order and only train the cost-map parameter, and we use the example map showed in Figure I We fixed the ranking order as R (1,2) 2) and train its cost maps. Because the ranking order is fixed and there are only two cost maps, only the second cost map will be used when routing the first pair (i.e., (S1, E)).. Finally, we visualize the trained cost maps as showed in Figure (b). There are two larger cost values (the yellow grids) in the cost map, which will give out large pair ((S), F1) will take the path as showed in Figure (f) instead of taking its shortest path which will block the second pair( (S2, F22)). shows that our cost maps can capture the global information and guide routers to approach global optimal.
if the path chooses go through here. As result, the first
5.2.3 SCALABILITY OF RANKING COST ALGORITHM
In Liao et al. (2020), their algorithm is only evaluated on the maps with size of 8 x 8. In He & Bao (2200), their algorithm evaluated on the maps with size of 30 30 and with only 5 pairs. The search space is huge in their methods, which prevent them from applying to larger maps. To test the scalability of our algorithm, we apply our algorithm on larger maps with size of 150 x 150 and with 15 pairs. Figure (e)) shows the routing result of our algorithm, which implies that our method could be adapted to larger scales applications.
DISCUSSION
In this paper, we propose a novel algorithm, called Ranking Cost, to solve the historically chal- lenging circuit routing problem. In our method, we combine search-based algorithms (i.e., A*) and learning-based algorithms (i.e., evolution strategies) to form a new powerful algorithm which could take advantage of both sides. Our method is a one-stage circuit routing algorithm which can opti- mize the global objective function directly, and is easy to implement and flexible for new design rules and constraints. Experimental results show that method is powerful and scalable more complex tasks. In the future, we will extend Ranking Cost to broader applications, such as pedestrian path prediction, multi-agent path finding and robot navigation.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Dor Atzmon, Jiaoyang Li, Ariel Felner, Eliran Nachmani, and Sven Koenig. Multi-directional heuristic search. In International Joint Conference on Artificial Intelligence (ICAI), 2020, 2020.
Benedicte M Babayan, Naoshige Uchida, and Samuel Gershman. Belief state representation in the dopamine system. Nature communications, 181: 2018.
Jaime Barceló, Hanna Grzybowska, and Sara Pardo. Vehicle routing and scheduling models, simu- lation and city logistics. In Dynamic Fleet Management, pp. 163-195. Springer, 2007.
Chambon and Michel Tollenaere. Automated al-based mechanical design hydraulic manifold blocks. Computer-aided design, 23(3):213-22,, 1991.
Huang-Wo Yu Chen and Yao-Wei Chang. Global and detailed routing. In Electronic Design Automation, pp. 687-749. Elsevier, 2009.
Minsik Cho, Katrina Lu, Kun Yuan, and David Z Pan. Boxrouter 2.0: Architecture and imple- mentation of hybrid and robust global router. In 2007 IEEF/ACM International Conference on Computer-Aided Design, pp. 503-508. IEFE, 2007.
Symeon E Christodoulou and Georgios Ellinas.. Pipe routing through ant colony optimization. Jour- nal of Infrastructure systems, (6(2):149-155) 2010.
Clyde F Coombs and Happy T Holden. Printed circuits handbook, volume 1. McGraw-Hill New York, 2001.
J de Vincente, Juan Lanchares, and Román Hermida. Rsr: A new rectilinear steiner minimum tree approximation for fpga placement and global routing. In Proceedings. 24th EUROMICRO Conference (Cat. No. 98EX204), volume 1, pp. 192-195. IEEE, 1998.
Jan Fabian Ehmke, André Steinert, and Dirk Christian Matffeld Advanced routing for city logistics service providers based time-dependent travel times. Journal of computational science, 3(4): 193-205, 2012.
Walter M Grayman, Robert M Clark, and Richard M Males. Modeling distribution-system water quality; dynamic approach. Journal of Water Resources Planning and Management, 114(3):295- 312, 1988.
Nikolaus Hansen and Andreas Ostermeier: Completely derandomized self-adaptation in evolution strategies. Evolutionary computation, 9(2):159-195, 2001.
Youbiao He and Forrest Sheng Bao. Cireuit routing using monte carlo tree search and deep neural networks. arXiv preprint arXiv:2006. /3607, 2020.
T-T Ho. Sitharama Iyengar, and S-Q Zheng. A general greedy channel routing algorithm. IEEE transactions on computer-aided design of integrated circuits and systems, 10(2):204-211, 1991.
Jiang Hu and Sachin S Sapatnekar. survey on multi-net global routing for integrated circuits. Integration, 11(1):1-49, 2001.
Tsung-War Wei Huang, Pei-Ci Wu, and Martin D Wong. Ui-route: An ultra-fast incremental maze routing algorithm. In 2014 ACM/IEEE International Workshop on System Level Interconnect Prediction (SLIP), pp. 1-8. IEEE, 2014.
Andrew B Kahng, Jens Lienig, Igor I. Markov, and Jin Hu. VLSI physical design: from graph partitioning to timing closure. Springer Science Business Media, 2011.
Sang-Seob Kang, M Sehyun, and SH Hah. A design expert system for auto-routing of ship pipes. Journal of Ship Production, 15(1):1-9, 1999.
Hui Kong, Tan Yan, and Martin DF Wong. Automatic bus planner for dense pobs. In 2009 46th ACM/EEEE Design Automation Conference, pp. 326-331. IEEE, 2009.

---

Under review as a conference paper at ICLR 2021
Mark R Kramer. The complexity of wirerouting and finding minimum area layouts for arbitrary vlsi circuits. Advances computing research, 2:129-146, -969,16,111 1984.
Haiguang Liao, Wentai Zhang, Xuliang Dong, Barnabas Poczos, Kenji Shimada, and Levent Bu- rak Kara. A deep reinforcement learning approach for global routing. Journal of Mechanical Design, 142(6), 2020.
Enrico Malavasi and Alberto Sangiovanni- Vincemiilii Area routing for analog layout. IEEE trans- actions on computer-aie aided design of integrated circuits and systems, 12(8): 1197, 1993.
Tarak Nath Mandal, Ankita Dutta Banik, Kaushik Dey, Ranjan Mchera, and Rajat Kumar Pal. Al- gorithms for minimizing bottleneck crosstalk in two-layer channel routing. In Computational Advancement in Communication Circuits and Systems, pp. 313-330. Springer, 2020.
Fan Mo, Abdallah Tabbara, and Robert K Brayton. A force-directed maze router. In IEEE/ACM In- ternational Conference on Computer Aided Design. ICCAD 2001. IEEE/ACM Digest of Technical Papers (Cat. No. 01CH37281), 404-407. IEEE, 2001.
Zhongdong Qi, Yici Cai, and Qiang Zhou. Accurate prediction of detailed routing congestion using supervised data learning. 2014 IEEE 32nd International Conference on Computer Design (ICCD), pp. 97-103. IEEE, 2014.
Ingo Rechenberg. Evolutionsstrategie:: Optimierung technischer systeme nach prinzipien der biolo- gischen evolution. frommann-holzbogg stuttgart, 1973. Step-Size Adaptation Based on Non-Local Use of Selection Information. In Parallel Problem Solving from Nature (PPSN3), 1994.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies as scalable alternative to reinforcement learning, arXiv preprint arXiv: 2017.
Robert R Schaller. Moore's ' law: past, present and future. IEEE spectrum, 34(6):52-59, 1997.
Daohang Shi and Azadeh Davoodi. Trapl: Track planning of local congestion for global routing. In Proceedings the
the 54th Annual Design Automation Conference 20/7, pp. 1 1-6, 2017.
David Silver. Cooperative pathfinding. AIIDE, 1:117-122, 2005.
Nathan R Sturtevant. The grid-based path planning competition. Al Magazine, 35(3):66- 69, 2014.
Aviv Tamar, Yi Wu, Garrett Thomas, Sergey Levine, and Picter Abbeel. Value iteration networks. In Advances in Neural Information Processing Systems, pp. 2154-2162, 2016.
Ronald J Williams. Simple statistical grodient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-22 1992.
Zhiyao Xie, Yu-Hung Huang, Guan- Qi Fang, Haoxing Ren, Shao- Yun Fang, Yiran Chen, and Jiang Hu. Routenet: Routability prediction for mixed-size designs using convolutional neural net- work. 2018 IEEF/ACM International Conference on Computer-Aided Design (ICCAD), pp- 1-8. IEEE, 2018
Ran Zhang. Study of Routing Algorithms for PCB Design. PhD thesis, 2016.
Yanheng Zhang and Chris Chu. Gdrouter: Interleaved global routing and detailed routing for ulti- mate routability. In Proceedings of the 49th Annual Design Automation Conference, pp. 597-602, 2012.
Quan Zhou, Xueyan Wang, Zhongdong Qi, Zhuwei Chen, Qiang Zhou, and Yici Cai. aceu- rate detailed routing routability prediction model in placement. In 2015 6th Asia Symposium on Quality Electronic Design (ASQED), pp. 119-122, IEEE, 2015.
10

---

Under review as a conference paper at ICLR 2021
A RANKING COST TRAINING
Algorithm Ranking Cost Training
Initialize: Graph G (V, E), vertex number m [V], nets (Ni, Mr), ranking parameter
0, E RR cost-map parameter 0g E _ learning rate, a, noise standard deviation or and de
evaluator number yl.
for ( = 1, 2, do
for i = 1.... n do
Sample 6, (0.
Get sampled ranking parameter 0, and cost maps parameter 0g with:
0, = 0, + 0r
(13)
0. 8. ocCi
Construct ranking order R and cost maps C' from 6, and 6-. Route nets on graph G with the ranking order and cost maps. Compute rewards rę F(O,., 0.) from routing results. end for
Collect all scalar reward {ri, ] from each evaluator. Compute normalized rewards {Fi. Fu } via Equation 12
Update ranking parameter 8, and cost map parameter 0g with:
0r 0, +
TJEJ
nd,
f=1
(14)
0g
+
TJCj
noc
j=1
end for
B ENVIRONMENT SETUP
To evaluate algorithm, we build grid map simulator the test environment. Algorithms evaluated on randomly generated grid maps. In the experiment, we take use of three different maps sizes: 16 16, 32 32 and 64 x 64. We construct two types of maps, i.e., simple
without obstacles and a more complex one with obstacles. All the start vertices and end vertices are also randomly generated in both simple maps and complex maps. Each map with size of 16 x 16 contain 4 start-end pairs, and 6 pairs for 32 x 32 and 10 pairs for 64 x 64. We randomly generate 50 maps for each size and each type and there are total 300 random maps. We report the success rate and the common average of total length of each algorithm. The success rate is the proportion of successfully connected maps to all random maps. Because different algorithm will have different connected maps, it is not fair to compare the average length over each algorithm's 's own successful maps. A algorithm with only one successful case may have lower average length than a algorithm with 100% success rate. Thus only report the average length over common successful maps of all algorithms. All the maps can be found in the supplementary material.
C DETAILS OF HYPER-PARAMETERS
For both Cost-Map Learning and Ranking Cost, the maximum training episode is 1000, learning rate is 0.001, the number of evaluators is 40, the noise standard deviation o, is 0.1 and o. is 0.1. All the rewards returned from evaluators will be scaled to [-1, 0]. When there not successful connection, reward of -1 will be given. Our code can be found in the supplementary material.
11

---

Under review as a conference paper at ICLR 2021
D RESULT OF RANKING ORDERS
Sample Number 5 10 15 20 25
30
35
40
45
50
100
200
Ranking Learning
Success Rate
0.08 0.12 0.16 0.16 0.22 0.16
0.22
0.20
0.20
0.22
0.22
0.24
0.30
Table The changes of success rates with different order sample numbers. The result shows that is hard to improve the performance by linearly increasing the sample number. The learned ranking order can achieve much better performance than randomly sampled orders.
E OTHER ROUTING TASKS
There are also some other routing problems, such as routing of hydraulic systems (Chambon & Tollenacre [991). routing of ship pipes (Kang et al. [999). routing of urban water sys- tems (Christodoulou & Ellinas 2010 Grayman et al. 1988). and routing of city logistics (Barceló al. 2007| Ehmke al. 2012) Multi-agent path finding, a task similar circuit routing, has been exhaustively studied in robotics and video games (Silver) 2005 Sturtevant 2014 Baabayn et al.)
2018 Atzmon al. 2020). But in multi-agent path finding task, paths allowed to intersect as long as the agents do not appear in the same place at the same time. To certain degree, circuit routing more difficult than multi-agent path finding tasks.
12


Reviews:
[{"review_id": "nPjOZyNq6rp", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\t\n\t1.  Summary & contributions\nThis paper develops an approach for solving a (simplified) circuit routing problem, which is to find non-intersecting paths between pairs of points (so called nets) in a grid. The paper uses a learning based approach based on OpenAI Evolution Strategies (OpenAI-ES) which learns 1) the order in which to route the different nets and 2) so called cost-maps for each net which provide additional guidance to the A* algorithm to account for later nets while routing earlier nets (i.e. to 'avoid the greedy pitfall').\n\n\t2. Strengths & weaknesses\nThe paper is well written and generally easy to follow and uses a principled and elegant approach to solving an interesting problem. I especially like the 'natural' way in which a learned policy integrates with A* search, and the resulting desirable properties. This makes the method a very principled approach.\n\nThe major limitation of this work is that the proposed method is only compared in terms of solution quality, and not by computational cost. From the specified parameters (up to 1000 training iterations with 40 parallel workers), the necessary compute seems orders of magnitude higher than the baselines, for example the 'random approach' which takes the best of 5 tries. To substantiate the claim that the method \"outperforms baselines with higher connectivity rates and better scalability\", I think at least baselines should be evaluated with the same computational budget, and ideally the trade-off between solution quality and computational cost should be explored.\n\nAlso, I wonder, why is the method not compared to Liao et al. 2020, He & Bao, 2020?\n\nAnother aspect which is relevant is that, if I understood correctly, the 'policy' consist only of the ranking parameters and the cost maps, and is thus tied to a specific instance of the circuit routing problem which cannot generalize to new instances, such that the training procedure should be run again for each new instance, adding to the high cost.\n\n\t3. Recommendation\nMy current assessment is that the paper is marginally below the acceptance threshold.\n\n\t4. Arguments for recommendation\nThe paper is of high quality, well written and well motivated, but the experiments lack a comparison of the algorithm and baselines with respect to computational cost, which is relevant to support the claim that this method outperforms baselines and has better scalability.\n\n\t5. Questions to authors\nCould you add experimental results with respect to running time or number of iterations, for example extend table D to a number of samples (40K ?) such that the running time is comparable with the proposed method?\n\n\t6. Additional feedback\nMinor comments/suggestions/compliments/questions:\n- The term 'score function J(theta)' can be confusing since typically the score function refers to grad log p_theta. Maybe 'objective function' could be an alternative?\n- Why does A* use Euclidean distance as heuristic and not Manhattan distance which seems more sensible in a grid?\n- I like the qualitative comparison which only compares length for problems solved by all solvers\n- What is the key that makes this approach more scalable compared to  Liao et al. 2020, He & Bao, 2020?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "dvmSyMe7p9", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary\n\nAuthor considers the circuit routing problem, where each net contains two nodes. The exact circuit routing problem is NP-hard in general, and author proposed to an approximate method. It uses several parameters to control the solution returned by a greedy search, i.e. the order of the nets to be routed and the greedy route selected by each net.  At last, evolution strategy is deployed to find the best parameter that results in the most optimal greedy solution. Author evaluated the method on multiple grid environments, and shows that the method performs better in terms of both accuracy and scalability compared to other similar methods that uses learning to find a good solution.\n\n### Strength:\nThe paper is organized very clearly, and all the ideas are demonstrated with good explanations and examples.\nI found the idea to be very simple and interesting. The algorithm seems to be quite easy to be implemented.\n\n### Weakness:\nI am concerning on the novelty of the paper. The paper uses parameter to control the execution of a sequential A* algorithm, and the parameters are updated using neural strategies. It is not clear why a sequential A* algorithm is selected here. For example, under what conditions of the routing problem, the coupling of evaluation strategy and the execution of a sequential A* algorithm can return an optimal solution.\n\nOn the significance part, I am not satisfied by experiments that author designs.\n* On the baselines: Currently author only selects baselines that utilizes learning. As the circuit routing is a well known problem, author should include some baselines using traditional methods to demonstrate the significance of deploying RC on the routing problems. \n* On the problem instances: Currently, author only considers the circuit routing in a grids with non-overlapping constraint. These problems can also be solved using traditional methods. Author can consider to evaluate RC on problems whose design constraint cannot be handled using traditional methods, as promised by the introduction. This can tighten the argument and reasonably narrow audience's focus on only the learning based algorithm.\n\n### Comments:\n* Have author tried to apply the idea of neural evolution on general combinatorial optimization problem,  e.g. approximate a Max-SAT problems? In particular, you can also learns a variable order and value order using the same formulation in RC. As many combinatorial problems can be reduced to Max-SAT, it potentially can increase the significance of the work.\n\n### Questions:\n* I found the problem is very similar to the disjoint vertex path problems. Is there any connection between the two problems?\n*During training, whether the learned ranking can be decoupled with the learned cost map? For example, can you still obtain a good routing plane using the same cost map while changing to a different order that is suggested by algorithm? What is the cost map for the first net in Figure 1f)? Does it shows any interesting structure so that you can still obtain a good routing plan if we try to route the second net before the first one? ", "extra_scores": {}, "extra_text": {}}, {"review_id": "Fi8PoCjMJfE", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\nSummary:\n \nIn this paper the authors attempt to solve the circuit routing problem through a novel approach of combining search-based routing techniques (e.g. A* search) and evolutionary strategies (e.g. OpenAI-ES). The authors define new parameters e.g. cost maps and a ranking parameter which improve the efficiency and effectiveness of their circuit routing solution. As opposed to heuristics based (2-step) routing solutions, the authors develop a solution which optimizes a single global cost function. This makes the solution easily scalable to new constraints and designs while avoiding sub-optimal solutions (common problem for 2-stage routing). The authors show that their approach doesn’t require human demonstrations or training data of any kind thereby giving their solution an edge over learning-based techniques requiring training data. Lastly, through experiments the authors establish that their approach is scalable to larger applications.\n\n\n##########################################################################\nReasons for score: \n \nThe authors present an all-round discussion for the different approaches to solve the circuit routing problem with their limitations. They also establish how the proposed approach excels where the previous approaches get stuck or give sub-optimal solutions. However, the authors do not present any information regarding the time complexity of their proposed approach. Along with that, the paper is also missing comparisons with the exact solutions proposed in past papers targeting this problem. Supplementary data and experiments can help alleviate these concerns. \n\nUpdated: The authors added the requested timing complexity data and additional experiments with better baselines to compare the proposed RC algorithm against. They present valid issues with reproducing some of the previous work. While a theoretical proof establishing the worst-case time complexity of RC to be better than random sampling plus Seq A* would be ideal. The empirical data presented does support the claim that RC algorithm is useful for finding more optimal solutions for large maps faster than Seq A* plus random sampling. \n \n##########################################################################\nPros:\n\n1.\tThe authors present a detailed description of existing approaches to solve the circuit routing problem along with the key limitations of the approaches discussed.\n2.\tSpecifically, since the proposed approach does not require training data or human demonstration, it has a big advantage on other learning-based methods. Since, training data for routing problems is hard to generate (time-consuming) or find easily (lack of open source benchmarks/data).\n3.\t Section 4 presents a well written incremental description of the proposed routing approach starting from ranking learning to cost map learning to ranking cost.\n4.\tThe experiments presented in Section 5, clearly demonstrate the superiority of the proposed approach over the baseline approaches considered in the paper.\n5.\tLastly, the ablation studies clarify the limitations of scaling the random sample bucket for rank learning. Figure 2 b) does a particularly good job of illustrating the usage of Cost maps. Further, the authors demonstrate the scalability of their approach to larger applications. Which are missing in the cited learning-based previous approaches.\n \n##########################################################################\nCons: \n \n1.\tThe presented approaches rely heavily on the ability of OpenAI-ES algorithm to learn the cost maps and ranking order that will help achieve optimal routing. It would be useful if the authors could present an analysis of the limitations of this algorithm. Are there any cases when it fails to converge to the optimal solution? Are there other alternative solvers that could replace this evolutionary strategy in such scenarios? \n2.\tSection 5, the choice of baseline approaches while covering the fundamental types of routing approaches (sequential, learning (RL) based, cost-map learning) do not show performance compared to the related works cited in the paper. For instance, Liao et al. (2020), He and Bao (2020), or 2-stage routing algorithms. \n3.\tWhile the authors correctly list the limitations of heuristic based (2-stage) routing algorithms, they fail to credit their simplicity which can be critical when routing very large-scale designs like VLSI chips. Such a tradeoff of simplicity vs optimality of solution would require a comparison of the time complexity of the different approaches analyzed in this paper and how they scale with the complexity of the problem.\n4.\tAlbeit the heuristic based approaches might converge on sub-optimal solutions. However, if they are much faster than ranking cost, combining multiple trials of heuristics-based approaches with human expert interventions could give ranking cost a competition in finding the optimal routing faster.\n5.\tAbove suggested analysis of time complexity will help understand up to what number of random samples of ranking orders can be tried, while matching the time taken by ranking cost, for Sequential A* and VIN baselines. Thereby allowing for a fairer comparison in the results presented in Table 1.\n \n##########################################################################\nQuestions during rebuttal period: \n\n1.\tKindly address the concerns regarding time complexity of the proposed and past routing approaches as described in the Cons section.\n \n#########################################################################\nSome typos: \n\n(1)\tSection 2.3, “Recently, Liao et al. (2020) trained* a deep Q-network”.\n(2)\tSection 6, “Our method is a* one-stage”.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "EP5SlErXXGw", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers the problem of determining efficient routes for connecting pairs of source, destination points over a circuit board. Due to physical constraints no two routes may intersect, and the routes may not pass through obstacles if there are any. For efficient performance it is desirable that the paths are as short as possible; as such the authors consider minimizing the sum length of all the paths as the objective. The paper proposes a ranking cost algorithm that combines A* search with an evolution optimization technique for learning efficient routes. Experimental evaluations show the proposed approach outperforming an RL based approach.\n\nRouting in circuit boards is an important problem for the vlsi community. Moreover, the problem has a combinatorial optimization flavor to it, which have been considered and is of broad interest to the iclr community as well. The main issue I have with the paper is the lack of sufficient motivation given for the proposed solution. E.g., why A* search, why OpenAI-ES? To me the proposed approach feels a bit “non-standard”, which leaves me wondering why the authors chose to go via this route. Could you have solved this via an RL formulation in one stage for example? \n\nThe other issue I have is regarding generalization. Can the parameters learned by the proposed algorithm be used for finding routes in unseen circuit board (or nets) configurations? As far as I understand, both training and evaluation is done for a fixed board and nets configuration. If this is indeed the case, then how is the learning approach justified over well-known black-box optimization (e.g., simulated annealing, genetic algorithms etc.) or fast approximation algorithms (e.g., integer programming with time cut-off etc.)? \n\nMinor: is the variance parameter $\\sigma$ in AI-ES learned as well, or is only the mean learned? \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies an interesting problem motivated by VLSI design. The reviewers agree that there are interesting aspects of the RC algorithm. Nevertheless, the paper could be improved by a clearer characterization/apples-to-apples comparison to baselines, particularly regarding computation cost, use of parallelism, as well as a more thorough contrast to state of the art in general. Given the contribution is experimental, and this is a well studied problem, it is important to establish whether the solution is indeed best-in-class; cost due to training should be taken into account, and minimized to the extend possible. Going beyond the baselines considered here, as well as reviewing possible theoretical connections to other problems and guarantees, would also strengthen the paper.
Decision: Reject