Exploiting Monotonicity in Interval Constraint Propagation

Ignacio Araya, Gilles Trombettoni, Bertrand NeveuAAAI 2010 · DOI

Introduction

Solving systems of non-linear equations or inequalities over real numbers is a fundamental challenge in fields such as robotics, kinematics, and robust control. Interval-based solvers are the standard tool for these problems because they reliably handle floating-point errors. However, they often suffer from the "dependency problem": if a variable appears multiple times in an equation (e.g., $x^2 - x$), standard interval arithmetic treats each occurrence as independent. This leads to a massive overestimation of possible values, hindering solver efficiency.

The Mohc Algorithm

This paper introduces Mohc (Monotonic Hull Consistency), a new algorithm designed to overcome the dependency problem by exploiting function monotonicity. While it is well-known that monotonicity can eliminate overestimation, Mohc provides an adaptive way to utilize this property within a standard constraint propagation loop.

Methods and Components

The Mohc-Revise procedure enhances standard propagation with several key innovations:

  1. Adaptive Filtering: Mohc uses a ratio ($ ho_{mohc}$) to determine if a function is "monotonic enough" to justify advanced filtering, ensuring computational resources are spent where they provide the most benefit.
  2. MinMaxRevise: This component handles variables that appear only once in a constraint. If the function is monotonic relative to these variables, it uses their bounds to quickly contract the search space.
  3. MonotonicBoxNarrow: For variables with multiple occurrences, Mohc employs a specialized univariate interval Newton iteration to "shave" domains more effectively than traditional box-consistency algorithms.
HC4-Revise tree propagation for minimizing and maximizing a function within interval constraints, forming the basis for Mohc's enhancements.
  1. Occurrence Grouping: Even if a function isn't monotonic over an entire variable range, Mohc can identify and exploit monotonicity over subgroups of variable occurrences using Taylor-based approximations.
Geometric illustration of the interval narrowing process, showing how variable domains are 'shaved' to produce tighter bounds.

Key Insights

  • Emergent Monotonicity: A function may not be monotonic initially, but as the solver narrows the search space into smaller "boxes," monotonicity often emerges. Mohc is designed to detect and exploit this "bottom-up" property.
  • Optimal Enclosures: The authors prove that if a function is monotonic with respect to every variable, Mohc computes the Hull Consistency—the sharpest possible box enclosing all solutions.

Experimental Results

The algorithm was evaluated against state-of-the-art solvers (like HC4, Box, and Octum) using 17 Numerical Constraint Satisfaction Problems (NCSPs). The results demonstrate that Mohc is a powerhouse for complex non-linear systems:

  • Significant Speedups: Mohc achieved a 163x speedup on the "Butcher" problem and a 49x speedup on "Direct Kinematics" compared to the best competitors.
  • Search Space Reduction: The number of "choice points" (splits in the search space) was drastically reduced. For the "Virasoro" problem, choice points dropped from millions to roughly 38,000.
  • Efficiency: Mohc consistently provided the best trade-off between filtering time and search space reduction, even when compared to high-end 3B consistency algorithms.

Conclusion and Future Work

Mohc demonstrates that exploiting monotonicity is a highly effective strategy for solving non-linear constraints. While the current version relies on user-defined parameters for triggering checks, future work aims to make the algorithm fully auto-adaptive, allowing it to dynamically tune its sensitivity to monotonicity during the search process.

Summary updated

BibTeX
@inproceedings{araya2010exploiting,
  author = {Ignacio Araya and Gilles Trombettoni and Bertrand Neveu},
  title = {{Exploiting Monotonicity in Interval Constraint Propagation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7541},
}
Figure