Transportation researchers are trying to improve traffic in the city but, in order to do that, they first need to estimate the location of each of the cars in the city. They need our help to model this problem as an inference problem of an HMM. For this question, assume that only one car is being modeled.

a. We define the variables as follows: X, the location of the car; S, the noisy location of the car from the signal strength at a nearby cell phone tower; and G, the noisy location of the car from GPS. In our HMM model Figure S14.3, the signal-dependent location S_t not only depends on the current state X_t but also depends on the previous state X_t−1. We want to compute the belief P(x_t |s_1:t , g_1:t). In this part we consider an update that combines the dynamics and observation update in a single update. Complete the forward update expression by filling in the expression of the form:

b. We consider extending the Viterbi algorithm for the HMM from the previous part. We want to find the most likely sequence of states X_1:T given the sequence of observations s_1:T and g_1:T . Find the dynamic programming update for t > 1 for the modified HMM of the following form:

Figure S14.3

Transcribed Image Text:

P(xt $1t, 91:t) =, P(xt-181:-1,91:t-1).