A neural scheduling framework for distributed multi-robot task allocation, consisting of a multi-decoder graph attention model (MDGAM) policy model and a critic-free group relative multi-agent policy gradient (GRMAPG) training algorithm, which improves task-completion performance over existing heuristic and learning-based methods.
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.
This article investigates the time-constrained multirobot efficient search (MuRES) problem, focusing on the asynchronous coordination among multiple robots. To the best of authors’ knowledge, almost all MuRES solutions adopt the synchronous decision-making framework, wherein the robots act simultaneously. The synchronous assumption simplifies the MuRES problem formulation and facilitates the development of coordination search strategies. However, in real-world scenarios, spatial variability and heterogeneous motion characteristics render the synchronous execution scheme inefficient, leading to large idle time and poor task allocation. To address these limitations, we introduce the multiagent asynchronous probability-decomposed policy gradient (MA-APD) algorithm, which targets the asynchronous multirobot efficient search problem. MA-APD comprises two core components: first, the generalized value function approximation module, which evaluates and asynchronously decomposes the nonconvex time-constrained MuRES objective, and second, the asynchronous policy gradient module, which maps the decomposed value function onto individual robot’s decision-making timeline, enabling the asynchronous actor updates. To improve MA-APD’s sample efficiency and training stability, we further introduce an off-policy learning mechanism, a soft update module, and an entropy regularization term. Extensive simulation results in canonical MuRES environments indicate that MA-APD consistently outperforms canonical MuRES solutions as well as multiagent reinforcement learning algorithms. Furthermore, MA-APD is deployed to a physical multirobot system for moving target search in both self-constructed and realistic indoor environments, validating its practical effectiveness.
Qihang Peng, Hongliang Guo, Chih-yung Wen et al.· IEEE Transactions on robotic...· 0 citations
Multi-agent path planning (MAPP) under partial observability requires agents to coordinate their movements and complete tasks efficiently without access to global information. The planning space and coordination complexity grow rapidly with increasing numbers of agents, targets, and obstacles. We formulate large-scale MAPP as a partially observable networked Markov decision process. Based on this formulation, we propose a decentralized model-based Actor-Critic using the Kronecker-factored trust region (DM-ACKTR) algorithm. The algorithm integrates local model learning with ACKTR-based policy optimization in an independent learning architecture. Each agent learns a local model to predict the next observation and reward. These predictions are used to construct additional transitions for Actor and Critic updates. A neighborhood-based communication mechanism incorporates information from nearby agents into value estimation. Region partitioning reduces each agent’s effective planning space. These improvements enable DM-ACKTR to continue outperforming the baseline algorithms as the scale of the MAPP problem increases. Experiments across three training and five evaluation scenarios show that DM-ACKTR achieves the best overall performance. Among the five evaluated algorithms, it consistently obtains the highest TCR and lowest CR, improving TCR by 2.06–4.35% and reducing CR by 11.26–25.95% relative to the respective best baselines.
Ye-Min Liu, Jinhao Yang, Xiang-Yu Ma et al.· Electronics· 0 citations
Decentralized multi-robot task allocation (MRTA) is essential for scalable and resilient autonomous systems. The Consensus-Based Bundle Algorithm (CBBA) is a widely adopted decentralized baseline. However, its individual task-level bidding is poorly aligned with the min-sum objective of minimizing total team travel distance, leading to suboptimal allocations in spatially distributed environments. This paper introduces the Grouping Auction-Consensus Algorithm (GACA). This decentralized MRTA framework adopts the two-phase auction-consensus architecture of CBBA while fundamentally redesigning its bidding mechanism to reason over groups of spatially proximate tasks. A nearest-neighbor preprocessing step partitions tasks into spatially coherent groups before allocation. Agents then iteratively propose structured group-level actions: claiming unassigned groups, acquiring partial groups, or contesting groups held by other agents. Competing actions are resolved through a consensus phase. Operating in the MT-SR-IA problem class, GACA is evaluated against CBBA using a Mixed-Integer Linear Program as the ground-truth optimality reference. Across four swarm sizes and 4,000 test worlds, GACA achieves a median percent optimality of approximately 97% compared to 81--84% for CBBA, while converging in equal or fewer iterations. A scalability evaluation over 3,280 additional problem instances spanning swarm sizes of 5 to 20 agents and task counts of 10 to 50 confirms that these gains generalize robustly across a wide range of problem configurations.
J. Rodriguez, Sven Koenig, Wenjie Dong et al.· 0 citations
Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective start locations to their respective goal locations while minimizing path costs.
Many MAPF studies rely on a common assumption of synchronized actions, where the actions of all agents start at the same time and always take a time unit, which may limit the applicability of MAPF planners in practice.
To bypass this assumption, various algorithms have been developed to handle asynchronous, non-unit-time actions, ranging from optimal to unbounded sub-optimal algorithms.
This paper focuses on bounded sub-optimal algorithms for MAPF with asynchronous actions (MAPF-AA) due to their ability to balance solution quality and runtime efficiency.
For MAPF, the recent bounded sub-optimal algorithms can intelligently distribute the sub-optimality bound among the agents based on agent-agent collision to achieve fast planning even with tight bounds.
We find that directly adapting these techniques to MAPF-AA can degrade their performance due to asynchronous actions.
This paper thus develops new techniques to consider asynchronous actions when distributing the sub-optimality bound among the agents and when selecting nodes for expansion during planning.
Results show that our approach achieves up to 60% higher success rates and reduces the number of expansions during planning by up to an order of magnitude compared to existing methods.
Xuemian Wu, Shizhe Zhao, Zhongqiang Ren· Proceedings of the Internati...· 0 citations
Efficient task allocation for large-scale Heterogeneous Multi-Robot Systems (HMRS) is critical, yet dealing with complex temporal logic tasks in partially known environment (PKE) remains a computational bottleneck. Existing approaches often struggle to balance exploring uncertain regions and exploiting known resources, while also suffering from exponential computational complexity. To address these issues, this paper presents a robust planning framework that simultaneously handles high-level logical constraints and environmental uncertainty without sacrificing scalability. We formulate the problem as a min-max regret optimization, proposing a Region-Binding Atomic Proposition (RbAP) to capture resource uncertainty within the automaton structure. To solve this, we propose the Extended Planning Decision Tree (E-PDT) equipped with a novel Regret-based Branch-and-Bound (BnB) strategy. Unlike traditional methods that rely on prior probabilities or worst-case analysis, our approach dynamically prunes suboptimal policies, effectively balancing the need for information gathering (exploration) and task completion (exploitation). Theoretical analysis confirms the feasibility and completeness of our approach. Extensive numerical and physical experiments demonstrate that the proposed framework achieves near-linear scalability with respect to the number of robots and types, significantly outperforming MILP-based baselines in both solution quality and computational efficiency. Note to Practitioners—Task allocation for large-scale heterogeneous multi-robot systems is critical in applications like warehouse logistics and disaster response. However, existing planning methods often struggle with environmental uncertainty, relying on unavailable probability data or failing to scale. This work presents a fast, robust planning framework that uses a regret-minimization strategy to balance exploring uncertain areas with completing tasks. Unlike optimization-based approaches that can be computationally prohibitive, our E-PDT method achieves near-linear scalability, coordinating thousands of robots in seconds. This allows practitioners to deploy large robot fleets that adaptively search for resources without needing precise prior knowledge. Current limitations assume a known static map topology with uncertain resource locations; future extensions will address fully dynamic and unknown environments.
Xinkai Liang, Hui-Xuan Chan, Ying Liu et al.· IEEE Transactions on Automat...· 0 citations
This paper develops a multi-agent reinforcement learning-based (MARL) delegation training that enables agents to make sequential delegation decisions while minimizing the total execution cost and introduces two new frameworks for collaboration and delegation in multi-agent systems.
Ziqing Lu, Avinash Mudireddy, Sarra M. Alqahtani et al.· 0 citations