Adaptive Obstacle-Aware Task Assignment and Planning for Heterogeneous Robot Teaming (OATH)

Multi-Agent Task Assignment and Planning (MATP) has attracted growing attention but remains challenging in terms of scalability, spatial reasoning, and adaptability in obstacle-rich environments.

To address these challenges, we propose OATH (Adaptive Obstacle-Aware Task Assignment and Planning for Heterogeneous Robot Teaming). Our OATH framework advances MATP by introducing two novel obstacle-aware strategies for task allocation. First, we develop an adaptive Halton sequence map, the first known application of Halton sampling with obstacle-aware adaptation in MATP, which adjusts sampling density based on obstacle distribution. Second, we integrate Dijkstra task-to-task distance matrices that encode traversability. Combined, these strategies significantly improve allocation quality in obstacle-rich environments. For task assignment, we propose a cluster–auction–selection framework that integrates obstacle-aware clustering with weighted auctions and intra-cluster task selection. These mechanisms jointly enable effective coordination among heterogeneous robots while maintaining scalability and near-optimal allocation performance. In addition, our framework leverages an LLM to interpret human instructions and directly guide the planner in real time.

We validate OATH in Isaac Sim, showing substantial improvements in task allocation quality, scalability, adaptability to dynamic changes, and overall execution performance compared to state-of-the-art MATP baselines.

The OATH introduces an adaptive Halton sequence that dynamically adjusts sampling density based on obstacle distribution. In addition, the proposed hierarchical cluster–auction–task selection scheme generalizes to any number of task types and reduces allocation complexity while respecting robot capacity and capability constraints. Together, these components enable scalable and near-optimal task assignment for heterogeneous robot teams operating in obstacle-rich environments.

Beyond task assignment, OATH integrates LLMs as persistent interpreters throughout the execution phase. Unlike prior approaches that employ LLMs only for initialization, our framework continuously leverages LLMs to translate natural language instructions into structured constraints and task updates. This design ensures ongoing adaptability to dynamic human intent, unforeseen obstacles, and mission changes.