Spider Search: An Efficient and Non-Frontier-Based Real-Time Search Algorithm

Abstract

Real-time search algorithms are limited to constantbounded search at each time step. We do not see much difference between standard search algorithms and good realtime search algorithms when problem sizes are small. However, having a good real-time search algorithm becomes important when problem sizes are large. In this paper we introduce a simple yet efficient algorithm, Spider Search, which uses very low constant time and space to solve problems when agents need deep (but not exhaustive) path analysis at each step. Moreover, we did some experimental tests to compare Spider search with other searches. We expect that Spider search is the first in a new class of tree-based rather than frontier-based search algorithms.