Beyond the Remembered World: Predictive 4D Belief for Persistent Navigation in Evolving Worlds

Mingjian Gao; Zhaocheng Li; Haoyang Huang; Wenqiao Zhang; Yingjie Niu; Hao Zhou; Chao Li; Juncheng Li

cs.AISep 30, 2026

Beyond the Remembered World: Predictive 4D Belief for Persistent Navigation in Evolving Worlds

Authors: Mingjian Gao, Zhaocheng Li, Haoyang Huang, Wenqiao Zhang, Yingjie Niu, Hao Zhou, Chao Li, Juncheng Li, +2 more

Organizations: Zhejiang University · University of California, San Diego · Deeprobotics · Chinese University of Hong Kong

Abstract

Persistent spatial memory enables embodied agents to navigate familiar environments across repeated visits. However, targets may move while unobserved, including during navigation, making remembered locations unreliable by the time an agent arrives. Despite advances in memory retrieval and state prediction, accounting for continued hidden world evolution and revising beliefs under limited visibility remain challenging. We study Evolving-World Navigation, where agents infer target locations from intermittent observations, predict their states at inspection time, and revise beliefs using visual evidence. We propose EvolvingNav, which constructs a time-indexed belief from timestamped 3D object histories through a structured persistence-relocation model. The belief distinguishes persistence at the last observed location from relocation to alternative locations and retains probability mass outside the known candidate set. An event-driven filter propagates the current belief as time elapses, forecasts target occupancy at candidate inspection times, and incorporates new RGB-D evidence. Negative observations downweight location hypotheses according to calibrated, visibility-conditioned detection probabilities, while evidence tracking prevents repeated use of the same observations. A frozen, zero-shot vision-language controller uses the updated belief to choose actions and replan. We further introduce EvoWorld-Bench, a benchmark grounded in human activity traces, comprising 54 scenes and 803,680 tasks with controlled changes before and during navigation. In simulation and real-robot experiments, EvolvingNav improves navigation success and search efficiency over the evaluated baselines. Paired experiments show the clearest gains under learnable temporal patterns, while ablations demonstrate the value of preserving uncertainty and incorporating visibility-aware evidence.

Figures & tables

Figure 1: Overview of EvolvingNav for predictive embodied reasoning and action in evolving worlds.

Figure 2: EvolvingNav couples persistent 4D memory, predictive belief, and an embodied agent that updates and replans from stepwise evidence.

Figure 3: Overview of EvoWorld-Bench evaluation protocols.

Figure 4: Construction of EvoWorld-Bench .

	FindingDory		GOAT-Bench			EvoWorld-Bench
Method	HL-SR $\uparrow$	HL-SPL $\uparrow$	SR $\uparrow$	SPL $\uparrow$	Repeat-SR $\uparrow$	First-Inspection SR $\uparrow$	Search SR $\uparrow$	SPL $\uparrow$
Open-vocabulary and lifelong navigation
VLFM ( Yokoyama et al., 2024 )	13.42	10.86	15.79	5.45	11.82	20.65	28.36	24.67
ZSON ( Majumdar et al., 2022 )	27.89	21.81	29.64	2.45	16.37	26.84	32.13	28.55
FindingDory Agent ( Yadav et al., 2025 )	52.44 PR	40.92	New A	New A	New A	New A	New A	New A
LagMemo GLUE ( Zhou et al., 2025 )	32.79	23.25	20.61	1.74	11.27	30.18	42.27	33.82

Table 1: Cross-benchmark comparison (%).

\pm

denotes standard deviation over five seeds.

Figure 5: Predictive, last-seen, and nearest-first search on EvoWorld-Bench .

Method	Dynamic SR $\uparrow$	Online Recovery SR $\uparrow$	Excess Distance (m) $\downarrow$	Revisit Success $\uparrow$
SLaTe-PRO ( Patel et al., 2023 )	34.7	21.5	18.9	8.7
SGM+NEP ( Kurenkov et al., 2023 )	41.3	27.8	15.6	12.4
FlowMaps ( Argenziano et al., 2026 )	29.6	18.9	22.4	6.5
PredictiveGraphs ( Saavedra-Ruiz et al., 2026 )	46.8	36.7	13.2	18.9
EvolvingNav (ours)	65.2	58.7	8.4	32.6

Table 2: N4 online-dynamic navigation with execution-time target motion.

