Constraint-Based Motion Planning

Maxim Garber and Ming C. Lin

[ abstract | publications | performance timings | videos ]

Abstract

Motion planning is one of the key research challenges for design automation and rapid manufacturing using virtual environments. We present a novel framework for motion planning of rigid and articulated robots in complex, dynamic, 3D environments and demonstrate its application to virtual prototyping. It is based on transforming the motion planning problem into the simulation of a dynamical system. Motion of each rigid robot is subject to the influence of virtual forces induced by all type of geometric constraints. These may include constraints to enforce joint angle limit and connectivity constraints for articulated robots, constraints to enforce a spatial relationship between multiple collaborative robots, or constraints to have the robot follow an estimated path to perform certain tasks in a sequence. The resulting algorithm uses all contributing forces to move the robot along the estimated path, while avoiding collision with obstacles and enforcing joint and positional constraints. Our algorithm works well in dynamic environments with moving obstacles and is applicable to challenging planning scenarios where multiple robots must move simultaneously to achieve a collision free path. We demonstrate its effectiveness on parts removal, automated car painting, and assembly line planning.

Publications

Constraint-Based Motion Planning using Voronoi Diagrams
Maxim Garber and Ming C. Lin
Proc. Fifth International Workshop on Algorithmic Foundations of Robotics (WAFR), 2002 pdf(1.1M)

Constraint-Based Motion Planning for Virtual Prototyping
Maxim Garber and Ming C. Lin
Proc. ACM Symposium on Solid Model and Applications, 2002 (Poster) pdf(439k)

Performance Timings

We use a hardware accelerated distance field computation method [Hoff et al. 1999] to generate surface repulsion constraints for obstacle avoidance. We are continuing to work on other optimization to improve the hardware accelerated distance field computation and hierarchical culling for proximity queries. The current performance timings are shown below.
Scene	Polygons	Per Time Step	Total Time
Scene 1 - Maintainability Study	20470	0.093 sec.	67 sec.
Scene 2 - Automated Car Painting	25738	0.038 sec.	18 sec.
Scene 3 - Assembly Line Planning	16962	0.0085 sec.	16 sec.
Table 1. Benchmark timings in seconds for our three example scenes. Per Time Step: The average time for the planner to compute one time step of the simulation. Total Time: The total time taken for the planner to complete the planning task.

Videos

	Scene 1 - Maintainability Study View 1 (mpeg 8.4Mb) - View 2 (mpeg 8.1Mb) In assembly maintainability studies, motion planning is used to find whether it is possible to remove a particular part from an assembly, and if so, to find one possible removal path. In our example a bolt and a washer must avoid each other in the confines of tight compartment inside a pump assembly. The goal, to remove the bolt from the assembly, requires both objects to maneuver around each other without colliding.
	Scene 2 - Automated Car Painting View 1 (mpeg 3.2Mb) - View 2 (mpeg 3.1Mb) In this example an articulated robot arm is used to trace a path along the body of a car for painting. The robot is composed of rigid components that are held together by constraints. For all of the components of the robot, the planner must compute paths that satisfy the joint constraints, do not collide with the obstacles or the car, and lead the end effector along the prescribed path
	Scene 3 - Assembly Line Planning View 1 (mpeg 7.1Mb) - View 2 (mpeg 7.9Mb) In this example the robot arm must access a part moving past it on a conveyer belt. The factory floor contains a piping structure that is moving over the conveyer belt in the opposite direction to the part's movement. The moving obstruction causes the robot to reactively modify its path to avoid collision.

For more information please visit the University of North Carolina web page on Motion Planning and Constraint-Based Motion Planning.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.