From what I can remember from my ''formal methods'' class (not much), a non-deterministic state machine is essentially a deterministic state machine underneath (a deterministic state machine with the same function can be constructed from any non-deterministic state machine).

So either of these machines definitely moves into some state, whether it is represented by a single state (DSM), or a group of states (NSM). But a fuzzy machine changes state based on probability, and is therefore different from the other two.

Of course I could be completely wrong.

quote: Original post by Argus
although I'm sure fuzzy logic deals in probabilities as well.

Sorry Argus, but Fuzzy Logic and Probabilities are most definitely not the same thing. Fuzzy Logic falls under the umbrella of truth functional (truth maintenance) systems while probability theory is a field unto itself.

The difference between the two fields can be seen by considering the rules for conjunction and disjunction of propositions...

In Fuzzy Logic:

T(A and B) = min(T(A),T(B))T(A  or B) = max(T(A),T(B))   

T(.) is the truth functional that returns a value in [0,1]

In Probability theory

P(A and B) = P(A|B)P(B)P(A  or B) = P(A)+P(B) - P(A and B)   

P(.) is a density function with the range [0,1]
P(|) is the conditional probability function
If A and B are mutually exclusive events then P(A|B) = 0

Furthermore, Fuzzy Logic is not consistent with normal propositional or First Order Logic, so that

T(A and !A) != T(True)   

This is not to say that Fuzzy Logic doesn't have a use. It's useful for describing vagueness in the states of the world (rather than uncertainty in beliefs about the state of the world, which probability theory provides).

Of course, everything that Fuzzy Logic offers is provided by probability theory, so it has fallen out of favour with many researchers.


On the question about the difference between deterministic and non-deterministic state machines. The difference between the two is in the type of information. Imagine that the state machine is in fact an agent (an agent is just something that perceives and acts).

A deterministic agent has perfect knowledge about the state of the domain (its state plus the environment state) and the outcomes of its actions are deterministic. Therefore the agent can always know with certainty where it is at the current time and where it's going to be at some future time.

A non-deterministic agent (Stochastic State Machine) has uncertainty in its knowledge of the state of the domain AND/OR in the outcomes of it's actions. Uncertainty in the state of the domain might arise because the agent did not know exactly which state it started in, or perhaps because its sensors are noisy. The agents actions dont actually put the agent in several different states, however given the model the agent has of itself and the environment, it may not be able to determine with certainty the exact outcome state (ask yourself where exactly will a ball land if thrown in the air). In this case it has uncertainty regarding it's transitions. Some or all of these factors will cause the agent to have uncertain beliefs about it's state at any time and about future states it may end up in.

This uncertainty is modelled using probability theory since it provides a complete calculus for the agent, whereas Fuzzy Logic does not.

Finally, a Fuzzy State Machine is a substitute for a Stochastic State Machine on simplistic problem domains. If you limit the domain sufficiently so that the sorts of decisions that must be made are simple responses to stimuli (a stimulus response agent), then you can get away with employing Fuzzy Logic to represent vagueness about the state of the agent and associate responses to the perceived state. This is clearly a hack because in fact the agent IS in one state and only one state, so there is no need to assign a truth value to being in that state. And before you say that "ah, the agent doesn't KNOW the truth about which state it's in", you're talking about uncertainty of beliefs, which is covered correctly by probability theory.

Fuzzy Logic should best be thought of in terms of its origins: Fuzzy Set Theory. Fuzzy Logic really dictates the degree with which something belongs in a particular set. Is John a member of the set of tall people? You can assign a truth curve, T(Height), over heights that dictates for any given height whether that person is in the set of tall people. You can do the same for all other height categories you might be interested in (short, medium, etc). When you've done that, you can pick a person and figure out (using the logic of Fuzzy Set Theory (Fuzzy Logic)) the degree with which that person belongs to each set.

A Fuzzy State Machine would then employ the outcome of this test to implement a deterministic decision. So, for example, if John was in the tall set with value 0.4, in the medium set with value 0.3 and in the short set with value 0.3, you might make a decision to call John tall since this is the maximum value achieved.

