Map updating and path planning for real-time mobile robot navigation

This paper describes a navigation system which unites three important capabilities: it enables a mobile robot to avoid obstacles, map the environment, and plan local paths around more complex obstacles while navigating. This system extends and integrates the histogram grid representation and the modified A* algorithm. Our system uses the histogram grid representation and updating method to represent the robot´s environment and update a map quickly and reliably with the data from a laser range scanner. Our system also uses the modified A* algorithm to search this grid to plan and replan local paths. The navigation system that we have developed enables a mobile robot to smoothly avoid obstacles while navigating towards a goal at speeds of 0.15 to 0.35 meters per second, speeds which are faster than those typically obtained in similar systems