Motion Planning

This is the first installment of a two-part tutorial. The goal of the first part is to give the reader a basic understanding of the technical issues and types of approaches in solving the basic path-planning or obstacle-avoidance problem. The second installment will cover more advanced issues, including feedback, differential constraints, and uncertainty. Note that this is a brief tutorial rather than a comprehensive survey of methods. For the lat ter, consult some of the recent textbooks. Motion planning involves getting a robot to automatically determine how to move while avoiding collisions with obstacles. Its original formulation, called the piano mov er´s problem, is imagined as determining how to move a complicated piece of furniture through a cluttered house. Have you ever argued about how to move a sofa up a stairwell? It has been clear for several decades that getting robots to reason geometrically about their environments and synthesize such plans is a fundamental difficulty that recurs all over robotics.