Makespan Minimization for Multi-Robot Task Allocation With Balance-Aware Pointerformer
Abstract
This paper presents a transformer-based reinforcement learning framework for time-critical multi-robot task allocation, where the objective is to minimize mission completion time (i.e., makespan) by formulating the problem as a min–max multi-depot open vehicle routing problem. In this problem, conventional methods often do not scale well to large instances. Standard transformer policies scale better but are sensitive to the order in which robots are allocated, since early allocations constrain later choices and can produce imbalanced workloads that lead to a prolonged makespan. To address this, we propose Balance-Aware Pointerformer (BAP), which adapts problem augmentation and multi-start decoding into a diverse-order exploration strategy with a shared baseline, supported by a memory-efficient encoder that keeps this exploration tractable. In addition, BAP incorporates a balance-aware context embedding that explicitly encodes global and per-robot progress, guiding the policy toward workload-balanced allocations. Experimental results on uniform and clustered task distributions demonstrate that BAP remains competitive with a time-limited MILP solver on small instances, improves solution quality on larger-scale problems, and achieves lower makespan than representative heuristic and learning-based baselines across nearly all tested settings.