Extracting paths from fields built with linear interpolation

Algorithms such as Field-D* use linear interpolation to infer continuous fields of costdistance-to-goal, where costdistance is cost integrated over distance. Traditionally, field values have been used as direct input to trajectory planners. In contrast, we focus on extracting a minimum costdistance path between two points, given the continuous field. We identify a suboptimal phenomenon that occurs when standard path extraction techniques are used on linearly interpolated quantity-to-goal fields. The phenomenon causes paths to drift sideways toward their horizontal or vertical bounds, resulting in increased path length and unnecessary turns. We find that the sub-optimality is a mathematical consequence of the linear interpolation used to create the costdistance-to-goal field. We present a possible improvement that calculates path segment directions using an interpolation between the costdistance-to-goal gradient vectors, and perform a series of experiments comparing this method with the current state-of-the-art. We find that the proposed method can achieve a significant reduction in path length error, and we provide discussion and examples of when it should and should not be used.