We present an interpolation-based planning and replanning algorithm for generating low-cost paths through uniform and nonuniform resolution 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, /4 , /2, etc.͒. As a result, even "optimal" gridbased 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 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 a version of the algorithm for uniform resolution grids and a version for nonuniform resolution grids. Together, these approaches address two of the most significant shortcomings of grid-based path planning: the quality of the paths produced and the memory and computational requirements of planning over grids. We demonstrate our approaches on a number of example planning problems, compare them to related algorithms, and present several implementations on real robotic systems.
Ferguson et al. REF introduced Field D* algorithm that used linear interpolation during planning to compute approximate path cost estimates for arbitrary positions within each grid cell and generate paths with a series of continuous courses.
Using interpolation to improve path planning: The Field D* algorithm
Journal of Field Robotics
Computer Science