Portal de Periódicos da CAPES

The Computational Complexity of Motion Planning

2003; Society for Industrial and Applied Mathematics; Volume: 45; Issue: 3 Linguagem: Inglês

10.1137/s003614450139517

1095-7200

Jeffrey R. Hartline, Ran Libeskind-Hadas,

AI-based Problem Solving and Planning

In this paper we show that a generalization of a popular motion planning puzzle called Lunar Lockout is computationally intractable. In particular, we show that the problem is PSPACE-complete. We begin with a review of NP-completeness and polynomial-time reductions, introduce the class PSPACE, and motivate the significance of PSPACE-complete problems. Afterwards, we prove that determining whether a given instance of a generalized Lunar Lockout puzzle is solvable is PSPACE-complete.