FixTheRobot Explore Robotics / Navigation / M4 / M4-L2

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

Navigation · Sampling-Based and Kinodynamic Planning · M4-L2 · Intermediate

Grow an RRT

Incident report · Meridian General Hospital

16:30. Scout has to cross the loading dock between two long walls with gaps at opposite ends, past stacked crates. A grid planner would work, but the facilities team wants the same planner to run on the arm that unloads the pallets, where a grid is hopeless.

You will write the one move of an RRT, grow the tree to the goal, and then let it keep sampling to see whether the route gets any shorter.

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 extension step: nearest node, a steer of at most eta, and an edge check that must cover the whole edge, not only the new point. Stage 2 is the loop around it, with a tree stored as nodes and parents. Stage 3 is an experiment: plain RRT does not stop improving because it is slow, it stops because it never changes an edge once built.

    The random samples are generated by the page, because learner code here has no random module. Grading is result-based, on the practice dock and on hidden docks.

    Theory for this lab

    Sampling-Based and Kinodynamic Planning labs

    1. M4-L1: Collision-Check a Footprint
    2. M4-L2: Grow an RRT: this lab.
    3. M4-L3: Rewire to a Better Path with RRT*
    4. M4-L4: Park the Car-Like Robot

    Educational simplification: a point robot, axis-aligned walls and boxes, a fixed step size, goal bias done by putting the goal in every tenth sample, and a short sample list. Real planners also take a goal region, a kinematic steering function and a time limit.

    Get the next lab

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