Learning Algorithmen for Hybrid Automata

[Falk Harnisch]

Hello,

I'm not sure if this is the right place to ask, but I am currently working on a study project concerning hybrid automata learning algorithms. 

I wanted to ask if there is a ways to use LearnLib to learn said hybrid automata or if there is any implementation for this purpose available.

Best regards !

[Markus Frohme]

Dear Falk,


can you provide any reference as to what you understand under 'hybrid automata'? It's the first time I come across this term. So chances are low that LearnLib and/or AutomataLib directly supports it, but maybe you can write your own code that can re-use some of the existing infrastructure.


Kind regards,
Markus

> --
> You received this message because you are subscribed to the Google Groups "LearnLib Q&A" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to learnlib-qa...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/learnlib-qa/a564a45d-8f76-4ef6-940a-7298ea5951edn%40googlegroups.com.

[Falk Harnisch]

Hi Markus,

Thank you for having a look 😁.

With Hybrid Automata, I'm referring to those that have continuously evolving states with discrete transitions between them.
Like it's Introduced in the following paper: (PDF) An Introduction to Hybrid Automata (researchgate.net)

Best
Falk

--- Falk Harnisch · Business Administration

globaldatanet · Alter Teichweg 11-13· 22081 Hamburg

 

Mobil: +49 176 43877270

 

globaldatanet GmbH · Geschäftsführer: Marc Schröter
Sitz der Gesellschaft: Hamburg · HRB 147716 · Amtsgericht Hamburg

[Carlos Diego Nascimento Damasceno]

Falk,

 

During my Ph.D., I did some very brief experiments on learning HAs based on a paper by Medhat et al. (2015).

 

This paper proposes a framework that employs passive learning algorithms (from LearnLib) to generate Mealy Machines (FSM) from discretized IO traces of hybrid models from Matlab/Simulink programs. 

To do this, the authors rely on change-point analysis, for segmenting continuous signals into string sequences; K-means, for clustering IO segments; RPNI, to generate an FSM that provides a sort of a scaffold of the HA; and Linear regression, to estimate the continuous behavior of states. 

Maybe this work can give you some hints (e.g., other papers citing it) on proceeding with your work.

To view this discussion on the web visit https://groups.google.com/d/msgid/learnlib-qa/CAGdS_MJ%3DjZZ34AjTPgVQ0pWpLykGnG7MLw7TrSRp%2BZh1LgjpZA%40mail.gmail.com.

--

Carlos Diego Nascimento Damasceno, Ph.D.

Postdoctoral researcher @ Radboud University (iCIS)

URL: <https://damascenodiego.github.io/>

[Markus Frohme]

Dear Falk,


thanks for the information about hybrid automata. They look very interesting, but as I already suspected these behaviors are not directly supported by LearnLib/AutomataLib.

You may use existing automata (and to that extend even learning) algorithms if you can directly describe/access the properties of a hybrid automaton. For example, you can use flow-functions as node properties and jumps for transition properties, etc. The problem I see is when switching to the semantic interpretation of a HA via TTS (since you usually learn via observations). They are essentially infinite state transition systems with an infinite (continuous) input domain. There exist interfaces for infinite state transition systems in AutomataLib, but many algorithms require finite state systems.

This situation is similar to that of visibly push-down automata (VPAs, a form of regular push-down automata). They also use control locations (finite representation) but are semantically infinite state systems, since each location can be visited with arbitrary stack contents. All algorithms around VPAs (minimization, equivalence, learning, etc.) are separate implementations that specifically handle the stack semantics. I'm afraid you would have to do the same for HA.

So, you can take a look at the library if there is anything useful for you (e.g., caches) but most of the work would probably need to be done by yourself.


Kind regards,
Markus

Am Sat, Jan 08, 2022 at 12:12:38PM +0100 schrieb Falk Harnisch:
> Hi Markus,
>
> Thank you for having a look 😁.
>
> With Hybrid Automata, I'm referring to those that have
> continuously evolving states with discrete transitions between them.
> Like it's Introduced in the following paper: (PDF) An Introduction to
> Hybrid Automata (researchgate.net)

> <https://www.researchgate.net/publication/227222476_An_Introduction_to_Hybrid_Automata>
>
> Best
> Falk
>
>
> *--- Falk* Harnisch · Business Administration