The Focussed D* Algorithm for Real-Time Replanning Anthony Stentz Robotics Institute Carnegie Mellon University Pittsburgh, Pennsylvania 15213 U S A Abstract Finding the lowest-cost path through a graph is central to many problems including route planning for a mobile robot. If arc costs change during the traverse, then the remainder of the path may need to be replanned. This is the case for a sensor-equipped mobile robot with imperfect information about its environment. As the robot acquires additional information via its sensors, it can revise its plan to reduce the total cost of the traverse. If the prior information is grossly incomplete, the robot may discover useful information in every piece of sensor data. During replanning, the robot must either wait for the new path to be computed or move in the wrong direction; therefore, rapid replanning is essential. The D* algorithm (Dynamic A*) plans optimal traverses. ID real-time by incrementally repairing paths to the robot's state as new information is discovered. This paper describes an extension to D* that focuses the repairs to significantly reduce the total time required for the initial path calculation and subsequent replanning operations. This extension completes the development of the D* algorithm as a full-generalization of A* for dynamic environments where arc costs can change during the traverse of the solution path. The paper describes an extension to D* that focuses the cost updates to minimize state expansions and further reduce computational costs. The algorithm uses a heuristic function similar to A* to both propagate cost increases and focus cost reductions. A biasing function is used to compensate for robot motion between replanning operations. The net effect is a reduction in run-time by a factor of two to three. The paper begins with the intuition behind the algorithm, describes the extension, presents an example, evaluates empirical comparisons, and draws conclusions. The Focussed D* algorithm improves upon the basic D* algorithm by focusing the search on the robot's location, reducing the number of states that need to be examined. This results in faster replanning and more efficient path computation. The algorithm maintains an OPEN list of states for expansion, with states classified as RAISE or LOWER based on their path cost. RAISE states propagate cost increases, while LOWER states propagate cost reductions. The algorithm uses a focussing heuristic to direct the search towards the robot's location, reducing the number of states that need to be processed. This results in a significant reduction in computational time, with the algorithm being up to three times faster than the basic D* algorithm. The Focussed D* algorithm is tested on various environments, with results showing that it outperforms other algorithms in terms of speed and efficiency. The algorithm is particularly effective in large environments, where the basic D* algorithm is less efficient. The algorithm is also able to handle dynamic environments where arc costs change during the traversal of the solution path. The algorithm isThe Focussed D* Algorithm for Real-Time Replanning Anthony Stentz Robotics Institute Carnegie Mellon University Pittsburgh, Pennsylvania 15213 U S A Abstract Finding the lowest-cost path through a graph is central to many problems including route planning for a mobile robot. If arc costs change during the traverse, then the remainder of the path may need to be replanned. This is the case for a sensor-equipped mobile robot with imperfect information about its environment. As the robot acquires additional information via its sensors, it can revise its plan to reduce the total cost of the traverse. If the prior information is grossly incomplete, the robot may discover useful information in every piece of sensor data. During replanning, the robot must either wait for the new path to be computed or move in the wrong direction; therefore, rapid replanning is essential. The D* algorithm (Dynamic A*) plans optimal traverses. ID real-time by incrementally repairing paths to the robot's state as new information is discovered. This paper describes an extension to D* that focuses the repairs to significantly reduce the total time required for the initial path calculation and subsequent replanning operations. This extension completes the development of the D* algorithm as a full-generalization of A* for dynamic environments where arc costs can change during the traverse of the solution path. The paper describes an extension to D* that focuses the cost updates to minimize state expansions and further reduce computational costs. The algorithm uses a heuristic function similar to A* to both propagate cost increases and focus cost reductions. A biasing function is used to compensate for robot motion between replanning operations. The net effect is a reduction in run-time by a factor of two to three. The paper begins with the intuition behind the algorithm, describes the extension, presents an example, evaluates empirical comparisons, and draws conclusions. The Focussed D* algorithm improves upon the basic D* algorithm by focusing the search on the robot's location, reducing the number of states that need to be examined. This results in faster replanning and more efficient path computation. The algorithm maintains an OPEN list of states for expansion, with states classified as RAISE or LOWER based on their path cost. RAISE states propagate cost increases, while LOWER states propagate cost reductions. The algorithm uses a focussing heuristic to direct the search towards the robot's location, reducing the number of states that need to be processed. This results in a significant reduction in computational time, with the algorithm being up to three times faster than the basic D* algorithm. The Focussed D* algorithm is tested on various environments, with results showing that it outperforms other algorithms in terms of speed and efficiency. The algorithm is particularly effective in large environments, where the basic D* algorithm is less efficient. The algorithm is also able to handle dynamic environments where arc costs change during the traversal of the solution path. The algorithm is