Premium
Using interpolation to improve path planning: The Field D * algorithm
Author(s) -
Ferguson Dave,
Stentz Anthony
Publication year - 2006
Publication title -
journal of field robotics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.152
H-Index - 96
eISSN - 1556-4967
pISSN - 1556-4959
DOI - 10.1002/rob.20109
Subject(s) - motion planning , grid , interpolation (computer graphics) , algorithm , path (computing) , computer science , range (aeronautics) , occupancy grid mapping , mathematical optimization , implementation , set (abstract data type) , any angle path planning , resolution (logic) , mobile robot , robot , motion (physics) , mathematics , artificial intelligence , engineering , geometry , programming language , aerospace engineering
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” 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 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.