Differential A*: an adaptive search method illustrated with robot path planning for moving obstacles and goals, and an uncertain environment

摘要

Differential A* is presented. It is a method that builds on the A*/configuration-space approach to adapt quickly to changes in the space by determining and updating the localized regions affected by those changes rather than regenerating the entire space. This is particularly effective with moving obstacles or goals and in an uncertain environment because only small parts of the space are affected at a time. This technique can provide significant speed improvements over, with the same desired results, as complete space regeneration. The A* search algorithm and its relationship to the configuration space method of path planning are presented. The connection of A* to wave propagation in configuration space for path planning is described. The differential A* method is outlined, with the focus on path planning. Examples of moving obstacles and goals and planning in an uncertain environment are presented.