A hospital delivery robot drives along a corridor cut into n cells, numbered 0 to n - 1. Beside each cell the corridor has either a "door" or a plain "wall", as recorded in the map world. The robot does not know which cell it is in: its belief is a list belief of n probabilities that add up to 1, belief[i] being the probability that it is in cell i.
A side-facing sensor now reports reading, which is "door" or "wall". The sensor is not perfect:
- beside a door it reports
"door"with probabilityp_see_door(and"wall"otherwise); - beside a wall it reports
"wall"with probabilityp_see_wall(and"door"otherwise).
Write sense_update(belief, world, reading, p_see_door, p_see_wall) that returns the robot's new belief after the reading: the list of the probabilities P(\text{cell } i \mid \text{reading}), in cell order.
If the reading is impossible from every cell the robot could be in (every cell's new weight is 0), the robot admits it is lost: return the uniform belief, 1 / n for every cell.
Examples
Input: belief = [0.2, 0.2, 0.2, 0.2, 0.2],
world = ["door", "wall", "wall", "door", "wall"],
reading = "door", p_see_door = 0.8, p_see_wall = 0.9
Output: [0.42105263, 0.05263158, 0.05263158, 0.42105263, 0.05263158]
Explanation: a door cell explains "door" with probability 0.8, a wall cell with
1 - 0.9 = 0.1. The weights 0.16, 0.02, 0.02, 0.16, 0.02 add up to 0.38;
0.16 / 0.38 = 0.4211.
Input: belief = [0.0, 0.5, 0.5, 0.0, 0.0],
world = ["door", "wall", "wall", "door", "wall"],
reading = "door", p_see_door = 0.8, p_see_wall = 1.0
Output: [0.2, 0.2, 0.2, 0.2, 0.2]
Explanation: the robot was sure it stood beside a wall, and walls never read "door".
Constraints
- answers are compared with a tolerance of
1e-6; do not round
Goals
- Weight every cell's belief by how likely the reading would be from that cell
- Normalise so the new belief adds up to 1
- Decide what to do when no cell can explain the reading