Enhancing state space search for planning by monte-carlo random walk exploration

State space search is one of the most important and proverbial techniques for planning. At the core of state space search, heuristic function largely determines the search efficiency. In state space search for planning, a well-observed phenomenon is that for most of the time during search, it explores a large number of states while the minimal heuristic value has not been reduced. This so called “plateau escape” phenomenon has attracted many interests in heuristic search areas, especially in satisfiability (SAT) and constraint satisfaction problems (CSP). In planning, the efficiency of many state space search based planners largely depend on how fast they can escape from these plateaus. Therefore, their search performance can be improved if we could reduce the plateau escaping time. In this paper, we propose a Monte-Carlo Random Walk (MRW) assisted plateau escaping algorithm for planning. Specifically, it invokes a Monte-Carlo random search procedure to find an exit when a plateau is detected during the search. We establish a theoretical model to analyze when a Monte-Carlo random search is helpful to state space search in finding plateau exits. We subsequently implement a sequential and a parallel version of the proposed scheme. Our experimental results not only show the advantages of using random-walk to assist state space search for planning problems, but also validates the performance analysis in the theoretical model.