Introduction to Artificial Inteligence

Goals

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

Uncertain Harassed Citizen Problem - Domain Description

As they try to find their best path, in the real world, typical citizens in a Bureaucatic tangle cannot even tell in advance what type of resource is needed to unblock a given node, if any. There may be evidence which can help, but one cannot be sure until the node in question is reached! Not knowing the blockages in advance makes it hard to plan an optimal path, so reasoning about the unknown is crucial. We know that certain types of blockage are more likely to occur if specific resources are nearby. For example, officials that want a bribe appear in places where such funds are more expected to be plentiful, such as institutions that approve large construction projects. The distribution also depends on global factors, such as political decisions to decrease the bureaucracy. It is known that Mr. Blue has promised to improve the processes for approving construction, but politicians frequently promise things without basis. Nevertheless it may be possible that such a measure, the "bureaucracy reduction law in construction" (BRC for short) will pass, which is also unknown.

Our probabilistic model is: the BRC is true with a certain probability P(BRC). Resources with a given ID are indepenently 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 each resource at node v, with the obvious prior distribution. In each vertex v, a blockage occurs randomly based on whether there is an appropriate resource at neighboring nodes, but also depending on the global BRC variable. Thus we have one binary random variable for existence of each blockage type at each vertex, depending on the resource variables in the relevant nodes (as stated above), with a noisy or conditional distribution.

The causal strength of the noisy-or distributions is as follows: the probability of blockage given no resource anywhere near is 0.01 if no BRC, and 0.001 if BRC is true. The probability of blockage of any type with no BRC and exactly one neighbor with the same resource is 0.2. With BRC this probability drops down to 0.1.

All in all, you have 3 types of variables (BN nodes): blockages (one for each vertex for each blocakge type), resources (one for each vertex for each resource type), and BRC.

In your program, a file specifies the geometry (graph), and parameters such as P(BRC). Then, you enter some locations where resources and blockages 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 blockages of each type:

1. What is the probability that each of the vertices contains a blockage of a given type?
2. What is the probability that a certain path (set of vertices) is free from blockages? (Note that the distributions of blockages 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 blockages? (bonus)

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

#PBRC  0.1    ; Probability of BRC true is 0.1
#V 4          ; number of vertices n in graph (from 1 to n)
#B 2          ; Number of different blockage IDs ([1, 2] in this case)

#V 1 K 1 0.4  ; Vertex 1, probability of key (resource) ID 1 is  0.4
#V 1 K 2 0.2  ; Vertex 1, probability of key ID 2 is  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

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, would be:

Global: BRC
  P(BRC) = 0.1
  P(no BRC) = 0.9

VERTEX 1:
  P(Key1) = 0.4
  P(not Key1) = 0.6

  P(Blockage1|BRC, no Key1 at V2) = 0.001
  P(Blockage1|BRC, Key1 at V2) = 0.1
  P(Blockage1|not BRC, no Key1 at V2) = 0.01
  P(Blockage1|not BRC, Key1 at V2) = 0.2
  P(no Blockage1|BRC, no Key1 at V2) = 0.999
  P(no Blockage1|BRC, Key1 at V2) = 0.9
  P(no Blockage1|not BRC, no Key1 at V2) = 0.99
  P(no Blockage1|not BRC, Key1 at V2) = 0.8


VERTEX 2:
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. "key ID 1 reported at vertex 2", and then "key ID 2 reported not to be at vertex 3" etc.). The online interactive operations your program should support are: