Speeding up the Parti-Game Algorithm

Maxim Likhachev* and Sven Koenig**

*Carnegie Mellon University, **Georgia Institute of Technology

maxim+@cs.cmu.edu, skoenig@cc.gatech.edu

 

Abstract

In this paper, we introduce an efficient replanning algorithm for nondeterministic domains, namely what we believe to be the first incremental heuristic minimax search algorithm. We apply it to the dynamic discretization of continuous domains, resulting in an efficient implementation of the parti-game reinforcement-learning algorithm for control in high-dimensional domains.