Can We Get There Faster: Tuning Sample-Based Path Planners

Abstract

Sample-based path planners (SBPs) must balance sampling time and path optimality in complex domains. Without an adequate balance, SBPs will either take too long sampling or return a path with too much excess path length (EPL). Knowing and exploiting the relationship between sampling and EPL enables faster convergence to the optimal path. However, most models of this relationship are either overly restrictive or rely on indirect representations of EPL. We show a useful, direct relationship between the number of samples and EPL in the presence of sparse obstacles is a probability distribution function consisting of a binomial expansion of gamma distributions. Using simulations of SBPs, we show our proposed distribution is able to infer planner parameters from empirical data. We also present an algorithm that uses our distribution to improve the convergence of SBPs. Simulations show our algorithm reduces median path length by approximately 10% in higher dimensions without significantly reducing success rate.