Dynamic Multi-Robot Task Allocation under Uncertainty and Communication Constraints: A Game-Theoretic Approach

• URL: http://arxiv.org/abs/2604.11954v1
• Date: Mon, 13 Apr 2026 18:48:51 GMT
• Title: Dynamic Multi-Robot Task Allocation under Uncertainty and Communication Constraints: A Game-Theoretic Approach
• Abstract summary: We study dynamic multi-robot task allocation under uncertain task completion, time-window constraints, and incomplete information.<n>We model incomplete information through hub-based sensing regions that determine task visibility and a communication graph that governs inter-hub information exchange.<n>Using this framework, we propose Iterative Best Response (IBR), a decentralized policy in which each agent selects the task that maximizes its marginal contribution to locally observed welfare.
• Score: 2.7148994623424207
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study dynamic multi-robot task allocation under uncertain task completion, time-window constraints, and incomplete information. Tasks arrive online over a finite horizon and must be completed within specified deadlines, while agents operate from distributed hubs with limited sensing and communication. We model incomplete information through hub-based sensing regions that determine task visibility and a communication graph that governs inter-hub information exchange. Using this framework, we propose Iterative Best Response (IBR), a decentralized policy in which each agent selects the task that maximizes its marginal contribution to the locally observed welfare. We compare IBR against three baselines: Earliest Due Date first (EDD), Hungarian algorithm, and Stochastic Conflict-Based Allocation (SCoBA), on a city-scale package-delivery domain with up to 100 drones and varying task arrival scenarios. Under full and sparse communication, IBR achieves competitive task-completion performance with lower computation time.

Related papers

• Beyond Task-Agnostic: Task-Aware Grouping for Communication-Efficient Multi-Task MoE Inference [16.917643169487402]
  We propose emphTask-Aware Coactivation Grouping (TACG) to group experts by task-aware co-activation.<n>We also introduce emphGeneric Expert Shared Replication (GESR) to identify generic experts with consistently central co-activation profiles.<n>Our framework reduces the average communication cost by 31.39% over the baseline, while preserving an average Jain fairness index of 0.9975.
  arXiv  Detail & Related papers  (2026-05-31T04:51:09Z)
• Edge-AI-Driven Learning-to-Rank for Decentralized Task Allocation in Circular Smart Manufacturing [54.4933359656657]
  This work proposes an Edge-AI-driven decentralized task allocation framework based on ranking-aware negotiation.<n>A ranking-aware formulation finally reshapes the learning objective to align with the ordering-based nature of winner selection.<n>Results show improved delay and deadline adherence under high load, and enhanced energy efficiency under tighter constraints.
  arXiv  Detail & Related papers  (2026-05-14T20:38:25Z)
• Improving the Efficiency of Language Agent Teams with Adaptive Task Graphs [52.26652574704317]
  Large language models (LLMs) are increasingly deployed in teams, yet existing coordination approaches often occupy two extremes.<n>We introduce Language Agent Teams for Task Evolution (LATTE), a framework for coordinating LLM teams inspired by distributed systems.
  arXiv  Detail & Related papers  (2026-05-07T14:19:17Z)
• GoAgent: Group-of-Agents Communication Topology Generation for LLM-based Multi-Agent Systems [55.12339141172908]
  GoAgent is a communication topology generation method that explicitly treats collaborative groups as the atomic units of MAS construction.<n>Experiments on six benchmarks demonstrate the state-of-the-art performance of GoAgent with 93.84% average accuracy while reducing token consumption by about 17%.
  arXiv  Detail & Related papers  (2026-03-20T06:21:32Z)
• Self-Configurable Mesh-Networks for Scalable Distributed Submodular Bandit Optimization [6.522338519818377]
  We study how to scale distributed bandit submodular coordination under realistic communication constraints in bandwidth, data rate, and connectivity.<n>Our approach enables near-optimal action coordination by optimizing the agents' communication neighborhoods over time.<n>It is observed to converge faster, outperform benchmarks for bandit submodular coordination, and can even outperform benchmarks that are privileged with a priori knowledge of the environment.
  arXiv  Detail & Related papers  (2026-02-22T22:36:37Z)
