Asynchronous state machines

[casella]

State machines were introduced in Modelica 3.3. A fundamental assumption in state machines is that “all parts of a state machine must have the same clock” (sect. 17.1). This works well if one wants to explicitly model a digital control system, where each state machine corresponds to a task which is periodically executed with a certain clock period. In this case, input variables from sensors are sampled by the sample() operator and output variables to actuators are sampled and held by the hold() operator. In this case, a single clock is defined for the entire state machine.

In many applications, controllers are not mainly performing continuous regulation functions, e.g. via digital PID controllers, but are rather reacting to events that only happen every now and then. In this case, explicitly representing each execution cycle of the digital control algorithm results in a very large number of time events, that can slow down the simulation dramatically. One such case is control automata on power grids, which monitor certain quantities in strategic points of the network, e.g. currents or power flows exceeding certain thresholds, and react by changing the status of control devices in the system such as breakers or tap changers. The currently available state machines cannot conveniently describe this setup, because an adequately fast reaction time forces the modeller to use a very short clock period, thus generating a lot of unnecessary time events.

The requirements for the new concept are as thus as follows:

• the state machine must be able to monitor several boolean conditions, and its transitions to react instantaneously to any of them changing its value;
• when transitions are fired, the state machine must be able to also sample other continuous input variables, e.g., if current i1 exceeds the maximum, the following course of action may depend on another current i2 being larger or smaller than a certain value in that same instant;
• it should be possible to define transitions that fire x seconds after their enabling conditions have become true, with the optional additional requirement that the condition has remained true throughout the whole time interval; in general, x can be a parameter or a discrete variable.

I suspect that it would be much more natural to build this semantics on top of discrete variables, rather than on top of event-triggered clocked variables, but I really have no precise idea how this concept could be implemented efficiently (in terms of computational effort) and conveniently (in terms of how to specify the state machine). I'll leave this up to discussion in the MAP-LANG group.

[miscco]

@gkurzbach and I discussed this earlier this morning and we couldnt really find an aggreement. The one thing we were sure about is that we should expand Event-Clocks so that we can add additional activation conditions and merge two boolean partitions.

What we also agreed was, that it should not be possible to combine two Event-Clocks by accident, so an explicit statement is needed.

We came up with two general cases:

Clock c = Clock(cond1);
activate(c, cond2);

Where c is an Event-Clocks and cond1 and cond2 are continuous-time expressions of type boolean. This would add another activation conditon to the Event-Clock c, equivalent to the following

Clock c = Clock(cond1 || cond2);

Th advantage of this approach would be that it would enable us to connect multiple inputs of boolean type to the Event clock.

The second idea was to allow merging of two Event-Clocks, which would be nice in the context of state machines, as each Clock could have its own partition initially

Clock c1 = Clock(cond1);
Clock c2 = Clock(cond2);
merge(c1, c2);

Where c1 and c2 are Event-Clocks and cond1 and cond2 are continuous-time expressions of type boolean. This would again create a single Event-Clock, but also merge the individual partitions associated with the event clocks:

Clock c = Clock(cond1 || cond2);

[HansOlsson]

As far as I can see the first two requirements (monitoring several) and sampling other signals could be made to work with minimal changes. E.g.

  Boolean b1=level1>10;
  Boolean b2=level2>5;
  Clock c=Clock(edge(b1) or edge(b2)); // Could define Clock(b1, b2) or Clock({b1, b2}) to mean this.
  Real x1=sample(level1, c);
  Real x2=sample(level2, c);

We could also define merging of clocks in a general way (instead of merging the conditions), but I don't think that a clock ticking as "merged condition" should require the clock partitions to be merged.

For the last requirement there are some other state machine variants that have it as a primitive, but I assume you could make a component with:

   Boolean b1Simple=level1>10;
   Boolean startB1;
   Real startB1End;
   Boolean b1;
equation
   when b1Simple and not pre(startB1) then
      startB1=true;
      startB1End=time+...;
  elsewhen pre(startB1) and not b1Simple then
      startB1=false;
      startB1End=time;
  end when;
  b1=startB1 and time>=startB1Time;

The problem is that this uses the old when-mechanism, and it seems weird to mix the two. One could imagine doing this with a state-machine, but the problem is that the transitions don't have a common clock (they are not even clocked) - so it would require additional changes.

