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

Although researchers have studied which factors influence the behavior of traditional search algorithms, currently not much is known about how domain properties influence the performance of real-time search algorithms. In this paper we demonstrate, both theoretically and experimentally, that Eulerian state spaces (a superset of undirected state spaces) are very easy for some existing real-time search algorithms to solve: even real-time search algorithms that can be intractable, in general, are efficient for Eulerian state spaces. Because traditional real-time search testbeds (such as the eight puzzle and gridworlds) are Eulerian, they cannot be used to distinguish between efficient and inefficient real-time search algorithms. It follows that one has to use non-Eulerian domains to demonstrate the general superiority of a given algorithm. To this end, we present two classes of hard-to-search state spaces and demonstrate the performance of various real-time search algorithms on them.

Notes

Text Reference

Sven Koenig and Reid Simmons, "Easy and Hard Testbeds for Real-Time Search Algorithms," Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI), 1996, pp. 279 - 285.

BibTeX Reference

@inproceedings{Koenig_1996_3000,
   author = "Sven Koenig and Reid Simmons",
   title = "Easy and Hard Testbeds for Real-Time Search Algorithms",
   booktitle = "Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI)",
   pages = "279 - 285",
   year = "1996",
}

The Robotics Institute

Menu