Source-linked AI summary
Compact Bellman-Grounded Cognitive Maps for Cost-Aware Navigation
Yuzhe Han, Mingkun Xu, Yujie Wu
TL;DR
Existing cognitive-map models support reusable guidance but do not explicitly represent additive heterogeneous movement costs, while scalable memory remains a challenge. BCM addresses this with a self-supervised Bellman-grounded objective and compact, goal-independent representation; on weighted grids, it retains strong performance and encodes route-cost structure without per-goal retraining.
Problem
Existing cognitive-map models provide reusable guidance but lack inherent representation of heterogeneous movement costs, which can make geometrically plausible routes substantially more expensive.
Method
BCM learns goal-conditioned transition-ranking scores from local edge costs using a Bellman-grounded objective built from sampled transitions, with a compact goal-independent representation for online multi-goal planning.
Results
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.
Takeaways & Limitations
Additive route-cost structure can be encoded in a compact, reusable cognitive-map representation, allowing changing goals without rebuilding the map or per-goal retraining.
Takeaways & Limitations
BCM targets fixed, known, coordinate-structured weighted graphs and requires updating or retraining after substantial topology or edge-cost changes; Gap rises to 12.4% at N = 3600 under wide costs.
Abstract
from arXiv · showhide
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.
Introduction
Existing cognitive maps reuse representations across goals but generally omit additive heterogeneous movement costs and face scaling challenges. BCM addresses both gaps with Bellman-grounded cost awareness and a compact, goal-independent representation.
- Existing cognitive-map approaches capture occupancy, connectivity, or action-consistent direction but do not inherently represent actual heterogeneous movement costs.
- Full-rank spectral maps require quadratic storage, while CML-style learners scale with enumerated state and action spaces.
- BCM grounds local scores in additive edge costs using a self-supervised Bellman objective built from graph transitions without shortest-path supervision.
- BCM supports online planning across changing goals from a shared representation, with coordinate-dependent parameter growth of O(N) on two-dimensional grids.
- Across weighted-grid layouts through N = 1600, BCM maintains full success and approximately 5% mean Gap, versus about 45% for the evaluated connectivity-based spectral map.
Method
BCM encodes coordinates and local transitions, trains their scores with Bellman grounding, and performs online visited-aware greedy readout. Its interaction-based coordinate encoding preserves compact parameter growth while recovering row–column structure.
- Architecture: A node encoder maps coordinates to embeddings, and a transition encoder maps embedding differences to transition representations.
- Bellman-Grounded Objective: The Bellman-grounded objective combines immediate edge cost with the best downstream score and uses sampled transitions without shortest-path or optimal-action labels.
- Online Greedy Readout: The learned goal-independent representation supports changing goals without rebuilding or retraining the map.
- Online Greedy Readout: A visited-aware greedy rule prefers unvisited neighbors and permits revisits only when no unvisited action remains, adding limited path memory.
- Compact Coordinate Encoding: Interaction-based coordinate encoding captures row–column combinations while preserving O(N) input-layer growth and outperforms additive k-hot encoding.
Experiments
Experiments evaluate BCM on weighted grid layouts, varying edge-cost heterogeneity, obstacle geometry, graph size, coordinate encoding, and readout memory. BCM generally preserves full success with low Gap and compact growth, but accuracy declines at the largest tested scale and the method lacks exact-search guarantees.
- Experimental setup: BCM is evaluated on fixed weighted 2D grids with U-shaped, central-block, and wall-with-gap layouts under uniform, mild, and wide edge costs.Scaling experiments use N ∈ {400, 900, 1600, 3600} on the U-shaped layout with wide costs.
- Weighted path quality: 47.2% Gap is reached by binary-Laplacian EigenAgent under wide costs, whereas BCM remains at 5.1% on the same U-shaped graph.Both methods reach every goal in this comparison; APF solves only 82% of pairs and reaches 42.3% Gap on solved wide-cost pairs.
- Weighted path quality: 44.6%–47.0% Gap is reached by EigenAgent across layouts under wide costs, while BCM maintains full success with Gap below 5.9%.APF success varies from 0.98 on the central-block layout to 0.68 on the wall-with-gap layout.
- Scalability and storage: 0.734 MB to 0.755 MB is BCM’s representation growth from N = 400 to N = 3600, compared with 0.613 MB to 49.751 MB for EigenAgent and 1.920 MB to 155.520 MB for APSP.BCM’s transition encoder contributes a fixed 0.724 MB, while coordinate-dependent parameters grow as O(N).
- Scalability and storage: 5.8% Gap with a 0.744 MB representation is achieved by BCM at N = 1600, compared with 45.2% Gap and 9.824 MB for EigenAgent.APSP attains exact routing with 30.720 MB at this size.
- Limitations: 12.4% Gap at N = 3600 marks BCM’s reduced accuracy at the largest tested scale, and substantial topology or edge-cost changes require updating or retraining.BCM targets repeated planning on fixed, known, coordinate-structured weighted graphs and is less accurate on denser maze layouts.
- Visited-aware readout: 1.00 wide-cost success rate is reached by adding visited-aware readout to the interaction model, raising SR from 0.84 without changing learned parameters.wSPL rises from 0.799 to 0.950 while successful-route weighted-cost efficiency remains approximately 0.95; the rule uses a temporary length-N visited mask.
Related Work
Prior cognitive-map and learned-planning approaches reuse representations across goals, but they encode different quantities and often retain search or storage costs. BCM is positioned against these reusable, spectral, and exact-search alternatives.
- Cognitive maps support flexible routing by storing reusable representations of environments.
- Successor representations encode policy-conditioned future occupancy, while quasimetric and universal-value methods support goal reaching across changing goals.
- Spectral approaches organize states through graph connectivity, whereas differentiable planners embed value-iteration-like computation in learned architectures.
- Dijkstra and A* provide exact per-query planning, while APSP precomputes exact pairwise answers with quadratic storage and constant-time next-hop lookup.
- Learned heuristics reduce search effort but generally do not preserve the same admissibility-based guarantees as exact methods.
Discussion
The discussion presents BCM as a minimal, modular planner whose shared Bellman-grounded objective supports compact coordinate-based representations and low empirical Gap. Its current readout and encoding remain replaceable, especially because memoryless rollouts and limited structural cues contribute to remaining failures.
- BCM combines coordinate encoding, transition encoding, and local readout under one Bellman-grounded training objective.
- Factorized coordinate binding distinguishes node conjunctions and may extend to other factorized state representations, though experiments validate it only on 2D grids.
- BCM’s method-specific representation increases from 0.734 MB at N = 400 to 0.755 MB at N = 3600, while encoding weighted route-cost structure.
- A visited-aware readout improves success without retraining by prioritizing unvisited neighbors and allowing fallback when none remain.
- BCM is presented as a minimal modular starting point whose components can be strengthened or replaced while retaining the cost-grounded representation.
Conclusion
BCM supports repeated planning on fixed, known weighted graphs by encoding additive route costs in a compact, reusable cognitive-map representation. It maintains strong performance across tested weighted grids while allowing changing goals without rebuilding or retraining the map.
- BCM learns goal-conditioned transition-ranking scores from local heterogeneous edge costs through a Bellman-grounded objective and uses visited-aware greedy readout.
- Full success and approximately 5% mean Gap are maintained through N = 1600 under the widest weight range, versus about 45% for a representative connectivity-based spectral map.
- The coordinate-dependent parameter count grows as O(N) on two-dimensional grids, although Gap rises to about 12% at N = 3600.
- Because the 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
The work studies graph-planning algorithms in synthetic fixed environments without human-subject, private, or deployed decision-system data. Real-world deployment would require separate evaluation of safety constraints, uncertainty, and failure recovery.
- The study uses synthetic fixed environments and does not involve human-subject data, private data, or deployed decision systems.
- Potential risks are limited to downstream real-world use, where safety constraints, uncertainty, and failure recovery should be evaluated separately before deployment.