Hybrid task planning and scheduling in heterogeneous multi-agent systems based on LLMs and constraint programming

Complex tasks that require resource sharing, temporal dependencies, and collaboration among agents with different capacities must be carried out by heterogeneous multi-agent systems, such as those involving humans and robots. Converting high-level natural language job descriptions into executable and optimized plans is a fundamental challenge for these systems. Although they require experts to explicitly describe the domain models, traditional optimization techniques, such as those based on constraint programming (CP), offer strong assurances of optimality. Large language models (LLMs), on the other hand, can interpret natural language and reason over high-level descriptions, but lack reliability and formal guarantees when employed alone. Because of these factors, we present a two-layer architecture that combines the benefits of CP with the flexibility of LLMs. Specifically, the first layer makes use of an LLM to interpret natural language task descriptions and break them down into ordered action sequences. Then, the second layer formulates the resulting plan as a constraint optimization problem, enabling efficient scheduling and allocation among agents under resource and time limitations. We benchmark our method against various baseline approaches, including an oracle baseline and a state-of-the-art PDDL-based one, and validate it in different scenarios with increasing planning complexity. Results show that the proposed framework improves feasibility, solution optimality, and efficiency compared to the baselines.