Learning to Solve Multi-Robot Task Allocation with a Covariant-Attention based Neural Architecture
Authors: Steve Paul
Payam Ghassemi
Souma Chowdhury
Venue:  (2021)
Keywords: Graph neural network
Attention mechanism
Reinforcement learning
Multi-robotic task allocation

Abstract: This paper presents a new graph neural network architecture over which reinforcement learning can be performed to yield online policies for an important class of multi-robot task allocation (MRTA) problems, one that involves tasks with deadlines, and robots with ferry range and payload constraints and multi-tour capability. While drawing motivation from recent graph learning methods that learn to solve combinatorial optimization problems of the mTSP/VRP type, this paper seeks to provide better convergence and generalizability specifically for MRTA problems. The proposed neural architecture, called Covariant Attention-based Model or CAM, includes three main components: 1) an encoder: a covariant compositional node-based embedding is used to represent each task as a learnable feature vector in manner that preserves the local structure of the task graph while being invariant to the ordering of graph nodes; 2) context: a vector representation of the mission time and state of the concerned robot and its peers; and 2) a decoder: builds upon the attention mechanism to facilitate a sequential output. In order to train the CAM model, a policy-gradient method based on REINFORCE is used. While the new architecture can solve the broad class of MRTA problems stated above, to demonstrate real-world applicability we use a multi-unmanned aerial vehicle or multi-UAV-based flood response problem for evaluation purposes. For comparison, the well-known attention-based approach (designed to solve mTSP/VRP problems) is extended and applied to the MRTA problem, as a baseline. The results show that the proposed CAM method is not only superior to the baseline AM method in terms of the cost function (over training and unseen test scenarios), but also provide significantly faster convergence and yields learnt policies that can be executed within 2.4ms/robot, thereby allowing real-time application.

Under review as a conference paper at ICLR 2021
LEARNING TO SOLVE MULTI-ROBOT TASK ALLOCA- TION WITH A COVARIANT-ATTENTION BASED NEURAL ARCHITECTURE
Anonymous authors Paper under double-blind review
ABSTRACT
This paper presents a new graph neural network architecture over which reinforce- ment learning can be performed to yield online policies for an important class of multi-robot task allocation (MRTA) problems, one that involves tasks with dead- lines, and robots with ferry range and payload constraints and multi-tour capa- bility. While drawing motivation from recent graph learning methods that learn solve combinatorial optimization problems of the mTSP/VRP type, this paper seeks to provide better convergence and generalizability specifically for MRTA problems. The proposed neural architecture, called Covariant Attention-based Model or CAM, includes three main components: 1) an encoder: a covariant compositional node-based embedding is used to represent each task as learn- able feature vector in manner that preserves the local structure of the task graph while being invariant to the ordering of graph nodes; 2) context: vector rep- resentation of the mission time and state of the concerned robot and its peers; and 2) a decoder: builds upon the attention mechanism to facilitate a sequen- tial output. In order to train the CAM model, policy-gradient method based on REINFORCE used, While the new architecture can solve the broad class of MRTA problems stated above, demonstrate real-world applicability use a multi-unnanned aerial vehicle or multi-UAV-based flood response problem for evaluation purposes. For comparison, the well-known attention-based approach (designed to solve mTSP//RP problems) is extended and applied to the MRTA problem, as a baseline. The results show that the proposed CAM method not only superior to the baseline AM method in terms of the cost function (over train- ing and unseen test scenarios), but also provide significantly faster convergence and yields learnt policies that can be executed within 2, 2..s//rooo, thereby allow- ing real-time application.
INTRODUCTION
In multi-robot task allocation (MRTA) problems, we study how to coordinate tasks among a team of cooperative robotic systems such that the decisions free of conflict and optimize quantity of in- terest (Gerkey & Mataric 2004). The potential real-world applications of MRTA are immense, con- sidering that multi-robotics is one of the most important emerging directions of robotics research and development (Yang et al. 2018 Rizk et al. 2019). and task allocation is fundamental to most multi- robotic or swarm-robotic operations. Example applications include disaster response (Ghassemi & Chowdhury] 2018). last-mile delivery (Aurambout et al.) 2019), environment monitoring (Es- pina al.) 2011), and reconnaissance (Olson et al., 2012)). Although various approaches (e.g., graph-based methods (Ghassemi & Chowdhury 2018] Ghassemi et al.] 2019). integer-linear pro- gramming (II.) approaches (Nallusamy al. 2009: Toth & Vigol 2014; Cattaruzza et 2016 Jose & Pratihar 2016), and auction-based methods (Dias et al., [0066] Schneider et al. (015)) have been proposed to solve the combinatorial optimization problem underlying MRTA operations, they usually do not scale well with number of robots and/or tasks, and do not readily adapt to complex problem characteristics without tedious hand-crafting of the underlying heuristics. In the recent years, rich body of work has emerged using learning- based techniques to model solutions or intelligent heuristics for combinatorial optimization (CO) problems over graphs. The existing meth- ods are mostly limited classical CO problems, such multi-traveling salesman (mTSP), vehicle

---

