====== HW 01 - Bayesian update ======

===== Background =====

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.

-----

==== Occupancy Grid ====

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**.

{{ :courses:be5b99cpl:hw:hw01_og.png?nolink&450 | Occupancy grid example}}

-----

==== Bayesian update for a single grid cell ====

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**.

-----

=== General 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

-----

=== Simplified Bayesian update formula: ===

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)}
$$ 


-----

===== Assignment =====


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

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


==== Input ====

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

<code>
$ ./main m1 m2 m3 ...
</code>

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.
==== Output ====

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:

<code>
$ ./main 0 0 0
0.20000 0.05882 0.01538
</code>

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.

<code>
00000000: 302e 3230 3030 3020 302e 3035 3838 3220  0.20000 0.05882 
00000010: 302e 3031 3533 380a                      0.01538.
</code>
==== Examples ====

<note tip>
When you have a file ''pub00.in'' containing the program input, you can pass its contents to your program as command-line arguments like
<code>
$ ./main $(< pub00.in)
</code></note>

<note>
Upload your solution into [[https://cw.felk.cvut.cz/brute/|BRUTE]] as a zip archive containing only the file ''main.c''
</note>