Archived

This topic is now archived and is closed to further replies.

Nelson

Markov Chains

Recommended Posts

Hi all, Recently, I read an article from Eric Dybsand (Game Devlopers conference 2001: An AI Perspective) in Gramasutra, there is AI topic I even have never heard of, "Markov chains". (BTW, I am a junior AI programmer!!)I wonder if someone can provide me some information or website regarding Markov chanins. Thanks you very much!! Nelson

Share this post


Link to post
Share on other sites
quote:
Original post by Nelson

Hi all,

Recently, I read an article from Eric Dybsand (Game Devlopers conference 2001: An AI Perspective) in Gramasutra, there is AI topic I even have never heard of, "Markov chains". (BTW, I am a junior AI programmer!!)I wonder if someone can provide me some information or website regarding Markov chanins. Thanks you very much!!

Nelson


A 5 second web search using Alta Vista revealled 6,249 hits on "Markov chains". Some of the first of them were:

http://www.ms.uky.edu/~viele/sta281f97/markov/markov.html
http://forum.swarthmore.edu/workshops/sum96/discrete/markov.html
http://www.maths.cam.ac.uk/undergrad/courseinfo/coursesIIA/text/node1.html

(I tried to pick out some of the more introductory in tone)

Also, it''s my opinion, that all AI programmers (junior or otherwise) would be well served to learn how to use a web search when they have questions like this one.

Eric

"You can give a man a fish, and feed him for a day. Or you
can teach a man to fish, and feed him for a lifetime" - Multi-Cultural Saying

Share this post


Link to post
Share on other sites
Sorry and Thanks!

I heavily rely on Yahoo, and there was only two founds. I should have tried other search engine. sorry for being so naive!! I take your message very seriously (as encouragement!!), I will learn!! Thanks! , and please teach me more!!

Nelson

Share this post


Link to post
Share on other sites
quote:
Original post by Geta
Also, it''s my opinion, that all AI programmers (junior or otherwise) would be well served to learn how to use a web search when they have questions like this one.



Agreed 100%, sometimes I feel *I* should write a FAQ for my fellow students that keep asking me for help.

BUT, there is quite a lot of material, especially as soon as you reach a certain level of education, that you just can''t really find on the Net. Introductory material, mainly.
For instance, I found tons of verbose material on Hidden Markov Models, but I still havent a freaking clue on what the damn thing is, because not a single time did I ever see a reference to introductory material...

So don''t be too snappy with beginners

youpla :-P

Share this post


Link to post
Share on other sites
quote:
Original post by ahw

BUT, there is quite a lot of material, especially as soon as you reach a certain level of education, that you just can't really find on the Net. Introductory material, mainly.
For instance, I found tons of verbose material on Hidden Markov Models, but I still havent a freaking clue on what the damn thing is, because not a single time did I ever see a reference to introductory material...

So don't be too snappy with beginners

youpla :-P




There are 3 introductory level URLs in my response above.

As to my alleged snappiness, I noticed you snipped the quote where I pointed out the benefit of learning how to learn by one's own actions? Anyway, I'm sure all readers would appreciate if you would take comments like yours to email if you feel you must jump in with a personal opinion about the style anyone uses to answer questions.

Eric


Edited by - Geta on April 29, 2001 4:03:35 PM

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
hey Eric, didn''t YOU just post a reply to the board that was a personal opinion about ahw''s message to you?

I personally (yes that means this is an opinion, are you gonna bite my head off to?) think you were pretty tough on Nelson.

I have some experience with both MM''s and HMM''s, and I can tell you I would have really appreciated it if a message board like this could have pointed me in the right direction when I was starting.

Nelson, if you''re having any problems understanding the stuff on MM''s, post back here and i''ll see if I can give you a hand.

kiev

Share this post


Link to post
Share on other sites
hey Eric, didn''t YOU just post a reply to the board that was a personal opinion about ahw''s message to you?

I personally (yes that means this is an opinion, are you gonna bite my head off to?) think you were pretty tough on Nelson.

I have some experience with both MM''s and HMM''s, and I can tell you I would have really appreciated it if a message board like this could have pointed me in the right direction when I was starting.

Nelson, if you''re having any problems understanding the stuff on MM''s, post back here and i''ll see if I can give you a hand.

kiev

Share this post


Link to post
Share on other sites
Mmm, well, I''ve just started reading GameDev.net and already I can contribute something! Cool!

