Motion Planning for Closed Chain Systems | Algorithms & Applications Group

Algorithms & Applications Group
Motion Planning for Closed Chain Systems

Motion Planning for Closed Chain Systems
supported by NSF, Texas Higher Education Coordinating Board
Xinyu Tang, Shawna Thomas, Nancy Amato
Project Alumni: Li Han, Dawen Xie

Closed chain systems are involved in many applications in robotics and beyond, such as the Stewart Platform, parallel robots, closed molecular chains, animation, reconfigurable robots, and grasping for single and multiple robots. However, motion planning for closed-chain systems is particularly challenging due to additional constraints, called closure constraints , placed on the system. Using only the traditional joint angle representation, it is extremely difficult to randomly sample a set of joint angles that satisfy the closure constraints since the probability that a random set of joint angles lies on the constraint surface is zero. In our initial work, we proposed a two-stage kinematics-based probabilistic roadmap (KBPRM) to sample closed configurations using inverse kinematics. Later on we augemented this method to handle higher DOF problems by iteratively relaxing constraints (IRC) . In our most recent work, we propose a reachable-distance based prepresentation of the closed-chain systems, which enables us to sample directly in the subspace subspace where closed constraints are satisfied.

Using Inverse Kinematics to Handle Closure Constraints (KBPRM)

In our initial work, we proposed a two-stage kinematics-based probabilistic roadmap (KBPRM) planner for closed chains. In the first stage, we build a (small) kinematic roadmap that deals solely with the robot's kinematics and utilizes both forward and inverse kinematics in its construction. In the second stage, the environment is populated with copies of the kinematic roadmap, and rigid body connections are made between nodes with the same closure type. Both stages employ PRM planners to construct their roadmaps. Our experimental results indicate that the use of kinematics to guide the generation and connection of closure configurations is very beneficial, both reducing the computation costs and improving the connectivity of the resulting roadmap as compared to previous purely randomized approaches.

The example linkage has two kinematics loops and there are 12 links in total. The movie shows rigid body movement between configurations with same closure type and transformation between closed configurations without translating the linkage.
Movie: a 2-loop linkage (mpg 1.3MB)

Handle High DOF Problems by Iteratively Relaxing Constraints (IRC)

The efficiency of KBPRM depends critically on how the linkage is partitioned into open chains. The original method assumed the Partition was provided as input to the problem. In the extended work, we proposed a fully automated method for partitioning an arbitrary linkage into open chains and for determining which should be positioned using the inverse kinematic solver. Even so, the size (number of links) of the closed loops that can be handled by this method is limited because the inverse solver can only be applied to small chains. To handle high DOF closed loops, we show how we can use the Iterative Relaxation of Constraints (IRC) strategy to efciently handle large loops while still only using inverse kinematics for small chains.

Luxo is lamp made up by a 3-loop linkage and an adjustable head. Our planner can find the path to ajust the lamp from a given start posture to a given end posture.
Movie: Luxo (mpg 1.1MB)

A single loop with 98 links. The movie shows the transformation between two configurations.
Movie: a 98-link linkage (mpg 1.1MB)

See IRC project webpage for more information about Iterative Relaxation of Constraints (links to Dr. Bayazit's web page).

Fast Enforcement of Closure Constraint Using Reachable Distances

Instead of randomly sampling in the joint angle space to find closed configurations, we overcome this challenge by precomputing the subspace where closed constraints are satisfied and then directly sampling in this subspace. We represent the chain as a hierarchy of sub-chains by recursivly breaking down the problem into smaller subproblems. Each sub-chain in the hierarchy may be partitioned into other, smaller sub-chains forming a closed loop. For any sub-chain, we can compute the attainable distance (reachable distance or length) between its two endpoints recursively. Instead of randomly sampling in the joint angle space, we recursively sample in the reachable distance space. This provides distinct advantages over traditional approaches:

joint angles are quickly and easily calculated using basic trigonometry relationships instead of using more expensive inverse kinematics solvers
configurations are guaranteed to satisfy closure constraints

Our method can be used to significantly improve the performance of sampling-based planners for closed-chain systems such as Probabilistic Roadmap Methods (PRM) and Rapidly-Exploring Randomized Trees . We provide the necessary motion planning primitives (namely sampling and local planning) to implement most sampling-based motion planners. Our experimental results show that our method is fast and efficient in practice making sampling configurations with closure constraints comparable to sampling open chain configurations that ignore closure constraints entirely. It is easy to implement and general. It is also extendible to more distance-related constraints besides the ones demonstrated here.

	A grasping experiment where 2 articulated arms collaborate to grasp an object and transport it from one end of the environment to the other. Each arm is composed of 3 links with variable lengths. Movie: Two Arms Collaboration (mpg 0.5MB)
	A fixed-base 20 link closed chain in an environment without obstacles. The links have variable lengths. The chain (red) travels from the start (green) to the goal (orange). Movie: 20 Links (mpg 0.3MB)

Papers

Planning with Reachable Distances: Fast Enforcement of Closure Constraints, Xinyu Tang, Shawna Thomas, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 2694-2699, Rome, Italy, Apr 2007. Also, Technical Report, TR06-008, Parasol Laboratory, Department of Computer Science, Texas A&M University, Sep 2006.
Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)

Efficient Planning of Spatially Constrained Robots Using Reachable Distances, Xinyu Tang, Shawna Thomas, Nancy M. Amato, Technical Report, TR07-001, Parasol Laboratory, Department of Computer Science, Texas A&M University, Jan 2007.
Technical Report(ps, pdf, abstract)

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)

A Kinematics-Based Probabilistic Roadmap Method for High DOF Closed Chain Systems, Dawen Xie, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 473-478, New Orleans, LA, Apr 2004. Also, Technical Report, TR03-007, Parasol Laboratory, Department of Computer Science, Texas A&M University, Nov 2003.
Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)

A Kinematics-Based Probabilistic Roadmap Method for Closed Chain Systems, Li Han, Nancy M. Amato, In Proc. Int. Wkshp. on Alg. Found. of Rob. (WAFR), pp. 233-246, Hanover, NH, Mar 2000.
Proceedings(ps, pdf, abstract)

Department of Computer Science | Dwight Look College of Engineering | Texas A&M University
Privacy statement: Computer Science Engineering TAMU

	Luxo is lamp made up by a 3-loop linkage and an adjustable head. Our planner can find the path to ajust the lamp from a given start posture to a given end posture. Movie: Luxo (mpg 1.1MB)
	A single loop with 98 links. The movie shows the transformation between two configurations. Movie: a 98-link linkage (mpg 1.1MB)