Scale-Based Monotonicity Analysis in Qualitative Modelling with Flat Segments

Abstract

Qualitative models are often more suitable than classical quantitative models in tasks such as Model-based Diagnosis (MBD), explaining system behavior, and designing novel devices from first principles. Monotonicity is an important feature to leverage when constructing qualitative models. Detecting monotonic pieces robustly and efficiently from sensor or simulation data remains an open problem. This paper presents scale-based monotonicity: the notion that monotonicity can be defined relative to a scale. Real-valued functions defined on a finite set of reals e.g. sensor data or simulation results, can be partitioned into quasi-monotonic segments, i.e. segments monotonic with respect to a scale, in linear time. A novel segmentation algorithm is introduced along with a scale-based definition of "flatness".

Keywords

Piecewise Quasi-Monotone Functions, Model-Based Diagnostic, Qualitative Model Abstraction

Reference

Martin Brooks, Yuhong Yan, Daniel Lemire, Scale-Based Monotonicity Analysis in Qualitative Modelling with Flat Segments, IJCAI05, Edinburgh, UK, July 2005.

Download

Hint : It is sometimes necessary to hold down shift while clicking in order to save a document.

Software

The software used for this paper is available from Yuhong Yan upon request.

BibTeX

@inproceedings{YLBIJCAI05,
   author    = {Martin Brooks and Yuhong Yan and Daniel Lemire},
   title     = {Scale-Based Monotonicity Analysis in Qualitative Modelling with Flat Segments},
   booktitle = {Proceedings of IJCAI'05},
   year      = {2005},
   url = {http://www.daniel-lemire.com/fr/documents/publications/ijcai05_web.pdf}
}

Authors

Related work

Errata

In the original version of this paper, as it appears in IJCAI'05 proceedings, we were pessimistic in the complexity analysis of the algorithm which is O(n K): we added an extra log K factor.

Valid XHTML 1.0! Valid CSS!