MOTION PLANNING IN THE PRESENCE OF MOVING OBSTACLES

This paper investigates the computational complexity of planning the m otion of a body B in 2-D or 3-D space, so as to avoid collision with m oving obstacles of known, easily computed, trajectories. Dynamic movem ent problems are of fundamental importance to robotics, but their comp utational complexity has not previously been investigated. We provide evidence that the 3-D dynamic movement problem is intractable even if B has only a constant number of degrees of freedom of movement. In par ticular, we prove the problem is PSPACE-hard if B is given a velocity modulus bound on its movements and is NP-hard even if B has no velocit y modulus bound, where, in both cases, B has 6 degrees of freedom. To prove these results, we use a unique method of simulation of a Turing machine that uses time to encode configurations (whereas previous lowe r bound proofs in robotic motion planning used the system position to encode configurations and so required unbounded number of degrees of f reedom). We also investigate a natural class of dynamic problems that we call asteroid avoidance problems: B, the object we wish to move, is a convex polyhedron that is free to move by translation with bounded velocity modulus, and the polyhedral obstacles have known translationa l trajectories but cannot rotate. This problem has many applications t o robot, automobile, and aircraft collision avoidance. Our main positi ve results are polynomial time algorithms for the 2-D asteroid avoidan ce problem, where B is a moving polygon and we assume a constant numbe r of obstacles, as well as single exponential time or polynomial space algorithms for the 3-D asteroid avoidance problem, where B is a conve x polyhedron and there are arbitrarily many obstacles. Our techniques for solving these asteroid avoidance problems use ''normal path'' argu ments, which are an interesting generalization of techniques previousl y used to solve static shortest path problems. We also give some addit ional positive results for various other dynamic movers problems, and in particular give polynomial time algorithms for the case in which B has no velocity bounds and the movements of obstacles are algebraic in space-time.