Exploiting Parallelism in Multi-Task Robot Allocation Problems

Multi-Agent Systems (MASs) have been widely adopted in robotics, as a means to solve complex missions by subdividing them into smaller tasks. In such a context, Multi-Robot Task Allocation (MRTA) has been a relevant research area, with the main aim of providing formulations and solutions to different mission configurations, in order to optimize the planning and the execution of complex missions utilizing multiple robots.In recent years, robotic systems have become more powerful thanks to the adoption of novel computing platforms, enabling an increased level of parallelism, in terms of sensing, actuation, and computation. As a result, more complex missions can be achieved, at the cost of an increased complexity for the optimization of the mission planning.In this paper, we first introduce the distinction between physical and virtual tasks of the robots, and their relation in terms of parallel execution. Therefore, we propose a mathematical formalization of the mission planning problem for Multi-Task (MT) robots, in the presence of tasks that require only a Single-Robot (SR) to complete, and in the presence of Time-Extended Assignments (TAs). The problem is modeled with a Mixed-Integer Linear Programming (MILP) formulation, with the objective of minimizing the total makespan of the mission, exploiting the potential (physical and virtual) parallelism of the robots. The model is validated over some representative scenarios, and their respective solutions are obtained with the CPLEX optimization tool, showing the generality of the proposed formulation.