Real-Time Search in Non-Deterministic Domains

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 Introduction Real-time (heuristic) search methods, a term coined by Korf [ Korf, 1987 ] , interleave search with action execution, limiting the amount of deliberation performed between action executions. After an act...