On the Complexity of Motion Planning Problem of a Forklift

Discrete and Computational Geometry, Graphs, and Games

Abstract

The robot motion planning problem is one of the most studied problems in computational geometry in continuous settings. We study the Forklift Motion Planning Problem, which is defined based on a puzzle called Zaikoban, in a discrete setting of 3-dimensional space. We demonstrate that the configuration space method can be applied to the discrete case. In particular, we show that the forklift motion planning problem is solvable in polynomial time for the one-box case, and show that the general forklift motion planning problem with multiple boxes is PSPACE-complete by reduction to the nondeterministic constraint logic (NCL) problem.