Search

Multi-agent systems have received a tremendous amount of attention in many areas of research and industry, especially in robotics and computer science. With the increased number of agents in missions, the problem of allocation of tasks to agents arose, and it is one of the most fundamental classes of problems in robotics, formally known as the Multi-Robot Task Allocation (MRTA) problem. MRTA encapsulates numerous problem dimensions, and it aims at providing formulations and solutions to various problem configurations, i.e., complex multi-agent missions. One dimension of the MRTA problem has not caught much of the research attention. In particular, problem configurations including Multi-Task (MT) robots have been neglected. However, the increase in computational power, in robotic systems, has allowed the utilization of parallel task execution. This in turn had the benefit of allowing the creation of more complex robotic missions; however, it came at the cost of increased problem complexity. Our contribution to the aforementioned domain can be grouped into three categories. First, we model the problem using two different approaches, Integer Linear Programming and Constraint Programming. With these models, we aim at filling the gap in the literature related to the formal definition of MT robot problem configuration. Second, we introduce the distinction between physical and virtual tasks and their mutual relationship in terms of parallel task execution. This distinction allows the modeling of a wider range of missions while exploiting possible parallel task execution. Finally, we provide a comprehensive performance analysis of both models, by implementing and validating them in CPLEX and CP Optimizer on the set of problems. Each problem consists of the same set of test instances gradually increasing in complexity, while the percentage of virtual tasks in each problem is different. The analysis of the results includes exploration of the scalability of both models and sol

Multi-Agent Systems have received a tremendous amount of attention in many areas of research and industry, especially in robotics and computer science. With the increased number of agents in missions, the problem of allocation of tasks to agents arose, and it is one of the most fundamental classes of problems in robotics, formally known as the Multi-Robot Task Allocation (MRTA) problem. MRTA encapsulates numerous problem dimensions, and it aims at providing formulations and solutions to various problem configurations, i.e., complex multi-robot missions. One dimension of the MRTA problem has not caught much of the research attention. In particular, problem configurations including Multi-Task (MT) robots have been neglected. However, the increase in computational power, in robotic systems, has allowed the utilization of parallel task execution. This in turn had the benefit of allowing the creation of more complex robotic missions; however, it came at the cost of increased problem complexity. To overcome the aforementioned problem, we introduce the distinction between physical and virtual tasks and their mutual relationship in terms of parallel task execution. To fill in the gap in the literature related to MT robot problem configurations, we provide a formalization of the mission planning problem, using MT robots, in the form of Integer Linear Programming and Constraint Programming (CP), to minimize the mission makespan. The models are validated in CPLEX and CP Optimizer on the set of benchmarks. Moreover, we provide a comprehensive performance analysis of both solvers, exploring their scalability and solution quality.

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., Aggregate Farming in the Cloud, FIESTA - Federated Choreography of an Integrated Embedded Systems Software Architecture