$S^3$-Nav: Structured Spatial-Semantic Decision Making for Language-Guided Robot Navigation

Chaemin Lee; Hae Min Cho

cs.ROOct 14, 2026

$S^3$ -Nav: Structured Spatial-Semantic Decision Making for Language-Guided Robot Navigation

Authors: Chaemin Lee, Hae Min Cho

Organizations: Department of AI, Gachon University, Seongnam 13120, Republic of Korea

Abstract

This paper presents $S^3$ -Nav, a structured spatial-semantic decision-making framework for language-guided robot navigation under partial observability. Rather than assuming a complete environment representation in advance, $S^3$ -Nav incrementally constructs persistent spatial-semantic state while exposing only a capacity-controlled, task-conditioned view to the high-level policy. This separation decouples what the robot must retain from what the policy needs to inspect, allowing decision complexity to be controlled without discarding grounded evidence required for subsequent reasoning and validation. High-level navigation outputs remain provisional and are independently grounded and validated against persistent semantic evidence and current geometric observations before physical execution or task termination. Evaluations across multiple environments and object- and relation-goal tasks demonstrate that separating persistent state, decision-facing evidence, and execution authority improves closed-loop navigation reliability while reducing policy reasoning cost.

Figures & tables

Fig. 1: Qualitative navigation example for the relational instruction “Find a chair next to a plant.” The robot first explores while no goal-matched object is available, then switches to approach after detecting goal-compatible relational evidence, and finally terminates after the execution layer verifies the terminal conditions.

Fig. 2: Overview of the S 3 -Nav structured decision architecture. Perception, localization, and mapping update a persistent spatial-semantic state, from which a goal-conditioned decision-facing evidence view is constructed. A high-level decision policy produces provisional navigation intents, while the deterministic validation and execution layer $\Gamma$ resolves grounded references and retains authority over physical execution and terminal acceptance.

Symbol	Description
$S_{t}$	Persistent spatial-semantic decision state at decision step $t$ .
$g_{s}$	Parsed goal schema.
$\mathcal{O}_{t}$	Persistent object entries.
$\mathcal{R}_{t}$	Confirmed-relation entries.
$\mathcal{F}_{t}$	Retained frontier set.
$P_{t}$	Current robot pose.

TABLE I: Notation used in the persistent-state formulation.

Scenario	Goal	Initial	Distractor
S1	Relation: next_to	Seen	No
S2	Relation: next_to	Unseen	No
S3	Relation: on	Seen	No
S4	object-goal	Unseen	No
S5	relation-goal	Unseen	Yes

TABLE II: Navigation scenarios used in the evaluation.

Fig. 3: Record-capacity sensitivity of Qwen under Estimated localization on selected relation-goal tasks from HSSD and InternScenes. Each capacity is evaluated over five matched episodes per suite, and GT-SSR uses the complete five-episode set.

Policy	Record Capacity	SSR $\uparrow$	SR@3m $\uparrow$	GT-SSR $\uparrow$	$N_{\mathrm{GT\text{-}valid}}$	RSR $\uparrow$	TL (m) $\downarrow$	Duration (s) $\downarrow$
Heuristic	Full	0.680	0.680	0.680	21	0.800	5.234 $\pm$ 3.313	130.76 $\pm$ 210.42
Heuristic	K14	0.840	0.840	0.800	23	0.947	5.629 $\pm$ 3.144	87.02 $\pm$ 156.28
Qwen	Full	0.680	0.680	0.600	19	0.900	5.573 $\pm$ 2.975	136.00 $\pm$ 208.98
Qwen	K14	0.960	0.960	0.960	24	0.950	5.298 $\pm$ 3.155	41.94 $\pm$ 22.07

TABLE III: Overall comparison of Qwen and heuristic high-level policies under Estimated localization across the HSSD scenarios. SSR, SR@3m, and GT-SSR are evaluated over the complete episode set, while RSR is reported over relation-goal episodes. Bold indicates the best observed performance value.

