INF552: Programming Assignment 7 [Hidden Markov Models]

INF552: Programming Assignment 7 [Hidden Markov Models]
Part 1: Implementation [7 points]
The file hmm-data.txt contains a map of a 10-by-10 2D grid-world. In it, the top-left corner cell has
coordinates (0, 0). The ith row has x coordinate i, and the jth column has y coordinate j. The row and
column indices start from 0. The free cells are represented as 1s and the obstacles are represented as 0s.
There are four towers, one in each of the four corners, as indicated in the data file. Your task is to use a
Hidden Markov Model to figure out the most likely trajectory of a robot in this grid-world. Assume that
the initial position of the robot has a uniform prior over all free cells. In each time-step, the robot moves
to one of its neighboring free cells chosen uniformly at random. At a given cell, the robot measures L2
distances (Euclidean distances) to each of the towers. For a true distance d, the robot records a noisy
measurement chosen uniformly at random from the set of numbers in the interval [0.7d, 1.3d] with one
decimal place. These measurements for 11 time-steps are also provided in the data file. You should output
the coordinates of the most likely trajectory of the robot for 11 time-steps. The Viterbi algorithm is the
recommended algorithm to use.
You can write your program in any programming language. However, you will have to implement the
algorithms yourself instead of using library functions. In your report, please provide a description of the
data structures you use, any code-level optimizations you perform, any challenges you face, and of
course, the requested outputs.
Part 2: Software Familiarization [2 points]
Do your own research and find out about library functions relevant to Hidden Markov Models. Learn
how to use them. Compare them against your implementations and suggest some ideas for how you can
improve your code. Describe all this in your report.
Part 3: Applications [1 point]
Do your own research and describe some interesting applications of Hidden Markov Models.
Submission Guidelines
In your report, please include the names of all group members and mention their individual contributions.
The report should be in PDF format. Your submission should include the code as well as the report. It is
due before 5/5, 11:59pm in an archive in zip, tar.gz or tar.xz format. Only one submission is required for
each group by one of the group members. Please submit your homework on BlackBoard (do NOT email
the homework to the instructor or the TA).