A new algebraic method for robot motion planning and real geometry

摘要: We present an algorithm which solves the findpath or generalized movers' problem in single exponential sequential time. This is first for whose time bound less than double exponential. In fact, combinatorial exponent of equal to number degrees freedom, making it worst-case optimal, and equaling improving bounds many special purpose algorithms. The accepts a formula semi-algebraic set S describing free configurations produces one-dimensional skeleton "roadmap" set, connected within each component S. Additional points may be linked roadmap linear Our method draws from results singularity theory, particular makes use notion stratified sets as efficient alternative cell decomposition. introduce algebraic tool called multivariate resultant gives necessary sufficient condition system homogeneous polynomials have solution, show that can computed polynomial parallel Among consequences this result are new methods quantifier elimination improved gap theorem absolute value roots polynomials.