Efficient Replanning For Mobile Robots

Abstract

The research literature has addressed extensively the motion planning problem for one or more robots mobbing through a field of obstacles to a goal. Most of this work assumes that the environment is completely known before the robot begins its traverse. The optimal algorithms in this literature research a state space (e.g., visibility graph, grid cells) using the distance transform or heuristics to find the lowest cost path from the robot's start state to the goal state. Cost can be defined to be distance traveled, energy expended, time exposed o danger, etc. This paper presents the D* algorithm for generating optimal paths for a robot operating with a sensor and a map of the environment. The robot's sensor is able to measure arc costs in the vicinity of the robot, and the known and estimated arc values comprise the map. Thus, the algorithm can be used for any planning presentation, including visibility graphs and grid cell structures. The paper describes the algorithm, illustrates its operation, presents our approach for implementation, and then concludes with a proof of operation.