Abstract
Iterative Threshold Search (ITS) is a limited-memory heuristic search algorithm designed to bridge the gap between the memory-intensive A and the memory-efficient but redundant IDA. By utilizing available memory to store pruned nodes and backing up cost estimates (B-values) to parent nodes, ITS avoids the redundant node re-expansions characteristic of IDA. Theoretical analysis proves that ITS dominates IDA in terms of node generations. Experimental results on the Traveling Salesman Problem (TSP) demonstrate that ITS significantly reduces both node generations and execution time as available memory increases, particularly in domains where node generation is computationally expensive.
1. Introduction
Heuristic search algorithms typically face a trade-off between time and memory efficiency. A is optimal in node expansions but suffers from exponential memory growth, limiting its applicability to small-to-medium problems. Conversely, IDA (Iterative Deepening A) operates with linear memory by re-exploring the search space with increasing cost thresholds. However, IDA is "forgetful," discarding all information between iterations and leading to significant redundant work.
This paper introduces Iterative Threshold Search (ITS), a "best-of-both-worlds" approach. ITS utilizes available system memory to store previously explored nodes and their updated cost estimates, ensuring it never performs more work than IDA while approaching A's efficiency as memory increases.
2. The ITS Algorithm
ITS functions similarly to IDA by using a threshold ($z$) to limit search depth. It improves upon IDA through two primary mechanisms:
- B-values: ITS maintains a $B$-value for each branch. When a subtree is exhausted, the minimum cost discovered within it is "backed up" to the parent's $B$-value.
- Smart Retraction: When the allocated memory ($S$) is exhausted, ITS prunes the least promising nodes. Before deletion, a node's cost information is preserved in its parent's $B$-value.
These mechanisms allow ITS to skip expensive branches in subsequent iterations if their $B$-values already exceed the current threshold. Theoretically, ITS is shown to be a simplified version of MA* and a generalization of MREC.
3. Experimental Evaluation
The algorithm was benchmarked on three combinatorial optimization problems: Flow-shop Scheduling, the 15-Puzzle, and the Traveling Salesman Problem (TSP). The TSP instances involved 5 to 40 cities with random uniform cost matrices.
3.1 Performance on TSP
On the TSP, ITS demonstrated substantial improvements over IDA. Even with zero additional memory ($S=0$), ITS(0) generated fewer nodes and ran faster than IDA. As memory allocation increased, performance gains became more pronounced.
As shown in the figure above, the number of node generations for ITS decreases significantly as more memory is provided, approaching the theoretical minimum of A*.
3.2 Computational Efficiency
The practical benefit of ITS is most evident when node generation is computationally expensive. In the TSP, the bookkeeping overhead of ITS is negligible compared to the cost of regenerating nodes.
The ratio of running times indicates that ITS can be over 10 times faster than IDA* on larger TSP instances when sufficient memory is available.
4. Discussion and Limitations
While ITS dominates IDA* in node generations, its "per-node" overhead is higher. This makes it less suitable for problems like the 15-puzzle, where node generation is extremely fast and the heuristic is simple. In such cases, the time spent managing the search tree can exceed the time saved by avoiding re-expansions. Furthermore, the effectiveness of ITS depends on the threshold increment; large increments reduce the utility of backed-up information.
5. Conclusion
ITS provides a robust framework for utilizing available memory to enhance heuristic search. By guaranteeing dominance over IDA* and offering significant speedups in complex domains, ITS serves as an efficient alternative for large-scale optimization problems where memory is limited but not strictly linear.
Summary updated