Answered by:
Infer.net used in Wumpus World? (Migrated from community.research.microsoft.com)
Question

Vermeulen posted on 04062009 2:37 AM
Hi, for a school project I am trying to implement simple AI for navigating around in a Wumpus World. Is Infer.net the right tool to use to implement this? And how do you think I should go about this?
Two 4x4 Bernoulli arrays I imagine basically, one for probability of a 'pit' the other for probability of a Wumpus
Friday, June 3, 2011 4:51 PM
Answers

jwinn replied on 04222009 12:19 PM
For a small model like this, inference should be virtually instantaneous even for calculating all probabilities. If you are experiencing slowdown, Infer.NET is probably recompiling the model every time, which cause significant overhead. To check, switch ShowProgress on for the inference engine and see if compilation is happening more than once.
One way to avoid this is to use the InferAll method with a list of all variables you wish to infer (as John G. hints at above). Insert a call to inferenceEngine.InferAll(arrayOfAllVariablesYouWishToInfer), before your first call to Infer() and things should speed up considerably.
For other hints on speeding up Infer.NET, see this page:
http://research.microsoft.com/enus/um/cambridge/projects/infernet/docs/improving%20the%20speed%20and%20accuracy%20of%20inference.aspxBest,
John W.
 Marked as answer by Microsoft Research Friday, June 3, 2011 4:52 PM
Friday, June 3, 2011 4:52 PM
All replies

