Motion planning arises in many application domains such as computer animation (digital actors), artificial life (group behaviors), 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. Nevertheless, PRMs are not as effective in environments where the solution path requires the robot to pass through a narrow passage and they have not been used for multiple robots. 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 (i) "virtual prototype" analysis, where the goal is to find a removal path for one part (the robot) from an assembly of other parts (obstacles), (ii) "drug design," where we generate candidate binding sites for a ligand (drug molecule) in a large protein molecule, and (iii) "deformable objects," where the robot can deform itself to avoid collision while following a path. In the second part of talk, we describe recent work for planning sophisticated group behaviors using dynamic roadmaps. 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 such as homing, exploring, and shepherding. We also show that agent behavior can be regionally customized by annotating the roadmap with rules.

DATE: March 12, 2003, Wednesday @ 15:40
PLACE: EA-409