Map-Consistency Preconditions for Multi-Robot Task Graphs

When several robots split up a mission, such as "clear the debris from the east entrance and stage it by the truck," the plan quietly assumes that everyone agrees on where things are. It assumes that "the east entrance" in the excavator's map and "the east entrance" in the hauler's map are the same physical spot. On real robots that assumption fails slowly. Each robot's estimate of its own position drifts as it moves, and the transform between two robots' maps is only as good as the last time they recognized a shared place. That event is called an inter-robot loop closure. Current language-model task planners write the plan as if positions were exact. Current multi-robot mapping systems correct drift passively, whenever loop closures happen to occur, and do not care which parts of the mission depend on it.

We propose to make map agreement a first-class part of the task plan. A language model breaks the mission into a dependency graph of subtasks, as existing planners do. A deterministic compiler then finds every point where two robots' subtasks are physically coupled, for example a hand-off, a shared destination, or one robot working where another reported something. For each such point it attaches a required tolerance on how well those two robots' maps must agree. It checks that requirement against the uncertainty reported by a distributed mapping back-end, and inserts a rendezvous or revisit subtask only where the requirement is not yet met. The claim is that spending drift correction where the task needs it, rather than uniformly, gets most of the reliability of aggressive active loop closure at a fraction of its detour cost. The claim also covers keeping the plan valid when the map later shifts under it.

Core Claim

Planners like DART-LLM produce a directed acyclic graph (DAG) of subtasks with temporal dependencies ("dig before haul"). They then dispatch those subtasks to fixed coordinates from a separate single-view detector. Their own ablation shows that making dependencies explicit matters a great deal: Llama-3.1 falls from 84% to 45% on collaborative tasks without the DAG. We argue there is a second, missing kind of dependency that is spatial rather than temporal. It is the requirement that two robots share a sufficiently consistent frame before a coupled subtask can succeed.

Concretely, for a coupled subtask $k$ between robots $i$ and $j$, let $\Sigma_{ij}$ be the marginal covariance of the relative transform between their map frames, as estimated by the distributed back-end. Let $\tau_k$ be the positional tolerance the subtask's skill requires, such as a few decimeters for a payload hand-off or meters for "search this region." The precondition is

$$\sqrt{\lambda_{\max}(\Sigma_{ij})} \le \tau_k,$$

where $\lambda_{\max}$ is the largest eigenvalue, so the left side is the worst-direction standard deviation of relative position. When the precondition is unmet, the compiler chooses a set $R$ of loop-closure subtasks to insert. These are rendezvous at a co-observable landmark, or a revisit to a landmark the other robot has mapped. It chooses $R$ to minimize the added mission time $\Delta T(R)$, subject to every coupled subtask's precondition holding, as predicted, at its scheduled start. The new part is that the constraint comes from the task graph, not from a global uncertainty budget.

Research Program

The system has three layers, and only the top one uses a language model. The top layer is a DAG decomposer in the style of DART-LLM. We run it both with a large cloud model and with an onboard Llama-3.1-8B, since DART-LLM reports 0.96 response-time reliability for that model at the edge. Its skill catalog is extended so that each skill carries a tolerance $\tau$, in the way SMART-LLM attaches payload limits to skills for coalition formation.

The middle layer is the compiler. It identifies coupled subtasks from the DAG. Its first job is to re-express every subtask goal relative to landmark identities rather than raw coordinates, so goals move with the map when it deforms. Its second job is to query the back-end for $\Sigma_{ij}$ and insert rendezvous nodes by solving the small constrained scheduling problem above. We will solve it exactly with integer programming for missions of the size in the benchmarks, and greedily for larger ones.

The bottom layer is an existing distributed metric-semantic back-end. Kimera-Multi supplies robust peer-to-peer loop-closure rejection through distributed graduated non-convexity, an outlier-robust optimization. SlideSLAM supplies sparse object landmarks at 1.84 KB each, which are natural rendezvous anchors. We reuse both; we do not build a new mapping algorithm. What we add to the back-end is an interface that exposes relative-frame covariances and landmark-association events to the compiler.

The loop closes during execution. When the back-end accepts or rejects an inter-robot loop closure, the compiler re-resolves landmark-anchored goals and re-checks preconditions. It then removes rendezvous nodes that have become unnecessary or adds new ones. The language model is re-queried only if a precondition cannot be met by any feasible rendezvous. This addresses the open-loop limitation that DART-LLM names as future work, without making every map update into a language-model call. It also keeps the system usable when the cloud uplink that Cladera et al. depend on is unavailable.

The work sits relative to prior efforts in three ways. Single-robot active loop closure motivates it by showing that revisits matter a lot. 3D Active Metric-Semantic SLAM cuts translation error by over 90% by trading exploration against semantic revisits, and Zhang et al. show an 8% flight-time detour preserves map fidelity. Both, however, optimize a single robot's global map quality, with no notion of which errors a mission can tolerate. Scalable Active Information Acquisition is multi-robot but switches behaviors on a uniform covariance threshold with no task semantics; it is our main competing design. The air-ground system of Cladera et al. is the closest end-to-end language-to-mission system. It relies on semantic-topological graphs with no metric back-end and a one-way scout-then-follow flow, so metric agreement between robots is never checked.

