FixTheRobot Explore Robotics / Navigation / M3 / M3-L4

This lab works on phones, but writing code is much easier on a laptop.

Navigation · Global Planning: Graph Search · M3-L4 · Advanced

Replan When the Corridor Closes

Incident report · Meridian General Hospital

14:20. A fire door shuts on the second floor, right on Scout's route. The robot stops, replans, and the whole floor freezes for two seconds while the planner searches the entire building again. On a busy afternoon the doors close every few minutes, and a fleet of robots does it at once.

You will build the field that makes replanning cheap, work out which cells a closed door actually affects, and recompute only those. The rest of the building keeps the answers it already had.

Your task

    Simulation
    solution.pyLoading Python…
    Ctrl+Enter runs
    What Python can I use?

    Plain Python with math and heapq. Your code runs in a background worker: an endless loop is stopped after a few seconds and the page stays usable. It runs in your browser and is never sent anywhere.

    Hints

    What this lab teaches

    Stage 1 builds a cost-to-go field with a search that starts at the goal, so that one search serves every possible position of the robot, and the robot drives downhill. The starter uses one marker for “wall” and “not reached”, and the search floods through the walls. Stage 2 finds the cells that must change when a door closes: those that lose every neighbour one step closer to the goal. Stage 3 repairs the field by seeding the affected cells from the neighbours that are still true and spreading with a priority queue, touching nothing else. The final question asks when it is simpler to search again from scratch.

    Grading is result-based: your field, affected set and repaired field are compared with exact answers on freshly generated hidden wards with different closed doors.

    Theory for this lab

    Global Planning: Graph Search labs

    1. M3-L1: Implement Dijkstra
    2. M3-L2: Implement A* with Search Replay
    3. M3-L3: Fix a Corner-Cutting Planner
    4. M3-L4: Replan When the Corridor Closes: this lab.

    Educational simplification: a 4-connected grid with unit steps, one closure at a time, and no heuristic or priority keys. D* Lite and LPA* add a heuristic and keys so that they also handle cost changes and a moving robot (lesson M3-T6).

    Get the next lab

    Get notified when new robotics labs are released. One email per new lab, nothing else.