Jason Brownlee's article -- contest winner -- has just been published online.

The intent the essay is to provide a practical introduction to FSM, within the context of AI as a control technique. The emphasis is placed on practicality both in definition and explanation, rather than heavy theoretical or mathematical concepts.

Congratulations Jason, a great article. Hoping to see more of your work soon! ;) Be sure to check out the current contest for your chance to get some spotlight too!

http://ai-depot.com/FiniteStateMachines/

Good article to give a basic introduction to FSM use. However it ignores one of the big problems with FSM. That is state change occurence.

If you update your FSM, and half way through the update a trigger is generated to change the state, then continuing the update means you are updating in the incorrect state.

Defering the state change means you need a whole bunch of arbitration logic to decide which goes next.

Organising code so that the state change happens right at the end of update is difficult too, with the possibility of a sub module firing a trigger to change state.

I've yet to find a solution to this very big problem, which can get very ugly as your project becomes much larger and everything is state driven.

Hey SCA, welcome to the AI Depot.

> "means you are updating in the incorrect state"

It depends how you define your problem. If the condition still has to be true when the next state is active, then yes, it's an incorrect state. However, in practice, transitions are taken as instantaneous triggers that you follow no matter what happens after that.

It doesn't seem such a complex problem to me. You can make all your logic atomic, so that while a FSM updates happens, nothing else can change (including transition conditions).

Also, if that's not an option, just have a transition back to the originating state for the opposite condition.

Simple! Or maybe too much... What's wrong with this approach?

I have only used finite state machines in hardware design, and this is not a problem except in the rare cases where a clock signal is not used. Basically, at each rising clock edge is the only time inputs are valid, and state transitions occur between clock edges. If inputs change multiple times before a clock edge triggers a state change, only the last change is relevant. This may seem like a problem but not really, because you can design the system in order to avoid such glitches.

Rob

>It depends how you define your problem. If the condition still has >to be true when the next state is active, then yes, it's an >incorrect state. However, in practice, transitions are taken as >instantaneous triggers that you follow no matter what happens after >that.

Here in lies the problem. For example, if you have a heavily stated game which has some kind of front menu, some kind of loading screen, car runs along a track, pause brings up pause menu, crossing line brings up finish menu etc it is easy to come up with a FSM to drive all of this.

From this you have the intro state which await the "start game" trigger that takes you to loading state. When the "load complete" trigger arrives we then go to play state, and all the objects in the game are updated. However, if during play state update the car crosses the line then the trigger "end of race" appears. So a snippet of code may look like :

Simulation.UpdateAllObjects();
Hud.Update();

if(rTime<0.0f)
{
this.SendTrigger(TIMEUP,NULL);
}

if(Controller.PausePressed())
{
this.SendTrigger(PAUSEPRESSED,NULL);
}

However, if during the simulation update the car crosses the line, the trigger is fired to the game controller, the game controller switches to finish screen, so all future processing in that state is now invalid.

Problems can come from when the pause is pressed etc etc at this time.

Your code assumes that UpdateAllObjects() does not change the state, since your processing of the transitions will be the same no matter what.

You need to separate the transition checks from the state processing, and potentially also buffer the state changes. Atomicity!

Execute transitions would then prioritise all the possible transitions, and execute the most important.

>Your code assumes that UpdateAllObjects() does not change the state, >since your processing of the transitions will be the same no matter >what.

This is true but it is often very difficult to identify the functions that can lead to state change since potentially the updateplayer function could be buried much further down the list, ie

UpdateSimulator()
UpdateWorld()
UpdatePlayer()
UpdateCollision()
SendStateChangeTrigger()

Although it's kind of obvious that the player can lead to state transitions you will not always be able to identify everything down there that may change state, I have no formal way of ensuring I have caught every possible state change from all functions that I'm calling. Also as logic in the game changes, suddenly the functions that can lead to state changes also varies.

>You need to separate the transition checks from the state >processing, and potentially also buffer the state changes. Atomicity!

>StateActions();
>CheckTransitions();
>ExecuteTransitions();

