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

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. 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.