This topic is not something that can be covered completely in one post. I would be happy to answer questions and continue this thread for as long as I have something to contribute.

A brief introduction to Markov Chains
(also called Markov Models, Hidden Markov Models).

Markov Chains are models for the temporal evolution of a system. Let''s start with the fundamental underlying assumption of a Markovian system.

"The future is independant of the past, given the present."

This means that any future state of the system can be entirely predicted from your present knowledge state and does not require any knowledge of the past.

Take for example the trajectory of an object. If you know its current position and velocity vector, then you can predict where it will be in the future. You don''t need to know where it was before its current state.

A Markov Chain is therefore entirely determined by two things.
1) Its initial state; and,
2) Its transition function.

The transition function is merely an operator that, given a present state, transforms the system to another state. This might be represented as a finite state machine or perhaps an analytic mathematical model. To continue the trajectory example, we may first assume linear dynamics for our object and then hold that
x(t+dt) = x(t) + v(t)*dt

(x is 1-D position and v is 1-D velocity)

More formerly and perhaps a little more correctly we would say that dx = (v) * dt, so that dx is our operator to apply to our current state. Because the system is linear we have:
x(t+dt) = x(t) + dx.

The Markov chain arises because we run this system over many such time steps. The name also arises from the fact that Markov models are often represented using Graph Models. A graph model for the trajectory problem would be:

--->[v(t-1)]--->[v(t)]--->[v(t+1)]--->
_____ \_____ \_____ \__
| | |
V v v
--->[x(t-1)]--->[x(t)]--->[x(t+1)]--->

(I really hope the arrows come out where they''re supposed to! Sorry if they don''t!!!)

Where a node in the graph [] represents a problem variable and an arrow indicates causal influence. So, for example, x(t) depends on x(t-1) and v(t-1) and on no variables at earlier time steps.

So, how could you use this concept in game development?

A common Markov Chain used in games is a finite state machine where states occur at finite time intervals. FSMs are not particularly interesting for deterministic transitions between states. You could substitute the FSM for a set of if-then rules and achieve the same thing (although perhaps less efficiently).

Markov Models become interesting when you represent the states of the system by probability distributions over the possible values of the state. Then the transition function is given as a conditional probability distribution. Such models are often called Belief Networks and when they represent systems that evolve over time, they are called Dynamic Belief Networks (DBNs).

DBNs are a very powerful tool for modelling the beliefs of agents and for modelling the evolution of a system where there is some uncertainty involved (certainly the case when your NPC is interacting with a human!).

You can find a good coverage of the topic of Markov models and Belief Networks in "An Introduction to Artificial Intelligence", Russel & Norvig (its referenced in the books section of GameDev.net).

I''d be happy to elaborate further on this topic or answer specific questions if they arise.

Regards,

Tim

Share this post


Link to post
Share on other sites
CORRECTION:

Why is it that I always get this book confused with another I have! The correct title of Stuart Russell''s book is

"Artificial Intelligence: A Modern Approach", S. Russell & P. Norvig., Prentice Hall.

There is a second edition of this book in the works, however, Stuart and his wife recently had an addition to the family, so word is that the revised edition is going slowly!

Tim

Share this post


Link to post
Share on other sites
quote:
Original post by kiev_class

hey Eric, didn''t YOU just post a reply to the board that was a personal opinion about ahw''s message to you?

I personally (yes that means this is an opinion, are you gonna bite my head off to?) think you were pretty tough on Nelson.

I have some experience with both MM''s and HMM''s, and I can tell you I would have really appreciated it if a message board like this could have pointed me in the right direction when I was starting.

Nelson, if you''re having any problems understanding the stuff on MM''s, post back here and i''ll see if I can give you a hand.

kiev




Yeah kiev, that is the problem that arises when people (ahw first, then me, and now you) begin to make personal comments to other people in public. It destroys the information exchange of the board, is rude, and should be taken to email in the first place. If you want to continue swapping personal comments, then let''s take it to email.

BTW, if providing an answer to Nelson''s question (which I did) and offering a suggestion to the programmer communitiy at-large is being "tough on Nelson" then I''m sure he''s capable of standing up and and saying so, right? I''d suspect he doesn''t really need your protection.

Anyway, I think the best thing to do is for the discussion of Markov Chains to take place here and your (and mine, and anyone else''s) personal comments should go to email. Don''t you?

Eric

Share this post


