D e MAC : Enhancing Multi-Agent Coordination with Dynamic DAG and Manager-Player Feedback (2025)

Abstract: Multi-agent systems (MAS) powered by large language models (LLMs) have shown potential in tackling multifaceted problems through advanced understanding and reasoning. However, they struggle to adapt to evolving task dependencies and to handle uncertainties, such as shifting priorities or unpredictable disruptions. These constraints undermine their ability to dynamically adjust long-term strategies and inter-agent collaboration. To address these challenges, we propose DeMAC, a Dynamic Environment-Aware Manager-Player Agents Coordination framework that enhances multi-agent coordination through long-term strategic planning. DeMAC uses a dynamically updated directed acyclic graph (DAG) and a Manager-Player Dual-Feedback mechanism to align strategic and operational decisions. Moreover, DeMAC enables agents to maintain collaboration and dynamically adapt to changing environmental conditions, outperforming traditional reinforcement learning and human-agent collaboration in the Overcooked simulation. Experimental results highlight DeMAC’s ability to tackle complex coordination tasks, demonstrating its potential to advance LLM-based MAS in dynamic, complex task dependency environments.

## introduction multi-agent systems (mas) based on large language models (llms) @xcite have shown significant potential in tackling multifaceted challenges by utilizing llms' advanced language understanding, reasoning, and generalization capabilities. llm-based multi-agents are applied to abstract language tasks including debates, fact verification, and third-party arbitration @xcite @xcite . beyond * : corresponding author these abstract tasks, recent investigations have begun evaluating their efficacy in physical simulation environments @xcite @xcite . in these settings, mas often require strategic reasoning capabilities that not only enable agents to navigate dynamic environments but also anticipate or plan actions from other agents @xcite @xcite . the overcooked environment is widely leveraged in mas research @xcite for its realistic simulation of complex tasks and dynamic interactions, ideal for multiagent coordination @xcite . the variety of items and actions influences environmental uncertainty and task dependencies. figure 1a illustrates a scenario where the variety of items and actions are limited, the task flow is relatively fixed, resulting in low-level uncertainty. in low-level uncertainty scenario, agents only require basic coordination because task dependency relationships are clear. in contrast, figure 1b depicts a dynamically changing environment with diverse task flows, leading to high-level uncertainty driven by factors like ingredient locations, pot states, and resource competition, which complicate task dependencies. action sequences (e.g., chopping lettuce or onions first) reshape dependencies, influencing task prioritization and coordination. in high-level uncertainty, agents must adapt their coordination strategies to address changing conditions and evolving task dependencies. in overcooked environments, most llm-based mas @xcite @xcite @xcite rely on a synthesis of reinforcement learning and human-agent interaction. however, in complex task dependency and uncertain environments (figure 1b ), these approaches demonstrate some constraints. reinforcement learning optimizes individual agent policies but limits global perspective and long-term collaboration @xcite @xcite . this results in misaligned objectives and inefficiencies in multi-agent collaboration @xcite , ultimately undermining cohesive team performance. human-agent interaction enables decentralized collaboration @xcite , but it struggles to cope with the dynamic and unpredictable nature of human decisions, such as suddenly extinguishing a fire or deviating from planned tasks. this process frequently leads to re-planning of tasks, ultimately hindering effective coordination. these approaches are insufficient for delivering cohesive long-term strategies and dynamic inter-agent collaboration required for complex task dependency, uncertain environments. to address these limitations, we propose dynamic environment-aware manager-player agent coordination framework (demac), which targets the challenges of task dependencies and uncertainties in mas. demac utilizes a directed acyclic graph (dag) (similar to the task flow in figure 1b ) to represent task dependencies and execution order. this ensures that agents follow a consistent, conflict-free plan, addressing the limitations of previous methods, where agent coordination often leads to conflicting goals and inconsis-tent task execution. demac consists of three key modules: (i) dynamic dag information update: this module ensures the dag remains updated to reflect task progress and environmental changes, addressing task dependencies and uncertainty. dynamically adjusts the task flow, optimizing task order, and minimizing conflicts. (ii) manager-player dual-feedback: integrates strategy formulation and high-level planning to synchronize both strategic and operational decisions and employs a reflection loop to optimize agent coordination and ensure alignment with long-term goals. (iii) environment perception: converts environmental data into actionable insights by abstracting grid-level observations into high-level representations, allowing agents to adjust their strategies and reduce uncertainty in decision-making. in summary, the key contributions of this paper are as follows: ## experiments in this section, we present the experimental setup and results to evaluate the demac framework's performance. we conducted experiments in two overcooked environments foot_4 @xcite to assess demac under varying task complexities. the experiments focus on evaluating the effectiveness of demac in terms of task completion, efficiency, and adaptability across different layouts and environments. ## conclusion this paper proposes the demac framework that integrates long-term planning into llm-based multi-agent systems for collaborative tasks. by leveraging dynamic dag structures for task decomposition and harmonizing actions, demac enables agents to maintain coherence amidst intricate dependencies and environmental uncertainties. experiments conducted in the overcooked simulation environment show significant improvements in traditional reinforcement learning methods and human-agent collaboration in terms of game score, success rate and task completion efficiency. future work includes extending demac to more diverse and realistic environments and exploring its applicability in real-world scenarios that require sophisticated agent coordination and long-term planning.