FixTheRobot Explore Robotics / Navigation / M8 / M8-L4

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

Navigation · Missions, Coverage and Fleets · M8-L4 · Advanced

Break the Deadlock

Incident report · Meridian General Hospital

07:40. Three robots arrive at the elevator lobby within a few seconds of each other: one with medication for the ICU, one with a sample for pathology, one returning to the charger. They all stop, and none of them moves again.

The lobby is a plus-shaped junction with one-cell corridors. You will plan the robots in space and time, make the plan respect swaps and parked robots, and then find the order of priorities that lets all of them through.

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 is the single-robot building block: breadth-first search over (cell, time) pairs that avoids vertex and edge reservations, including the swap that physical robots cannot do. Stage 2 chains robots: each planned path is reserved, including the long wait at the goal. Stage 3 shows that a fixed priority order can leave a robot with no path, and fixes it by searching over orders.

    Grading is result-based: your plans are checked for legality, for vertex and swap conflicts, and (in stage 1) for the earliest arrival, on the practice lobby and on hidden lobbies with different starts and goals.

    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
    4. M8-L4: Break the Deadlock: this lab.

    Educational simplification: a 7 x 7 grid, three robots, discrete time, robots wait or move one cell per step, every robot parks at its goal until the end, and conflicts are two robots in one cell or two robots exchanging cells. Real fleets add kinematics, delays, many more robots and continuous reservations.

    Get the next lab

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