John Guiver replied on 04062009 9:49 AM
Hi
What an excellent project! Yes, Infer.NET is a good fit here. I now have a working model that gives probabilities of pit and wumpus given observations to date (wumpus, pit, breeze, and stench). As this is a school project, I don't want to give too much away, but I am happy to work with you on this, either publically in the forum, or via the Infer.NET support alias.
To start with, we want to define the variables. My model has the following (working in C#):
Variable<int> wumpusPosition = Variable.Random<int>(Discrete.Uniform(25));
Variable<bool>[,] hasPit = new Variable<bool>[5, 5];
Variable<bool>[,] hasWumpus = new Variable<bool>[5, 5];
Variable<bool>[,] hasBreeze = new Variable<bool>[5, 5];
Variable<bool>[,] hasStench = new Variable<bool>[5, 5];These are dotNet arrays rather than Infer.NET arrays, as Ranges are not applicable here. The next thing to do is to specify the model by writing down the relationships between the variables at each position. The one between hasWumpus and wumpusPosition is a bit tricky. hasBreeze is defined from the neighbouring random variables for hasPit (similarly for stench and wumpus). I'll let you have a go at this before saying more.
Once your model is in place, you can specify observations for Pit, Wumpus, Breeze, and Stench based on which squares you have visited. You can then infer Pit and Wumpus probabilities for unvisited squares.
What is the timeframe for this project?
Regards
John G
Friday, June 3, 2011 4:51 PM 
Vermeulen replied on 04062009 4:14 PM
hey John, thanks for the quick and detailed response
I have set up my model (very close to that, although the variables are in a Square struct, and there is a 4x4 array of squares), and figured out the hasBreeze/hasStrench parts.
What I am stuck on though is the infering probability for the unvisited squares. Would you be able to go into more detail on that?
The main idea for the project is to use Wumpus World AI to test out randomly generated Wumpus World levels, then use a search function to find hardest (yet beatable) levels using this AI. The main idea of the project is more to do with evolutionary algorithms than dealing with uncertainity, but I thought this would be the best way to tackle the AI.
Thanks again,
 Lee
Friday, June 3, 2011 4:51 PM 
Vermeulen replied on 04062009 4:16 PM
Oh and as for the timeline, I'll be working on it for the next few days. It's somewhat part of a larger term project
Friday, June 3, 2011 4:51 PM 
John Guiver replied on 04072009 3:57 AM
I am wondering why are you using a 4x4. The web site I was looking at shows a 5x5  I just want to make sure that we are on the same page...
Going with my variable definitions for now, the first bit of the model sets the prior for whether a cell has a pit or not. There can be any number of pits as drawn from a Bernoulli prior with a probability of 0.2. The Wumpus is different in that there can only be one Wumpus, and therefore we encode its position drawing from a uniform Discrete prior over 25 (5x5) possible positions. However, we would like a posterior probability of a Wumpus being on a particualr square, so the second bit of the model below encodes that as a Bernoulli distributed variable for each square.
for (int i=0; i < 5; i++)
{
for (int j=0; j < 5; j++)
{
hasPit[i, j] = Variable.Bernoulli(0.2);
hasWumpus[i, j] = (wumpusPosition == i + (j * 5));
}
}
The next bit of model, as hinted at yesterday represents the neighbourhood relationships between breeze and pit, and between stench and Wumpus. So for example, the corner cases encoded as follows:// Corner cases
hasBreeze[0, 0] = hasPit[0, 1]  hasPit[1, 0]; hasStench[0, 0] = hasWumpus[0, 1]  hasWumpus[1, 0];
hasBreeze[0, 4] = hasPit[0, 3]  hasPit[1, 4]; hasStench[0, 4] = hasWumpus[0, 3]  hasWumpus[1, 4];
hasBreeze[4, 0] = hasPit[4, 1]  hasPit[3, 0]; hasStench[4, 0] = hasWumpus[4, 1]  hasWumpus[3, 0];
hasBreeze[4, 4] = hasPit[4, 3]  hasPit[3, 4]; hasStench[4, 4] = hasWumpus[4, 3]  hasWumpus[3, 4];The edge cases and the nonedge cases can be similarly represented, though with three and four neighbours respectively.
At this point the model is complete, and you need to do inference. As you step through Wumpus world, you will need to write down the observations. After each new observation, you can run inference again. For example:
// Square (0,0)
hasBreeze[0, 0].ObservedValue = true;
hasStench[0, 0].ObservedValue = false;
hasPit[0, 0].ObservedValue = false;
hasWumpus[0, 0].ObservedValue = false;
// Square (1,0)
hasBreeze[1, 0].ObservedValue = false;
hasStench[1, 0].ObservedValue = true;
hasPit[1, 0].ObservedValue = false;
hasWumpus[1, 0].ObservedValue = false;You can get the inferred posterior distributions for values by creating an inference engine and calling the Infer method. For example, continuing the above game, you are currently at square (1,0) and are interested in the posterior probabilities for hasPit and has hasWumpus at (2,0) and (1,1). The code for this is:
InferenceEngine ie = new InferenceEngine();
Bernoulli postPit20 = ie.Infer<Bernoulli>(hasPit[2, 0]);
Bernoulli postPit11 = ie.Infer<Bernoulli>(hasPit[1, 1]);
Bernoulli postWumpus20 = ie.Infer<Bernoulli>(hasWumpus[2, 0]);
Bernoulli postWumpus11 = ie.Infer<Bernoulli>(hasWumpus[1, 1]);
At any step, you could choose to either get the probabilties for just the neighbouring squares, or for the whole grid. If you get the probabilties for the whole grid, there are a couple of caveats. One is that each inference you do as above will recompile the model and that will be excessive for 25 inferences; there is a way to stop this happening (the InferAll method) but I won't get into that now. The second is that, with the current release, trying to infer an observed variable (i.e. a variable in a square that you have visited) it will return an error  of course the outcomes for these square are known, so this isn't a problem, but your code will need to check for this.Let me know how you get on.
John G.
Friday, June 3, 2011 4:51 PM 
minka replied on 04072009 7:42 AM
I assume that the recompiles happen because hasPit and hasWumpus are not connected. You can avoid such recompiles by creating separate InferenceEngines to infer hasPit and hasWumpus.
Friday, June 3, 2011 4:51 PM 
John Guiver replied on 04082009 3:34 AM
Yes, thanks Tom. That is the main reason why the recompiles happen, and having separate engines for the pit and wumpus certainly makes a big difference. If you are just interested in the inferences in the neighbourhood of your position then this suffices.
If, at each step, you want to recover inferences at all grid squares then some recompiles still happen as you iterate across the grid and come across new squares which didn't affect inference in previous squares. For this case, InferAll does the trick.
John
Friday, June 3, 2011 4:51 PM 
Vermeulen replied on 04212009 8:12 AM
Hey again,
I just wanted to thank you again for your help, I got the application working perfectly and Infer.net is working great.
I didn't expect the performance of the program to drop so heavily though, I knew bayesian networks were fairly bad for that but I expected a small slowdown. At the start of the map I am calculating all probabilities, then only calculating for the adjacent squares when the player is moving throughout the map
Thanks again,
Lee
Friday, June 3, 2011 4:52 PM 
jwinn replied on 04222009 12:19 PM
For a small model like this, inference should be virtually instantaneous even for calculating all probabilities. If you are experiencing slowdown, Infer.NET is probably recompiling the model every time, which cause significant overhead. To check, switch ShowProgress on for the inference engine and see if compilation is happening more than once.
One way to avoid this is to use the InferAll method with a list of all variables you wish to infer (as John G. hints at above). Insert a call to inferenceEngine.InferAll(arrayOfAllVariablesYouWishToInfer), before your first call to Infer() and things should speed up considerably.
For other hints on speeding up Infer.NET, see this page:
http://research.microsoft.com/enus/um/cambridge/projects/infernet/docs/improving%20the%20speed%20and%20accuracy%20of%20inference.aspxBest,
John W.
 Marked as answer by Microsoft Research Friday, June 3, 2011 4:52 PM
Friday, June 3, 2011 4:52 PM