Learning to Solve Multi-Robot Task Allocation with a Covariant-Attention based Neural Architecture
Authors: Steve Paul
Payam Ghassemi
Souma Chowdhury
Venue: ICLR 2022 Submitted (2022)
Keywords: MRTA
Reinforcement learning
graph learning

Abstract: This paper demonstrates how time-constrained multi-robot task allocation (MRTA) problems can be modeled as a Markov Decision Process (MDP) over graphs, such that approximate solutions can be modeled as a policy using Reinforcement Learning (RL) methods. 
   Inspired by emerging approaches for learning to solve related combinatorial optimization (CO) problems such as multi-traveling salesman (mTSP) problems, a graph neural architecture is conceived in this paper to model the MRTA policy. The generalizability and scalability needs of the complex CO problem presented by MRTA are addressed by innovatively using the concept of Covariant Compositional Networks (CCN) to learn the local structures of graphs. The resulting learning architecture is called Covariant Attention-based Mechanism or CAM, which comprises: 1) an encoder: CCN-based embedding model to represent the task space as learnable feature vectors, 2) a decoder: an attention-based model to facilitate sequential decision outputs, and 3) context: to represent the state of the mission and the robots. To learn the feature vectors, a policy-gradient method is used. The CAM architecture is found to generally outperform a state-of-the-art encoder-decoder method that is purely based on Multi-head Attention (MHA) mechanism in terms of task completion and cost function, when applied to a class of MRTA problems with time deadlines, robot ferry range constraints, and multi-tour allowance. CAM also demonstrated significantly better scalability in terms of cost function over unseen scenarios with larger task/robot spaces than those used for training. Lastly, evidence regarding the unique potential of learning-based approaches in delivering highly time-efficient solutions is provided for a benchmark vehicle routing problem -- where solutions are achieved 100-1000 times faster compared to a non-learning baseline, and for a benchmark MRTA problem with time and capacity constraints -- where solutions for larger problems are achieved 10 times faster compared to non-learning baselines.

Under review as a conference paper at ICLR 2022
LEARNING TO SOLVE MULTI-ROBOT TASK ALLOCA- TION WITH A COVARIANT-ATTENTION BASED NEURAL ARCHITECTURE
Anonymous authors Paper under double-blle boinnd review
ABSTRACT
This paper demonstrates how time-conttrained multi-robot task allocation (MRTA) problems can be modeled as a Markov Decision Process (MDP) over graphs, such that approximate solutions can be modeled policy using Reinforcement Learning (RL.) methods. Inspired by emerging approaches for learning to solve related combinatorial optimization (CO) problems such multi-traveling salesman (mTSP) problems, a graph neural architecture is conceived in this paper to model the MRTA policy. The generalizability and scalability needs of the complex CO problem presented by MRTA are addressed by innovatively using the concept of Covariant Compositional Networks (CCN) to learn the local structures of graphs. The resulting learning architecture is called Covariant Attention-ban -baed Mechanism or CAM, which comprises: 1) an encoder: CCN-based embedding model to represent the task space as learnable feature vectors, 2) decoder: an attention- based model to facilitate sequential decision outputs, and 3) context: to represent the state of the mission and the robots. To learn the feature vectors, policy-gradiens method is used. The CAM architecture found to generally outperform a state- of-the-art art encoder-decoder method that is purely based Multi-head Attention (MHA) mechanism in terms of task completion and cost function, when applied class of MRTA problems with time deadlines, robot ferry range constraints, and multi-tour allowance. CAM also demonstrated significantly better scalability in terms of cost function over unseen scenarios with larger task/robot spaces than those used for training. Lastly, evidence regarding the unique potential of learning- based approaches delivering highly time-efficient solutions is provided for a benchmark vehicle routing problem where solutions are achieved 100-1000 times faster compared to a non-learning baseline, and for benchmark MRTA problem with time and capacity constraints where solutions for larger problems are achieved 10 times faster compared to non-learning baselines.
INTRODUCTION
In multi-robot task allocation (MRTA) problems, study how to coordinate tasks among team of cooperative robotic systems such that the decisions are free of conflict and optimize a quantity of interest (Gerkey & Matarić 2004). The potential real-world applications of MRTA are immense, considering that multi-robotics is one of the most important emerging directions of robotics research and development, and task allocation is fundamental to most multi-robotic or swarm-robotic opera- tions. Example applications include disaster response (Ghassemi & Chowdhury 2018). last-mile delivery (Aurambout et al. 2019), ) environment monitoring (Espina et al.) (011] 1). reconnaissance (Ol) son et 2012) and combat Behjat et al. 22021) Although various approaches (c.g., graph-based methods (Ghassemi al. 2019), integer-lineat programming (ILP) approaches (Nallusamy et al.
2009 Toth & Vigo 2014), 1, and auction methods (Dias et al., 2006 Schneider et 20.55) 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 on using learning- based techniques to model solutions intelligent heuristics for combinatorial optimization (CO) problems over graphs. The existing methods are mostly limited to classical CO problems, such as multi-traveling salesman (mTSP), vehicle routing (VRP), and max-cut type of problems. We specifically focus on a class of MRTA problems that falls into the Single-tast 2004] NNnes et al., 2017). Based on iTax taxonomoy as defined in Gerkey & Matarić (2004), these problems fall into the In-schedule Dependencies (ID) category. Here, feasible and conflict-free task
Robots, and Single-robot Tasks (SR-ST) class defined in (Gerkey & Matarić

---

Under review as a conference paper at ICLR 2022
allocation is defined as assigning any task to only one robot (Ghassemi et al. 2019). For solving these problems, we propose a new covariant attention-based model (aka CAM), a 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. We implement CAM on original MRTA problem, suite of benchmark MRTA problems and benchmark VRP problems to perform generalizability, scalability and comparative analyses of the new method. We also perform an analysis on the impact of the neighborhood size on the performance on the benchmark MRTA problem.
1.1 MULTI- TASK ALLOCATION
In recent years, learning approaches based on Graph Neural Networks or GNN are being increasingly used to solve planning problems with a CO formulation, e.g., TSP, VRP, Max-Cut, Vertex,, and MRTA Kool et al. (2019): 90: [Barrett et al. (2099; Khalil et al. (2017); Kaempfer Wolf (2018): Mittal
ct al. (2019); Li ct al. (2018), Nowak et al. (2017); Wang & Gombolay (2020); Tolstaya al. (2020); Sykora et al. ) Dai et al. (2017). Further details on these related learning- -based studies can be found in Appendix A Some of the conventional ILP, MILP, and INLP based methods for MRTA have been discussed in Appendix [.I] GNNs provide the advantage of being able to capture both Euclidean features (e.g., task location), well oon-Euclidean features such as task capacity, task deadline and the local structure of task neighborhoods. The latter serves as higher-level meaningful features that assist in generalized decision-maker making These existing studies are however limited in three key aspects: 1) They address simplified problems that often exclude common real-world factors such as resource and capacity constraints Kool et al. (2019): KKemmper & Wolf (2018); Khalil et al.) (2017): [Tolstaya et al. (2020)) 2) They are mostly focused on smaller sized problems (< 100 tasks and 10 robots) Paleja et al. (2020); [Strens& Windelinekx (2005); |Wang& & Gombolay (2020);
(2019]]Kammpper
Sykora et al. (2020). with their scalability remaining unclear. 3) They rarely provide evidence of generalizing to problem scenarios that are larger in size than those used for training. This capability would be particularly critical since real-world MRTA problems often involve simulating episodes whose costs scale with the number of tasks and robots, making re- trainingg efforts burdensome. To address these gaps, here we propose new learning framework that can solve large- MRTA problems (SR-ST) with commonly considered constraints - involving up to 1000+ tasks and 200+ robots and generalize across even larger problem scenarios without the need to re-train. For most practical scenarios with larger number of locations, highly optimal solution is not always desired, while a good feasible solution the priority as pointed out by Cappart et al. (2021). Therefore, to enable scalable policies, we design a novel encoder based on the concept of Covariant Compositional Networks (CCN) Hy et al. (0018) which hypothesized to effectively combine local structural information with permutation invariance. The encoder is followed by decoder based on a Multi- Attention mechanism Kool et al. (2019); Vaswani et al. (2017) which fuses the encoded information and httpl//mmmiisioossspcifffi information (Context) using simple matrix multiplication, in order to enable decentralized sequential decision-making.
1.2 CONTRIBUTIONS OF THIS PAPER
The primary contributions of this paper can thus be stated as follows: 1) We formulate the general SR-ST class of MRTA problems as a Markov Decision Process or MDP over graphs with the multi- robot state information embedded as the context portion of the policy model, such that the (task allocation) policy can be learned using an RL approach. 2) We design the GNN that acts as the policy network an encoder-decoder architecture, where the encoder is innovatively based on covariant compositional networks (CCN), whose embedding capabilities significantly improve generalizability and scalability to larger task graphs and multi-robot teams. 3) We implement an attention based decoder (inspired by Kool et al. 2019g) to enable sequential decision-making, and specifically extend it a multi-agent combinatorial optimization setting. The proposed CAM architecture is evaluated on a representative MRTA problem that involves coordinating a team of unmanned acrial vehicles (UAVs) to efficinficy deliver flood relief. The results of this case study demonstrate how CAM clearly outperforms the state-of-the the-art art attention based method AM (Kool et al.) (2019). in terms of scalabilty and convergence, thereby emphasizing the effectiveness of the new encoder. Further case studies show that CAM continues to compare favorably to AM over benchmark MRTA problems (with time and capacity constraints) and CVRP problems. Comparisons to non-learning baselines for these benchmark problems demonstrate the significant online computation advantages of learnt policies, with the latter being 10-100 times faster. The remainder of the paper is organized as follows: Section defines the MRTA problem and its formulation as MDP over graphs. Section 3 presents
2

---

