Compact Bellman-Grounded Cognitive Maps for Cost-Aware Navigation Yuzhe Han1 , Mingkun Xu1∗ , Yujie Wu2∗ 1
arXiv:2609.05104v1 [cs.AI] 4 Sep 2026
2
Guangdong Institute of Intelligence Science and Technology (GDIIST), Zhuhai, China Department of Computing, The Hong Kong Polytechnic University, Hong Kong SAR, China [email protected], [email protected]
Abstract
Dijkstra – 102.66 (optimal)
BCM (ours) – 102.66
Biological agents navigate familiar environments not by resolving 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.
EigenAgent – 135.68 (+32%)
CML – oscillatory failure
Introduction Animals and humans navigate familiar environments not by solving each new goal from scratch, but by reusing a learned cognitive map (Tolman 1948), built through experience and queried as goals change. This suggests that the difficulty of planning lies not only in search but also in the efficiency of the representation being reused. Reproducing this flexibility in artificial agents remains challenging, particularly on weighted graphs, where the most direct geometric route need not be the least costly. Cognitive-map models were designed to provide this exact type of reusable guidance, yet they are currently missing a crucial dimension: the actual cost of movement. For instance, successor representations capture policy-conditioned predictive occupancy (Dayan 1993; Stachenfeld, Botvinick, and Gershman 2017); spectral methods organize states according to graph connectivity (Mahadevan and Maggioni 2007; Zuo et al. 2026); and inverse-model metrics induce actionconsistent directional guidance (Stöckl, Yang, and Maass 2024; Lin et al. 2026). None of these approaches inherently ∗
Corresponding author.
Obstacle 2
Start
Goal
4 6 8 Average adjacent edge weight
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.
understands that traversing a swamp costs more than walking on a paved road. Consequently, under heterogeneous edge weights, such representations can favor routes that are geometrically or topologically plausible yet substantially more expensive (Figure 1). Beyond this lack of cost awareness, existing reusable maps also face scalability challenges. Full-rank spectral maps retain a quadratic number of coefficients, while CML-style learners rely on one-hot state and action parameterizations that grow with the enumerated spaces. The core challenge is therefore to learn a compact, reusable cognitive-map repre-
sentation that captures additive route-cost structure. To address this challenge, we introduce the Bellmangrounded Cognitive Map (BCM) that combines cost-aware local scoring with a compact, reusable, goal-independent representation for planning across goals. Three key innovations enable this: first, a Bellman-grounded objective makes the scores cost-aware: for a nonterminal step, its score is shaped by the cost of that edge plus the best downstream score. We construct this self-supervised objective from the graph’s own transitions and edge costs, without shortest-path supervision. Second, BCM retains online planning: each action is selected on demand from local scores, without first constructing a complete path or expanding a search tree (Mattar and Lengyel 2022; Russell and Norvig 2020). And because the encoder is goal-independent, the underlying node representation is shared across goals. Changing the goal, therefore, requires neither rebuilding nor retraining the map. Third, an interaction-based coordinate encoder keeps the map compact by binding per-axis embeddings, so √ that the coordinate-dependent parameter count grows as O( N ) on two-dimensional grids. Our contributions are threefold: • A cost-grounded cognitive map. We identify additive route cost as a missing representational component of reusable cognitive maps on heterogeneous weighted graphs, and introduce BCM to ground goal-conditioned guidance in weighted route structure without shortestpath supervision. • Compact online multi-goal planning. BCM supports online planning across changing goals from a shared cognitive map, while √ its coordinate-dependent parameter count grows as O( N ) on two-dimensional grids. • Empirical validation. Across three weighted-grid layouts through N = 1600, BCM maintains full success and approximately 5% mean Gap under the widest weight range, compared with about 45% for the evaluated connectivity-based spectral map.
Method As illustrated in Figure 2, BCM has three components: transition encoding, Bellman-grounded training, and online greedy readout. A node encoder ψ maps node coordinates to embeddings, and a transition encoder ϕ maps differences between node embeddings to transition embeddings.
Problem Setup We consider repeated planning in a single fixed environment, modeled as an undirected weighted graph G = (V, E) with N = |V | nodes. Each node i ∈ V has coordinates xi (e.g., its position on a 2D grid), and each edge (i, j) ∈ E has a known positive cost ci→j > 0. We write N (i) = {j | (i, j) ∈ E} for the neighbors of i. Given a start node s and a goal node g, the planner constructs a route by sequentially selecting a neighboring node until reaching g.
Transition Encoding This difference-based form follows inverse-model cognitive maps (Stöckl, Yang, and Maass 2024), but rather than align-
ing each difference with a separate action embedding, we compare a candidate local transition with the displacement toward the goal. A node encoder ψ maps each node’s coordinates to an embedding oi = ψ(xi ) ∈ Rdo . The transition encoder ϕ then maps an embedding displacement between two nodes to a transition embedding: zi→j = ϕ(oj − oi ),
(1)
dz
where zi→j ∈ R . For a candidate neighbor j ∈ N (i) and goal g, we define Di (j; g) = ∥zi→j − zi→g ∥2 .
(2)
A smaller Di (j; g) assigns higher priority to candidate j under the learned goal-conditioned transition geometry.
Bellman-Grounded Objective We train ψ and ϕ using the Bellman-grounded regression objective h 2 i L(θ) = E(i,j,g) Di (j; g) − ci→j − sg[ min Dj (k; g)] k∈N (j)
(3) where sg[·] denotes the stop-gradient operator. For nonterminal transitions, the target combines the immediate edge cost with the best downstream score, providing additive Bellman grounding. Detaching the bootstrap term yields a semi-gradient TD update (Sutton 1988). The targets are constructed from sampled local transitions and observed edge costs, without shortest-path or optimal-action labels. Because Di (g; g) = 0 by construction, the goal provides a structural terminal anchor for the recursion. In particular, when g ∈ N (j), the bootstrap term satisfies mink∈N (j) Dj (k; g) = Dj (g; g) = 0, so the target reduces to the immediate edge cost ci→j . Accordingly, we interpret Di (j; g) as a goal-conditioned transition-ranking score whose learned geometry reflects additive weighted route-cost structure, rather than as an exact optimal cost-to-go.
Online Greedy Readout After training, BCM performs online planning through a local greedy rollout. The learned node representation is shared across goals, so changing the goal requires neither rebuilding nor retraining the map; it only changes the goal-conditioned scores used during local readout. To reduce cycling during the rollout, at node i we define the candidate set ( N (i) \ V, N (i) \ V ̸= ∅, Ci = (4) N (i), otherwise, where V contains the nodes visited during the current rollout. The next node is selected as j ∗ = arg min Di (j; g). j∈Ci
(5)
This visited-aware rule prefers unvisited neighbors while allowing revisits when no unvisited action remains. It introduces limited path memory without adding goal or shortestpath information; we isolate its effect in the ablation study.
Shared Pipeline Goal g (Compact coordinate encoding)
(any goal)
g
Readout + Output (neighbor difference)
(goal difference)
n
(visited-aware)
Output: gradients
gradients
Training (offline, per graph) ？
Deployment (online, per goal)
Bellman-grounded loss:
✓
Optional cache: shared across goals
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.
Compact Coordinate Encoding The node encoder ψ maps node coordinates to embeddings. A naive state-wise one-hot code makes the input-layer parameter count grow as O(N ), tying the encoder size to the number of nodes. For an S × S grid with N = S 2 , we instead encode the two coordinate axes independently, re√ ducing this parameter growth to O(S) = O( N ) for fixed embedding width. The resulting additive k-hot encoding, however, underperforms empirically (Table 3), suggesting that independent axis contributions do not adequately capture row–column interactions. To introduce these interactions, let r(n) = ⌊n/S⌋ and c(n) = n mod S denote the row and column indices of node n. Learnable projections Wr and Wc map the corresponding one-hot coordinates to rn = Wr er(n) ,
cn = Wc ec(n) .
(6)
We then define on = ψ(xn ) = [rn ; cn ; rn ⊙ cn ] ∈ Rdo ,
(7)
where ⊙ denotes the Hadamard product. The interaction term √ captures row–column combinations while preserving O( N ) input-layer parameter growth. In the ablation study, this encoding substantially improves over additive k-hot encoding and approaches the performance of state-wise one-hot encoding.
Experiments Setup We evaluate on fixed weighted 2D grid graphs, where each node has integer coordinates and each edge has a known positive cost. We consider three obstacle layouts probing different geometric conditions: a U-shaped trap, a central block, and a vertical wall with a single-cell gap. The
U-shaped layout scales proportionally with the grid side, whereas the wall thickness and gap in the wall-with-gap layout remain one cell wide. Edge costs follow three regimes: uniform (all costs equal to 1), mild (cij ∼ U(1, 3)), and wide (cij ∼ U (1, 10)), with continuous uniform sampling in the latter two regimes. Unless otherwise stated, experiments use N = 1600 (40 × 40); scaling experiments vary N ∈ {400, 900, 1600, 3600} on the U-shaped layout under wide costs. Across graph sizes, BCM uses a transition MLP with two hidden layers of width 256 and a 256-dimensional output (dz = 256). The per-axis embedding dimension is 64, yielding do = 192 for the interaction encoding. Our main results (Table 1) report mean±std over three runs using seeds 42, 111, and 512, with 100 evaluation start–goal pairs per run. Unless otherwise noted, other experiments use a single run and 100 evaluation pairs per graph. Our baselines span the space between searching anew for every goal and precomputing all answers in advance. At one end, Dijkstra provides exact per-query weighted-optimal search. At the other, APSP removes online search by precomputing exact pairwise distance and next-hop tables, requiring O(N 2 ) storage and enabling O(1) next-hop lookup at each rollout step. Between them lie methods that build a reusable representation once and read from it across goals. CML (Stöckl, Yang, and Maass 2024), the direct predecessor of our method, learns an inverse-model metric giving heuristic directionality toward a goal. EigenAgent (Zuo et al. 2026) instead builds its representation analytically from the binary graph Laplacian, yielding a spectral potential that does not use edge costs. APF (Khatib 1986) is a hand-designed local potential built from geometric attraction and obstacle repulsion, using only geometric distance rather than edge costs and requiring neither learning nor precomputation. Together, these methods differ along the three axes summarized
in Table 1. Path quality is compared across Dijkstra, EigenAgent, CML, APF, and BCM. Because CML exhibits low success already on the base layout (Table 1) and incurs a large state- and action-indexed representation (13.43M parameters at N = 1600), we report it once as a lower reference and exclude it from the scale and layout analyses; the storage comparison covers BCM, EigenAgent, and APSP, representing parametric, spectral, and exact pairwise routing representations, respectively. BCM uses the interaction encoding throughout; its one-hot and k-hot variants appear in the ablation. For EigenAgent, we request k = N − 2 modes at each size and retain all numerically converged modes; at N = 1600, ARPACK converges to 1534 modes. The main comparison uses the binary Laplacian, while two cost-weighted variants only partially reduce the empirical Gap. BCM uses visited-aware greedy readout in (5), whereas CML, EigenAgent, and APF use their native greedy planners; Table 4 separately isolates the effect of BCM’s visited-aware rule. Metrics. We report success rate (SR), Cost, and Gap. SR is the fraction of start–goal pairs for which a method reaches the goal. Cost is the mean realized weighted path cost over successfully solved pairs. Gap is the mean per-pair relative excess over the corresponding Dijkstra optimum: cpath Gap = E (8) − 1 success × 100, copt where cpath is the realized path cost and copt is the Dijkstraoptimal cost for the same start–goal pair. Thus, Gap = 0% denotes optimal routing. Because Cost and Gap are conditioned on success, they must be interpreted jointly with SR when a method has incomplete success.
Weighted Path Quality We first test whether grounding a reusable cognitive map in additive edge costs improves routing as cost heterogeneity increases. Table 1 compares the methods on the same Ushaped graph under uniform, mild, and wide costs. Under uniform costs, EigenAgent and BCM both reach every goal with low Gap. As costs become heterogeneous, the Gap of the binary-Laplacian EigenAgent increases from 24.4% under mild costs to 47.2% under wide costs, whereas BCM remains at 4.0% and 5.1%, respectively. APF fails on 18% of the pairs across all three regimes and reaches a 42.3% Gap under wide costs on the pairs it solves. CML exhibits low success across all three regimes, despite receiving edge-cost information in the evaluated weighted setting. These results highlight different sensitivities among the evaluated alternatives. APF’s local geometric potential is susceptible to the U-shaped trap and does not account for heterogeneous edge costs. Although the evaluated weighted CML variant receives edge-cost information, its directional objective does not explicitly encode additive downstream route cost. EigenAgent retains full success, but its binaryLaplacian representation encodes connectivity without using edge costs, consistent with its increasing Gap as cost heterogeneity grows. BCM instead grounds its transition scores in
immediate edge costs and bootstrapped downstream scores, maintaining low empirical Gap across the tested weight regimes. One remaining possibility is that EigenAgent’s degradation arises simply because the main comparison uses a binary Laplacian. We therefore evaluate two cost-weighted variants: inverse-cost and RBF-weighted Laplacians. Under mild costs, their Gap decreases only from 24.4% to 21.4%–22.9%. Under wide costs, the inverse-cost variant reaches 42.2%, while the RBF variant reaches 51.8%. Neither tested variant closes the gap to BCM. For the evaluated constructions, these results suggest that incorporating costs into spectral affinities alone is insufficient to reproduce the low-Gap behavior obtained through BCM’s additive downstream grounding. Performance across layouts. We next test whether the effect of cost grounding persists across different obstacle geometries. We repeat the comparison on a central-block layout and a wall with a single-cell gap under mild and wide costs (Table 2). BCM reaches every goal on all three layouts, with Gap remaining below 5.9%. The binary-Laplacian EigenAgent again degrades as cost heterogeneity increases, reaching 44.6%–47.0% Gap under wide costs. APF is more sensitive to obstacle geometry: its success rate ranges from 0.98 on the central-block layout to 0.68 on the wall-with-gap layout, while its Gap also increases with cost heterogeneity. Across the tested layouts, BCM therefore maintains low Gap and full success relative to the evaluated geometric and connectivitybased alternatives.
Scalability and Storage We next examine whether BCM’s compact cost-grounded representation maintains low empirical Gap as graph size increases. We vary N ∈ {400, 900, 1600, 3600} on the Ushaped layout under wide costs, using the same architecture and hyperparameters throughout. Storage. Figure 3(a) shows that BCM’s representation grows only from 0.734 MB at N = 400 to 0.755 MB at N = 3600. Its transition encoder contributes a fixed 0.724√ MB, while the coordinate-dependent parameters grow as O( N ). In contrast, EigenAgent’s near-full-rank spectral representation grows from 0.613 MB to 49.751 MB, and the exact distance and next-hop tables of APSP grow from 1.920 MB to 155.520 MB. At N = 1600, EigenAgent and APSP require 13.2× and 41.3× the representation size of BCM, respectively; at N = 3600, these ratios increase to 65.9× and 206.1×. Path quality and trade-off. BCM maintains full success at every tested size, with Gap remaining below 5.9% through N = 1600 and rising to 12.4% at N = 3600. EigenAgent also retains full success, but its Gap remains above 38% and reaches 50.0% at the largest size (Figure 3(b)). At N = 1600, BCM achieves 5.8% Gap with a 0.744 MB representation, compared with 45.2% Gap and 9.824 MB for EigenAgent; APSP attains exact routing with 30.720 MB (Figure 3(c)). Among the evaluated reusable representations, BCM therefore provides a substantially lower-Gap and smaller-representation operating point through N = 1600.
Properties Method Dijkstra (opt.) †
CML APF† EigenAgent BCM (ours)
Mild [1, 3]
Uniform
Reuse Weighted Sublinear SR↑ Cost↓
Wide [1, 10]
Gap↓
SR↑ Cost↓
Gap↓
SR↑ Cost↓
Gap↓
1.00 108.8
0.0
✗
✓
—
1.00
28.5
0.0
1.00
47.1
0.0
✓ ✗ ✓ ✓
✓ ✗ ✗ ✓
✗ — ✗∗ ✓
0.27 0.82 1.00 1.00
40.0 27.0 29.9 28.5
185.6± 29.8 0.0± 0.0 4.4± 1.1 0.07± 0.05
0.20 0.82 1.00 1.00
50.6 53.8 59.5 48.8
147.8± 37.3 19.7± 0.3 24.4± 1.7 4.01± 0.37
0.16 0.82 1.00 1.00
107.1 154.4± 72.0 147.4 42.3± 0.8 163.0 47.2± 1.7 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. BCM
100
400
900
1600
3600
(c) Quality–storage trade-off (N = 1600)
50
50
40
40
Gap (%)
102
101
APSP
(b) Path-quality scaling
Gap (%)
Representation size (MB)
(a) Representation scaling
EigenAgent
30 20
30 20
10
10
0
0 400
N (nodes)
900
1600
N (nodes)
3600
EigenAgent
BCM APSP
100
101
Representation size (MB)
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. Its degradation at N = 3600, however, indicates reduced accuracy at the largest tested scale.
Ablation We isolate two design choices that support BCM’s empirical performance: the interaction-based coordinate encoding and the visited-aware greedy readout. All experiments use the U-shaped layout with N = 1600. Coordinate encoding. Table 3 isolates the node encoding while holding the transition head, training protocol, and readout fixed. The state-wise one-hot encoding attains the lowest Gap, but its coordinate-dependent parameter count grows as O(N ), yielding 541K total parameters at N = 1600. The additive k-hot encoding reduces the model to 152K parameters but degrades substantially under heterogeneous costs. Adding the cross-axis interaction increases the parameter count by 22%, from 152K to 186K, while reducing Gap from 12.82% to 3.31% under mild costs and from 15.88%
to 4.94% under wide costs. The interaction encoding therefore approaches one-hot performance within 0.9 percentage points while √ using about one third of its parameters and retaining O( N ) coordinate-dependent parameter growth. Visited-aware readout. Without path memory, greedy local readout can repeatedly select previously visited nodes and enter short cycles. The visited-aware rule prefers unvisited neighbors and falls back to the full neighborhood when no unvisited candidate remains. Applying this rule without changing the learned parameters raises the interaction model’s SR from 0.84 to 1.00 under wide costs. The improvement holds across all three encodings, ranging from 14 to 21 percentage points. At the same time, wSPL (defined in Table 4) rises from 0.799 to 0.950, while the average weighted-cost efficiency among successful rollouts remains approximately 0.95. Thus, the improvement in success does not come at the cost of more expensive successful routes. The rule adds no learned parameters and requires only a tempo-
Mild [1, 3]
Wide [1, 10]
Layout
Method
SR↑ Cost↓ Gap↓ SR↑ Cost↓ Gap↓
U-shaped∗
Dijkstra (opt.) 1.00 APF† 0.78 EigenAgent 1.00 BCM 1.00
47.3 0.0 1.00 106.4 51.6 20.1 0.78 130.4 58.5 23.6 1.00 158.3 48.9 3.5 1.00 111.3
Center block APF EigenAgent BCM
Dijkstra (opt.) 1.00 † 0.98 1.00 1.00
Dijkstra (opt.) 1.00 † 0.68 Wall w/ gap APF EigenAgent 1.00 BCM 1.00
wSPL↑
None Visited-aware None Visited-aware
0.0 42.2 45.2 5.8
one-hot k-hot interaction (ours)
0.86 0.76 0.84
42.9 0.0 1.00 97.9 53.4 22.7 0.98 146.5 53.2 21.8 1.00 144.9 44.2 3.2 1.00 102.5
0.0 47.2 44.6 5.2
Table 4: Visited-aware readout ablation on the U-shaped layout under the wide-cost regime (N = 1600). We report PM copt 1 i weighted SPL, wSPL = M i=1 Si max(copt ,cpath ) , where
48.1 0.0 1.00 110.4 46.3 21.1 0.68 126.4 60.9 24.4 1.00 165.7 49.5 3.0 1.00 114.7
0.0 43.9 47.0 5.3
M is the number of Dijkstra-reachable evaluation queries, Si ∈ {0, 1} is the success indicator, and copt and cpath are i i 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.
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. Encoding
SR↑ Encoding
1.00 0.97 1.00
0.833 0.698 0.799
i
0.958 0.865 0.950
i
search. In addition, the current terminal convention supports goal-conditioned transition ranking rather than calibrated final-edge value estimation.
Scaling # Params Gap↓ (mild) Gap↓ (wide)
one-hot O(N √ ) k-hot (additive) O(√N ) interaction (ours) O( N )
541K 152K 186K
2.55 12.82 3.31
4.11 15.88 4.94
Table 3: Coordinate-encoding ablation (N = 1600, Ushaped 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.
rary length-N visited mask during each rollout. The ablation therefore shows that the learned cost-grounded scores can support efficient routes, while lightweight path memory improves the robustness of greedy local readout by reducing short cycles.
Limitations BCM currently targets repeated planning on fixed, known, and coordinate-structured weighted graphs, with one representation learned per graph. Substantial changes to topology or edge costs would therefore require updating or retraining the model. We also observe reduced accuracy on denser maze layouts and at the largest tested scale: under wide costs, Gap rises to 12.4% at N = 3600. These results indicate that the current model is most reliable when coordinates provide meaningful structural information and at moderate graph scales. As a learned local planner, BCM does not inherit the formal optimality or completeness guarantees of exact graph
Related Work Cognitive maps. Cognitive maps (Tolman 1948) are internal representations of an environment that support flexible routing, studied both as accounts of biological navigation (Whittington et al. 2020; Gornet and Thomson 2024) and as reusable structures for planning. Existing approaches differ in the quantity encoded by the representation. Successor representations (Dayan 1993; Stachenfeld, Botvinick, and Gershman 2017; Barreto et al. 2017) learn policyconditioned future occupancy through an expectation-based temporal-difference recursion. Spectral methods (Mahadevan and Maggioni 2007; Machado et al. 2018; Wu, Tucker, and Nachum 2019) organize states through diffusion in the graph-Laplacian eigenbasis, including EigenAgent (Zuo et al. 2026). Our main EigenAgent instantiation is constructed from the binary Laplacian and therefore does not use heterogeneous edge costs; the two cost-weighted variants only partially reduce the empirical Gap. Inverse-model metrics (Stöckl, Yang, and Maass 2024; Lin et al. 2026; Polykretis and Danielescu 2024) learn embedded observation differences aligned with corresponding action vectors, producing an action-aligned directional signal for local guidance without an explicit additive downstream-cost recursion. Linear RL (Piray and Daw 2021) and its featurized extensions (Bazarjani and Piray 2026) are closer in their use of a Bellman formulation for control, but solve a default-policyregularized soft-control problem through a linearized formulation. Across these lines, BCM differs by using immediate edge costs and a hard minimum over downstream transitions, grounding its nonterminal transition-ranking scores in a hard-minimum Bellman-grounded recursion over the graph’s edge costs.
Learned planning representations. Goal-conditioned reinforcement learning (Kaelbling 1993), including universal value functions V (s, g) (Schaul et al. 2015), reuses learned parameters across changing goals. Quasimetric representations similarly support goal reaching through greedy descent (Wang et al. 2023; Eysenbach et al. 2022). Differentiable planners (Tamar et al. 2016; Wang et al. 2024, 2025; Zhao, Xu, and Wong 2023) embed value-iteration-like computation in learned architectures, while Plan2vec (Yang et al. 2020) learns a latent representation for planning using shortest-path supervision. BCM focuses on a different operating point: repeated planning on one fixed, known weighted graph. It learns a compact, graph-specific, cost-grounded representation from local graph transitions and edge costs, without shortest-path labels or per-goal retraining. Search. Dijkstra and A* with an admissible heuristic (Dijkstra 1959; Hart, Nilsson, and Raphael 1968) provide exact per-query planning. All-pairs precomputation (Floyd 1962) shifts computation into a quadratic-storage table. Contraction hierarchies (Geisberger et al. 2008) trade graph preprocessing and auxiliary storage for faster exact shortest-path queries. Learned heuristics (Yonetani et al. 2021; Archetti, Cannici, and Matteucci 2022) retain per-query search while reducing node expansions, generally without retaining the same admissibility-based guarantees. BCM studies a different operating point: a graph-specific learned representation is constructed once and reused across goals through local readout. We therefore use exact search and all-pairs precomputation as references; unlike exact graph search, BCM does not provide formal optimality or completeness guarantees.
Discussion BCM separates planning into a few parts—a coordinate encoding, a transition encoder, and a local readout—all trained under a single Bellman-grounded objective. The objective provides the common training principle; the surrounding components are implementation choices, and here each is instantiated in a basic form: a compact coordinate encoding whose parameters grow with per-axis resolution, a feedforward transition encoder with two hidden layers, and a greedy readout with a visited-aware rule. That so minimal an instance already achieves low empirical Gap suggests that cost-grounded representation is a useful core ingredient, while each surrounding component remains a place to strengthen rather than a fixed part of the method. Consider the encoding. Its binding principle—encoding factors separately and then binding them to distinguish their conjunctions—is not conceptually specific to coordinates and may extend to other settings where node identity factorizes: grid coordinates split naturally into x and y, while a puzzle state may decompose into tile identity and position. Coordinates are the case studied here, and our experiments validate this principle only for 2D grids; nevertheless, extending such factors toward more abstract structure offers a promising direction toward more transferable representations. The payoff of this binding is structural: the transition encoder remains fixed in width, the readout adds no learned parameters, and the coordinate-dependent model parameters grow as
√ O( N ). Consequently, BCM’s method-specific representation increases only from 0.734 MB at N = 400 to 0.755 MB at N = 3600, while supporting goal-conditioned transition scores that reflect weighted route-cost structure. Beyond the coordinate encoding, the transition encoder is equally open to strengthening: a graph-based encoder aggregating neighborhood structure could provide topological cues that the current feedforward map must infer indirectly. The readout admits a similar interpretation. The greedy rule follows the network’s goal-conditioned transition scores without memory of its path and can stall by cycling among a few nodes. A visited-aware rule that prioritizes unvisited neighbors, while allowing fallback when none remain, substantially improves success without retraining or changing the learned scores. That such a lightweight modification is effective suggests that memoryless rollout contributes substantially to the remaining failures. Stronger readouts incorporating limited lookahead, backtracking, or local search are therefore a natural next step, while the reusable costgrounded representation remains the common foundation. Taken together, these components make BCM a minimal but complete instance: strong enough to achieve low empirical Gap on the tested weighted graphs, plain enough that each part invites a better replacement. We offer it less as a finished planner than as a modular starting point for representationcentric planning.
Conclusion We presented BCM, a cost-grounded cognitive-map model for repeated planning on fixed, known weighted graphs. BCM learns goal-conditioned transition-ranking scores from local heterogeneous edge costs through a Bellman-grounded objective and generates routes using visited-aware greedy readout. Across the tested weighted grids, BCM maintains full success and approximately 5% mean Gap through N = 1600 under the widest weight range, compared with about 45% for a representative connectivity-based spectral map. Its √ coordinate-dependent parameter count grows as O( N ) on two-dimensional grids, although Gap rises to about 12% at N = 3600. Because the underlying representation is shared across goals, changing the queried goal requires neither rebuilding the map nor per-goal retraining. These results show that additive route-cost structure can be encoded in a compact, reusable cognitive-map representation.
Ethical Statement This work studies graph-planning algorithms in synthetic fixed environments and does not use human-subject data, private data, or deployed decision systems. Potential risks are limited to downstream use of planning systems in real-world settings, where safety constraints, uncertainty, and failure recovery should be evaluated separately before deployment.
References Anderson, P.; Chang, A.; Chaplot, D. S.; Dosovitskiy, A.; Gupta, S.; Koltun, V.; Kosecka, J.; Malik, J.; Mottaghi, R.; Savva, M.; and Zamir, A. R. 2018. On Evaluation of Embodied Navigation Agents. arXiv:1807.06757.
Archetti, A.; Cannici, M.; and Matteucci, M. 2022. Neural Weighted A*: Learning Graph Costs and Heuristics with Differentiable Anytime A*. In Machine Learning, Optimization, and Data Science (LOD), volume 13163 of Lecture Notes in Computer Science, 596–610. Springer. Barreto, A.; Dabney, W.; Munos, R.; Hunt, J. J.; Schaul, T.; van Hasselt, H.; and Silver, D. 2017. Successor Features for Transfer in Reinforcement Learning. In Advances in Neural Information Processing Systems (NeurIPS). Bazarjani, A.; and Piray, P. 2026. Default Feature Representations of the Cognitive Map. bioRxiv. Preprint. Dayan, P. 1993. Improving Generalization for Temporal Difference Learning: The Successor Representation. Neural Computation, 5(4): 613–624. Dijkstra, E. W. 1959. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1: 269–271. Eysenbach, B.; Zhang, T.; Levine, S.; and Salakhutdinov, R. 2022. Contrastive Learning as Goal-Conditioned Reinforcement Learning. In Advances in Neural Information Processing Systems (NeurIPS). Floyd, R. W. 1962. Algorithm 97: Shortest Path. Communications of the ACM, 5(6): 345. Geisberger, R.; Sanders, P.; Schultes, D.; and Delling, D. 2008. Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. In International Workshop on Experimental Algorithms (WEA), 319–333. Gornet, J.; and Thomson, M. 2024. Automated Construction of Cognitive Maps with Visual Predictive Coding. Nature Machine Intelligence, 6: 820–833. Hart, P. E.; Nilsson, N. J.; and Raphael, B. 1968. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2): 100–107. Kaelbling, L. P. 1993. Learning to Achieve Goals. In International Joint Conference on Artificial Intelligence (IJCAI), 1094–1098. Khatib, O. 1986. Real-Time Obstacle Avoidance for Manipulators and Mobile Robots. The International Journal of Robotics Research, 5(1): 90–98. Lin, H.; Yang, Y.; Zhao, R.; Pezzulo, G.; and Maass, W. 2026. Neural Sampling from Cognitive Maps Enables GoalDirected Imagination and Planning. Nature Machine Intelligence, 8: 1045–1065. Machado, M. C.; Rosenbaum, C.; Guo, X.; Liu, M.; Tesauro, G.; and Campbell, M. 2018. Eigenoption Discovery through the Deep Successor Representation. In International Conference on Learning Representations (ICLR). Mahadevan, S.; and Maggioni, M. 2007. Proto-Value Functions: A Laplacian Framework for Learning Representation and Control in Markov Decision Processes. Journal of Machine Learning Research, 8: 2169–2231. Mattar, M. G.; and Lengyel, M. 2022. Planning in the brain. Neuron, 110: 914–934. Piray, P.; and Daw, N. D. 2021. Linear reinforcement learning in planning, grid fields, and cognitive control. Nature Communications, 12(1): 4942.
Polykretis, I.; and Danielescu, A. 2024. Mapless mobile robot navigation at the edge using self-supervised cognitive map learners. Frontiers in Robotics and AI, 11. Russell, S.; and Norvig, P. 2020. Artificial Intelligence: A Modern Approach. Pearson Series in Artificial Intelligence. Pearson, 4th edition. Schaul, T.; Horgan, D.; Gregor, K.; and Silver, D. 2015. Universal Value Function Approximators. In International Conference on Machine Learning (ICML), 1312–1320. Stachenfeld, K. L.; Botvinick, M. M.; and Gershman, S. J. 2017. The Hippocampus as a Predictive Map. Nature Neuroscience, 20(11): 1643–1653. Stöckl, C.; Yang, Y.; and Maass, W. 2024. Local PredictionLearning in High-Dimensional Spaces Enables Neural Networks to Plan. Nature Communications, 15: 2344. Sutton, R. S. 1988. Learning to Predict by the Methods of Temporal Differences. Machine Learning, 3(1): 9–44. Tamar, A.; Wu, Y.; Thomas, G.; Levine, S.; and Abbeel, P. 2016. Value Iteration Networks. In Advances in Neural Information Processing Systems (NeurIPS). Tolman, E. C. 1948. Cognitive Maps in Rats and Men. Psychological Review, 55(4): 189–208. Wang, T.; Torralba, A.; Isola, P.; and Zhang, A. 2023. Optimal Goal-Reaching Reinforcement Learning via Quasimetric Learning. In International Conference on Machine Learning (ICML). Wang, Y.; Li, W.; Faccio, F.; Wu, Q.; and Schmidhuber, J. 2024. Highway Value Iteration Networks. In International Conference on Machine Learning (ICML). Wang, Y.; Wu, Q.; Ashley, D. R.; Faccio, F.; Li, W.; Huang, C.; and Schmidhuber, J. 2025. Scaling Value Iteration Networks to 5000 Layers for Extreme Long-Term Planning. In International Conference on Machine Learning (ICML). Whittington, J. C. R.; Muller, T. H.; Mark, S.; Chen, G.; Barry, C.; Burgess, N.; and Behrens, T. E. J. 2020. The Tolman–Eichenbaum Machine: Unifying Space and Relational Memory through Generalization in the Hippocampal Formation. Cell, 183(5): 1249–1263. Wu, Y.; Tucker, G.; and Nachum, O. 2019. The Laplacian in RL: Learning Representations with Efficient Approximations. In International Conference on Learning Representations (ICLR). Yang, G.; Zhang, A.; Morcos, A. S.; Pineau, J.; Abbeel, P.; and Calandra, R. 2020. Plan2Vec: Unsupervised Representation Learning by Latent Plans. In Learning for Dynamics and Control (L4DC), 935–946. Yonetani, R.; Taniai, T.; Barekatain, M.; Nishimura, M.; and Kanezaki, A. 2021. Path Planning using Neural A* Search. In International Conference on Machine Learning (ICML), 12029–12039. Zhao, L.; Xu, H.; and Wong, L. L. S. 2023. Scaling up and Stabilizing Differentiable Planning with Implicit Differentiation. In International Conference on Learning Representations (ICLR).
Zuo, J.; He, Y.; Zhang, W.; Fang, F.; and Wu, S. 2026. From Representation to Action: A Unified Laplacian Framework for Spatial Representation and Path Planning. In International Conference on Machine Learning (ICML).