Optimized simultaneous conflict-free task assignment and path planning for multi-AGV systems

In this paper we address the problem of assigning a set of tasks to a set of Automated Guided Vehicles (AGVs), in a conflict-free manner. Specifically, we consider a system of multiple AGVs, moving along a predefined roadmap, and utilized for transportation of goods in automated warehouses. Sequential application of task assignment and path planning often gives rise to pathological situations, such as deadlocks, in which AGVs block each other, thus preventing tasks completion. In this paper we propose a method for assigning tasks while taking into account the subsequent path planning, encoding possible conflicts into a conflict graph, that is subsequently utilized for defining constraints of an optimization problem. Simulations are performed on maps of real industrial environments, to compare the proposed method with traditional task assignment.