research-article

Precise piecewise affine models from input-output data

Authors:

Nimit SinghaniaAuthors Info & Claims

EMSOFT '14: Proceedings of the 14th International Conference on Embedded Software

Article No.: 3, Pages 1 - 10

https://doi.org/10.1145/2656045.2656064

Published: 12 October 2014 Publication History

Abstract

Formal design and analysis of embedded control software relies on mathematical models of dynamical systems, and such models can be hard to obtain. In this paper, we focus on automatic construction of piecewise affine models from input-output data. Given a set of examples, where each example consists of a d-dimensional real-valued input vector mapped to a real-valued output, we want to compute a set of affine functions that covers all the data points up to a specified degree of accuracy, along with a disjoint partitioning of the space of all inputs defined using a Boolean combination of affine inequalities with one region for each of the learnt functions. While traditional machine learning algorithms such as linear regression can be adapted to learn the set of affine functions, we develop new techniques based on automatic construction of interpolants to derive precise guards defining the desired partitioning corresponding to these functions. We report on a prototype tool, Mosaic, implemented in Matlab. We evaluate its performance using some synthetic data, and compare it against known techniques using data-sets modeling electronic placement process in pick-and-place machines.

References

[1]

A. Albarghouthi and K. L. McMillan. Beautiful interpolants. In Proceedings of the 25th International Conference on Computer Aided Verification, CAV'13, pages 313--329, 2013.

Digital Library

[2]

R. Alur, R. Bodík, G. Juniwal, M. M. K. Martin, M. Raghothaman, S. A. Seshia, R. Singh, A. Solar-Lezama, E. Torlak, and A. Udupa. Syntax-guided synthesis. In Formal Methods in Computer-Aided Design, FMCAD, pages 1--17, 2013.

[3]

R. Alur, T. Henzinger, G. Lafferriere, and G. Pappas. Discrete abstractions of hybrid systems. Proceedings of the IEEE, 88(7):971--984, 2000.

[4]

A. Bemporad, A. Garulli, S. Paoletti, and A. Vicino. A bounded-error approach to piecewise affine system identification. Automatic Control, IEEE Transactions on, 50(10):1567--1580, Oct 2005.

[5]

L. Breiman. Hinging hyperplanes for regression, classification, and function approximation. Information Theory, IEEE Transactions on, 39(3):999--1013, May 1993.

Digital Library

[6]

M. Colón, S. Sankaranarayanan, and H. Sipma. Linear invariant generation using non-linear constraint solving. In W. Hunt and F. Somenzi, editors, Computer Aided Verification, volume 2725 of Lecture Notes in Computer Science, pages 420--432. Springer Berlin Heidelberg, 2003.

[7]

I. Dillig, T. Dillig, B. Li, and K. McMillan. Inductive invariant generation via abductive inference. SIGPLAN Not., 48(10):443--456, Oct. 2013.

Digital Library

[8]

G. Ferrari-Trecate, M. Muselli, D. Liberati, and M. Morari. A clustering technique for the identification of piecewise affine systems. Automatica, 39(2):205--217, 2003.

Digital Library

[9]

S. Gulwani. Dimensions in program synthesis. In Proceedings of the 12th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming, pages 13--24, 2010.

Digital Library

[10]

A. Gupta and A. Rybalchenko. Invgen: An efficient invariant generator. In Proceedings of the 21st International Conference on Computer Aided Verification, CAV '09, pages 634--640, Berlin, Heidelberg, 2009. Springer-Verlag.

Digital Library

[11]

T. A. Henzinger and J. Sifakis. The embedded systems design challenge. In FM 2006: 14th International Symposium on Formal Methods, LNCS 4085, pages 1--15, 2006.

Digital Library

[12]

M. I. Jordan and R. A. Jacobs. Hierarchical mixtures of experts and the em algorithm. Neural Comput., 6(2):181--214, Mar. 1994.

Digital Library

[13]

A. Juloski, W. Heemels, and G. Ferrari-Trecate. Data-based hybrid modelling of the component placement process in pick-and-place machines. Control Engineering Practice, 12(10):1241--1252, 2004. Analysis and Design of Hybrid Systems.

[14]

A. Juloski, S. Weiland, and W. P. M. H. Heemels. A bayesian approach to identification of hybrid systems. Automatic Control, IEEE Transactions on, 50(10):1520--1533, Oct 2005.

[15]

A. Magnani and S. Boyd. Convex piecewise-linear fitting. Optimization and Engineering, 10(1):1--17, 2009.

[16]

K. L. McMillan. An interpolating theorem prover. Theor. Comput. Sci., 345(1):101--121, Nov. 2005.

Digital Library

[17]

N. Megiddo. On the complexity of polyhedral separability. Discrete Comput Geom, 3:325--337, 1988.

Digital Library

[18]

N. Megiddo and A. Tamir. On the complexity of locating linear facilities in the plane. Oper. Res. Lett., 1(5):194--197, Nov. 1982.

Digital Library

[19]

S. Paoletti, A. L. Juloski, G. Ferrari-Trecate, and R. Vidal. Identification of hybrid systems a tutorial. European Journal of Control, 13(2-3):242--260, 2007.

[20]

J. Roll, A. Bemporad, and L. Ljung. Identification of piecewise affine systems via mixed-integer programming. Automatica, 40(1):37--50, 2004.

Digital Library

[21]

R. Vidal, S. Soatto, Y. Ma, and S. Sastry. An algebraic geometric approach to the identification of a class of linear hybrid systems. In Decision and Control, 2003. Proceedings. 42nd IEEE Conference on, volume 1, pages 167--172 Vol.1, Dec 2003.

Cited By