Policy	Record Capacity	SSR $\uparrow$	SR@3m $\uparrow$	GT-SSR $\uparrow$	$N_{\mathrm{GT\text{-}valid}}$	RSR $\uparrow$	TL (m) $\downarrow$	Duration (s) $\downarrow$
Heuristic	Full	0.867	0.867	0.800	13	0.800	8.421 $\pm$ 7.509	125.06 $\pm$ 196.43
Heuristic	K14	0.933	0.933	0.867	13	0.900	7.036 $\pm$ 5.528	90.38 $\pm$ 145.40
Qwen	Full	0.800	0.800	0.800	12	1.000	6.630 $\pm$ 4.290	162.58 $\pm$ 229.29
Qwen	K14	1.000	1.000	1.000	15	1.000	6.477 $\pm$ 4.012	57.04 $\pm$ 35.45

TABLE IV: Comparison of Qwen and heuristic high-level policies on InternScenes under Estimated localization. The evaluation includes object- and relation-goal navigation, with GT-SSR reported over the complete episode set and RSR over relation-goal episodes. Bold indicates the best observed performance value.

Scenario	Full	K14	Full	K14	Full	K14
	Heuristic GT-SSR		Qwen GT-SSR		Qwen Tokens/Call
S1	1.000	1.000	1.000	1.000	2,771	2,370
S2	1.000	1.000	0.600	1.000	2,423	2,374
S3	0.400	0.800	0.800	0.800	3,358	2,298
S4	0.800	0.800	0.400	1.000	2,514	2,318
S5	0.200	0.400	0.200	1.000	3,188	2,410

TABLE V: Scenario-level comparison of Full and K14 decision-facing record views under Estimated localization over five runs per HSSD scenario. The table reports GT-SSR for both policies and combined prompt-and-completion Tokens/Call for Qwen.

Suite	Localization	SSR $\uparrow$	GT-SSR $\uparrow$	RSR $\uparrow$	RPE Trans. (m) $\downarrow$	RPE Rot. (rad) $\downarrow$	TL (m) $\downarrow$
HSSD	Estimated	0.960	0.960	0.950	0.1527 $\pm$ 0.1638	0.0726 $\pm$ 0.0828	5.298 $\pm$ 3.155
HSSD	GT Odometry	0.880	0.840	0.950	0.0034 $\pm$ 0.0011	0.0030 $\pm$ 0.0011	5.538 $\pm$ 2.940
InternScenes	Estimated	1.000	1.000	1.000	0.1178 $\pm$ 0.1365	0.0582 $\pm$ 0.0568	6.477 $\pm$ 4.012
InternScenes	GT Odometry	1.000	1.000	1.000	0.0251 $\pm$ 0.0561	0.0121 $\pm$ 0.0320	6.359 $\pm$ 3.638

TABLE VI: Localization comparison for Qwen K14 across HSSD and InternScenes using five repeated runs per task or scenario. The policy, record-capacity condition, and downstream navigation stack are fixed while the pose source is changed.

Fig. 4: Representative closed-loop navigation trace with online map construction for the relational instruction “Find a chair next to a plant.” Starting without a pre-existing map, S 3 -Nav incrementally expands the occupancy representation while accumulating spatial-semantic evidence during exploration. The robot subsequently identifies goal-compatible relational evidence, approaches the selected target, and terminates after execution-layer validation. The final map shows the occupancy representation and trajectory accumulated during the episode.

