Learning the automaton of a real life system

[John Huynh]

Hi everyone,

I've been working on Learnlib for a few weeks now and currently I want to create an SUL that has no input sequences as a DFA. Instead, it should have different input sequences that have to be abstracted from a mapper in order to be learned from the learning algorithm. 

I am aware of the existence of creating an SUL via a Java class, but how can you create an SUL consisting of a few distinct states that can not be modeled by a queue, a stack or similar (like in the given examples on GitHub)?

I give you an example: Imagine a moving object that needs to have a safe distance to a wall. Let's say the object can only move forwards and backwards and has a sensor. As soon as the sensor measures a distance of 5 meters or smaller to the wall the object needs to switch to "backwards". After being in the state backwards for a certain amount of time t, it should switch back to "forwards".

So it should have two states, where it either accelerates forward or backward. As inputs, the system gets integers or floating point numbers which represent
1. the distance d to the wall when accelerating forward and
2. the time t when accelerating backwards. 

Now those input sequences have also to be mapped to an abstract input sequence for the learning algorithm to understand.

My question is: Is there a way to model such a complex scenario? If yes, how do you do it? If no, could you tell me where the limitations of Learnlib are?

Thank you very much in advance.

Yours sincerely,

John Huynh

[Markus Frohme]

Dear John,


first off, two things:

1) there is currently no formalism in LearnLib/AutomataLib that natively supports the concept of time (such as "timed automata"). So the expressiveness of your model/SUL highly depends (and varies depending) on how you abstract this concept into time-discrete input sequences.

2) When you use the SUL interface, you normally end up with learning a Mealy machine (i.e. transition-based output) instead of DFAs (state-based acceptance).


That said, the sky is the limit for how you want to abstract from your system. Regarding the choice of input and output symbols, I would suggest to choose actions for manipulating the moving object ("move forward (1sec|2sec|fast|slow)", "move backwards", etc.) as inputs and observations of the object ("valid position", "too close to wall", etc.) as outputs. Regarding what your model should express, I think two approaches could be useful: a "mode-based" automaton and a "location-based" automaton.


The mode-based automaton is similar to what you already suggested, where states essentially represent the modes "moving forward" or "moving backward". Let's say you input something like "move with 10cm/s" and your object outputs "moving forward" you would be in a forward state. However, on "move with 15cm/s" it could output "moving backwards" because you were already too close to the wall. Here, you would be in a backward state which would behave differently from the forward state for future inputs.


In the location-based approach, states represent the location of your object. This could be used if your object can be moved for certain amounts of time/distance (e.g. "move forward for 1 sec." or "move for 20 cm"). If your SUL then outputs information like "valid" / "too close to wall" your model would then tell you something like "You can more forward 4 times (for 1 sec. each) without getting to close to the wall" (because the output is "valid", "valid", "valid", "valid", "too close"). If you add things like "move left", "move right", etc. and layout the resulting automaton nicely, it would essentially represent a (2D) grid of valid locations in your environment.


I hope, I could give some inspiration.

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/f9634717-21b0-407b-8448-917079b7c72f%40googlegroups.com.

[John Huynh]

Dear Markus,

thank you very much for the detailed answer! I managed to construct a custom location-based SUL in LearnLib.

Regarding to real life systems, I still have a few questions that come along with another example that I would like to approach:

Imagine we have a ball that starts at a certain point h_max and falls until it hits the ground h_0, then bounces up to h_max again and then falls again and so on.

Certainly, we can model this example with two states 1. "falling" and 2. "rising" with the inputs h_max and h_0. 

Now, all this I simply can define in a custom java class that represents the SUL and can be learned from. The "issue" is that I have to know how the system works internally.

I would like to simulate this scenario, where I don't know the system internally and where I only get the height of the ball and the direction it is moving in per time unit.

So it should be some sort of black-box system that serves as SUL.

How could I possibly set up such an SUL and learn such a system without knowing the states of it, but only about the corresponding outputs of certain inputs? 

Kind regards,

John

> To unsubscribe from this group and stop receiving emails from it, send an email to learn...@googlegroups.com.

