Systematic Multi-Agent Vision-and-Language Navigation: Formulation, Benchmark, and Method

AI summary

Overview

Research area: Embodied AI / Vision-and-Language Navigation (VLN), specifically multi-agent embodied navigation in continuous 3D environments (computer vision and robotics).

Technical level: Advanced. It assumes familiarity with VLN-CE, topological mapping, imitation learning, LLM-based task planning, and multi-agent path finding.

Scope (one sentence): The paper formalizes multi-agent VLN as a dependency- and resource-constrained coordination problem, releases a benchmark (MAVLN) with 11,724 episodes across 145 scenes, and proposes a baseline system (TRISS) combining an LLM subtask scheduler, a shared topological memory, and conflict-aware execution.

What This Paper Is About

Most VLN research has one agent following one instruction to one nearby goal. Real deployments often need a team of robots to split a mission into subtasks that depend on each other (one agent must finish before another can act) and that tie up resources (an agent carrying an object, or an agent that must stay put until a teammate releases it). The paper defines this problem formally, builds an automatically generated and verified benchmark for it in unseen HM3D scenes, and proposes a coordination-ready baseline system to measure how far current methods are from solving it.

Key Contributions

1. A systematic formulation of multi-agent VLN. To the authors' knowledge, this is the first formalization of multi-agent VLN as a constrained coordination problem: a mission is a DAG of subtasks, each carrying permitted executors, prerequisite subtasks, and resource attributes (holding chains and presence locks), with per-subtask success defined by arrival inside a success radius under all constraints.
2. A verified four-stage task-crafting pipeline. Grounded scene understanding (VLM descriptions at viewpoint granularity summarized to zones), diverse mission synthesis from household profiles and zone features, mission instantiation with makespan optimization, and verified instruction rendering with a closed-loop filter that checks LLM-reconstructed arrival sequences against ground-truth constraints. The backbone LLM across the four curation stages is from the Gemini-3 series.
3. The MAVLN benchmark and platform. 11,724 episodes across 145 scenes with teams of up to 4 agents and three instruction regimes (decentralized, centralized, centralized-implicit), built on Habitat 3 with HM3D, plus constraint-aware metrics (SR, SPL, CSR, ISPL/CSPL, TC, TS, MAC). The paper states MAVLN is the first multi-agent VLN benchmark supporting flexible team sizes and the first embodied navigation benchmark to include dependency and resource constraints plus inter-agent conflict measurement.
4. The TRISS system. A coordination-ready baseline coupling a compact LLM subtask scheduler with shared topological memory and a conflict-aware execution mechanism (conflict-free target allocation via the Hungarian algorithm, Conflict-Based Search path planning, and topology maintenance).

Main Findings

• Oracle upper bound with parallelism: With oracle scheduling and oracle navigation, TRISS reaches 100.0 SR with 215 time steps on val-unseen and 206 on test-unseen, showing the task is solvable and that multi-agent execution is feasible.
• Pre-allocation shortens realized makespan: Removing pre-allocation (the "legacy variant") raises time steps from 215 to 261 on val-unseen and from 206 to 248 on test-unseen, quantifying the benefit of overlapping travel with dependency-induced waiting.
• Single-agent execution is much worse: Restricting execution to one agent drops SR to 67.1 (val-unseen) and 69.1 (test-unseen) and raises time steps to 412 and 419.
• Navigation, not just scheduling, is the bottleneck: Replacing oracle navigation with the learned navigator drops test-unseen SPL from 99.6 to 5.2. ETPNav trained on MAVLN reaches only 2.8 and 5.6 SR, though with higher CSPL and ISPL.
• LLM schedulers lag far behind oracle scheduling: With the LLM scheduler (Gemma4 / Qwen3.6), decentralized-style SR is 7.0/7.3 on val-unseen and 8.3/7.9 on test-unseen; centralized-style SR is 7.5/7.6 and 6.8/8.4; centralized-implicit SR is 5.5/6.2 and 7.1/6.8. Random and sequential dispatch of ground-truth atomic instructions score far lower (0.3 and 3.4 SR on val-unseen), showing that the ordering and allocation matter.
• Constraints are pervasive in the data: Holding chains appear in 92.9% of missions, presence locks in 28.3%, both together in 26.3%, and only 5.1% of missions reduce to a pure DAG. Episodes average five subtasks (up to eight), and over half field three or more agents.
• Retracing quantifies memory headroom: Teams spend roughly a quarter of total travel distance revisiting paths already traversed, and the proportion grows with trajectory length.
• Larger teams enable more parallelism: The optimal multi-agent makespan is shorter than the best single-agent serialization in all but several resource-constrained cases, and the gap widens with team size.
• Every system component matters (ablations, val-unseen SR): disabling shared memory 6.2 vs. 9.1 enabled; unbounded planning space 7.8 vs. 9.1 bounded; coarse-scale planner only collapses to 0.0 SR vs. 9.1 for dual-scale; step limit 20 gives 6.0 vs. 9.1 at 30; 50% teacher forcing gives 6.0 vs. 9.1; 2 concurrent agents gives 4.9 vs. 9.1 with 4; pretraining on MAVLN only gives 5.7, +REVERIE 7.3, +NavRAG 9.1.
• Not reported in the provided content: full human-evaluation results for instruction reliability (the pipeline says such an evaluation was performed), and the remainder of Section V beyond the LLM-scheduler discussion.

Methodology in Plain English

