A watering robot rides a circular rail that runs round a greenhouse. The rail is cut into n cells, numbered 0 to n - 1 in the direction of travel; after cell n - 1 comes cell 0 again. The robot's belief belief is a list of n probabilities that add up to 1: belief[i] is the probability that it is in cell i.
The robot is commanded to move u cells forward. Its wheels slip on the wet rail, so it does not always get exactly there. From whatever cell it is in, it ends up
u - 1cells further on with probabilityp_under(it undershoots),ucells further on with probabilityp_exact,u + 1cells further on with probabilityp_over(it overshoots),
and these three probabilities add up to 1.
Write move_update(belief, u, p_under, p_exact, p_over) that returns the robot's belief after the move, in cell order.
Examples
Input: belief = [0, 1, 0, 0, 0], u = 2, p_under = 0.1, p_exact = 0.8, p_over = 0.1
Output: [0.0, 0.0, 0.1, 0.8, 0.1]
Explanation: the robot was surely in cell 1; it lands in cell 2, 3 or 4.
Input: belief = [0.5, 0, 0, 0, 0.5], u = 1, p_under = 0.2, p_exact = 0.6, p_over = 0.2
Output: [0.4, 0.4, 0.1, 0.0, 0.1]
Explanation: from cell 4, one cell on is cell 0 (0.5 * 0.6 = 0.3) and two cells on is
cell 1 (0.5 * 0.2 = 0.1); from cell 0 the robot reaches cells 0, 1 and 2.
Constraints
- answers are compared with a tolerance of
1e-6; do not round
Goals
- Move every cell's probability by the commanded step, split over the possible outcomes
- Wrap positions around a circular track with the remainder operator
- See that moving spreads a belief out: the motion update is a convolution