Iterative Relaxation of Constraints (IRC) is a hierarchical strategy for solving motion planning problems. It is particularly well suited for the notoriously difficult `narrow passage' problems. It works by first simplifying the problem by relaxing some feasibility constraints, solving the easier version of the problem, and then using that solution to help 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 major 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
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.
IRC for Rigid Bodies
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.
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.
IRC for Open Chain Systems
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.
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.
Related Publications
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. DOI: 10.1109/IROS.2005.1545045 @INPROCEEDINGS{1545045, This paper presents a technique for improving the efficiency of automated motion planners. Motion planning has application in many areas such as robotics, virtual reality systems, computer-aided design, and even computational biology. Although there have been steady advances in motion planning algorithms, especially in randomized approaches such as probabilistic roadmap methods (PRMs) or rapidly-exploring random trees (RRTs), there are still some classes of problems that cannot be solved efficiently using these state-of-the-art motion planners. In this paper, we suggest an iterative 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 us find a solution for the harder 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.
Keywords: Computational Biology, Sampling-Based Motion Planning, Virtual Reality
Links : [Published] BibTex
author={O. B. {Bayazit} and {Dawen Xie} and N. M. {Amato}},
booktitle={2005 IEEE/RSJ International Conference on Intelligent Robots and Systems}, title={Iterative relaxation of constraints: a framework for improving automated motion planning},
year={2005},
volume={},
number={},
pages={3433-3440},
doi={10.1109/IROS.2005.1545045}}Abstract