|
Abstract : |
Many search domains are non-deterministic. Although real-time search methods have traditionally been studied in deterministic domains, they are well suited for searching nondeterministic domains since they do not have to plan for every contingency-- they can react to the actual outcomes of actions. In this paper, we introduce the min-max LRTA * algorithm, a simple extension of Korf's Learning Real-Time A * algorithm (LRTA*) to non-deterministic domains. We describe which non-deterministic domains min-max LRTA * can solve, and analyze its performance for these domains. We also give tight bounds on its worst-case performance and show how this performance depends on properties of both the domains and the heuristic functions used to encode prior information about the domains. 1, |
