Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a graph learning approach for solving the multi-robot task allocation (MRTA) problem. It frames the problem as a Markov Decision Process (MDP) and trains a policy with a graph neural network architecture using REINFORCE. Results show that the proposed approach scales better compared to a non-learning baseline and is more accurate than a multi-headed attention (MHA) approach.
main_review: **Strengths**

The paper tackles the important problem of MRTA that is typically a computationally expensive optimization problem. The proposed approach of learning heuristics to solve it quickly seems appealing. Since the optimization is over a graph, choosing a graph neural network architecture seems like a natural fit that scales for varying numbers of tasks and robots without retraining the model. The paper also presents a substantial evaluation comparing it to a SOTA non-learning baseline.

**Weaknesses**

The main weakness of the paper is that it is unclear from the results if the CAM policy is learning something meaningful. Without clearly showing this, it is difficult to accept the paper at this time. 

Looking at Tables 1 and 2, it appears that even though CAM is faster than BiG-MRTA, the performance of the policy is substantially worse. Interestingly, this is especially pronounced when the robot to task ratios are low (i.e. 1:10). This suggests that the policy being learned is possibly myopic, i.e., robots greedily pick tasks that suffices when ratios are high (1:5 or higher). 

I would like to see a qualitative result showing the actions chosen by CAM vs BiG-MRTA, especially in the low robot to task ratio regimes. This would help convince the reader that the policy being learned is indeed meaningful.

**Suggestions for improvement**

*Overall story*

The paper prescribes a very specific architecture for learning policies that solve MRTA problems. However, it does not offer much insight into why this approach is preferred over alternatives. For instance, an ablation study can be provided to show the relative importance of different components -- why do we need the attention layer as opposed to a simpler aggregation step in GNN, rounds of message passing in the graph, etc. Additionally, for readers unfamiliar with MRTA problems, the paper appears difficult to follow. The paper would benefit from providing more insight into why one needs to apply learning for this problem, why GNN architecture is natural, why RL over other paradigms such as imitation learning of offline solvers.

*Technical Points*

The paper assumes full observability, i.e., each robot has the full state of other robots. Practically, for real-world problems with communication bottlenecks, this seems unrealistic. It would be good to explain how this assumption can be relaxed for applications in practical settings. It was also unclear how the architecture scales to dynamically changing robots since the size of the context would vary, requiring retraining. Results in Section 5.2 claim that the same model scaled to a varying number of robots. It would be good to have a subsection in section 3 that explains how the varying context is handled. 

The reward function defined seems very sparse, i.e., 0 for all states until all tasks are inactive. Historically, REINFORCE performs poorly in such settings, mostly doing random explorations till it sees high reward states enough times. It could be interesting to compare this against an approach that uses imitation learning to bootstrap RL. For instance, the results show that the non-learning baseline BiG-MRTA does quite well, outperforming the proposed approach on many trials. How well does this approach fair against a baseline that imitates the BiG-MRTA policy? How much does REINFORCE improve upon this policy by using this as a warm start?

Finally, the visited tasks are masked after prediction. By doing this, the model has no idea that it should not put all probability mass on visited tasks. This may result in random tie breaks. How would the approach compare to a method that takes the visited tasks as input to the CAM model? 

*Formatting and style*

As presented, the paper appears dense and at times difficult to read. This is likely due to a lot of details pertaining to MRTA, architectural details, and result descriptions. These details can easily be moved to the appendix and the main body of the paper can focus on the higher-level interpretation of results (e.g. the proposed approach, though faster than big BiG-MRTA, actually performs poorer on rewards). I would also recommend minimizing the use of abbreviations or having a table of abbreviations for reference and using new line enumerations to further improve the readability of the paper.
summary_of_the_review: My overall recommendation is weak reject. While the paper tackles learning for a difficult optimization problem, it is not clear from the results whether it succeeded in learning something meaningful.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposed a neural architecture for learning to solve multi-robot task allocation (MRTA) problems. The MRTA problem is modeled as a MDP, and then the so-called covariant attention-based neural architecture (CAM) is proposed. The main paper contribution is the CAM architecture.

Case studies are presented in which the proposed CAM is compared with other learning based and non-learning based methods. In the reported experiments CAM obtained smaller errors (average cost) and smaller processing time.

main_review: 1. The paper is well written and well organized. The references are appropriate and the problem being addressed is very well explained.

