The objective of this is to apply Hidden Markov Models to localization problem. Consider a robot with the task of localization (inferring where it is from the available data) given a map of the world and a sequence of percepts and actions. The robot is placed in a maze-like environment as shown in Figure.

The robot is equipped with four sonar sensors that tell whether there is an obstacle- the outer wall or a shaded square in the figure – in each of the compass directions (NSEW). We assume that the robot has a correct map. The robot performs action Move to move to one of the adjacent or neighbouring square.

X_t: state variable representing the location of the robot on the discrete grid.

dom(X_t) = {s₁,...,s_n}: domain of X_t the set of empty squares.

NEIGHBOURS(s): the set of empty squares that are adjacent to and let N(s) be the size of that set.

The transition model for Move action is given as:

Assume uniform distribution over all the squares; P(X_o= i)= 1/n.

E_t: sensor variable that can have 16 possible values, each a four-bit sequence giving the presence or absence of an obstacle in a particular compass direction.

The observation model can be given as:

ε is the sensor’s error rate and errors occur independently for the four sensor directions, (1- ε)^t is probability of getting all the four bits right and the probability of getting all of them wrong is ε^d_it, and d_it is the discrepancy that is the number of bits that are different – between true values for square i and the actual reading e_t from the sensor.

(a) First the robot needs to estimate its current location and then determine the most likely path it has taken to get where it is now for a given time t.

(b) Repeat (a) and find out the localization error as a function of number of observations for various values of (0.00, 0.02, 0.05, 0.10, 0.20) and plot them. Localization error is Manhattan distance from the true location.

(c) Repeat (b) for path accuracy, which is defined as the fraction of correct states on the Viterbi path.