Real-Time Search in Non-Deterministic Domains
Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence. Planning. 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.
@inproceedings{ijcai1995p214,
title = {Real-Time Search in Non-Deterministic Domains},
author = {Koenig, Sven and Simmons, Reid G.},
booktitle = {Proceedings of the Fourteenth International Joint Conference on
Artificial Intelligence, {IJCAI-95}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Chris S. Mellish},
pages = {1660--1668},
year = {1995},
note = {Planning},
url = {https://ijcai.org/proceedings/1995/214},
}
TY - CPAPER TI - Real-Time Search in Non-Deterministic Domains AU - Koenig, Sven AU - Simmons, Reid G. T2 - Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI-95 PB - International Joint Conferences on Artificial Intelligence PY - 1995 SP - 1660 EP - 1668 UR - https://ijcai.org/proceedings/1995/214 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
