
Project Personnel:Nancy Amato
We present a hierarchical strategy called Iterative Relaxation of Constraints (IRC) for addressing the narrow passage problem. We first simplify the problem by relaxing some feasibility constraints, solve the easier version of the problem, and then use that solution to help us find a solution for the harder problem. For example, we might first find a path that allows small collisions and then iteratively refine the path until it is collisionfree.
There are two benefits to this approach. First, in many cases relaxing the feasibility constraints increases the relative volume of the free Cspace, making the relaxed version easier to solve than the original version. Second, the solution path for the relaxed problem can be used to identify a smaller region of Cspace in which to focus the search for a solution to the original problem.
We show how this strategy can be applied to rigid bodies and to linkages with high degrees of freedom, including both open and closed chain systems. Experimental results are presented for linkages composed of 998 links. Although we use PRMs as the automated planner, the framework is general and can be applied with other motion planning techniques as well.
For rigid bodies, the size of the robot greatly affects the probability of finding a valid solution. Within the IRC framework, we should then reduce the robot's size and find a solution to this version of the problem. A solution path for the originalsized robot is found by repeatedly increasing the robot size and fixing any resulting problems in the path for the new robot size.
Even with a small change in robot size, OBPRM's speed dramatically changes while IRC stays nearly linear with the scale of the robot. Note that since the IRC solution for a given robot requires the solution with smaller versions of the robot first, the values for number of nodes and time are cummulative.
For an articulated robot with out closed chains, the number of links affects the probability of finding a valid solution as this directly changes the dimensionality of Cspace that must be searched. Hence, we find a solution for a robot with fewer links, and then gradually add links, fixing invalid configurations in the path, until a solution to the original problem is found.
An interesting observation is that an approximate solution may require dramatic adjustment for harder versions. We see this when going from the 13link version to the 14link version. After the 14link version, improvement time becomes linear again. This suggests that the solution to the 13link version is not easily applicable to the 14link version. Note that another execution would likely generate different adjustment characteristics (i.e., there is nothing particularlly specially about 13 or 14 links).
As in the open chain application, we reduce the difficulty of the problem by reducing the number of links in the chain. We do this by selecting some pivot joints in the original chain and fixing the joint angles between two consecutive pivots. Intuitively, this is similar to connecting consecutive pivots with virtual links to create a virtual closed chain. We use KBPRM to solve the problem for the virtual closed chain.
The results here are only for applying IRC to the node generation phase of KBPRM. While we do not yet find a solution path, note that generating valid closed chain configurations is a challenging problem in its own right. We consider chains with 9 to 26 links. Below are the results for attempting to generate 100 nodes.
Iterative Relaxation of Constraints: A Framework for Improving Automated Motion Planning, O. Burchan Bayazit, Dawen Xie, Nancy M. Amato, In Proc. IEEE Int. Conf. Intel.
Rob. Syst. (IROS), pp. 586  593, Edmonton, Alberta, Canada, Aug 2005.
Proceedings(ps, pdf, abstract)
Solving Motion Planning Problems by Iterative Relaxation of Constraints, Osman Burçhan Bayazit, Ph.D. Thesis, Department of Computer Science and Engineering, Texas A&M University, College Station, Texas, U.S.A., May 2003.
Ph.D. Thesis(ps, pdf, abstract)
Project Alumni:O. Burchan Bayazit,Dawen Xie
Parasol Home  Research  People  General info  Seminars  Resources Parasol Laboratory, 425 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 778433112 parasoladmin@cse.tamu.edu Phone 979.458.0722 Fax 979.458.0718 Department of Computer Science and Engineering  Dwight Look College of Engineering  Texas A&M University Privacy statement: Computer Science and Engineering Engineering TAMU Web Accessibility Policy and Law  Web Accessibility and Usability Standards  Contact Webmaster 