Polynomial-time optimal liveness enforcement for guidepath-based transport systems. (August 2021) - Reveliotis, Spyros; Masopust, Tomáš; Ibrahim, Michael
Abstract: Zone-controlled guidepath-based transport systems is a modeling abstraction representing the traffic dynamics of a set of agents circulating in a constricted medium. An important problem for the traffic coordinator of these systems is to preserve liveness, that is, the ability of each agent to successfully complete its current trip and to be engaged in similar trips in the future. We present a polynomial-time algorithm for enforcing liveness in a class of these systems, in a maximally permissive manner. Our result is surprising and applicable in the traffic control of various unit-load material handling systems and other robotic applications.