A Reinforcement Learning-Based Heuristic for Multi-Agent Task Scheduling with Spatial Constraints

This paper addresses a multi-agent task scheduling problem with precedence constraints and spatial interference for the assembly of three-dimensional structures using agents. The objective is to minimize the overall completion time (makespan) by assigning tasks to agents while ensuring collision-free execution in a dynamic and shared spatial environment. We propose a reinforcement learning-based heuristic in which each task is modeled as a learning automaton that iteratively updates a probability distribution over agent assignments based on observed performance. Candidate schedules are evaluated through a surrogate cost function that estimates the makespan while avoiding explicit collision checking. A path planning module based on an A* search enforces collision avoidance and temporal consistency, being used for validating the feasibility of the generated schedules. Computational experiments demonstrate that the proposed approach identifies efficient task allocations, adapts to heterogeneous and homogeneous agent capabilities and effectively balances workload while reducing makespan.