Optimizing Container Loading With Autonomous Robots

Abstract

In this paper, we investigate a problem associated with transferring a set of containers from the storage to the loading area of a warehouse using autonomous robots. In addition to assigning robots to containers, the special topology considered in this paper requires coordinated planning of the robots' movement to avoid conflicts. We formulate the joint problem of robot assignment and movement coordination with the objective of minimizing the time required for all robots to carry their assigned containers to the destination, subject to conflict-free movement of all robots. We use the concept of abstract time windows (ATWs) to represent the movement of robots. The conditions for detecting conflicts in the ATW representation are introduced along with the necessary operations for resolving conflicts. For the solution of the problem, two approaches are developed. The first is a mathematical programming approach that formulates the problem as a mixed-integer linear program that allows optimal solution using appropriate solvers, while the second is a heuristic approach that allows fast, close-to-optimal solutions. Even though the proposed approaches focus on the case where the number of robots is equal to the number of containers, we also discuss how to solve the problem when having unequal number of robots and containers. Simulation results show that the heuristic approach provides a solution within 5% of the optimal solution with the minimum time of completion of all tasks being the performance metric, and executes six orders of magnitude faster than a state-of-the-art mathematical programming solver.