Introduction to Artificial Inteligence

Goals

Probabilistic reasoning using Bayes networks, with scenarios similar to the simplified Canadian 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 blocked areas (edges) and possible location of salt (vertices). A map of the area is supplied (graph). Some of the area (edges Ei) may be icy, each with a known probability P(Ei).

Now, suppose that a supply drone has examined the area from the air, and deposited salt at locations adjacent to icy edges. The drone's 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).

However, the drone has been manufactued by Nobert Technologies, owned by Liman Sisters which has since declared for chapter 11, and as a result has been known to be rather erratic. The drone is known to deposit salt at a location even when not needed, with a certain known "leakage probability" L. Also, sometimes the drone forgets to deposit salt when in fact it should, and its 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 has been deposited, or whether an edge has ice. The sensor output is binary: 1 means salt detected, 0 means no salt. (For edges, 1 means ice, 0 means no ice). We will assume in the basic exercise the sensor is precise. But only some of the vertices or edges will be scanned.

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 for each edge, sensor readings?
2. What is the distribution of salt for each of the vertices (including those for which there is no 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 W3 I0.1   ; Edge from vertex 1 to vertex 2, weight 3, ice probability 0.1
#E 2 3 W2 I1     ; Edge from vertex 2 to vertex 3, weight 2, ice probability 1
#E 3 4 W3 I0.3   ; Edge from vertex 3 to vertex 4, weight 3, ice probability 0.3
#E 2 4 W4 I0.3   ; Edge from vertex 2 to vertex 4, weight 4, ice probability 0.3

Note that we do not specify ice and salt in the map, as these are random variables, only the prior probability of ice is known. The "noisy or" 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).

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
EDGE 2 3, P(ICE) = 1
; etc.

VERTEX 1, P(V1 | E 1 2)
  P(SALT|ICE) = 0.75
  P(SALT|NO ICE) = 0.01       ; Leakage probability

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.01       ; Leakage probability

; 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: 1
Vertex 1 reading: 1 

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
Vertex 1 Probability of salt: 1
Vertex 2 Probability of salt: 0.7
Edge 2 4 Probability of ice: 0.4

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.

Deadline: December 31, 2009.