NSDL: Neuro-Symbolic Division of Labor for Multi-Robot Task Planning

Xincheng Tan, Ke Wang, Yining Di, Minfeng ZhuarXiv 2026 · arXiv

TL;DR

NSDL (Neuro-Symbolic Division of Labor) is a framework that splits multi-robot task planning into two specialized parts: a vision-language model (VLM) that "reads the room" to judge the world state, and a deterministic solver that handles the mechanical heavy lifting of scheduling and constraints. By offloading structural planning to a symbolic solver, NSDL achieves near-perfect out-of-distribution accuracy, effectively eliminating the common "hallucinated" plans and physical impossibilities that plague end-to-end neural planners.

What Problem Does This Paper Address?

Planning for a team of different robots (e.g., one with two arms, one that can only push) to complete a task based on a single image and a natural language instruction is incredibly difficult.

Current approaches usually fall into two camps:

  1. End-to-End Neural Planners: These models try to go straight from pixels to a full joint plan. While they have great "common sense," they often fail at hard constraints—like trying to pick up a third object when both robot hands are already full (see Figure 1).
  2. Formalize-then-Plan: These use a model to translate the scene into a symbolic language (like PDDL) for a classical planner. The bottleneck here is the translation; if the model misses one tiny detail in the image, the entire symbolic plan fails.

The authors identify a fundamental "division of labor" problem: which parts of planning should be learned by a neural network, and which should be computed by a deterministic algorithm?

Figure 1: Common failures in existing planners. Left: Misjudging the scene (judgment error). Right: Violating physical constraints like arm capacity (structural error).

Methods

The NSDL framework introduces a collaborative workflow between a trained VLM and a symbolic solver:

  • The Plan Sketch: Instead of a full plan, the VLM (e.g., Qwen2.5-VL-7B) produces a "sketch." This includes a verdict on which goals are already met, which robot is assigned to which subtask, and the high-level order of operations.
  • The Solver ($\Phi$): A deterministic component takes this sketch and expands it into a valid, executable joint plan. It automatically inserts necessary mechanical steps (like opening a cabinet before grabbing an item), manages handoffs between robots, and ensures no robot exceeds its physical capacity.
  • Tool-Augmented Trajectory: The model operates in a multi-turn dialogue. It can call a detect tool (a YOLO-based object detector) for visual evidence and a schedule tool (the solver). If the solver rejects a sketch (e.g., due to a dependency cycle), it returns a structured error, allowing the model to revise its plan.
  • Training Recipe: The authors use Supervised Fine-Tuning (SFT) followed by Reinforcement Learning (RL) with the solver in the loop. The RL phase uses the GRPO algorithm to reward the model for producing sketches that the solver can successfully turn into valid, goal-achieving plans.
Figure 2: The NSDL overview showing the division of labor. The VLM judges the state and writes a sketch, while the solver expands it into a scheduled joint plan.

Datasets

  • VIKI-L2: A standard benchmark for multi-robot task planning.
  • LOCUS-Bench: A new, more granular benchmark introduced by the authors. It separates difficulty into two axes: State-judgment (S) (how hard it is to read the scene) and Structural-planning (M) (how complex the coordination is). This allows for a "locus of failure" analysis to see exactly where a model breaks down.

Key Insights and Ideas

  • Structural Errors are "Solvable": Once the solver takes over the structure, errors related to ordering, scheduling, and physical constraints (like arm capacity) nearly disappear. The rejection rate for plans dropped from ~23% (without the solver) to near zero.
  • The "Listing" Bottleneck: The authors discovered that most remaining failures aren't because the model "misread" a relation (e.g., thinking an apple is on the table when it isn't), but because it failed to list the goal in the first place. If a model doesn't realize an object needs moving, no amount of visual evidence helps.
  • Neuro-Symbolic Robustness: The 7B model using NSDL reached 97.0% out-of-distribution (OOD) accuracy on VIKI-L2. This suggests that the "division of labor" is key to generalization; the model learns the logic of the task while the solver handles the mechanics.

Key Results

  • Superior Performance: NSDL outperforms end-to-end planners (like VIKI-R) and formalize-then-plan baselines across the board. On VIKI-L2 OOD tasks, NSDL-RL (7B) achieved 97.0% accuracy compared to VIKI-R's 33.3%.
  • Efficiency: The framework works effectively with relatively small backbones (3B to 8B parameters), proving that you don't need a massive frontier model if you architect the system correctly.
  • LOCUS-Bench Analysis: The new benchmark revealed that while RL significantly helps the model list more goals correctly, it doesn't necessarily fix deep "judgment" errors where the model fundamentally misunderstands the scene's state.
Figure 3: Accuracy of NSDL on the LOCUS-Bench S×M grid. Darker blue indicates higher accuracy.

Limitations and Future Work

  • Enumeration Failures: The model still occasionally misses goals it should have identified. The authors suggest that future work should focus on teaching models which goals to list rather than just how to sequence them.
  • Open-Loop Planning: Currently, NSDL generates a plan from a single initial image. The authors aim to extend this to closed-loop execution, where the model can react to changes in the environment in real-time.
  • Action Model Dependency: The solver relies on a pre-defined action model (STRIPS-style). Expanding this to more complex, non-linear physical interactions remains a challenge.

Summary updated

Abstract

Planning for a heterogeneous robot team from a scene image and an instruction involves two kinds of decisions. Some must be judged from the scene: which goals are already met, how the task splits, and which robot does what. Others follow from these and can be computed: prerequisite actions, handoffs between robots, and timing. We argue that each kind should go to the component suited to it: a small vision-language model learns the first, and a deterministic solver computes the second. In NSDL (Neuro-Symbolic Division of Labor), the trained model writes its judgments as a plan sketch, which lists the goals that still need action and the intended steps in order, each with a robot. The solver expands the sketch into an executable joint plan. The model calls two tools, a detector for evidence and the solver, and is trained with the solver in the loop. We evaluate on the public VIKI-L2 benchmark and on LOCUS-Bench, a new benchmark that grades the two kinds of difficulty separately. NSDL outperforms end-to-end planners and formalize-then-plan baselines on both benchmarks and with three backbones from 3B to 8B; the 7B model reaches 97.0% out-of-distribution accuracy on VIKI-L2. Ordering and scheduling errors nearly disappear once the solver writes the structure; the remaining failures are misjudged states, and most goals the model misses are ones it never lists. Code, model weights, and LOCUS-Bench are publicly available at https://github.com/Xincheng-Tan/NSDL.
BibTeX
@misc{tan2026nsdl,
  author = {Xincheng Tan and Ke Wang and Yining Di and Minfeng Zhu},
  title = {{NSDL: Neuro-Symbolic Division of Labor for Multi-Robot Task Planning}},
  year = {2026},
  eprint = {2611.16671},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.16671},
}
Figure