Min-Max Regret Task Allocation and Planning of Heterogeneous Multi-Robot System in Partially Known Environments

• URL: http://arxiv.org/abs/2607.13403v1
• Date: Wed, 15 Jul 2026 02:59:38 GMT
• Title: Min-Max Regret Task Allocation and Planning of Heterogeneous Multi-Robot System in Partially Known Environments
• Abstract summary: This paper presents a robust planning framework that simultaneously handles high-level logical constraints and environmental uncertainty without sacrificing scalability.<n>We show 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.
• Score: 5.229463033279081
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• DARRMS -- An Efficient Algorithm for Dynamic Attention Radius in Resource-Constrained Multi-Agent Systems [0.0]
  We introduce a new algorithm that allows for reduced demand on computational resources without a large cost of other performance metrics.<n>Agents will limit their observability to some attention radius, which intentionally allows them to ignore parts of the environment that might be unnecessary for action planning.
  arXiv  Detail & Related papers  (2026-06-10T19:14:56Z)
• Scalable Inspection Planning via Flow-based Mixed Integer Linear Programming [8.568142982906755]
  Inspection planning is concerned with computing the shortest robot path to inspect a given set of points of interest.<n>We present highly scalable Mixed Linear Programming (MILP) solutions for GIP that significantly advance the state-of-the-art in both runtime and solution quality.
  arXiv  Detail & Related papers  (2026-03-17T14:40:26Z)
• Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning [56.240199425429445]
  Multi-Robot Motion Planning (MPMP) involves generating trajectories for multiple robots operating in a shared continuous workspace.<n>While discrete multi-agent finding (MAPF) methods are broadly adopted due to their scalability, their coarse discretization trajectory quality.<n>This paper tackles limitations of two approaches by introducing discrete MAPF solvers with constrained generative diffusion models.
  arXiv  Detail & Related papers  (2025-08-27T17:59:36Z)
• Hierarchical Budget Policy Optimization for Adaptive Reasoning [49.621779447691665]
  We present Hierarchical Budget Policy Optimization (HBPO), a reinforcement learning framework that enables models to learn problem-specific reasoning depths without sacrificing capability.<n>HBPO partitions the exploration space into budget-constrained hierarchies (512-2560 tokens), each with differentiated reward structures that preserve both efficiency incentives and reasoning capabilities.<n>Extensive experiments demonstrate that HBPO reduces average token usage by up to 60.6% while improving accuracy by 3.14% across four reasoning benchmarks.
  arXiv  Detail & Related papers  (2025-07-21T17:52:34Z)
• Neural ATTF: A Scalable Solution to Lifelong Multi-Agent Path Planning [0.5701273481078372]
  This paper presents a new algorithm that combines a Priority Guided Task Matching (PGTM) Module with Neural STA* (Space-Time A*), a data-driven path planning method.<n>Tests against state-of-the-art MAPD algorithms, including TPTS, CENTRAL, RMCA, LNS-PBS, and LNS-wPBS, demonstrate the superior scalability, solution quality, and computational efficiency of Neural ATTF.
  arXiv  Detail & Related papers  (2025-04-21T14:25:32Z)
• Self-Supervised Learning-Based Path Planning and Obstacle Avoidance Using PPO and B-Splines in Unknown Environments [0.0]
  Smart BSP is an advanced self-supervised learning framework for real-time path planning and obstacle avoidance in autonomous robotics.<n>The proposed system integrates Proximal Policy Optimization (PPO) with Convolutional Neural Networks (CNN) and Actor-Critic architecture.<n>During the training process a nuanced cost function is minimized that accounts for path curvature, endpoint proximity, and obstacle avoidance.
  arXiv  Detail & Related papers  (2024-12-03T05:20:29Z)
• Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach [57.788675205519986]
  We learn high-quality traces from POMDP executions generated by any solver. We exploit data- and time-efficient Indu Logic Programming (ILP) to generate interpretable belief-based policy specifications. We show that learneds expressed in Answer Set Programming (ASP) yield performance superior to neural networks and similar to optimal handcrafted task-specifics within lower computational time.
  arXiv  Detail & Related papers  (2024-02-29T15:36:01Z)
• Hierarchical Constrained Stochastic Shortest Path Planning via Cost Budget Allocation [16.150627252426936]
  We propose a hierarchical constrained shortest path problem (HC-SSP) that meets those two crucial requirements in a single framework. The resulting problem has high complexity and makes it difficult to find an optimal solution fast. We present an algorithm that iteratively allocates cost budget to lower level planning problems based on branch-and-bound scheme to find a feasible solution fast and incrementally update the incumbent solution.
  arXiv  Detail & Related papers  (2022-05-11T01:25:38Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• Goal Kernel Planning: Linearly-Solvable Non-Markovian Policies for Logical Tasks with Goal-Conditioned Options [54.40780660868349]
  We introduce a compositional framework called Linearly-Solvable Goal Kernel Dynamic Programming (LS-GKDP)<n>LS-GKDP combines the Linearly-Solvable Markov Decision Process (LMDP) formalism with the Options Framework of Reinforcement Learning.<n>We show how an LMDP with a goal kernel enables the efficient optimization of meta-policies in a lower-dimensional subspace defined by the task grounding.
  arXiv  Detail & Related papers  (2020-07-06T05:13:20Z)
• Robust Reinforcement Learning with Wasserstein Constraint [49.86490922809473]
  We show the existence of optimal robust policies, provide a sensitivity analysis for the perturbations, and then design a novel robust learning algorithm. The effectiveness of the proposed algorithm is verified in the Cart-Pole environment.
  arXiv  Detail & Related papers  (2020-06-01T13:48:59Z)
• 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)

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.