Introduction to Artificial Inteligence

Goals

Probabilistic reasoning using Bayes networks, with scenarios similar to the EU refugee problem environment of assignment 1.

Uncertain EU Refugee Problem - Domain Description

As they try to find their best path, in the real world, the refugees do not know with certainty the location of the Border police. Pinpointing their locations is important for the refugees (in order to avoid them). However, it is known that the police tend to be in border locations, and also sometimes at locations with food so as to try to capture the refugees. The border locations are known, but food locations are also uncertain. Sometimes information about them becomes available due to tweets by other refugees.

Our probabilistic model is: food pacakges are independently generated at vertices with a certain probability depending on the known vertex identity v, a probability Pr(v). Thus we have a binary random variable standing in for the existence of food at node v, with the obvious prior distribution. In each vertex v, border police occur randomly based on whether there is food at v and neighboring nodes, and whether v is a border node. Thus we have one binary random variable for existence of police at each vertex, depending on the food variables in the relevant nodes (as stated above) and the type of node (border or non-border), with a noisy or conditional distribution.

The causal strength of the noisy-or distributions is as follows: the probability of police given no food anywhere near is 0.5 for a border node. The probability of police for a non-border node, with food in this node but no food in any of the neighbors is 0.3. Probability of policy for a non-border node with no food, and exactly one neighbor with food is 0.2. Probability of leakage (spontaneous appearance) is 0.1. This is all for the "standard" refugee policy. However, if the Hungarian government chooses to enforce a crackdown, the probability of police at all border nodes (given no food) increases to 0.8. Whether or not there is a crackdown is also a random "Policy" variable, which is "standard" with probability Ps and "crackdown" with probability 1-Ps.

All in all, you have 3 types of variables (BN nodes): food (one for each vertex), Police (one for each vertex), and Policy.

In your program, a file specifies the geometry (graph), and parameters such as Ps. Then, you enter some locations where food and police are reported either present or absent (and the rest remain unknown). This is the evidence in the problem. Once evidence is instantiated, you need to perform reasoning about the likely locations of police:

1. What is the probability that each of the vertices contains police?
2. What is the probability that a certain path (set of vertices) is free from police? (Note that the distributions of police in vertices are NOT necessarily independent.)
3. What is the path from a given location to a goal that has the highest probability of being free from police? (bonus)

Input can be as an ASCII file, similar to graph descriptions in previous assignments, for example:

#V 4    ; number of vertices n in graph (from 1 to n)

#V 1 N 0.4  ; Vertex 1, non-border node, probability of food 0.4
#V 2 B 0.2  ; Vertex 2, border node, probability of food 0.2


#E 1 2 W1 ; Edge between vertices 1 and 2, weight 1
#E 2 3 W3 ; Edge between vertices 2 and 3, weight 3
#E 3 4 W3 ; Edge between vertices 3 and 4, weight 3
#E 2 4 W4 ; Edge between vertices 2 and 4, weight 4

#Goal V3  ; To be used in optional bonus, if applicable

Requirements

Your program should read the data, including the distribution parameters, which are defined as above. The program should construct a Bayes network according to the scenario. The program should also allow for an output of the Bayes network constructed for the scenario.

For example, part of the output for the above graph, for the parameter values Ps = 0.9, would be:

VERTEX 1: food
  P(food) = 0.4
  P(no food) = 0.6

VERTEX 1: police | food at 1, food at 2
  P(police | not food 1, not food 2) = 0.1
  P(no police | not food 1, not food 2) = 0.9

  P(police | not food 1, food 2) = 0.2
  P(no police | not food 1, food 2) = 0.8

  P(police | food 1, not food 2) = 0.3
  P(no police | food 1, not food 2) = 0.7

  P(police | food 1, food 2) = 0.44
  P(no police | food 1, food 2) = 0.56

VERTEX 2:  food
  P(food) = 0.2
  P(no food) = 0.8

VERTEX 2: police | food at 1, food at 2, food at 3
  P(police | not food 1, not food 2, not food 3) = 0.5
  P(no police | not food 1, not food 2, not food 3) = 0.5

  etc.

You should then query the user for a set of evidence. We do this by reading one piece of evidence at a time (e.g. "food reported at vertex 1", and then "food reported not to be at vertex 3" etc.). The online interactive operations your program should support are: