In Situ Adaptive Tabulation (ISAT) Overview

ISAT is a nonlinear function approximator of dependent variables, y, as a function of independent variables, x. This is accomplished by dynamically constructing local linear approximations that are stored in a lookup database.

Nonlinear function: y=f(x), xєRn, yєRp

ISAT approximation: y=A1x, y=A2x, y=A3x, etc.

Example Animation   The animated graphic is an example with 2 independent variables (x and y as horizontal axes) and the 1 dependent variable (z as the vertical axis). ISAT approximates the function with multiple local linear regions. As the error tolerance increases, the approximation becomes increasingly granular to the point that individual linear regions can be observed.

The first eigenfunction of an L-shaped membrane. The second and third eigenfunctions have also been shown in MathWorks' publications. This animation shows an ISAT approximation to that function. The error tolerance for z is steadily ramped from 0.01 to 0.99. The error tolerance of the current frame is indicated on the figure. Initially at a low error tolerance of 0.01, the approximation is nearly exact but requires 206 ISAT records. When the error tolerance is increased to 0.1, 48 ISAT records are stored. At an error tolerance of 0.5, only 12 ISAT records are required to meet the relaxed error bound.

Explicit error control of the approximation of y is maintained by defining a region where the linear approximation is considered accurate. For n=1, this is a range on the value of x. For n=2, the estimate of the region of accuracy is an ellipse. For higher dimensional n, the estimate of the region of accuracy is a hyper-ellipsoid. For very nonlinear functions many linear approximations are required. For linear functions one record is required.

ISAT takes a fundamentally different approach to nonlinear function approximation. Most other function approximation approaches attempt to fit the entire nonlinear surface with one functional form. By using multiple local approximations, the functional form adapts to the nonlinear function. With this free functional form, ISAT is ideally suited for nonlinear functions with discontinuities or non-continuously differentiable points.

ISAT and Neural Networks

ISAT is an alternative to neural networks, not a replacement. ISAT is better suited to large-scale problems with O(n2+np) scaling, can better approximate functions with discontinuities, explicitly limits approximation error, can limit function approximation derivatives, is adaptive to new data training without re-optimization, and is simple to tune.

Areas of Application

Turbulent combustion simulations: Research Industry

Nonlinear model predictive control: Research

ISAT is a computational reduction technique applied to nonlinear model predictive control (NMPC) to make real-time applications feasible.  ISAT was originally developed for turbulent combustion simulations [1] and has recently been added to the popular CFD package, FluentTM   Like artificial neural networks, ISAT is a storage and retrieval method.  Unlike neural nets, ISAT is adaptive to extrapolation.  In addition, ISAT learns as it goes so there is no specified amount of training data before it starts performing.

ISAT is effective when the model is solved many times with the same time step size.  ISAT stores and retrieves the results of the model integrator that includes a sensitivity analysis (such as DASPK 3.0).  When ISAT receives an integration request, one of three actions is performed.  The first scenario is when the initial conditions (f) are within a region of accuracy centered around the initial conditions to a stored integration (f1).  The second scenario occurs when f is outside of the region of accuracy.  However, when an integration is subsequently performed, the final states are found to be within a specified error tolerance from the final states of the stored integration.  In this scenario the region of accuracy is grown.  The final scenario occurs when f is outside of the region of accuracy for the initial and final states.  In this case a new record is added to the ISAT database along with a new region of accuracy around the initial conditions.  As a demonstration, an example 2-D ISAT database is built sequentially in the following video.  The title of the graph changes at each step to indicate retrievals, growths, and additions.  View video (AVI)

 Scenario 1:  Retrieval Scenario 2: Growth Scanario 3: Addition

The ISAT technique shows considerable promise for the application of medium to large scale ODE and DAE models in NMPC.  Below is an example of the computational reduction possible with ISAT.  The model describes a binary distillation column (cyclohexane n-heptane) with 32 ordinary differential equations (ODEs).  The ISAT database was trained with NMPC step changes around the starting setpoint.  With training, the ISAT speed increased as more retrievals substituted growths and additions.

After 5000 optimizations a single step test was performed in order to show the trained ISAT speed.  The CPU times shown are from a Dell Inspiron 1100 laptop with a 2.0 GHz Celeron processor.

This example shows that the ISAT technique is effective in reducing the computational load while maintaining the accuracy of nonlinear MPC.  In addition to this example, ISAT has been successfully applied to projection method reduced models (balanced empirical gramians) and proper orthogonal decomposition reduced models with similar results.  In addition, a DAE model with 64 states has been successfully implemented in ISAT for NMPC with average optimization times of less than 0.5 seconds.

References

[1]Pope, S. B., "Computationally Efficient Implementation of Combustion Chemistry Using In Situ Adaptive Tabulation", Combustion Theory Modelling, 1997, 1, pp. 41-63.

Publications

Peer Reviewed

Hedengren, J. D. and Edgar, T. F., Approximate Nonlinear Model Predictive Control with In Situ Adaptive Tabulation, Computers and Chemical Engineering, Volume 32, pp. 706-714, 2008.  [Preprint],   [Abstract]

Hedengren, J. D. and Edgar, T. F., In Situ Adaptive Tabulation for Real-Time Control, Industrial & Engineering Chemistry Research, Ind. Eng. Chem. Res., Volume 44, Issue 8, pp. 2716 -2724, 2005.  [Paper, Abstract]

Hedengren, J. D. and Edgar, T. F., Order Reduction of Large Scale DAE Models, Computers and Chemical Engineering, Volume 29, Issue 10, pp. 2069-2077, 2005.  [Abstract]

Conference Publications

Hedengren, J.D. and Edgar, T.F., Order Reduction of a Large-Scale Index-2 DAE Model, , Computing and Systems Technology Division, AIChE National Meeting, Cincinnati, OH, Nov 2005.   [Abstract]

Hedengren, J. D. and Edgar, T. F., Adaptive DAE Model Reduction, Texas-Wisconsin Modeling and Control Constortium (TWMCC), Madison, WI, Sept 2004.

Hedengren, J. D. and Edgar, T. F., Order Reduction of Large Scale DAE Models, Computing and Systems Technology Division, AIChE National Meeting, Austin, TX, Nov 2004.   [Paper, Presentation]

Hedengren, J. D. and Edgar, T. F., In Situ Adaptive Tabulation for Real-time Control, Proceedings of the American Control Conference (ACC), Boston, MA, July 2004.  [Paper, Presentation]

Hedengren, J. D. and Edgar, T. F., Dependency Analysis for DAE to ODE Conversion and Model Reduction, Texas-Wisconsin Modeling and Control Constortium (TWMCC), Austin, TX, Feb 2004.   [Paper]

Hedengren, J. D., In Situ Adaptive Tabulation for Real-time Control, Admission to Candidacy, 9 Dec. 2003 - Himmelblau Library (CPE 4.446).  [Paper, Presentation]

Hedengren, J. D. and Edgar, T. F., In Situ Adaptive Tabulation for Nonlinear MPC, Poster Session: Systems and Process Control, AIChE National Meeting, San Francisco, CA, Nov 2003.   [Paper]

Hedengren, J. D. and Edgar, T. F., In Situ Adaptive Tabulation for Nonlinear MPC, Texas-Wisconsin Modeling and Control Constortium (TWMCC), Madison, WI, Sept 2003.   [Presentation]

Doctoral Dissertation

Hedengren, J. D., Real-Time Estimation and Control of Large-Scale Nonlinear DAE Systems, Doctoral Dissertation, The University of Texas at Austin, 2005.  PDF (1.4 MB)