DISTRIBUTED GRAPH-BASED, HETEROGENEOUS, SELF-ORGANIZING SWARM TASK-ALLOCATION

Swarms of autonomous robots are increasingly used in situations that are dangerous for humans, such as search and rescue operations after a disaster. In these scenarios, aerial and ground robots with different capabilities must decide which robot carries out each task, while new tasks emerge during the mission and communication remains limited: this is exactly the task allocation problem we tackle in this work. Classical combinatorial approaches (e.g., the Hungarian algorithm) guarantee optimal, minimum-cost assignments, but they are centralized, computationally expensive, and dependent on a precisely calibrated cost function. Moreover, they operate on individual snapshots of the system state, with no guarantee of temporal consistency, often causing unnecessary task reassignments. Classical distributed approaches converge slowly to a collision-free, minimum-cost assignment. This thesis proposes a self-organizing, distributed multi-agent task allocation system that overcomes these limitations while keeping decentralization, collision-free behaviour, and temporal consistency. The architecture combines a local Ego-Net, which evaluates tasks according to each agent's own perception and capabilities, with a Coordination GNN that aggregates information from neighbouring robots to determine the task to execute (or an idle state), enforcing locality by design so that a centrally trained model remains consistent with fully decentralized deployment. Training follows a two-phase pipeline: (i) imitation learning first reproduces the Hungarian algorithm's assignments, keeping their quality and collision-free behaviour without its centralized structure; (ii) reinforcement learning then fine-tunes the model to optimize the system's temporal dynamics, reducing collisions and unnecessary task switching through an explicit temporal memory, and introducing the desired behaviour through the reward. The system is evaluated on a custom benchmark built with Jumanji, a JAX-based simulation library, using a two-dimensional grid environment with obstacles. The benchmark uses scenarios from 2 to 100 robots and from 5 to 200 tasks, with the number of tasks scaled proportionally to the number of robots. While training is carried out with up to 25 robots, the model generalizes to scenarios with up to 100 robots, keeping collisions within 1% of the episodes in full mesh and in the limited-range regime. The results show that the proposed approach preserves the assignment quality of classical methods while overcoming their limitations of centralization, dependence on an explicit cost function, and temporal blindness.