This assignment concerns probabilistic reasoning to estimate a quantity of interest using noisy observations acquired over time. We consider the example of an intelligent road vehicle equipped with a (noisy) sensor that needs to locate other vehicles in order to plan a safe path to its goal.
Consider a grid world with an autonomous car (with your software in its computer) moving in the presence of other cars on the road. The autonomous car (now referred to as AutoCar) needs to know the location of other cars (referred to as StdCar) in order to plan its path safely without collisions with other cars. The domain is described as follows:
Figure: The simulated 2D environment used in this assignment. The AutoCar (leftmost car) estimates a belief (multiple colours) over the positions of other 3 StdCars. ****
The environment is a 2D grid world with discrete grid cells. The grid can have cells which are occupied with obstacles. Along with the AutoCar, there can be $K$ StdCars present in the environment. The cars can move from one grid cell to another grid cell that is unoccupied. Some cars may simply be static the whole time.
The AutoCar is equipped with a microphone-like sensor that measures the loudness of another car in the vicinity. The loudness recorded in the microphone can be interpreted as a measurement of the relative distance between the AutoCar and a StdCar.
The sensor measurements are noisy. Let $z_t$ denote the measured distance. The distance is normally distributed as $z_t = \mathcal{N}(\vert \vert y_t - x_t \vert \vert_2, \sigma^{2})$, where $y_t$ and $x_t$ denote the true positions of the AutoCar and the StdCar in the grid respectively and $\sigma$ denotes the standard deviation. For example, if the relative distance is 5 grid cells then the sensor may measure the distance as 5.1, 4.0, 8.0 with decreasing probabilities.
The motion of a StdCar(s) is also uncertain. When the car takes an action (i.e., movement from one grid cell to another cell) the car may not arrive at the intended grid cell. The transition probabilities for car movement are assumed to be known.
Assume that the movement of the StdCar(s) is independent of each other. Note that in real road driving this assumption may not be true, two cars may be moving while taking the motion of each other into consideration, but such correlations can be ignored for now. The noise in the sensor measurement for each car is also assumed independent.
Our goal is to implement a probabilistic tracker (running on the AutoCar) that estimates a probability distribution (a belief) over the possible location of StdCar(s) from sensor data collected over time. Formally, we want to estimate the belief as $p(x^k_t \vert z^k_0, z^k_1, \dots z^k_t)$, where $x^k_t$ denotes the 2D location for the $k^{th}$ StdCar from the sequence of noisy observations $\{z^{k}_0, z^{k}_1, \dots z^{k}_t \}$ of the $k^{th}$ StdCar as received by the AutoCar’s sensor up to time $t$. Since, the estimated beliefs are probability distributions, they must be normalised.
Please implement an algorithm (called Estimator) to estimate the belief over the position of each StdCar(s) from the collected measurement corresponding to that car. Analyse the state space, the transition and the observation models.