Deadlock avoidance algorithm for AGVs on a tessellated layout

Automated guided vehicle (AGV) systems are widely used in different industrial environments. The performance of these systems depends heavily on the control strategies used, among others to ensure all movements are executed in a deadlock-free manner. In this paper, we propose a deadlock avoidance algorithm that is proven to result in deadlock-free behavior for limited known future movements of all AGVs. The algorithm can be applied to a system with a tessellated layout, where the drivable space is discretized into tiles. There are no restrictions on the shapes and sizes of both tiles and AGVs, hence such a system is suitable for controlling a heterogeneous fleet. Tiles need to be reserved for an AGV before the AGV can move over them. The deadlock avoidance algorithm is called each time the central controller wants to reserve tiles for an AGV; the reservation is only allowed if, within limited known future movements of all AGVs, at least one order of movements exists such that the system remains deadlock-free.