Home research People General Info Seminars Resources Intranet
| Alg & App Group| Home | Research | Publications | People | Resources | News

Algorithms & Applications Group
Motion Planning for Constrained Systems

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


Constrained motion planning problems are problems where a set of constraints are placed on the motion of a robot. These constraints could require that parts of the robot such as the end effector occupy a specified subset of the workspace. They could also require that certain joints of the robot remain in contact with each other (e.g., closed chains). Motion planning with constraints has many applications, including the Stewart Platform, parallel robots, closed molecular chains, animation, reconfigurable robots, and grasping for single and multiple robots.

Constrained problems are particularly challenging because they require that the robot satisfy a problems constraints in addition to an validity conditions associated with the problem. In many problems these constraints require that a part of the robot such as its end effector be located at a single point or along a manifold. In these problems traditional motion planning methods will fail because probability of generating a sample which satisfies these constraints is zero. We address this problem by developing a set of specialized sampling methods that can generate samples which satisfy constraints. These samplers can be used in combination with existing motion planning methods to solve problems with constraints.

In our initial work, we proposed a two-stage kinematics-based probabilistic roadmap (KBPRM) to sample closed configurations using inverse kinematics. We then augemented this method to handle higher DOF problems by iteratively relaxing constraints (IRC) . Later we proposed a reachable-distance based prepresentation of the constrained systems, which enables us to sample directly in the subspace subspace where constraints are satisfied. In our most recent work we proposed reachable-volumes which computes the region of space that joints of a robot can occupy while satisfying constraints, then places the joints in these regions to generate samples that satisfy the constraints. Reachable volumes generalizes reachable distance to applicable to robots with 3-dimensional spherical joints as well as to robots with combinations of spherical, planar and prismatic joints.

The KBPRM, IRC, Reachable Distance and Reachable Volume methods are discussed in more detail below.

Sampling Based Motion Planning With Reachable Volumes

In the reachable volumes project we explore the regions of space that the joints and end effectors of a robot can reach. We present a method for computing reachable volumes which is applicable to unconstrained systems as well as systems with joint closure constraints and constraints on the position of the joints and end effectors of the robot. This method is applicable to high dof linkages, closed chains and tree-like robots and can be applied to robots that include spherical, prismatic and planar articulated joints (and combinations thereof). Reachable volume can be used to guide robot design and can assist in robot operation by allowing the operator to see what portions of the robot can reach.

We also present a family of samplers that use reachable volumes to generate samples for a wide variety of motion planning problems. We show that these methods can be applied to problems with as many as 256 degrees of freedom and to robots that include combinations of spherical, prismatic and planar articulated joints. We also show that it can be applied to problems that include end effector constraints, closure constraints and constraints on the position of the joints of the robot.


The reachable volumes of a 16 dof fixed-base grasper with spherical joints is affected by constraints placed either on the end effectors or on the base. The reachable volume of the base (teal) given constraints on the end effectors to grasp a cubic object (blue and green). The reachable volumes of a 16 dof fixed-base grasper with spherical joints is affected by constraints placed either on the end effectors or on the base. The reachable volume of the base (teal) given constraints on the end effectors to grasp a cubic object (blue and green).


The reachable volume of the base of a WAM robot grasping a spherical object. In order to reach the object, the elbow joint must be located in the purple region (right), the second arm joint must be located in the light blue region(center) and the wrist of the grasper must be located in the green region(left). The reachable volumes of the knuckle joints and the object being grasped are not visible because they are contained in the reachable volume of the wrist. This robot has 15 dofs and includes both spherical and planar joints. An example configuration is shown in gray.


Generating a sample for a 6 link grasper whose end effectors are constrained to be located in the red and green regions.


In this video we define reachable volumes and show how they are computed. We also show visualizations of the reachable volumes for a number of example robots.
Movie: Sampling Based Motion Planning with Reachable Volumes Part 1: Theoretical Foundations

In this video we show how the reachable volume sampler can be used to generate samples in a set of example environments.
Movie: Sampling Based Motion Planning with Reachable Volumes Part 2: Application to Manipulators and Closed Chain Systems

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:

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

Sampling-Based Motion Planning with Reachable Volumes: Theoretical Foundations, Troy McMahon, Shawna L. Thomas, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), Hong Kong, China, May 2014.
Proceedings(pdf, abstract)

Sampling Based Motion Planning with Reachable Volumes, Troy McMahon, Shawna L. Thomas, Nancy M. Amato, Technical Report, TR14-003, Parasol Laboratory, Department of Computer Science, Texas A&M University, Feb 2014.
Technical Report(pdf, abstract)

Reachable Distance Space: Efficient Sampling-Based Planning for Spatially Constrained Systems, Xinyu Tang, Shawna Thomas, Philip Coleman, Nancy M. Amato, International Journal of Robotics Research, 29(7):916-934, Jun 2010.
Journal(pdf, abstract)

Planning with Reachable Distances, Xinyu Tang, Shawna Thomas, Nancy M. Amato, In Proc. Int. Wkshp. on Alg. Found. of Rob. (WAFR), Guanajuato, Mexico, Dec 2008.
Proceedings(ps, pdf, abstract)

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.
Proceedings(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)



Parasol Home | Research | People | General info | Seminars | Resources  

Parasol Lab, 301 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 77843-3112 
Contact Webmaster      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