Why Greedy Fails

Greedy is the most seductive idea in robotics: at every moment, do the locally best thing and hope it adds up to a globally good plan. Sometimes it does. In task allocation, it spectacularly does not, and the gap between "what looks best right now" and "what's actually best for the team" is where this entire phase of the course lives.

The two-robot ambush

Strip the problem to its bones. Two robots, two packages, and a tape measure.

• Robot A is 10 m from package 1, but 100 m from package 2.
• Robot B is 10 m from package 1, and 10 m from package 2.

Now run the greedy rule: everyone grab your nearest job. Both robots see package 1 sitting 10 m away and both reach for it. One wins; the loser slinks off to the only box left:

• Greedy: A and B both want package 1. B takes it; A drives 100 m to package 2. Total: 110 m.
• Optimal: A takes package 1 (10 m), B takes package 2 (10 m). Total: 20 m.

Same robots, same packages, same instant in time, and greedy did five and a half times the driving. Nobody made a "wrong" choice. Every robot picked its genuinely nearest task. The fleet still lost, because nearest-for-me and best-for-us are different questions, and greedy only ever asks the first one.

Now make it a swarm

The two-robot case is cute. The real failure is structural, and it gets worse with scale. Picture a warehouse where the packages aren't spread out evenly. They're clustered, a dense knot of jobs in one aisle and a few stragglers far away.

Turn the swarm loose under the greedy rule and watch what happens:

• Every robot near the cluster sees a nearby task and dives in. So do their neighbors.
• A traffic jam forms over the cluster: several robots converging on jobs a single robot could have mopped up.
• The far-flung tasks? Nobody's nearest task is out there, so they sit unclaimed until some unlucky robot is finally forced to make the long haul.

A few robots get overloaded, the rest go idle, and the total travel distance balloons, not because any individual made a bad call, but because nobody coordinated who takes what. The optimal assignment does the thing that feels wrong: it deliberately sends some robots past a near task to a farther one, because the global cost comes out lower even when no single robot's choice looks locally best.

The fix isn't "be less greedy," it's "see the whole board"

The lesson hiding in that 110-vs-20 gap is not try harder locally. You cannot patch greedy by making each robot a little smarter about its own choice; the information it needs lives in everyone else's choices. The cure is a global view: an assignment that scores all pairings at once and picks the set that minimizes total cost, contention and all.

That single requirement, coordinating the assignment instead of racing for it, is the doorway to the next two lessons:

• Auctions let robots bid on tasks, so contention surfaces as a price instead of a collision, and the cluster sorts itself out without a central planner.
• The Hungarian algorithm solves the assignment optimally and exactly, treating the whole thing as a bipartite matching problem.

You might ask: why not just check every possible assignment and keep the cheapest? You can, for tiny fleets. The trouble is how fast "every possible assignment" grows.

↘ The assignment problem, stated honestly

Formally, task allocation is the assignment problem on a bipartite graph: robots on one side, tasks on the other, edge weight $c_{ij}$ = cost for robot $i$ to do task $j$. We want a one-to-one matching that minimizes total cost. Let $x_{ij} \in \lbrace 0, 1 \rbrace$ mark whether robot $i$ is assigned task $j$:

$$\min \sum_{i,j} c_{ij}\, x_{ij}$$

subject to every robot taking exactly one task and every task being taken exactly once:

$$\sum_j x_{ij} = 1 \quad \forall i, \qquad \sum_i x_{ij} = 1 \quad \forall j.$$

Greedy ignores the joint structure entirely. Each robot just grabs its cheapest remaining task:

$$j^* = \arg\min_{j \text{ unassigned}} c_{ij}.$$

That runs in roughly $O(n^2)$ comparisons and never reconsiders; it has no notion that taking $j^*$ might force another robot into a brutal $c_{ij}$ later. That blindness is the bottleneck: greedy can shove every expensive task onto one robot.

The Hungarian algorithm (Kuhn–Munkres) solves the same problem optimally in $O(n^3)$. You pay a polynomial-time premium and, in return, the contention is priced in from the start. For very large swarms even $O(n^3)$ is too much centralization, which is why distributed methods, auctions chief among them, approximate the optimum without anyone holding the full cost matrix.

Here is a fact that surprises most people the first time they hear it. You can write the assignment problem as an integer program, where every variable is forced to be 0 or 1, and integer programs are usually brutally hard. But for this particular problem, you can quietly drop the "must be a whole number" rule, solve the easier continuous version, and the answer comes back as clean 0s and 1s anyway. The structure of the cost matrix (a property called total unimodularity, named for the four conditions Alan Hoffman and David Gale spelled out) guarantees it. You ask for a relaxed answer and get the exact one for free.

↘ A robot fleet is the great-grandchild of moving dirt piles

Send a robot past a near task to a far one, and you have rediscovered a question more than two centuries old. In 1781 the French mathematician Gaspard Monge asked how to move a pile of soil to a hole in the ground while spending the least total effort, the problem of "déblais et remblais," cuts and fills. Every shovelful is an agent, every gap is a task, and the cost is the distance you carry the dirt. That is the assignment problem with sand instead of robots.

The source for this lesson puts it plainly: the assignment problem is a special case of the transportation problem, which is a special case of the minimum-cost flow problem, which is itself a special case of a linear program. Nest the boxes and our two robots fighting over a package sit at the bottom of a tower that climbs all the way up to general optimization.

Monge could not fully solve his own question. It took until the 1940s, when the Soviet mathematician Leonid Kantorovich reframed it in a way that finally cracked open, work on resource allocation that later earned him a share of the 1975 Nobel Memorial Prize in Economics. The whole field is now called optimal transport, and the same math that routes Kantorovich's freight reappears every time a swarm decides who drives where.

Key takeaways

• Greedy = each robot grabs its nearest task. Simple, fast, and locally optimal.
• It is globally suboptimal, and the failure is real: 110 m where 20 m was possible.
• The damage is worst when tasks are clustered, which is where contention peaks.
• The cure is a global view of the assignment, which is exactly what auctions and the Hungarian algorithm provide.