|
Planning Algorithms: An important book goes from pixels to paper Steve Lavalle
Steve LaValle, a motion planning expert and robotics researcher, wrote a book over the course of ten years and gave it away-for free-over the Internet for the simple reason that he wanted to change how people think about planning algorithms. Now, that same book, called Planning Algorithms, has been released in a printed edition by Cambridge University Press. Its publication marks the first time that planning algorithms from robotics, AI, and control theory have been unified comprehensively and cohesively under one umbrella. One of the key ideas is that all planning problems with imperfect state information are unified under the study of information spaces. Planning algorithms are used to get a machine to make some sequence of decisions-to move a piano through a house without hitting something, to fly an aircraft over complicated terrain while identifying targets, or to play hide-and-seek with a robot. They are developed in robotics, AI, and control theory but with different goals. Robotics addresses the automation of mechanical systems that have sensing, actuation, and computational capabilities. Artificial intelligence considers achieving tasks modeled discretely, like solving puzzles, building a stack of blocks, or playing sequential games. Control theory concerns designing inputs to physical systems described by differential equations over continuous spaces. The research communities of robotics, AI, and control theory started on different problems, but they have been on a collision course over the past couple of decades. In each of these areas, many successes have led to widespread use of their techniques in industry. LaValle hopes that his book will play a role in uniting efforts among these now disparate groups and stimulate widespread, international interest in planning. Within AI, planning algorithms are the natural complement to machine learning, which has been a flourishing discipline over the past decade. Planning Algorithms was unveiled in May 2006 at the IEEE International Conference on Robotics and Automation. While not a math book, mathematical concepts are explained in its 826 pages. "Planning needs the right mathematical grounding and unification of discrete and continuous ideas," he said. The focus of the book is on algorithm issues related to planning. In robotics, motion planning algorithms generate useful motions by processing complicated geometric models. Within AI, systems use decision-theoretic models to compute appropriate actions. In the control theory world, algorithms compute feasible trajectories for systems, with some additional consideration of feedback and optimality. According to LaValle, all three areas fundamentally need algorithms that convert high-level specifications of tasks from humans into low-level descriptions of how to move or make decisions based on sensor information. The feedback LaValle has received for his online book has been overwhelming, with a worldwide audience that might not have been possible if the book was distributed only by traditional channels. The online book grew from course notes from classes he has taught since 1995. Currently, it is being downloaded at the rate of about 5,000 copies per month, from the U.S., China, and Europe to Africa, Australia, and Iran (ninth in number of downloads). "People can download it, and it's immediately in their hands. I've gotten hits from all over the world, including some really far-fetched places," he said. Perhaps LaValle's first graduate student from Fiji will be the result of the download he provided to a user in that country. "Professors want to have an impact," said LaValle. "Books these days are too expensive for most students, who are the most likely readers." The book, written primarily for computer scientists and engineers, will also appeal to those who work in computational biology, virtual prototyping, manufacturing, video game development, and computer graphics. It has been met with praise by his colleagues and has already been used in courses at California Institute of Technology, Carnegie Mellon University, Northwestern University, University of North Carolina, Utrecht University (Netherlands), and many others. It won't be long before it is available in translation in Japan, the world's powerhouse in robotics and mechanical system design. LaValle has worked in motion planning and robotics for most of his career. He has taught this material at Stanford University, Iowa State University, and the Tec de Monterrey before coming to the University of Illinois in 2001, where he is associate professor of computer science. LaValle's other projects include motion planning for closed chains (loops) and theory of computation for robots revolving around information sensing (most often used for humanoid robots). His RRT (Rapidly-Exploring Random Tree) algorithm, for searching high-dimensional spaces to solve multiple-dimension path planning problems, is used in research labs and industrial products around the world (see below). === RRT (Rapidly-Exploring Random Tree) Algorithm A more complex example of a motion planning problem, one that involves a differential or kinematic constraint, is how to get a car to parallel park itself. The wheels cannot move sideways, they can only turn and wiggle the car sideways. The car can go backwards and forwards, and certain speed must be maintained so the car doesn't hit anything. "It's a kind of search problem that involves applying various controls," said LaValle. "Probing and exploring a space is one thing. When momentum or dynamics are introduced is when trouble arises. In addition to computer science, we have to understand both dynamics and control theory." A solution to these kinds of problems can be found using Rapidly-Exploring Random Trees (RRTs), a method developed by LaValle, which is a data structure and algorithm designed to search high-dimensional spaces. It is constructed incrementally in a way that quickly reduces the expected distance of a randomly-chosen point to the tree. Unlike random walks, which suffer from a bias toward places already visited, an RRT is biased toward places not yet visited, resulting in a fast exploration or spread into the space it is searching. RRTs have been used in Mars exploration vehicles, humanoid robots, and many other robots. "With an independent parameter for every degree of freedom," explained LaValle, "quickly planning to get from point A to point B through a continuous space of transformations is a real accomplishment. We're not obsessed with finding an optimal path. We're happy to find a path at all." Written by Judy Tolliver, May 23, 2006
|
|