HW 01 - Bayesian update

Imagine you build a robot that moves around a room. To avoid bumping into walls, chairs, or tables, the robot needs some idea of where things are. Usually, the robot is equipped with some sensors and creates a map of the room from its sensor readings.

One simple and common way to represent the map is called an occupancy grid. These maps divide the space (in our case room) into a grid of discrete cells. For each cell, we want to know if it is occupied (something is there) or free (empty).

But the robot never knows this with 100% certainty, because the sensor readings may be noisy. So instead of just saying occupied / free, each cell is assigned a probability that the cell is occupied, given all past sensor measurements.

In this assignment, we will focus on just a single cell. You can think of it like a box. We don’t know whether something is in it, but we get a sequence of sensor readings, each telling us:

• 0 = sensor reports that the box is free
• 1 = sensor reports that the box is occupied

To estimate the probability that the box is occupied, we combine multiple sensor readings. With every new measurement, we update the probability for that box using a Bayesian update formula.

Let’s denote the probability of a cell being occupied by:

$$ P = p(cell = occupied \vert measurements) $$

When a new measurement $m \in \{0,1\}$ arrives, we update the probability $P$:

$$ P_{next} = \dfrac{p(m \vert cell = occupied) \cdot P}{p(m \vert cell = occupied) \cdot P + p(m \vert cell = free) \cdot (1-P)} $$

where:

• $p(m \vert cell = occupied)$ … probability the sensor reports $m$ when the cell is actually occupied
• $p(m \vert cell = free)$ … probability the sensor reports $m$ when the cell is actually free

For our assignment, let’s assume that the sensor is correct in 80% of cases, meaning that:

$$p(m = 1 \vert cell = occupied) = 0.8$$ $$p(m = 1 \vert cell = free) =0.2$$ $$p(m = 0 \vert cell = occupied) = 0.2$$ $$p(m = 0 \vert cell = free) =0.8$$

Plugging these values into the general formula gives us two simple update rules:

• If measurement = 1:

$$ P_{next} = \dfrac{0.8 \cdot P}{0.8 \cdot P + 0.2 \cdot (1-P)} $$

• If measurement = 0:

$$ P_{next} = \dfrac{0.2 \cdot P}{0.2 \cdot P + 0.8 \cdot (1-P)} $$

Write a C program that iteratively applies the Bayesian update to estimate the probability that a single grid cell is occupied given sensor measurements.

1. Start with an initial probability $P = 0.5$
2. For each measurement $m \in \{0,1\}$:
   • Apply the simplified Bayesian update formula to compute the new probability $P$
   • Print the updated probability

All measurement values will be given to you via the command line arguments (argv):

$ ./main m1 m2 m3 ...

where m1, m2, … are individual measurements, each equal to 0 or 1.

Your program should check that all measurements are 0 or 1. Otherwise, it should print an error message Error: Invalid input. and exit the program with a return value of 1.

Hint: use function atoi() or atof() from <stdlib.h> to convert the command-line arguments (strings) to integers/floats.

Your program should output the posterior probabilities for each iteration as a series of space-separated numbers with five digits after the decimal point, terminated by a newline. After successful processing of all the values, your program should return 0.

I.e. the command line arguments 0 0 0 should generate an output as 0.20000 0.05882 0.01538 + newline, see:

$ ./main 0 0 0
0.20000 0.05882 0.01538

Using the xxd tool, you can check the output in more detail. Notice the values 20 and 0a which are hexadecimal representations of the space and newline characters.

00000000: 302e 3230 3030 3020 302e 3035 3838 3220  0.20000 0.05882 
00000010: 302e 3031 3533 380a                      0.01538.