Presentation of : The Computational Complexity of Motion Planning
Paper written by Jeffrey R. Hartline and Ran Libeskind-Hadas, published in the Society of Industrial and Applied Mathematics Review, 2003
1. Introduction:
Motion planning is a field that involves studying and optimizing movement and use of space. Many motion planning problems are qualified as complex to solve, harder than P problems . This paper examines the computational complexity of a popular motion planning game: the Lunar Lockout puzzle .
The popular version uses 5x5 grids, while the general LL is of the size mxm. Moreover , the specific variance treated in the paper distinguishes between mobile and stationary robots. (there is no distinction in the game normally)
2. Results:
The authors introduce the class of PSPACE, which is the class of problems that are solvable in polynomial space of the size of the input. PSPACE problems are at least as hard as NP-Complete problems, and arguably (still yet to prove) strictly harder .
The authors end up proving , that a generalized variance of the Lunar Lockout (GLLV)puzzle belongs to the class PSPACE as well as is PSPACE-Complete. meaning that if GLLV is solvable, any other problem in PSPACE-Complete is solvable.
3. Proof and Further reading
The proof of GLLV belonging to PSPACE-Complete is complex in the way that it relies on non-deterministic Turing Machines, as well as using an approach that is analogous to that of Cook’s theorem proof and the satisfiability (SAT and 3SAT) problem.
The original paper does a great job of laying the bases of proofs to the reader, but further reading in the aforementioned topics are of great help to understanding the proof:
- Computational Complexity: https://smith.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=d35bd38c-9dff-4d8f-a9ea-ab9800643af8
- NP-Completeness and Cook’s theorem: https://smith.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=7396647e-6305-410d-8d7d-aba3011ee876
- Savitch’s theorem : NPSPACE= PSPACE https://courses.cs.washington.edu/courses/cse431/14sp/scribes/lec16.pdf
An overview of the proof that is divided as two theorems:
Theorem 1: GLLV is in PSPACE
WTS :GLLV is in NPSPACE ( solved by a nondeterministic Turing machine in Polynomial space)
Given an instance of mxm board, there are at most 4^(m²) possible configurations (an empty cell, a mobile robot, a stationary robot or a target robot ). If the instance is solvable then there exists a sequence of at most 4^(m²) configurations from the start to the solution.
A nondeterministic decider will repeatedly “guess” the next move of the robot and halt after 4^(m²).
In binary, 4^(m²) is stored in log_2(4^(m²)) = O(m²) : Linear for an input of m².
Using Savitch’s theorem : PSPACE = NPSPACE,
GLLV is in PSPACE
Theorem 2: if GLLV is solvable, every PSPACE-Complete is also solvable
The approach is analogous to SAT problem: WTS that every problem in PSPACE is reducible to GLLV.
This proof is the more complex part. It uses the notion of gadgets, which are an important way to model and simplify the GLLV scenarios.
4 . Conclusion :
I found this paper to be genuinely engaging. There was a lot of effort done in the first couple pages to familiarize the reader to the problems being discussed and it was really helpful to see how these notions can be applied to the General Lunar Lockout Variance puzzle.
The strategy used in the proof of PSPACE-completeness, although successful in the case of GLLV, faces many obstacles in the case of GLL. Since there is no distinction between mobile and stationary robots, there are more complications and unexpected interactions between the elements.
Furthermore, I believe the result of this paper is of great importance. By introducing ad discussing this new level of complexity (PSPACE) and showing that some motion planning problems belong to that class proves that in the field of robotics, calculations and algorithms can be complex to the point where the search for a 100% accurate algorithm is not efficient and that estimations and heuristics are the optimal approach.
This further highlights the challenges facing small-scale operations. It is very hard to calculate the exact way a robot arm should move to reach for an object, let alone to perform a precise surgery .
Overall, I am very glad I got to read this paper. I chose to present it because I am very interested in robotics, and was curious how my recently acquired experience in Computability Theory applies to this less abstract topic.
