Abstract

Abstract: In this report, we investigate the influence of domain properties on the performance of real-time search algorithms. We study uninformed, revolving real-time search algorithms with minimal lookahead that solve suboptimal search problems, for example variants of Korf's LRTA* algorithm and edge counting (these algorithms have been used successfully in the literature). We demonstrate, both theoretically and experimentally, that they can search Eulerian domains (a superset of undirected domains) very easily: even the real-time search algorithms that can be intractable are always efficient in Eulerian domains. 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 superiority of a real-time search algorithm across a wide range of domains; the studied real-time search algorithms differ in this respect from traditional search algorithms. To this end, we describe two classes of domains ('reset state spaces' and 'quicksand statespaces') that do not suffer as much from the problems of the standard test domains and demonstrate the performance of various real-time search algorithms in them.

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.