Search papers, labs, and topics across Lattice.
This paper addresses the challenge of task allocation in Heterogeneous Multi-Robot Systems (HMRS) operating in partially known environments by introducing a min-max regret optimization framework. The authors propose a Region-Binding Atomic Proposition (RbAP) to encapsulate resource uncertainty and utilize an Extended Planning Decision Tree (E-PDT) with a Regret-based Branch-and-Bound strategy to efficiently balance exploration and exploitation. Experimental results show that this approach achieves near-linear scalability and significantly outperforms traditional MILP-based methods in both solution quality and computational efficiency.
Achieving near-linear scalability in multi-robot task allocation while effectively managing environmental uncertainty could revolutionize how we deploy heterogeneous robotic systems in complex settings.
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.
