Speeding-up state-space search by automatic abstraction.

Abstract

Most existing abstraction algorithms are sensitive to the initial problem formulation. Given two different descriptions of the same space, they will produce different abstractions, of which one might be efficient for problem-solving while the other might be inefficient. This thesis presents a completely automated approach to generating and using abstractions for problem solving in state-spaces. The strategy to overcome the problem of sensitivity is called the graph relabelling strategy. The abstraction algorithms used are all based on that strategy and on a theoretical study of the complexity to abstract and to search using an abstraction. This study presents theorems and compares analytical results to some known graph algorithms. Extensive experiments confirm that our abstractions can be quickly computed and greatly reduce problem-solving time in state-spaces, especially those with invertible operators.