Baselines

The naive reference point is DART-LLM's pipeline as published. The DAG is dispatched to coordinates from each robot's own drifting map, with no active loop closure and no re-resolution. This measures how much of DART-LLM's reported success, 94% on its most complex tier with DeepSeek-r1-671B and 84% with Llama-3.1, survives once positions come from realistic drifting odometry instead of a reliable object map. No reported result was found on Lacuna for any LLM task planner's success under distributed-SLAM drift, so this number is itself a finding.

The second baseline is the same planner on top of Kimera-Multi with passive loop closure only. It tests whether a strong back-end alone suffices; Kimera-Multi reports trajectory error falling from about 20 m to under 0.15 m on Medfield once loop closures occur.

The strongest competitor is task-agnostic active loop closure. A uniform covariance threshold, in the style of Scalable Active Information Acquisition, triggers rendezvous or revisits whenever any inter-robot uncertainty exceeds it, beneath the same planner and back-end. We sweep the threshold over the same grid we use to set tolerances, and give it identical detection, communication, and compute budgets. Beating it means reaching equal or higher coupled-subtask success at significantly lower added mission time, or higher success at equal added time, across the whole Pareto curve and not at one tuned point. The closest published figure for its cost is the 8% detour of Zhang et al., single-robot. For its accuracy benefit, the closest is the over 90% translation-error reduction in 3D Active Metric-Semantic SLAM, also single-robot.

Two ablations isolate the key ingredients. The first keeps landmark-anchored goals and re-resolution but removes precondition-driven rendezvous insertion. The second keeps insertion but dispatches to raw coordinates.

Why not just…?

Why not just trigger loop closures on a global uncertainty threshold? This is the real threat, and the proposal is built to lose to it cleanly if it deserves to. If missions have many coupled subtasks spread evenly through time, a well-tuned uniform threshold will do what our compiler does. Our advantage should appear only when coupling is sparse or tolerances vary widely across skills. We will therefore report the Pareto comparison stratified by the number of coupled subtasks per mission and the spread of tolerances. If the tuned uniform threshold matches us across all strata, we will conclude that task-aware scheduling is unnecessary and publish that.

Why not just anchor subtask goals to landmark IDs and skip rendezvous scheduling? Anchoring fixes the case where the back-end shifts a corridor after a loop closure and a static DAG points at the old spot. It cannot help when the two robots have not yet associated any common landmark, which is exactly when their relative frame is most uncertain. The first ablation measures this directly. We expect it to recover most failures in missions with early natural overlap and few failures in long divergent missions, such as the kilometer-scale air-ground trials of Cladera et al.

Why not just give the covariances to the language model and let it add loop-closure steps? The evidence on language models and metric quantities is discouraging. Mouselinos et al. find spatial blindness and ordering biases even in 2D constructions, with pass@1 of 13.6% that rises to 28.1% only with a separate tool-executing agent. We will still run this variant with the same model and budget, prompting it with the covariance and tolerance table. The comparison shows whether the deterministic compiler is needed or whether a verifier-style agent, as in Self-collaboration Code Generation, is enough.

Why not just use a centralized server map? Centralization removes the relative-frame problem only while every robot is connected. Kimera-Multi's City Scene numbers, 1989.4 MB centralized versus 57.50 MB distributed, show the bandwidth cost. We treat centralized SLAM as an upper bound on map agreement rather than a deployable competitor.

Proposed Experiments

The main testbed is the Unity DCIST simulator (Camp and City scenes) that Kimera-Multi was evaluated in, running Kimera-Multi as the back-end. We port DART-LLM's 102 instructions into it with matched robot skills. The two-robot sequential and collaborative tiers contain the hand-offs and shared destinations that create coupled subtasks. We inject odometry drift at controlled levels, calibrated by replaying drift statistics from the Medfield State Hospital multi-robot data and the heterogeneous platforms in M3ED. We also inject perceptual-aliasing outliers up to the 70% rate used for Kimera-Multi.

Metrics are coupled-subtask success, whole-mission success, hand-off position error against simulator ground truth, added path length and mission time, bytes exchanged, and trajectory error. We also track how often the language model had to be re-queried.

The decisive check is a sweep over drift magnitude and coupling density. The prediction has two parts, both of which could fail. First, the naive DART-LLM pipeline's collaborative-tier success should fall steeply with drift while ours stays flat. Second, our added mission time should grow with the number of coupled subtasks, while the uniform-threshold baseline's grows with mission length. These follow because our rendezvous are triggered only by coupled preconditions, while threshold triggers fire whenever uncertainty accumulates. If the tuned uniform baseline sits on or beyond our Pareto frontier at every coupling density, the core claim is false.

A secondary check runs the full stack with onboard Llama-3.1-8B and a simulated uplink blackout mid-mission. It tests whether landmark re-resolution and precondition checking keep missions valid without any further language-model calls.