FixTheRobot Explore Robotics / Navigation / M8 / M8-L1

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

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

Order the Stops

06:30. The pharmacy has eight deliveries for Scout, and the wards phoned them in at random. Driven in that order, the route zigzags across the whole building and the first blood-sample kit arrives late.

You will write the greedy rule a first version of every fleet scheduler uses, repair its tour by reversing segments, and then compute the best possible tour for a short list to see how far the shortcuts are from it.

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 nearest neighbour: always go to the closest stop not yet visited. Stage 2 is 2-opt, a local search that removes crossings by reversing a segment of the tour. Stage 3 is an exact depth-first search with pruning for six stops, and a question on why the same code is hopeless for thirty.

    Grading is result-based: your functions are run on the practice example and on freshly generated hidden maps, and compared with the exact answer or with the defining property of the result (for 2-opt, that no improving move is left).

    Theory for this lab

    Missions, Coverage and Fleets labs

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

    Educational simplification: straight-line distances between stops (real routes follow corridors and doors, so the cost matrix would come from a path planner), one robot, one depot, symmetric costs, no time windows and no battery limit.

    Get the next lab

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