[Markus Frohme]

Dear John,


just two things to consider before I give my ideas:

1) Are automata the correct representation? If you take physical experiments such as your bouncy ball you usually have time-continuous functions that describe some physical properties which might be (overly) complicated to put into an automaton structure. Automata are usually good for time- (or rather "action-") discrete processes with repetitive structures (i.e. loops). However, given that you said your ball reaches h_max again, I assume it is some kind of an perpetual motion situation, so an automaton representation would be fine here.

2) Is active automata learning the correct approach? The clou about *active* automata learning is that the learner can choose inputs to a system. Let's say you want your inputs to describe the speed or direction of the ball. When you have a free-falling ball it is pretty unrealistic to change its speed or direction mid-fall. Here, maybe a passive learning approach would be more fitting, where you only observe data and try to generalize it as much as possible.


Having that said, I think the most convenient input alphabet for you experiment would be "time passed". Let's say you start your experiment and after the input "1 second" you observe "falling down". After another second you still observe "falling down" and after another one it is "bouncing up". This would pretty much be the location-based automaton approximation for your ball.

By scaling the interval you could introduce new input symbols (e.g. "0.5 seconds") which would give you a higher resolution of the ball's position. You could also output things like the downward/upward speed of the ball. However, be careful when outputting real-valued data from sensors: If they fluctuate even a little bit, they are seen as unequal outputs from an automaton perspective, so you wouldn't get a nice loop structure but just chains of individual data values. Using outputs like "moving up", "moving down" allows you to abstract from certain physical "inconveniences".


Hope this helps you a bit.


Kind regards,
Markus

[John Huynh]

Dear Markus,

I think you are right, it may not be the correct approach to learn a simulation by active automata learning. Nevertheless, I followed your suggestions and created a setup that gives me an automaton which issues a corresponding output for the input "time passed" in seconds and I can define how many seconds I want to be handled in the automaton in the alphabet (line 31 in "LearnSimulation.java").

I am layman when it comes to java programming so bear with me. I made a class called "Simulation" where I simply simulate the experiment in the method "simulate()" for a certain amount of cycles. This function returns a list of pairs that consist of the height and corresponding state. The position of the pair values correspond to the seconds passed. For example, the pair in second position gives me the height and the state the ball is in, after two seconds have passed.

In "LearnSimulation.java" I created a custom SUL that handles the seconds as inputs and outputs the corresponding state using the return values

of the "simulate()" method. The height is unused for now. I know that this whole thing won't work when I simulate less cycles than i want to have displayed in the automaton, but I just wanted to demonstrate my thoughts by sharing these files and results.

I attached the two java files I mentioned (and a pair java file which should be self-explanatory) and the final learned automaton as png.

Is my code an approach that one would usually do? Or is there something else I could improve?

Furthermore, what do I need to change in order to perform passive automata learning?

Thank you again,

Kind regards,

John

[Markus Frohme]

Dear John,


your approach was pretty much correct. There was only a small bug in your
SUL implementation: In your step function you always queried the
"input-1st" position of your simulation without acknowledging the state of
your application. For example, the second "1" input should query the
second data point of your simulation, not the first. You would need to
keep track of the elapsed time in your SUL rather than the internalState.

I uploaded an updated version [0] of the code which should give you a more
expressive model (you can play with the input alphabet or the fallDuration
parameter).


The difference of a passive approach is that for passive learning you
don't need a SUL implementation that computes outputs for given inputs on
demand but a set of (previously computed) samples that describe your
system. See our in-tree passive example [1].

Currently, LearnLib only supports one passive learning algorithm for Mealy
machines (RPNI) and for a good generalization of Mealy machines you need a
lot of data. However, given that you already mapped your observations to
RISING/FALLING, maybe a DFA interpretation (i.e. RISING = accepted,
FALLING = rejected) may be possible, too. Then you could also use the EDSM
and MDL variants of the (base) RPNI learner.


Kind regards,
Markus


[0] - https://gist.github.com/mtf90/f5f369daa0bad3c00c7e17e8a99d4f90

