- Rating
- 2(+1)
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
The paper introduces ReCoNav, a framework for long-horizon vision-and-language navigation with ordered visits, hard constraints, and preferences. Given a fully-observed scene graph, it translates natural-language instructions into a formal instruction contract. Its Determination Engine combines symbolic rules and route-feasibility queries to resolve target ambiguities, verify interpretations, and guide VLM-based repairs. A constraint-aware solver then generates routes satisfying the resulting specification. Evaluation on 192 tasks across nine indoor scenes, using ground-truth scene graphs, shows improved instruction satisfaction over the evaluated baselines. The main contribution is coordinating instruction interpretation, target grounding, and route planning through shared constraints and verification.
Critical strengths
The authors study an interesting problem. Supporting human preferences and constraints is important for deploying robots in the real world.
Critical weaknesses
-
The paper is hard to follow despite careful reading. VLN is a broad problem, and it is unclear which subproblem the paper aims to address. Is the main contribution (1) enabling VLN to satisfy additional constraints and preferences, or (2) providing a formal way to verify the translation from natural language to formal specifications? If (1), handling additional natural-language constraints and preferences is not novel in itself, and the distinction from prior work needs clarification. If (2), the paper does not clearly establish the verification foundation: what are the minimal trusted assumptions, and are the checking rules predefined or generated by the VLM? Checking a solution against a VLM-generated specification does not, by itself, verify that the specification correctly captures the original instruction. VLM judgments alone do not constitute formal verification.
-
The writing needs improvement. For example, the abstract and introduction state that the Determination Engine uses “scene and task rules,” but it is initially unclear whether these rules are predefined by human experts, generated online by a foundation model, or derived from the instruction’s hard constraints and preferences. Their relationship to these constraints and preferences should be explained more clearly. The connection between the stated insight "that uncertainty in individual judgments does not preclude deterministic relations between them (line 89)" and the subsequent description of local rules is also insufficiently explained. A concrete example early in the paper would help clarify the reasoning mechanism and its contribution.
-
The problem definition does not clearly distinguish between planning over a discrete navigation graph and motion through continuous space. Line 136 defines a collision-free waypoint route, (pi=(s_0,q_1,...,q_n)), but how are the connecting motions constructed, and what assumptions are made about the robot’s ability to follow them? Also, whether eq(4) minimizes the cost of the waypoint only or the entire trajectory is not clear.
-
The paper should state its assumptions more clearly and earlier. In particular, the task definition should explicitly state that a scene representation obtained through pre-exploration is available before planning. The use of fixed, ground-truth scene graphs in the benchmark should also be highlighted early, as it substantially affects the scope of the problem.
-
Given the global scene graph and deterministic transitions, the planning component becomes classical symbolic planning or task and motion planning (TAMP). The problem lies in translating natural language into a formal specification, rather than solving the symbolic planning problem itself. After the problem is converted to a formal specification, it is unclear why a classical SAT/SMT-based planner or TAMP solver cannot solve the problem. Prior work, including LLM+P [1] and CaStL [2], already combines language models with formal planning. The paper should clarify this distinction.
-
Handling additional constraints or preferences expressed in natural language is not, by itself, novel. For example, CaStL [2] uses an LLM to translate constraints into PDDL and Python scripts that add constraints to a downstream SMT-based task and a motion planner. The related work discussion should include these approaches and explain the additional contributions of the proposed scoped constraints, preference handling, and determination mechanism.
[1] Liu et al. LLM+P: Empowering Large Language Models with Optimal Planning Proficiency. 2023. [2] Guo et al. CaStL: Constraints as Specifications through LLM Translation for Long-Horizon Task and Motion Planning. ICRA 2025.
Questions for authors
-
Lines 138–139: Could the authors explain (D(v)) more concretely?
-
Could the authors state more precisely what is new relative to prior work on translating natural-language constraints into formal specifications for symbolic planning?
13 comments
Response to W1
W1. Research scope
-
Research problem and contributions. The Overall Response clarifies our research problem and three contributions. Here, route constraints refer to visits, their order, scoped avoidance and counts, and preferences, as defined in Section 3.1 (lines 137–138). Spatial constraints such as IN and NEAR restrict candidate domains and are well studied in prior navigation work. Our focus is the remaining gap: propagating route constraints across navigation stages so that they govern both target choices and complete routes.
We respectfully disagree with the assessment that the paper is hard to follow and does not clearly define its research problem and contributions. The submitted paper explicitly describes both, together with the distinction from spatial grounding:
Limitations and challenge (Section 1, Limitations of existing approaches, lines 83–85): Identifies the limitations of existing approaches in propagating scoped requirements across navigation stages and states the resulting challenge.
Contributions (Section 1, final paragraph): States the three contributions: the instruction contract, ReCoNav, and the benchmark.
Relationship to spatial grounding (Section 2, Spatial and constraint-aware navigation, lines 120–122): Distinguishes semantic and spatial matching from route-constraint reasoning.
-
Verification and trusted assumptions. Verification is one component of ReCoNav, one of our three contributions alongside the benchmark and instruction contract. ReCoNav is designed to improve VLN reliability through formal reasoning. As stated in Section 1 (lines 88–89), “uncertainty in individual judgments does not preclude deterministic relations between them.” VLM judgments may be uncertain, but we trust the predefined relations imposed by scene and task definitions. This is not only our insight but also our minimal trusted assumption. ReCoNav implements these relations through predefined rules and solver queries to derive judgments, verify their consequences, and provide evidence for repair.
For example, task semantics define the following rule for visit events :
In Figure 3,
BEFORE(v,v)is a judgment proposed by the VLM. Applying the predefined rule yields , exposing a contradiction. The conflict does not establish whether the BEFORE relation or its event references were misinterpreted. The engine provides the violated rule, implicated judgments, and source phrase as evidence for the VLM to revise the interpretation.Rules also support derivation. The rule excludes a candidate binding when it admits no hard-feasible route. In Figure 3, route queries establish this premise for the bindings to R9 and R10. Excluding them leaves R4 as the unique feasible bedroom target.
We will make these connections and the verification assumptions more explicit in the revised Introduction.
Response to W2
W2. Scene/task rules and the reliability insight
-
Rules versus VLM judgments. Our insight is that “uncertainty in individual judgments does not preclude deterministic relations between them” (Section 1, lines 88–89). W1 explains this insight and the scene/task rules with examples. Rules are not the judgments extracted by the VLM. They encode the relations those judgments must satisfy according to scene and task definitions. These rules are predefined in the implementation.
Figure 3(a) explicitly displays the checking relation separately from
BEFORE(v,v). The former is a task-defined rule, and the latter is the VLM judgment being checked. -
Core rules. We will further clarify the distinction between rules and judgments and add a complete table of the core rules to the revised paper.
Rule group Rules Instruction contract consistency for fields with a blacklist Scene grounding and contract consistency for a required event Global binding determination Complete-route verification for required visits for the final visit for applicable hard orders for hard AVOID for hard COUNT New notation:
- is a retained source phrase, and are lexical boundaries in . contains the declared events matching event reference . is the source phrase cited for field , and is its conservative blacklist.
- tests whether ASG entity satisfies the target type, label, and spatial qualifiers specified for event in the contract. means that events and explicitly refer to the same target entity.
- denotes adopting binding .
- For soft clause , is its violation cost. equals one when its condition holds and zero otherwise.
The anonymous repository provides the implementations and repair procedure.
Overall Response to Reviewer 4z11
Thank you for recognizing the importance of constrained navigation and for suggesting CaStL [1] and LLM+P [2]. We appreciate prior advances in formal planning. Our work builds on this foundation and investigates how formal reasoning can be used more extensively to improve the reliability of long-horizon VLN.
Overall Response
Research problem. We study constrained long-horizon VLN, where ordered visits, scoped AVOID and distinct-entity COUNT constraints, and preferences must govern decisions throughout navigation. The central challenge is to propagate these requirements across instruction interpretation, grounding, and complete-route planning. Figure 1 illustrates an important consequence: even after semantic and spatial matching identifies candidate targets, route constraints and preferences may determine which target should be selected.
Benchmark. Conventional VLN focuses on route following. We first construct a scene-grounded benchmark to evaluate these requirements and their role in target selection. Existing methods achieve low full-instruction satisfaction, including those given global scene information. These results show that scene access and formal planning alone do not ensure full-instruction satisfaction.
Technical approach. Observation/history-based VLN may lack information about distant targets and connecting routes, motivating maps, memory, and pre-exploration. Map-informed VLM planning, as in MapGPT and NavGPT+ASG, is one possible approach. These findings motivate ReCoNav’s use of formal scene and route evidence throughout the decision process. Rules and solver queries provide explicit feasibility, infeasibility, and preference evidence for interpretation, grounding, and final planning.
Our contributions address this problem at three levels:
The anonymous repository provides implementations, rules, and prompts. The project page provides task examples and real-robot demonstrations.
[1] Guo, Kingston, and Kavraki. CaStL: Constraints as Specifications through LLM Translation for Long-Horizon Task and Motion Planning. ICRA 2025.
[2] Liu et al. LLM+P: Empowering Large Language Models with Optimal Planning Proficiency. 2023.