Complete Motion Planning

GAMMA Group

University of North Carolina at Chapel Hill

 

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 

two-gears-path

two-gears-no-path

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