FixTheRobot Explore Robotics / Navigation / M3 / M3-L3

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

Navigation · Global Planning: Graph Search · M3-L3 · Intermediate

Fix a Corner-Cutting Planner

Incident report · Meridian General Hospital

13:05. Scout scrapes the corner of the pharmacy door frame again, and the paint on that corner is a different colour from the paint on the rest of the wall. The route in the log is a perfect staircase of cells, and one step of it passes diagonally through a corner that two wall cells share.

You will fix the legal-move rule, make the planner pay for cells close to walls instead of minimising distance, and then deal with the pharmacy hatch, which is a goal that lies inside the wall and cannot be stood on.

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

    A grid planner moves between cell centres, but the robot occupies space in between. Stage 1 is the corner rule: a diagonal step is legal only if both cells it squeezes between are free. Stage 2 plans on a costmap with the step cost length × (1 + 4 × cost / 252), where cells at 253 and above are forbidden: the shortest route hugs walls and the lowest-cost route does not. Stage 3 handles a goal that is not reachable as a cell: plan to the reachable cell closest to the goal within a tolerance, return the empty route when nothing is within it, and see why stopping at the first cell inside the tolerance circle is wrong.

    Grading is result-based: your functions are run on the practice wing and on freshly generated hidden wings, and the routes are checked cell by cell for validity, corner cuts, cost and distance to the goal.

    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: this lab.
    4. M3-L4: Replan When the Corridor Closes

    Educational simplification: a 0.25 m grid, Nav2-style cost values (254 lethal, 253 inscribed, 0 to 252 decaying), a circular robot handled by inflation, and a fixed cost factor of 4. Real planners also smooth the path and check the footprint (lessons M3-T7 and M4-T2).

    Get the next lab

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