Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: I recommen the paper to be accepted. It is well written paper addressing an imporant use case, allocating multi-robot tasks, e.g. UAVs in the case of flood disaster. Introduction gives credit to previous work and motivation for the research. Paper discusses the development of a method called Covariant Attention-based model (CAM) which expands the work of Kool et al (2019) into multi-robot tasks.  The theoretical background of the method is sufficiently explained and the novelty of the method is clear. Obtained results are compared against a state-of-the-art method and shown to outperform it.

The deficiency of the paper is the explanation of the experiments. It would interesting to understand how the allocation process is learned to be done, namely how would the learned process be applicable for a real scenario. Now it was only said that the area is one square kilometer and the task times vary, but more details of the simulations would give more insight ito the real usefullness of the method. 

Minor corrections:
Section 4.2 1 x 1 sq.km => I guess this should be 1 sq. km or 1x1 km?
Algorithm 1:  N epochs -> N epoch (r3)

review_title: Well written paper discussing multi-robot task allocation expanding existing robot task allocation method into the multi-robot case, however description of th test case experimenting the method quite limited.

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary
-------
The authors adapt an existing RL approach to combinatorial optimization to be used for their particular application of optimizing a fleet of UAVs (simulation) to deliver supplies. For this the problem is presented as a graph, a cost function is defined and an optimization is applied. 


Critique, Questions, and Discussion
-----------------------

1) In order to follow the explanation better I would recommend describing the task in more detail in 2.1: What are the actions? What is the exact optimization problem that is being solved? Figure 1 shows that the outputs of the architecture are the action probabilities, but the reader still does not know what the actions are and has no clear picture of the problem that is being solved.

2) Turns out the paper never mentions what the actions are and does not specify the MDP to which the reinforcement learning approach is being applied.

3) It is not explained how the competitor methods (AM) is adapted to the problem at hand.

4) I would recommend to clearly state somewhere in the beginning of the paper what are the specific contributions of this work from methodological standpoint.

5) It is not clear from the description of the task why formulating the problem as a graph is beneficial in this scenario. How does the distance information, for example, enter the decision-making of the agents? Maybe a clearer explanation of the task and the exact optimization problem would help the reader see it.

6) How efficient would be a classical (non-RL) solution on this particular problem? It would be interesting to see some numerical estimation of this that would explain the necessity for heuristics in this problem.


Recommendation and justification
--------------------------------
In my opinion the potential impact of this paper is not sufficient (even if perfectly executed) to be presented at ICLR. This work does not offer methodological novelties, and the particular application is of limited significance as the experiments are conducted on a toy problem, not on the real task that is given as motivation. To the best of my understanding this work is interesting from engineering standpoint as application of RL-based combinatorial optimization to a particular problem, but does not constitute scientific contribution.


Additional remarks
------------------
Typos
pg 3: "consist of multiple tasks located in different locationS"
pg 3: "Therefore its possible" -> it's
pg 4: "ThereforE we define a matrix"


--------------------- UPDATE Nov 30 ---------------------
-----------------------------------------------------------------

I find the updated manuscript to be a significant improvement over the initial version. The class of problems is now clearly described and the problem formulation explains the challenge and the need for an RL-based solution approximation.

Seeing now that this work is not about a particular deployment scenario, but rather aims to present a method that can be used to solve a general class of constrained routing problems, another set of question arise.

Probably the main limitation that precludes from evaluating the significance of contribution and seeing this work as general contribution to the list of solution for routing problem is the fact that is was evaluation on only single instance of such problem, with only single set of experiments parameters (20 robots / 200 tasks). Since the paper aims to propose a general method that is widely applicable is it only reasonable to expect to see experimental evidence that when applied to a diverse set of problems of this class it comes out on top. How does it fare against other similar routing optimization problems? How does if fare against other methods or AM is the only method that is worth comparing to?

With this in mind I am raising my score for this paper from 3 to 5 "Marginally below acceptance threshold". The reason for not going higher is the lack of demonstration of applicability of this methods to a wider range of problems.
review_title: An adaptation of an existing method to a particular domain, lacks significance

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper presents an interesting idea of using neural-network-based RL to solve a type of vehicle routing problems, where the vehicles are tasked with visiting spatial locations to deliver items, and are subject to load capacity and delivery time constraints. In order to solve this problem, the authors propose an encoder-decoder architecture to decide for each robot, where to move next. The encoder is inspired from the Covariance Compositional Networks and the decoder utilizes an attention module, and the network is trained via REINFORCE. The results show that the proposed method outperforms the baseline in unseen test cases, in terms of task completion rate and the specified cost function.


