Evaluation of real-time search algorithms in dynamic worlds (summary of results)

There are many application domains of real-time Artificial Intelligence (AI), where the world changes during the problem solving process. Several real-time search algorithms have been proposed for problem solving in dynamic environments. However, there has not been any systematic evaluation and comparison of these algorithms. This paper provides a classification of different dynamic worlds. It then provides a detailed model of a dynamic world where changes occur in edge costs around a zero mean. A formal analysis of the model suggests that the static rank ordering of solution paths is preserved in the proposed dynamic model. The paper provides analysis of two real-time search algorithms, namely DYNORAII and RTA∗, for the real-time path planning problem. We provide new results on the path planning problem in the proposed dynamic model of graphs. We also provide experimental evaluation of DYNORAII and RTA∗ in their ability to minimize response-times in dynamic environments.