Under review as a conference paper at ICLR 2021
routing (VRP), and max-cut type of problems. In this paper, we are instead interested in learning policies for an important class of MRTA problems (Korsah et al. 2013) that include characteristics such as tasks with time deadlines, robots with constrained payload and ferry-range, and ability to conduct multiple-tours.
In this paper, we show how such MRTA problems be modeled as Markov Decision Process over graphs, allowing us to learn task allocation policies by performing reinforcement learning (RL) over graphs. We specifically focus on class of MRTA problems that falls into the Single-task Robots, and Single-robot Tasks (SR-ST) class defined in (Gerkey & Mataric 2004] Nunes et al. 2017 Here, feasible and conflict-free task allocation is defined as assigning any task to only one robot (Ghassemi et al. (211)). Subsequently, we propose new covariant attention- based model (aka CAM), neural architecture for learning over graphs to construct the MRTA policies. This architecture builds upon the attention mechanism concept and innovatively integrates an equivariant embedding of the graph to capture graph structure while remaining agnostic to node ordering.
1.1 MULTI-ROBOT TASK ALLOCATION
The MRTA problem can be formulated as an Integer Linear Programming (ILP) or mixed ILP. When tasks are defined in terms of location, the MRTA problem becomes analogical to the Multi- Traveling Salesmen Problem (mTSP) (Khamis et al. 2013)) and its generalized version, the Vehicle Route Plamning (VRP) problem (Dantzig & Ramser 1959). Existing solutions to mTSP and VRP problems in the literature (Bektas, 2006 [Baekers et al. 2016) have addressed analogical problem characteristics of interest to MRTA, albeit in a disparate manner, these characteristics include limited vehicle capacity, tasks with time deadlines, and multiple tours per vehicle, with applications in the operations research and logistics communities (Azi et al.. 2010 Wang et al. 2018). ILP-based mTSP-type formulations and solution methods have also been extended to task allocation problems in the multi-robotic domain (Jose& & Pratihar, 2016). Although the ILP--baed approaches can in theory provide optimal solutions, they are characterized by exploding computational effort as the number of robots and tasks increases TToth& & Vigol 2014, Cattaruzza et al. 2016). For example, for the studied SR-ST problem, the cost of solving the exact II.P formulation of the problem, even with linear cost function (thus an ILP), scales with On mm² n2²). where n, m, and h represent the number of tasks, the number of robots, and the maximum number of tours per robot, respectively (Ghassemi ctt al. 2019). As a result, most practical online MRTA methods, e.g., auction-based methods (Dias jet al. 2006 and bi-graph matching methods (Ghassemi & Chowdhury 2018), some sort of heuristics, and often report the optimality gap at least for smaller test cases compared to the exact ILP solutions. Recently, it has been shown that Graph Neural Networks (GNNs) can provide an alternative method with a computational efficient run-time (Kool et al. 2019).
1.2 LEARNING OVER GRAPHS
Neural network based methods for learning CO can be broadly classified into: (i) Reinforcement
Learning (RL) methods (Kool et al. 2019 Barrett et al. 2019 Khalil et al., 2017]; and (ii) supervised learning (often combined with RL) methods (Kaempfer & Wolf 20118 8 Mittal et al. 2019 Li al.)
2018 Nowak et al. (017)). . The supervised learning approaches typically address problem scenarios where samples abundant (e.g.. influence maximization in social networks (Mittal et al.. 2019) or inexpensive to evaluate (e.g.. TSP (Kaempfer & Wolf (018)), and are thus unlikely to be readily applicable to solve complex problems over real-world graphs. RL based techniques to learn on graphs include attention models with REINFORCE (Kool et al. (201)) and deep Q-learning (Khalil ct al. 2017 Barrett al. 2019). among others, with some extending solutions to multi-agent settings (Jiang et al. (020) In this work, we are interested in the first class of the methods (i.e., RL methods over graph space).
Dai et al. (2017) showed that combination of graph embedding and RL methods can be used to approximate optimal solutions for combinatorial optimization problems, as long as the training and test samples are drawn from the same distribution. Mittal et al. (2019) presented new framework to solve a combinatorial optimization problem. In this framework, Graph Convolutional Network (GCN) performs the graph embedding and Q-Learning learns the policy. The results demonstrated that the proposed framework is able to learn to solve unseen test problems that have been drawn from the same distribution that of the training data-set. More importantly, it has been shown that using a learnt network policy instead of tree search, both methods are using the same embedding GCN, showed a speedup of 5.5 for problem size of 20,000. Similarly, the effectiveness of learning
2

---

Under review as a conference paper at ICLR 2021
network policy using Q-Learning to solve the Max Cut problem (a combinatorial problem) has been demonstrated by Barrett et al. (2019).
Recently, there has been a growing interest in using
models (e.g., pointer
networks and attention mechanism) to encode and learn the combinatorial optimization problems in graph space (Kaempfer & Wolf 2018 Kool et al. 2019). Kool al. (2019) implemented framework using an encoder/decoder based on attention mechanism and REIN FORCE algorithm for solving wide variety of combinatorial optimization problem as graphs, with the main contribution being flexibility of the approach on multiple problems with the same hyper parameters. Majority of the above methods solve classical problems (i.e., mTSP, VRP and Max-Cur type of problems) with- out physical, real-world constraints. Taking into account additional physical characteristics such as robots with payload capacity and range constraints and tasks with time deadline requires fun- damental modification of the encoding and decoding mechanisms in the neural architecture, which motivates the research presented here.
In this paper, a new neural architecture is proposed that combines the attention mechanism with an enhanced encoding network (embedding layers), where the latter is particularly designed to capture local structural features of the graph in equivariant manner. The embedding layer is variation of Covariant Compositional Networks (CCN), introduced by Hy et al. (2018). This node-based embedding has been chosen since it: i) operates on undirected graph; ii) uses receptive field and aggregation functions based on tensor product and contraction operations (which are equivariant), which leads a permutation- and rotation-invariant embedding; and iii) provides extendable representation (n-th order tensor representation can be useful to extend the work to multi-level net- works, e.g., involving multiple node properties). We found an exact implementation of the CCN to be computationally burdensome for learning policies in large MRTA problems, and hence a variation of the CCN is proposed in this work.
1.3 CONTRIBUTIONS OF THIS PAPER
The general SR-ST problem studied here considers location-encoded tasks, meaning each task is defined as a robot visiting location and dropping a payload (the payload dropping time is ignored for simplicity of implementation). This setting can also be generalized to multi-agent problems addressing last-mile delivery applications. Unlike a single agent setting, the multi-agent setting leads to a combinatorial optimization problem with additional complexities, attributed to resolving conflicts between agents' decisions. Apart from the multi-agent setting, we also consider additional constraints for tasks and robots/agents. Each task-i in N is associated with a time deadline 4; by which the task has to be done in order for it to be considered as successfully completed. The constraints for the robots include: 1) Each robot has a limited range of distance that it can travel with full charge, i.c., in one tour; and 2) Each robot has maximum capacity of payload it can carry (bounding the max number of tasks it can perform in one tour).
With the above context, the primary contributions of this paper be stated as: 1) Formulating the studied class of MRTA problems as a Markov Decision Process or MDP over graphs, such that the optimal (task allocation) policy can be learned using an RL approach. 2) Extending the attention-based mechanism (AM) (Kool et al. 2019). serving as a decoder, and associated context to multi-agent combinatorial optimization setting; and 3) Incorporating a covariant compositional mechanism for node- based embedding (aka encoder) of the graph such that local structural informa- tion and associated task properties are preserved. The resulting CAM architecture is evaluated on a large representative (simulated) MRTA problem, which involves coordinating a team of multiple unmanned aerial vehicles (UAVs) to respond to flood victims by dropping survival packages. The simulation results provide important evidence of the promising convergence of the CAM method, and its advantage over the standard attention mechanism approach, in terms of the MRTA cost func- tion and scalability of the learnt policy with number of tasks. The remaining portion of the paper is organized as follows. Section 2 describes the MRTA problem definition and its formulation as 3 presents our proposed new graph neural network for the MRTA problem. Section 5 describes simulation settings and different case studies. Results, encapsulating the performance of these methods different-sizeet problems and various analyses of the proposed method, are presented in Section 6 The paper ends with concluding remarks.
MDP over graphs. Section
2 MRTA: PROBLEM DEFINITION AND FORMULATIONS
The multi-robot task allocation (MRTA) problem is defined as the allocation of tasks and resources among several robots that act together without conflict in the same environment to accomplish
3

