Algorithmic motion planning

Abstract

INTRODUCTION Motion planning is a fundamental problem in robotics. It comes in a variety of forms, but the simplest version is as follows. We are given a robot system B, which may consist of several rigid objects attached to each other through various joints, hinges, and links, or moving independently, and a two-dimensional or threedimensional environment V cluttered with obstacles. We assume that the shape and location of the obstacles and the shape of B are known to the planning system. Given an initial placement Z 1 and a nal placement Z 2 of B, we wish to determine whether there exists a collision-avoiding motion of B from Z 1 to Z 2 , and, if so, to plan such a motion. In this simpli ed and purely geometric setup, we ignore issues such as incomplete information, nonholonomic constraints, control issues related to inaccuracies in sensing and motion, nonstationary obstacles, optimality of the planned motion, and so on. Since the early 1980's, motion planning has been an intensiv