Graph-Based Task Allocation for Multi-Agent Fleet Management: A Genetic Algorithm Approach with LLM Integration

Efficient task allocation and coordination are critical for heterogeneous multi-agent systems operating in dynamic field environments. This paper presents a closed-loop framework that integrates Large Language Models (LLMs) with graph-based optimisation to enable end-to-end task decomposition, allocation, and adaptive execution. High-level task scripts are initially parsed by an LLM into structured execution flows, which are transformed into Directed Acyclic Graphs (DAGs) capturing action-level dependencies. A Genetic Algorithm (GA) then optimises agent-to-task assignments by minimising makespan under capability and battery constraints. To ensure robustness, the framework incorporates an LLM-driven recovery module that enables localised replanning under execution failures without interrupting unaffected agents. System-level experiments in a high-fidelity agroforestry simulation demonstrate a 37% increase (p<0.001) in harvesting productivity and a 19% reduction in human idle time compared to manual baselines. Under mid-execution failures, the system maintains significantly higher performance, with replanning latencies averaging 24 s. The framework scales to large fleets (up to 1000 agents) and effectively enhances human–robot collaboration through structured, dependency-aware coordination.