SEECS Colloquium

Motion planning arises in many application domains such as computer animation (digital actors), mixed reality systems and intelligent CAD (virtual prototyping and training), and even computational biology and chemistry (drug design). Surprisingly, a single class of planners, called probabilistic roadmap methods (PRMs), have proven effective on problems from all these domains. Strengths of PRMs are simplicity and efficiency, even in high-dimensional configuration spaces. Although these new methods are powerful, they may fail in environments where the solution path requires the robot to pass through a narrow passage.

In the first part of the talk, we suggest a hierarchical strategy addressing this problem where we first simplify the problem by relaxing some feasibility constraints, solve the easier version of the problem, and then use that solution to help find a solution for the harder problem. We will show how this strategy can be applied to various domains with different types of robots, including: (i) "virtual prototyping" design where the goal is to find a removal path for one part (the robot) from an assembly of other parts (obstacles), (ii) "ligand binding" where we generate binding sitecandidates for a ligand (drug molecule) in a large protein molecule, and (iii) "deformable objects" where a robot will deform to avoid the collisions while following a path.

In the second part of talk, we describe recent work for planning sophisticated group behaviors. In this work, we investigate how the addition of global information in the form of a roadmap of the environment enables more sophisticated flocking behaviors for homing, exploring and shepherding behaviors.

Osman Burchan Bayazit received his BS in Computer Engineering from Middle East Technical University, Ankara, Turkey and his MS in Computer Science from Texas A&M University. He is currently a PhD candidate at Texas A&M and plans to graduate in summer 2002. More information, including current projects, papers, and a poster for the first part of this talk, can be found at http://www.cs.tamu.edu/people/burchanb/