Constraint-Based Motion Planning for Virtual Prototyping
	Maxim Garber	garber@cs.unc.edu
	Ming C. Lin	lin@cs.unc.edu

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.

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.

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.