Condition	SSR $\uparrow$	GT-SSR $\uparrow$	$N_{\mathrm{GT\text{-}valid}}$	RSR $\uparrow$	TL (m) $\downarrow$	Duration (s) $\downarrow$
Complete (Qwen K14, Est.)	1.000 $\pm$ 0.000	1.000 $\pm$ 0.000	5	1.000 $\pm$ 0.000	10.688 $\pm$ 0.047	75.40 $\pm$ 1.88
w/o Persistent Memory	0.000 $\pm$ 0.000	0.000 $\pm$ 0.000	0	0.250 $\pm$ 0.500	19.263 $\pm$ 6.615	600.00 $\pm$ 0.00
w/o Explicit Frontier Cues	0.800 $\pm$ 0.447	0.800 $\pm$ 0.447	4	1.000 $\pm$ 0.000	8.790 $\pm$ 2.794	177.70 $\pm$ 236.09

TABLE VII: Component ablation of persistent memory and explicit frontier cues on the HSSD Living Relation Unseen scenario under Qwen K14 with Estimated localization. The ablations retain the common navigation and terminal-validation stack while selectively removing cross-step memory or frontier records. Values are mean

\pm

sample standard deviation where applicable.

Condition	Policy Lat. (ms) $\downarrow$	E2E Decision Lat. (ms) $\downarrow$	Qwen Calls/ Ep. $\downarrow$	Tokens/Ep. ( $\times 10^{3}$ ) $\downarrow$	RTF $\uparrow$
Heuristic Full (Est.)	$\mathbf{0.02\pm 0.01}$	$\mathbf{30.9\pm 21.8}$	–	–	$0.340\pm 0.041$
Heuristic K14 (Est.)	$0.20\pm 0.03$	$33.0\pm 22.5$	–	–	$\mathbf{0.345\pm 0.041}$
Qwen Full (Est.)	$1535.3\pm 130.0$	$1567.4\pm 138.3$	$29.7\pm 15.4$	$86.3\pm 47.2$	$\mathbf{0.243\pm 0.021}$
Qwen K14 (Est.)	$\mathbf{1486.8\pm 118.2}$	$\mathbf{1525.4\pm 133.4}$	$\mathbf{28.5\pm 17.4}$	$\mathbf{67.3\pm 42.0}$	$0.237\pm 0.021$
Qwen K14 (GT Odometry)	$1475.3\pm 110.2$	$1594.3\pm 139.4$	$31.7\pm 19.2$	$74.5\pm 47.2$	$0.235\pm 0.018$

TABLE VIII: Runtime comparison across policy, record-capacity, and localization conditions on HSSD. The table reports policy latency, end-to-end decision latency, navigation-policy reasoning cost, and real-time factor. Values are mean

\pm

sample standard deviation over the available run-level measurements, and bold indicates the best observed value within each policy family under Estimated localization.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Parameter	Function	Value
$\tau_{\mathrm{goal}}$	goal-matched next_to distance	$1.80\,\mathrm{m}$
$\tau_{\mathrm{strict}}$	strict next_to distance	$0.75\,\mathrm{m}$
$\tau_{z}^{\mathrm{strict}}$	strict height difference	$0.55\,\mathrm{m}$
$\tau_{z}^{\mathrm{goal}}$	goal-matched height difference	$0.85\,\mathrm{m}$
$\tau_{\mathrm{on}}$	on horizontal distance	$0.65\,\mathrm{m}$
$\tau_{z}^{\min},\tau_{z}^{\max}$	on height interval	$0.04,\,1.25\,\mathrm{m}$

Appendix

TABLE S1: Spatial-memory and geometric-relation thresholds.

Fig. S1: Example of the structured policy interface used by S 3 -Nav. The persistent spatial-semantic state contains the parsed goal schema, object and confirmed-relation memory, frontier cues, robot pose, and compact partial-map and navigation summary. The context-construction procedure selects records in the decision-facing view under the active capacity condition and serializes them for Qwen. The resulting high-level output remains provisional and is passed to the deterministic execution layer for grounded target resolution, action validation, and physical execution.

Parameter	Configured value
K14 ranked-record capacity	14 structured records
Qwen maximum model length	6,000 tokens
Serialized numeric precision	3 decimal places
Missing serialized measurement	null
High-priority goal entries considered	up to 2
Task-relevant semantic records considered	up to 10

