FixTheRobot Explore Robotics / Navigation / M6 / M6-L4

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

Navigation · Local Planning and Obstacle Avoidance · M6-L4 · Advanced

Pass Without Colliding: ORCA

Incident report · Meridian General Hospital

12:10. In the narrow service corridor Scout meets the linen cart robot coming the other way. Both slow down, both stop 0.8 m apart, both wait. A porter has to carry the trolley by hand. The fleet log shows two robots that did everything right and still did not move.

You will construct the velocity obstacle, split the avoidance between the two robots the way ORCA does, and then find out why a perfectly symmetric meeting stalls and what small convention gets it moving.

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 geometry of the truncated velocity obstacle: the nearest boundary point is on one of two straight legs or on the circle that cuts off the tip, and the direction of the boundary there defines a half-plane of allowed velocities. Stage 2 is the ORCA step: each robot constrains itself to the half-plane through its velocity plus half the correction and picks the allowed velocity closest to the one it prefers. Stage 3 runs a closed-loop meeting with your preferred-velocity function in the loop.

    Grading is result-based: the escape vectors and velocities are compared with the exact ones, and the meetings are simulated and measured for contact, arrival and delay.

    Theory for this lab

    Local Planning and Obstacle Avoidance labs

    1. M6-L1: Escape the Local Minimum
    2. M6-L2: Implement the Dynamic Window
    3. M6-L3: Avoid a Moving Obstacle
    4. M6-L4: Pass Without Colliding: ORCA: this lab.

    Educational simplification: two disc-shaped robots in an open plane, perfect knowledge of each other, velocities applied instantly, and a single neighbour, so the velocity choice is a projection onto one half-plane instead of the linear program that a crowd needs (lesson M6-T5). The loop is run for you by a harness that calls your function every tick.

    Get the next lab

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