Real-Time Search in Nondeterministic Domains

Abstract

Many search domains are nondeterministic. 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 nondeterministic domains. We describe which nondeterministic 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.