TL;DR
This paper tackles the challenge of multi-agent intention scheduling by introducing a novel approach that uses online goal recognition to infer other agents' goals in real-time. This allows agents to make better decisions in dynamic environments, even when the goals of other agents are not known beforehand, and achieves performance comparable to agents with prior knowledge.
What Problem Does This Paper Address?
In multi-agent systems, especially those employing the Belief-Desire-Intention (BDI) model, agents often pursue multiple goals concurrently. To act effectively, an agent needs to predict what other agents will do next. Traditional approaches to "intention-aware multi-agent scheduling" assume that an agent knows the current goals of other agents a priori. This assumption is often unrealistic in real-world scenarios, such as disaster response, where potential goals might be known, but current intentions are not. Simply assuming all possible goals are active leads to poor predictions. This paper addresses this gap by proposing a method where an agent can learn the current goals of other agents on the fly, enabling more robust and adaptive multi-agent coordination.
Methods
The core of this paper is the integration of online goal recognition into a Monte-Carlo Tree Search (MCTS)-based intention scheduler.
- Goal Recognition: The authors extend existing work on "Goal Recognition as Reinforcement Learning" (GRAQL) to handle multi-goal recognition. Instead of assuming a single goal, they consider a set of possible goals. They use KL divergence to measure the difference between observed agent behavior and the expected behavior for each potential goal. A key innovation is a heuristic approach that identifies a set of "current" goals as those whose KL divergence is within a certain threshold of the minimum. This avoids the combinatorial explosion of considering all possible goal combinations. They also adapt the distance measure to use an exponential moving average of KL divergence, making it more sensitive to recent observations.
- Intention Scheduling: The proposed scheduler, called IGR, builds upon the state-of-the-art intention-aware scheduler IRM. IGR uses the inferred goals from its goal recognition module to inform its MCTS rollouts. Instead of relying on a fixed "tactic set" for other agents (as IRM does), IGR dynamically predicts their actions based on their inferred goals. This involves using the single-goal Q-functions from the goal recognizer to guide the rollout policy for the other agent. IGR also offers flexibility in how intentions are interleaved, supporting both action-level and plan-level interleaving.
Datasets
The evaluation is performed in the Craft World environment, a well-known benchmark for multi-agent research, specifically the two-agent version developed by Dann et al. (2022). The paper does not introduce new datasets but uses this existing environment with 10 different scenarios designed to test various interaction types (selfish, allied, adversarial).
Key Insights and Ideas
- Real-time Goal Inference is Crucial: The paper strongly suggests that assuming prior knowledge of other agents' goals is a significant limitation in many practical multi-agent scenarios. The ability to infer goals dynamically is key to achieving robust performance.
- Heuristic Goal Recognition is Effective: The proposed heuristic for identifying current goals (within a KL divergence threshold) is a practical way to manage the complexity of multi-goal recognition, offering a good trade-off between accuracy and computational cost.
- Rollout Policy Matters: The choice of how to simulate other agents' behavior during MCTS rollouts is critical. IGR's approach of using single-goal Q-values for rollouts appears to be more effective than IRM's approach of assuming a conjunctive policy, especially when paired with agents that don't perfectly adhere to IRM's assumptions.
- Flexibility in Interleaving: The ability to configure intention interleaving at either the action or plan level is important for adapting to different task structures and agent behaviors.
Key Results
The paper demonstrates that IGR generally performs well, often outperforming intention-unaware agents (like Sp) and achieving performance close to, and sometimes exceeding, intention-aware agents that have full prior knowledge of goals (like IRM).
- Overall Performance: IGR scored, on average, 0.79 points more than the intention-unaware Sp and only 0.20 points less than the prior-knowledge IRM.
- Outperforming IRM: In 8 out of 40 scenario/paired-agent combinations, IGR outperformed IRM. This is attributed to IGR's more flexible rollout policy, which better predicted the behavior of certain agents (like Q-learn) compared to IRM's assumption of a conjunctive goal policy.
- Handling Multiple Goals: IGR showed good performance even in scenarios with a larger number of possible and true goals, indicating its robustness to complex goal sets.
- Impact of Incomplete Goal Sets: In scenarios where the assumed set of possible goals did not include all true goals, IGR's performance decreased but still remained competitive, outperforming the intention-unaware baseline.
Limitations and Future Work
- Partial Observability and Noisy Observations: The current evaluation assumes full observability. The authors note that while GRAQL has shown robustness to partial and noisy observations, this has not been explicitly evaluated for IGR. This is a key area for future work.
- Adversarial Settings: While IGR performs well in adversarial scenarios, the paper suggests that directly applying counterplanning techniques could be a non-trivial but promising extension.
- Comparison with Other Formalisms: The paper acknowledges that direct comparison with other plan recognition approaches that use grammar parsing or explicit plan libraries is difficult due to differing formalisms.
- Computational Cost: While IGR's computational cost is comparable to IRM (due to deep function approximation in both), the MCTS rollouts can still be computationally intensive.
The authors suggest that future work should focus on evaluating IGR in more complex environments with partial observability and noisy observations, and exploring extensions for counterplanning and direct comparison with other plan recognition formalisms.
Summary updated