The Robotics Institute

Carnegie Mellon Robotics Institute

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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.

Notes

Text Reference

Sven Koenig and Reid Simmons, "Real-Time Search in Nondeterministic Domains," Proceedings ofthe Fourteenth International Joint Conference on Artificial Intelligence (IJCAI), 1995, pp. 1660 - 1667.

BibTeX Reference

@inproceedings{Koenig_1995_3001,
   author = "Sven Koenig and Reid Simmons",
   title = "Real-Time Search in Nondeterministic Domains",
   booktitle = "Proceedings ofthe Fourteenth International Joint Conference on Artificial Intelligence (IJCAI)",
   pages = "1660 - 1667",
   year = "1995",
}

The Robotics Institute

Menu