TL;DR
This paper presents a novel approach to automating the complex process of team formation for multi-agent systems. By leveraging advances in multi-agent epistemic planning, the authors enable an "initiator" agent to proactively plan how to assemble a team, assess member capabilities, and negotiate promises, all before any actual communication occurs. This work offers a principled and scalable way to operationalize collective intention.
What Problem Does This Paper Address?
Forming effective teams in multi-agent systems is a crucial but challenging problem. Cooperative problem-solving typically involves four phases: identifying potential members, forming the team, formulating a plan, and executing it. While existing work has explored various aspects, this paper focuses on the initiator's role in the first three phases, aiming to automate the cognitive process of team formation. The core challenge is how an initiator can reason about and plan for team assembly, including assessing agent capabilities and negotiating commitments, in a way that guarantees the team can achieve a collective goal. This is particularly difficult because it requires reasoning about agents' beliefs and intentions, and planning for uncertain dialogue outcomes.
Methods
The paper extends the Multi-Agent Epistemic Planning (MEP) formalism to handle non-deterministic actions, which are crucial for modeling dialogue and negotiation. This allows the initiator to plan for various possible responses from potential team members. The approach models team formation from the initiator's perspective, treating agents as "blindly committed" once they agree to join. The initiator's reasoning process is encoded as a single, integrated planning problem with three distinct stages:
- Capability Assessment: The initiator asks potential members about their abilities. This is modeled as a non-deterministic action with "yes" and "no" outcomes, allowing the initiator to plan for both possibilities.
- Bargaining: The initiator negotiates with agents by making promises (subgoals) to secure their willingness to join. This is also modeled as a non-deterministic action, reflecting agreement or refusal.
- Team Planning: Based on the commitments made, the initiator plans for the team to achieve the collective intention (original goal plus promises).
The entire process is encoded into a Fully Observable Non-deterministic (FOND) planning problem, allowing a planner to synthesize a conditional plan that guides the initiator's dialogue strategy.
Datasets
The authors use a modified version of the "Blocks World for Teams" (BW4T) domain as a testbed. This domain is extended to include agents with varied capabilities and tasks that can require multiple agents, making it suitable for modeling team formation. No new benchmark datasets were introduced; rather, the existing BW4T domain was adapted.
Key Insights and Ideas
- Proactive Planning for Dialogue: The most significant insight is that an initiator can and should plan for dialogue and team formation before any communication occurs. This allows for ruling out ineffective strategies and ensuring a higher chance of success.
- Epistemic Planning for Beliefs and Intentions: Using MEP is crucial because it allows the initiator to reason about agents' nested beliefs and how they might perceive their own objectives being met, which is essential for successful negotiation and commitment.
- Non-determinism as a Dialogue Model: Modeling questions and bargaining as non-deterministic actions effectively captures the uncertainty inherent in dialogue and allows for robust planning that accounts for various outcomes.
- Integrated Reasoning: Encoding all three stages (assessment, bargaining, planning) into a single planning problem allows for efficient reasoning and leverages modern planner capabilities like relevance analysis and policy reuse.
- Expressiveness of Beliefs: The distinction between problems 3 and 4 highlights how modeling agents' beliefs about the world (even if incorrect) can lead to different team formation strategies and outcomes, showcasing the power of epistemic reasoning.
Key Results
The paper demonstrates the feasibility of their approach through a preliminary evaluation using the BW4T domain. They successfully generated valid solutions for four different scenarios, showcasing the planner's ability to synthesize conditional plans for team formation. The results indicate that the approach is scalable, with solving times that are manageable even for complex scenarios. For instance, problems 3 and 4, which involved more complex bargaining and belief dynamics, took approximately 35 seconds to solve. The generated plans effectively guided the initiator through capability assessment and bargaining to form a team capable of achieving the collective goal.
Limitations and Future Work
The authors acknowledge that their current work focuses on the initiator's reasoning process and does not cover the actual execution of the plan or the dialogue phase itself. They also note that the agents are modeled as "blindly committed" once persuaded, which simplifies their behavior. Future work includes:
- Extending the encoding to include richer forms of dialogue within the team formation process.
- Exploring the domain of narrative planning, where sequenced speech acts are central.
- Further conceptual and empirical work to define the precise scope of their claim regarding the amenability of various team formation models to their planning-based approach.
- Using the work of Johnson [22] to assess the performance of teams created using their approach.
Summary updated