skip to content

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

three robots on a grid where every aisle fits one robot at a time. which robot takes which pod decides where the traffic jams happen. robots are filled while carrying, and thin aisles fit one robot at a time.

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.

0501000255075100125150pointssteps from arrival to deliveryhalf the points after 35 stepsour 24 deliveries on the practice casesdelivered after 0 steps: 100.0 points
every pod starts at 100 points and loses them from the moment it appears, so a pod that waits costs points even if it's delivered eventually, and one that's never delivered scores nothing. all of ours arrived within 18 steps. hover the curve to read any point.

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.

how the planner decides each stepeach time step the game engine asks for moves. the planner takes a snapshot of the floor along with the plan from the previous step, then loops: take a candidate plan, route every robot with space-time a* around the others' reservations, replay the engine's own step loop on those routes, and keep the plan if it scores better, mutating it by relocating, swapping, reordering, or re-inserting pods. when the step's time budget runs out, the first move of every robot in the best plan goes back to the engine.repeats until the step's time budget runs outcandidate planwho carries which pod, whenroute every robotspace-time a* + reservationsreplay the engineexact copy of its step loopscore the plankeep it if it beats the bestrelocate · swapreorder · re-insert565 – 18,088plans simulated per stepgame engineasks each idle robotsnapshot+ last step's planfirst movesof the best plan found
every step starts from the last step's plan and improves it for as long as the budget allows. the engine only ever sees each robot's next move.

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

practice case 5, recorded from the game engine: three robots and four pods for a station with a single dock. thick lines carry a pod, and the grey band shows who holds the dock. both runs match until step 13.

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

one planning step on a larger generated floor: four robots that carry two pods each, twelve pods, and narrow aisles. each frame is a new best plan. the score is on the engine's 0–100 scale, and the plans axis is logarithmic.

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.

practice case 6, one bar for each step where a robot needed a decision. the gaps are steps where every robot was mid-aisle. the two tall tiers are full searches, when the run starts or new pods arrive; the short grey bars keep improving or re-check the current plan. hover a bar for its step.

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

scores out of 100 on the public practice cases, each run through the unchanged game engine. the greedy baseline sends every robot down its shortest path to the nearest pod and ignores the others. hover a row for pods delivered.
scores on the public practice cases
caseour plannergreedy baselineexample driver
case 1, level 190.5, 1 of 1 delivered90.5, 1 of 1 delivered83.5, 1 of 1 delivered
case 2, level 184.7, 3 of 3 delivered75.3, 3 of 3 delivered27.3, 1 of 3 delivered
case 3, level 281.9, 2 of 2 delivered78.8, 2 of 2 delivered74.1, 2 of 2 delivered
case 4, level 286.0, 6 of 6 delivered84.5, 6 of 6 delivered70.3, 5 of 6 delivered
case 5, level 383.2, 4 of 4 delivered63.5, 3 of 4 delivered54.1, 3 of 4 delivered
case 6, level 378.9, 8 of 8 delivered78.2, 8 of 8 delivered42.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.