Affiliations: Computing Science Department, University of Alberta, Edmonton, AB, Canada. E-mails: {holte, nburch}@cs.ualberta.ca
Note: [] Corresponding author: Robert C. Holte, Computing Science Department, University of Alberta, Edmonton, AB T6G 2E8, Canada. E-mail: [email protected]
Abstract: Move pruning is a low-overhead technique for reducing search cost in single-agent search problems by avoiding the generation of duplicate states. Redundant sequences of moves, where the effect of one sequence is provably identical to some other sequence of moves, are suppressed during search. We present an algorithm for automatically identifying redundant move sequences in a general class of single-agent search problems, and a method for selecting redundant move sequences to prune during search. We demonstrate that the redundant move sequences which are to be pruned must be chosen carefully, and give experimental results using our move pruning method which show a speedup of multiple orders of magnitude in a variety of domains. Finally, we give theoretical results on conditions where move pruning does, and does not, affect the correctness of different search algorithms.
