A Formal Definition of the Multi-Robot Multi-Task Time-extended Assignment Problem Configuration

Multi-Robot Systems (MRSs) play a crucial role in several fields, including industrial automation, precision agriculture, and urban search and rescue, by enhancing efficiency and operational capabilities. One of the main challenges in these systems is the efficient allocation of tasks, known as Multi-Robot Task Allocation (MRTA). This paper focuses on a particularly complex configuration of MRTA that involves Multi-Task (MT) Robots capable of performing multiple tasks simultaneously, Multi-Robot (MR) Tasks that require coordinated efforts from several robots, and Time-extended Assignments (TA) that demand extended duration scheduling. Despite notable advancements in this area, the MT-MR-TA configuration remains underexplored. Existing research often fails to address the specific challenges associated with coordinating and scheduling these complex tasks. This paper aims to fill this gap by introducing new computational models based on Integer Linear Programming (ILP) and Constraint Programming (CP). These models are purposefully designed to formalize and tackle the intricate dynamics of MT-MR-TA, offering a structured approach to solve this multidimensional optimization problem. We rigorously evaluate these models for their effectiveness using advanced, general-purpose solvers across various instances, with a focus on model scalability, solver efficiency, and overall solution quality.