Motion planing

Robotics Research

The Sixth International Symposium

edited by Takeo Kanade and Richard Paul

The International Foundation for Robotics Research Cambridge, USA.

2

Motion Planning
Jean-Claude Latombe Robotics Laboratory, Department of Computer Science Stanford University, Stanford, CA 94305, USA

One important goal in robotics is to make it possible for robots to perfonn taskswhose goals are expressed in high-level declarative terms. In this context, researchers in motion planning develop algorithms to automatically generate motions to achieve goals fonnulated as geometric arrangements of the robot and its workspace. Motions must avoid collisions with obstacles. They must deal adequately with the laws of nature (e.g., friction, gravity, inertia). They must also makeenough infonnation available to the robot controller, either by sensing the environment or by reasoning about motion mechanics, or both, so that the successive states of the robot relative to its environment are reliably recognized. The first paper, Robot Algorithms, by Jean-Claude Latombe, takes the stand that, like computer science, robotics is fundamentally about algorithms. Robot alg~rithms,however, differ in significant ways from computer algorithms. Latombe's paper suggests that a unique characteristic of robot algorithms is how they combine a control component involving very basic control issues, such as controllability and observability, and a planning component raising fundamental computational issues, such as calculability and complexity. The second paper, Motion Planning for MobileRobot.!: From Academic to Practical Issues, by Jean-Paul Laumond, investigates in more detail the relationship between controllability and complexity for one particular class of robots: the mobile robots. Laumond stresses the difference between holonomic motion planning, which essentially lies in the realm of computational geometry and can now be solved efficiently, and nonholonomic motionplanning, which also raises control theory issue. This comparison illuminates the relation between controllability and motion planning complexity. The third paper, Towards a Theory of Information Invariants for Cooperating Autonomous Mobile Robot.!, by Bruce Donald, James Jennings, and Daniela Rus relates to the observability issue in robot algorithms. More specifically, it considers cooperating robotspushing large, heavy objects. Donald, Jennings, and Rus develop "information invariants" that make it possible to establish some explicit trade-of equivalence between

the internal state retained by each robot, communication among robots, sensory information, and information derived from task mechanics. The fourth paper, Feeding and Sorting Algorithms for the Parallel·law Gripper, by KenGoldberg, explores algorithms to orient and recognize parts with a paralleljaw gripper equipped with a passive translating bearing. The algorithm orienting parts uses information derived from task mechanics to iteratively reduce the set of possible orientations of a part. Part recognition uses a lowcost linear sensor. Goldberg's work is a good demonstration that neatly designed robot algorithms may yieldefficient and cost-effective hardware implementation. The fifth paper, A Safe Swept Volume Method for Collision Detection, by Andre Foisy and Vincent Hayward, addresses a basic problem in most motion planners, namely collision detection. Foisy and Hayward propose an elegant algorithm that detects collision along a given robot path in a given environment. The algorithm is both safe - it neverclassifies a subset of the path as collision-free if it isn't - and reliable - if enough time is available, it computes the colliding subsets of a path with arbitrary precision. These papers illustrate some of the major trends in motion planning research over the past few years. In particular, motion planning has evolved from the pure geometric problem of finding collision-free paths in known...