GptGet

MDGAM-Based Cooperative Task Scheduling for Communication-Constrained Distributed Multi-Agent Systems

TL;DR

MDGAM framework improves task completion by 4.13% using GRMAPG algorithm.

cs.MA 🔴 Advanced 2026-08-01 3 views
Licheng Wang Mingtao Huang Yuan Shen
AI Reader Arxiv Page Download PDF
multi-agent systems task scheduling graph attention model deep reinforcement learning distributed systems

Key Findings

Methodology

The paper proposes a neural scheduling framework for communication-constrained distributed multi-robot task allocation (MRTA), consisting of a multi-decoder graph attention model (MDGAM) policy model and a critic-free group relative multi-agent policy gradient (GRMAPG) training algorithm. MDGAM uses an extended graph attention mechanism to jointly update node and edge features, and employs multiple decoders to generate task-selection decisions and communication messages.

Key Results

  • Experiments show that under medium-scale settings with intermediate communication range, the MDGAM framework improves the number of completed tasks over PI-maxAss and CAM by 4.13% and 3.74%, respectively.
  • Across different problem scales and communication ranges, the MDGAM framework outperforms existing heuristic and learning methods in task completion performance.
  • Ablation studies validate the effectiveness of individual components within the MDGAM framework.

Significance

This research is significant in both academia and industry as it addresses long-standing pain points in multi-agent system task scheduling. By explicitly considering both task planning and communication-based coordination, the MDGAM framework improves execution efficiency, reducing runtime and communication costs.

Technical Contribution

Technical contributions include proposing a novel multi-decoder graph attention architecture capable of task planning in communication-constrained environments. The GRMAPG algorithm reduces trainable parameters and improves training convergence, enabling end-to-end policy optimization.

Novelty

The MDGAM framework is the first to combine task planning and communication coordination in distributed task scheduling, significantly differing from existing methods. Compared to related work, it offers new theoretical guarantees and engineering possibilities.

Limitations

  • Information propagation may be limited in communication-constrained environments, affecting task planning effectiveness.
  • The computational complexity of the framework may increase significantly with the number of tasks and agents.
  • In extreme cases, additional communication resources may be required to ensure information exchange.

Future Work

Future work may include extending the MDGAM framework to accommodate more types of tasks and agent attributes, and exploring more efficient communication protocols to further enhance task scheduling performance.

AI Executive Summary

Cooperative task scheduling in communication-constrained distributed multi-agent systems is challenging because each agent must make decisions from partial and dynamic observations while satisfying complex practical constraints. Existing heuristics rely on handcrafted bidding rules and repeated consensus, whereas many learning-based methods assume global observations and lack explicit communication-based coordination. To address these limitations, this paper proposes a neural scheduling framework for distributed multi-robot task allocation (MRTA), consisting of a multi-decoder graph attention model (MDGAM) policy model and a critic-free group relative multi-agent policy gradient (GRMAPG) training algorithm. MDGAM uses an extended graph attention mechanism to jointly update node and edge features, and employs multiple decoders to generate task-selection decisions and communication messages. GRMAPG constructs group-relative advantages from equivalent task-planning instances to replace the critic network used in conventional MARL algorithms, thereby reducing training difficulty and improving convergence performance. Experiments under different problem scales and communication ranges show that the proposed method improves task-completion performance over existing heuristic and learning-based methods, while ablation, complexity, and generalization tests further validate the proposed innovations.

Deep Analysis

Background

Distributed multi-agent systems are increasingly deployed in intelligent transportation, Internet of Things, and emergency-response scenarios, where robots, vehicles, or UAVs must cooperate to serve spatially distributed tasks under limited sensing, computation, and communication resources. Multi-robot task allocation (MRTA) addresses the assignment and scheduling of tasks for a robot team through centralized optimization or distributed coordination. Given heterogeneous robots and spatially distributed tasks, its objective is to determine task-execution sequences that optimize a global performance metric, such as task completion, collected reward, or travel cost.

Core Problem

In communication-constrained environments, task scheduling faces challenges of incomplete and dynamically changing information. Each agent only has access to partial and time-varying information and must coordinate with nearby peers through limited communication links. This paper considers a communication-constrained MRTA problem with heterogeneous robot attributes, various task constraints, and limited communication ranges.

Innovation

The paper proposes a novel neural scheduling framework that combines task planning and communication coordination. MDGAM uses an extended graph attention mechanism to update node and edge features, and employs multiple decoders to generate task-selection decisions and communication messages. The GRMAPG algorithm constructs group-relative advantages from equivalent task-planning instances, replacing the critic network used in conventional MARL algorithms.