• Prompt-Based Spatio-Temporal Graph Transfer Learning [22.855189872649376]
  We propose a prompt-based framework capable of adapting to multi-diverse tasks in a data-scarce domain. We employ learnable prompts to achieve domain and task transfer in a two-stage pipeline. Our experiments demonstrate that STGP outperforms state-of-the-art baselines in three tasks-forecasting, kriging, and extrapolation-achieving an improvement of up to 10.7%.
  arXiv  Detail & Related papers  (2024-05-21T02:06:40Z)
• Distributed Multi-Task Learning for Stochastic Bandits with Context Distribution and Stage-wise Constraints [0.0]
  We present conservative distributed multi-task learning in linear contextual bandits with heterogeneous agents.<n>The exact context is unknown, and only a context distribution is available to the agents.<n>Our algorithm constructs a pruned action set during each round to ensure the constraints are met.<n>It includes synchronized sharing of estimates among agents via a central server.
  arXiv  Detail & Related papers  (2024-01-21T18:43:55Z)
• Federated Natural Policy Gradient and Actor Critic Methods for Multi-task Reinforcement Learning [46.28771270378047]
  Federated reinforcement learning (RL) enables collaborative decision making of multiple distributed agents without sharing local data trajectories. In this work, we consider a multi-task setting, in which each agent has its own private reward function corresponding to different tasks, while sharing the same transition kernel of the environment. We learn a globally optimal policy that maximizes the sum of the discounted total rewards of all the agents in a decentralized manner.
  arXiv  Detail & Related papers  (2023-11-01T00:15:18Z)
• Learning Connectivity for Data Distribution in Robot Teams [96.39864514115136]
  We propose a task-agnostic, decentralized, low-latency method for data distribution in ad-hoc networks using Graph Neural Networks (GNN) Our approach enables multi-agent algorithms based on global state information to function by ensuring it is available at each robot. We train the distributed GNN communication policies via reinforcement learning using the average Age of Information as the reward function and show that it improves training stability compared to task-specific reward functions.
  arXiv  Detail & Related papers  (2021-03-08T21:48:55Z)
• Learning Task-oriented Disentangled Representations for Unsupervised Domain Adaptation [165.61511788237485]
  Unsupervised domain adaptation (UDA) aims to address the domain-shift problem between a labeled source domain and an unlabeled target domain. We propose a dynamic task-oriented disentangling network (DTDN) to learn disentangled representations in an end-to-end fashion for UDA.
  arXiv  Detail & Related papers  (2020-07-27T01:21:18Z)
• Bottom-up mechanism and improved contract net protocol for the dynamic task planning of heterogeneous Earth observation resources [61.75759893720484]
  Earth observation resources are becoming increasingly indispensable in disaster relief, damage assessment and related domains. Many unpredicted factors, such as the change of observation task requirements, to the occurring of bad weather and resource failures, may cause the scheduled observation scheme to become infeasible. A bottom-up distributed coordinated framework together with an improved contract net are proposed to facilitate the dynamic task replanning for heterogeneous Earth observation resources.
  arXiv  Detail & Related papers  (2020-07-13T03:51:08Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)
• Distributed Primal-Dual Optimization for Online Multi-Task Learning [22.45069527817333]
  We propose an adaptive primal-dual algorithm, which captures task-specific noise in adversarial learning and carries out a projection-free update with runtime efficiency. Our model is well-suited to decentralized periodic-connected tasks as it allows the energy-starved or bandwidth-constraint tasks to postpone the update. Empirical results confirm that the proposed model is highly effective on various real-world datasets.
  arXiv  Detail & Related papers  (2020-04-02T23:36:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.