search
A hundred robots, no collisions
It is the era of automated warehouses and drone fleets, and a new kind of search problem arrives at scale: route not one agent but a hundred, each from its own start to its own goal, through a shared grid where two may never occupy the same cell at the same instant. Planning each path independently produces a tangle of collisions; planning all of them jointly explodes into the product of every agent's options. Find conflict-free paths that are collectively efficient, resolving clashes by replanning around them rather than searching the joint space whole. Get it wrong and the fleet deadlocks in gridlock, robots frozen nose to nose, or you brute-force a joint plan that never returns in time — multi-agent path finding keeps a thousand machines moving.
Who this problem belongs to
The two figures whose methods fit it best, out of 62 in contention.
Dijkstra's 1959 shortest-path algorithm is the foundational building block underneath essentially every practical multi-agent path-finding system: each individual agent's route through the shared grid is computed by exactly his algorithm or a direct descendant (A* being its heuristic-guided heir), and modern conflict-based search methods for this problem work by repeatedly recomputing single-agent shortest paths under added constraints whenever a collision is detected — a direct, structural descendant of his 1959 method applied iteratively. His broader work on structured reasoning about correctness and his semaphore concept for managing contention between concurrent processes are also conceptually adjacent to collision avoidance among agents sharing resources. He did not himself address the multi-agent, jointly-optimal version of the problem, but the single-agent core the whole field builds on is unmistakably his.
Karp's foundational work on combinatorial optimization, including efficient algorithms for network flow, bipartite matching, and assignment problems (some via his contributions building on the Hungarian algorithm lineage and his own max-flow min-cut era results with Edmonds), gives direct technical purchase on two core pieces of this problem: assigning a hundred agents to a hundred goals efficiently, and reasoning about the combinatorial explosion of jointly planning their paths. His 1972 NP-completeness results also explain precisely why the joint multi-agent planning space is intractable to search exhaustively, justifying the problem's demand for a decoupled, conflict-driven replanning approach rather than a full joint search. His domain is general combinatorial algorithms rather than robotics specifically, but the mathematical core of this problem is squarely his territory.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
62 figures are scored on this problem. Draw it in a battle to see where you land.