Homotopy based optimal configuration space reduction for anytime robotic motion planning

Anytime sampling-based motion planning algorithms are widely used in practical applications due to limited real-time computing resources. The algorithm quickly finds feasible paths and incrementally improves them to the optimal ones. However, anytime sampling-based algorithms bring a paradox in convergence speed since finding a better path helps prune useless candidates but also introduces unrecognized useless candidates by sampling. Based on the words of homotopy classes, we propose a Homotopy class Informed Preprocessor (HIP) to break the paradox by providing extra information. By comparing the words of path candidates, HIP can reveal wasteful edges of the sampling-based graph before finding a better path. The experimental results obtained in many test scenarios show that HIP improves the convergence speed of anytime sampling-based algorithms.