Field D*: An interpolation-based path planner and replanner

We present an interpolation-based planning and replanning algorithm for generating direct, low-cost paths through nonuniform cost, grids. Most grid-based path planners use discrete state transitions that artificially constrain an agent's motion to a small set of possible headings (e.g. 0, pi/4, pi/2, etc). As a result, even 'optimal' grid-based planners produce unnatural, suboptimal paths. Our approach uses linear interpolation during planning to calculate accurate path cost estimates for arbitrary positions within each grid cell and to produce paths with a range of continuous headings. Consequently, it is particularly well suited to planning low-cost trajectories for mobile robots. In this paper, we introduce the algorithm and present a number of example applications and results.