Re: FuSM resources


Subject: Re: FuSM resources
From: Amit Dubey (adubey@undergrad.math.uwaterloo.ca)
Date: Sat Apr 01 2000 - 03:26:33 MET DST


In article <8c329q$d6d$1@news.netvision.net.il>,
Amit Bar-nir <barnir@elron.net> wrote:
>Hi,
>
>I'm looking for some thorough online resources explaining Fuzzy State
>Machines. Some example code would be even nicer...
>
>Anyone aware of such resources?
>
>thnx,
>Amit.

    The phrase "fuzzy state machine" is a bit of a misnomer. You may have
a bit more luck doing a web search for Markov models. Fuzzy state
machines have nothing to do with fuzzy logic.

    A bit of background: a "regular" finite state machine is a
"simple computer" that can be in _one_ of a finite number of states. You give
it input, and with each piece of input, there is a transition from the current
state to another state. You can think of it this way: imagine you had a file
on disk. A function ("the current state") will read one byte from the
disk, and it will have a case statement on that input. Each case
clause will call another function ("the next state"). The next function
then reads a byte, and this process continues.

    Simple stuff. Using a bit of handywork you can use a matrix rather
than functions and switch statements to encode a regular FSM.

    A Markov chain generalizes this. Instead of a single choice of
a function to call, there are a number of choices, each with a probability
assigned to them.

    The following C code snippet executes a two-state markov chain (or
fuzzy state machine, if you will). The input "alphabet" - the types
of input that it recognizes are simply strings made of 'A''s and 'B''s.

StateOne() {
    char c = getchar();
    if( c == 'A' ) {
        if( rand() < 0.8 ) StateOne(); // Stay in this state with 0.8 prob
        else StateTwo(); // Move to other state with 0.2 prob
    } else if( c == 'B' ) {
        if( rand() < 0.25 ) StateOne(); // Stay with 1/4 prob
        else StateTwo(); // Move with 3/4 prob
}

StateTwo() {
    char c = getchar();
    if( c == 'A' ) {
        if( rand() < 0.5 ) StateOne(); // Change state with 0.5 prob
        else StateTwo();
    }
    if( c == 'B' ) {
        StateOne(); // Always go to the other state
    }
}

    From what I understand, regular FSMs (aka regular automata) are used in
things like action games... the input in this case is the user's movement
instead of a file on disk. And each function call has a reaction for the
computer player. So, in the above code 'A' might be replaced with
"human player attacks" and 'B' might be replaced with "human player
blocks" or somthing. And instead of just making a function call, you would
add some code into the StateOne() and StateTwo() functions (like, attack
or block, or jump or whatever)... ok the probabilities are by no means
realistic, but hopefully you get the picture.

    Even cooler than Markov chains are hidden Markov chains (a kind of
Bayesian network). With this technology, given a set of actions, you can
figure out what the states are... so you can "learn" how to act. But that's
maybe not so easy to explain.

    Hope this helps.

>--
>====================================
>"We believe that life, creation,
> everything is based on mathematics"
>
> - Universal Zulu Nation
>====================================
>
>

-- 
 Amit Dubey____________________________________________________________________
 MMath Student, University of Waterloo                      adubey@netscape.net
 Comp.ai FAQ co-maintainer                                 (519) 885-1211 x3402

############################################################################ This message was posted through the fuzzy mailing list. (1) To subscribe to this mailing list, send a message body of "SUB FUZZY-MAIL myFirstName mySurname" to listproc@dbai.tuwien.ac.at (2) To unsubscribe from this mailing list, send a message body of "UNSUB FUZZY-MAIL" or "UNSUB FUZZY-MAIL yoursubscription@email.address.com" to listproc@dbai.tuwien.ac.at (3) To reach the human who maintains the list, send mail to fuzzy-owner@dbai.tuwien.ac.at (4) WWW access and other information on Fuzzy Sets and Logic see http://www.dbai.tuwien.ac.at/ftp/mlowner/fuzzy-mail.info (5) WWW archive: http://www.dbai.tuwien.ac.at/marchives/fuzzy-mail/index.html



This archive was generated by hypermail 2b25 : Thu Apr 06 2000 - 15:59:52 MET DST