Under review as a conference paper at ICLR 2022
our proposed new GNN architecture. Section 4 describes simulation settings and different case studies. Results are discussed in Section 3
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 enviromment to accomplish common mission. The optimum solution (decision) of the MRTA problem is a sequence of tasks for each robot (conflict-free allocation) that maximizes the mission outcome (e.g., fraction of tasks completed) or minimize the mission cost (e.g., total distance travelled) subject to the robots' range constraints. Here, the following assumptions are made: 1) All robots are identical and start/end the same depot: 2) There are no environmental uncertainties; 3) The location (Ii, ys) of task-i and its time deadline T; known to all robots; 4) Each robot 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 no other tasks are feasible to be undertaken due to the lack of available range, Each tour defined departing from the depot, undertaking at least one task, and returning to the depot. 6) Motivated by the multi-UAV relief delivery problem, tasks are considered to be instantaneous, which means that reaching the waypoint associated with a task completes that task. This MRTA problem is a class of combinatorial optimization problems, which can be modeled in graph space. In order to learn policies that yield solutions to this CO problem, we express the MRTA problem Markov Decision Process (MDP) over a graph, described next. The optimization formulation of MRTA is then given in Section 2.2
2.1 MDP OVER A GRAPH
The MRTA problem involves a set of nodes/vertices (V) and a set of edges (E) that connect the vertices to each other, which can be represented as a complete graph G = (V, E). Each node represents a task, and each edge connects pair of nodes. Let Q be weight matrix where the weight of the edge (Wiy E Ω2) represents the cost (e.g.. distance) incurred by a 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 NNN - 1)/2, respectively. Node i is assigned a 3-dimensional feature vector denoting the task location and time deadline, i.e., d; [ yi, 7i] where i N]. Here, wij be computed as Wiy = / (z: 1 22)² (y: )2 where j,j E NJ.
The MDP defined in decentralized manner for each individual robot (to capture its task selection process) can be expressed as a tuple- < S,A, Pa. R >. The components of the MDP can be defined as: State Space (S): A robot at its decision-make maaknng instance uses 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) the planned (allocated) tasks of its peers, 5) the remaining ferry-range of its peers, and 6) 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). Here assume that each robot can broadcast its information to its peers without the need for a centralized system for communication, as aligned with modern communication capabilities Sykora al. (2020). Action Space (A)): The set of actions is represented as A, where each action a is defined as the index of the selected task, be selected by multiple robots, but the other tasks are allowed to be chosen once if they are active (not completed or missed tasks). Pa(s'Is, a): A robot by taking action a at state reaches the next state s' in deterministic manner (i.e., deterministic transition model is defined). Reward (R): The reward function is defined as - feost, 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 based trigger. An event is defined as the condition that a robot reaches its selected task or visits the depot location.
{0, (0. N) with the index of the depot O. The task O (the depot)
2.2 MRTA AS OPTIMIZATION PROBLEM
This MRTA problem is adopted from (Ghassemi et al. 2019: Ghassemi & Chowdhury, 2021 l) with the following modification - payload constraints are not imposed on the robot. The exact solution of the MRTA problem can be obtained by formulating it as an integer nonlinear programming problem, which can be summarily expressed as:
min foost =r ---u(rreee
(1)
[1 ifr 0 where r E 10,1] and u(r) - { otherwise
(2)
3

---

Under review as a conference paper at ICLR 2022
subject to -. <
(3)
dig S k [0
(4)
Here T. is the time at which task i was completed, A2 is the available range for robot at any point of time, and 61j is the distance between nodes i and j. A detailed formulation of the exact ILP constraints that describe the MRTA problem with range restrictions, multi-toun per robot and tasks with deadlines, can be found (Ghassemi & Chowdhury 2021). Note that, here use slightly different objective/cost function to better reflect the generalized setting for the class of MRTA problems with ferry-range and task-deadline constraints For compactness of representation, only the main constraints involved in the studied MRTA problem are shown in the above set of equations. We however consider all of the constraints, except the one related to payload capacity, as defined in the work by (Ghassemi & Chowdhury (021]; for detailed formulation of the MRTA problem, please refer to (Ghassemi Chowdhury] (022).
Here, we craft the objective function (Eg, equation 1 such that it emphasises maximizing the completion rate (i.e., the number of completed tasks divided by the total number of tasks); and perfect completion rate (100%) is feasible, then the travelled cost is also considered. The term of 1- r is defined as task completion rate; i.c., the number of completed tasks (NVscesss) ) divided by the total tasks (N) or r (N N susssss) /N. Here, d, is a normalized value of the total distance travelled by all robots in the team. The term d, is the average travelled distance over all robots (i.e., d, = -i== / ///////22///// N)). The terms N₂ and d! represent respectively the number of robots and the total traveled distance by robot-i during the entire mission. The above objective function (Eq. equation[] [ gives a positive value if the completion rate is lower than 100%, otherwise it gives a negative value. Equation [ ensurees that the objective function bounded in the range (-1,1).
3 COVARIANT ATTENTION-BANE
NEURAL ARCHITECTURE
For learning to work on the MDP defined over graphs in Section 2.1 we need to represent each node as a continuous vector, preserving its properties as well as the the structural information of the neighborhood of that node.
State
CAM: Graph Neural Network
Gready Policy
Actions Selecied
Graph
Decoder
Before describing the technical com- ponents of our proposed Covariant Attention Mechanism, the so-called CAM neural architecture, we provide an illustration and summary descrip- tion here of how this policy architec- ture is used by robots or agents dur- ing an SR-ST operation. The CAM model for task allocation is called by/for each robot right when reaches its current destination (lask location or depot), in order to decide its next task or destination. While robots are moving toward their selected task locations, they can check if their decision is conflicting with another robot based on recent information. If there is conflict, the robot with the worst time can cancel its current task and select a new task. Since full full-observability 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 is executed centrally off- or on-board each robot. As an example, Figure T iillustrates how robot-1 and robot-2 uses the CAM policy model to choose a task at two different decision decision-making instances (f to and = fz). Here, the inputs to the CAM model includes 1) the task graph information, i.e., the properties of all the tasks/nodes de and the computed weight matrix Ω, 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 strategy of choosing the task with the highest probability used here, which thus provides the next destination to be 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.
Encoder
Task
Time
Robot-1
Context
('o
Poars
Output: Prob. Serecinggg
CAM: Graph Neural Network
Greadly Policy
Actions Selected
Task Graph
Decoder
Encoder
PFR F.
Task
Time
Robot-2
Context
P
PoEss
Figure I: Deployment of an MRTA policy using CAM archi- tecture. a) Robot-1 at to- b) Robot-2 at f1; here, the CAM output for previously selected task (task 2 in (b)) is set at O.
Figure 2 shows the detailed architecture of CAM. As shown in this figure, the CAM model consists of 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 state of robot consists of it's destination x. y coordinates and the available range p. The encoder and decoder components are described below.
4

---

Under review as a conference paper at ICLR 2022
3.1 CCN-INSPIRED NODE ENCODER
For learning over graphs, the performance of the trained model depends mostly on the ability of
Query Idartas
Mission state
Key Idwasss N]
Value [deese N]
Node (1, N) los
feature (6)
Robot taking decision (f)
Peer robots i [1, N.1, it
the Graph Neural Network (GNN) to transform all the
Nour
Slack deriins
Contest
Uneartd
required node information into a feature vector or tensor. For case, apart from the node properties, some of the features that essential include a node's s local neighborhood infor- mation, and permutation invariance. Using a node's s local neighborhood infor- mation which consists of its association with its local neighbors during training is more beneficial than considering the association with the entire graph, for generalizing to unseen nodes as demonstrated by frameworks like GraphS AGE (Hamilton et al., 2017), thus enabling the GNN to generalize for problems with larger number of nodes without the need to re-train. The encoder represent the properties of each graph node (preserving its structural information) into continuous feature vector of dimension dembed, which fed to the decoder. Each node i, has three properties which are the x-coordinate (r), y-coordinate (y), and the time deadline (r) of the task. Note that our encoding mechanism can also be extended to a probabilistic scenario, for example where an estimated deadline follows probability distribution (common in disaster response type operations). The encoding for each node should include its properties and the its positional association with its neighboring nodes. We implement variation of CCN (Hy et al. (018). We determine the nearest neighbors of a node (Nb,) based on the positional coordinates (ær and y). The first step is to compute a feature vector by linear transformation for each node i. To encode the node properties, we do a linear transformation of d, to get a feature vector Fa, for all i E [1, NJ, i.e. Fa, Wddd + ba-
f
F Concat(Pe J N.h
Butch Nov mell tini
Hostch Nermal Hesttttt
NELA /// 1.00
Query Valuel
Linear(P
Sortmax iituitoll
Linser
Fend Peedgrware
p
Key:
Concat(F a. F!*t
Linear
Agarogate
Decoder
Encoder
Figure 2: CAM architecture with the information flow along the con- text, encoder & decoder. The node are represented by the colored circles, where the colors represents the time deadline. The robots are represented by the pentagon shapes and the robot highlighted (green) is the robot taking decision.
Here Wd e X3 ba 1 di [I,, yr Ti.. For effective decision making, we also need to preserve the structural information. Therefore we define a matrix F., as in equation
F&b- Concat(Fa,).
Nb,
(5)
We compute matrix F:N6 (as shown in Eq. equation 6 which we believe captures the association of a node with its local neighbours (one-hop neighbors) terms of the node properties.
F: = w No (FX) - Fa,) + Nb
(6)
where W.Nb Rddena x denvet 6.49 E x FrNb 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 is to its neighbors. Further explanation regarding this design choice is discussed in Appendix B and we strongly encourage the reader to go over the section.
We compute the final embedding for each node using Eq. equation
F. Aggregate (W (Concaat P(")) +by
Here, Wy E (gchetaa by IR [IddmmaddX1 Thus finally we get an embedding F; for each node, where F, E Rddeesss x1, Wd, ba, Whb Nb, Wy, and by are learnable weights and biases. The Aggregate function is the summation across all the columns of matrix. This summation along with the relative difference in node properties, as in Eq. cquation 6 preserves permutation-invaarince invariance and the structural properties (cognizance of inter-node distances for example) of the graph. Note that, these operations make the encoded state w.r.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 or to graph rotations. Equations 5 6 and 7 represents a single layer of encoding. Multiple layers of encoding can be performed with the output of the previous layer being the inputs to equations and i the next layer.
5

---

Under review as a conference paper at ICLR 2022
3.2 ATTENTION-BASEE BASED DECODER AND CONTEXT
The main objective of the decoder is to use the information from the encoder and the current state as context or query, and thereof choose the best task by calculating the probability value of getting selected for each (task) node. In this case, the first step is to feed the embedding for each node (from the encoder) as key-values (K, V). The key I and value V/ for each node is computed by two separate linear transformations of the node embedding obtained from the encoder. The next step is compute a vector representing the current state, also known as the context (as shown in bottom left of Fig. 2
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 destination of other robots; 5) Available range for other robots all concatenated to a single vector of length hyg which then undergoes a linear transformation to get a vector of length dembed also called the query Q. Figure 2 illustrates the structure of the decoder.
Now the attention mechanism can be described as mapping the query (Ω) to a set of key-value (K,, V) pairs. The inputs, which are the query (Q) is a vector, while K and V are matrices of size dembed x N (since there are N nodes). The output is a weighted sum of the values V, with the weight vector computed using the compatibility function expressed as:
Attention(KC, V, Q) = softmax (CTTax//T//////// (
(8)
Here hu is the dimension of the key of any node (k; K.) 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 in this work is similar to the decoder implemented in Kool al. (2019) and Vaswani itt al. (017). As shown in (Vaswani et al. 2017) the MHA layer can be defined as:
MHA(K,
Linear Innea(Concat(headd ... .headd.....dd...) ))
Here head, = Attention (K, V. Q) and he (taken as 8 here) is the number of heads. The feed- forward
layer is implemented to further process the mapping that results from the MHA layer, and transform it to dimension that is coherent with the number of nodes in the task-graph (N). The interjecting batch normalization layers serve to bound values of a specific batch using the mean and variance of the batch. The final softmax layer outputs the probability values for all the nodes. Here, the next task to be done is then chosen based on a greedy approach, which means that the node with the highest probability will be chosen. The nodes which are already visited will be masked (by setting its probability as 0) so that these nodes are not available for selection in the future time steps of the simulation of the multi-robot operation.
4 CASE STUDIES
We design and execute a set of numerical experiments described in Appendix D.3 to investigate the performance of our proposed learning-basse algorithm over graph space (CAM) and compare it with 1) an extended version of a state-of-the-a art graph learning- based algorithm proposed by (Kool et al., 2019), so called attention -reention-baeed mechanism (AM) approach; 2) a recent bipartite graph matching method BiG-MRTA (Ghassemi & Chowdhury 2021): : 3) a myopic baseline called Feasibility- preserving Random-Was Walk (Feas-RND) that takes randomized but feasible actions (avoiding conflicts and satisfying other problem constraints). Since the BiG-MRTA method has been shown provide near-optimal solutions in comparison to ILP (and competitive performance w.r.t. state-of-the-art online MRTA methods) Ghassemi & Chowdhury (202T), performance of AM and CAM. The Feas RND method on the other hand provides baseline that AM and CAM should clearly surpass in performance (cost function), in order to demonstrate that meaningful MRTA policies are being learnt as opposed to simply mapping random feasible actions.
used here to comparatively gauge
RESULTS AND DISCUSSION
5.1 GENERALIZABILITY AND SCALABILITY ANALYSIS OF CAM
The CAM model has been trained on scenarios with 200 tasks and varying robot size (randomly a robot size between 10 and 50 has been selected). Then, 100 test scenarios have been generated per robot-task size from the same distribution of training scenarios. In this paper, generalizability refers to the performance of the trained model on unseen test scenarios that involve the same (or lower) number of tasks as in the scenarios used for training; and where the test and training scenarios are drawn from the same probability distribution over task locations and deadlines. In this work, generalizability was analysed on test scenarios with the number of tasks fixed at 50 and 200, drawn from the same distribution over a 2D space, and number of robots fixed at 5 and 40. In this paper, scalability refers to the performance of the trained model over test scenarios with higher (and increasing) numbers of tasks and robots than that encountered in the scenarios used for training. Here, we analyze scalability

---

Under review as a conference paper at ICLR 2022
by evaluating the CAM model test scenarios with the number of tasks fixed at 500 and 1000, and the number of robots fixed at 50 and 1000. The task-to-robot ratio is however kept the same across the generalizability and scalability analysis cases, in order not to introduce another control factor affecting the numerical experiments. To measure and compare performance, we use two metrics: 1) Average cost function (Eq. D: This metric accounts for the completion rate of tasks and the total travelled distance, averaged over the set of test scenarios; and 2) Average computing time: This measures how long each method takes to compute the entire solution, averaged over the test set. The latter is particularly important to note in scalability analysis, since state-of- saae-of--the-and art non- non-learning based MRTA methods scale poorly in terms of computing efficiency as numbers of tasks and robots increases.
Table I: MRTA - Multi-UAV flood response: Generalizability; Task size (up to 200) and number of robots (up to 40). Average cost function (with the average computation time in seconds). Lower the better.
Table showw the cost function (the lower the better) for the unseen test scenarios for both AM and CAM. Note that the cost function (as defined by [q[ for MRTA produces negative value when the completion rate is 100%, while positive value indicates a task completion rate below 100%. As it can be seen from Table. [ that the proposed CAM approach outperforms the AM approach in all the test cases by achieving better mean values of the cost function, respectively. The CAM approach performs signifi- cantly better than AM in terms of the cost function for the lower task-to-robot ratio (here, 5). Based on table[] the proposed CAM approach achieved perfect completion rate for most of scenarios with the task-to-robot ratio of 5. The local structure of the graph is not only important for effective 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.
# of Tasks
# of Robots
Avg. Cost Function (Avg. Computing Time in seconds)
BiG-MRTA
Beas-RND
AM
CAM
5
-0.27 (0.21)
0.27 (0.5)
0.07 14)
-0.03 (0. 14)
50
10
-0.70 (0.20)
0.03 (0.3)
-0.20 (0.15)
-0.47 (0.16)
10
-0.47 (0.80)
0. (1.2)
0.10 (0.33)
0.01 (0.32)
100
20
-0.72 (1.21)
0.05 (0.8)
-0.16 (0.34)
-0.50 (0.34)
20
-0.66 (4.72)
0.34 (1.9)
0.09 (1.34)
0.04 (1.21)
200
40
-0.74 (8.37)
0.05 (1.1)
-0.07 (1.43)
-0.45 (1.40)
Table 2: MRTA - Multi-UAV flood response: Scalability w.r.t. number of tasks and robots; showing average cost function (and avg. computation time in sec). Lower the better.
To investigate the scalability of the learnt model, we use a new set of unseen test scenar- ios with numbers of tasks and robots much larger than
# of of Tasks
Avg. Cost Function (Avg. Computing Time in seconds) BIG-MRTA
Robots
Feas-RND
AMM
CAM
50
-0.73 (69.3)
0.34 (4.2)
0.10 (4.23)
0.07 (4.31)
500
100
-0.77 (135.3)
(2.6)
-0.02 (4,29)
-0.37 (4.71)
100
-0.76 (595.4)
0.34 (8.7)
0.09 (19.22)
0,06 (19.05)
1000
those of the scenar-
200
-0.76 (1420)
0.06 (5.4)
0.02 (20.00)
-0.31 (20.03)
ios used in training (the latter involved 200 tasks). T the performance of the trained model
of CAM and AM in terms of the cost function (lower the better) for four large case studies, involving 500-tasks- -ataakss----oooss..... 300-tasks-100--robott 100-robots, each case, 100 randomly generated scenarios (i.e., task locations and deadlines randomized) are used. As shown in Table 2 the proposed CAM method outperforms the AM method in all cases, with significant difference in the cost function for the case studies with the task-to-robot ratio of 5. In the largest case (i.e., 2000-task-200-robeee for most of the scenarios (Appendix F) It can be argued that, for time-critical problems such as MRTA in disaster response, generating an optimal solution is less of a priority, compared to generating a feasible near-optimal solution as quickly as possible; this capability of the learnt models in evident from the results in Table 7 in Appendix [ BiG-MRTA requires a significantly larger computing time for larger sized problem (see Fig. 5 in Appendix E.I Comparison with the BiG-MRTA solutions also indicate remaining scope of improvement for learning methods, in terms of distance travelled.
1000-tasks-100-rbbba
and 20000ttsks-200-rbbot for
the learnt model by CAM achieved perfect completion rate
The comparison with Feas-RND shows how the learning method is markedly better than random feasible myopic decisions, therehy indicating that meaningful MRTA policies have been learnt here, as opposed to producing random feasible solution by virtue of the masked policy network design. In the Feas-RND method, a robot takes a task-selection decision randomly from a feasible set of choices that abide by all the constraints in the problems, e.g., related to inter-robot conflicts, task deadline and robot range. As shown in Table 7 CAM achieves more than 92% task completion rate for all the scenarios, which is found to be 5%%30% gain in task completion rate over that achieved by
7

---

Under review as a conference paper at ICLR 2022
Feas- across these scenarios. The performance of CAM in terms of the task completion rate is comparable to that of BiG-MRTA (which is slightly better), with the highest difference being 6.9% for the
case. Note that CAM continues to be better than AM is all these cases as well. Later in Section 5.2 we also compare the performance of CAM, AM, and BiG-MRTA on a benchmark MRTA problem where the objective is just maximize the task completion rate (hence the cost function is not affected by distance travelled), where CAM proves to be highly competitive.
We performed two ablation studies (Appendix E.2 on CAM understand the importance of the novel encoder and the decoder (adopted from attention mechanism). In the first ablation study, the CCN based encoding is replaced with simple feedforward layers (as explained in Appendix E.2). with the decoder remaining the same. It should be noted that the node embedding length (dembed). ). is the same for all the cases. In the second ablation study, the MHA based decoding was replaced with simple feedforward layers and softmax layer (as explained in Appendix (.22). with the encoder remaining the same. As shown by Table in both of the cases (i.e., with the encoder and decoder respectively ablated), we observe significant decrease in the performance across all scenarios, with the maximum dip in the completion rate being 19.8% and 13.4% for the first and the second study, respectively. Compiling the results from the first ablation study for the encoder and the comparison of CAM with AM, we posit that the CCN based encoding, which is able to aggregate local node neighborhoods while remaining agnostic to node ordering, clearly aids in providing better policies. Similarly, from the second case of the ablation study, we can conclude the MHA based decoding, which computes a compatibility of the current state information with the node information, aid in learning better policies.
Ablation study:
5.2
COMPARATIVE ANALYSIS ON BENCIIMARK MRTA PROBLEMS AND CVRP PROBLEMS
MRTA Task Allocation Problem with Time and Capacity (TAPTC): The CAM architecture is implemented and tested on a well-known class of (NP hard) MRTA problems known as Task Allocation Problem with Time and Capacity constraints or TAPTC, as described in Mitiche et al. (019)) In TAPTC, each task i has time deadline (f:) and workload (w;), and each robot has a work capacity (c,). The time to finish task by robot j is defined wi/cj. We compare the results of CAM on TAPTC with that of AM (Kool et al. 2019) and with those of the three non-learning baseline methods, namely 1) Iterated Local Search (ILS) (ansttenneeenn al., 2009). which uses meta heuristic approach, 2) Enhanced Iterated Local Search (EILS) (Vansteenwegen et al., 2009), which has controlled runtime and perturbations (compared to ILS), and 3) Bi-Graph MRTA (BiG- MRTA) (Ghassemi & Chowdhury (02T), which uses a bigraph construction and maximum weighted matching approach. Further details of the TAPTC benchmark, the baselines used here, and the changes made to CAM and AM for this case study are discussed in Appendix F For the results shown here, the CAM model is implemented such that computing the embedding of each node of the task graph. The testing is performed for different scenarios that are characterized by the number of robots and % of tasks having slack time deadline. Mitiche et al.] (2019) categorized the TAPTC problems into 2 groups based on the value of the high deadline for the tasks. Table 3 here presents the results for group 2, with the group results given in Table 10 in Appendix F4 In these tables, the scenario nomenclature is defined as: R75A5 denotes time deadline and a team of A = 5 robots. Results on the impact of neighborhood size (k) on CAM performance is also discussed in Appendix F.4 Table 3 shows that for all scenarios with A = {5, 7). CAM performs better than both AM and the non-learning baselines in terms of task completion rate; and CAM achieves top performance for 50% of the scenarios with A = {2, 3).
nearest neighbors are considered when
R- = 75% tasks have a normally-distribute
Table 3: MRTA- TAPTC Group 2: Performance of CAM, AM and baselines in terms of average completion rate. Bold style indicate the best value for the scenario. Higher the better.
Complation Rate
R2552
R25A3
R2535
R25A7|
R50NZ
R58A3
R50A7
R75AT
R75A3
RR553
|R7A7
R100X
R10R3]
RIORAS
R108A7
118
45.00
63.35
95:67
100.00
42.35
100.00
40.33
58.33
83.67
100.00
50.35
16.38
96.38
45.67
58100
190.00
80.35
41.00
3933
86.35
100,00
50.7
BIG-IRI
MRTA
46.00
65.07
5067
45.35
63.0
87.31
56.67
41.00
37000
8000
95.00
14
3000
7500
91.77
AM
47.53
65.35
100.00
100.00
29.00
64.67
100.00
100.00
23.67
3967
100.00
100.00
20.35
36.35
76.67
100.00
C)ME-D)
33,00
160.00
45.67
74.33
109.00
10000
31.00
35000
10R00
100.00
29.35
45.35
90.67
100.00
Table 4: MRTA- TAPTC Group 2: Average computation time (in milliseconds) to generate the
entire solution for each scenario.
Aug. Computaiion
R35A2
R25A3
R25AS
R25A7
R30AZ
RSDA3
RSBAS
R50A7
I05A2
R75A3
RREAA
R75X7
RIOBAZ
R100A3
RI0OAS
RE00AA
KILS
676.55
1063 87
14.87
V00000
750667
1010.15
23:35
10066)
1714.97
2561.67
998.33
169.33
1791
1416.00
10015
ISCAMITAA
147.71
13507
392.70
710.2
105.5
211
400.00
023.3
109.76
159.35
479.2
75530
100,10
325.4
331.00
650.56
AM
95.45
14.15
94.31
05.35
03.67
94.14
04.35
04.90
100.35
93.07
23.46
98.39
114R3
10W
105.07
CAMBROS
114.0
9500
94.31
94.79
94.87
96.10
94.39
94.54
10537
95.90
14.31
94334
14.35
95.55
95.74
8

---

Under review as a conference paper at ICLR 2022
A comparison of the computation time to generate the entire MRTA solution, shown in Table 4 demonstrates the advantage of learning based methods over non-learming baselines as the problem size increases w.L.t. the number of robots and tasks. Capacitated VRP: To demonstrate the versatility of the proposed CAM architecture, we train and test the CAM and the AM architectures (for comparison) on benchmark variation of the Vehicle Routing Problem (VRP), known the Capacitated VRP (CVRP). The CVRP benchmark consists of N task locations, where a vehicle is required to visit the locations and deliver packages in manner that minimizes cost function. We also use the Lin- Kernighan heuristics (LKH3) solver (Helsgaun 2017) and the Simulated Annealing (SA) algorithm implementation provided by Google Operations Research (OR) tools as well-regarded non-learning based baselines for comparing the results obtained by CAM and AM. Further details regarding the CVRP problem, the baseline method, and settings changes for CAM and AM are presented in Appendix G.T Table 5able55ssun summarizes the results of all four approaches (i.e., AM, CAM, and Google OR) on unseen scenarios for varying task size (# of locations) ranging from 50 to 1,000, in terms of the cumulative computing time and the cost function (both as average values across scenarios of given size). LKH3 is a well known state-of-the-ar art method for solving CVRP problems and also has the best performance (considering only cost and not run time). As shown in Table 5 the performance of all methods except LKH3 are comparable for small sized problems (50, 100, and 200 locations or tasks). As expected. the main advantage of the proposed CAM approach is apparent for the problems with larger number of tasks (i.e., 500 and 1000 tasks). where the average cost function of the solutions obtained by the CAM significantly better (less than half of AM's s and one-third of Google OR's, s). In these larger-sized scenarios, the computing time performance of CAM is slightly better than that of AM, and together AM and CAM are two orders of magnitude faster than SA (Google OR) and LKH3 in generating the entire solution (sequence of tasks to be undertaken).
Table 5: CVRP: Comparison of average cost function (and average time taken generate the entire solution). Lower the better.
CONCLUSION
In this paper, we proposed a new GNN architecture, called CAM, for multi- robot task allocation
# OF TASKS
AvG. COST FUNCTION (AvG. COMPUTING TIME)
LKH3
GOOGLE OR
AM
CAM
50
10.53 (46s)
11.3 (2x)
12.3 (0.04s)
12.2 (0.04s)
100
15.58 (60s)
17.6 (58)
17.4 (0.09s)
17.9 (0.09s)
problem with a set of complexities, includ-
200
17.69 (86s)
21.3 (20s)
21.6 (0.18s)
21.8 (0s)7s)
500
24.87 (123s)
$4.5 (20s)
34.0 (0.53s)
29.1 (0.53s)
1000
28.67 (189s)
81.8 (200s)
64.1 (1.31s)
41.6 (1.49s)
ing tasks with time
deadline and robots with constrained range. This new architecture incorporates an encoder based on covariant node-based embedding and decoder based on attention mechanism. A simple RL algorithm has been implemented for learning the features of the encoder and decoder. In addition, to compare the performance of the proposed CAM method, an attention-based mechanism approach (aka AM) has been extended to be able to handle a multi-agent CO setting problem, along with a recent saae--ffthhe-ae method BiG-MRTA, and a mypoic baseline method FNa.-RND. To evaluate the performance of the proposed CAM architecture and the extended version of AM, they are trained with the same settings. All the methods were tested on 100 unseen case studies. Performance was analyzed in terms of the cost value and the completion rate. Our primary proposition, CAM, outperformed AM and Feas-RND on test scenarios by achieving better cost function value, and was also able to achieve high task completion rate (> 92%) for even larger sized problems without the need to retrain, which is comparable to the npar-optimal (but O(10 102) more expensively computed) solutions by BiG-MRTA, thereby demonstrating the favorable scalability of CAM. The computational cost analysis showed that the proposed CAM model takes a few milliseconds to compute a decision, thereby providing clear advantage over non-learning based approaches to MRTA in the context of online (time-sensitive) planning. Moreover, the advantage of using local neighborhood information for node encoding can be seen in the scalability analysis on the MRTA and CVRP, where CAM demonstrates superior performance when applied to graphs with larger number of tasks/nodes. The ablation studies in Appendix F.2 showed the importance of the CCN based encoding and the MHA based decoding used in CAM. A comparisons over different suite of benchmark MRTA problems showed that CAM was competitive w.r.t. standard non-learning baselines including BiG-MRTA, in terms of task completion rate, while providing substantially faster solutions compared to the latter. Lastly, a comparative analysis on different CAM models with varying neighborhood size (while encoding) was performed (appendix F6) to study the impact of the neighborhood size in the encoder. Based on Appendix F. (for MRTA-TAPTC, TAPTC), k is a trade off between accuracy and computation time.

---

with the Under review as a conference paper at ICLR 2022
Ethics statement: The work in this paper does not have any direct negative societal consequences.
The CAM architecture which includes the encoder, decoder and the context part, can be coded in any programming language by following the equations in section and figure 2 The dataset for training the UIRTA-Mult-DUe Flood response problem can be gener- ated using the information in Appendix D.3 The codes for the AM method can be obtained from routel The AM method can be modified for solving the MRTA-Mult--UAV Flood Response problem using the information from Appendix D.5 Both CAM and AM method can be trained using the settings in table The codes for the BRGA method and Feas-RND can be obtained from /ttEps://gitule com/ The training data for MRTA-TAPTC can be generated using the information in Appendix [:5] Both CAM and AM can modified using the information Ap- pendix F.2 Details on running BiG-MRTA for MRTA- TAPTC can be obtained from Ghassemi et al. (2019) and the corresponding code from https: /ttl//gittut thub.. com adams hat.smllabuuu-eeee
Reproducibility statement:
https: httpDp/.c...tttte....oooaaaatta.
The EILS can be coded using the inforation in Mitiche et al. (2019). The test dataset can be ob- The CAM architecture can be modified for CVRP using the information in Appendix G.1.1 and G.1.2 The codes for the AM method and implementation for LKH3 can be obtained from https: /ttps//giitub com/ wouterkoo route The google OR tools implementation can be done using the gwwglooooo..ooooooooooooooooooo.
tained from https: / / /tt/nniiuurrrormrrt wtw com/aattccctt
attent on- ample https:::////........ //deve /eve weeveloperrs google l. cwmccoooooooooooo http:///ttt/ttttto/o//ootnnnni/o
dataset generated using the information in Appendix G.4
10

---

Under review as a conference paper at ICLR 2022
REFERENCES
Claudia Archetti, Dominique Feillet, Michel Gendreau, and M. Grazia Speranza. Complexity of the VRP and SDVRP. Transportation Research Part C: Emerging Technologies, 2011. ISSN 0968090X. doi: 10. 10.10166j.trc.2009III 12.006.
Jean-Philippe Aurambout, Konstantinos Gkoumas, and Biagio Ciuffo. Last mile delivery by drones: An estimation of viable market potential and access citizens across european cities. European Transport Research Review, 11(1):30, 2019.
Nabila Azi, Michel Gendreau, and Jean- Yves Potvin. An exact algorithm for a vehicle routing problem with time windows and multiple of vehicles. European Journal of Operational Research, 202(3):756-763, 2010.
Thomas Barrett, William R Clements, Jakob N Foerster, and Alex Lvovsky. Exploratory combinatorial optimization with reinforcement learning. arXiv preprint arXiv: 1909.04063, 2019.
Amir Behjat, Hemanth Manjunatha, Apoorva Kumar, Jani, Leighton Collins, Payam Ghassemi, Joseph Distefano, David Doermann, Karthik Dantu, Ehsan Esfahani, and Souma Chowdhury. Learning robot swarm tactics over complex adversarial environments. In International Symposium on Multi-Robb and Multi-Agent Systems (MRS'21), Cambridge, UK, Nov, 2021. IEEE.
Tolga Bektas. The multiple traveling salesman problem: overview of formulations and solution procedures. Omega, 34(3):209- 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, 313,,333211 2016.
Quentin Cappart, Didier Chételat, Elias B. Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial Optimization and Reasoning with Graph Neural Networks. 2021. doi: 10.249663ijcai.22221553
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 Ramser. The truck dispatching problem. Management science, 6(1): 80 91, 1959.
M Bernardine Dias, Robert Zlot, Nidhi Kalra, and Anthony Stentz. Market- multirobot coordination: A survey and analysis. Proceedings of the IEÉE, 94(7):1257-1270, 2006.
Maria Valera Espina, Raphael Grech, Deon De Jager, Paolo Remagnino, Luca Iocchi, 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-954, 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.1 10/111//E 8-11//EE121111-1111...
Payam Ghassemi and Souma Chowdhury. Multi-robar task allocation in disaster response: Addressing dynamic tasks with deadlines and robots with range and payload constraints. Robotics and Autonomous Systems, pp. 103905, 2021.
11

---

Under review as a conference paper at ICLR 2022
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-Robor and Multi-Agent Systems (MRS), Pp. 83-85, New Brunswick, NJ, aug 2019. IEEE. ISBN 978-1-728111 1-21111-74-7
doi: 10.1 109/MR9 2019 200.20000990000 8901062. //ieeexplors www.eplooe... leee org/ /ttp://ttmmmmtmmt0////////
URL https
William I.. Hamilton, Rex Ying, and Jure Leskovec. Inductive represstioonn learnin on large graphs. CoRR,
2017. Utl.http://axxii..orr 0221 0221
Keld Helsgaun. An Extension of the Lin=Kernighan--ellgaa TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems: Technical report. Roskilde Universitet, December 2017.
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):241745, 2018.
Sarah Ismail and Liang Sun. Decentralized hungarian-based approach for fast and scalable task allocation. In 2017 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 23-28. IEEE, 2017.
Jiechuan Jiang, Chen Dun, Tiejun Huang, and Zongqing Lu. Graph convolutional reinforcement learning. In International Conference on Learning Representations, 2020. URL https:// openreview http:/oorummdd-Hxxxoo5555
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, 80:34 42, 2016.
Yoav Kaempfer and Lior Wolf. Learning the multiple traveling salesmen problem with permutation invariant pooling networks. ArXiv, abs/1 803.003.000000 003.09621, 2018.
Richard M Karp. An algorithm to solve the x assignment problem in expected time o (mn log n). Networks, 10(2):143-152 1980.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in Neural Information Processing Systems, pp. 034486358, 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 7th International Conference Learning Representations, ICLR 2019, 2019.
Qingbiao Li, Fernando Gama, Alejandro Ribeiro, and Amanda Prorok. Graph neural networks for decentralized multi-robot path planning. In IEEE International Conference on Intelligent Robots and Systems, 2020. ISBN 9781728162126. doi: 10. 10.0110//00 202.0944442000299116666
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- 2018.
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev, Reinforcement learning for combinatorial optimization: A survey, 2021. ISSN 03050548.
Hakim Mitiche, Dalila Boughaci, and Maria Gini. Iterated local search for time-extended multi-robot task allocation with apatio-temporae and capacity constraints. Journal of Intelligent Systems, 2019. ISSN 03341860. doi: 10. 10.15 1515/isss-220 2018-0267.
Akash Mittal, Anuj Dhawan, Sahil Manchanda, Sourav Medya, Sayan Ranu, and Ambuj Singh. Learn- ing heuristics over large graphs via deep reinforcement learning, arXiv preprint arXiv:1903.03330 2019.
12

---

Under review as a conference paper at ICLR 2022
R Nallusamy, K Duraiswamy, R Dhanalaksmi, and P Parthiban. Optimization of non- con-linear multiple traveling salesman problem using k-means clustering, shrink wrap algorithm and meta-heuristics. 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, 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 reconnais- sance and the magic 2010 competition. Journal of Field Robotics, 29(5):762-792, 2012.
Rohan Paleja, Andrew Silva, Letian Chen, and Matthew Gombolay, Interpretable and personalized apprenticeship scheduling: Learning interpretable scheduling policies from heterogeneous user demonstrations. Advances in Neural Information Processing Systems, 2020.
Eric Schneider, Elizabeth Sklar, Simon Parsons, and Tuna Özgelen. Auction-based task allocation for multi-robot teams in dynamic environments. In Conference Towards Autonomous Robotic Systems, pp. 246-257. Springer, 2015.
Malcolm Strens and Neil Windelinckx. Combining planning with reinforcement learning for multi- robot task allocation. In Daniel Kudenko, Dimitar Kazakov, and Eduardo Alonso (eds.), Adaptive Agents and Multi-Agent Systems II, pp. 260-274, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. ISBN 978-3-540-32274-00
Quinlan Sykora, Mengye Ren, and Raquel Urtasun. Multi-agent routing value iteration network, In 37th International Conference on Machine Learning, ICMI. 2020, 2020. ISBN 9781713821120.
Ekaterina V. Tolstaya, James Paulos, Vijay R. Kumar, and Alejandro Ribeiro. Multi-robot coverage and exploration using spatial graph neural networks. ArXiv, abs/201 1.01119, 2020.
Paolo Toth and Daniele Vigo. Vehicle routing: problems, methods, and applications. SIAM, 2014.
Pieter Vansteenwegen, Wouter Souffriau, Greet Vanden Berghe, and Dirk Van Oudheusden. Iter- ated local search for the team orienteering problem with time windows. Computers & Opera- fions Research, 36(12). (261::32211 -290,, 2009. ISSN 0305-0548. doi: https://bb.org/10.1116.... URL ht / www. www.scceeiccccc..cc.. rect. comt/.commcee wwt.c///cceeeeeeatttceee/eeae/ae New developments hub location.
2009.03. 0008.
00305054809000880
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://arxiv. org/ attp//bss//0../////////// 03762
Di Wang, Mengqi Hu, and Yang Gao. Multi-criteria mission planning for a solar- powered multi-robot system. In ASME 2018 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers Digital Collection, 2018.
Zheyuan Wang and Matthew Gombolay. Learning scheduling policies for multi-robot coordination with graph attention networks. IEEE Robotics and Automation Letters, 5(3):4509 2020. doi: 10.1 10w.09999...... 2.2......200002211
13

---

Under review as a conference paper at ICLR 2022
A LEARNING OVER GRAPHS
Neural network based methods for learning CO can be broadly classified into: (i) Reinforcement
Learning (RL) methods Kool et al. [ Barrett ct al. (2019); ; Khalil et al. (017); Strens &
Windelinckx (2005); and (ii) Supervised learning (often combined with RL) methods Kaempfer & Wolf (201 8); Mittal et al. (2019): ; Li et al. 2018); : Nowak et al. 2017). The supervised learning
approaches typically address problem scenarios where samples are abundant (e.g.. influence maxi-
mization in social networks Mittal et al. (2019)) or inexpensive to evaluate (e.g.. TSP Kaempfer &
Wolf (2018) 8) and are thus unlikely to readily applicable to solve complex problems over real- wollworld graphs. RL based techniques to learn on graphs include attention models with REINFORCE Kool (ct al. (2019) and deep Q-learning Khalil et al. (2017); Barrett et al. (2019), among others, with some extending solutions to multi-agent settings Jiang et al. (2020). In this work, we are interested in the first class of the methods (i.e., RL methods over graph space).
Dai et al. Dai et al. (017)) showed that a 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 can learn to solve unseen test problems that have been drawn from the same distribution as that of the training data set. More importantl, it has been shown that using a learned network policy instead of tree search, both methods are using the same embedding GCN, showed a speedup of 5.5 for a problem size of 20,000 for influence maximization. Similarly, the effectiveness of learning a 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 sequence-to-sequeee networks and attention mechanism) to encode and learn the combinatorial optimization problems in graph space Kaempfer & Wolf (201 8); Kool et al. (2019). Kool et al. Kool et al. (2019) implemented framework using an encoder/decoder based on attention mechanism and REINFORCE algorithm for solving wide variety of combinatorial optimization problems as graphs, with the main contribution being flexibility of the approach on multiple problems with the same hyperparameters. Wang et al. |Wang& & Gombolay (2020) showed how learning can lead generate faster solutions than standard exact methods for multi-robot scheduling problems. However, the size of the problem that has been studied in that work and other similar studies Paleja et al. (2020); Sykora et al. (2020) is limited to robots and 100 tasks, and only temporal constraints were considered. In this paper, we study larger problems (up to 1000 tasks/200 robots) as well as include complexities such as time deadlines for tasks, robot ferry range constraints, capacity constraints, multiple routes, etc. Graph learning has been implemented for a multi-robot coverage problem in Tolstaya et al. (2020), which demonstrates good scalability. However, this work is addressing a multi-robot exploration problem (and not MRTA), and it not clear how this proposed method can be applied to an MRTA problem with complexities such range constrain, capacity constraints, time extended tasks, multiple routes, etc. Apart from CO problems, graph learning can also be used to perform path planning as demonstrated in Li et al. (2020).
models (e.g.. pointer
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 an equivariant manner. The embedding layer is a variation of Covariant Compositional Networks (CCN), introduced by [y et al. (2018). CCN was originally implemented for predicting molecular properties by learning local structural information of the molecules. This node-based embedding has been chosen since i) operates on an undirected graph: ii) uses receptive field and aggregation functions based on tensor product and contraction operations (which are equivariant), which leads to a permutation- and rotation-ing -inarriann embedding; and iii) provides an extendable representation (n-th order tensor representation can be useful to extend the work to multi-level networks, 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. An attention mechanism has been successfully implemented for problems with sequential processes, e.g., Natural Language Processing (NLP) Vaswani et al. (2017). Here we are interested in the attention mechanisms since they involve simple matrix multiplications, which make them not only computationally inexpensive
14

---

Under review as a conference paper at ICLR 2022
(by utilizing modern GPUs), but also programmatically easy to be implemented. In this work, implement an srcentionbbasee decoder for CAM as proposed in Kool et al. (2019) Vaswani et al. (2017).
B EMBEDDING LOCAL STRUCTURAL INFORMATION
Local structural or neighborhood information of a graph node/ task refers to the association of the node to its neighboring nodes. These information includes how the properties of the neighborhood nodes differ from that of the node under consideration. It is this information that is being encoded in the node embedding along with the information of the node properties d, The encoder should be able to use this local structural information in order to scale to larger-sized problems pointed out by (Cappart et al. 202T). Here, we explain how local structural information is being encoded with the help of two graphs, one which is small and the other is larger graph but having some nodes with similar neighborhood as shown in figure 3 Node A in graph G1, and nodes B, and in graph G2 have almost similar neighborhood. Here the local neighborhood information encoding of nodes A, B, and (which are FA" F and F respectively) will be almost same, irrespective of the size the graph. Therefore by equation 6 ((Fa)) Faa) ~ (F Faa) = (F Fac)) (FX) ~ FNb association with it's neighboring are almost the same, which is being captured by equation 6
B = F Even though the actual locations of nodes A, B, and C are different, their
Tight deadline
F Fg May R
Neighborhood
Graph G1
Graph G2
Neighborhood
of
Y
Neighborhood
Slack deadline
X
Figure 3: Node A belongs to smaller sized graph G1, while B and C are nodes of larger-sized graph G2. Based on the relative positions of its neighbor nodes (represented by the dashed lines), and the deadline of neighbor nodes (color of the nodes), A, B, and C has similar neighborhood.
C LEARNING FRAMEWORK
Both the CCN-inspired encoder and the attention-based decoder consist of learnable weight matrices as explained in Sections 3.1 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 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 O m m2h)), where n, m, and l represent the number of tasks, the number of robots, and the maximum number of tours per robot, respectively Therefore, Learning Method: In this work we implement a simple policy gradient method (REINFORCE) as the learning algorithm with greedy rollout baseline, which also enables us to compare the effectiveness 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 (0 (0BL, The size of the training data and the validation data used for this paper is mentioned in section D.3 Each sample 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 architecture is shown in Alg. D in Appendix E. It should be noted that the policy gradient method requires the evaluation of cost function, which is defined to be same in Eq. equation]] [] Policy: We define the policy such that the robot r does not satisfy the constraints in Eqs. equation 3 it returns depot (i.e., 0). Otherwise the robot the learnt CAM network
reinforcement learning algorithm to conduct the learning.
CAM).
15

---

Under review as a conference paper at ICLR 2022
and chooses the output (task) based greedy approach (selects task with the highest probability value), as shown in Fig.
Algorithm 1 Training Algorithm
Input: Ng: Number of epochs, Ns: Number of batch, Batch size, Nu: Training data size, Nut Validation data size.
1: RCAMRL- CAM-RI
PAMM-LL Baseline CAM-RI
887
3: for epoch = 1.. I..NNpach do
4: Dr. Da x- GeneraleeSeenariosSNNn.
5: .o [Na//B]
step = I..NN,
7:
Dub + SamplcRandom Du. M) {Dus: Batch Training Datasct]
8:
Jan CalculateCos((OCAM.. Dub)
a, Sona &- CalculateCost(CcAmauu Dus)
10:
VL D i= (Serus Sena..) log softmax(ax)
OCAMRI. ADAM( OCAM.RI)
12:
end for
13:
BL PBL Jocsivl + CalculateCost( a. feam -CalculatcCos(@ DT)
Da)
14:
15:
if (INg ABL > E Socas) A (T-Test(au, att > then
DAM--I.. OCAM-RI
17: end
18:
end for
19:
CalcuateCost Procedure:
20: for = L..ID do
au, Sunas f- Simulation(O, D;)
22: a f- a
23: feust f- fast U font
24: end for
25: return a, foos
C.1 SIMULATION AND FRAMEWORK SETTINGS
The "Python" 3.7 and the 64-bit distribution of "Anaconda 2020.02" are used to implement the MRTA approaches. The environment, training algorithm, and the evaluation of the trained model, are all implemented in Pytorch-1.5 for CAM and AM. The training, based on Pytorch, is deployed two GPUs (NVIDIA Tesla V100) with 16GB RAM.
D MORE DETAILS ON MRTA
D.1 CONVENTIONAL METHODS FOR MRTA
The MRTA problem can be formulated Integer Non-Linear Programming (INLP) problem depending on the application. When tasks are defined in terms of location, the MRTA problem becomes analogical to the Multi-Traveling Salesmen Problem (mTSP) (Khamis et al. 2015) and its generalized version, the Vehicle Route Planning (VRP) problem [Dantzig & Ramser 1959 Existing solutions to mTTP and VRP problems in the literature (Bektas) |0066 Brackers er al.) 2016) have addressed analogical problem characteristics of interest MRTA, albeit disparate manner; these characteristies include tasks with time deadlines, and multiple tours per vehicle, with applications in the operations research and logistics communities (Azi al. 2010 Wang et al. 2018). II.P-based mTSP-ttpe formulations and solution methods have also been extended to task allocation problems in the multi-robotic domain (Jose & Pratihar 2016). Although the ILP-based approaches can in theory provide optimal solutions, due to the NP-hard time complexity of the SR-ST problems (Mazyavkina et al. 2021 Archetti et al.) 2011), they are characterized by exploding computational effort as the number of robots and tasks increases (ooth & Vigo 2014 Cattaruzza al.] 2016). For example, for the studied SR-ST problem, the cost of solving the exact integer programming formulation of the problem scales with O 00'2mm m²h?). where m,, and / represent the number of tasks, the number of robots, and the maximum number
Integer Linear Programming (ILP), mixed ILP
16

---

Under review as a conference paper at ICLR 2022
of tours per robot, respectively |Ghassemi et al. 2019). As result, most practical online MRTA methods, c.g., duction-basee methods (Dias et al. 2006) and bi bi-graph matching methods (Ghassemi & Chowdhury) 2018 Ismail & Sun 2017), use some sort of heuristics, and often report the optimality gap at least for smaller test cases compared to the exact ILP or INLP solutions (where tractable).
D.2 MORE DETAILS ON ENCODING THE CONTEXT
As discussed section 3.2 the context portion of while robot makes a decision, consists of 1) Current time t; 2) Available range of the robot taking decision pr: 3) Current location of robot taking decision (2r, yr-); 4) Current destination of other robots (Tpr Up, V p E P,): 5) Available range for other robots (Pp. V/ p E P,), where P. represents the peers of robot Here, features 2 and 3 represent
the current state the robot taking the decision, while features 4 and 4 represents the states of the peer robots. The context feature vector be computed as shown in Eq 10
Linear(Concattt, Qr. Qp.))
(10)
where,
Q = Linear((zr yr, Prl
(11)
and
Qp. Epep, LitearLinerr(ppp. Ny. Ppl)
(12)
The dimensions of Qr, and Qp, is dembeds and the length of the final feature vector Q is also considered dembed. The summation aggregation operation in Eq 12. makes the context vector agnostic to the number of robots.
D.3 DESIGN OF EXPERIMENTS & LEARNING PROCEDURES
To evaluate the proposed CAM method, we define an MRTA case study with varying number of UAVs and 200 task (flood victims) 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 1 hour. The UAVs are assumed to have a range of 4 km, and nominal speed of 10 km/h. We assume instantancous battery swap is provided at depot location, which is used when UAV' return to depot since they were running low on battery. It is important to note that the flood victim application is used here merely for motivation, and the CAM architecture is in no way restricted to this application, but can rather solve problems in the broad (important) class of capacity/range-costraiin Moreover, even the policies learnt here for CAM demonstration on the described case settings can generalize to related SR-ST problems with up 1,000 tasks, which represents a fairly large MRTA problem in reference to the existing literature in the MR domain.
and timed task-constrained SR-ST problems.
To perform learning and testing of the learned model, we proceed follows: Learning Phase: We use a 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 100 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, the models are tested for different cases of varying number of tasks and varying number of robots with each case having 100 random test scenarios from training data distribution. Here, for each task in sample scenario, the location of the tasks, time deadline, location of the depot are all generated from random uniform distribution. More details the learning framework is given in Appendix C The training and testing settings and the modifications to AM for MRTA are given in Appendix D
D.4 BASELINES
BIG-MRTA: The BiG-MRTA algorithm Ghassemi & Chowdhury (202I): Ghassemi et al. (2019) is an online method based on the construction and maximum weighted matching of bipartite graph. BiG-MRTA (Ghassemi & Chowdhury 2021) uses a novel combination of a bipartite graph construction, an incentive model to assign edge weights in the bigraph, and maximum weighted matching (based on the Karp algorithm (Karp) 1980)) over the bigraph to allocate tasks to robots. This method has been developed online solver for SR-ST type MRTA problems, where tasks have
17

---

Under review as a conference paper at ICLR 2022
deadlines, new tasks could appear during the mission, and robots are subject to range and payload constraints.
AM: The number of attention heads for the encoder is 8, with 3 layers of encoding. The node embedding length is 128.
Feas- Beas-NND:BA In the Feas- RND approach, each robot randomly chooses available tasks that are feasible to be undertaken by the UAV, satisfying all the constraints in section 2.2 The algorithm used for Feas-RND can be found in (Ghassemi & Chowdhury 2021
D.5 MORE DETAILS ON TRAINING FOR MRTA
In order to compare the convergence of the proposed CAM method with that of the AM approach, we run both methods with similar settings and plot their learning curve (convergence history), as shown in Fig. iin appendix D As seen from this figure, the AM method took 3 epochs to reach its best cost value and stagnated. On the other hand, the CAM method took 20 epochs to reach the best cost value of AM and continued to improve up to 24 epochs, leading to significantly better cost function value (AM = -0.266) compared to AM (J = -0.009). The stagnation of AM could be attributed to direct implementation of the transformer network (Vaswani al. 2017), which was designed for machine translation and thus consists of multiple layers of Multi-head attention. In contrast, our CAM model uses simple linear transformations of the node properties and its relative differences in local neighborhoods to capture structural information.
Learning Curve:
0.3
CAM
AM
0.2
Cost Funetion
0.1
0.0
-0.1
-0.2
20 40 60 80
100
Figure 4: MRTA: Learning curve of CAM and AM for 200 tasks.
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-agentrrobor combinatorial optimization problems. To be able to implement the AM method for our problem (for comparison with our CAM method), the AM method is adapted to a multi- setting. For this purpose, we make the following three changes to the AM method: (i) The node properties that are defined in Section 2.1 are used in AM; (ii) The context for the attention mechanism is modified to be the same as that used for CAM; and (iii) The cost function used for training is changed to that in Eq. equation []
We want to compare the structural representational quality of CAM and AM for generalizability and scalabilty. Hence, for fair comparison, both CAM and AM models were trained with the same settings (Table 6 and (4p.
D.5.1 COMPUTING TIME (TRAINING AND EXECUTION)
Based on the epoch information in Section D.3 the average time to complete training epoch was found to be 19.50 minutes (i.e., ~ 1.7 seconds per sample) for CAM and AM. The average computing time (from Tables [ and taken by the learnt policies for producing the entire MRTA solution (sequence of tasks assigned to each robot) was found to grow from 0.14 s to 20 s. as the number of tasks grew from 50 1000, and thus remaining unprecedentedlly attractive for real-time decision-making even for large problems.
E
MRTA - MULTI-UAV FLOOD RESPONSE: FURTHER RESULTS
E.
TASK COMPLETION RATE AND COMPUTATION TIME
Table 7 shows the completion rate which corresponds to the test cases for generalizability (Table and the test for scalability (Table 2). respectively.
18

---

Under review as a conference paper at ICLR 2022
Table 6: MRTA: Training algorithm settings for CAM and AM for MRTA--APTE
DETAILS
AM
CAM
Algorithm
REINFORCE Rollout
REINFORCE
Baseline
Rollout
Epochs
100
100
# of tasks
200
200
Training samples
10000
10000
Baseline samples
1000
1000
Optimizer
Adam
Adam
Learning step size
0.0001
0.0001
Training frequency
100 SAMPLES
100 SAMPLES
Table 7: MRTA Multi-UAV flood response: Comparison of CAM and AM on completion rate. Higher the better.
of Tasks
# of Robots
Avg. Completion Rate
BiG-MRTA
Feas-RND
AM
CAM
5
96.82
63.85
89.8
92.8
50
99. 89.88
93.54
98.0
99.2
10
99.15
64.45
91.8
92.5
100
20
99.98
94.04
98.0
99.8
20
99.91
65.06
93.85
95.05
200
40
100.00
94.59
98.65
T00.0
50
99.93
65.18
92.64
93.00
500
T00
100.00
94.16
98.42
99.92
99.95
65.33
93.26
93.77
1000
200
100.00
94.22
98.45
99.95
1500
CAM BIG-MRTAA
Compuntion1 woeetonmmeelnnn tecomes
1200
Trme
500
1:684
T-1025 1o0
1000 RuD
Figure 5: MRTA-Multia flood response: Comparison of the average computation time in seconds for CAM and BiG-MRTA, for the different scenarios. The x-axis denotes the different scenarios. For example, T-50-R-5 corresponds to the scenarios with 50 tasks and 5 robots.
Figure 5 shows the comparison of the average computation time between CAM and BiG-MRTA. can be seen that, the computation time of BiG-MRTA increases exponentially as compared to that for BiG-MRTA is slightly greater than that of CAM as can be seen from table 7 this advantage comes with very high computational cost. This shows the scalability of CAM to larger-sized problems. On comparing the cost function in tables [ and 2. it can be seen that, compared to BiG-MRTA, the performance of CAM drops for scenarios with higher tasks/robot ratios (such as
of CAM. Even though the completion
100-tasks-50-robots) However, this dip in performance is marginal when comparing the task completion rate (in tables with the maximum dip in performance for CAM being 7.3% (between 100-tasks- 10-robots and 100-tasks-20-robaee ro-roots).... One of the reason for this behaviour, is due to the cost function (Eq where the distance minimization only taken into account when the task completion rate 100%. Hence, we also compared the performance of CAM, AM, and BiG-MRTA benchmark MRTA problem in section 5.2 where
19

---

Under review as a conference paper at ICLR 2022
the objective is just to maximize the task completion rate, in which CAM demonstrates superior performance compared to the other methods.
E.2 ABLATION STUDIES
Table 8: MRTA Multi-UAV flood response: Ablation studies. The performance is compared
with respect to the average cost function of 100 testing scenarios (with % task completion rate). CAM E CAM model with CCN-based encoding ablated; CAM CAM model with AM based decoding ablated
# of # tasks
# of robots
Avg. Cost Function (Avg.
Completion Rate)
CAM
CAMErF
CAM Drr
-0.03 (92.8)
0.26 (73.0)
0.20 (79.8)
50
10
-0.47 (99.2)
-0.07 (95.6)
0.07 (92.4)
10
0.01 (92.5)
0.26 (73.6)
0.19 (80.8)
100
20
-0.50 (99.8)
-0.01 (96.0)
0.05 (93.3)
20
0.04 (95.0)
0.24
(81.6)
200
40
-0.45 (100.0)
0.04 (95.5)
0.06 (93.9)
50
0.07 (93.0)
0.23 (76.3)
0.19 (80.4)
500
100
-0.37 (99.9)
0.04 (95.1)
0.07 (92.9)
100
0.06 (93.7)
(77.9)
0.18 (8T.0)
1000
200)
-0.31 (99.9)
0.02 (95.0)
0.05 (94.0)
For Encoder: In order to study the true impact of the graph node encoding, we compared the performance of CAM with it's covariant based encoding removed to get new model CAMg In this case the, node encoding is performed using a simple feedforward network, following Eq 14 The decoder for CAMErr is the same as that of CAM.
Fa. Wddd + ba F:= WF Fa, bF
(13)
(14)
where, di [Ii Mo. TiJ, Vi E V. Wd, WF, ba, and bF are learnable weights and biases, where Wd e R3 by Rddama x1 and W e Redented aedintedddumnn Xdinttd
bp E IRdmmax
For Decoder: In order to study the impact of the MHA based decoder, we compare the performance of CAM, with it's decoder being replaced by a simple feedforward network to get a new model CAMD which takes in the node embeddings and the context information, and computes the output probabilities using the following equations. The encoder for CAMD is the same as that of C'M..
Act softmaz((PA1) ...., P
(15)
P.Act LeaakyReLU dec ConCacat (F,, 2) + baee), wherei V
(16)
Here Widee and bdee are learnable weights and biases, where Wdee E IR. N and haee E Nxx1 F, V V are the node embeddings from the encoder, and E [gderteed is the context vector. The value of dembed for both the models is the same as that of CAM in section 5 Both the models were trained on the MRTA-Multi-AA. flood response problem in section 4 using the parameters in table 6 and tested on the same test scenarios as that used for CAM,, AM, and BiG-M RT A, for varying number of locations and varying number of robots (shown in table The third and the fourth column in table 8 shows the average cost function of 100 test scenarios, and it's corresponding % completion rate, for CAMEgF and CAMDDr ablation study, respectively.
As can be seen from table 8 the performance of both CAMErr and CAMDrr is significantly poor compared to C'AM, in terms of both cost function and task completion rate, The performance drop is more for scenarios with lower number of robots, with the maximum drop in task completion rate being for C'AM being 19.8% (for 50-tasks-5-robonn 5-roooss,, and for CAMper being 13.4% (for It can also be observed that, the performance drop is greater for C'MM than CAMpprs this indicates that the CCN-based encoder has slightly more influence on the performance, than the decoder.
20

---

Under review as a conference paper at ICLR 2022
F MRTA TASK ALLOCATION PROBLEM w/ TIME & CAPACITY (TAPTC)
F.1 PROBLEM DESCRIPTION AND FORMULATION
In order to assess the effectiveness of the CAM architecture for MRTA problems with time-extended assignments, we test and validate our CAM on Task Allocation Problem with Time and Capacity (TAPTC) benchmark problem Mitiche et al. (2019). which falls into the ST-SR- TA-TW (Single Task robot, Single Robot task, Time-extended Assignment, Time Windows). The TAPTC involves task locations within a 100 x 100 grid map, with each task having a time deadline 44 and also a workload wi. Each robot j has a work capacity of cj. All the robots move with maximum speed of 1 unit per second. A task is considered to be completed only if a robot j visits node and spends a time of w//c wt/cc. Each scenario is generated based on uniform distribution reported in MMttihhe et al. (2119) and the training samples for our models are generated from the same distribution.
For evaluating the performance of the learned model and conducting comparative analysis, the TAPTC dataset (accessible from http: /ttpur/////uu....../ com/ taptc15in This dataset consists of test cases with 100 tasks and varying number of robots (A 2, 3, 5, robots), and the speed of every robot is considered to be the same (1 unit per second). The test cases can be divided equally into two groups, based on tight deadlines (Group 1) and slack deadlines (Group 2). Each group can be further divided into 4 sub-categories based on the fraction of tasks (R = 25%, 50%, 75%, and 100%) that have normally distributed task deadlines. For example, 25% indicates that there are 25 tasks with deadlines normally distributed between the limits cz and faigh. while the remaining 75 tasks have a deadline of Unigh. For group (tight deadline), the value of hhigh is considered as half as that for group 2 (tight deadline). In both the groups, for all values of A and R. there will be 3 samples. Therefore the total number test cases is given by number of groups |A| x [ x 3) = 96, where each group has 48 test cases. Further description of the test cases can be found in Mitiche et al. (2019).
The exact solution of the MRTA-TAPTE problem can be obtained by formulating it as the following integer non-linear programming (INLP) problem:
N
if of > T. otherwise
min feost
ris
(17)
0,
1=1
subject
81 E S (
(18)
$ 8 vi
(19)
Here, N is the number of tasks/nodes, T/ is the time at which task i was completed, is the time deadline of task i, and 5 = [$1, 82, ...8]] is the sequence of all the nodes that were visited. The minimum cost function that can be achieved using Eq. is O, which corresponds to the case where all the tasks are successfully completed. A detailed formulation the exact ILP constraints that describe the MRTA-TAPTC problem can be found in Mitiche et al. (2019). Note that, in our paper we use a slightly different reward function as compared to the objective function in Mitiche et al. (2019). but the intention of both the functions are essentially the same, which is to maximize the number of successfully completed tasks.
Here, we craft the objective function (Eq. equation 17) such that only missed tasks (T! TT)
contribute to the cost function. It is important to note that the objective function can be tailored according to the priority of the problem. Since the main priority in Mitiche et al. (2019) is to maximize
the number of successfully completed tasks, the objective function (Eq. [1) also prioritizes task
completion for fair comparison with the baseline methods. The constraints in Eq. 18 and 19 are such that each tasks must be visited exactly once by any robot.
F.2 MODIFICATIONS TO CAM AND AM
1. Change in encoder: The encoder for MRTA-TAPTE problems consider additional node properties, namely the location of the tasks (I; y:), the time deadline (r,), and the workload w;, i.c., d; =
(Zr, Ves Táy wa].
21

---

Under review as a conference paper at ICLR 2022
The context for the MHA layer in the decoder consists of the following five features: 1) elapsed mission time; 2) Work capacity the robot taking decision; 3) Current location of robot taking decision; 4) Current destination of peers; and 5) Work capacity of peer.
2. Change in context:
Cost function: We use Eq. 17 as cost function.
The decoder need change in this case.
F.3 BASELINE METHODS
We consider three non-learning methods, which are i) Iterated Local Search (ILS), ii) Enhanced Iterated Local Search (EILS), iii) Bi-Graph MRTA (BiG-MRTA), which briefly described below. The learning based baseline method we implemented here is AM with minor modifications as also discussed below.
i) Iterated Local Search (ILS): This is an online meta heuristic iterated search algorithm Vansteen wegen al. (2009), where the output of one iteration is partially used as the input to the next iteration. During each iteration, the best solution is improved by perturbation step. followed by a local search.
iî) Enhanced Iterated Local Search (EILS): EILS also an online meta heuristic iterated search method Mitiche et al. (2019), with an improved perturbation step as compared to Vansteenwegen
al. 2009).
iii) Bi-Graph MRTA (BiG-MRTA): The BiG-MRTA algorithm Ghassemi & Chowdhury [202 Ghassemi al. (219) an online method based on the construction and maximum weighted matching of a bipartite graph. BiG-MRTA (Ghassemi & Chowdhury 202T) uses novel combination of a bipartite graph construction, an incentive model to assign edge weights in the bigraph, and maximum weighted matching (based on the Karp alogirthm (Karp) 1980)) over the bigraph to allocate tasks to robots. This method has been developed as an online solver for SR-ST type MRTA problems, where tasks have deadlines, tasks could appear during the mission, and robots subject to range and payload constraints.
The AM implementation is almost the same for the MRTA- TAPPTC problem as that im- plemented for the multi-UAV flood response problem in section D.3 In addition, the changes implemented in CAM, as explained in Section F.2, are also applied here. The number of attention heads for the encoder is 8, with 3 layers of encoding. The node embedding length 128.
iii) AM:
Both CAM and AM trained using REINFORCE described in algorithm Tusing the settings given in Table 9
Table 9: MRTA TAPTC: Settings for model training for CAM models and AM
DETAILS
VALUES
Algorithm Baseline
REINFORCE Rollour
Epochs # of tasks
100
100
Training samples
500,000
Baseline samples
10,000
Optimizer
Adam
Learning step size
0.0001
Training frequency
500 SAMPLES
F.4 RESULT AND DISCUSSIONS
Tables 3 and 10 summarize the performance of CAM alongside the baseline methods, in terms of the average completion rate, i.e, the ratio of the number of successfully completed tasks to the total number of tasks averaged over 3 samples for the scenarios (denoted by A and R). The CAM model here uses & 9, where A represents the number of nearest neighbors considered for node for computing its node embedding. For group 1, the CAM model was able to generate the best results for 8 out of the 16 different scenarios (Table 10). From Table I0 it can be inferred that CAM has a superior performance compared to the baselines for cases with larger number of robots (best performance for all cases with A 7, and for 3 out of 4 scenarios with A 5), including maximum
22

---

Under review as a conference paper at ICLR 2022
margin of 19% for R75A7 compared the next best solution (EILS). While for cases with smaller number of robots (A = )). CAM achieved the best performance for one scenario (R25A3), with the worst performance having margin of only 7% (scenario R R75A3) compared to best performer (EILS) in that case.
For group 2, CAM achieves top performance for all scenarios with A (5, 7), while achieving top performance for 50% of the scenarios with = 2, 3, as discussed in Section 5.2 of the main text.
Tables IT and gives the average computation time (in milliseconds) generate the entire solution for all the methods. As can be seen from these tables, for the non-learning methods EILS and BiG-MRTA, the general trend is an increase in the computation time with increasing number of robots, while for both the learning- based methods (CAM and AM) the computation time increases marginally with increasing number of robots.
200
CAMIK-
CAMIK-B;
CAMIK-B)
180
CAMIK-12
AM
Cost Funciion
160
100
20
Epoch
60
100
Figure 6: MRTA-TAPTC: Learning curve of all CAM models and AM model.
F.5 MORE DETAILS ON TRAINING DATASET FOR MRTA-TAPTC
Each training sample has 100 tasks, and are located randomly within a 100 100 grid map. Each task has a time deadline 50 I Ti < 600, and workload 10 S S 30. Each sample has number of robots where < n, S The initial positions of the robots randomly within the grids. Each robot, j has work capacity of c, where 1 S cj < 3. All the robots move at speed spends time of ws/c.. All the training samples generated such that all the associated variables (mentioned above) follow a uniform distribution within their respective bounds.
sample is also chosen
unit. A task is considered to be completed only if robot j visits node and
Table 10: MRTA TAPTC Group 1: Performance of CAM, AM and baselines in terms of average completion rate. Bold font values indicate the best performer for the corresponding scenario. Higher the better.
Avg. Complttinn Rat
R2552
ROSA3
RMAS
R25A7
R80A2
RSSA3
R50AS
RS0A7
RYSAY
R3SA3
RT563
R75A7
R100A2
RTORAT
RIORAS
R10RA7
I.S
23,00
$2.35
52.35
75.07
31.67
90.07
52.31
73.67
21.00)
30.77
50.33
72.31
19.35
16.35
42.35
66.35
23,00
21.33
32.33
BRC-AIRTA
23.33
77.33
21.00
31.67
AM
20.67
13.33
2033
23.67
38.00
63,00
1700
23.00
63.3
16.33
25333
47.67
92.00
71.77
Table 11: MRTA TAPTC Group 1: Average computation time (in milliseconds) to generate the entire solution for each scenario.
Aug. Cumpataina Time
R25A2
RISA3
R2SAS
RZSA7
RS8A2
RSBA3
RS0AS
RS0A7
R75A2
RISAS
R78AS
R7SA7
KI00AZ
RI0AA
RI0BAS
R180A7
RILS
1900
102.0
103
22
15
217000
152220
201407
30,00
245.0
972.33
S19EED
137.00
42.33
305307
335500
BR-MRRTA
33.34
115.0
20.37
377.00
31.31
85.73
255.00
437.0
38.8
98.35
32..8
33007
75.64
1900
406
563.00
10381
95.65
11..0
13350
10705
100
12988
F.6 IMPACT OF NEIGHBORHOOD SIZE FOR CAM ENCODER
Tables and 13 compare the performance of CAM models with varying neighborhood size (k) in
the encoder, based the average completion rate (average of the 3 samples) for all the scenarios (all
23

---

Under review as a conference paper at ICLR 2022
values of A and R. for the two groups). The impact of the neighborhood size & (during encoding) is more evident on the performance of Group test cases which has tasks with more number of tight deadlines. As shown in Table 12 the completion rate of CAM (with k {6. 9, 12)) are almost comparable, while the performance of CAM with = 3 is significantly lower than the other models. Lower the neighborhood size, smaller will be the local structural information learned, which could result in performance loss, However, increasing neighborhood size beyond a point may not necessarily improve performance. The average epoch time for training for the models with k = (3, 6, 9, 12] are 11, 13. 14.3, and 15 minutes respectively. Figure 6 shows the learning curve for training all the CAM models and AM model.
Table 12: MRTA TAPTC Group I: Comparison of performance (average completion rate) of CAM models with varying neighborhood size (k). Higher the better.
Aay. Complation Rey-
K352
RISAT
K35K5
RISA7
KARAT
K9K35
RERLAY
KI5A3
RTSAT
K75A5
R7SA7
KIRIX
KIGA3
KINKSS
KINKS
CAMKK
2037
12.00
33,07
19.33
14:00
20100
31.07
76.00
13.3
20.35
42.07
10.33
13.33
20.35
35.07
5000
CAM.K.6
23:00
37.31
6:
91,00
17.83
37.7
61:00
92.00
13.87
25.33
14.07
24.83
41.67
71:33
23.67
38,00
27.00
1633
47.67
28.0
37.7
16.87
43.67
Table 13: MRTA TAPTC Group Comparison of performance (average completion rate) of CAM models with varying neighborhood size (k). Higher the better.
Compltttin Raie
R25A5
R25A7
K3632
R7EA5
R75A7
CAMK
7687
58.33
CAM
7867
31.00
7807
32,00
G FURTHER DETAILS ON CAPACITATED VEHICLE ROUTING PROBLEM
G.1 FORMULATION OF CAPACITATED VEHICLE ROUTING PROBLEM (CVRP)
The vehiele routing problem here we considered a capacitated vehicle routing problem (CVRP), where a vehicle is required to deliver packages to number of locations N. Each task is designated an index from to N. We also consider depot with id as O. Each location has demand e on the number of packages where E [1, NJ. and the vehicles has constraint for the maximum number of packages it can carry, such that C < D. We assume that each package of the same size. The vehicle is required to create multiple routes visiting different locations to deliver the packages. The vehicle starts from a depot, has a maximum capacity for the number of packages, and can have multiple routes to deliver all the packages satisfying the demands in every location. Here assume that the vehicle can return to the depot for refilling to maximum capacity before starting a new route. In this experiment we do not consider split delivery where the demand of location is fulfilled partially during a route, and then completed in another route. The ILP formulation for CVRP can be represented as:
min feust E j E [1.
(20)
subject to C--1 max (0, C. cc) i
(21)
D, i i=0
where R is the number of routes, ō, is total distance travelled in route j. C2 is the available capacity at a time t, V is the set of locations visited. The node encoding and the context encoding are modified for CVRP (as explained in appendix G.I.T and G.1.2 for both CAM and AM. Both CAM and AM are trained for the scenarios with 100 locations and tested on the unseen scenarios with varying number of locations ranging from 50 to 1,000. The experimental details of this comparative study are given in Appendix G.2
G.1.1 ENCODING FOR CVRP
Except for the node properties, all the other steps for computing the node embeddings is same for CVRP compared to MRTA for CAM and AM. The node properties associated with the CVRP
24

---

Under review as a conference paper at ICLR 2022
includes the coordinate, y coordinate, and the demand for each location. Therefore each node can be represented as d, = [I, Vs, Ci), where 244, Yr, and G are the & coordinate, coordinate, and capacity respectively for node i. For the encoding,de d, for CVRP will be used in equation 22 for CAM.
F. W. df ba
(22)
G. CONTEXT ENCODING
The context serves the same purpose for which is represent the current state. For CVRP the current location and the remaining capacity as the context, for CAM and AM.
G.2 TRAINING DETAILS FOR CVRP
The training procedure for CVRP follows algorithm T in appendix D with the only change being in the calculation of the cost. Equation[20jp 20 used in the algorithm [ to compute the cost. Table [4 shows the different parametric setting for training CAM and AM for CVRP. CAM and AM models were trained for 100 tasks and tested on CVRP with 5 different task sizes (50, 100, 200, 500, 1000). Figure shows the learning curve for training CAM and AM.
Table 14: CVRP: Training algorithm settings for CAM and AM for CVRP
DETAILS
AM
CAM
Algorithm
REINFORCE
REINFORCE Rollout
Baseline
Rollout
Epochs
100
100
tasks
100
100
Training samples
20000
20000
Baseline samples
1000
1000
Optimizer
Adam
Adam
Learning step size
0,0001
0,0001
Training frequency
100 SAMPLES
100 SAMPLES
G.3 BASELINE DETAILS FOR CVRP
Lin-Kernighan heuristics (LKH3): We performed single with maximum number of trails as 10000.
AM: Same that of MRTA--Muti-UAV flood response and MRTA-TAPTC.
Google OR tools:
The first solution strategy algorithm used was PATH CHEAPEST ARC and the local search algorithm was Simulated Amnealing-
G.4 MORE DETAILS ON CVRP DATASET
Table 15: The capacity of the vehicle for different test scenarios
# of Tasks
Capacity (C)
40
100
50
200
100
500
250
1000
500
The dataset used for training CVRP consists of scenarios with 100 locations and one depot. The and coordinates of the locations (including the depot) randomly generated from uniform distribution within the limits [0. 1]. The demand for all task locations will be random integer from uniform distribution between [1.9], with depot assigned 0 demand. The vehicle capacity (C)
25

---

Under review as a conference paper at ICLR 2022
for scenario with 100 locations, is considered as 50. The dataset used for testing (to analyze both generalizability and scalibility) has the same limits as explained above. The assumed capacity of the vehicle for test scenarios of different number of locations shown in Table
90
CAM
Con Plactio
60
50
20
100
150
200
250
300
Epoch
Figure 7: CVRP: Learning curve of CAM and AM (trained on problem size with 100 locations).
H LIMITATIONS OF CAM
This work is implemented for fixed number of nodes but can be easily extended for cases where nodes are determined dynamically. The impact of the learning algorithm parameters such as the learning rate, training frequency training batch size, is not analyzed. Parametric analysis of the learning algorithm, as well as the implementation of more recent state-of-the-art RL algorithms (e.g., PPO), can be considered other directions of future work with CAM. The current learning framework for CAM has been implemented with greedy approach for decision makiinn,. The
performance can be improved by adopting an epsilon greedy approach. In real-world settings, is possible that two robots want to make decisions at the same time, which might cause them to visit the same location. This is very rare and there are various mitigations address this issue. For example, while robots are moving toward their selected task locations, they can check if their decision conflicting with another robot based on recent information. If there is conflict, the robot with the worst time can cancel its current task and select new task.
I ABBREVIATIONS:
Table 16: Abbreviations used in this paper
CAM
Dovariant-Attention based Model
CCN
Covariant Compositional Networks
CO
Combinatorial Optimization
CVRP
Capacitated Vehicle Routing Problem
BILS
Enhanced Iterated Local Search
GNN
Graph Neural Network
ID
In-schedule Dependencics
ILP
Integer Linear Programming
ILS
Iterated Local Search
INLP
Integer Non-Linear Programming
MDP
Markov Decision Process
MHA
Multi-Head Attention
MR
Multi-Ron Robot
MRTA
Multi-Robot Task Allocation
mTSP
multi- Traveling Salesman Problem
RL
Reinforcement Learning
SR-ST
Single-Robo task Single Task robot
TAPTC
Task Allocation Problem with Time and Capacity
TSP
Traveling Salesman problem
UAV
Unmanned Acrial Vehiele
VRP
Vehicle Routing Problem
26


Reviews:
[{"review_id": "xvVJxIcncDy", "reviewer": "Reviewer_AMwa", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. The paper is well written and well organized. The references are appropriate and the problem being addressed is very well explained.\n\n2. 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.\n\n3. 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.\n\n4. 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.\n\n5. 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?\n", "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.\n\nCase 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.\n", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "EiUW_FyjbVr", "reviewer": "Reviewer_8Xfc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n\nThe 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.\n\n**Weaknesses**\n\nThe 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. \n\nLooking 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). \n\nI 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.\n\n**Suggestions for improvement**\n\n*Overall story*\n\nThe 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.\n\n*Technical Points*\n\nThe 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. \n\nThe 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?\n\nFinally, 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? \n\n*Formatting and style*\n\nAs 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_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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "AurQPW3Cghe", "reviewer": "Reviewer_uLHX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "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. \nThe 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.  \n\n\n<Minor comments>\n1. Deterministic assumption:\nThey 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.\n\n2. The first sentence of 2.1 \nThe sentence starting with \"The MRTA problem can…\" may be inaccurate. (A graph itself is not a \"problem.\")\n\n3. Too small figures and tables.\nMany figures (e.g., 1) and tables (e.g., 3 and 4) are too small to read. Please make them larger and improve the readability. \n\n4. Highlight color\nTable 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.\nPlease use other styles (e.g., underline or bold style).\n\n5. Topline\nIn 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. \nAlso, it helps readers grasp the information to give underline or bold to the best value. \n\n6. Qualitative evaluation\nOnly quantitative results are shown. Providing qualitative evaluations may help readers understand the characteristic of the proposed methods.\n\n\n", "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.\nThe proposed learning architecture is called Covariant Attention-based Mechanism (CAM). \nThe 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.\n", "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. \nAs a whole, the paper is a good paper involving meaningful new information. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6IuC0uhWmFZ", "reviewer": "Reviewer_Yr3w", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Strengths:\n\n+ The idea of using learning methods to solve a SR-ST MRTA problem is interesting. \n\n+ Discussion of the technical approach is clear.\n\nWeaknesses:\n\n- 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?\n\n- 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?\n\n- 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?\n\n- 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\".\n\n- 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?\n\n- What are the task completion time of each approach for the testing scenarios in Table 1 and Table 2?\n\n- 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.  \n\n- Minor: The variable t_i is used for both deadline and event/timestep index.\n", "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.", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-3vXyGshTsS", "reviewer": "Reviewer_tBqb", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "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_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.\n\n", "summary_of_the_review": "An application paper with adequate evaluations.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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