Introduction to Artificial Inteligence
Assignment 7 (Bonus Assignment)
Programming assignment - Decision-making under uncertainty
Canadian Traveler Problem - Extension
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.
- 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.
- 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.
- 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
- Source code and executable files of programs.
- Explanation of the method employed in your algorithm.
- Non-trivial example runs on at least 2 scenarios,
including the input and output (except for bonus 3, which requires more
scenarios).
- Submit makefile and short description on how to run your program.
Deadline: January 20, 2011.