@device(postscript)
@libraryfile(Mathematics10)
@libraryfile(Accents)
@style(fontfamily=timesroman,fontscale=11)
@pagefooting(immediate, left "@c<Technical Report 1996>",
center "@c<Computer Science>",
right "@c<Carnegie Mellon>")
@heading(The Influence of Domain Properties on the
Performance of Real-Time Search Algorithms)
@heading(CMU-CS-96-115)
@center(@b(Sven Koenig, Reid G. Simmons))
@center(August 1996)
@center(FTP: CMU-CS-96-115.ps)
@blankspace(1)
@begin(text)

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 state spaces") 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.

@blankspace(2line)
@begin(transparent,size=10)
@b(Keywords:@ )@c<Domain properties (here: Eulerian graphs), efficient and
inefficient real-time search algorithms (edge counting, Learning Real-Time
A*, node counting), testbeds (blocksworld, eight puzzle, gridworld,
quicksand state space, racetrack domain, reset state space)>
@end(transparent)
@blankspace(1line)
@end(text)
@flushright(@b[(43 pages)])