Nested Search versus Limited Discrepancy Search
This addresses a problem for researchers and practitioners in search algorithms, offering an incremental improvement in heuristic-based search methods.
The paper compares Nested Search (NS) and Limited Discrepancy Search (LDS) for state space search with heuristics, finding that NS, which focuses on the best heuristic playout, often outperforms LDS, which focuses on the best heuristic move, under similar search times.
Limited Discrepancy Search (LDS) is a popular algorithm to search a state space with a heuristic to order the possible actions. Nested Search (NS) is another algorithm to search a state space with the same heuristic. NS spends more time on the move associated to the best heuristic playout while LDS spends more time on the best heuristic move. They both use similar times for the same level of search. We advocate in this paper that it is often better to follow the best heuristic playout as in NS than to follow the heuristic as in LDS.