---

Under review as a conference paper at ICLR 2021
common mission. The optimum solution (decision) of the MRTA problem is sequence of tasks (conffict-free allocation) that maximizes the mission outcome (or minimize the mission cost) sub- ject to the robots' capacity/urip bounds. Here, the following assumptions are made: 1) All robots are identical and start/end at the same depot; 2) There are no environmental uncertainties; 3) The location (#i, 3t) of task-i and its time deadline & are known to all robots; 4) Each robot can share its state and its world view with other robots; and 5) There is depot (Task-O), where each robot starts from and visits if other tasks are feasible to be undertaken due to the lack of available range or payload. Each tour is defined as departing from the depot, undertaking at least one task, and return- ing to the depot. This MRTA problem a class of combinatorial optimization problems, which are expressed generally in graph space. In this section, we express the MRTA problem as MDP over graph. Then, MRTA formulated as an optimization problem.
2.1 MDP OVER A GRAPH
The MRTA problem can be represented as a complete graph 9 = (V, which contains a set of nodes/vertices (V) and set of edges (E) that connect the vertices to each other. Each node is a task, and each edge connects a pair of nodes. The weight of the edge (wir) represents the cost (e.g., distance) incurred by robot to take task-j after achieving task-i. For MRTA with N tasks, the number of vertices and the number of edges are N and N(N - 1)/2, respectively. Node is assigned a 3-dimensional feature vector d, [.,, V.]
In order to perform learning, the MRTA problem is defined as a Markov Decision Process (MDP) for each individual robot, which can be expressed as a tuple < 8, A, R. >. The components of the MDP are defined below. State Space (S): A robot at its decision-making instance uses a state E S, which contains the following information: 1) the current mission time, 2) its current location, 3) its remaining ferry-range (battery state), 4) its remaining payload, 5) the planned (allocated) tasks of its peers, 6) the remaining ferry-range of its peers. 7) the remaining payload of its peers, and 8) the states of tasks. The states of tasks contain the location, the time deadline, and the task status active, completed, and missed (i.e., deadline is passed). Action Space (A): The set of actions is represented as A, where each action a is defined as the index of selected task, {O...., N) with the index of the depot as O. The task 0 (the depot) can be selected by multiple robots, but the other tasks are allowed to be chosen once if they are active (not completed or missed tasks). (s'|s, a): A robot by taking action a at state s reaches the next state s' in a deterministic manner (i.e., deterministic transition model is defined). Reward (R): The reward function is defined -faus and is calculated when there is no more active tasks (all tasks has been visited once irrespective of it being completed or missed). Transition: The transition is an event-based trigger. An event defined as the condition that a robot reaches its selected task or visits the depot location.
2.2 MRTA AS OPTIMIZATION PROBLEM
The exact solution of the MRTA problem can be obtained by formulating it as the following integer nonlinear programming problem:
min feest = r pue--u(rr- u(-r)e-
subject to A set of integer linear constraints (Ghassemi et al. (2019)
A detailed formulation of the exact ILP constraints that describe the MRTA problem with capacity and range restrictions, multi-tours per robot and tasks with deadlines, can be found in this recent work on decentralized MRTA (Ghassemi al. 2019). Note that, in our paper we use a slightly different objective/cost function to better reflect the general problem setting presented here.
Here, we craft the objective function (Eq. I such that it emphasises maximizing the completion rate (i.e., the number of completed tasks divided by the total number of tasks); and if perfect com- pletion rate (100%) is feasible, then the traveled cost is also considered. In Eq. []. u(.) is the step function. The term of 1 1- r is defined as task completion rate; i.e., the number of completed tasks (Naucees)) divided by the total tasks (N) orr = N N-Nussas d, is a normalized value of the total dis- N
tance traveled by all robots in the team. The term d, is the average travelled distance over all robots (i.e., d, IN duoi
V2 N ). The terms N, and dotal represent respectively the number of robots and the total traveled distance by robot-í during the entire mission. The above objective function (Eq. (I) gives positive value if the completion rate is lower than 100%, otherwise it gives negative value.
4

---

Under review as a conference paper at ICLR 2021
3 COVARIANT ATTENTION-BASEE NEURAL ARCHITECTURE
Before describing the tech- nical components of the proposed Covariant Atten- tion Model, the so-called CAM neural architecture, we provide an illustration and summary description here of how this policy ar- chitecture is used by robots during an SR-ST operation. The CAM model for task allocation is called by/for each robot right when reaches its current destina- tion (task location or de- pot), in order to decide its next task or destination. Since full-observability is assumed across the multi-robot team and the policy-model execution-ting is almost negligible, the current setup is agnostic to whether the online CAM model executed centrally off-board or on-hoard each robot. As an exam- illustrates how robot-1 and robot-2 uses the CAM policy model to choose task at two different decision-making instances (t to and = t, respectively). Here, the in- puts the CAM model includes 1) the task graph information (i.e., the location of each task and its associated time deadline), 2) the current mission time, 3) the state of robot-r, and 4) the states of robot-r's peers. The CAM model then generates the probability of selecting each task as its output. A greedy policy to choose the task with the highest probability is used here, which thus provides the next destination to visited by that robot. It should be noted that the probability values for completed tasks and missed tasks (i.e., missed deadline) are set at O.
State
CAM: Graph Neural Network
Greedy Pollcy
Action:
Graph
Decoder
Selected
Encoder
Task
(a)
Time
to
Robot1
Context
("e
Poens
Output:
Selecting Task
CAM: Graph Neural Network
Greedy
Graph
Decoder
Pollcy
Actions Selected
Encoder
Task
(b)
Time
Robot-2
AHHA
Context
Poets
Figure Deployment of the MRTA policy model based on the CAM architecture. a) Robot-1 at to. b) Robot-2 at 41; here, the CAM output for previously selected task (e.g., task 2 in (b))
at O.
ple, Figure [
Task d
dg
Figure Tigure[showw shows the detailed architecture of CAM. As shown in this figure, the CAM model con- sists three key components, namely: Context, Encoder, and Decoder. The context includes the current mission time, the states of robot-r, and the states of robot-r's peers. The encoder and de- coder components are described below.
Node Features location
Context
Graph
Task time dead line
Current time
Robot-r
de Concat(d' V3
Current location
Linear(d))
Linear(d d))
Remaining range
Remaining payload
Concat(F F. F
3.1 CCN-INSPIRED NODE ENCODER
Peers
Linear
The main function the encoder to repre- sent the properties of each graph node and pre- serving its structural information into a contin- uous feature vector of dimension demted, which is digestible in the decoder. Each node i, has three properties which are the x-coordinate, y- coordinate, and the time deadline of the task. The encoding for each node should include its prop- erties and the its positional association with its neighboring nodes. We implement a variation of CCN Hy et al. (2018). We determine the near- est & (here we take = 5) neighbors of a node (N6.) based on the positional coordinates (z and y). The first step is to compute feature vector by linear transformation for each node i.
Planned task
F
Remaining range
Aggregate
Remaining payload
Encoder
Output:
MHA (Masked) Layers
Batch Normalization
Prob. of
Selecting Task
Batch Normalization
Sottmar
Lineas
Feedforward
Decoder
The architecture of the context, en- coder and decoder for CAM.
Figure 2:
To encode the node properties, do linear transformation of d; to get feature vector Fý for all i E [1, N). as shown in Eq.
Fd
W + ba
where W'd Rdontaa33 by Rddees For effective decision making, we also need to preserve the N as defined in Eq. (4)
structural information. Therefore we define a matrix d
(o))aa(d?)) Nb;
5