2. One of the paper contributions is the modeling of the MRTA problem as a MDP over graphs. This formulation is important because it allows to propose the covariant attention-based neural architecture (CAM) to learn MRTA problems.

3. The CAM architecture is the main paper contribution. The CAM is basically an encoder-decoder architecture, it uses attention mechanisms in the encoder and in the decoder, it uses information of other agents (context), and it codifies spatial information using a Graph Neural Network. The author put nicely together all these different elements in the CAM, which is able learn appropriately MRTA problems.

4. The reported results are convincing. Case studies are presented in which the proposed CAM is compared with other learning based and non-learning based methods. In the reported experiments CAM obtained smaller errors (average cost ) and smaller processing time. CAM scales well with the number of tasks and the number of robots.

5. It could be good that authors could explain about the limitations of CAM. It can really be used in any CAM problem? Is it  easy to use? Is tit easy to model any CAM problem and to put as required by the CAM?

summary_of_the_review: This is a novel paper. The proposed covariant attention-based neural architecture (CAM) is a novel architecture as well as the modeling of MRTA problems as MPDs. Moreover, the use of the CAM architecture allows solving MRTA problems in a better way than using tradition methods. MRTA scales well with the number of robots/agents and with the number of tasks.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new method, including neural network architecture, for solving time-constrained multi-robot task allocation (MRTA) problems. The proposed approach models the target problem as a Markov Decision Process (MDP) over graphs and use Reinforcement Learning (RL) methods to solve the problem.
The proposed learning architecture is called Covariant Attention-based Mechanism (CAM). 
The architecture is shown to have better performance than an existing state-of-the-art encoder-decoder method regarding task completion, cost function, and scalability. Though the performance is still lower than non-learning-based baseline methods, i.e., BiG-MRTA, the computational cost is significantly smaller than the baselines.

main_review: The strength of the paper is that it proposed a new and effective method for MRTA problems. To interpret the task as an MDP is not new. However, the architecture based on the multi-head attention-based encoder-decoder network is interesting. 
The weakness of the paper is about the generality of the theory and the evaluation. In contrast with the general discussion and argumentation in the Introduction, the proposed method contains many specific formulation and network architectures (e.g., equations (1) and (2), and network architecture shown in Figures). How much generality does the proposed framework have? Which part actually did contribute to the performance? Ablation studies are expected to clarify these points. The evaluation was conducted in terms of generalizability, scalability, completion rate, and computation time. However, apparently, computation time and quality of solution have a trade-off relationship. The discussion or fair evaluation about the trade-off should be mentioned. For example, in a standard optimization problem, we can get a little worse solution by limiting the computational time (i.e., terminating the iterative algorithm). It is clearly shown that the proposed method is better in computation time. However, the performance considering the trade-off should be fairly discussed.  


<Minor comments>
1. Deterministic assumption:
They assume the dynamics are deterministic. However, their theory is based on MDP. Therefore, the approach seems to be naturally applied to a probabilistic environment as well. I suggest the authors mention this point.

2. The first sentence of 2.1 
The sentence starting with "The MRTA problem can…" may be inaccurate. (A graph itself is not a "problem.")

3. Too small figures and tables.
Many figures (e.g., 1) and tables (e.g., 3 and 4) are too small to read. Please make them larger and improve the readability. 

4. Highlight color
Table 3 and some tables in Appendix have a green background as a highlight. If you use the dark colors (e.g., green, blue and purple) as "highlight," the readability becomes significantly worse.
Please use other styles (e.g., underline or bold style).

5. Topline
In Table 1, BiG-MRTA is shown as a topline. It's better to use a different style that allows readers to easily distinguish the topline from baselines. For example, you can use a double line between BiG-MRTA and AM. 
Also, it helps readers grasp the information to give underline or bold to the best value. 

6. Qualitative evaluation
Only quantitative results are shown. Providing qualitative evaluations may help readers understand the characteristic of the proposed methods.



summary_of_the_review: This paper proposes a new learning architecture which is called Covariant Attention-based Mechanism (CAM), to solve time-constrained multi-robot task allocation (MRTA) problems using a learning-based approach. The method works in an appropriate manner, and empirical results show the advantage of the method. Also, the approach itself is based on a modern approach and is worth studying. 
As a whole, the paper is a good paper involving meaningful new information.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper introduces a deep graph policy learning method that chooses tasks for each individual robot in a swarm thus addressing the problem of single-task robot and single-robot task (SR-ST) multi-robot task allocation (MRTA). The proposed method is based on the work by Kool et al (2019) with the main theoretical extensions on (1) adding constrains to the optimization objective of MRTA and (2) improving the encoder.
main_review: Strengths:

+ The idea of using learning methods to solve a SR-ST MRTA problem is interesting. 

+ Discussion of the technical approach is clear.

Weaknesses:

- The theoretical novelty is not high. The decoder and the training algorithm REINFORCE are similar or identical to the method by Kool et al (2019). The main novelty is to add constraints to the optimization objective of MRTA. However, it is not clear what new challenges are caused by adding the constraints? Theoretically, why does these constrains make the optimization problem more challenging to solve?

- The paper states that "this MRTA problem is adopted from Ghassemi et al (2019) with the modification of removing payload". However, the optimization problem introduced in Ghassemi et al (2019) includes other constraints that are ignored by the paper. Other than payload, why other constraints are removed?

- What is the meaning of t? The paper explains that "the transition is an event-based trigger", so it seems that t means the index of events (e.g., in Figure 1). In this case, when an event happens and all robots choose their tasks, how to guarantee that no multi-robots select the same task?

- The terms generalizability and scalability are used throughout the paper. But they are not clearly defined, and in some places, they are used interchangeably, e.g., "generalizing to problem scenarios that are larger in size".

- The experimental results are not clearly presented, especially the evaluation metrics. Besides the issue of clearly defining generalizability and scalability, can the authors provide the single value metric to quantify generalizability and scalability?

- What are the task completion time of each approach for the testing scenarios in Table 1 and Table 2?

- Without a centralized system, assuming each robot knows the information from all other robots in the swarm is not practical for real-world swarm applications.  

- Minor: The variable t_i is used for both deadline and event/timestep index.

summary_of_the_review: Although the idea of using learning to address MRTA problems is interesting, the paper is preliminary and will need significant improvements on novelty justification, terminology definition, and experimental result presentation.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper considers the multi-robot task allocation problems. To address the limitations of existing studies, such as real-world constraints, larger-sized problems and generalizations, this paper proposed a learning architecture, Covariant Attention-based Mechanism. They further conduct adequate evaluations and the results have shown great improvements over the state-of-the-art methods.


main_review: This paper considers a very real-world problem, and there are many details in the context. The reviewer is not very familiar with this sub-area. As an application paper, it might be acceptable that the proposed method is a combination of some commonly used architectures or algorithms, such as multi-head attention, encoder-decoder and RL algorithms. In general, the technical novelty is not enough, although the empirical results are significant. Specifically, the reviewer is not sure what insights can this paper bring to AI community. 
summary_of_the_review: An application paper with adequate evaluations.
review_title: null

Meta-review: The paper considers the problem of solving time-constrained multi-robot task allocation (MRTA) problems. Formulating the problem as a Markov decision process (MDP), the paper proposes Covariant Attention-based Mechanism (CAM), a graph neural network-based policy that can be trained to solve MRTA problems via standard RL methods. The encoder adapts the covariant compositional network to improve generalizability, while the decoder extends a recent combinatorial optimization architecture to the multi-agent optimization domain. Experimental results demonstrate that CAM outperforms an encoder-decoder baseline in terms of task completion, generalizability, and scalability, while also providing greater computational efficiency than non-learning baselines.

The paper considers an important topic---multi-agent task allocation is an interesting and challenging combinatorial optimization problem. The proposed CAM architecture adapts existing components in an interesting way and seems sensible for the MRTA domain. The reviewers initially raised concerns regarding the conclusions that can be drawn from the experimental evaluation, the significance of the algorithmic contributions, as well as the motivation for the proposed approach. The authors made a concerted effort to address these concerns through the addition of new experimental evaluations (e.g., comparisons to a myopic baseline and ablation studies), updates to the text, and detailed responses to each reviewer. Unfortunately, only one reviewer responded and updated their review (increasing their score). In light of this, the AC also reviewed the paper. The AC agrees with the strengths identified by the reviewers (including those noted above) and with the contributions provided by the additional evaluations. However, the paper remains unnecessarily dense, while at the same time not being self-contained (e.g., the new experimental results are relegated to the appendix rather than appearing in the main text). The paper would also benefit from a more concise motivation for learning-based solutions to MRTA and a clearer discussion of the paper's contributions.
Decision: Reject