I simplified the SUL to generate the upward/downward motion from a sine
wave. Also, it looked like you used an older version of LearnLib
(0.12.something). The uploaded code uses the latest version 0.14.0. But
this should only concern some import statements -- you still should get
the general gist of it.

[1] -
https://github.com/LearnLib/learnlib/blob/develop/examples/src/main/java/de/learnlib/examples/passive/Example1.java

[John Huynh]

Dear Markus,

I don't think that I completely understand your code [0]. 

First of all, what do the states in the automaton represent?

Secondly, in my code, the approach was that the input (the parameter) in the step function already should represent the elapsed time. What does your input parameter represent and why is it that "elapsedTime += input" ? An Example would be awesome.

Thirdly, I don't know how the height of the ball is handled here [0] because there is no starting point the ball is falling from. Or do i miss something?

Thanks a lot.

Kind regards,

John

[John Huynh]

Hi again,

I thought about it again and I think the answer to my third point is that the fall duration of the ball is influenced by the height of the ball right?

I attached a picture that results from the simulation with the alphabet = [1,3] and fallDuration = 2. What would it mean for example when I go from state "0" to state "1" with "1/FALLING" and then from state "1" to state "2" with "1/FALLING" again? 

[Markus Frohme]

Hi John,


I'll answer both of your mails in this one:


To your third question: As I said, it is a big simplification. I do not model the height or the weight of the ball directly (which would determine its movement). Instead, I directly describe its "movement speed" by a sine function. A positive value means "bouncing up" and a negative value means "falling down".

Basically from the time frame 0 to 1 rad, the ball is falling and from 1 rad to 2 rad the ball is bouncing up again. By scaling this factor with 1/fallDuration you can determine how long the ball will fall down or bounce up (which in reality would correlate to something like adjusting the height). By calculating the modulo value I make sure to cycle through 0 to 2 rad to prevent fluctuating values due to floating point arithmetic. (Coming to think about it, it should probably say "% 2", and not "% fallDuration").

I used a sine wave to make sure that I observe a nice repetitive movement pattern that exposes loops. (We already discussed the whole issue whether automata are a good approximation for physical processes).


To your second question: Let's say the learner poses the query "i1 i2 i3". On your SUL, it would be executed as "pre() step(i1) step(i2) step(i3) post()". In order to answer the step(i2) call correctly, the system needs to remember that step(i1) was executed previously. In your example, let's say the query was "1 2 3". So you wait 1 second and then wait another 2. The step(2) would then have to return the observation after 3 seconds. But you only returned the observation after 2 seconds (or 'input' seconds in general). This is why your hypothesis always returned the single state automaton, because you didn't actually perform steps in the SUL but just returned the simple answers (basically from the initial state) to the inputs. For the bouncing ball, the easiest way to remember the state is to simply aggregate the time that has passed.


To your first question and second mail: If you take the 1/FALLING transition from the initial state of your hypothesis, you basically say "If I wait 1 second after initialization, I observe that the ball is falling" and you reach state 1. If you then take the next 1/FALLING transition (to state 2), you say "If I wait another second, the ball is still falling" and so on. However, instead of waiting 1 second twice, you can also just wait 2 seconds after initialization, which is why there is a 2/FALLING transition from state 0 to 2. The states basically give you all possible configurations, which expose a significantly different behavior for future inputs. Or the other way around: Since both two 1/* transitions and one 2/* transition reach the same state (2), they will behave identical for all future inputs.

Note that the hypothesis looks a little bit weird because if you follow only the 1/* transitions you get outputs like FFRF, which does not look like a properly bouncing ball. This is because after reaching the apex from bouncing up (i.e. speed = 0) you also output "FALLING" rather than "RISING", so the "speed > 0" test is maybe a little bit too simple. Also note that by setting the fallDuration to 2, you circumvented the above error because you actually do compute "% 2" now.


I hope that clears up some things.


Kind regards,
Markus

[John Huynh]

Dear Markus,

thank you so much! Things are much clearer now!

Kind regards,

John