multi-robot task allocation
Multi-robot task allocation is the problem of deciding which robot does which job, when a team of robots faces a pile of work. Imagine a warehouse with ten delivery robots and forty packages to move: someone — or some piece of software — has to hand out the packages so the whole job finishes fast, nobody trips over each other, and no robot sits idle while another is swamped. That deciding, done well and done over and over as new jobs appear, is task allocation.
The hard part is that the best answer depends on everything at once: how far each robot is from each job, how much battery it has left, whether two jobs are easier done by the same robot in one trip, and the fact that the situation keeps changing. A simple rule like 'every robot grabs the nearest job' is fast but can leave the team badly balanced. So roboticists look for assignments that minimize total time, total distance traveled, or some other cost — a tug-of-war between giving each robot a fair load and getting the whole job done quickly.
A popular family of solutions borrows the idea of an auction, or market. Each job is put up for 'bid'; every robot calculates how cheaply it could do that job (in time or energy) and bids that number; the job goes to the lowest bidder, and the process repeats for the next job. No central boss has to know everything — robots only need to compare bids — so these market-based methods keep working even as robots join, drop out, or discover the world is not what they expected.
Three cleaning robots share an airport at night. Each new spill is broadcast as a job; the robot that can reach it soonest bids lowest and wins it, so the closest free robot always takes the next mess.
A market-based auction hands each job to the robot that can do it most cheaply — no central planner needed.
Researchers sort these problems by how much each robot can do at once and how far ahead the plan looks — for example, whether a robot handles one task at a time or several, and whether jobs are assigned just for now or scheduled into the future.