| Sponsor | Sven Koenig |
| Area | Intelligent Systems |
Problem
Autonomous agents often need to be able to replan quickly as their knowledge changes. Examples are mobile robots or computer-controlled agents in games (such as "Total Annihilation") that can observe obstacles that they did not know about and that block their paths. Since replanning from scratch is often extremely time consuming, researchers have developed planning methods that are incremental versions of heuristic search methods. For example, Focussed D* by Anthony Stentz and D* Lite by Likhachev and Koenig both move a mobile robot on a shortest path from its current vertex to a goal vertex as the edge costs of the graph change. Your task is to compare these two algorithms (either theoretically by analyzing them or experimentally by implementing them) and characterize exactly when their behavior differs, for example, when they expand different vertices, whether one algorithm can be transformed into the other, whether one algorithm implements optimizations that the other one does not, and so on. This is a topic for a student who likes algorithms.
Improved Fast Replanning for Robot Navigation in Unknown Terrain. Technical Report, GIT-COGSCI-2002/3, College of Computing, Georgia Institute of Technology, Atlanta (Georgia), 2001.
The Focussed D* Algorithm for Real-Time Replanning