TL;DR
This paper introduces IRM, a novel multi-agent intention scheduling approach that uses reward machines to predict other agents' actions, even when their internal programs are unknown. This allows for more robust and safer multi-agent coordination, outperforming existing methods in scenarios where agents are not co-designed.
What Problem Does This Paper Address?
Coordinating multiple intelligent agents, especially in complex environments, is a significant challenge. A key aspect of this is "intention progression" – deciding what to do next. In multi-agent settings, an agent's decision-making is influenced by what other agents are trying to achieve and what actions they might take. Existing "intention-aware" scheduling methods often assume that an agent knows the internal plans or programs of other agents, or that these programs are similar to its own. This assumption breaks down in scenarios where agents are developed independently or have different underlying architectures. The paper addresses this gap by proposing a method that allows agents to predict the behavior of others based on a high-level specification of their tasks, rather than their specific implementation.
Methods
The core of the proposed approach, IRM (Intention Progression with Reward Machines), lies in using Reward Machines (RMs) to model the tasks of other agents. RMs are a formal way to represent tasks as state machines that emit rewards upon completion of certain abstract "steps" or "phases."
Here's how it works:
- Reward Machines for Task Specification: Instead of knowing another agent's program (e.g., its plans in a Belief-Desire-Intention (BDI) architecture), IRM uses RMs that describe the high-level goals or tasks of other agents. These RMs can be derived from declarative task specifications like Linear Temporal Logic (LTL).
- Action Automata: The possible actions an agent can take in a given state are modeled using an action automaton.
- Task Automaton: A combined "task automaton" is constructed, integrating the environment state, the current states of all relevant RMs, and the action automaton. This automaton captures the joint state of the system from the perspective of predicting another agent's behavior.
- Tactic Set: From the task automaton, a "tactic set" is computed. This set provides an approximation of a rational agent's behavior by estimating the expected reward for taking each action in a given state, considering the shortest path to achieving the task. This is crucial for predicting future actions.
- MCTS Integration: IRM integrates this tactic set into a Monte Carlo Tree Search (MCTS) based scheduler.
- Expansion Phase: When it's another agent's turn to act, IRM uses the tactic set to determine the set of expandable actions, rather than relying on assumed internal plans.
- Rollout Phase: During simulations (rollouts), IRM models other agents as trying to maximize the heuristic value from the tactic set, using a noisy softmax distribution to account for potential irrationality or non-cooperative behavior.
The key novelty is the shift from inferring behavior from internal programs to inferring it from high-level task specifications (RMs).
Datasets
The paper evaluates IRM on two existing multi-agent domains:
- Office World: A simulated environment where agents collect and deliver coffee and mail, avoiding decorations and other agents.
- Craft World: A domain where agents collect resources to craft various items.
The authors extend these domains to multi-agent settings and consider cooperative, selfish, and adversarial scenarios. No new benchmarks were introduced.
Key Insights and Ideas
- The Danger of Egocentric Assumptions: The most striking insight is how much existing intention-aware schedulers (like IB) can struggle when they assume other agents behave identically to themselves. In the Office World, this egocentric view led to frequent collisions and failures because neither agent predicted the possibility of being in the same room.
- Reward Machines as a Bridge: RMs provide a powerful abstraction. They allow an agent to understand what another agent is trying to achieve without needing to know how it's trying to achieve it. This is crucial for interoperability between independently developed agents.
- Predicting "Good Enough" Behavior: The tactic set doesn't aim for perfect prediction but rather for a reasonable approximation of rational behavior. This is sufficient for robust coordination, especially in adversarial or uncertain environments.
- IRM's Advantage in Non-Co-Designed Settings: The results strongly suggest that IRM's ability to model external agents based on RMs, rather than assuming shared internal structures, is its primary advantage, particularly when agents are not fully co-designed.
Key Results
- Office World: IRM significantly outperformed existing methods (IB and Sp) in scenarios where agents were not co-designed, achieving success rates of up to 0.97 compared to IB's 0.73 and Sp's 0.44. This was attributed to IRM's ability to anticipate and avoid collisions, a risk that egocentric models missed.
- Craft World:
- In fully co-designed scenarios (where all agents shared the same GPTs), IB performed best, as expected, due to its access to detailed internal plan information.
- However, in partially co-designed and non-co-designed scenarios, IRM consistently outperformed IB.
- IRM also significantly outperformed Sp (a non-intention-aware baseline) across all scenarios.
- In adversarial settings, IRM showed a marked advantage, achieving higher scores in scenarios where the goal was to maximize
blue_goals - red_goals.
Limitations and Future Work
- Computational Complexity: The paper notes that the size of the task automaton can be exponential in the number of tasks. While the tactic set computation is polynomial in the size of this automaton, generating and managing these large structures can still be computationally intensive. The authors suggest that recomputing these for the current environment state can offer a more compact representation.
- RM Generation: The paper assumes RMs are available or can be computed. The process of automatically generating RMs from complex task specifications is an area of ongoing research.
- Future Work: The authors suggest extending the approach to more complex multi-agent scenarios and exploring how to adapt IRM when the goals of other agents change dynamically. They also highlight the potential for IRM to be applied in scenarios involving a mix of BDI and non-BDI agents.
Summary updated