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

Coloured Tiles in the Toy Shop

histogram localization · 2D grid · motion model with slip · sense update

A small demonstration robot rolls over the floor of a toy shop, which is tiled in coloured squares. The floor plan grid is a list of equal-length strings: grid[r][c] is the colour letter of the tile in row r, column c (row 0 at the top, column 0 on the left). The robot does not know where it starts: every tile is equally likely, 1 / (rows * cols).

It then makes the steps, each a pair (direction, reading). In each step, in this order:

  1. Move. The robot is commanded one tile "N" (up, row − 1), "S" (down, row + 1), "E" (right, column + 1) or "W" (left, column − 1). The floor is slippery. From any tile it

    • moves one tile in the commanded direction with probability p_move;
    • slides one tile to each side instead, with probability p_slip each: east or west for a command "N" or "S", north or south for "E" or "W";
    • stays on its tile with the remaining probability 1 - p_move - 2 * p_slip.

    The edge of the floor is a skirting board: any of these moves that would leave the grid leaves the robot on its own tile instead.

  2. Sense. A colour sensor under the robot reads a colour letter reading. The likelihood of that reading is p_hit on a tile of that colour and p_miss on any other tile. Update with Bayes' rule and normalise.

Write tile_localize(grid, steps, p_move, p_slip, p_hit, p_miss) that returns the final belief as a list of rows, belief[r][c] for each tile.

Examples

Input:  grid = ["RGB", "GBR"], steps = [("E", "B")],
        p_move = 0.8, p_slip = 0.05, p_hit = 0.9, p_miss = 0.1
Output: [[0.00704225, 0.03521127, 0.57042254],
         [0.00704225, 0.31690141, 0.06338028]]
Explanation: the blue tiles are (0, 2) and (1, 1). Moving east piles probability up
against the right edge, so (0, 2), which robots reach from (0, 1) and keep when they
bump, ends far ahead of (1, 1).

Input:  grid = ["RGB"], steps = [("N", "G")],
        p_move = 0.7, p_slip = 0.1, p_hit = 0.9, p_miss = 0.2
Output: [[0.15384615, 0.69230769, 0.15384615]]
Explanation: in a single row, "N" always bumps; only the sideways slips move anything.

Constraints

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

Goals

  • Run the histogram filter on a 2D grid of cells
  • Model a move that may slip sideways or bump into the edge
  • Keep the move-then-sense order over several steps
Starting Python…