Overall, the idea of the paper is interesting. It extends the work by Kool et al. 2019 to incorporate constraints in the optimization problem, such as payload capacity and visit deadlines. However, the paper could be improved in terms of clarity and mathematical rigor. Moreover, the reviewer expects more extensive experiments to demonstrate the efficacy of the proposed method, as well as discussion on what enables the proposed method/network to work better). As such, the reviewer believes that this paper is not suitable for publication in its current form. However, the idea of extending the existing method to take into account various constraints is novel and useful, and the reviewer believes that an improved version of this paper would make a good contribution in the area of vehicle routing optimization.


Here are the detailed comments.
1. Contributions

$\quad$ It seems that in the paper, the authors are targeting a specific problem scenario: A team of robots are tasked with delivering items to some spatial locations, with load capacity constraints for the robots and delivery deadlines for the locations. This is an interesting scenario, but seems like a specific application, which makes the contribution of this paper a bit narrow. The reviewer believes that the proposed learning-based approach could actually be applied to a wider range of "standard" vehicle routing problems with temporal constraints, such as the orienteering problem with time window/deadlines, the TSP with time window/deadline, the prize-collecting TSP with temporal constraints, some of which are discussed in Nunes et al. 2017, in addition to the problem studied in the paper. The reviewer encourages the authors to consider these possibilities and also compare with the state-of-the-art optimization-based and learning-based methods for some of these standard problems.


2. Clarity

There are many things that could have been explained more clearly. Here are a few examples.

$\quad$ a. There should be a formal definition of the optimization problem, which shows the objective function, the constraints, and the variables to be optimized. The authors should also explain what the solution looks like, e.g., it's a sequence of locations to be visited for each robot. Although such information might be pieced together from different places in the paper, it'd be of a great value to present a formal optimization formulation.

$\quad$ b. There are no clear descriptions of what the obtained decision rule is like. While it could be understood from the network architecture and descriptions here and there that each robot runs the network to obtain the next location (unless it runs out of battery and/or items), a clear algorithmic description of the decision rule should be provided.

$\quad$ c. In Sec. 2.3, for the context part, how are the current destinations of the other robots determined? It seems that each robot will need to wait for the other robots to compute their next destinations, before it can compute its own. But then how does one resolve the cyclic dependencies here?

$\quad$ d. There should be a discussion on what enables the proposed method to outperform the baseline, in terms of training speed and test performance.

$\quad$ e. The authors could provide an intuitive explanation about the permutation invariance in Sec. 2.3, in the context of this routing problem.

$\quad$ f. In the results section, it is not clear how the approach of Kool et al. 2019 is modified for the problem in this paper. What are the changes, and is it trained using the cost function of Eq. 9 or the original cost function in Kool et al. 2019? 

$\quad$ g.  The introduction of the problem type at the beginning of page 2 is confusing. It should actually be multi-robot task and single-task robots (based on Nunes et al. 2017). 

$\quad$ h. In the sentence above Sec. 1.1, what does multi-scale features mean here? What are the scales in the context of the routing problem in this paper?


3. Mathematical rigor

$\quad$ a. The matrix equation in Eq. 3 is problematic. The dimensions of $W$ and $d$ don't match. The authors probably want to left multiply $d$ with $W$.

$\quad$ b. In Eq. 5, the dimensions of $d_i^{Nb}$ and $d_i$ don't match and the subtraction cannot be performed. Although it is understood what operation the authors want to do here, this should be written properly.

4. Other comments

$\quad$ a. Typos. Here are just a few examples. Please check through the paper.

 $\quad$ $\quad$  page 1, salesmn -> salesman

  $\quad$ $\quad$ page 2, learn solve -> learn to solve

 $\quad$ $\quad$  page 3, extra hyphen between in and order 

  $\quad$ $\quad$ page 4, therefor -> therefore

$\quad$ b. Not properly-written sentences

  $\quad$ $\quad$ page 3, paragraph above Sec. 1.3, "this can be used to..." -> "which can be used to..."

  $\quad$ $\quad$ page 4, "Therefor we define a matrix $d_i^{Nb}$ as defined in Eq. 4."

$\quad$ c. In page 4, the notation for matrix/vector dimension is a bit strange, or at least the authors should define it. The authors could have used the standard way of "$W \in \mathbb{R}^{m\times n}$".

$\quad$  d. Fig. 2 and 3 are not properly placed and overlap with the text.


review_title: Interesting idea, but more clarity and more thorough experimentation are needed

Meta-review: This paper presents a GNN architecture for policies that solve multi-robot task allocation problems. The proposed architecture extends Koul et al (2019) by adding payload constraints and task deadlines. The paper looks at routing problems of medium-to-large size, e.g. 20 robots and 200  tasks. The reviewers are happy that most of their concerns were addressed by they are still concerned that the experimental validation is focusing too much on the multi-TSP or Vehicle Routing Problems, and request more extensive experimental validation on similar optimization problems as in Nunes et al (2017). I tend to agree. The proposed method has a lot of merit and just needs one more iteration of improvements to incorporate further experiments, before it becomes ready for publication. 

   
Decision: Reject