Although this is all very nice with a fairly small system, in a large game this becomes quite unwieldy. State actions would update the world, the world would update the objects, the objects update the HUD, the game logic get's updated, the loading thread etc get's updated. Putting CheckTransitions in each of the thousands of functions you enter will see performance seep away >_< Not to mention the fact that several layers down you could well be in a number of different FSM's and checking triggers for them all.

In my current project I am working at quite a flat level and so every function that can possibly change state is doing what you suggest, ie :-

o) Update function A
o) Did a state transition Occur ? Yes, do no more
o) Update function B
o) Did a state transition occur ? Yes, do no more

This is feasable for a small low level part, but at higher game control states it gets tricky.

>Execute transitions would then prioritise all the possible >transitions, and execute the most important.

I've tried this before but have got huge problems from it. If you have several message requests ie Pause game, load level, end game then it's hard to decide which one you should do. Some are more critical than other's, as code changes state transitions could again change their priorities. Also you get problems whereby objects fire off triggers and then assume what they requested has happened. If the pad handler fires the trigger "go to pause menu" and then sits there awaiting "end of pause menu" to go back to ingame pad decoding, then it will sit and spin waiting for a message that never arrives.

Solution ? Best solution I can think of is using the throw/catch mechanism. Ie whenever a state transition occuers it throw's an exception identifying the FSM that transitioned. The function above attemtps to catch it, if it fails (ie the FSM is a higher level) then it throws it. If it does catch it then update is finished and bails out, no more is done, that way you avoid updating in the incorrect state.

If the exception was not caught, and instead thrown, then the higher level then attempts to catch the exception and applies the same rules.

This way as soon as a state change occurs no more processing at that level of FSM is considered, meaning no race conditions and nothing is updated in the incorrect state.

Although I'm not mad enough to attempt to get this to work in my game ^_^ However, with such a heavily stated project that I'm working on, I'm desperate for answers, cause I can see this biting us in a major way!

When an agent is active as finite state machine, how condition evaluation methods determine state transition ??

In history the finite state machines were built physically as well. Roughly they could be seen as finite in their states. But more precise there was no practical limit to support the notion finite.

Moreover there were always margins and noise at all levels. This made those FSMs unpredictable or only roughly regular, but on a bad day it could change then. Afterward a reason could be the humidity of the room for that experiment. Yes afterwards everything is easy to understand. Extrapolating to the future is knowing the future and that has no one really proved.

So the process of abstraction to a mathematical thought FSM can introduce solutions that don’t exist in physical FSMs. That transition can be evaluated is then a result of our abstraction, and then it's not given, and it can be hard to prove it.

I could tell a very simple proof of Fermat's last theorem but then physically and look what Wiles had to do. Maybe Fermat has though as well of a physical solution, so much easier to do.

Can you proof that an abstraction doesn’t introduce new phenomena and doesn’t loose connections? Can you describe what you mean with an abstraction? Can we avoid seeing through our colored glasses?

Does someone know a physical solution for the traveling salesman, who has to meet a number of cities in the shortest way. So a physical solution?

Many things run then parallel, isn’t it?

Ed

Ed vd M: In history the finite state machines were built physically as well. Roughly they could be seen as finite in their states. But more precise there was no practical limit to support the notion finite.

Quite so.

Ed vd M: Moreover there were always margins and noise at all levels. This made those FSMs unpredictable or only roughly regular, but on a bad day it could change then.

Yes, I'll agree with this. Earlier machines were unreliable and "measured" as much as computed. We use the digital system now, but there are antecedents to this - Charles Babbage used 4 states (I think) for his machine designs in the 1830s. He realised that a wheel with 4 digits is more practical, if you have to get it to work in a mechanical computer, than one with 10 digits on. Now, it is amusing to speculate - if he had a flash of genius and realised that even FOUR states was too much, that the obvious thing to do was to minimise the states as much as possible he could have replaced his wheels by levers instead and the mechanics would have been much more buildable. Maybe history could have been very different if the IT age had arrived early in this way?

