1. Multiagent Systems (MAS)
Definition
A collection of decision-making entities (agents) aiming to optimally achieve a common goal by collecting/exchanging information and interacting.
General Challenges
- Communication: Limited bandwidth, noisy channels, lack of synchronization.
- Complexity: Joint decision space grows exponentially with the number of agents (\(n^m\)).
2. The Complexity Problem
Consider \(m\) agents, each with \(n\) possible controls. The joint control space is the Cartesian product:
\[ U(x) = U^1(x) \times \cdots \times U^m(x) \]Standard Rollout
Minimizes over all joint controls simultaneously.
\( O(n^m) \)
Exponential Complexity!
Multiagent Rollout
Minimizes one agent at a time.
\( O(nm) \)
Linear Complexity!
3. The Algorithm
We replace the one-step lookahead minimization with \(m\) successive minimizations, one-agent-at-a-time.
Sequential Minimization
- Agent 1 minimizes cost, assuming other agents use the base policy.
- Agent 2 minimizes cost, given Agent 1's choice and others using base policy.
- ...
- Agent m minimizes cost, given all previous choices.
Cost Improvement: It can be proven that Multiagent Rollout achieves cost improvement over the base policy: \( J_{\tilde{\mu}}(x) \leq J_{\mu}(x) \).
4. Case Studies
Spiders and Flies
Spiders must coordinate to catch flies. Greedy approach fails (spiders cluster). Multiagent rollout splits spiders strategically.
Warehouse Robots
Efficient path planning for hundreds of robots in Amazon-like warehouses.
Search and Rescue
Collaborative search in unknown environments.
Interactive visualization: Experiment with multiagent rollout in a grid world.