[gkurzbach]

Especially in the case of state machines it could be useful to have the two event clocks separated throughout the model and still have the possibility to merge them. This could be reached by writing:

Boolean b1=activate(Clock(),cond1);
Boolean b2=activate(Clock(),cond2);

b1 and b2 are somehow connected by equations of the state graph and the clocks are determined by clock inference, which leads finally to one partition where the clocks are merged.

[HansOlsson]

I believe we need to analyze this in more detail, see #2313 for more thoughts; and would like a more detailed problem description - since I think we need to re-analyze this in detail and not add quick solutions.

Specifically having a unified clock (based on the transitions) wouldn't solve the problem of delays (i.e. waiting 5 seconds before triggering); and in general a triggered clock seems odd in combination with the current synchronous state machines.

The reason that I find it odd is that even if synchronous state-machines don't have delays they have non-immediate transitions. Such transitions are taken "the next clock tick". If the clock ticks are some form of unified triggered clock it seems as if "next clock tick" for the state-machine will be very unpredictable.

[HansOlsson]

Language group: Can in theory be handled without any language extension, see #2313.

However, there might be some efficiency to gain by not computing condition if not used - would be possible already if we didn't need to store this variable (could use HideResult?). Manually using condition=state1.active and x>0 instead of just condition=x>0 is possible, but seems like a step back.

[christoff-buerger]

[...] we should expand Event-Clocks so that we can add additional activation conditions and merge two boolean partitions.

[...] it should not be possible to combine two Event-Clocks by accident, so an explicit statement is needed.

[...] allow merging of two Event-Clocks, [...] each Clock could have its own partition initially

Clock c1 = Clock(cond1);
Clock c2 = Clock(cond2);
merge(c1, c2);

Where c1 and c2 are Event-Clocks and cond1 and cond2 are continuous-time expressions of type boolean. This would [...] create a single Event-Clock, but also merge the individual partitions associated with the event clocks:

Clock c = Clock(cond1 || cond2);

We should not support merging of clock partitions by any means. The reason is, that the clock calculus we use guarantees a well-defined partial order, which in turn is essential for many of its theoretical properties. Our very order is that you can split equation parts into sub-clocked partitions by sampling but never join such; this is for example important to guarantee termination of clock partitioning. If you could join clock partitions, we have to define fix-point semantics that are unique (minimal fix-point); if you know the Knaster–Tarski (fix-point) theorem, you are aware how horrible complicated that will be.

Instead I suggest you have a look on modelica/Modelica_Synchronous#45, which introduced logical clocks in Modelica_Synchronous that can be used to model reasoning about multiple event clocks to define a new event clock. Logical clocks should enable the kind of event processing you like.

[christoff-buerger]

@casella, @miscco, @gkurzbach: Please check my above comment.

[gkurzbach]

The original request from above is looking for an easy way to trigger clocked state machines from external continous sources. This happens all the time e.g, in a powers station. To enable this, the clocked condition of a transition has to be triggered somehow by a continous boolean condition. Therefore the the continous condition has to be converted to a clocked e.g. by a boolean Clock constructor. This needs to happen at multiple transitions to have multiple triggers. A transition with such a clock should fire only, when this particular clock ticks. To keep the property of a state machine to have only one clock (because it is a connected equations system) a new clock has to be generated which merges the different boolean clocks and ticks when any of the merged clock ticks.

I agree that this is something opposite from splitting the equation system into partitions.

But, as I see now, this can be handled by the definition of the state machine and it only needs to be defined for boolean clocks. There is no need to extend the language with new operators to support this. It is enough, to allow continous boolean conditions in transitions and to generate a common clock by combining these by { cond[1], cond[2], ... } (like in when equations) during transformation. The condition of the transition i ist converted to c[i]=tmp[i] && !previous(tmp[i]) where tmp is Boolean tmp[nTransitions]=sample(cond);

To have delayed transitions (as defined using previous(c[i]) ) in this case makes not really sense, so this can be forbidden. Instead, a real time delay (as reqested) can be implemented using the usual delay operator from the continous time domain, e.g. the user simply writes delay(condition, delayTime, delayMax) into the third argument of the transition function. There is no special handling needed by the state machine. And because it is a discrete delay it can be optimised to be not too expensive.

