Alternatives to state machine for user-definable behavior without reprogramming?

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
Hi:

I've developed a machine which implements a real-time dynamically
reconfigurable state machine.  This is done by having two sets of state
transition tables in memory, ping-pong style, then synchronously
switching from one state machine data structure to the other when it is
appropriate to do so.

Transitions are done in 2-4us on a TMS320F2812 DSC.  The output of the
state machine is waveform generation tables that produce digital
waveforms and time-domain pulses as a function of crank angle in an
engine lab experiment.  The inputs to the state machine are the cycle
count, external world input bits and button presses.  The state machine
is evaluated once per engine cycle.

The main purpose of this is that with optically accessible engines,
combustion is usually "skip-fired" so that a burn takes place only 1 in
10 cycles, for ex.  Thus, rather than make a single waveform table with
9 duplicate cycles and 1 fired, by using a state sequencing waveform
generator, only the waveforms of unique cycles need to be stored.  Also,
the state machine can modify the waveforms based on external input
conditions, which a simple sampling arbitrary waveform generator cannot do.

The only problem with this scheme is that the users are challenged by
the state machine concept, and the programmer who has to develop the
user interface (which must be backward compatible with an older system
without sequencing capability) is also "not used to thinking in the
state machine metaphor."  So he is stressed trying to figuring out how
to make a generalized user interface to this, that doesn't let the users
hang themselves.

I tend to argue that it isn't a big deal, the state graphs are usually
going to be rather simple.  I proposed some language extensions to the
old description file format that would allow access to the state machine
function in a readable way, but that was ignored.  I don't make light of
the programmer's task--it is challenging and I'd have to spend a long
time thinking about it myself to solve it.


Rather than get into the specifics of the engineering of this system,
I'm interested in simply considering if there are alternate approaches
to accomplishing the desired effect.  That is:

1.  Dynamically reconfigurable waveform tables, synchronous with the
engine cycle boundary, must have all decisions deterministically made
and internal data structures switched in 2-4 us, but frequency of this
process needing to happen is low, about 30Hz max.

2.  Absolutely glitch-free waveform table switching.

3.  No discontinuities of the waveform cycle sequence, ie., no skipped
or duplicated cycles when changing data.

4.  Make decisions on what waveforms to output based on 16-bit cycle
count, and 16-bits of external input bits.

Oh, the way waveforms are generated is by compare match interrupts with
value of a counter which is interfaced to a quadrature encoder.  This
mechanism should be retained.

I have spent considerable time studying the development of industrial
automation, robotic, machine, avionics, etc. control technology, and it
seems to be the case that the state machine concept is central and standard.

Further, that in the past 10 years, the reconfigurable (table-driven)
state machine concept has become accepted as the preferable way to
implement a state machine, if the need exists to change the state graph
without reprogramming.

Thus, I think it is likely that I have selected the best architecture
for this application.

But I am always interested to learn new ideas and consider alternative
approaches.

Any thoughts are welcome.



--
_____________________
Mr.CRC
We've slightly trimmed the long signature. Click to see the full one.
Re: Alternatives to state machine for user-definable behavior without reprogramming?
Quoted text here. Click to load it

Presumably, you mean "build the 'new' FSM while still using the 'old'
FSM and, once complete, wait for a convenient time (e.g., TDC) to
switch from one to the other -- ensuring that the 'current state'
maps conveniently into the new FSM"  (your reference to "ping pong"
left me with the impression that you were bouncing back and forth
between the two FSM's "often"/regularly)

Quoted text here. Click to load it

So, your FSM might (typically) sit in a "thumb twirling" state for
9 "cycles" before advancing to the "meat and potatoes" portion of
the machine for the "cycle that matters".

Quoted text here. Click to load it

