Cannot avoid penalty? Let’s minimize

Abstract

Multi-robot systems are deployed in a warehouse to automate the process of storing and retrieving objects in and out of the warehouse. The efficiency of the system largely depends on how the tasks are allocated to the robots. Though there exists a number of techniques that can perform multi-robot task allocation quite efficiently, they hardly consider deadline for task completion while assigning tasks to the robots. A careful allocation is of paramount importance when there is an associated penalty with each of the tasks if it is not completed within a stipulated time. In this work, we develop an algorithm, called Minimum Penalty Scheduling (MPS) that allocates tasks among a group of robots with the goal that the overall penalty of executing all the tasks can be minimized. Our algorithm provides a robust, scalable, and near-optimal real-time task schedule. By comparing with the state-of-the-art algorithm, we show that MPS attracts up to 62.5% less penalty when a significant number of tasks are bound to miss the deadline. Additionally, MPS is also suitable for real-time multi-processor scheduling since it schedules a higher number of tasks within their deadline.