---
title: "Real-Time Search in Non-Deterministic Domains"
authors:
  - "Sven Koenig"
  - "Reid G. Simmons"
doi: ""
url: "https://ijcai.org/proceedings/1995/214"
pdf: "https://ijcai.org/proceedings/1995/0214.pdf"
venue: "Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence"
year: 1995
pages: "1660-1668"
track: "Planning"
keywords:
---

# Real-Time Search in Non-Deterministic Domains

Sven Koenig, Reid G. Simmons

*Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence*, pages 1660-1668.

## 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.