EIA-9975018, EIA-0103742, EIA-9805823, ACR-0113971, CCR-0113974, EIA-9810937, EIA-0079874 and by the Texas Higher Education Coordinating Board grant ATP-0005120261-2001. Some of this work was performed when Bayazit was with the Parasol Lab and his work was supported in part by the Turkish Ministry of Education. Iterative Relaxation of Constraints: A Framework for Improving Automated Motion Planning* *This research supported in part by NSF Grants ACI-9872126

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. 2005 IEEE.

Overview