Appendix

TABLE S2: Structured-context and Qwen-interface parameters.

Parameter	Configured value
Heuristic raw-stop distance	$0.5\,\mathrm{m}$
Heuristic raw-stop bearing	$35^{\circ}$
Desired standoff $d^{\star}$	$0.7\,\mathrm{m}$
Standoff margin $\epsilon$	$0.2\,\mathrm{m}$
Lower standoff bound	$0.5\,\mathrm{m}$
Upper standoff bound	$0.9\,\mathrm{m}$

Appendix

TABLE S3: Heuristic and common standoff-control parameters.

Gate	Trigger	Response
Invalid depth	$d_{t}^{\mathrm{ctr,min}}\leq 0\lor\text{valid fraction}<0.05$	Hold
Hard	$d_{t}^{\mathrm{ctr,min}}<0.42\lor d_{t}^{\mathrm{ctr},10}<0.55$ $\lor\;r_{t}^{0.80}>0.26$	Reverse/turn
Near	$d_{t}^{\mathrm{ctr},10}<0.85\lor r_{t}^{0.80}>0.12$	Cap/steer
Slow	$d_{t}^{\mathrm{ctr},10}<1.25\lor r_{t}^{0.80}>0.05$	Reduce speed

Appendix

TABLE S4: Forward-motion depth-safety gates.

Parameter	Configured value
Confirmed-relation stale limit	80 updates
Slip samples before recovery	8
Recovery cooldown	$2.5\,\mathrm{s}$
Fixed recovery-count limit	No fixed limit

Appendix

TABLE S5: Repository-maintenance and recovery parameters.

Condition	Calls/ Ep. $\downarrow$	Tokens/Ep. ( $\times 10^{3}$ ) $\downarrow$	Policy Lat. (ms) $\downarrow$
Qwen Full (Est.)	$29.7\pm 15.4$	$86.3\pm 47.2$	$1535.3\pm 130.0$
Qwen K14 (Est.)	$28.5\pm 17.4$	$67.3\pm 42.0$	$1486.8\pm 118.2$
Qwen K14 (GT Odometry)	$31.7\pm 19.2$	$74.5\pm 47.2$	$1475.3\pm 110.2$

Appendix

TABLE S6: Qwen-specific navigation-policy reasoning cost on HSSD over 25 episodes per condition. Qwen Calls/Ep. and Tokens/Ep. exclude the cached goal-schema parsing request, and Tokens/Ep. combines prompt and completion tokens. Values are mean

\pm

sample standard deviation across runs.

Task	Condition	SSR $\uparrow$	SR@3m $\uparrow$	GT-SSR $\uparrow$	$N_{\mathrm{GT\text{-}valid}}$	RSR $\uparrow$	SNE (m) $\downarrow$	GT-SNE (m) $\downarrow$	TL (m) $\downarrow$	Duration (s) $\downarrow$
I1	Heuristic Full	1.000	1.000	0.800	5	–	0.1524 $\pm$ 0.0366	0.0372 $\pm$ 0.0210	3.7589 $\pm$ 0.1641	33.20 $\pm$ 0.76
	Heuristic K14	1.000	1.000	1.000	5	–	0.1632 $\pm$ 0.0328	0.0376 $\pm$ 0.0079	3.7003 $\pm$ 0.0588	33.40 $\pm$ 1.08
	Qwen Full	1.000	1.000	1.000	5	–	0.1724 $\pm$ 0.0075	0.0332 $\pm$ 0.0106	3.8562 $\pm$ 0.3213	38.50 $\pm$ 4.78
	Qwen K14	1.000	1.000	1.000	5	–	0.1801 $\pm$ 0.0141	0.0485 $\pm$ 0.0161	3.6541 $\pm$ 0.0194	34.00 $\pm$ 0.79
	Qwen K14 (GT Odometry)	1.000	1.000	1.000	5	–	0.1779 $\pm$ 0.0075	0.0341 $\pm$ 0.0095	3.7437 $\pm$ 0.0797	36.70 $\pm$ 1.82
