Stochastic Node Caching for Memory-Bounded Search

Linear-space search algorithms such as IDA* (Iterative DeepeningA*) cacheonly thosenodeson thecurrentsearch path, but may revisit the samenode againand again. This causesIDA* to take an impractically long time to find a solution. In this paper, we proposea simple and effective algorithm called StochasticNude Caching(SNC) for reducing the numberof revisits. SNC cachesa nodewith the best estimate, which is currently known of the minimum estimatedcostfrom the nodeto the goal node. Unlike previous relatedresearchsuch as MREC, SNC cachesnodesselectively, basedon a fixed probability. We demonstratethat -. -- YNC caneffectiveiy reducethe numberof revisits compared to MREC, especiallywhen the state-space forms a lattice.

Authors

• Teruhisa Miura Toru Ishida

Keywords

No keywords are indexed for this paper.