Ed vd M: I could tell a very simple proof of Fermat's last theorem but then physically and look what Wiles had to do. Maybe Fermat has though as well of a physical solution, so much easier to do.

I'm not quite sure what you mean here. What would a "physical" proof of a theorem involve?

Ed vd M: Can you proof that an abstraction doesn’t introduce new phenomena and doesn’t loose connections? Can you describe what you mean with an abstraction? Can we avoid seeing through our colored glasses?

I would say we cannot, however we can show that certain features of the phenomenon in which we are interested are preserved.

Ed vd M: Does someone know a physical solution for the traveling salesman, who has to meet a number of cities in the shortest way. So a physical solution?

I presume you mean an algorithm that can obtain the solution in polynomial time? No, I don't have and I don't think it is possible. Alan Turing categorised the travelling salesman problem as NP-Complete, which means he put it in the set of problems that all need non-polynomial time to solve and are all equivalent to each other. There has never been a proof, as far as I know, that the NP-Complete problems really ARE NP, but I hold little hope of a solution.

Various approaches could be used to get round this. The most obvious, use of a massively parallel computer was suggested by Alan Turing, but this does not really address the apparent intractability of the problem: it simply swaps having the stars burn out while your program runs for having to use more matter than is actually in the universe to make it. Of course, massive parallelism could extend the number of points for which the problem can be solved, but that is all - the problem would remain NP.

One approach which may be of interest is quantum computing.

Hi Paul.

This becomes a very strange posting.

Paul: Maybe history could have been very different if the IT age had arrived early in this way?

Ed: YEESSSS!

Do your remember the 4 color problem? Computers!

Ed vd M: I could tell a very simple proof of Fermat's last theorem but then physically and look what Wiles had to do. Maybe Fermat has though as well of a physical solution, so much easier to do.

Paul: I'm not quite sure what you mean here. What would a "physical" proof of a theorem involve?

Ed: With a physical proof I mean using notions that are possible in physics. For instance when a result is possible in a physical room then the inverse will also possible in the same physical room, while in math that's not necessary. In physics the cause can’t come out of another reality. That would be very strange.

Example:

If b = a^2 and b is in that physical room then a as well. This is for math possible in R and not in Z. So in physics is less freedom then in Z-math. R doesn’t exist in physics. Also such a nice idea. Fermat's theorem is also diophantic so belonging to Z and not R. And in this way I think you can already see the physical solution.

Physics is more complete here. This has to do with the exactness of math. Maybe it's over exact. You can google for the difficult math of Bourbaki. That's maybe an awful math but also richer.

Example: Physics has not a real paradox. Achillus and the turtle of Zeno is not really solved by the reasoning with limit of our mathematical thinking.

Maths: http://www.lix.polytechnique.fr/~ilan/zeno.html

No invert the problem, then Zeno looked too short. That's much more logical. Grin.

Maye we can build a time machine and tell it him. This is for people who think mathematical time can reversed so also in reality.

Ed vd M: Can you proof that an abstraction doesn’t introduce new phenomena and doesn’t loose connections? Can you describe what you mean with an abstraction? Can we avoid seeing through our colored glasses?

Paul: I would say we cannot, however we can show that certain features of the phenomenon in which we are interested are preserved.

Ed: And the other limiting relations? What are features? Can you classify them? I think it's very difficult.

Ed: Do you know of the roughness of stochastics. The roughness is certainly true, but ever seen a paper about it. Statistics need first to know the qualitative structure. So famous scientists are also telling strange things. Example: That we live is given. And what can you read the chance we exist is very remote.

Math is thought as started with axiomata and we have built it to a gigantic monument But the step from nature to math I see still as extremely difficult.

Ed vd M: Does someone know a physical solution for the traveling salesman, who has to meet a number of cities in the shortest way. So a physical solution?

Paul: I presume you mean an algorithm that can obtain the solution in polynomial time?

Ed: I don't mean a mathematical algorithm, but, more let water stream between the cities and whoops - the solution, such kind of solution. When you like in a metaphor. But mathematically not possible in a recursive way.