Of course, now we can see the problems with Fuzzy Logic. What is the truth value that John is both Tall and Short? 0.3 given the rules above. What is the truth value that John is Tall and not Tall? 0.4

What does this last value mean for making a decision based on whether John is Tall or not? According to this he is both! Basically, Fuzzy Logic is NOT a good decision tool. It has been used successfully in domains that are very simplistic where parameters can be tuned to give the desired affect (like thermostats!) but it doesn't scale up. If you want to implement an agent that can deal with uncertainty, then there are well established methods involving probability theory and decision theory.

Now we just need to convince game publishers/developers of this fact!

Cheers,

Timkin


[edited by - Timkin on August 1, 2002 10:20:07 PM]

quote: Original post by Timkin
What does this last value mean for making a decision based on whether John is Tall or not? According to this he is both! Basically, Fuzzy Logic is NOT a good decision tool. It has been used successfully in domains that are very simplistic where parameters can be tuned to give the desired affect (like thermostats!) but it doesn''t scale up.

Forgive me for remarking that this sounds excessively negative! You are certainly correct in that fuzzy logic probably doesn''t do a good job in making decisions in discrete domains, but I am sure there are many continuous domains in computer gaming where fuzzy logic would be an effective tool. Any kind of steering behaviour might be one example. Deciding where to place a building in an RTS might be another. Evaluating the degree of danger posed by nearby opponents in a Civilization-style game might be a 3rd. Essentially the fuzzy logic just puts a friendly rules-based face on the way you weight your inputs in order to create an output, but that''s not so different from a neural network either. If you as the designer can come up with vague rules or heuristics for your AI, and the output can be thought of as a continuous variable, then I would argue that fuzzy logic could be a very useful tool.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files ]

quote: Original post by Timkin
Sorry Argus, but Fuzzy Logic and Probabilities are most definitely not the same thing. Fuzzy Logic falls under the umbrella of truth functional (truth maintenance) systems while probability theory is a field unto itself.

Heh well I wasn''t quite equating the two, but it''s clear that I was mistaken. However, at the risk of incurring your wrath I now wish to point out the confusion that might be caused by the following :

quote: On the question about the difference between deterministic and non-deterministic state machines. The difference between the two is in the type of information. Imagine that the state machine is in fact an agent (an agent is just something that perceives and acts).

A deterministic agent has perfect knowledge about the state of the domain (its state plus the environment state) and the outcomes of its actions are deterministic. Therefore the agent can always know with certainty where it is at the current time and where it''s going to be at some future time.

A non-deterministic agent (Stochastic State Machine) has uncertainty in its knowledge of the state of the domain AND/OR in the outcomes of it''s actions.

Non-deterministic state machines are not stochastic state machines from what I understand of them, and they don''t involve probability theory. They can always be reduced to deterministic state machines. If FuSMs are what you say they are, then they are related to neither.

Just trying to avoid confusing those people who were asking about them, and again I could be quite wrong.

quote: Original post by Kylotan
Forgive me for remarking that this sounds excessively negative!

No need to ask my forgiveness! Everyone is entitled to an opinion! I may come across as negative and in many ways that''s what I intended. Fuzzy Logic IS an inappropriate tool to use for most of the situations it is applied to. It only gets applied because people don''t know of the appropriate tool, or at least don''t understand it enough to know that it is appropriate. In this case I am talking about probability/decision theory over Fuzzy Logic. Every example you suggest is better dealt with using decision theory. Indeed, it is widely recognised within academic circles that Fuzzy Logic isn''t all it was cracked up to be. But the public persona of Fuzzy Logic enables it to persist. It''s a buzz word and people like buzz words. Tell the average coder they really need to implement probability theory and the principle of maximum expected utility and they''ll just stare at you cross-eyed and go back to fragging bots. Tell them you want them to put Fuzzy Logic into their latest project and they''ll say ''cool''!

