Energy Efficient Multi-Robot Task Allocation Constrained by Time Window and Precedence

To meet the demands in terms of energy-efficient and fast production and delivery of goods, robotic fleets began to populate warehouses and industrial environments. To maximize the profitability of the operations, multi-robot systems are required to coordinate agents and avoid downtime efficiently. In this paper, agent coordination is formulated as a multi-robot task allocation (MRTA) problem with time and precedence constraints. The method capitalizes on a graph method to build a measure graph reflecting the sparsity of tasks and a precedence graph, which includes the task constraints, to group the tasks into batches. A batch solver is provided to obtain the final solutions to the MRTA. In this way, the sustainability and environmental impact of logistics operations can be improved by reducing the number of robots needed to complete tasks and also by assigning tasks closest to the robot location, reducing the amount of time and the total energy required for the robots to complete the job. Extensive experiments on both uniformly distributed and sparse data sets prove the effectiveness of the proposed algorithm compared to state-of-the-art algorithms such as MIP and TePSSI. Note to Practitioners—This paper was motivated by the problem of minimizing the energy consumption of multi-robot systems in the execution of complex tasks, which requires, in the most general case, the motion of the robot to a target location and further on-site operations. This scenario is particularly relevant in smart, automated warehouses, where mobile robots are repeatedly demanded to store or dispatch goods in a structured environment, where operation duration and future requests are known a priori. The paper formulates this problem by means of a batched multi-robot task allocation (BMRTA) optimization, which can include time windows and precedence constraints jointly. First, the task constraints are encoded into two graphs and then combined to group subtasks together in batches. Then, each batch is solved separately, minimizing the overall energy required to achieve the tasks in the batch. Although the optimality of the solution is ensured only locally, i.e., within the same batch, the task clustering improves the computational efficiency with respect to global approaches, especially in large-sized problems. Experimental results demonstrated that when comparing BMRTA with literature approaches such as MIP and TePSSI, not only the energy consumption but also the total travel distance can be minimized while the total duration of the tasks remains comparable.