Introduction to Artificial Inteligence

Goals

Probabilistic reasoning using Bayes networks, with scenarios similar to the Russian Traveller environment of assignment 1.

Russian Traveller Problem - Domain Description

(This is an obscure variant of the well-known Canadian Traveller problem.) Out for a supply detail in the russian steppes, our robot is trying to navigate the graph, and needs to reason about areas blocked by ice or fire (edges) and possible location of salt and water containers (in vertices) A map of the area is supplied (graph). Some of the area (edges Ei) may be icy, each with a known probability Pice(Ei), or on fire each with a known probability Pfire(Ei). We will assume that the ice and fire are indpendent events, thus it will be possible for an edge to contain either, both, or none.

Now, suppose that a supply drones have examined the area from the air, and deposited salt at and water containers locations adjacent to icy edges (respectively edges with fire). The drones task was defined as follows. If the vertext is not immediately adjacent to an icy edge, do not deposit any salt. However, if there is at least one icy adjacent edge, do deposit salt (i.e. basically a logical "or" gate). Likewise if the vertext is not immediately adjacent to an edge on fire, deposit a water container only with a small probability Pwater. However, if there is at least one adjacent edge on fire, always deposit water (i.e. basically a leaky logical "or" gate).

Unfortunately, the drones, which have been manufactued by Obwama Technologies Incorporated, were shipped through Yenem en route to their client in Europe in order to promote reconcilliation and world peace. Locals in the mid-way depot may have replaced some of the subsystems with peaceful non-violent freedom-fighting devices, causing the drones to behave eratically (those that don't explode on arrival, that is). Sometimes the drones forget to deposit salt or water when in fact they should, and their behaviour is "noisy or" where the "connection strength" increases with the edge weight.

Knowing this, the agent can use a sensor in order to scan a vertex, in order to discover whether any salt or water has been deposited, or whether an edge has ice or fire. The sensor output is a set of characters, one of the following combinations.

1. For an edge: (O, F, I, FI) meaning: OK, Fire, Ice, Fire and Ice, respecively.
2. For a vertex: (O, S, W, SW) meaning: nothing, Salt, Water, Salt and Water, respectively.

In your program, a file specifies the geometry (graph), In this type of environment, sensing actions are free, and all the measurements are made before any decision is made. The agent should make the following computations:

1. What is the distribution of ice and fire for each edge, given sensor readings?
2. What is the distribution of salt and water for each of the vertices, given the sensor readings?

We will assume that the locations where the sensing actions are executed are given in the input, as are the results of sensing. 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)

#E 1 2 W1 I0.1 F0.7 ; Edge between vertices 1 and 2, weight 1, ice prob 0.1, fire prob 0.7
#E 2 3 W3 I1   F0   ; Edge between vertices 2 and 3, weight 3, ice prob 1, fire prob 0
#E 3 4 W3 I0.3 F0.1 ; Edge between vertices 3 and 4, weight 3, ice prob 0.3, fire prob 0.1
#E 2 4 W4 I0.3 F0.2 ; Edge between vertices 2 and 4, weight 4, ice prob 0.3, fire prob 0.2

Note that we do not specify ice, salt, fire, and water in the map, as these are random variables, only the prior probability of ice and fire are known. The "noisy or" connection strength (i.e. Prob(salt=true|ice at edge e = true, no other edge has ice) should be (1-1/(1+w(e))). You may assume for simplicity that the degree of each vertex is no greater than a small constant (say 5). Likewise for the relationship between fire and water. Assume that the causal mechanism for depositing salt is independent of the causal mechanism for depositing water.

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 (a partial printout):

EDGE 1 2, P(ICE) = 0.01, P(FIRE) = 0.3
EDGE 2 3, P(ICE) = 1, P(FIRE) = 0
; etc.

VERTEX 1, P(V1 | E 1 2)
  P(SALT|ICE) = 0.75
  P(SALT|NO ICE) = 0            ; Leakage probability (zero for salt)

  P(WATER|FIRE) = 0.9
  P(WATER|NO FIRE) = 0.01       ; Leakage probability for water

VERTEX 4, P(V 4 | E 2 4, E 3 4) 
  P(SALT|ICE, ICE) = 0.95
  P(SALT|ICE, NO ICE) = 0.8
  P(SALT|NO ICE, ICE) = 0.75
  P(SALT|NO ICE, NO ICE) = 0     ; Leakage probability (zero for salt)

  P(WATER|FIRE, FIRE) = 0.95
  P(WATER|FIRE, NO FIRE) = 0.8
  P(WATER|NO FIRE, FIRE) = 0.75
  P(WATER|NO FIRE, NO FIRE) = 0.01  ; Leakage probability for water

; etc.

You should then query the user for a set of sensor readings. An example of the type of sensor readings provided for the above map

Edge 1 3 reading: 0
Edge 2 3 reading: F
Vertex 1 reading: SW 

Now, perform probabilistic reasoning in order to answer the questions on distribution of ice and salt, and report on the answers, including all the posterior probabilities. For example:

Posterior probabilities:
Edge 2 3 Probability of ice: 1, Probability of fire: 0
Vertex 1 Probability of salt: 1, Probability of water: 1
Vertex 2 Probability of salt: 0.7, Probability of water: 0.2
Edge 2 4 Probability of ice: 0.4, Probability of water: 0.2

etc. 

Deliverables

1. Source code and executable files of programs.
2. Explanation of the method for constructing the BN and your reasoning algorithm.
3. Non-trivial example runs on at least 2 scenarios, including the input and output.
4. Submit makefile and short description on how to run your program. i.e. how what parameters are passed to the program and how other inputs (e.g. positions of the agents known to your program) including at least one full example on how to run your program with actual input.

Due date: January 2, 2011.