Problem 477223 · medium · Robotics · Level 04 Belief and Optimisation

Lost on the Ring Corridor

histogram localization · Bayes filter · motion update · sense update · argmax with ties

A mail robot is switched on somewhere in a ring-shaped office corridor of n cells, numbered 0 to n - 1 in its direction of travel; after cell n - 1 comes cell 0 again. Beside each cell there is a "door" or a "wall", as given in the map world. The robot has no idea where it is, so its belief starts uniform: 1 / n for every cell.

It then makes a series of steps, each a pair (u, reading). In each step, in this order:

  1. Move. The robot is commanded u cells forward. From any cell it actually ends up u - 1 cells further on with probability p_under, u cells on with probability p_exact, or u + 1 cells on with probability p_over (these add up to 1), wrapping round the ring.
  2. Sense. Its sensor reports reading, "door" or "wall". It reports the true side of the cell the robot is in with probability p_correct, and the other one otherwise. The belief is updated with Bayes' rule and normalised to add up to 1.

After each step, the robot's best guess is the cell with the largest probability. Because floating-point sums can differ in the last digits, cells whose probability is within 1e-9 of the largest count as tied, and the best guess is then the tied cell with the smallest index.

Write localize(world, steps, p_under, p_exact, p_over, p_correct) that returns a list with one tuple (best, p_best) per step: the best guess after that step and its probability.

Examples

Input:  world = ["door", "wall", "wall", "door", "wall", "wall", "wall"],
        steps = [(1, "door"), (3, "door"), (1, "wall")],
        p_under = 0.1, p_exact = 0.8, p_over = 0.1, p_correct = 0.9
Output: [(0, 0.39130435), (3, 0.68944099), (4, 0.65058487)]
Explanation: after the first "door", cells 0 and 3 tie (0.3913 each), so the guess is
cell 0. Three cells on from cell 0 is the other door, which the second reading
confirms; from cell 3, three cells on is a wall. One more cell takes it to cell 4.

Input:  world = ["door", "wall", "door", "wall"], steps = [(1, "door"), (2, "door")],
        p_under = 0.1, p_exact = 0.8, p_over = 0.1, p_correct = 0.9
Output: [(0, 0.45), (0, 0.48121387)]
Explanation: this corridor looks the same from cell 0 and from cell 2; no reading can
tell them apart, and the two stay tied.

Constraints

  • answers are compared with a tolerance of 1e-6; do not round

Goals

  • Start from a uniform belief and alternate motion and sense updates
  • Report the best guess after every step with a tolerant tie-break
  • Watch a belief that starts flat become sharp as evidence arrives
Starting Python…