CSCE 782: Problem Set 1

Due: Monday, 18 September 2006 @2:30pm

Upload Problem Set

Markov Models

For this problem set you will implement a NetLogo program that displays a randomly generated MDP and then solves it using the value iteration algorithm from Figure 1.2 in the textbook.

Your program should have sliders that let the user choose the number of states, the number of actions, and a measure of how likely an action is likely to fail and lead to another state. That is, at one extreme we have error-free (deterministic) actions always leads from one state to another. Thus, the model you generate will have a probability of 1 associated with every edge. At the other extreme each action can lead us to every state in the graph, with equal probability. Try to come up with a set of sliders that let the user choose from a wide variety of different MDP topologies.

Implementing and displaying your MDP will be made much easier if you use the new NetLogo links primitives for drawing directed graphs.

Once you can generate an MDP you will then implement the value iteration algorithm to solve the generated MDP. Your final result should also be shown graphically, perhaps by changing the color of the chosen action edges. Note also that the value iteration algorithm can be easily parallelized by asking each node to do its calculation in parallel.

Submission Instructions

As will all the problem sets, you will hand them in using our department's dropbox.

José M. Vidal
Last modified: Wed Aug 23 09:46:45 EDT 2006