Components for state restoration in tree search

Abstract

Constraint programming systems provide software architectures for the fruitful interaction of algorithms for constraint propagation, branching and exploration of search trees. Search requires the ability to restore the state of a constraint store. Today’s systems use different state restoration policies. Up ward restoration undoes changes using a trail, and downward restoration (recomputation) reinstalls information along a downward path in the search tree. In this paper, we present an architecture that isolates the state restoration policy as an orthogonal software component. Applications of the architecture include two novel state restoration policies, called lazy copying and batch recomputation, and a detailed comparison of these and existing restoration policies with “everything else being equal”. The architecture allows the user to optimize the time and space consumption of applications by choosing existing and designing new state restoration policies in response to application-specific characteristics.