Learning multi-robot task allocation using capsule networks and attention mechanism

This paper presents a new graph reinforcement learning (RL) architecture to solve multi-robot task allocation (MRTA) problems without requiring any tedious heuristics. Multi-feature tasks are abstracted as nodes in an undirected graph in this case. The primary goal is to not only generalize across unseen problems of similar size but also scale to problems with much larger task spaces without retraining; which otherwise could be particularly expensive when simulating multi-robot operations. While drawing inspiration from the emerging paradigm in learning to solve combinatorial optimization (CO) problems, a new encoder–decoder architecture called Capsule Attention-based Mechanism or CAPAM is presented here to achieve this goal. More specifically, a novel choice of encoder is made in the form of graph capsule convolutional networks, which enables permutation invariant embeddings that capture the local and global structure of the task graph by using higher-order statistical moments of the vectors of node features. This encoded information is combined with a context component encoding mission and robot states, and processed through the decoder that computes the probability of selecting different available tasks by a robot. To train the CAPAM model, a policy-gradient method based on Proximal Policy Optimization is used. When evaluated over unseen scenarios, CAPAM demonstrates comparable task completion performance and faster decision-making compared to standard non-learning-based online MRTA methods. CAPAM demonstrates substantial gains in generalizability and (task) scalability in comparison to a popular approach for learning to solve CO problems (the pure attention mechanism) and preserves this performance advantage even under partial observation scenarios.