MPK - Motion Planning Kit


Motion Planning Kit (MPK) is a C++ library and toolkit for developing single- and multi-robot motion planners. It includes SBL, a fast single-query probabilistic roadmap path planner.

MPK can handle arbitrary kinematic tree structures and an arbitrary number of robots and obstacles at the same time. New robots with any combination of prismatic and revolute joints can be defined and added without recompiling.

The salient feature of MPK is an exact yet fast dynamic collision checker for straight-line segments in configuration space that can handle models of realistic complexity. While other collision checkers used in motion planners discretize motions with a fixed c-space resolution, which requires tedious parameter tuning and may still result in missing collisions, MPK's collision checker is guaranteed not to miss collisions even if the objects are very thin. At the same time, it is efficient by dynamically adapting the resolution locally to the 'difficulty' of the collision check. The only parameter of the checker is a minimum workspace clearance between objects which can usually be set to a constant value for all kinds of planning problems. What distinguishes MPK's collision checker from other exact collision checking approaches is that it combines a greedy approach to quickly identify collisions with a distance-based scheme to correctly prove segments collision-free.

Recently GREEDY-MGP, an efficient multi-goal tour planner for robot arms, has been incorporated into MPK. It can be used in spot-welding, car painting, inspection, and measurement tasks, where the robot must determine an optimal tour and a collision-free path through multiple goals. The multi-goal motion planning problem combines the classical traveling-salesman problem and the shortest collison-free path-planning problem (details).




Motion Planning, Path Planning Software, Probabilistic Roadmaps, SBL, Dynamic Collision Checking
Last modified: Wed May 07 12:22:19 PST 2006