Method	First-Inspection SR $\uparrow$	Search SR $\uparrow$	Recovery SR $\uparrow$	Dist. (m) $\downarrow$	Time (s) $\downarrow$	Inspect. $\downarrow$
Last Seen + Search	17.2	26.6	12.8	56.2	284	2.19
Time Frequency	21.9	31.3	14.0	52.9	277	2.05
Retrieval + Reasoning	26.6	37.5	17.1	50.3	281	2.03
EvolvingNav	34.4	48.4	24.3	43.8	248	1.84

Table 3: Primary LYNX M20 search results.

Figure 6: Core component ablation; error bars show five-seed standard deviations.

Update rule	Rank $\downarrow$	Top-1 $\uparrow$	NLL $\downarrow$	ECE $\downarrow$
No Update	5.82	62.98	2.838	0.172
Hard Removal	10.09	42.69	11.514	0.204
Bayesian Update	5.25	64.71	1.497	0.151
Bayesian + Calibration	4.96	66.93	1.530	0.130

Table 4: Negative-evidence update ablation.

	Temporal			LOSO
Predictor	Top-1 $\uparrow$	MRR $\uparrow$	NLL $\downarrow$	Top-1 $\uparrow$	MRR $\uparrow$	NLL $\downarrow$
Last Seen	0.00	0.1699	3.4011	50.00	0.5850	1.8825
Time Frequency	33.85	0.5462	1.8400	49.53	0.6166	1.6455
Direct Transformer	34.16	0.5586	1.7292	51.71	0.6884	1.3157
Shared semantic prior	36.02	0.5957	1.5766	59.47	0.7462	1.0448
	38.24	0.5971	1.4925	61.18	0.7523	0.9778

Table 5: Current-state prediction on temporal and LOSO splits.

Appendix figures & tables23 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 7: Temporally versioned 4D memory construction.

Source	$\mathbf{N_{\rm raw}}$	$\mathbf{N_{\rm std}}$	$\mathbf{N_{\rm used}}$	$\mathbf{N_{\rm ref}}$
CASAS Aruba	1,602,820	20,252	428	480
ARAS	5,184,000	5,080	312	360
HD-EPIC	59,454	10,786	742	864
ParaHome	212 seq.	860	186	216
OPPORTUNITY	869,387	2,551	318	372
HOMER+ (sim.)	65 seq.	1,991	356	420

Appendix

Table 6: Audited source contributions.

Figure 8: Temporal change density in paired routine and random worlds.

Regime	Mechanism	Frozen signal	Role
Stable/rare	Infrequent events	Home/return tendency	Persistence control
Routine	Activity state machine	Chain-specific locations	Routine prediction
Personal	Placed/carried lifecycle	Owner placement habit	Long-term memory
Irregular	Affordance sampling	Affordance only	Uncertainty control

Appendix

Table 7: Mobility regimes in EvoWorld-Bench .

	Task	Decision signal	Primary measure
P	Current-state prediction	Region/receptacle belief	R@ $k$ / NLL
N1	Predictive navigation	Event-filtered belief	First-Inspection SR
N2	Belief-guided search	Full belief + cost	Search SR / cost
N3	Evidence-aware replanning	Updated posterior	Recovery SR
N4	Online-dynamic navigation	Arrival-time belief	Online Recovery SR
N5	Cross-scene generalization	Any protocol above	Held-out SR

Appendix

Table 8: Prediction and navigation protocols in EvoWorld-Bench .

	Standard Simulation Worlds				Photorealistic Simulation				Evolving Simulation Worlds
	R2R-CE		HM3D-OVON		PointNav		SAGE-Bench		EvoWorld-Bench
Method	SR	SPL	SR	SPL	SR	SPL	SR	SPL	SR	SPL
Navigation-trained or task-adapted
MTU3D ( Zhu et al., 2025 )	8.8	6.5	40.8 PR	12.1 PR	75.8	72.7	25.9	15.6	35.2	30.7
NaVid ( Zhang et al., 2024b )	37.4 PR	35.9 PR	60.3	36.0	15.3	13.4	17.4	15.1	31.0	22.6
Uni-NaVid ( Zhang et al., 2024a )	47.0 PR	42.7 PR	39.5 PR	19.8 PR	15.9	13.2	26.4	23.1	55.3	41.7

Appendix

Table 9: Cross-environment navigation.

