Multi-Agent Route Optimization for Robotic Mobile Fulfillment Systems

Abstract

The Robotic Mobile Fulfillment System (RMFS) is a robotized material handling system where multiple robots transport movable shelves to and from stocking points and workstations in a warehouse. In this paper, we deal with the problem of finding collision-free routes for multiple robots to move from their starting points to destinations in a RMFS, which is defined as a generalization of the multi-agent path finding problem (MAPFP). In RMFSs, collisions among moving robots may occur due to the physical volume of robots and the inexact execution of planned routes by robots in terms of the planned timing of passing through points on the routes, which makes it difficult to directly apply the existing algorithms for MAPFP that assume the exact execution of planned routes by agents with no physical volume. Therefore, we defined the problem as a multi-agent path finding problem with the prespecified time spacing at points to address the possible sources of collisions among robots, and propose an integer optimization model for the problem. Since the proposed integer optimization model has a large number of decision variables and constraints, we propose heuristic and exact algorithms based on the Lagrangian relaxation technique and the conflict based search. Experimental results show that the proposed algorithms are effective in finding good quality solutions within a limited time even when the number of robots or the time spacing are large.