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



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.


Keywords: reinforcement learning, variable resolution discretization, Parti-Game, planning, lifelong planning, search, incremental search