Cheers,

Timkin

quote: Original post by Argus
However, at the risk of incurring your wrath I now wish to point out the confusion that might be caused by the following

It concerns me that you think you'd incur my wrath for pointing something out, whether it was a mistake or not! I would hope that if I do make mistakes, people do point them out. I would hate to be responsible for spreading inaccurate or incorrect information.

quote: Original post by Argus
Non-deterministic state machines are not stochastic state machines from what I understand of them, and they don't involve probability theory. They can always be reduced to deterministic state machines.

Perhaps it's an issue of terminology, or that we're talking about different things. I'll explain what I mean by certain things and you can hopefully pick up either a) where our terminologies differ; or, b) where you believe I have said something incorrect.

When you say a non-deterministic FSM, I take that to mean a state machine (or map function, or transition graph, or agent function) with a number of possible states at any given time (iteration, step, etc). These possibilities may arise because the transition from one state to the next is stochastic; i.e., not deterministic, (has an element of randomness to it). This is slightly different to a state machine with a deterministic transition function but with uncertainty over which state the machine is in at t=0. However, both are described as stochastic (at least in my experience) because they both rely on probability theory to describe the state of the machine at any given time. I suspect that your usage of non-deterministic is in reference to the first form of uncertainty, being a non-deterministic transition from one state to the next. Am I correct in that presumption? If not, could you elaborate on your perspective of a non-deterministic agent please?

quote: Original post by Argus
If FuSMs are what you say they are, then they are related to neither.

I have only ever seen Fuzzy State Machines built by writing a Fuzzy Logic interface to a deterministic state machine, such that the interface maps continuous valued domain variables to a finite set of discrete decision inputs, which are then fed to the stimulus-response FSM for an action/decision outcome. Of course, as I indicate above, this is far better dealt with using probability/decision theory.

One point I forgot to mention earlier. Why would I keep pushing probability and decision theory over Fuzzy Logic? Because they offer rationality for autonomous agents, whereas Fuzzy Logic does not. An agent relying on Fuzzy Logic to make decisions cannot make rational decisions even if FL is combined with a utility measure. This is true of other truth maintenance systems and Dempster-Shafer theory (the other main alternative to probability theory, which has also fallen out of favour because of its shortcomings). These systems require hacks (from moderate to severe) to provide the ability to make rational decisions. Probability/decision theory provides rationality free of charge.

Cheers,

Timkin


[edited by - Timkin on August 2, 2002 9:30:28 PM]

quote: Original post by Timkin
Every example you suggest is better dealt with using decision theory.

Would you be able to provide a small example of how you would use decision theory to approach one of the examples I posed above? All the entry-level online tutorials I''ve read give examples of decision theory that are basically nothing more than making a discrete choice based on pre-defined probabilities. For example, how would you represent - or get around the need to represent - a fuzzy rule such as "If enemy unit is Near and enemy unit is offensive then risk is high" for a game like Civilization?

quote: Indeed, it is widely recognised within academic circles that Fuzzy Logic isn''t all it was cracked up to be. But the public persona of Fuzzy Logic enables it to persist. It''s a buzz word and people like buzz words.

Personally, I have been interested in fuzzy logic because it seems to offer a very quick and easy way of mapping rough heuristics to a reasonably high-quality output. It''s obvious just by the way they are constructed that you can''t expect fuzzy logic systems to be the most accurate way of modelling a system, but they seem efficient in terms of how accurate the system is compared to the developer time invested. They can also use quite simple fuzzy rules which are intuitive to non-mathematicians and programmers, which is potentially a big benefit in the game design world where you may want the designers to be able to shape the AI themselves.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files ]

quote: Original post by Timkin

Original post by Argus
Non-deterministic state machines are not stochastic state machines from what I understand of them, and they don''t involve probability theory. They can always be reduced to deterministic state machines.

