DIFFERENTIAL A*: AN ADAPTIVE SEARCH METHOD ILLUSTRATED WITH ROBOT PATH PLANNING FOR MOVING OBSTACLES AND GOALS, AND AN UNCERTAIN ENVIRONMENT

Abstract

The robot path planning problem involves planning optimal paths for a robot to follow while ensuring it will not hit any obstacles or itself. In a state or perfectly known world, this has been addressed using the configuration space representation and the A* search algorithm. However, when movement, changes, or unexpected obstacles occur in the environment, a new method, Differential A*, can adapt the solution to the current situation. It updates only the fraction of space that is critically affected. This technique can provide significant speed improvements, with the same desired results, compared to complete space regeneration.