Minkowski Sum Based (M-Sum) Motion Planner
Jyh-Ming Lien
Overview
In this work, we provide an investigation to the following question: Is there a motion planner that behaves like a deterministic planner for lower dimensional motion planning problems and behaves like a probabilistic planner for higher dimensional problems? Such a planner should have the advantages of both deterministic and probabilistic motion planners. Our strategy to achieve this goal is to use Minkowski sum of the robot and the obstacles in workspace. Our experimental results show that our new method, called M-sum planner, which uses the geometric properties of Minkowski sum to solve motion planning problems, is at least 10 times more efficient than the Probabilistic Roadmap Methods (PRMs) and its variants in all the examples studied.Full Text
DOWNLOADPublications
Hybrid Motion Planning Using Minkowski Sums, Jyh-Ming Lien. Proceedings of the Robotics: Science and Systems Confrence (RSS), Zurich, Switzerland. June 2008.Hybrid Motion Planning Using Minkowski Sums, Jyh-Ming Lien, Proceedings of Robotics: Science and Systems IV, June 2008
BibTeX
BibTeX
Benefits
- M-sum planner reuses configurations
- M-sum planner separates the translational and rotational motions
- M-sum planner connects the configurations generated using Minkowski sum more efficiently
Software and Examples
- Source code is available (please send requests to: jmlien@cs.gmu.edu)
- An output example of our program is shown below
- An example with a 10 DOF articulated robot. (Start and goal configurations are shown in red and green, respectively.)
- A roadmap generated using Gaussian PRM with 2000 nodes using d=0.1. Even though you can see that there are more configurations around the obstacle, the distribution of the configurations is too scattered.
- A roadmap generated using Gaussian PRM with 2000 nodes using d=0.001. Even though we pick a much smaller d, the distribution of the configurations is still scattered. (Note: We found this scatteredness has little to do with the value of d. The scatteredness is mainly due to the fact that Gaussian PRM samples around C-obsts that are induced by robot self-collision.)
- An roadmap generated using M-sum planner with 2000 nodes. Note that we do not have to specify any parameters and the configurations are very close to the obstacles, thus to the narrow passage.
- A path found using the roadmap above
Related Work
- Point-based Minkowski Sum
- Gaussian Sampling for Probabilistic Roadmap Planners by Boor et al.
- Obstacle-Based PRM by Amato et al. at Parasol Lab
List of MASC Research Pages