Compact Bellman-Grounded Cognitive Maps for Cost-Aware Navigation
Authors: Yuzhe Han, Mingkun Xu, Yujie Wu
Organizations: Guangdong Institute of Intelligence Science and Technology (GDIIST), Zhuhai, China · Department of Computing, The Hong Kong Polytechnic University, Hong Kong SAR, China
Biological agents navigate familiar environments not by re-solving routes for each new goal, but by reusing a learned map built once and read off as goals change. Existing artificial cognitive-map models mimic this reuse, yet their guidance is not explicitly grounded in additive heterogeneous route costs. Furthermore, they often struggle with memory efficiency: representative state-indexed and high-rank spectral constructions incur substantial storage growth as the environment scales. We present BCM, which grounds a reusable cognitive map in local edge costs through a self-supervised Bellman-grounded objective and a compact coordinate encoding, supporting changing goal queries without per-goal retraining. On weighted grids of up to N=1600 nodes, BCM maintains full success and only a 5% mean Gap relative to exact Dijkstra search, compared with about 45% for a connectivity-based spectral baseline. Notably, as the graph size increases from N=400 to N=3600, its memory footprint grows sublinearly while maintaining competitive performance, making our method scalable to complex environments. Together, these results show that additive route costs can be written into a compact, reusable cognitive-map representation, bridging the gap between biological flexibility and optimal path planning.
Figures & tables
Figure 1: Planning on the same weighted U-shaped graph. BCM matches the Dijkstra reference cost, EigenAgent incurs 32% higher cost, and CML fails by oscillation.
Figure 2: Overview of BCM. A shared pipeline compactly encodes node coordinates ( ψ ) and transitions from embedding differences ( ϕ ). Training applies a Bellman-grounded cost-grounding objective to the discrepancy D . At deployment, BCM performs online local readout, while node embeddings may optionally be cached and reused across goal queries.
Properties
Uniform
Mild [1,3]
Wide [1,10]
Method
Reuse
Weighted
Sublinear
SR ↑
Cost ↓
Gap ↓
SR ↑
Cost ↓
Gap ↓
SR ↑
Cost ↓
Gap ↓
Dijkstra (opt.)
✗
✓
—
1.00
28.5
0.0
1.00
47.1
0.0
1.00
108.8
0.0
CML †
✓
✓
✗
0.27
40.0
185.6 ± 29.8
0.20
50.6
147.8 ± 37.3
0.16
107.1
154.4 ± 72.0
APF †
✗
✗
—
0.82
27.0
0.0 ± 0.0
0.82
53.8
19.7 ± 0.3
0.82
147.4
42.3 ± 0.8
EigenAgent
✓
✗
✗ ∗
1.00
29.9
4.4 ± 1.1
1.00
59.5
24.4 ± 1.7
1.00
163.0
47.2 ± 1.7
BCM (ours)
✓
✓
✓
1.00
28.5
0.07 ± 0.05
1.00
48.8
4.01 ± 0.37
1.00
114.0
5.07 ± 0.64
Table 1: Path quality under increasing edge-cost heterogeneity ( N=1600 , U-shaped layout). Reuse denotes reuse across goals; Weighted , the use of edge costs; and Sublinear , reusable representation storage growing sublinearly in N (—: not applicable). ∗ EigenAgent requests k=N−2 modes and retains 1534 numerically converged modes at N=1600 , yielding quadratic storage in this near-full-rank setting. Results are mean ± std over three runs, with 100 pairs per run. Cost and Gap are computed over successful pairs; † marks incomplete success. Best full-success non-reference results are shown in bold . CML uses the authors’ released implementation and native greedy planner.
Mild [1,3]
Wide [1,10]
Layout
Method
SR ↑
Cost ↓
Gap ↓
SR ↑
Cost ↓
Gap ↓
U-shaped ∗
Dijkstra (opt.)
1.00
47.3
0.0
1.00
106.4
0.0
APF †
0.78
51.6
20.1
0.78
130.4
42.2
EigenAgent
1.00
58.5
23.6
1.00
158.3
45.2
BCM
1.00
48.9
3.5
1.00
111.3
5.8
Center block
Dijkstra (opt.)
1.00
42.9
0.0
1.00
97.9
0.0
Table 2: Path quality across obstacle layouts under mild and wide edge-cost heterogeneity ( N=1600 ). Cost and Gap are computed over successfully solved pairs. † denotes methods with SR<1 . ∗ The U-shaped rows use a single seed ( 42 ), whereas Table 1 reports three-seed means. Bold indicates the lowest Cost and Gap among non-reference methods with full success.
Figure 3: Scalability and method-specific representation size on the U-shaped layout under wide edge costs. (a) Representation size on a logarithmic scale, counting model parameters for BCM, retained eigenvectors and eigenvalues for EigenAgent, and exact distance and next-hop tables for APSP. Optional BCM node-embedding caches, graph adjacency, and edge-cost storage are excluded. (b) Path-quality Gap as N increases. (c) Empirical quality–storage trade-off at N=1600 . All plotted methods reach every goal at every tested size; APSP is the exact quadratic-storage reference.
Encoding
Scaling
# Params
Gap ↓ (mild)
Gap ↓ (wide)
one-hot
O(N)
541K
2.55
4.11
k -hot (additive)
O(N)
152K
12.82
15.88
interaction (ours)
O(N)
186K
3.31
4.94
Table 3: Coordinate-encoding ablation ( N=1600 , U-shaped layout; Gap in %). All variants share the same transition head, training protocol, and readout; only the node encoding changes. All variants use a single seed (42), whereas Table 1 reports three-seed means. Scaling denotes asymptotic parameter growth with N , whereas # Params gives the total trainable parameter count at N=1600 . Bold indicates the lowest Gap.
SR ↑
wSPL ↑
Encoding
None
Visited-aware
None
Visited-aware
one-hot
0.86
1.00
0.833
0.958
k -hot
0.76
0.97
0.698
0.865
interaction (ours)
0.84
1.00
0.799
0.950
Table 4: Visited-aware readout ablation on the U-shaped layout under the wide-cost regime ( N=1600 ). We report weighted SPL, wSPL=M1∑i=1MSimax(ciopt,cipath)ciopt , where M is the number of Dijkstra-reachable evaluation queries, Si∈{0,1} is the success indicator, and ciopt and cipath are the Dijkstra-optimal and realized weighted path costs, respectively. Failed rollouts contribute zero. This metric adapts SPL ( Anderson et al. 2018 ) by replacing path length with weighted cost. Gap is omitted because it is conditioned on success and is not directly comparable when SR differs substantially.
Graph-based agent memory organizes an agent’s experiences, facts, and procedures as linked structures for persistent, evidence-aware retrieval and reuse.