Fast Medial Axis Approximation via Max-Margin Pushing

Guilin Liu and Jyh-Ming Lien


Maintaining clearance, or distance from obstacles and sampling efficient enough configurations on the medial axises are a vital component for successful motion planning. Maintaining high clearance often creates safer paths for robots. Having bias for sampling on medial axis also offers higher possibility to find a path in complex environment where the feasible configuration space only occupies a small proportion of the whole space. Inspired by the similarity between medial axis and max-margin scheme in optimization, especially in Support Vector Machine, we propose a new method to quickly construct the medial axis for the motion planning environment both in low and high dimensional space. However, directly applying the SVM classification on the large volume of uniformly sampled configurations suffers from huge computation and the medial axis is usually not the real medial axis due to SVMís optimization functionís tolerance to the mis-classification. Instead, we show a method that can quickly push any configuration to the medial axis by using the characteristics of the Max-Marginís optimization function. Experiments in low and high dimensional space and comparisons with other medial-axis motion planning algorithm are shown.


Fast Medial Axis Approximation via Max-Margin Pushing, Guilin Liu and Jyh-Ming Lien, IEEE/RSJ International Conference on Intelligent Robot and System (IROS), 2015
Web Site  / Paper(pdf) / BibTeX

IROS 2015 presentation
Method Overview



Video: Medial Axis via Max-Margin Pushing

Related Work/Links
Computer Science @ George Mason University