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

1. Problem Statement

The paper addresses the Multi-Agent Task Assignment and Planning (MATP) problem, specifically within heterogeneous robot teams operating in obstacle-rich and dynamic environments.

• Core Challenges:
  • Scalability: Traditional optimization methods struggle with large numbers of robots and tasks.
  • Spatial Reasoning: Standard task assignment often relies on Euclidean distance, ignoring obstacles, leading to infeasible paths or inefficient clustering.
  • Adaptability: Existing systems lack the ability to integrate real-time human instructions (e.g., adding tasks, changing priorities, or reporting new obstacles) during execution without stopping the mission.
  • Heterogeneity: Robots have varying capabilities (e.g., ground robots vs. drones, different payload capacities) that must be respected during allocation.

2. Methodology: The OATH Framework

The authors propose OATH, a hierarchical framework that integrates three main components: an adaptive spatial map, a cluster-auction-selection assignment algorithm, and an LLM-guided interaction loop.

A. Adaptive Obstacle-Aware Spatial Modeling

Instead of standard grid maps, OATH uses an Adaptive Halton Sequence Map:

• Mechanism: It generates a low-discrepancy sequence of sampling points. Crucially, it introduces a probabilistic acceptance function that adjusts point density based on proximity to obstacles.
  • Sparse sampling in open areas.
  • Dense sampling near obstacles and narrow passages to ensure navigability.
• Distance Calculation: A Dijkstra algorithm is run on this adaptive map to compute a task-to-task distance matrix. This ensures that the "cost" between tasks reflects actual traversability around obstacles, not just straight-line distance.

B. Hierarchical Task Assignment (Cluster–Auction–Selection)

To handle scalability and heterogeneity, the framework uses a three-stage process:

1. Obstacle-Aware Clustering: Tasks are grouped using agglomerative clustering based on the obstacle-aware distance matrix (not Euclidean distance). This prevents grouping tasks separated by walls.
2. Cluster-Weighted Auction (CWA):
   • Robots bid for task clusters based on two factors: spatial proximity (distance to cluster center) and capability compatibility (how well the robot's skills match the task types in the cluster).
   • A scoring function combines these factors to assign clusters to robots, resolving conflicts iteratively.
3. Intra-Cluster Task Selection: Once a robot is assigned a cluster, it solves a local Mixed-Integer Linear Programming (MILP) problem to determine the optimal sequence of pickup and delivery tasks within its capacity limits. This balances global efficiency with local optimality.

C. LLM-Guided Real-Time Interaction

The framework integrates Large Language Models (LLMs) as a persistent interpreter, not just a pre-mission planner.

• Function: The LLM parses natural language human instructions (e.g., "Add a task at coordinates X, Y" or "There is a new wall near Z") into structured JSON intents.
• Pipeline:
  • Add Task: The planner incrementally updates the Halton map and re-runs the assignment cycle.
  • Obstacle Update: The planner removes affected nodes/edges from the map and triggers replanning via D-Lite*.
  • Priority Change: The planner adjusts task weights and re-optimizes sequences.
• Clarification Loop: If an instruction is ambiguous, the LLM engages in a dialogue with the user to resolve missing parameters before updating the planner.

D. Path Planning

• Temporal Constraints: Task sequences are encoded using Linear Temporal Logic (LTL).
• Execution: A Büchi automaton is constructed from the LTL formula and composed with the environment transition system to form a Product Automaton.
• Search: The D-Lite* algorithm searches this product automaton for the optimal path, allowing for efficient dynamic replanning when new obstacles are detected.

3. Key Contributions

1. Adaptive Halton Sequence Map: The first application of Halton sampling with obstacle-aware density adaptation in MATP, providing a spatial foundation that balances sampling efficiency with navigability.
2. Hierarchical Heterogeneous Allocation: A novel Cluster–Auction–Selection framework that generalizes to any number of task types and robot capabilities, reducing computational complexity while maintaining constraint satisfaction.
3. LLM-Guided Online Pipeline: A fully integrated system where LLMs act as persistent interpreters for real-time human intervention, supporting dynamic task injection, obstacle updates, and priority shifts without mission interruption.
4. Comprehensive Validation: Extensive testing in NVIDIA Isaac Sim and real-world hardware experiments using TurtleBot3 platforms, demonstrating robustness to communication latency and sensing noise.

4. Experimental Results

The authors compared OATH against three baselines: CBBA (Consensus-Based Bundle Algorithm), KAN (K-means + Auction + Nearest Neighbor), and KAM (K-means + Auction + MILP).

• Efficiency & Scalability:
  • OATH demonstrated near-linear scaling in total running time and steps as the number of tasks increased (up to 100 tasks).
  • It achieved a 27.4% reduction in mission completion time compared to CBBA, despite slightly higher allocation computation time, because its assignments were more path-feasible.
  • OATH showed significantly lower sensitivity to problem complexity (task count, robot count, capacity) compared to CBBA and KAM.
• Solution Quality:
  • In small-scale tests (9–12 tasks), OATH solutions were within 16–24% of the global optimum (MILP/Gurobi) but computed in milliseconds vs. seconds/minutes for the solver.
  • For larger tasks (>15), the MILP solver often timed out, whereas OATH consistently produced feasible solutions.
• LLM Performance:
  • The LLM parser achieved 100% accuracy on obstacle updates and high accuracy on task/priority changes, with errors occurring only on highly ambiguous inputs (which triggered clarification loops).
  • The system successfully handled real-time replanning in hardware experiments, with the LLM inference time being the primary latency bottleneck (seconds), while the planner update was near-instantaneous (milliseconds).

5. Significance

This work bridges the gap between theoretical multi-robot planning and practical deployment in dynamic, real-world settings.

• Practicality: By validating on physical hardware with real communication delays and sensing noise, it proves that complex, obstacle-aware planning is feasible outside simulation.
• Human-in-the-Loop: It establishes a new paradigm for human-robot interaction, moving from static pre-mission planning to dynamic, language-driven adaptation, allowing operators to intervene seamlessly during execution.
• Robustness: The combination of adaptive sampling and hierarchical allocation provides a robust solution for heterogeneous teams in cluttered environments, addressing the "scalability vs. optimality" trade-off that plagues current MATP systems.