Boosting Bidirectional A* Efficiencies: State-nonexistence Fast-confirming Hashing Schemes and Partial Problem-based Informed Heuristic Generations

Abstract: It is well-known that most games and real world problems are technically classified as NP-hard, and we often resort to human-like heuristics to get their sub-optimal solutions. In case we really want to find an optimal path to a fixed goal of a problem instance in an enormous search space, the conventional A* algorithm framework may be useful. The success of A* algorithms depends on how to generate a maximally informed admissible version of h-val, the estimated distance to the goal state, such that it is not larger than but still as close as the unknown real distance to the goal. Recently we have suggested a method of generating a heuristic value with that property. To operate A* algorithms in binary search fashions, some depth of fixed step backward states are pre-stored in disk, and the hashing schemes to handle efficiently pre- stored states must be designed to confirm fast the non-existence of a given state, not its existence, because the optimal path is there as soon as the existence of a state is confirmed. In this paper, state-nonexistence fast-confirming hashing schemes have been experimentally compared. The same pre-stored static backward states are also used for solving partial problems for the purpose of generating maximally informed admissible heuristic which guides the priority queue for A* algorithm in deciding which state to expand next. To show the validity of our method, it has been massively experimented for instances of Rubik‟s cube problem whose search space of states reachable from any given start state is known to cover 43*1018 states. The partial problems are experimentally compared, by varying forward search depths and tie-breaking functions, to show their effectiveness and efficiency in generating heuristic values.

Keywords: bidirectional A*, state-nonexistence fast-confirming hashing, partial problem-based heuristic, dynamic forward search, static backward search