Diverse Depth-First Search in Satisificing Planning

Abstract

Diverse best-first search (DBFS) is a successful algorithm for satisficing planning that is built on top of greedy best-first search and uses stochastic search techniques to select the next ``best'' state that is not always in agreement with the heuristic function. DBFS thus considers a diversity of search directions and avoids search plateaus caused by inaccurate heuristic estimation. However, the scalability of DBFS is still limited by the available memory resource, as in any planning system that uses best-first search at its core. This paper presents the diverse depth-first search (DDFS) algorithm that overcomes the memory bottleneck of DBFS. DDFS requires much less memory than DBFS yet it successfully incorporates DBFS' randomized node selection scheme for effective search diversification. Additionally, DDFS is enhanced with a transposition table to avoid duplicate search effort commonly found in depth-first search. Experimental results in solving problems used in previous International Planning Competitions show that DDFS can solve instances that remain unsolvable by DBFS due to its excessive memory requirements.