introduction and implementation of Hidden Markov Model
Question: The file hmm-data.txt contains a map of a 10-by-10 2D grid-world. The most up-left cell has a coordinate of (0, 0). The ith row has a x coordinate of i, and the jth column has a y coordinate of j. The row and column indices start from 0. The free cells are represented as '1's and the obstacles are represented as '0's. 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 four 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. For tie breaking, please always prefer the one with a smaller x coordinate, and a smaller y coordinate if the x coordinates are equal.
Answer: To find the most likely trajectory in 11 time-steps, we need to determine initial possible states, start probability, transition probability and emission probability according to the example of Viterbi algorithm - Wikipedia. List V stores possibilities of appearance for each entry in 10x10 grid in time t. V[t] is a 10-by-10 2-d list of the possibilities. For t = 0, we check each cell in the grid with the first observation, i.e. the noisy distances to 4 towers, under the condition that each noisy distance d’ falls in the range [0.7d, 1.3d], in which d is the actual distance using Euclidean. We find 9 out of 100 cells fulfill the condition, and we assign emission possibility to each of them, otherwise assign 0. Since the start possibility for each of 9 cells is the same, we can assign them with 1’s. Then we initial path dictionary with each possible cell (i, j) as key and list of path [(i, j)]. For t > 0, we also need to check each cell with the t-th observation. For those who is the possible cell for time t, we further check the possibility of its last steps. For possible cell (i, j), generally the last steps could be (i-1, j), (i+1, j), (i, j-1), (i,j+1). Taking boundary and “walls” represented by 0’s in the grid into account, some of possible last steps may be excluded. For each state of the remaining candidates, its probability = V[t-1][state] * transition_prob * emission_prob, where transition probability is 1/possible_directions_from_state, and emission probability is the product of probabilities on choosing the noise distance from set of numbers in [0.7d, 1.3d] with one decimal place for each d of 4 true distances. The one with maximum probability is the best possible last step to cell (i, j). Then V[t][(i, j)] stores the probability and path[(i, j)] stores the best path to (i, j). It may occur that multiple candidates have maximum probability, so we take the one with a smaller x coordinate, or a smaller y coordinate if the x coordinates are equal.
The final result of trajectory is: [(5, 3), (6, 3), (7, 3), (8, 3), (8, 2), (7, 2), (7, 1), (6, 1), (5, 1), (4, 1), (3, 1)]