Multi-Agent Coordination

How should work be allocated among specialized agents under capacity and cost constraints?

Specialized agents differ in cost for each task and in capacity. Allocating first come, first served wastes the cheap matches and overloads some agents.

Allocation is an assignment problem. It has exact polynomial-time algorithms, so a coordinator can compare its allocation with the optimum and know the price of a simple rule.

x_ij is 1 if task i goes to agent j, c_ij is the cost of that match and k_j the capacity of agent j.

1. Estimate the cost of each task-agent pair.

2. Expand each agent into capacity slots.

3. Solve the assignment exactly (Hungarian method).

4. Compare with the simple rule used today.

1. Tasks

2. Cost estimates

3. Capacity slots

4. Assignment solver

5. Dispatch

6. Result log

No published experiments. The Multi-Agent Coordination lab compares a greedy rule with the exact optimum on synthetic cost matrices.

Multi-Agent Coordination

No original research results are claimed. This area is presented as a technical perspective with a computable demonstration on synthetic data.

• Costs must be estimated; wrong estimates give an optimal answer to the wrong problem.
• Static assignment ignores tasks that arrive later.
• Dependencies between tasks need richer models.

Background reading by other authors. These are not Menlo Tech publications, and no Menlo Tech paper is cited because none has been published.

• Kuhn, H. "The Hungarian method for the assignment problem." Naval Research Logistics Quarterly 2(1-2), 1955.
• Wooldridge, M. An Introduction to MultiAgent Systems, 2nd ed. Wiley, 2009.