I2	Heuristic Full	1.000	1.000	1.000	5	1.000	0.1980 $\pm$ 0.0014	0.1498 $\pm$ 0.0023	4.0274 $\pm$ 0.0352	32.70 $\pm$ 0.91

Appendix

TABLE S7: Task-level navigation results on InternScenes over five runs per condition. I1 is the initially seen object-goal task, I2 is the initially seen relation-goal task, and I3 is the initially unseen relation-goal task.

N_{\mathrm{GT\text{-}valid}}

reports valid GT terminal-geometry support, RSR is not applicable to I1, and SNE metrics are reported only when their required terminal geometry is available.

Task	Condition	RPE Trans. (m) $\downarrow$	RPE Rot. (rad) $\downarrow$	Surface-Range MAE (m) $\downarrow$	Surface-Range RMSE (m) $\downarrow$	$N_{\mathrm{surface}}$
I1	Heuristic Full	0.0644 $\pm$ 0.0180	0.0316 $\pm$ 0.0070	0.1258 $\pm$ 0.0033	0.1270 $\pm$ 0.0028	173
	Heuristic K14	0.0525 $\pm$ 0.0087	0.0368 $\pm$ 0.0078	0.1288 $\pm$ 0.0026	0.1297 $\pm$ 0.0027	172
	Qwen Full	0.0429 $\pm$ 0.0036	0.0284 $\pm$ 0.0057	0.1305 $\pm$ 0.0043	0.1313 $\pm$ 0.0043	169
	Qwen K14	0.0670 $\pm$ 0.0255	0.0305 $\pm$ 0.0057	0.1267 $\pm$ 0.0021	0.1276 $\pm$ 0.0020	171
	Qwen K14 (GT Odometry)	0.0030 $\pm$ 0.0006	0.0036 $\pm$ 0.0006	0.1333 $\pm$ 0.0085	0.1342 $\pm$ 0.0080	174
I2	Heuristic Full	0.0570 $\pm$ 0.0200	0.0304 $\pm$ 0.0073	0.0666 $\pm$ 0.0021	0.0676 $\pm$ 0.0023	205

Appendix

TABLE S8: InternScenes localization and surface-range diagnostics over five runs per condition. Surface-range errors are computed from the available target-associated observations along each executed trajectory, and

N_{\mathrm{surface}}

reports the corresponding support count. Because observation sets differ across conditions, the surface-range errors are treated as geometric diagnostics rather than paired measurements.

Task	Condition	Calls/Ep. $\downarrow$	Tokens/Ep. ( $\times 10^{3}$ ) $\downarrow$	Policy Lat. (ms) $\downarrow$	E2E Decision Lat. (ms) $\downarrow$	RTF $\uparrow$
I1	Heuristic Full	–	–	0.015 $\pm$ 0.001	26.54 $\pm$ 1.73	0.355 $\pm$ 0.050
	Heuristic K14	–	–	0.191 $\pm$ 0.004	27.69 $\pm$ 0.60	0.356 $\pm$ 0.049
	Qwen Full	29.0 $\pm$ 5.2	77.131 $\pm$ 16.736	1401.74 $\pm$ 22.85	1448.94 $\pm$ 39.55	0.238 $\pm$ 0.022
	Qwen K14	25.4 $\pm$ 1.5	55.680 $\pm$ 2.761	1371.25 $\pm$ 11.92	1394.58 $\pm$ 12.89	0.229 $\pm$ 0.003
	Qwen K14 (GT Odometry)	29.2 $\pm$ 1.5	62.191 $\pm$ 2.494	1373.33 $\pm$ 13.38	1474.74 $\pm$ 10.12	0.254 $\pm$ 0.026