Building the benchmark. The team starts in Habitat 3 with HM3D house scenes. A vision-language model looks at panoramic renders and object labels from each viewpoint and writes descriptions, which are then merged into descriptions of larger zones in the house. Separately, an LLM invents household profiles, and for each zone picks the profile that fits best, then brainstorms a mission: a task demand plus a list of subtasks with targets and constraints. Missions that break well-formedness rules are discarded. Each subtask target is then grounded to an actual reachable viewpoint, given a short atomic instruction, and a schedule optimizer searches over legal execution orders and agent-to-subtask assignments to minimize makespan. Instructions are checked and refined by a VLM against the rendered trajectory, consolidated into three styles, and finally certified by asking an LLM to reconstruct the arrival order from the instructions and comparing that order to the ground truth, with retries and filtering for failures.

The formal task. Each subtask is visible only to the evaluator and carries a goal object, the set of agents allowed to do it, its prerequisite subtasks, and two resource flags. "Holding" means the agent carries an object and may do nothing else until the designated consumer completes. "Presence lock" means the agent must stay at the goal until a teammate completes a specific release subtask. Arrival alone does not complete a subtask; constraints gate the completion.

The system. An LLM first extracts a pool of atomic instructions from the mission text, then repeatedly dispatches them, one per agent per round, while reasoning about dependencies and locks. Agents can travel toward a destination early while waiting to "fire" a gated action, which overlaps travel with waiting. All agents write into one shared topological graph: each agent localizes its measured position to an existing node, predicts nearby waypoints from depth, and merges duplicates rather than forking the map, so one teammate's exploration becomes everyone's knowledge. A DUET-style dual-scale planner (coarse node-level plus fine neighborhood-level, fused by a learned gate) picks the next viewpoint from a bounded candidate set. For execution, a Hungarian-algorithm assignment gives each agent a distinct target, and Conflict-Based Search plans collision-free space-time routes. Two maintenance tricks prevent one agent's failure from corrupting the team map: a shared ban list for unreachable predicted viewpoints, and connecting only to the last viewpoint the agent verifiably passed through.

Training and evaluation. The planner is pretrained ETPNav-style for 200,000 steps on NavRAG data plus MAVLN training trajectories (with MAVLN unseen-split trajectories removed to prevent leakage), then trained with student-forcing imitation learning for 30,000 steps with a maximum trajectory length of 30 and four agents sharing memory, all on a single A100. Qwen3.6-27b and Gemma4-31b serve as subtask schedulers at inference, with results averaged over three runs.

Why This Matters

The paper argues that the two research threads that matter for real deployment—embodied navigation in unseen environments, and LLM-based multi-agent planning—have each matured on only half the problem: navigation work uses simplified coordination (mostly chain dependencies, no conflict measurement), while LLM planning work assumes known maps or simulator APIs. MAVLN is an attempt to put them in the same room, with measurable constraints and a conflict metric.

Real-world applications:

• Warehouse and fulfillment fleets: teams that fetch items, hand off tote/holding chains, and must not collide in shared aisles.
• Hospital and eldercare service robots: multi-step fetch-and-deliver missions where one robot must wait at a station until another completes a release step.
• Search and rescue or inspection: several robots covering an unseen building, sharing a map, and dividing targets under time pressure.
• Home robotics: household-profile-driven missions map directly onto domestic tasks like moving objects between rooms with dependencies.

Industry relevance: the benchmark provides a standardized way to evaluate multi-robot coordination stacks that combine an LLM front end with classical multi-agent path finding, and the low absolute scores (single-digit SR with LLM schedulers) make clear that shipping such systems today is premature—useful both for setting R&D priorities and for tempering claims about LLM-driven robot teams.

Future Directions

• Closing the scheduling gap. LLM schedulers reach roughly 5–8 SR while oracle scheduling reaches 9.1 with the same navigator and 100.0 with oracle navigation; better constraint reasoning during dispatch is the clearest target.
• Closing the navigation gap. SPL falls from 99.6 (oracle navigation) to 5.2 (learned navigator), and ETPNav trained on MAVLN reaches only 2.8–5.6 SR—VLN planners that handle long, multi-subtask routes in unseen scenes remain open.
• Exploiting the measured memory headroom. Roughly a quarter of travel distance is duplicated traversal, so persistent and shared memory are an explicitly quantified opportunity.
• Extending the formulation. The paper notes that arrival-to-subtask matching for systems that consume the mission instruction undecomposed is left to future work, and the formulation invites richer constraint types and team sizes beyond the four agents currently supported.

Target Audience

Researchers and graduate students in embodied AI, VLN, and multi-robot systems; engineers building LLM-plus-planner architectures for robot teams; and benchmark designers interested in automated, verifiable task generation with constraint annotations. Readers wanting a gentle introduction to VLN should start elsewhere—this paper assumes fluency in topological mapping, imitation learning, and multi-agent path finding.

Authors’ abstract

Vision-and-Language Navigation (VLN) has largely focused on a single agent following a single instruction, yet many real-world applications require teams of robots to tackle tasks beyond the capabilities of any individual agent. We present Systematic Multi-Agent Vision-and-Language Navigation, providing, to our knowledge, the first systematic formalization of multi-agent VLN as a constrained coordination problem: each mission consists of subtasks carrying dependency and resource constraints (presence locks and holding chains). A verified four-stage crafting pipeline instantiates the task as MAVLN, comprising 11,724 episodes across 145 scenes with teams of up to four agents under three instruction regimes, accompanied by tailored constraint-aware metrics. We further present TRISS, a coordination-ready navigation system coupling an LLM-based subtask scheduler, a shared topological memory that turns each agent's exploration into team knowledge, and a conflict-aware execution mechanism that realizes simultaneous intentions as collision-free routes. Extensive experiments establish TRISS as a comprehensive baseline and reveal substantial room for improvement across scheduling, planning, and execution, highlighting the challenges of coordinating under MAVLN task constraints. Project page: https://xyz9911.github.io/mavln.