Extending Consistent Domains of Numeric CSP

Hélène Collavizza, François Delobel, Michel RueherIJCAI 1999

Introduction

In engineering and Computer-Aided Design (CAD), finding a single solution to a set of constraints is often insufficient. Designers require tolerance: a range of values for components—such as a motor's torque or a projectile's launch angle—that are guaranteed to function correctly within a system.

Traditional numeric Constraint Satisfaction Problem (CSP) techniques typically focus on "external" consistency (e-consistency), which involves pruning values that cannot be part of a solution. However, e-consistency does not guarantee that every point within the remaining interval is valid. This paper introduces a framework for maximizing "internal" consistency (i-consistency), providing a computationally efficient method for engineers to define safe design tolerances in non-linear systems.

Defining Internal Consistency

The core innovation of this work is the shift from e-consistency to i-consistency. While e-consistency seeks the smallest box containing all solutions, i-consistency identifies a region where every point is a guaranteed solution.

Visualizing the difference between internal consistency (i-consistent box A and its extensions) and external consistency (the smallest external box).

To achieve this, the authors utilize a univariate extrema function. For any given non-linear inequality constraint, this function determines the boundary of the solution space for a specific variable while keeping other variables within their defined domains. The proposed i-extension algorithm follows a three-step process:

  1. Initialization: Start with a known safe subset (a point or small box already known to be a solution).
  2. Boundary Definition: Define extrema functions for every inequality in the system to find the limits of the variable being extended.
  3. Global Optimization: The maximal extension is determined by the minimum of these individual limits.

By focusing on one variable at a time and treating others as fixed intervals, the approach avoids the exponential complexity typically associated with general non-linear solvers. The authors leverage Box-consistency techniques, specifically the Newton method, to find these extrema efficiently.

Practical Application: The Ballistic Example

The framework was evaluated using several engineering problems, most notably a ballistic simulation. The objective was to find the maximum range of launch angles ($\alpha$) and initial speeds ($V$) that ensure a projectile hits a specific target interval in a gravitational field.

The ballistic problem setup: determining the range of launch angles and velocities to hit a target interval.

In this example, the authors began with a safe launch angle range of $[32^\circ, 35^\circ]$. By applying the i-extension framework, they successfully extended this range to $[32^\circ, 38.4^\circ]$ while maintaining the guarantee that the target would be hit. This demonstrates the practical utility of the method in expanding design tolerances without compromising system integrity.

Conclusion and Future Directions

The proposed framework offers a scalable, linear-complexity solution for calculating safe variable extensions in non-linear CSPs. By leveraging interval arithmetic and Newton-based pruning, it makes the computation of safe regions feasible for complex systems that were previously too expensive to solve this way.

However, some limitations remain. The resulting extension is dependent on the order in which variables are processed, and the algorithm requires a pre-existing "seed" solution to begin. Future research may explore simultaneous multi-variable extension to maximize the total volume of safe design boxes rather than focusing on univariate growth.

Summary updated

BibTeX
@inproceedings{collavizza1999extending,
  author = {Hélène Collavizza and François Delobel and Michel Rueher},
  title = {{Extending Consistent Domains of Numeric CSP}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
}
Figure