TL;DR
This paper introduces a novel approach for multi-agent systems where agents need to decide their next actions without knowing the internal workings of other agents. By using a "partially-ordered goal-plan tree" (pGPT) abstraction of their own plans, agents can better predict and coordinate with others, leading to improved performance in cooperative, selfish, and adversarial scenarios compared to existing methods.
What Problem Does This Paper Address?
Autonomous agents operating in a multi-agent environment often face the "intention progression problem": deciding which goal to pursue next and how to achieve it. This is particularly challenging when agents are not "co-designed," meaning they don't have full knowledge of each other's internal plans or strategies. Existing methods often assume agents have access to each other's plans, which is unrealistic in many real-world scenarios. This paper tackles the problem of intention progression when agents treat others as "black boxes" – they know their goals but not the specific steps they will take to achieve them. This lack of knowledge makes predicting and coordinating actions difficult, potentially leading to conflicts and suboptimal outcomes.
Methods
The core contribution is the partially-ordered goal-plan tree (pGPT). Unlike traditional goal-plan trees (GPTs) that represent a strict, sequential execution order of actions and subgoals, pGPTs capture only the essential ordering constraints implied by the agent's program, specifically those derived from preparatory effects (p-effects). This abstraction allows an agent to represent its own program in a way that is more robust to variations in how other agents might order their own subtasks.
The paper then adapts a Monte Carlo Tree Search (MCTS)-based scheduling approach (IA) to work with these pGPTs, creating a new scheduler called IB. In the MCTS algorithm, this adaptation affects how the search tree is expanded and how rollouts (simulations of future play) are performed. Instead of assuming a single, fixed execution path (as in GPTs), IB explores multiple possible execution paths consistent with the pGPT's partial ordering, effectively increasing the branching factor of the search. This allows IB to be more flexible in predicting and reacting to the actions of other agents.
Datasets
The paper does not introduce new datasets. Instead, it uses a synthetic generation of pGPTs and GPTs to create multi-agent scheduling problems of varying complexity. These synthetic problems are designed to mimic real-world scenarios with potential conflicts and dependencies. The evaluation is conducted across three settings: allied, neutral, and adversarial, which are standard benchmarks for multi-agent coordination research.
Key Insights and Ideas
- The power of abstraction: Representing an agent's program as a pGPT, which focuses on essential dependencies rather than strict ordering, is crucial for dealing with "black-box" agents. This abstraction allows for more flexible planning and prediction.
- Increased search flexibility pays off: While using pGPTs increases the branching factor in the MCTS search, leading to shallower simulations per node, the improved flexibility in modeling other agents' potential actions more than compensates for this. IB consistently outperforms IA, even with fewer simulation steps.
- "Selfish" agents can be surprisingly effective: In the neutral setting, IB agents with full awareness of their own goals but no knowledge of others' goals (IB-100) outperformed IA agents in the allied setting (IA-100), suggesting that efficient self-interested planning can be more effective than poorly coordinated cooperation.
- Awareness is key, but how you model it matters: Performance consistently improves with increased awareness of other agents' goals, but IB's ability to model potential variations in other agents' plans makes it more adept at leveraging this information than IA.
Key Results
The IB scheduler consistently outperformed the IA scheduler (which assumes other agents have the same program) across all evaluated settings (allied, neutral, adversarial) and levels of agent awareness.
- Allied Setting: IB-100 agents achieved an average team score of 11.475, compared to 10.157 for IA-100 agents, representing a 72% reduction in unachieved goals.
- Neutral Setting: IB-100 agents achieved significantly higher scores than IA-100 agents, demonstrating better selfish goal attainment.
- Adversarial Setting: IB agents generally achieved better net scores (own goals minus opponent goals) against various opponents compared to IA.
- Even unaware agents (IB-0 vs. IA-0) showed a slight performance advantage for IB, attributed to its greater flexibility in handling internal conflicts.
Limitations and Future Work
- Black-box assumption: While the paper addresses the "black-box" scenario, it still assumes agents have access to the goals of other agents (to varying degrees). A future direction is to infer these goals at runtime.
- Synthetic environments: The evaluation relies on synthetically generated pGPTs. Future work could explore performance on more complex, real-world benchmarks.
- Plan generation: The paper uses a pGPT generator. Investigating how different plan generation strategies might impact the pGPT abstraction and subsequent scheduling would be valuable.
- Relaxing assumptions: The authors suggest further relaxing assumptions, such as assuming agents pursue only a subset of known goals, which would need to be inferred dynamically.
Summary updated