Part $1$ Robot Localisation $($UG and PG$)$

Robot localization is the process of determining where a mobile robot is located concerning its environment. Robot localization

provides an answer to the question: Where is the robot now? A reliable solution to localization is one of the most fundamental

competencies required by an autonomous robot as the knowledge of the robot's location is an essential precursor to making

decisions about future actions.

In a typical robot localization scenario, a map of the environment is available and the robot is equipped with sensors that observe

the environment as well as monitor its own motion. The localization problem then becomes one of estimating the robot's position

within the map using information gathered from these sensors$.$ The following shows an example of a $2$D map drawn using ASCII

characters:

The character $\text{'}x\text{'}$ denotes an obstacle $($the path cannot be traversed$),$ while the character $\text{'}0\text{'}($Zero$)$ represents a traversable

position. Any position within the map is indicated by the coordinates $(k,j),$ where $k$ is the row number $($ordered top to bottom$)$ and $j$

is the column number $($ordered left to right$),$ starting from $1.$ For example, the top left position is $(1,1)$ and the bottom right is $(4,$

$.$

A robot moves on the map and gathers information along the way. In this version, the robot has a single non$-$deterministic Move

action and its sensors report whether or not obstacles lay immediately to the north, south, east, and west. A sequence of sensor

readings observed is the set of possible blocked directions. The following shows the example of the observed sensor readings at

each time step; which means e$.$g$.,$ at time $1,$ the north $(N),$ south $(S),$ and west $(W)$ of the robot have obstacles: $1\mathrm{.}1$ Problem Formulation

The state variable $x_t$ represents the location of the robot on the discrete grid; the domain of this variable is the set of

traversable points illustrated as $\text{'}0\text{'}$ points in the map.

Let NEIGHBORS $(i)$ be the set of traversable points that are adjacent to and let $N(i)$ be the size of that set. Then the

transition model for the Move action is defined as follows, which means the robot has an equal probability of moving to each of

its neighbors.

$P(x_{t+1}=j|x_t=i)=\{\begin{array}{ccc}\frac{1}{N}(i)& if\text{j}\text{i}\text{n}\text{N}\text{E}\text{I}\text{G}\text{H}\text{B}\text{O}\text{R}\text{S}& (i)\\ 0& \text{o}\text{t}\text{h}\text{e}\text{r}\text{w}\text{i}\text{s}\text{e}& \end{array}$

We don't know where the robot starts, so we will assume a uniform distribution over all the states; that is$,$

$P(x_0=i)=\frac{1}{K},$ where $K$ is the number of $\text{'}0\text{'}$ points in the map.

The sensor variable Et has $16$ possible values, each a four$-$bit sequence giving the presence or absence of an obstacle in each of

the compass directions $($North$,$ East, South, and West$).$ NSWE is the way of specifying the four$-$bit sequence and your program

must expand each direction in this order. For example, a four$-$bit sequence $1010$ represents that the sensors report an obstacle

on its north and west positions, while the east and south positions do not have obstacles.

The sensors$\text{'}$ error rate is $lon$ and that errors occur independently for the four sensors$.$ In that case, the probability of getting all

four bits right is $(1-lon{)}^4,$ and the probability of getting them all wrong is $lo{n}^4.$ Furthermore, if $d_{it}$ denotes the number of

directions are reporting erroneous values, then the probability that a robot at position i would receive a sensor reading $e_t($i$.$e$.,$

the observation$/$emission model$)$ is:

$P(E_t=e_t|x_t=i)=(1-lon{)}^{4-d_{it}}lo{n}^{d_{it}}$

Using the above problem formulation, you are requested to use the Viterbi forward algorithm provided below to find the Trellis

matrix. A trellis matrix gives us the probability of each state $($path in this case$)$ given each observation made by the robot's sensors$.$

For the path$($s$)$ that cannot be traversed, the probability is $0($Zero$)$ in the trellis matrix. Therefore, the trellis matrix could reflect the

possible positions of the robot. $1\mathrm{.}2$ Deliverables

Write your robot localisation program in Python $3\mathrm{.}6\mathrm{.}9$ in a file called

viterbi.py$.$ Your program must be able to run as follows:Input: Here, $[$input$]$ specifies the path to a text file. In GradeScope, the file path will be provided. Your program need to be able to

read the file in the following format:

The description of the input file to the program is as follows:

The first line indicates the size of the map $($rows by columns$).$