Analysing and Combining Partial Problem Solutions for Properly Informed Heuristic Generations

Abstract

Finding an optimal path to the fixed goal state of a problem instance lying in an enormous search space may be described in the framework of the conventional A^* algorithm. However, the estimated distance to the goal state, so called h_value, must be generated by an admissible heuristic such that it is not larger than but still as close as the unknown real distance to the goal. In this paper, we suggest a method of generating a heuristic with that property. After analyzing a number of devised partial problems, some are selected to be combined to produce a properly informed heuristic. In solving a complex problem with a fixed goal, some depth of fixed backward states is pre-stored. Those static backward states are also used for partial problem backward searches. For a given problem instance, the forward search is first performed for each of its partial problem. The dynamically generated space is combined with the static search space to produce the temporary search space, which is used to aid in the generation of each state heuristic for the course of problem solving. A novel method of constructing the temporary search space for each partial problem is suggested, in which each forward state found in the static backward space is back-propagated and propagated in the forward space. To show the effectiveness of our method, it has been massively experimented for instances of Rubik’s cube problem of some difficulty whose search space of states reachable from any given start state is known to cover 43*10¹⁸ states, the number of which even an 64-bit unsigned integer cannot hold.

Keywords: A^*, admissible heuristic, partial problems, dynamic forward search, static backward search, Rubik’s cube