Problem 536093 · hard · Robotics · Level 05 Planning and Mapping

The Map Was Wrong

replanning · breadth-first search · free-space assumption · simulation · tie-breaking

A delivery robot in a hospital basement plans on the floor plan it was given, known, but trolleys get parked in corridors, so the true basement, truth, may have more obstacles. Both are lists of strings of the same shape: '#' is blocked and '.' is free (row 0 at the top). Every cell blocked in known is also blocked in truth; the robot simply does not know about the rest. A cell is a pair (row, col).

Planning. The robot moves one cell up U (towards row 0), right R, down D or left L. A plan from a cell to the goal is a route through cells the robot believes are free that uses the fewest moves; when there are several, it is the one whose list of moves comes first when the lists are compared move by move in the order U < R < D < L. (From (2, 0) to (0, 2) on an empty map, U U R R beats U R U R, which beats R U U R.) If no route exists there is no plan.

Driving. The robot starts on start and makes a plan with known as its belief. Then, until it stands on goal:

  1. If it has no plan, it stops where it is.
  2. Otherwise it looks at the next cell of its plan. If that cell is blocked in truth, it marks the cell as blocked in its belief, counts one replan, and makes a new plan from the cell it is on (nothing else changes in its belief).
  3. If that cell is free, the robot drives into it.

Write replan_drive(known, truth, start, goal) that returns the tuple (driven, replans): driven is the list of cells the robot occupied, in order, from start to where it ends (on goal, or where it got stuck), and replans the number of replans. start and goal are free in truth.

Examples

Input:  known = ["....", "....", "...."], truth = ["....", "###.", "...."],
        start = (2, 0), goal = (0, 3)
Output: ([(2, 0), (2, 1), (2, 2), (2, 3), (1, 3), (0, 3)], 3)
Explanation: the first plan goes up column 0 and finds (1, 0) blocked. From (2, 0)
the next plan starts R then U, and finds (1, 1) blocked; the same happens at (1, 2).
From (2, 3) the way up is open.

Input:  known = ["....", "###.", "...."], truth = ["....", "###.", "...."],
        start = (2, 0), goal = (0, 3)
Output: ([(2, 0), (2, 1), (2, 2), (2, 3), (1, 3), (0, 3)], 0)
Explanation: with a correct map, the first plan already avoids the wall.

Input:  known = ["...", "..."], truth = [".#.", ".#."], start = (0, 0), goal = (0, 2)
Output: ([(0, 0), (1, 0)], 2)
Explanation: (0, 1) is blocked, so the robot replans down and around, drives to (1, 0),
finds (1, 1) blocked as well, and is left with no plan.

The setup provides aisles(rows, cols, seed, gap=3, clutter=0): a floor plan of double shelves with openings, plus clutter single boxes. With the same rows, cols, seed and gap, a larger clutter only adds boxes, so aisles(20, 30, 1) can be the map and aisles(20, 30, 1, 3, 25) the truth. The larger tests use it.

Constraints

  • known and truth have the same shape, with equal-length rows, up to 60 by 60

Goals

  • Simulate a robot that plans on its map, drives, and replans whenever it meets an unknown obstacle
  • Produce one exact shortest route by a stated order of moves
  • Keep the robot's belief separate from the true world
Starting Python…