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:
- 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.
- 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.
- MonotonicBoxNarrow: For variables with multiple occurrences, Mohc employs a specialized univariate interval Newton iteration to "shave" domains more effectively than traditional box-consistency algorithms.
- 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.
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
3Bconsistency 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