Paul: No, I don't have and I don't think it is possible. Alan Turing categorized the traveling salesman problem as NP-Complete, which means he put it in the set of problems that all need non-polynomial time to solve and are all equivalent to each other. There has never been a proof, as far as I know, that the NP-Complete problems really ARE NP, but I hold little hope of a solution.

Ed: Yes indeed NP-complete but seen from the mathematical standpoint. How would a biologist react? Do you know they often think in the way of what they see? In my language - what is striking, what do I recognize; of course I can ignore all that I don't understand. Try to think in that way and you grow mad. But they talk indeed about the reality. Still we can learn a lot from them as well.

Paul: Of course, massive parallelism could extend the number of points for which the problem can be solved, but that is all - the problem would remain NP.

Ed: Water can stream everywhere. Let it just rain. Cities close to each other, the same problem, isn’t it. But this is too simple. Electronics makes a lowest resistance, but all extra connections are then a hurdle. So, alas, you have to think deeper. You see these too simple ideas involve indeed parallelism.

You can say it in this way as well: The connections between the cities are of the low level of the individual cities themselves. The shortest route (one of them) is a global notion. In the physical chaos theory started by Per bak and the Santa Fe group they talk of layers. I call them LODs levels of detail because that notion is more productive. The low LOD of the cities is regular and mathematical to think as exact. The high LOD of the solution is regular as well. But the connection between the LODs is too much, too complex, however in detail simple, but that's not the point. And then mathematical complexity behaves as physical complexity, like it has inherently margins and chaos. Many physicians see the reality as contingent.

The high LOD comes to existence with emergence. Copy physical emergence and why shouldn't you find a solution. So you let then loose the exactness finding the shortest possible way. Strange subject!

Paul: One approach which may be of interest is quantum computing

Ed: yes everything parallel. But yes how to code that. Prime divisors, is easier and that was a success already.

Not a so bad subject isn't it?

Ed

Does anybody know of a good book on software fsm design or are resources limited to numerous sparodic articles? -not to take anything away from the quality of the article written by Jason Brownlee. ;)
I'm doing a 3rd year project on them for an AI course and my knowledge is more than slightly lacking at this point!
cheers,
whybot

http://www.ai-junkie.com/architecture/state_driven/tut_state1.html

A really good tutorial. The probably only one section I disagree is the disadvantages list:
> 1. Larger systems implemented using a FSM can be difficult to manage and maintain...
> 2. Not suited to all problem domains, should only be used when a systems behaviour can be decomposed into separate states...

ad 1.: one shall use a FSM to solve one single problem, and a system of FSM (usually hierarchical) to implement a whole application of ANY complexity. The true power of (system of) FSM is really visible if the application is really complex and you compare your FSM-design with any alternative design options (UML, agile, flow chart ...). So, it&#39;s not a disadvantage, as the FSM solution for a complex problem is always easier then any alternative.

ad 2.: it&#39;s probably just imprecise stated, so here my comment: FSM is perfect for any problem where decisions have to be done, i.e. to any logic problem (so this is the FSM domain). Non-FSM domains are for example mathematical calculations.

However, based on my experience I would add one disadvantage: programmers like coding, and working with FSM means working with pictures and tables. Actually there is no need to write one line of code in any programming language to implement FSMs. FSM is well defined and its functionality is very easy. So one can design a standard piece of code - FSM executor - and serve him with FSMs specifications as tables to execute it. If the executor can correctly run a system of FSM of any size, then usually 80-95% of the complexity of the application is solved. The rest one have to implement "conventionally" are some mathematical calculations, interfaces etc. From my point of view it is a big advantage not to have to write code but...

At www.stateworks.com/active/content/en/technology/SWSystem.php one FSM executor implementation is shown. There are few other possible but this one seems to be the best at the moment, based on years of experiences. In the papers sections on same web-site several problems listed in this thread are discussed (i.e. state machine misunderstandings or hierarchical system of state machines) so it&#39;s maybe of interest as extension to this very good Jason&#39;s FSM tutorial.

Thomas