Predictor	Temporal Top-1 $\uparrow$	MRR $\uparrow$	NLL $\downarrow$	LOSO Top-1 $\uparrow$	MRR $\uparrow$	NLL $\downarrow$
Uniform Random	9.32	0.2607	2.4509	11.96	0.3050	2.2980
Last Seen	0.00	0.1699	3.4011	50.00	0.5850	1.8825
Object Frequency	30.75	0.5476	1.7397	50.47	0.6441	1.8455
Time Frequency	33.85	0.5462	1.8400	49.53	0.6166	1.6455
Markov	18.94	0.4435	2.3772	49.38	0.6286	1.6982
Activity-Markov	25.16	0.4582	2.2436	49.84	0.6221	1.6183

Appendix

Table 10: Full current-state prediction results.

Method	Inspect. $\downarrow$	Distance (m) $\downarrow$	Recovery SR (%) $\uparrow$
Navigation and persistent memory
VLFM ( Yokoyama et al., 2024 )	4.85	18.72	22.41
LagMemo GLUE ( Zhou et al., 2025 )	3.92	13.24	45.62
HOV-SG ( Werby et al., 2024 )	3.36	12.08	51.24
DynaMem ( Liu et al., 2024a )	2.51	11.59	63.93
Predictive world and state modeling

Appendix

Table 11: EvoWorld-Bench routine-world search cost and recovery.

Different VLMs	Last-seen Agent			EvolvingNav			$\Delta$ Search SR $\uparrow$
Different VLMs	First-Inspection SR $\uparrow$	Search SR $\uparrow$	SPL $\uparrow$	First-Inspection SR $\uparrow$	Search SR $\uparrow$	SPL $\uparrow$	$\Delta$ Search SR $\uparrow$
GPT-4o	31.88	48.94	0.3215	59.72	71.86	0.6027	+22.92
GPT-5.5	42.36	51.31	0.3732	63.48	73.57	0.6531	+22.26
GPT-5.6-Luna	46.92	57.43	0.3970	63.87	83.36	0.6639	+25.93
Qwen2.5-VL-3B	16.26	26.55	0.1502	38.27	45.02	0.3727	+18.47
Qwen2.5-VL-32B	18.84	31.30	0.1591	42.44	46.21	0.3713	+14.91

Appendix

Table 12: VLM robustness on EvoWorld-Bench.

Figure 9: Outdoor car search under stale and predictive memories.

Group	Variant	First-Inspection SR $\uparrow$	Search SR $\uparrow$	SPL $\uparrow$	Inspect. $\downarrow$
Temporal encoding	w/o elapsed-time encoding	48.37	80.28	64.82	4.36
	w/o calendar context	47.75	76.11	66.20	4.05
	w/o both temporal cues	40.84	76.03	64.98	4.12
Historical evidence	w/o instance-specific history	57.57	80.77	66.61	4.30
Historical evidence	w/o negative history	45.86	79.53	63.83	4.44
	$K=8$	39.55	63.77	56.00	4.57

Appendix

Table 13: Temporal and memory ablations.

Figure 10: Evidence-aware belief updating and replanning after a negative inspection.

Predictor	Top-1 $\uparrow$	MRR $\uparrow$	NLL $\downarrow$
GRU	32.61	0.5471	1.8279
Direct Transformer	34.16	0.5586	1.7292
Structured Transformer (ours)	$\mathbf{38.24\pm 1.42}$	$\mathbf{0.5971\pm 0.0291}$	$\mathbf{1.4925\pm 0.0867}$

Appendix

Table 14: Predictor architecture on changed-only queries.

Figure 11: Predictive diagnostics under memory staleness and search budgets.

Method	Static SR	Routine SR	Random SR	Routine gain over Last Seen
Last Seen	84.38	38.49	23.19	–
Markov Transition	80.22	32.57	20.64	$-5.92$
Direct Transformer	69.79	48.82	31.39	$+10.33$
EvolvingNav	82.19	60.85	30.12	$+22.36$

Appendix

Table 15: Paired-world SR and routine gain (%).

Figure 12: Recovery under behavior shift and temporal grounding to held-out traces.

Platform	Morphology	Standing size	Mass	Endurance / range
LYNX M20	Wheel-legged	$820\times 430\times 570$ mm	$\sim$ 35 kg	3 h / 15 km unloaded
X30	Quadruped	$1000\times 695\times 470$ mm	56 kg	2.5–4 h / $\geq$ 10 km
Lite3 (LiDAR)	Quadruped	$610\times 370\times 496$ mm	13.5 kg	1.5–2 h / 2.7 km

Appendix

Table 16: Robot platforms for real-world evaluation.

	Indoor			Outdoor
