Background

Motion planning is a fundamental problem in robotics. The problem can be stated as finding a path for a robot, such that the robot can move along this path from its initial configuration to goal configuration without intersecting with any obstacle in the scene. Motion planning methods have been widely applied for robotics, computed aided design, bioinformatics and many other fields.

We are developing efficient and practical algorithms for complete motion planning. A complete motion planner either computes a collision-free path from the initial configuration to the final configuration or concludes that no such path exists.

Videos


*Find a path (video)*	*Path non-existence. Our algorithm only takes 3.356s to determine it. (Video)*

*Five gear example (video)*	*The collision-free path and a connectivity graph in the free space of the robot's 3 dimensional C-space.*

Publications

*C-DIST: Efficient Distance Computation for Rigid and Articulated Models in Configuration Space* Liangjun Zhang, Young J. Kim, Dinesh Manocha ACM Solid and Physical Modeling Conference (SPM07), 2007 Project Webpage Paper (.PDF 1.5M)
*A Hybrid Approach for Complete Motion Planning* Liangjun Zhang, Young J. Kim, Dinesh Manocha IEEE/RSJ International Conference On Intelligent Robots and Systems (IROS), 2007 UNC-CS Tech Report 06-022, 2006 PDF (1M); VIDEO 1(MPEG, 5M); VIDEO 2(AVI, 18M)
		*A Simple Path Non-Existence Algorithm Using C-obstacle Query* Liangjun Zhang, Young J. Kim, Dinesh Manocha The Seventh International Workshop on the Algorithmic Foundations of Robotics (WAFR), 2006, PDF (1M)
	*Fast C-obstacle Query Computation for Motion Planning* Liangjun Zhang, Young J. Kim, Gokul Varadhan, Dinesh Manocha IEEE International Conference on Robotics and Automation (ICRA), 2006, 3035-3040 PDF(1.4M) ICRA Presentation(1.1M)
	*Topology Preserving Free Configuration Space Approximation* Gokul Varadhan, Young J. Kim, Shankar Krishnan, Dinesh Manocha IEEE International Conference on Robotics and Automation (ICRA), 2006 PDF(1M)
	*Star-shaped Roadmaps - A Deterministic Sampling Approach for Complete Motion Planning* Gokul Varadhan, Dinesh Manocha Robotics: Science and Systems 2006 Project WWW Page
	*Generalized Penetration Depth Computation* Liangjun Zhang, Young J. Kim, Gokul Varadhan, Dinesh Manocha ACM Solid and Physical Modeling Conference (SPM06), 2006, 173-184 Project WWW page

Related Work

Efficient Approximate Algorithms for Boolean Operations, Motion Planning, Sweeps, and Minkowski Sum: Project WWW page