---

Under review as a conference paper at ICLR 2021
We do linear transformation of d, to get F, (as shown in Eq. (5)) which we believe captures the closeness of a node with its neighbours in terms of the node properties.
FND- = w-
df.) + b
(5)
where W.bb e Rd 8Nb Rl FNb captures the information about how close the node properties of neighbor nodes of node is to itself, which shows a representation of how important node i its neighbors, We compute the final embedding for each node using Eq. (
Fi Aggregate (W (Concat (F.". P( + by)
(6)
Here, W c Rddenss X deleneee where F; R Wd, ba. WNN, b4h, W, and by are learnable weights and biases. The Aggregate function here is the summation across all the columns of a matrix. This summation along with the relative difference in node properties, as in Eq. ( preserves permutation-invarian structural properties (cognizance of inter-node distances for example) of the graph. Note that, these operations make the encoded state (w..t. a given node) insensitive to the order of the neighboring nodes, and thus the overall state space becomes independent of the indexing of tasks to rotations of the graph. These permutation-ings -nvvaiiineee characteristics are important for the consistency of the state space encoding, and further helps in the generalizability of the learnt policies (which should be cognizant of the structure of the task-space graph) over unseen scenarios.
by e RddemdaxX1, Thus finally we get an embedding F; for each node,
and the
3.2 ATTENTION CEANTION-BASED DECODER
Kool et al. (2019) presented an attention mechanism- model for solving combinatorial op- timization problem, where an attention-based encoder and decoder are implemented. Attention mechanism became popular because of it successful implementation in natural language process- ing. The intuition behind attention mechanism, is focus on the most relevant part (in terms of language translation). The same concept can be applied for a combinatorial optimization problem with sequential decision making.
The main objective of the decoder is to use the information from the encoder, and the current state as context, choose the best task by calculating probability value for each node. The first step is feeding the output from the encoder (as key-values) and information from the current state (as context) to multi-head attention (MHA) layer. The context for the MHA layer in this experiment consist of the following seven features: 1) Current time; 2) Available range of the robot taking decision; 3) Current location of robot taking decision; 4) Current payload delivery capacity: 5) Current destination of other robots; 6) Available range for other robots; and 7) Current payload delivery capacity for other robots. Figure 2 illustrates the structure of the decoder. Attention mechanism can be described as mapping query (Q) to set of key-value (K, V) pairs. The inputs, which are the query (Q), key (K), and values (V), are all vectors. The output is a weighted sum of the values V, weight vector is calculated by the compatibility function:
Attention (2, K, V) = softmax (QKT) TORKT/VDS /V
where d is the dimension of K or V. In this work we implement a multi-head attention (MHA) layer in order to determine the compatibility of Q with K and V. The MHA implemented this work is the same as the one implemented in (Kool et al. 2019) and (Vaswani et al. 2017). As shown in (Vaswani et al. 2017) the MHA layer can be defined as:
Multihead (Q, K. V)- Linear InnearrConcat(hadd, ...
(t..hheaadddddh...... head,.)
(8)
where head, Attention( K, V) and h is the number of heads. The feed-forward layer is to convert the output from the MHA layer to dimension that can be taken in for the next process. The final softmax layer outputs the probability values for all the nodes. The next task to be done will be chosen based on a greedy approach, which means the node which has the highest probability will be chosen. The nodes which are already visited will be masked such that it will not be chosen in the future time steps of the simulation.
4 LEARNING FRAMEWORK
Both the CCN inspired encoder and the attention- based decoder consist of learnable weight matrices as explained in Sections 3.I and 3.2 In order to learn these weight matrices, both supervised and unsupervised learning methods can be used. However, supervised learning methods are not tractable

---

Under review as a conference paper at ICLR 2021
since the computational complexity of the exact I(N)LP solution process required to generate labels. The complexity of the ILP formulation of the MRTA problem scales with On 2m²)"), where n, m, and h represent the number of tasks, the number of robots, and the maximum number of tours per robot, respectively Therefore, we use a reinforcement learning algorithm to conduct the learning.
Learning Method: In this work we implement simple policy gradient method (REINFÖRCE) as the learning algorithm with greedy rollout base- line, which also enables us to compare the effec- tiveness of our method with that of (Kool et al.] 2019). For each epoch, two sets of data are used which are the training set and the validation set. The training data set is used to train the training model (fCAM) while the validation data set is used to update the baseline model (0CAM) ). The size of the training data and the validation data used for this paper is mentioned in Section 5.1 Each sam- ple data from the training and validation data-set consist of graph as defined in Section 2.1 The pseudo code of the training algorithm for our ar- chitecture is shown in Alg. [ It should be noted that the policy gradient method requires the eval- uation of a cost function, which defined be same as in Eq. ①]] Policy: We define the policy such that if the robot r' does not satisfy the con- straints in Eqs. 2 it returns to depot (i.e., a = 0). Otherwise the robot r runs the learnt CAM net- work and chooses the output (task) based a greedy approach (sclects a task with the highest probability value), as shown in Fig.
Algorithm 1 CAM - Training Algorithm
Inputs: Neppcct # of epochs, B: Batch size, Ng: Train- ing data size, No: Validation data size; OCAM: CAM model; O Baseline CAM model.
1: for epoch I...Nepuch do
2: Dir, Da <- GeneraleSSennaiiosNN.. (Nrr
3:
for step = 1.. L.. do
4:
Dub + RandSamplee M)
5:
Bl. .aan <- CalCost(0@A D(bb)
6:
a. Seon + -CalCos((OCMM: Dus)
7:
VC
$ ΣΣ (Jowe
(ons log softmax(a.)
8:
fCAM +- ADAAMALL, (CAM)
9:
avl Scanm t- CalCost( (BLL, Du)
10:
a, Sans +- CalCost(@raM: De))
11:
(ENg sul
ΣN Somi) Somi)
(T-Test( (am, BL) > c) then fCAM + ACAM
12:
13:
procedure CALCOST(8,)) D)
14:
a, fooa + 01.11
15:
for = 11.1D do
16:
a,, feomsi Simulation(O, D. aua
17:
18:
Jooa f- San U Jans
19:
return a, fas
5 CASE STUDIES
In this paper, consider flood disaster response application, where team of UAVs deliver survival kits to flood victims. Here we assume that the information on the locations of victims (tasks) is available priori. We design and execute a set of numerical experiments to investigate the performance of our proposed learning-based algorithm over graph space (CAM) and compare it with an extended version of a ofate-of-the-art graph learning- et al. (2019), so called attention-bused (AM) approach. In order to test and validate the approaches, a set of numerical experiments is designed to mimic flood scenarios. The results are compared in terms of the cost function (Eq. (1), and completion rate.
algorithm proposed by Kool
5.1 DESIGN OF EXPERIMENTS & LEARNING PROCEDURES
To evaluate the proposed CAM method, we define an MRTA case study with 20 UAVs and 200 task (flood vic- tims) locations. A 2D environment with 1 sq. km area is used for this purpose, with the time deadline of tasks varied from 0.1 to hour. A randomized sample case sce- nario is shown in Fig. 3 which depicts the task locations, depot location and task time deadlines. The UAVs are as-
1.0
1.0
0.8
Y-position [km]
Time Deadline
0.6
0,
0.4
sumed to have a range of km, a maximum capacity of 10 payloads and a nominal speed of 10 km/h. We assume in- stantaneous battery swap and payload replenishment are provided at depot location, which is used when UAVs re- turn to depot since they have either exhausted their (sur- vival kit) payloads or were running low on battery. It is important to note that the flood victim application is used here merely for motivation, and the CAM architec- ture is in no way restricted to this application, but can rather solve problems in the broad (important) class of capccty/ragge-costraaned and timed task-
0.2
0.0
0.0
0.0
0.2
0.4
0.6
0.8
1.0
X Xposiiton (km)
Figure 3: Sample scenario showing de- pot location (red star) and task locations (squares) colored by their time dead- lines.
7

---

Under review as a conference paper at ICLR 2021
constrained SR-ST problems. Moreover, even the policies learnt here for CAM demonstration on the described case settings can generalize to related SR-ST problems with up to 200 tasks, which represents a fairly large MRTA problem in reference to the existing literature in the MR domain.
To perform learning and testing of the learned model, we proceed as follows: Learning Phase: We use policy gradient reinforcement learning algorithm (REINFORCE with rollout baselines in this case) for learning the optimal policy. The learnable parameters in this architecture includes all the weights in the encoder and the decoder. The training is carried out for total of 200 epochs. Each epoch consists of 10,000 random training samples, which are evaluated and trained in batches of 100 samples. Testing Phase: In order to provide statistically insightful evaluation and comparison, 100 random test scenarios are generated for the 20-uav-200 saauuav----ask case study, such that the number of flood victims are constant (200) but their locations and time deadlines are different.
5.2 MODIFICATIONS TO AM
The attention-based mechanism (AM) reported by Kool et al. (2019) has been shown to solve a few different classes of single-agent/robot combinatorial optimization problems. To be able to imple- ment the AM method for our problem (for comparison with our CAM method), the AM method is adapted to multi-robot setting. For this purpose, we make the following three changes to the AM method: (i) The node properties that are defined Section a.re are used in AM; (ii) The context for the attention mechanism is modified to he the same as that used for CAM; and (iii) The cost function used for training is changed to that in Eq. (
5.3 SIMULATION AND FRAMEWORK SETTINGS
The "Python" " 3.7 and the 64-bit distribution of "Anaconda 2020.02" are used to imple- ment the MRTA approaches. The environment, CAM architecture, training algorithm, and the evaluation of the trained model, are all implemented in Pytorch-1.5. The attention- based architecture was also implemented in Pytorch. With the help of Pytorch, the training was deployed on two GPUs (NVIDIA tesla v100-pcie-16gb) with 16 GB RAM.
6 RESULTS AND DISCUSSION
0.20
Learning Curve:
In order to compare the sam-
Cost Cost Flunction
0.15
ple efficiency of the proposed CAM method with that of the AM approach, we run both methods with similar settings and plot their
0.10
CAM
learning curve (convergence history), as shown
0.05
AM
in Fig. As seen from this figure, our
CAM method converges faster and to a sig- nificantly better (by 69, 69.4% optimal cost func- tion value CAM 0.029) compared to AM (f = 0.093). In contrast to the 73 epochs taken by AM to converge, CAM reached the best cost value of AM only after epochs and reached its final converged value in 35 epochs. These results clearly demonstrate the better sample efficiency of our proposed method, CAM, in comparison AM. As described later the computational cost of each epoch for our CAM method is also ~22 minutes smaller than that of the AM method. Overall, our proposed approach reaches better cost function values significantly faster terms of number of training epochs, with the benefits being more pronounced in terms of wall time. The higher cost of AM could be in part attributed to directly implementing the encoding architecture of a transformer network (Vaswani et al. (2017);; this transformer mechanism was designed for machine translation and thus consists of multiple layers of Multi-head attention computations with a feed-forward struc- ture. In contrast, our CAM model uses simple linear transformations of the node properties and its relative differences in local neighborhoods to capture structural information. Thus the total number of learnable parameters in AM (almost 393600 weights) is significantly larger than that in our CAM architecture (almost 17400 weights), leading to slower convergence of the former.
0.
50
100
150
200
Epoch
Figure 4: Convergence plot comparing CAM and
AM for 200 epochs
Real-time Performance: Based on the epoch information in Section 5.1 the average time to com- plete a training epoch was found to be 12.48 min for AM and 10.17 min for CAM. The average decision making time of both methods are also comparable at 2233-2.4 ms.
Generalizability Analysis: Figure 5 shows the performance of the CAM and AM approaches for 100 unseen test scenarios in terms of cost function (the lower the better) and completion rate (the
8

---

Under review as a conference paper at ICLR 2021
higher the better). It can be seen from Fig. that our proposed CAM method outperforms the AM ap- proach by achieving 84% and 5% better median values of the cost function and the completion rate, respectively. We posit that the generalizability benefits of the CAM architecture can be attributed to its covariant compositional encoding, which is able to aggregate local node neighborhoods while remaining agnostic to node ordering. The local structure of the graph is not only important to effec- tive decision-making but also expected to be shared across various problems settings drawn from the same distribution, thereby promoting generalizability of policies when adequately captured.
Scalability Analysis: In order to study how the performance of the learnt model is gener- alizable to new unseen scenarios with differ- ent different task-space size (50 to 200 tasks),
0.20
100
Completion Rate [%6]
Cost Coxt Function
0.15
95
0.10
a set of tests are conducted with the 20-robot swarm. For each task size, 100 random see- narios are generated and tested. The results are shown in Fig. 6 In this figure, the dashed horizontal line shows the threshold value of O, where any cost below that line depicts a per- feet completion rate (100%); when imperfect, the net traveled distance is taken into consider- ation. The performance of both CAM and AM approaches improved by decreasing the number of total tasks. It can be seen from Fig. 6 that our primary method, CAM, outperforms the AM approach in all case scenarios. The proposed CAM method provided a 100% completion rate for 50-, 100-, and 150-task cases, while the AM method provides a 100% completion rate for 50- and 100-task cases, In terms of the cost function, the CAM method achieves up to 435% better values compared to the AM method.
90
0.05
CAM AM
CAM AM
Methods
Methods
(a) Cost function
(b) Completion rate
Figure 5: Generalizability analysis: The per- formance of the algorithms over 100 unseen test case scenarios. Each scenario includes 200 tasks and the swarm size is set at 20 robots.
7 CONCLUSION
Indicates 100% 0.0
task completion
In this paper, we proposed new graph neural network architecture, called CAM, for multi- robot task allocation problem with a set of com- plexities, including tasks with time deadline and robots with ferry range and payload capacity con- straints. This new architecture incorporates an encoder based on covariant node-based embed- ding and decoder based on attention mecha- nism. To learn the features of the encoder and decoder, the problem has been imposed as re- inforcement learning problem and it has been solved using a policy simple gradient algorithm, REINFORCE. In addition, to compare the per- formance of the proposed CAM method, an attention-based approach (aka AM) has been tended to be able to handle a multi-agent combi- natorial optimization problem (i.e., multi-robot task allocation problem).
Cost Cost Function
-0.2
CAM
-0.6
- AM
50
100
150
200
Number of Tasks
Figure 6: Varying task size for a 20-robot swarm: The performance of the CAM, and AM algorithms over varying task size for 100 un- seen test case scenarios per task size. The solid line shows the mean value and the shaded area shows the 95% confidence interval. The dashed gray line shows the threshold value of O. where any cost below of this line means a 100% com- pletion rate.
To evaluate the performance of the proposed architecture, and the extended version of AM are trained for 200 epochs and tested on 100 unseen case studies. Performance was analyzed in terms of cost function and completion rate. The new proposed architecture showed better sample efficiency than AM by reaching a better cost value only after 7 epochs versus 73 epochs of AM. Our primary method, CAM, outperformed the AM approach by achieving (up to) 84% better cost function value (in term of the mean value). The computational cost analysis showed that the proposed CAM model takes a few milliseconds to take a decision; hence, it is an excellent choice for online decision making (here, task allocation). A further study on the performance of both AM and CAM approaches on case studies with different number of tasks demonstrated that our proposed CAM method is superior to AM in all case studies. While the current method is operational over varying task size (the upper bound is the number of tasks that model has been trained on), it is not invariant to the size of swarm. One immediate future work is to expend the architecture to have swarm size invariant model.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Jean-Philippe Aurambout, Konstantinos Gkoumas, and Biagio Ciuffo. Last mile delivery by drones: An estimation of viable market potential and access to citizens across european cities, European Transport Research Review, 11(1):30, 2019.
Nabila Azi, Michel Gendreau, and Jean-Yve Potvin. An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles. European Journal of Operational Research, 202(3):756-76) 2010.
Thomas D Barrett, William R Clements, Jakob N Foerster, and Alex I Lvovsky. Exploratory com- binatorial optimization with reinforcement learning. arXiv preprint arXiv:1909.04063 2019.
Tolga Bektas. The multiple traveling salesman problem: overview of formulations and solution
procedures. Omega, 34(3):209-22) 219, 2006.
Kris Braekers, Katrien Ramaekers, and Inneke Van Nieuwenhuyse. The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 99:300-313, 2016.
Diego Cattaruzza, Nabil Absi, and Dominique Feillet. Vehicle routing problems with multiple trips. 4OR, 14(3):223-259, 2016.
Hanjun Dai, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems, 2017.
George B Dantzig and John H Ramser. The truck dispatching problem. Management science, 6(1): 80 80-91, 1959.
M Bernardine Dias, Robert Zlot, Nidhi Kalra, and Anthony Stentz. Market-based multirobot coor- dination: A survey and analysis. Proceedings of the IEEE, 1477):227-11270, 2006.
Maria Valera Espina, Raphael Grech, Deon De Jager, Paolo Remagnino, Luca locchi, Luca Marchetti, Daniele Nardi, Dorothy Monekosso, Mircea Nicolescu, and Christopher King. Multi- robot teams for environmental monitoring. In Innovations in Defence Support Systems-3, pp- 183-209. Springer, 2011.
Brian P Gerkey and Maja Matarić. A formal analysis and taxonomy of task allocation in multi- robot systems. The International Journal of Robotics Research, 23(9):939-953) 2004.
Payam Ghassemi and Souma Chowdhury. Decentralized Task Allocation in Multi-Robot Systems via Bipartite Graph Matching Augmented With Fuzzy Clustering. In Volume 2A: 44th Design Automation Conference, pp. V02AT03A014, American Society of Mechanical Engineers, aug 2018. ISBN 978-0-7918-5175-3 doi: 10.115/DETC2018-866666
Payam Ghassemi, David DePauw, and Souma Chowdhury. Decentralized Dynamic Task Allocation in Swarm Robotic Systems for Disaster Response: Extended Abstract. In 2019 International Symposium on Multi-Robar Robot and Multi-Agent Systems (MRS), pp. 83 83-85, New Brunswick, NJ, 8901062. URL https:
aug 2019. IEEE. ISBN 978 1-788-17781-221 -276--4 doi: 10.1109/MRS.200 201..89062.
//ieeexplore. Leee. org wwtp://////..eeeed/eoeeoo
Truong Son Hy, Shubhendu Trivedi, Horace Pan, Brandon M Anderson, and Risi Kondor. Predicting molecular properties with covariant compositional networks. The Journal of chemical physics, 148(24):241755, 2018.
Jiechuan Jiang, Chen Dun, Tiejun Huang, and Zongqing Lu. Graph convolutional reinforcement learning. In International Conference on Learning Representations, 2020. URL https:// openreview www.areviewnnet/eeee
Kelin Jose and Dilip Kumar Pratihar. Task allocation and collision-free path planning of central- ized multi-robots system for industrial plant inspection using heuristic methods. Robotics and Autonomous Systems, 40:34-42, 2016.
10

---

Under review as a conference paper at ICLR 2021
Yoav Kaempfer and Lior Wolf. Learning the multiple traveling salesmen problem with permutation invariant pooling networks. ArXiv, abs/ 0tts//803.096... 2018.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial op- timization algorithms over graphs. In Advances in Neural Information Processing Systems, pp. 6348-6358, 2017.
Alaa Khamis, Ahmed Hussein, and Ahmed Elmogy. Multi-robot task allocation: A review of the state-of-the-art. In Cooperative Robots and Sensor Networks 2015, pp. 31-51, Springer, 2015.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference Learning Representations, 2019. URL RtK.htttpp://pperevvieee
net/ ii 3d=
G Ayorkor Korsah, Anthony Stentz, and M Bernardine Dias. A comprehensive taxonomy for multi- robot task allocation. The International Journal of Robotics Research, 32(12):1495-1512 2013.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun, Combinatorial optimization with graph convolutional networks and guided tree search. In Advances in Neural Information Processing Systems, pp- 539-548, 2018.
Akash Mittal, Anuj Dhawan, Sahil Manchanda. Sourav Medya, Sayan Ranu, and Ambuj Singh. Learning heuristics over large graphs via deep reinforcement learning. arXiv preprint 1903:0090303333 2019.
R Nallusamy, K Duraiswamy, R Dhanalaksmi, and P Parthiban. Optimization of non-linear multiple traveling salesman problem using k-means clustering, shrink wrap algorithm and heua-heussss International Journal of Nonlinear Science, 8(4):480-487 2009.
Alex Nowak, Soledad Villar, Afonso S Bandeira, and Joan Bruna. A note learning algorithms for quadratic assignment with graph neural networks. stat, 1050:22, 2017.
Ernesto Nunes, Marie Manner, Hakim Mitiche, and Maria Gini A taxonomy for task allocation problems with temporal and ordering constraints. Robotics and Autonomous Systems, 90:55-70, 2017.
Edwin Olson, Johannes Strom, Ryan Morton, Andrew Richardson, Pradeep Ranganathan, Robert Goeddel, Mihai Bulic, Jacob Crossman, and Bob Marinier. Progress toward multi-robot recon- naissance and the magic 2010 competition. Journal of Field Robotics, 29(5):62--792, 2012.
Yara Rizk, Mariette Awad, and Edward W Tunstel. Cooperative heterogeneous multi-robot systems: a survey, ACM Computing Surveys (CSUR), 52(2):1-31, 2019.
Eric Schneider, Elizabeth Sklar, Simon Parsons, and A Tuna Özgelen. Auction-barnd -baed task alloca- tion for multi-robot teams in dynamic environments. In Conference Towards Autonomous Robotic Systems, pp. 246-257. Springer, 2015.
Paolo Toth and Daniele Vigo. Vehicle routing: problems, methods, and applications. SIAM, 2014.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. CoRR, abs/1706.03762, 2017.
URL http://// org/ htts//00.... 03762
Di Wang, Mengqi Hu, and Yang Gao. Multi-criteria mission planning for solar-powered multi- robot system. In ASME 2018 International Design Engineering Technical Conferences and Com- puters and Information in Engineering Conference. American Society of Mechanical Engineers Digital Collection, 2018
Guang-Zhong Yang, Jim Bellingham, Pierre E Dupont, Peer Fischer, Luciano Floridi, Robert Full, Neil Jacobstein, Vijay Kumar, Marcia McNutt, Robert Merrifield, et al. The grand challenges of science robotics. Science robotics, 3 3(14)),a 2018.
11


Reviews:
[{"review_id": "yXggKkUrhc1", "reviewer": "AnonReviewer4", "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": "Summary\n-------\nThe 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. \n\n\nCritique, Questions, and Discussion\n-----------------------\n\n1) 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.\n\n2) 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.\n\n3) It is not explained how the competitor methods (AM) is adapted to the problem at hand.\n\n4) I would recommend to clearly state somewhere in the beginning of the paper what are the specific contributions of this work from methodological standpoint.\n\n5) 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.\n\n6) 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.\n\n\nRecommendation and justification\n--------------------------------\nIn 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.\n\n\nAdditional remarks\n------------------\nTypos\npg 3: \"consist of multiple tasks located in different locationS\"\npg 3: \"Therefore its possible\" -> it's\npg 4: \"ThereforE we define a matrix\"\n\n\n--------------------- UPDATE Nov 30 ---------------------\n-----------------------------------------------------------------\n\nI 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.\n\nSeeing 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.\n\nProbably 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?\n\nWith 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.", "extra_scores": {}, "extra_text": {}}, {"review_id": "GQK0_nneKI", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "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.\n\nThe 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. \n\nMinor corrections:\nSection 4.2 1 x 1 sq.km => I guess this should be 1 sq. km or 1x1 km?\nAlgorithm 1:  N epochs -> N epoch (r3)\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "F-npOzNkFM", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "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.\n\n\nOverall, 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.\n\n\nHere are the detailed comments.\n1. Contributions\n\n$\\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.\n\n\n2. Clarity\n\nThere are many things that could have been explained more clearly. Here are a few examples.\n\n$\\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.\n\n$\\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.\n\n$\\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?\n\n$\\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.\n\n$\\quad$ e. The authors could provide an intuitive explanation about the permutation invariance in Sec. 2.3, in the context of this routing problem.\n\n$\\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? \n\n$\\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). \n\n$\\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?\n\n\n3. Mathematical rigor\n\n$\\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$.\n\n$\\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.\n\n4. Other comments\n\n$\\quad$ a. Typos. Here are just a few examples. Please check through the paper.\n\n $\\quad$ $\\quad$  page 1, salesmn -> salesman\n\n  $\\quad$ $\\quad$ page 2, learn solve -> learn to solve\n\n $\\quad$ $\\quad$  page 3, extra hyphen between in and order \n\n  $\\quad$ $\\quad$ page 4, therefor -> therefore\n\n$\\quad$ b. Not properly-written sentences\n\n  $\\quad$ $\\quad$ page 3, paragraph above Sec. 1.3, \"this can be used to...\" -> \"which can be used to...\"\n\n  $\\quad$ $\\quad$ page 4, \"Therefor we define a matrix $d_i^{Nb}$ as defined in Eq. 4.\"\n\n$\\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}$\".\n\n$\\quad$  d. Fig. 2 and 3 are not properly placed and overlap with the text.\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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