Artificial Intelligence for Robotics

D* (D-Star or Dynamic A*)

Earlier in the chapter, I talked about a priori knowledge. The A Star algorithm, for all its usefulness, requires that obstacles in the entire map be known in advance. What do we do if we are planning movement into an unknown space, where we will creating the map as we go along? If we have a robot with sensors, such as sonar or lidar, then the robot will be detecting and identifying obstacles as it drives along. It also has to continually replan its route based on increasing information.

The A* process is only run one time to plan a route for a robot, before it begins to move. D*, a dynamic replanning process, is constantly updating the robot’s path as new information becomes available.

The D* algorithm allows ...