Tim Hickey, Ph.D.

Professor of Computer Science and Volen National Center for Complex Systems
Brandeis University
Waltham, Massachusetts

Exploring Complex Non-Linear Systems Using Interval Arithmetic Constraints

Complex systems often tend to exhibit non-linear effects and that non- linearity makes such systems difficult to study using standard techniques. In this talk I presented a new approach to studying non-linear systems that relies on interval arithmetic constraint solving to infer properties of these systems. This work grows out of seminal research by Moore in the 1960s on application of interval arithmetic as well as work in the 1980s and 1990s on high-level computer languages based on logic and constraints.

The key idea behind this work is to build a system that will use numerical techniques to automatically make "provably correct" inferences about the parameters that appear in mathematical systems. For example, one could specify an ordinary differential equation with some parameters (known only to lie in some specific intervals) together with values of the solution function at certain points (again known to lie in specific intervals). The constraint solver would then try to shrink these intervals without removing any possible solutions to the system. In this way the parameters could be constrained to fairly small intervals by giving a large set of measured values (with explicit error intervals).

The techniques we use to implement such a solver decompose the original complex constraint into a large number of primitive constraints by introducing additional variables representing intermediate quantities. These new variables are initially assigned to the intervals [-infinity, infinity] and the constraint solvers for each of the primitive constraints is repetitively called to narrow its variables intervals. This process continues until there is no longer any change. The beauty of this technique is its simplicity. It allows one to work with extremely general constraints. The downside is that the constraint solver may not be able to make any progress on some constraints. There are several approaches to making this technique more robust. One method we have investigated is building meta- level solvers on top of the underlying solver.

There is much work to be done in this area. We are currently using these techniques to study hybrid systems. These are systems in which a digital controller interacts with a physical environment. The environment is generally modeled as a non-linear ODE or PDE and the constraint solvers we consider are well suited to this type of problem. We are also looking for examples of complex systems that arise when studying neural assemblies as they may provide interesting non-linear case studies for the solver.