Background

motionplanning

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 have developed 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

	*Global Vector Field Computation for Feedback Motion Planning* Liangjun Zhang, Steven M. LaValle, Dinesh Manocha IEEE International Conference on Robotics and Automation (ICRA), 2009 Project Webpage Paper Videos
	*Efficient Cell Labelling and Path Non-existence Computation using C-obstacle Query* Liangjun Zhang, Young J. Kim, Dinesh Manocha The International Journal of Robotics Research, November/December 2008 vol. 27 no. 11-12 1246-1257 Paper
	*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 Paper (1M), WAFR Presentation (1.8M)
	*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

Related Work

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