An automatic motion planning system for a convex polygonal mobile robot in 2-dimensional polygonal space

Abstract

We present an automatic system for planning the (translational and rotational) collision-free motion of a convex polygonal body B in two-dimensional space bounded by a collection of polygonal obstacles. The system consists of a (combinatorial, non-heuristic) motion planning algorithm, based on sophisticated algorithmic and combinatorial techniques in computational geometry, and is implemented on a Cartesian robot system equipped with a 2-D vision system. Our algorithm runs in the worst-case in time Ο(knλ6(kn) log kn), where k is the number of sides of B, n is the total number of obstacle edges, and λ6(r) is the (nearly-linear) maximum length of an (r, 6) Davenport Schinzel sequence. Our implemented system provides an “intelligent” robot that, using its attached vision system, can acquire a geometric description of the robot and its polygonal environment, and then, given a high-level motion command from the user, can plan a collision-free path (if one exists), and then go ahead and execute that motion.