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.
Introduction
Real-time search algorithms, such as Korf’s Learning Real-Time A (LRTA), are designed for agents that must interleave planning with action. These algorithms allow an agent to move before a complete path to the goal is computed, making them ideal for dynamic environments. Historically, these algorithms were evaluated on domains like the 8-puzzle or grid-based navigation. However, researchers Sven Koenig and Reid G. Simmons noticed that almost any "reasonable" algorithm performed well on these standard benchmarks. This paper investigates the underlying mathematical properties that make these domains "easy" and introduces more rigorous testbeds to expose algorithmic weaknesses.
The Eulerian Property and "Type 1" Domains
The authors identify the Eulerian property as the key factor behind the ease of traditional benchmarks. An Eulerian state space is one where every state has an equal number of incoming and outgoing actions. Standard undirected graphs, where every action is reversible, are a common subset of this category.
In these "Type 1" domains, the environment's symmetry prevents an agent from getting truly lost. The authors prove that even simple, deterministic random walks like Edge Counting—which simply chooses the action executed least often—achieve polynomial complexity ($O(n^3)$) in Eulerian spaces. This explains why researchers previously believed such algorithms were universally efficient; they were only being tested in "easy" neighborhoods.
Hard Testbeds: "Type 2" Domains
To claim an algorithm is generally superior, it must be tested on non-Eulerian domains where actions cannot be easily undone. The authors propose two classes of hard-to-search state spaces:
- Reset State Spaces: Topologies where certain actions (mistakes) send the agent back to the starting state.
- Quicksand State Spaces: Topologies where the majority of actions in any given state move the agent away from the goal.
In these "Type 2" environments, the complexity of inefficient algorithms like Edge Counting explodes from polynomial to exponential. Conversely, more sophisticated learning algorithms like min-LRTA* maintain a tight complexity of $O(n^3)$ across all state spaces.
Experimental Results
The performance gap was empirically demonstrated using a modified Blocksworld task. In a standard Eulerian version (Domain 1), all algorithms performed similarly. However, in a "Reset" version (Domain 2) where certain actions knock down the entire stack, the difference was astronomical. For a task with 50 blocks, Edge Counting was estimated to be 250 billion times worse than min-LRTA*.
Additionally, the authors tested a specialized algorithm called BETA (Building a Eulerian Tour Algorithm). While BETA achieved a superior $O(n^2)$ complexity in Eulerian domains, it lacks the general robustness of min-LRTA* in non-Eulerian spaces.
Conclusion
This research highlights a major pitfall in search algorithm evaluation: relying solely on symmetric, undirected spaces. To ensure benchmarking integrity, researchers must include non-Eulerian domains like "reset" and "quicksand" spaces. While this study focused on uninformed search, it sets the stage for future work exploring how these topological properties interact with complex heuristics and larger lookahead windows.
Summary updated