Problem 414333 · hard · Robotics · Level 04 Belief and Optimisation

The Move That Tells the Most

active localization · expected entropy · information gain · histogram localization

A night-watch robot patrols a ring-shaped corridor of n cells (after cell n - 1 comes cell 0). Beside each cell there is a "door" or a "wall", as given in world. Its current belief is belief (probabilities that add up to 1). It is unsure where it is and may choose its next move from candidates, a list of whole numbers of cells (negative means backwards). Rather than move at random, it picks the move that it expects to leave it most certain.

For a candidate move u:

  • Motion. From any cell the robot ends up u - 1, u or u + 1 cells further on (wrapping round the ring) with probabilities p_back, p_exact and p_ahead, which add up to 1.
  • Sensing. After the move it reads "door" or "wall". Beside a door it reads "door" with probability p_see_door; beside a wall it reads "wall" with probability p_see_wall.

The robot does not know yet which reading it will get. For each possible reading z it can work out the probability P(z) of getting it, and the belief it would then have (Bayes' rule after the move). The expected entropy of the move is

E(u) = \sum_{z \,:\, P(z) > 0} P(z)\, H(\text{belief after moving } u \text{ and reading } z),

where H(p) = -\sum_i p_i \log_2 p_i is the entropy in bits (cells with p_i = 0 add nothing). A reading with P(z) = 0 is left out.

Write best_move(world, belief, candidates, p_back, p_exact, p_ahead, p_see_door, p_see_wall) that returns the tuple (best, scores): scores is the list of the expected entropies E(u) in the order of candidates, and best is the candidate with the smallest one. Candidates whose scores are within 1e-9 of the smallest count as tied; then the one that comes first in candidates wins.

Examples

Input:  world = ["door", "wall", "wall", "door", "door", "wall", "wall", "wall"],
        belief = [0.5, 0, 0, 0, 0.5, 0, 0, 0], candidates = [1, 2, 3],
        p_back = 0, p_exact = 1, p_ahead = 0, p_see_door = 0.9, p_see_wall = 0.9
Output: (3, [1.0, 1.0, 0.46899559])
Explanation: the robot is in cell 0 or cell 4. Moving 1 or 2 puts it beside a wall
either way, so the reading cannot help: 1 bit of doubt remains. Moving 3 puts it in
cell 3 (a door) or cell 7 (a wall), and the reading tells the two apart.

Input:  the same world and belief, candidates = [0, 1, 2, 3, -1],
        p_back = 0.1, p_exact = 0.8, p_ahead = 0.1, p_see_door = 0.85, p_see_wall = 0.95
Output: (3, [1.64178726, 1.6832312, 1.7880274, 1.37727227, 1.37727227])
Explanation: cells 0 and 4 are half the ring apart and equally likely, so 3 forward
and 1 back reach the same cells with the same probabilities, just from opposite
starting cells. They tie, and 3 comes first.

Constraints

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

Goals

  • Predict, for a move not yet made, every reading the robot might get and how likely each is
  • Average the entropy of the resulting beliefs, weighted by those probabilities
  • Pick the move that leaves the robot least uncertain on average
Starting Python…