Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: 	
	1.  Summary & contributions
This 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').

	2. Strengths & weaknesses
The 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.

The 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.

Also, I wonder, why is the method not compared to Liao et al. 2020, He & Bao, 2020?

Another 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.

	3. Recommendation
My current assessment is that the paper is marginally below the acceptance threshold.

	4. Arguments for recommendation
The 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.

	5. Questions to authors
Could 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?

	6. Additional feedback
Minor comments/suggestions/compliments/questions:
- 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?
- Why does A* use Euclidean distance as heuristic and not Manhattan distance which seems more sensible in a grid?
- I like the qualitative comparison which only compares length for problems solved by all solvers
- What is the key that makes this approach more scalable compared to  Liao et al. 2020, He & Bao, 2020?

review_title: Interesting and well written paper but experiments can be improved

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.

Routing 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? 

The 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.)? 

Minor: is the variance parameter $\sigma$ in AI-ES learned as well, or is only the mean learned? 

review_title: Do the learned policies generalize to unseen board configurations? 

final_score: rating: 6: Marginally above acceptance threshold
review_content: ##########################################################################
Summary:
 
In 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.


##########################################################################
Reasons for score: 
 
The 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. 

Updated: 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. 
 
##########################################################################
Pros:

1.	The authors present a detailed description of existing approaches to solve the circuit routing problem along with the key limitations of the approaches discussed.
2.	Specifically, 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).
3.	 Section 4 presents a well written incremental description of the proposed routing approach starting from ranking learning to cost map learning to ranking cost.
4.	The experiments presented in Section 5, clearly demonstrate the superiority of the proposed approach over the baseline approaches considered in the paper.
5.	Lastly, 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.
 
##########################################################################
Cons: 
 
1.	The 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? 
2.	Section 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. 
3.	While 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.
4.	Albeit 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.
5.	Above 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.
 
##########################################################################
Questions during rebuttal period: 

1.	Kindly address the concerns regarding time complexity of the proposed and past routing approaches as described in the Cons section.
 
#########################################################################
Some typos: 

(1)	Section 2.3, “Recently, Liao et al. (2020) trained* a deep Q-network”.
(2)	Section 6, “Our method is a* one-stage”.

review_title: Review for Submission 45

final_score: rating: 5: Marginally below acceptance threshold
review_content: ### Summary

Author 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.

### Strength:
The paper is organized very clearly, and all the ideas are demonstrated with good explanations and examples.
I found the idea to be very simple and interesting. The algorithm seems to be quite easy to be implemented.

### Weakness:
I 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.

On the significance part, I am not satisfied by experiments that author designs.
* 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. 
* 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.

### Comments:
* 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.

### Questions:
* I found the problem is very similar to the disjoint vertex path problems. Is there any connection between the two problems?
*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? 
review_title: An interesting application of evolution strategies on a combinatorial problem, but the evaluation is limited.

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