TY - JOUR
AU - Yang, Chao
PY - 2023/12/31
Y2 - 2024/07/17
TI - On the Complexity of Motion Planning Problem of a Forklift: Discrete and Computational Geometry, Graphs, and Games
JF - Thai Journal of Mathematics
JA - Thai J Math
VL - 21
IS - 4
SE - Articles
DO -
UR - https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1545
SP - 785–798
AB - <p>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.</p>
ER -