How "general" does the interface need to be?  I.e., is it always
"skip N cycles and then run the *real* cycle"?  (trivial to
generalize)  Or, are there more convolutions involved?
(e.g., "skip N cycles UNLESS button 5 is depressed -- in which case,
run this *other* cycle instead of a 'skip' cycle")?

Quoted text here. Click to load it

You've said 30Hz -- implying ~30ms to build a new table.  But, what
is the overall latency tolerated?  I.e., if you can build tables
at 30Hz but they are 3,000 degrees out of phase, does that pose
problems?

Can the tables be pre-built and then just switched into place
at the appropriate run-times?

Quoted text here. Click to load it

Are you constraining the waveforms such that they always
"start at a fixed amplitude at a certain crank angle"?
E.g., 2.904 (or whatever) at TDC?  I.e., this solves your
problem as long as you always switch at TDC...

Quoted text here. Click to load it

See above.


You could also look into an interpreted, procedural language -- even
if it is application specific.  I recall evaluating an industrial
controller (as part of an acquisition program) many years ago that
I initially dismissed as "a toy" -- it only had a handful of
"command".  But, when my boss (knowingly) told me to "humor him"
and give it a more serious evaluation, I was stunned at how much
could be done with those few commands!  Picking a good set of commands
could mesh neatly with your application and might be more palatable
to "procedural thinkers".

Re: Alternatives to state machine for user-definable behavior without reprogramming?

[...]

Quoted text here. Click to load it

I don't think the problem is resistance to a non-procedural
programming, rather, it's resistance to having to read a manual or
apply mental effort. You must supply a user-interface where the
programming effort is reduced to that of choosing among distinct
options, setting controls, etc. An app would be ideal, but use an
Android platform to avoid having your pockets picked by Apple.

--
Joe

Re: Alternatives to state machine for user-definable behavior without reprogramming?
Hi Joe,

Quoted text here. Click to load it

Dunno.  That problem is pervasive in all application domains.
However, I *do* think that it is often easier for folks to
think of things in terms of:

do <this>
then <this>
and, if <whatever>, do <that>

Witness how confusing (non-electricians) find "ladder logic"
whereas the equivalent algorithm expressed procedurally would
be "obvious" to those same folks.

Quoted text here. Click to load it

I think the first step is finding an appropriate "mental
model" that folks can relate to.  *Then*, figuring out how
to commit that to practice -- hopefully unambiguously and
economically.

My (elided) question regarding whether any of this could be
"pre-canned" (is that redundapetitive?) was an attempt to
see how much of a "multiple choice" offering the user could
be presented.

Re: Alternatives to state machine for user-definable behavior without reprogramming?
Quoted text here. Click to load it

What you presume is correct.  The state changes within an existing FSM
can occur frequently, at up to a 3600RPM engine cycle rate, or 30Hz.
But changes to a new FSM configuration are less frequent.  New FSM data
is sent and digested casually in the background.

A nifty file system was devised to enable sending only the fragment of
the data structures that changed, then the DSC rebuilds the new FSM
configuration in the second half of mem using the changed part, and
re-copying from the running FSM the chunks that didn't change.

A large part of the user interface challenge is in dealing with
generality.  The ability to jump from one FSM to another of completely
different topology is presently permitted, although that would be atypical.

There are some controls such as whether it is permitted to transition to
a new FSM based on the current state, whether to reset the cycle count,
reset the state number, etc.  The output waveform tables of a given
state may be "single paradigm" meaning containing only the waveform for
one cycle, or "multi-paradigm" meaning containing more than one cycle of
waveforms, for a further complication.

Quoted text here. Click to load it

Yes.


It used to be that way.  Then when I proposed that waveforms could be
sequenced based on external inputs and the experiments naturally evolved,

  Or, are there more convolutions involved?
Quoted text here. Click to load it

Yes, now it is like this.  Quite a bit more difficult to can into a set
of basic templates.

Quoted text here. Click to load it

That is what is done, as described above.  This is the only way to get
the job done in 2us.  The transition table must be searched for matching
input conditions, state changed, then also check for a new FSM data set,
then re-init all the waveform table pointers with the new locations,
then be ready for the first angular waveform generation event in 2us.
And a few other things.

Quoted text here. Click to load it

I should point out that the waveforms are 32-bits of digital output, not
analog.  But effectively it is the same thing, as when a state change
occurs (switch to new waveform table) or switch to new FSM altogether,
the "phase" of the waveform must not have a discontinuity.

Quoted text here. Click to load it

I've thought about embedding Lua.  But I don't think it's feasible to
have a language interpreter doing the real-time part.  Even if it could
do *most* programs fast enough, there is no way to guarantee that the
user doesn't program something that fails to meet real-time deadlines.

That is one of the main reasons the state machine is so useful, because
it can have a guaranteed maximum evaluation time.

Alternately, is to use the programming language as the input the user
sees, but this just gets translated by the UI program into the suitable
data files.  Well, this is what we already do!  There is a text waveform
definition file, with which they don't want to loose backward
compatiblity.  On top of that they are attempting to add syntactical
elements to enable specifying FSM behavior.

I had my idea of how this might be done, but the programmer is doing it
differently.


Thanks for input.




--
_____________________
Mr.CRC
We've slightly trimmed the long signature. Click to see the full one.
Re: Alternatives to state machine for user-definable behavior without reprogramming?

Quoted text here. Click to load it

See below.


Sorry, I wasn't clear.  By "pre-built" I meant "during software
development" (I am hesitant to say "at compile time" as I want
to use that phrase elsewhere).

In other words, if your "inputs" allow you to do things like
"simulate a misfire" (hey, I don't know your application; I'm
just throwing out concepts that *might* strike a chord with you)
or "simulate a slow exhaust valve", etc.  Then, piece those
together at run-time...

Quoted text here. Click to load it

Understood.  "2.904" seemed easier to relate than "0xDeadBeef"

Quoted text here. Click to load it

Sorry, my fault, again.  I was meaning to use the interpreted language
just as a vehicle to allow a "procedurally oriented thinker" to
specify an algorithm.  Then, "your" job is to come up with a
"compiler" that converts that "program" into a FSM (or any other
representation you later might choose).

Quoted text here. Click to load it

Exactly.


I'm saying let the "user" write the FSM in a procedural language.
I suspect it would be trivial enough (the language) that you could
easily develop a "simulator" that lets the user see what *will*
happen when his "code" runs in your device.  (simulator need not
run at full speed -- in fact, it probably wants to run at "DC"
so the user can watch the engine advance through N sequential
rotations and see how the system reacts based on his 'simulated
switches/inputs')  This gives you a "contract" that you can
use between the parties (user <-> programmer):  "The simulator
said you would do blahblahblah... but you *didn't*!  Either the
simulator is broken or your *compiler* generated the wrong FSM!"

Quoted text here. Click to load it

Site Timeline