FixTheRobot Explore Robotics / Navigation / M3 / M3-L2

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

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

Implement A* with Search Replay

Incident report · Meridian General Hospital

11:30. The hospital has grown a wing and Scout's planner now takes a noticeable pause before every trip. The pharmacy is at the far end of a hall with one long wall; Dijkstra fans out over the whole hall, including the half that is nowhere near the pharmacy.

You will make the search face the goal with A*, write the heuristic that keeps it honest on a grid with diagonal moves, and then bend it with a weight to see how much speed a little suboptimality buys. A replay slider shows what each version expanded.

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 f = g + h: the cost so far plus an estimate of the cost to go. The starter orders by the estimate alone, which is greedy best-first search, fast in empty space and caught by the first wall it meets. Stage 2 is the heuristic itself: it must never overestimate (admissible) and should be as close to the truth as possible (informed). On an 8-connected grid with diagonal cost √2 that is the octile distance, and Manhattan distance is too large. Stage 3 weights the heuristic, f = g + w·h, giving a route at most w times the cheapest and a smaller search; the starter puts the weight on the wrong term.

    Grading is result-based: the routes are compared with the true cheapest cost, and the number of cells your search expands is compared with Dijkstra and with plain A*, with margins because tie-breaking changes counts a little. Use the replay slider to scrub through your expansions.

    Theory for this lab

    Global Planning: Graph Search labs

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

    Educational simplification: an 8-connected grid with straight steps of 1 and diagonal steps of √2, no costmap and no robot footprint. A diagonal step is allowed only if both cells it squeezes between are free (lab M3-L3 explains the rule).

    Get the next lab

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