Method	First-Inspection	Search SR	Dist.	First-Inspection	Search SR	Dist.
Last Seen + Search	18.8	31.3	28.6	15.6	21.9	83.8
Time Frequency	25.0	34.4	27.2	18.8	28.1	78.6
Retrieval + Reasoning	31.3	40.6	25.1	21.9	34.4	75.5
EvolvingNav	40.6	53.1	22.4	28.1	43.8	65.2

Appendix

Table 17: LYNX M20 results by environment.

Panel of Figure 13 — Figure 13: Indoor cup search with predictive belief (top) and stale Last Seen memory (bottom).

Method	Unchanged	Routine- consistent	Weak- routine	Broken- routine
Last Seen + Search	68.8	18.8	12.5	6.3
Time Frequency	50.0	50.0	18.8	6.3
Retrieval + Reasoning	62.5	43.8	25.0	18.8
EvolvingNav	62.5	68.8	37.5	25.0

Appendix

Table 18: LYNX M20 Search SR by temporal condition (%).

Platform	Method	First-Inspection SR	Search SR	Dist. (m)
LYNX M20	Last Seen + Search	18.8	25.0	55.4
LYNX M20	EvolvingNav	37.5	50.0	44.6
X30	Last Seen + Search	18.8	25.0	54.1
X30	EvolvingNav	31.3	43.8	46.8
Lite3	Last Seen + Search	18.8	31.3	51.8
Lite3	EvolvingNav	25.0	43.8	45.9

Appendix

Table 19: Cross-platform navigation transfer.

Figure 14: Long-horizon indoor document-delivery execution.

Figure 15: Long-horizon outdoor shared-bike search.

Explore similar work

OmniNav: Robust Long-Horizon Target Navigation in Dynamic Environments
Sep 8, 2026Yujie Tang, Meiling Wang, Jinhao Jiang +4Object Goal Navigation Environment
School of Automation, Beijing Institute of Technology, Beijing, China.
EvoNav-Bench: Benchmarking Lifelong Navigation in Evolving Environments
Sep 8, 2026Xilin Wang, Guoxi Zhang, Hongming Xu +3Object Goal Navigation Navigation
State Key Laboratory of General Artificial Intelligence, BIGAI · 2Tsinghua University
Rethinking Embodied Navigation via Relational Inductive Bias
Jun 9, 2026Weitao An, Chenghao Xu, Xu Yang +1Menu Open-Vocabulary
School of Electronic Engineering, Xidian University, Xi’an 710071, China · School of Information Science and Engineering, Hohai University, Nanjing 210098, China

Sep 8, 2026, cs.ROJ/K move · Enter open · S save

OmniNav: Robust Long-Horizon Target Navigation in Dynamic Environments

Yujie Tang, Meiling Wang, Jinhao Jiang, Sibo Zuo+3

School of Automation, Beijing Institute of Technology, Beijing, China.

Object Goal Navigation Environment Omnimem

Open paper AskPDF arXiv

Long-horizon target navigation requires a robot to sustain task execution across evolving observations, decisions, and physical interactions. This requires three coupled capabilities: maintaining valid scene memory, revising target beliefs under partial observability, and selecting interaction-feasible navigation endpoints. However, the state underlying each capability is only conditionally valid: scene representations become stale when objects move or disappear, unsuccessful searches alter beliefs over target locations, and geometrically convenient endpoints may still be infeasible for manipulation. To address these challenges, we present OmniNav, which formulates long-horizon navigation as continual inference over a factorized task state posterior coupling scene validity, target belief, and interaction feasibility. For representation, OmniNav incrementally constructs an updatable 3D object scene memory, preventing stale scene evidence from propagating to subsequent decisions. For exploration, it introduces an evidence-aware Bayesian belief-revision mechanism that derives dependency-aware region priors from semantic context, incorporates unsuccessful searches as negative evidence, and updates them for posterior-guided frontier selection. For interaction, OmniNav incorporates manipulation reachability and collision constraints into navigation-endpoint selection and propagates execution feedback through hierarchical closed-loop recovery. Extensive experiments demonstrate that OmniNav achieves the highest success rates among the compared methods on semantic ObjectNav and fine-grained instance navigation benchmarks, remains robust to target relocation, and improves real-world pick-and-place success from 53.3% to 71.7% over an adapted open-loop baseline. The project page of OmniNav is available at https://omni-nav.github.io/.

Abstract

Explore similar work

OmniNav: Robust Long-Horizon Target Navigation in Dynamic Environments

EvoNav-Bench: Benchmarking Lifelong Navigation in Evolving Environments

Rethinking Embodied Navigation via Relational Inductive Bias