Sampling-Based Motion Planning Lecture

In the lecture "Sampling-Based Motion Planning: from Intelligent CAD to Crowd Simulation to Protein Folding" here at Clemson, Dr. Nancy Amato of Texas A&M presented improvements to Probabilistic Roadmap Methods (PRM) for solving motion planning problems.

The problems that Dr. Amato described are all set in a n-dimensional Constraint Space (C-Space), where each constraint is one dimension. This could be as simple as a set of Cartesian coordinates or as complicated as bond angles between each carbon in a protein. The motion of the actor within its C-Space is determined by the presence of C-Obstacles, places where the actor cannot move in the C-Space.

PRMs build a set of possible routes through a C-Space by

1. Randomly generating a list of points in the C-Space and discarding invalid points (i.e. those within a certain proximity of an obstacle)
2. Connecting each remaining point to all other points and discarding any invalid connection

PRMs generate the path before the actor even begins moving, making querying paths a matter of looking up results instead of calculating them at the time of the query. Dr. Amato claimed that these methods are probabilistically complete and easily applied to high-dimensional spaces. The major drawback, though, comes from the fact that points are sampled randomly: it is unlikely that the actor will find a path through narrow passages.

The problem, then, is finding ways to sample nodes close to obstacles so that actors may better traverse narrow passages. PRMs that attempt to solve the problem in this way are called Obstacle-Based PRMs (OBPRM). The idea here is to

1. Find a point in an obstacle
2. Select a random direction
3. Find a free point in that direction
4. Determine the the boundary between the obstacle and the free point

The second problem is efficiency of mapping. By the nature of their design, PRMs are relatively easily parallelized at each stage, boosting their efficiency. In the case of moving constraints, PRMs must redo the entire pathfinding process for each distinct configuration of the C-Space. In this case, it is more efficient to repair approximate paths instead of redoing the entire pre-query stage.

In some cases, efficiency can be improved using hybrid human/planner systems in which a human agent traces a path through the space and the planner uses that path data to make decisions. The given example of this system had the human agent trace a path on a haptic device, then the path was passed to the planner. Dr. Amato's group used these systems in CAD designs and deformable object modelling, but she noted that this is only useful when the solution is fairly obvious to humans.

PRMs are also used to aid flocking (coordinated) behavior by helping individual members of the flock to find a path. Dr. Amato's group successfully applied this system to architectural problems.

The most interesting application (thanks to my bias toward biological applications of computing) was protein-folding modelling. While computers have successfully been used to determine the normal state of a protein for some time, they only look at the final state and not how the protein folded into that state. PRMs can model the actual folding process to show how a protein reaches its normal state. The presentation had some of the data from these experiments, and it looked promising, though I can't say I know enough about the results to talk about them in detail.

Overall, PRMs are an interesting concept. Randomness and probability in computing have always interested me because they allow for degrees of flexibility that rigidly logical systems do not provide and make behavior more realistic. These concepts are not necessarily useful in every case, but they provide an alternate way of thinking about how we solve problems that breaks out of the computer science shell.