Xue BLiu YMa LZhang XSun MXie X(2019)Safe Inputs Approximation for Black-Box Systems2019 24th International Conference on Engineering of Complex Computer Systems (ICECCS)10.1109/ICECCS.2019.00027(180-189)Online publication date: Nov-2019
https://doi.org/10.1109/ICECCS.2019.00027
Nayyer MRaza IHussain S(2018)A Survey of Cloudlet-Based Mobile Augmentation Approaches for Resource OptimizationACM Computing Surveys10.1145/324173851:5(1-28)Online publication date: 19-Nov-2018
https://dl.acm.org/doi/10.1145/3241738
Both ADuckham MWorboys M(2018)Identifying Surrounds and Engulfs Relations in Mobile and Coordinate-Free Geosensor NetworksACM Transactions on Spatial Algorithms and Systems10.1145/32345054:2(1-21)Online publication date: 10-Aug-2018
https://dl.acm.org/doi/10.1145/3234505
Show More Cited By

Index Terms

Precise piecewise affine models from input-output data
1. Computer systems organization
  1. Embedded and cyber-physical systems
  2. Real-time systems
2. Computing methodologies
  1. Modeling and simulation
    1. Model development and analysis
      1. Model verification and validation

Recommendations

Nonlinear regression with piecewise affine models based on RBFN
ICANN'05: Proceedings of the 15th international conference on Artificial neural networks: formal models and their applications - Volume Part II

In this paper, a modeling method of high dimensional piecewise affine models is proposed. Because the model interpolates the outputs at the orthogonal grid points in the input space, the shape of the piecewise affine model is easily understood. The ...
Test data compression based on input-output dependence

We use the fact that outputs of a large circuit depend on proper subsets of the circuit inputs to provide test data compression on the input side. The compressed input test data consists of patterns of length equal to the maximum number of inputs on ...
Input-Output Tools: A Language Facility for Interactive and Real-Time Systems

A conceptual model is discussed which allows the hierarchic definition of high-level input driven objects, called input-output tools, from any set of basic input primitives. An input-output tool is defined as a named object. Its most important elements ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

EMSOFT '14: Proceedings of the 14th International Conference on Embedded Software

October 2014

301 pages

ISBN:9781450330527

DOI:10.1145/2656045

Program Chairs:
Tulika Mitra
National University of Singapore, Singapore
,
Jan Reineke
Saarland University, Germany

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGBED: ACM Special Interest Group on Embedded Systems
SIGDA: ACM Special Interest Group on Design Automation
IEEE CAS
IEEE Council on Electronic Design Automation (CEDA)
SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 October 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

ESWEEK'14

Sponsor:

ESWEEK'14: TENTH EMBEDDED SYSTEM WEEK

October 12 - 17, 2014

New Delhi, India

Acceptance Rates

Overall Acceptance Rate 60 of 203 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
106
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Xue BLiu YMa LZhang XSun MXie X(2019)Safe Inputs Approximation for Black-Box Systems2019 24th International Conference on Engineering of Complex Computer Systems (ICECCS)10.1109/ICECCS.2019.00027(180-189)Online publication date: Nov-2019
https://doi.org/10.1109/ICECCS.2019.00027
Nayyer MRaza IHussain S(2018)A Survey of Cloudlet-Based Mobile Augmentation Approaches for Resource OptimizationACM Computing Surveys10.1145/324173851:5(1-28)Online publication date: 19-Nov-2018
https://dl.acm.org/doi/10.1145/3241738
Both ADuckham MWorboys M(2018)Identifying Surrounds and Engulfs Relations in Mobile and Coordinate-Free Geosensor NetworksACM Transactions on Spatial Algorithms and Systems10.1145/32345054:2(1-21)Online publication date: 10-Aug-2018
https://dl.acm.org/doi/10.1145/3234505
Hóu ZClouston RGoré RTiu A(2018)Modular Labelled Sequent Calculi for Abstract Separation LogicsACM Transactions on Computational Logic10.1145/319738319:2(1-35)Online publication date: 28-Apr-2018
https://dl.acm.org/doi/10.1145/3197383
Şahin SGedik B(2018)C-StreamACM Transactions on Parallel Computing10.1145/31841204:3(1-27)Online publication date: 27-Apr-2018
https://dl.acm.org/doi/10.1145/3184120
Sadraddini SBelta C(2018)Formal Guarantees in Data-Driven Model Identification and Control SynthesisProceedings of the 21st International Conference on Hybrid Systems: Computation and Control (part of CPS Week)10.1145/3178126.3178145(147-156)Online publication date: 11-Apr-2018
https://dl.acm.org/doi/10.1145/3178126.3178145
Kieroński ETendera L(2018)Finite Satisfiability of the Two-Variable Guarded Fragment with Transitive Guards and Related VariantsACM Transactions on Computational Logic10.1145/317480519:2(1-34)Online publication date: 9-Feb-2018
https://dl.acm.org/doi/10.1145/3174805
Neider DSaha SMadhusudan P(2018)Compositional Synthesis of Piece-Wise Functions by Learning ClassifiersACM Transactions on Computational Logic10.1145/317354519:2(1-23)Online publication date: 11-May-2018
https://dl.acm.org/doi/10.1145/3173545
Weinzierl MWeinzierl T(2018)Quasi-matrix-free Hybrid Multigrid on Dynamically Adaptive Cartesian GridsACM Transactions on Mathematical Software10.1145/316528044:3(1-44)Online publication date: 6-Feb-2018
https://dl.acm.org/doi/10.1145/3165280
Sanders PLamm SHübschle-Schneider LSchrade EDachsbacher C(2018)Efficient Parallel Random Sampling—Vectorized, Cache-Efficient, and OnlineACM Transactions on Mathematical Software10.1145/315773444:3(1-14)Online publication date: 3-Jan-2018
https://dl.acm.org/doi/10.1145/3157734
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten