Abstract

Many complex real-world decision and control problems contain an underlying constraint reasoning problem. This is particularly evident ina recently developed approach toplanning, where almost all planning decisions are represented by constrained variables. The result is that a signi cant part of the planning problem is translated into a constraint network whose consistency determines the validity of the candidate plan. Since higher-level choices about control actions can add or remove variables and constraints, the underlying constraint network is invariably highly dynamic. Real planning problems require arbitrary domain-dependent constraints in the constraint network, in addition to giving rise to continuous variables. These requirements present a number of signi cant challenges for a constraint reasoning mechanism. In this paper, we introduce a general framework for handling dynamic constraint networks with real-valued variables, by using procedures to represent and e ectively reason about general constraints. The framework is based on a sound theoretical foundation, and is proven to be sound and complete under well-de ned conditions. Furthermore, the framework provides hybrid reasoning capabilities, as alternative solution methods like mathematical programming can be incorporated into the framework, in the form of procedures.