Computational aspects of compliant motion planning

摘要

The study of robot motion planning forms an important bridge between researchers in robotics and those in theoretical computer science. Prompted by the capabilities of real robots and the heuristics used to control them, theoreticians have responded with a flood of algorithms and hardness results for motion planning problems. Compliant motion is one paradigm for robot motion planning, in which a robot commanded to move into a wall may slide along it. There are three important features that make the compliant motion model desirable. First, a robot performing basic compliant motion requires only a force sensor, and therefore may be easier to construct than a robot with more sophisticated sensors (such as a visual system). Second, the robot fits into existing environments without requiring any changes (such as installing special light beams). Third, sliding along the walls of the environment enables the robot to grope its way toward the goal, and often makes up for imprecise control and sensing. We start by investigating the geometric properties of compliant motion paths. These properties enable us to develop efficient motion planning algorithms for several flavors of compliant motion. The algorithms we develop in this thesis give rise to a novel data structure for maintaining the convex hull of a polygonal chain, which we describe in detail and hope it will be of independent interest. We conclude with a slightly different aspect of compliant motion. The path that a robot performing compliant motion follows in response to a commanded direction resembles the vertical path that a small particle follows when moving due to gravity in the presence of obstacles. We use our previous knowledge of compliant motion to develop algorithms and hardness results for the problem of taking a number of small particles out of a polygonal container.