Having this scenario there is no need for any fixpoint iteration during analysis. There is also no need to merge clocks but instead continous conditions are merged, what is already possible. modelica/Modelica_Synchronous#45, is nice but it does not solve the problem, because it is the other way around right now. In #2313 complications with different clocks are speculated. But in this case, there is only one boolean clock. Combinations with other clocks are already checked and lead to an error during compile time.

I believe that asynchronous state machines are an important use case for state machines in general and should be covered by the standard. This would make a uniform representation possible, not requirering yet another language extension.

[HansOlsson]

To keep the property of a state machine to have only one clock (because it is a connected equations system) a new clock has to be generated which merges the different boolean clocks and ticks when any of the merged clock ticks.

The problem is that even if this is possible, it doesn't produce result that seem consistent with user expectations - since the clock ticks in the state-machine would not occur at predictable times.

In particular: some transitions in state-machines are delayed - one clock tick. What does "one clock tick" mean for this merged system? Does it make sense that a condition for a non-active transition causes a tick of the merged clocked; and thus causes delayed transitions to fire?

[gkurzbach]

The problem is that even if this is possible, it doesn't produce result that seem consistent with user expectations - since the clock ticks in the state-machine would not occur at predictable times.

Yes , it is an asynchronous state machine, meaning the ticks are not predictable as usual with boolean clocks.

In particular: some transitions in state-machines are delayed - one clock tick.

Delayed transitions in that sense will be forbidden (lead to an compile time error) when continous conditions are used.

[christoff-buerger]

A bit offtopic discussion:

modelica/Modelica_Synchronous#45, is nice but it does not solve the problem, because it is the other way around right now.

@gkurzbach: I am not sure I fully understand. You mean it goes from clock-input to clock-output but you like boolean-input to clock-output?

Assuming that is what you like, I would like to add a few comments. Logical clock combination is not boolean logic. The reason is, that it is asynchronous. The meaning of c = a and b is very different for boolean and clock logic:

• Boolean logic: c is true, if, and only if, a and b are true.
• Clock logic: c ticks, if, and only if, either a ticks and b ticked in the past since the last tick of c, or b ticks and a ticked in the past since the last tick of c.

In that sense, conjunctive clocks -- and clock logic in general -- is asynchronous; because a and b does not mean that a and b tick at the very same moment.

For that reason I am a bit skeptical if event processing can be nicely modeled with normal Boolean operations. A disjunctive clock (or) is very special because it requires no asynchronous memory; just tick if any input-event happens.

General comment on the issue

I do not like the top down approach. We have two general state-machine like libraries, that are both extreme, each in their way:

• State graph is purely continuous, supporting ordinary Boolean logic for transitions (continuous rising edges) => asynchronous
• State machines is discrete, but with exactly one clock (prohibiting arbitrary rising edges) => synchronous

In practice, I think we can find combinations in-between these two extremes. For example a train system where we can have user events (emergency break or operation mode change due to the driver pushing some button) and automatic periodic samplings like "if in emergency break mode release the wheels shortly for bla ms every bla ms to avoid stalling". I do not think such mixed systems (event processing for picking a mode, whereas each mode is a discrete state machine whose states or transitions may eject events in turn) can be modeled with either (state machines nor state graph).

Instead of going now top-down and trying to fix the one by introducing stuff from the other we maybe first write some examples purely by hand to see what is really needed. I say so, because I am sure we already have all the means required to describe such systems in Modelica; we just lack a nice library for convenient graphical modeling. I just want to propose to get to/develop such library by first doing some proper case studies and then seeing what is missing. The discussions here are to abstract for me to be convincing; with some Boolean technical encoding schemes etc it is hard to see for me how useful such redesign/joining of the libraries would be.

[gkurzbach]

A disjunctive clock (or) is very special because it requires no asynchronous memory; just tick if any input-event happens.

That's what I want. More is not necessary.

Instead of going now top-down and trying to fix the one by introducing stuff from the other we maybe first write some examples purely by hand to see what is really needed.

I agree with you. The whole thing should be more elaborated. My description above is a rough sketch of an asynchronous state machine using the synchronous extension. Maybe there is a way to have both in one machine. I think defining an asychronous machine that way opens a path in that direction. To go this further more ideas are needed. Finally it has to be done in a MCP with proper use cases. In contrast, combining the StateGraph library with Synchronous will not work well.