Hybrid Motion Planning Using Minkowski Sums

Probabilistic and deterministic planners are two major approximate-based frameworks for solving motion planning problems. Both approaches have their own advantages and disadvantages. In this work, we provide an investigation to the following question: Is there a planner that can take the advantages from both probabilistic and deterministic planners? Our strategy to achieve this goal is to use the point-based 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, provides advantages over probabilistic or deterministic planners. In particular, M-sum planner is significantly more efficient than the Probabilistic Roadmap Methods (PRMs) and its variants in all the examples studied in this paper.