Link to post
Share on other sites
Well, it seems that you two (Eric and Kiev) have effectively killed this thread! 8^(

Either that or there is actually no one out there interested in Markov Models for game AI. I had considered developing an example of how to use one in a game, but I won''t bother if no one is reading this thread.

Tim

Share this post


Link to post
Share on other sites
Well, I am actually interested by your explanations, as they explain at last what a Markov Model *IS*.
I read a lot of papers on what I could use Hidden Markov Models for, but never what they freaking were... so thanks for that.

Now tell me, I am working on doing a gesture recognition system (it''s an idea I had *before* I saw Black and White )
and I have been thinking about different systems.
I found out about Hidden Markov Models, but they seem very Mathsy for me ... the other choice I have is Neural Networks, but I wonder how on earth I would do it if I allow my users to create their own new gestures... the other last solution I am considering is to try to find a way to do some pattern matching. Basically I analyze the mouse movements according to different criteria, then from that I get a "signature", and I try to match this signature with a table of existing ones; my difficulty here is to find a way to do "fuzzy matching"

So why would I use Markov Models in this context, or maybe what could they bring me ?

youpla :-P

Share this post


Link to post
Share on other sites
Quote:




Original post by ahw
Now tell me, I am working on doing a gesture recognition system (it''s an idea I had *before* I saw Black and White )
and I have been thinking about different systems.

I found out about Hidden Markov Models, but they seem very Mathsy for me...



Many of the uses of Hidden Markov Models (HMMs) to date have been in the field of engineering where they are used for monitoring (filtering) and prediction of dynamic systems. This has meant that much of what has been written has been presented solely in a mathematical context.

Over the past 10 years HMMs have been found to be a subclass of a more general model, the Dynamic Belief Network (DBN)(or sometimes called a Dynamic Bayesian Network). You will find a lot less mathematics in explanations of these networks. A good starting point for Belief Networks is, as I said, Russell and Norvig''s book. Also, there is a book by Finn Jensen. It''s titled something like "An Introduction to Bayesian Networks". It''s been some time since I picked it up so I could be out on the title. There are more advanced books on the topic however you will find that most of the material published in the field of Bayesian Networks (both static and dynamic) is published in the proceedings of the annual Uncertainty in Artificial Intelligence conference. Just do a web search for UAI proceedings.




the other choice I have is Neural Networks, but I wonder how on earth
I would do it if I allow my users to create their own new gestures... the other last solution I am considering is to try to find a way to do some pattern
matching. Basically I analyze the mouse movements according to different criteria, then from that I get a "signature", and I try to match this signature
with a table of existing ones; my difficulty here is to find a way to do "fuzzy matching"

So why would I use Markov Models in this context, or maybe what could they bring me ?




I think the correct question to ask is what is the best available model for my problem. It seems too apparent to me that many AI programmers are stuck on the buzz words of Neural Net and Genetic Algorithm. There are so many other tools out there (as you have discovered by investigating Markov Models).

It sounds to me that you want an AI tool that can recognise gestures made by the player. I presume the input devices are predominantly the mouse and perhaps the keyboard?

It is difficult to say which tool is most appropriate for the task without first knowing more about what the task is. Could you elaborate a little more on what it is you are trying to achieve and why?

You did say that you were trying to do some fuzzy pattern matching. Learning associations between input and outputs, in the presence of noise, is what artificial neural nets are good at. If this is indeed your task then you would want to investigate them further.

HMMs (and DBNs) on the other hand are useful for monitoring/filtering, prediction, diagnosis, classification, decision making under uncertainty and planning; just to name but a few applications over the past decade!

Let''s first elaborate on your problem and then we can see if ANNs or HMMs/DNBs are the most appropriate tool.

Tim

Share this post


Link to post
Share on other sites
Timkin wrote
quote:

I think the correct question to ask is what is the best available model for my problem. It seems too apparent to me that many AI programmers are stuck on the buzz words of Neural Net and Genetic Algorithm. There are so many other tools out there (as you have discovered by investigating Markov Models).



Precisely my point. I don''t want to use ANN just because it''s trendy. I am just looking for a method to solve my problem. If there is a better way to do it than using ANN, then sod it.
Now on the other hand, I am biased towards using something like ANN, because it would give me exprerience in their use. And since my Masters is on AI, this would come handy.

But to describe my idea more :
You simply record the position of the mouse while the user press the mouse button. What you get is a list of (x,y) coordinates.
Now the idea would be to observe this list under different aspects to "recognise" gestures (I don''t use the word picture, because my goal is not image recognition as such).
For instance, one thing you''ll notice is that a gesture is basically ONE line twisting in various directions, until the user release the mouse button. Right ?

First I want to normalize my values. To do that, I could use something like the total length of the segments I have drawn. Scale all the values down so that the total length of the gesture is 1.
Once I have normalized my values I want to analyze relative values, rather than absolute.
My idea is to observe the evolution of one or several parameters during the drawing of the gesture, and use this as a signature for the gesture.
For instance, if I observe the angle of the segments drawn, I get a series of angles. I can then draw a graph of the evolution of the angle, where x would be the position in the list of segments, and y the angle.
Sample this to say, 256 points, with the angle value becoming equal to a [-128 , 128] value (instead of [0,180])
And your gesture has it''s signature...

Now the problem is that when I draw something with the mouse, I will hesitate, or I will have a varying number of points, or my shape will be a bit dodgy, etc (try drawing a circle, for instance).
This is were the "fuzzy matching" comes in.
Should I use something as simple as
"Compare the values of the signature with a database of signatures, calculating a percentage of matching",
or do I go with something more complicated...

Mmmmmh.

Like I said, using ANN would be a good exercise, but if you understand what I am talking about now, you can see that there are several ways to go.
What''s your opinion.

(Oh, and since you mention Bayesian Networks, could you describe that too ... I ran into the word tons of times, but can never find a simple one-line description of what it is).

youpla :-P





Sancte Isidore ora pro nobis !

Share this post


Link to post
Share on other sites
Timkin:
I agree with Grahamr, you really should write an article about this, its a very interedting topic, and these threads don''t stay up for long.

------------------
It''s me again!

Share this post


Link to post
Share on other sites
quote:
Original post by Taharez

Timkin:
I agree with Grahamr, you really should write an article about this, its a very interedting topic, and these threads don''t stay up for long.

------------------
It''s me again!


If you are having trouble reading previous threads, then consider reseting the control at the top of the AI Forum, to show all topics (or just go back some number of days).

Eric

Share this post


Link to post
Share on other sites
Okay, it does sound like you have a pattern recognition task.

You can visualise the task as trying to match a pattern in your database to a set of pixels on the screen. That would be the lowest level at which you could perform this task. As you have indicated, you could alternatively compute a parameterisation of the pattern and try and match that to known parameterisations.

One important question: will your database of gestures be known before the player sits down to play the game? So that the AI is learning to recognise a specific gesture (basically the same as the voice recognition task. Present a word and learn how it is pronounced).
Or will it be the case that the player associates random gestures to states of the game and hence the correlations are learned by the system? Much like showing someone a picture of a chair and learning a label for it (and no one knows the word ''chair'' is an appropriate label for the object).

Tim

Share this post


Link to post
Share on other sites
quote:
Original post by grahamr

Hey, Tim. How about writing up an article for GameDev? This is a very interesting topic, and I''d love to hear more about it.




This couldn''t really be contained in a single article. It might take 2 or even 3. I''ll give some thought to a specific modelling problem in games and formulate a solution using HMMs/DBNs. I would then need to write up everything you need to understand to get to a final working model. That''s a lot of work... I''ll consider it over the weekend.

Tim


Share this post


Link to post
Share on other sites
quote:
Original post by Timkin
Okay, it does sound like you have a pattern recognition task.



Ah ! Where are simple words when I need them

Well yeah, pattern recognition. The reason I chose mouse input parametrization rather than picture recognition is because I think it''s more elegant (if only my explanations above weren''t so convoluted...)

Indeed, there is a major difference between having a limited set of gestures, which would be known at runtime; and being able to create your own gestures.
Thing is, I want the user to be able to create new gestures.
That''s where I was wondering how on Earth an ANN would accomodate that. And why I thought that "simple" pattern matching would be nicer...

Mmmmh.

youpla :-P



Sancte Isidore ora pro nobis !

Share this post


Link to post
Share on other sites
Okay, this discussion is getting off-topic for this thread, so why don''t we start another to discuss neural nets and what they can/cannot do.

On the issue of me doing an article on Markov models... okay, but it''s not something I am going to rush. It''ll take me a week or two to get it done as I am quite busy.

Hope that''s okay.

Cheers,

Tim

Share this post


Link to post
Share on other sites