Introduction to Artificial Inteligence

Goals

Sequential decision making under uncertainty using belief-state MDP for decision-making: the Canadian traveller problem. There are 3 possible extensions of assignments 4 and 5, you may choose any combination.

1. Bonus 1 (3 points): dependent edges. The probability distributions of edge blocking should be provided as a Bayes network over the edge blocking variables. You need to run the same value iteration algorithm as in assignment 5, but catering for the dependent edges. In order to compute the transition probabilities in the belief-state MDP, you need to perform belief updating in the Bayes network.
2. Bonus 2 (3 points): CTP with sensing. Same as assignment 5, except that in this version, another type of action is possible: sense(e). A cost of sensing each edge should be provides in the input. The result of sensing an edge is that the agent knows with certainty whether the edge is blocked.
3. Bonus 3 (3 points): Improving the value iteration. Same as assignment 5, but improve the order of backups. This is a research assignment, you need to compare various versions of ordering (invent an ordering heuristic), and perform experiments over a number of graphs. In order to do this bonus, prior discussion with the instructor is required, esp. on the requirements of result presentation for the experiments.

Maximum available bonus: 5, except for extreme cases.

Deliverables

1. Source code and executable files of programs.
2. Explanation of the method employed in your algorithm.
3. Non-trivial example runs on at least 2 scenarios, including the input and output (except for bonus 3, which requires more scenarios).
4. Submit makefile and short description on how to run your program.

Deadline: January 20, 2011.