A FAST ALGORITHM FOR PLANNING COLLISION-FREE PATHS WITH ROTATIONS

Motion planning is a major problem in robotics. The objective is to pl an a collision free path for a robot moving through a workspace popula ted with obstacles. In this paper, we present a fast and practical alg orithm for moving a convex polygonal robot among ii set of polygonal o bstacles with translations and rotations. The running time is O(c((n k)N + n log n)), where c is a parameter controlling the precision of the results, n is the total number of obstacle vertices, k is the numb er of intersections of configuration space obstacles, and N is the num ber of obstacles, decomposed into convex objects. This work builds upo n the slabbing method proposed by Ahrikencheikh et al. [2], which find s an optimal motion for a point among a set of nonoverlapping obstacle s. Here, we extend the slabbing method to the motion planning of a con vex polygonal robot with translations and rotations, which also allows overlapping configuration space obstacles. This algorithm has been fu lly implemented and the experimental results show that it is more robu st and faster than other approaches.