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
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
Do your own research and describe some interesting applications of Hidden Markov Models.
