State-Set Search

Abstract

State-set search is state space search when the states being manipulated by the search algorithm are sets of states from some underlying state space. State-set search arises commonly in planning and abstraction systems, but this paper provides the first formal, general analysis of state-set search. We show that the state-set distance computed by planning systems is different than that computed by abstraction systems and introduce a distance in between the two, dww, the maximum admissible distance. We introduce the concept of a multi-abstraction, which maps a state to more than one abstract state in the same abstract space, describe the first implementation of a multi-abstraction system that computes dww, and give initial experimental evidence that it can be superior to domain abstraction.