Fast medial-axis approximation via Max-Margin pushing

Abstract

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.