Perhaps it''s an issue of terminology, or that we''re talking about different things. I''ll explain what I mean by certain things and you can hopefully pick up either a) where our terminologies differ; or, b) where you believe I have said something incorrect. Well, it is a difference in terminology, but in this case I think you''re using "non-deterministic" in the general sense, while when applied to state machines "non-deterministic" has a very precise meaning.

quote: When you say a non-deterministic FSM, I take that to mean a state machine (or map function, or transition graph, or agent function) with a number of possible states at any given time (iteration, step, etc). These possibilities may arise because the transition from one state to the next is stochastic; i.e., not deterministic, (has an element of randomness to it).

This is where the formal definition differs. The formal non-deterministic state machine can go to multiple states, and does so (from a conceptual standpoint). The transitions cannot be stochastic (I believe), because formal NSMs can be reduced to DSMs through techniques like subset( ? ) construction. I think you could probably look this definition up on google.

I am assuming that the persons asking were referring to the standard sense in which NSMs and DSMs are taught.

quote: For example, how would you represent - or get around the need to represent - a fuzzy rule such as "If enemy unit is Near and enemy unit is offensive then risk is high" for a game like Civilization?

Kylotan : couldn''t one represent risk level as proportional to closeness and also proportional to offensive power? Then risk level is calculated by :
(risk = closeness of enemy unit * offensive power of enemy unit)
Of course that wouldn''t be ideal in a full game, but it would represent that particular logical rule, since both closeness and offensive power are quantitative.

quote: Original post by Argus
This is where the formal definition differs. The formal non-deterministic state machine can go to multiple states, and does so (from a conceptual standpoint).

I''ve never heard non-determinism used in that vein and I would be very surprised to hear it used that with regards to this topic! Did you obtain this definition from a book or a lecturer/teacher? I''d be very much interested to know the source. The reason why I am so curious is that I have taught this material at university level and have had other academics review the course material (with no objections to the terminology or the way in which it is used)!

quote: Original post by Argus
The transitions cannot be stochastic (I believe), because formal NSMs can be reduced to DSMs through techniques like subset( ? ) construction.

Which sounds very much like a cutset , which is a method of instantiating stochastic models into sets of deterministic models, each with an appropriate prior. This method is used for approximate inference in such systems.

quote: Original post by Argus
I am assuming that the persons asking were referring to the standard sense in which NSMs and DSMs are taught.

...and this is where I would take a stand, because I don''t believe that the definition you have given above IS the standard notion of deterministic vs non-deterministic state machines.

Could you describe for me please exactly what you mean by a deterministic and a non-deterministic state machine? Let''s assume a machine that has 4 states, {A,B,C,D}. Could you given an example architecture of your DSM with 4 states and your NSM with those 4 states please?


Thanks,

Timkin

quote: Original post by Timkin

Original post by Argus
This is where the formal definition differs. The formal non-deterministic state machine can go to multiple states, and does so (from a conceptual standpoint).

I''ve never heard non-determinism used in that vein and I would be very surprised to hear it used that way, with regards to this topic! Did you obtain this definition from a book or a lecturer/teacher? I''d be very much interested to know the source. The reason why I am so curious is that I have taught this material at university level and have had other academics review the course material (with no objections to the terminology or the way in which it is used)!

quote: Original post by Argus
The transitions cannot be stochastic (I believe), because formal NSMs can be reduced to DSMs through techniques like subset( ? ) construction.

Which sounds very much like a cutset , which is a method of instantiating stochastic models into sets of deterministic models, each with an appropriate prior. This method is used for approximate inference in such systems.

quote: Original post by Argus
I am assuming that the persons asking were referring to the standard sense in which NSMs and DSMs are taught.

…and this is where I would take a stand, because I don''t believe that the definition you have given above IS the standard notion of deterministic vs non-deterministic state machines.

Could you describe for me please exactly what you mean by a deterministic and a non-deterministic state machine? Let''s assume a machine that has 4 states, {A,B,C,D}. Could you given an example architecture of your DSM with 4 states and your NSM with those 4 states please?


Thanks,

Timkin