# Assignment 7 [Hidden Markov Models]

\$30.00

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
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