Home research People General Info Seminars Resources Intranet
| Algorithms & Applcations Group | Home | Research | Publications | People | Resources | News
Algorithms & Applications Group
Iterative Relaxation of Constraints

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 collision-free.

There are two benefits to this approach. First, in many cases relaxing the feasibility constraints increases the relative volume of the free C-space, 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 C-space in which to focus the search for a solution to the original problem.

Original Problem

Relaxed Problem

Approximate Solution to Relaxed Problem

Solution to 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 9-98 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 original-sized robot is found by repeatedly increasing the robot size and fixing any resulting problems in the path for the new robot size.

  • Feasibility Criteria: This is the depth the original robot is allowed to penetrate into an obstacle. The smaller the current robot, the larger the permitted penetration of the original robot.
  • Approximate Solution: The path for the smaller robot.
  • Improving the Approximate Solution: A valid path for the smaller robot may not be valid for the larger version because some configurations in the path may be in collision. We improve the path by (i) identifying invalid path configurations, (ii) replacing each invalid path segment with nearby valid configurations found by some local search method, (iii) attempting connections that repair the damaged path segments and if not possible, then generating additional configurations that can be used to do so.

Rigid Body Tunnel. For rigid body experiments, we keep the obstacles the same but scale the robot size from 1.0x (base/original model) to 1.1x, 1.2x, 1.3x, and 1.4x. IRC starts with the base model and the robot gets progressively bigger. As the size of the robot increases, sampling in the tunnel becomes harder.

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 C-space 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.

  • Feasibility Criteria: The number of links is the feasibility criteria.
  • Approximate Solution: A valid path for a robot with fewer links.
  • Improving the Aproximate Solution: The approximate solution is for a robot with smaller dof. To improve it, we first need to transform it into a set of configurations compatible with the current robot's dof. We do this by maintaining the parameters for the existing dofs and finding values for the new (extra) dofs. There are many ways to do this. We found that assigning random values to the new links worked well. After the path is applicable to the current robot (using all its dof), we can apply the same strategy as in the rigid body case for fixing invalid segments.

Walls with Open Chain. For open chain experiments, we vary the number of links from 2 (7 dof) to 19 (24 dof). IRC starts with 2 links as the base model and iteratively adds links. We stop experimenting with OBPRM past 7 links since the planner becomes inefficient after that.

An interesting observation is that an approximate solution may require dramatic adjustment for harder versions. We see this when going from the 13-link version to the 14-link version. After the 14-link version, improvement time becomes linear again. This suggests that the solution to the 13-link version is not easily applicable to the 14-link 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.

Original closed chain (black) has been relaxed by identifying pivots and connecting them with virtual links (red).

  • Feasibility Criteria: The number of links is the feasibility criteria.
  • Approximate Solution: A valid path for the virtual closed chain.
  • Improving the Aproximate Solution: To expand the approximate solution, we need to generate joint angles between two consecutive pivots. Since the portion of the chain between them is itself a closed chain, another application of KBPRM can be used.

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 77843-3112 
parasol-admin@cse.tamu.edu      Phone 979.458.0722     Fax 979.458.0718 

Department of Computer Science and Engineering | Dwight Look College of 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