Parameterized complexity analysis in robot motion planning

Abstract

A series of previous PSPACE- and NP-hardness results suggest that no general algorithm for robot motion planning can be polynomial in all of its input parameters, i.e., at least one parameter x must be exponential relative to a constant, e.g., 2/sup x/, or another parameter of the problem, e.g., y/sup x/. However, they have not answered the more relevant question posed by some FP space-based algorithms-namely, whether there is a general algorithm that is polynomial in all input parameters except k, in which k may yet be exponential relative to a constant or itself. In this paper, using the theory of parameterized computational complexity developed by Downey and Fellows (1992), the authors establish that the answer to this question is probably "no". The authors give an overview of this theory and derive their main result. Finally, they briefly discuss the implications for robotics of both these results and the parameterized complexity framework.