Cannot avoid penalty? Let’s minimize

Chayan Sarkar and Marichi Agarwal, "Cannot avoid penalty? Let’s minimize", IEEE International Conference on Robotics and Automation (ICRA), Montreal, Canada, 2019.


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 of 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 finds schedule such that a higher number of tasks can meet their deadline.

BibTex entry

    title={Cannot avoid penalty? Let’s minimize},
    author={Sarkar, Chayan and Agarwal, Marichi},
    booktitle={International Conference on Robotics and Automation (ICRA)},