algorithms · hackathon
amazon robotics hackathon
a python planner coordinating simulated warehouse robots under aisle, station, and capacity constraints. placed 3rd of 42 teams.
- timeline
- sep 2026
- stack
- python, space-time a*, local search
3rd
of 42 teams
the problem
at the amazon robotics hackathon at ubc, teams wrote the routing logic for simulated warehouse robots. the floor is a weighted graph: storage nodes where pods of inventory appear, stations where they need to go, and aisles that take a few steps to cross. every step, the game engine asks each idle robot for one move, either an adjacent node or a wait. pickups and drop-offs happen on their own when a robot stops in the right place.
it came in three levels. level 1 is one robot and a shortest path. level 2 adds robots and aisles that fit one robot at a time, so two robots on the same route block each other. level 3 adds stations with a limited number of docks and robots that carry more than one pod. we placed 3rd of 42 teams.
step 0 · 0 of 6 delivered · score 0.0 · next pod at step 0
a replay of our planner on three practice floors, recorded from the hackathon's game engine. robots leave storage, pick up pods, and deliver them to stations, waiting for each other at narrow aisles and single docks. final scores: level 1, 84.7; level 2, 86.0; level 3, 78.9.
how it’s scored
each pod is worth up to 100 points and starts losing them the moment it appears. speed matters, but a stranded pod scores nothing, so it costs far more than a slow one.
the engine also has rules that only matter under pressure. robots are asked in id order and valid moves take effect immediately, so when two robots want the same narrow aisle, the lower id gets it and the other one waits a step.
planning the whole floor
the engine is deterministic, and every call gets the full state of the floor, so we could simulate exactly what any move would do. we built a planner around that. it proposes a complete plan for every robot, plays it forward through an exact copy of the engine’s step loop, and keeps whichever plan the engine itself would score highest.
a plan is small: for each robot, an ordered list of stops (“pick up this pod”, “deliver that one”), plus the order in which robots get routed. the actual paths and all the waiting are derived from it, which kept the search space manageable.
sharing the floor
paths come from space-time a*, which searches over a node and a time together, so waiting in place is just another move. robots are routed one at a time in priority order, and each path goes into a reservation table that records which aisles and docks are taken at each step. later robots plan around those reservations: they can wait, take a detour, or use a narrow aisle once someone else has cleared it.
the reservation table follows the engine’s capacity rules exactly, including the lower-id-first tie-break. on the practice cases, the real engine never rejected a single planned move. one small rule turned out to matter a lot: a robot with nothing to do parks on a storage node, where the next pods are likely to appear, and never on a station, where it would block a dock.
greedy baseline: robot 2 never leaves the dock, so robot 0 waits outside with p4. 3 of 4 delivered before the 120-step limit · score 63.5
with the greedy baseline, robot 2 delivers and then stays on the only dock, so robot 0 waits outside with the last pod until the simulation ends: three of four delivered, score 63.5. our planner moves robot 2 off the dock straight after its delivery and all four pods arrive by step 16, score 83.2.
deciding who carries what
once routing is settled for a given plan, the real question is which plan. new pods are inserted greedily: candidate positions in every robot’s list are ranked by a quick distance estimate, and the best few are simulated exactly. then local search takes over. it moves a pod to another robot, swaps two pods, reorders a robot’s stops, or changes who gets routed first, keeping any change that raises the simulated score. when no small move helps anymore, it pulls out one to three pods and re-inserts them, sometimes accepting a slightly worse plan so it can get past plateaus. when the whole space is small enough, it just tries every plan.
plan 1 of 3,268 · empty plan · score 0.0
greedy insertion adds pods one at a time and reaches a score of 59.8 with pod 6 still undeliverable. local search then relocates and reorders stops, delivers every pod, and reaches 70.4 after 380 of the 3,268 plans simulated in that step.
the practice cases were small enough that insertion usually found the best plan on its own, so this figure runs the same code on a larger generated floor where the search has room to work.
adapting as it runs
new pods keep arriving, so a plan is never final. each step, the previous plan is carried over to the new state as the starting point, so the search only has to fit in new pods and fix whatever changed. compute is budgeted per step: 250 ms for the first plan, 180 ms when pods arrive, 100 ms while the plan is still improving, and 50 ms once it has settled. planning is capped at 45 seconds per test case, well inside the limits of one second per call and two minutes per case.
step 0 · 250 ms · first plan · 3,318 plans simulated. step 2 · 100 ms · still improving · 2,303 plans simulated. step 4 · 50 ms · settled, re-checking · 1,339 plans simulated. step 7 · 50 ms · settled, re-checking · 1,672 plans simulated. step 9 · 50 ms · settled, re-checking · 2 plans simulated. step 11 · 180 ms · p5, p6 arrived · 2,241 plans simulated. step 14 · 100 ms · still improving · 1,354 plans simulated. step 16 · 50 ms · settled, re-checking · 1,001 plans simulated. step 18 · 50 ms · settled, re-checking · 1,091 plans simulated. step 21 · 180 ms · p7, p8 arrived · 2,087 plans simulated. step 23 · 100 ms · still improving · 1,217 plans simulated. step 25 · 50 ms · settled, re-checking · 611 plans simulated. step 27 · 50 ms · settled, re-checking · 657 plans simulated. step 30 · 50 ms · settled, re-checking · 705 plans simulated. step 32 · 50 ms · settled, re-checking · 1,198 plans simulated. step 34 · 50 ms · settled, re-checking · 1,300 plans simulated. step 37 · 50 ms · settled, re-checking · 1,525 plans simulated.
if a planned move ever turned out to be invalid, or anything threw an exception, the robot would fall back to a plain shortest-path step and the next step would plan from scratch. the engine never gets an invalid answer.
results
| case | our planner | greedy baseline | example driver |
|---|---|---|---|
| case 1, level 1 | 90.5, 1 of 1 delivered | 90.5, 1 of 1 delivered | 83.5, 1 of 1 delivered |
| case 2, level 1 | 84.7, 3 of 3 delivered | 75.3, 3 of 3 delivered | 27.3, 1 of 3 delivered |
| case 3, level 2 | 81.9, 2 of 2 delivered | 78.8, 2 of 2 delivered | 74.1, 2 of 2 delivered |
| case 4, level 2 | 86.0, 6 of 6 delivered | 84.5, 6 of 6 delivered | 70.3, 5 of 6 delivered |
| case 5, level 3 | 83.2, 4 of 4 delivered | 63.5, 3 of 4 delivered | 54.1, 3 of 4 delivered |
| case 6, level 3 | 78.9, 8 of 8 delivered | 78.2, 8 of 8 delivered | 42.6, 4 of 8 delivered |
on the public practice cases, the planner matched or beat both baselines on every case, and it was the only one of the three to deliver every pod on all six. the final standings came from hidden test cases of similar size, where we placed 3rd of 42 teams.