I2	Heuristic Full	–	–	0.018 $\pm$ 0.002	29.07 $\pm$ 1.46	0.354 $\pm$ 0.048

Appendix

TABLE S9: InternScenes reasoning-cost and runtime results over five runs per condition. Qwen Calls/Ep. and Tokens/Ep. refer to navigation-policy Qwen requests, with Tokens/Ep. combining prompt and completion tokens. Policy Latency measures the high-level policy routine, and E2E Decision Latency measures the observe-to-command interval on policy-invoked decision events. Values are mean

\pm

sample standard deviation across runs.

Robot Navigation

Robot navigation studies how robots perceive, localize, plan, and move safely toward goals in static or changing environments.

See all 549 papers

SAP-Nav: Spatial Semantic Representation Meets Active Perception for Hierarchical Open-Vocabulary Object Navigation
Aug 13, 2026Xuetong Pei, Jian Liu, Vidura Munasinghe +4Active Perception Embodied Navigation
1Beihang University · 2Singapore University of Technology and Design · 3AIML, Adelaide University
Spatial and Semantic Reasoning for LLM-Driven Robot Navigation via MCP
Sep 23, 2026Jungsoo Lee, Jaegyun Park, Wansoo KimRobot Navigation Large Language Model-Based Robot Planning
Department of Robotics, Hanyang University, Seoul, 04763, Korea · Department of Robotics, Hanyang University ERICA, Ansan, 15588, Korea
DM $^3$ -Nav: Decentralized Multi-Agent Multimodal Multi-Object Semantic Navigation
Apr 23, 2026Amin Kashiri, Atharva Jamsandekar, Yasin YazıcıoğluVision-Language Navigation Multi-Robot Coordination
Northeastern University, Boston, USA · Department of Electrical and Computer Engineering at Northeastern University, Boston, MA

Aug 13, 2026J/K move · Enter open · S save

SAP-Nav: Spatial Semantic Representation Meets Active Perception for Hierarchical Open-Vocabulary Object Navigation

Xuetong Pei, Jian Liu, Vidura Munasinghe, Bo Miao+3

1Beihang University · 2Singapore University of Technology and Design · 3AIML, Adelaide University

Active Perception Embodied Navigation Open-Vocabulary Object Navigation Vision-Language Navigation Semantic Mapping

Open paper AskPDF arXiv

Hierarchical open-vocabulary object navigation (OVON) requires agents to follow free-form instructions that may specify targets through scene-, room-, region-, and instance-level cues in unseen environments. Although recent work LangMap has formalized this setting, reliably solving it under partial observations remains challenging: spatial grounding requires persistent environment-level evidence, whereas target verification requires clear and discriminative candidate views. We present SAP-Nav, a fully online, zero-shot framework that addresses both requirements through active perception. SAP-Nav incrementally constructs a Queryable Spatial-Semantic Representation from actively acquired room views, enabling spatial semantic queries from any explored location. It further employs Active Viewpoint Verification to assess whether the current observation provides sufficient evidence and, when necessary, reposition the agent to a more informative viewpoint before verifying candidates against category and attribute constraints. Although designed for hierarchical OVON, SAP-Nav supports both hierarchical and standard category-level OVON without task-specific training or precomputed scene maps. Experiments on LangMap and HM3D-OVON show that SAP-Nav achieves the overall best performance, including a 12.2% improvement in SR over training-based methods on region-level navigation. Real-world robot experiments further demonstrate its practical feasibility. Code will be made publicly available upon acceptance.

Abstract

Robot Navigation

Explore similar work

SAP-Nav: Spatial Semantic Representation Meets Active Perception for Hierarchical Open-Vocabulary Object Navigation

Spatial and Semantic Reasoning for LLM-Driven Robot Navigation via MCP

DM3^33-Nav: Decentralized Multi-Agent Multimodal Multi-Object Semantic Navigation

DM $^3$ -Nav: Decentralized Multi-Agent Multimodal Multi-Object Semantic Navigation