FixTheRobot Explore Robotics / Navigation / M8 / M8-L3

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

Navigation · Missions, Coverage and Fleets · M8-L3 · Intermediate

Explore by Frontiers

Incident report · Meridian General Hospital

03:20. The east wing has been renovated and nobody has a map. Scout is sent in to build one, with one rule: always drive to the best frontier, and come home when there is nothing left worth seeing.

On the first night it drives into a wall, then spends an hour looping to a frontier behind a door, and finally never stops. You will fix the three decisions behind these failures.

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 finds frontiers: free cells next to unknown cells, not walls. Stage 2 chooses among them with a utility, the unknown space a frontier is expected to reveal minus the cost of getting there, and the cost is a path length through known free space. Stage 3 asks when to stop, and the answer is reachability: a frontier nobody can reach does not count.

    Grading is result-based: your functions are run on partial maps from a reference exploration of the practice wing and of freshly generated hidden wings, and compared with the exact answers.

    Theory for this lab

    Missions, Coverage and Fleets labs

    1. M8-L1: Order the Stops
    2. M8-L2: Cover the Floor
    3. M8-L3: Explore by Frontiers: this lab.
    4. M8-L4: Break the Deadlock

    Educational simplification: a grid world with thick walls and doors, a noise-free sensor of radius 4 with line of sight, a robot that moves between 4-neighbour cells, a fixed utility (unknown cells in a 5 x 5 window minus half the path length), and no localization error. Real explorers cluster frontiers, work with probabilistic maps and handle noise.

    Get the next lab

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