Probabilistic reasoning with Bayes networks for scenarios from the simplified Unreal Tournament.
We will be using the same simplified Unreal Tournament domain, modified as follows. There is only one moving agent. Initial location of flags is unknown, but there are several known locations where flags are possible. The agent can use a sensor in order to detect flags. The sensor output is binary: 0 means no flag is nearby, 1 means a flag is nearby. The sensor can detect flags within a distance of D squares. However, the sensor is noisy, with noise factor a. If there is one flag with distance d <=D from the agent, the sensor returns 1 with probability 1-(a*d). That is, a*d is the probability of a false negative. Also, sometimes the sensor gives an output of 1 even if there is no flag, and this happens with probability b (probability of false positive). With more than one flag in the detection radius, the probability of the sensor returning 1 is based on the noisy or interaction.
In your program, a file specifies the geometry (map), including locations where flags are possible (typically 2-20), and the prior probability that a flag is in that location. We will assume that the priors of flag appearances are jointly independent. The agent should move and apply the sensor, and decide on a way to best look for flags. There will be several scenario types, requiring successively more complicated skills, defined below.
In this type of environment, sensing actions are free, and all the measurements are made before any decision is made. Movement is also free, but once the agent commits to a set of flags, no change is possible. The agent should make the following decision types:
For simplicity, we will assume that the locations where the sensing actions are executed are given in the input. Input can be as an ASCII file, similar to maps in previous assignments, for example:
################## # 3 S #### ### S#### # # ### ## ###### #s 2 S # # s # 9 # # 1 s # # ##################
In the map, numbers represent potential flag locations, where the value indicates a prior probability the a flag appears in that location (e.g. 2 means probability 20% that a flag appears there). s is a location where a sensing action occured but returned 0, and S is a location where a sensing action returned 1.
In this type of scenarios, the sensor result are not given a-priori. Movement and sensing have a cost, and the agent should decide how to move and where and when to make sensing actions. The environment in this case should be treated as a POMDP. This is a bonus part of the assignment.
Your program should read the data, including the parameters a, b, D. Then, the program should construct a Bayes network according to the scenario (and print it out), and then perform probabilistic reasoning in order to answer the questions on the locations most likely to have flags, and report on the answers, including the posterior probabilities. You may use any algorithm in the literature that supports solution or approximation of non-polytree BNs, including variable elimination and sampling. If you use an approximation algorithm, the user should be allowed to determine the error margin desired, and the quality of the approximation (e.g. variance) should be output as well.
The program should also allow for an output of the Bayes network constructed for the scenario, e.g.:
Location 1 prior: flag probability 0.6
Location 2 prior: flag probability 0.3
Sensor reading 1 depends on locations: 1
Probability table:
P(1| no flag) = 0.2
P(1| flag) = 0.7
Sensor reading 2 depends on locations: 2
Probability table:
P(1| no flag, no flag) = 0.2
P(1| flag, no flag) = 0.7
P(1| no flag, flag) = 0.8
P(1| flag, flag) = 0.95
Sensor reading 3 depends on locations: (none)
P(1) = 0.2
Deadline: June 14, 2005.