The Deadlock Recovery Problem in the AGV System with the Ladder Guidepath Layout and its Computational Complexity
Kenji Koizumi, Shigeru Masuyama
This paper proposes the minimum time deadlock recovery problem in the AGV system with the ladder guidepath layout(DRPL, for short) and analyzes its computational complexity. In order to analyze the computational complexity, this paper introduces the decision problem version of DRPL to ask whether all deadlocks in the AGV system are recoverable within predetermined time, and NP-hardness in a special case of the problem is proved. Moreover, the condition by which the problem becomes NP-hard when the AGV system has a ladder guidepath layout is clarified, and we propose a polynomial time algorithm that solves the optimization problem version of this problem whenever the problem in the ladder guidepath layout is not NP-hard.