Methodology

  • �� MDGAM framework uses an extended graph attention mechanism to jointly update node and edge features.
  • �� Multiple decoders generate task-selection decisions and communication messages.
  • �� GRMAPG algorithm constructs group-relative advantages from equivalent task-planning instances, reducing training difficulty and improving convergence performance.

Experiments

Experiments are conducted under different problem scales and communication ranges, comparing the MDGAM framework with existing heuristic and learning methods in task completion performance. Under medium-scale settings with intermediate communication range, the MDGAM framework improves the number of completed tasks over PI-maxAss and CAM by 4.13% and 3.74%, respectively.

Results

Experimental results show that the MDGAM framework outperforms existing heuristic and learning methods in task completion performance. Ablation studies validate the effectiveness of individual components within the MDGAM framework. Complexity and generalization tests further evaluate the proposed method in terms of component effectiveness, runtime and communication cost.

Applications

The MDGAM framework is suitable for a broad range of distributed task-planning applications and can be flexibly transferred to related scenarios with different practical constraints and settings. Experimental results show that the proposed method achieves higher task-completion performance than existing distributed algorithms, with additional advantages in runtime and communication cost.

Limitations & Outlook

Information propagation may be limited in communication-constrained environments, affecting task planning effectiveness. The computational complexity of the framework may increase significantly with the number of tasks and agents. In extreme cases, additional communication resources may be required to ensure information exchange.

Plain Language Accessible to non-experts

Imagine a kitchen where chefs need to complete various dishes within limited time and space. Each chef can only see the ingredients in front of them and coordinate with other chefs through limited communication. The MDGAM framework acts like a smart assistant, helping chefs optimize task allocation and coordination within limited communication range. The GRMAPG algorithm is like a clever scheduler, reducing repetitive work and improving dish completion efficiency.

ELI14 Explained like you're 14

Imagine you're in a game with friends, each having different abilities and tasks. You can only communicate within a limited range, how do you complete all the tasks? The MDGAM framework is like a super captain, helping you optimize task allocation and coordination in the game. The GRMAPG algorithm is like a smart assistant, reducing repetitive work and improving task completion efficiency.

Glossary

MDGAM (Multi-Decoder Graph Attention Model)

A neural network architecture for distributed task planning, combining task planning and communication coordination.

Used to generate task-selection decisions and communication messages.

GRMAPG (Critic-Free Group Relative Multi-Agent Policy Gradient)

A training algorithm for policy optimization that constructs group-relative advantages to reduce training difficulty.

Used to replace the critic network in conventional MARL algorithms.

Dec-POMDP (Decentralized Partially Observable Markov Decision Process)

A model for describing distributed task planning processes, considering partial observation and communication constraints.

Used to model the distributed task planning process.

MRTA (Multi-Robot Task Allocation)

A method for solving task assignment and scheduling problems for robot teams through centralized optimization or distributed coordination.

Used to optimize task execution sequences.

Graph Attention Mechanism

A mechanism for updating node and edge features using multi-head attention operations.

Used in the MDGAM framework for information exchange.

Open Questions Unanswered questions from this research

  • 1 How to effectively schedule tasks in larger-scale communication-constrained environments?
  • 2 How to further optimize communication protocols to enhance task scheduling performance?
  • 3 How to ensure effective information exchange in extreme scenarios?

Applications

Immediate Applications

Intelligent Transportation

The MDGAM framework can be used to optimize task scheduling in transportation systems, improving traffic efficiency and safety.

Long-term Vision

Internet of Things

In IoT scenarios, the MDGAM framework can be used to optimize task coordination between devices, enhancing overall system performance.

Abstract

Cooperative task scheduling in communication-constrained distributed multi-agent systems is challenging because each agent must make decisions from partial and dynamic observations while satisfying complex practical constraints. Existing heuristics rely on handcrafted bidding rules and repeated consensus, whereas many learning-based methods assume global observations and lack explicit communication-based coordination. To address these limitations, this paper proposes a neural scheduling framework for distributed multi-robot task allocation (MRTA), consisting of a multi-decoder graph attention model (MDGAM) policy model and a critic-free group relative multi-agent policy gradient (GRMAPG) training algorithm. MDGAM uses an extended graph attention mechanism to jointly update node and edge features, and employs multiple decoders to generate task-selection decisions and communication messages. GRMAPG constructs group-relative advantages from equivalent task-planning instances to replace the critic network used in conventional MARL algorithms, thereby reducing training difficulty and improving convergence performance. Experiments under different problem scales and communication ranges show that the proposed method improves task-completion performance over existing heuristic and learning-based methods, while ablation, complexity, and generalization tests further validate the proposed innovations.

cs.MA