Abstract

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.

Download the paper in pdf.

Download the paper in gzipped postscript (large download time).

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.