{"id":"e617438b-0c8d-4b5b-bd42-2f228a6a95b7","arxiv_id":"1908.03343","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A fully convolutional network trained on past path-planning examples predicts cost-to-go heuristics that reduce the number of cells explored by a greedy path planner in 2D grid worlds.","lead":"The paper trains a convolutional neural network to predict how far every cell in a grid map is from the goal, and uses that prediction as a guide for path-finding algorithms. It shows that the learned guide makes a simple path-finder expand far fewer cells than the standard straight-line guess, which could speed up robot navigation.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Sparse path-only supervision leaves off-path heuristic values unverified, so the headline search-cost reduction rests on an untested generalization assumption.","rationale":"I agree with the reader's weakest assumption. The empirical Table 2 reductions are impressive, but they are exactly the kind of end-to-end result that could hide a generalization failure: a few hundred labels per map cannot constrain 40k outputs, and the CNN's smoothness is an untested inductive bias. The proposed ablation isolates supervision density from architecture and evaluation. I do not see a separate flaw that would force a REJECT; the concern warrants the CONDITIONAL verdict the reader already gave.","tokens_in":9668,"tokens_out":13353,"duration_ms":162189,"concrete_test":"Retrain the Sparse model per environment type under two supervision regimes: the original one-A*-path-per-map mask, and a denser mask formed by the union of 20 independently sampled A* paths per map. Keep architecture, optimizer, and training length fixed, run 5 seeds per regime, and evaluate the greedy planner on the same 100 test maps with the fixed start/goal. If the denser-mask model gives statistically indistinguishable search cost and path quality, sparse-to-dense generalization is not the bottleneck; if it improves either metric by more than 10% (or reduces the spread across seeds), the original claim is conditional on unlabeled off-path cells being well covered by the training path distribution.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central quantitative claim is delivered by the Sparse model: eq. (4) is minimized with M(v)=1 only for vertices on the A* path, which is a tiny fraction of the roughly 40,000 valid cells in a 201x201 map. At test time, however, the greedy planner queries h(v) for arbitrary successors, most of which never received a label during training. If the CNN has not learned to extrapolate from one-dimensional path labels to the full two-dimensional cost-to-go field, those off-path values will be wrong and the reported one-to-two order reduction in expanded vertices will not transfer to new maps or to different start/goal pairs. The paper reports only end-to-end search costs and whole-map MAE learning curves; it does not report accuracy on off-path cells, and the fixed test start/goal (0,0)/(201,201) may align with the training-path distribution in an unexamined way. The Sparse+TD variant, which was intended to densify sparse targets, actually underperforms and is set aside, so the paper offers no corrective mechanism. This is the least secure link between the training objective and the headline result.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes learning search heuristics for grid-world path planning with fully convolutional neural networks. Given a binary obstacle map and a goal location, the network outputs a cost-to-go heuristic map over all vertices, and this map is used as the scoring function in a greedy best-first planner. Three training variants are introduced: dense regression to Backward Dijkstra cost-to-go values (BD), regression only to vertices on A* optimal paths (Sparse), and Sparse with additional temporal-difference Bellman backups from the network's own predictions (Sparse+TD). Experiments on seven 201x201 grid-world environment types from the Bhardwaj et al. dataset report the number of expanded vertices and path quality. The Sparse model reduces average expanded vertices by roughly one to two orders of magnitude relative to the Euclidean heuristic (e.g., Shifting gaps from 37,814 to 351 in Table 2), gives path quality close to optimal, and is faster end-to-end than A* with the Euclidean heuristic on the reported timing test. The paper also compares with SaIL and reports lower search costs for the learned convolutional heuristic. The presentation includes learning curves, path visualizations, and sample best/worst cases.","tokens_in":9819,"tokens_out":10528,"duration_ms":115387,"significance":"The central idea is simple but potentially useful: if a CNN can regress a usable cost-to-go field from cheap A* path labels, it removes the need for the dense Backward Dijkstra computation that dominates training-data generation in prior imitation-learning heuristics. The fully convolutional single-pass inference is a real advantage over per-state fully connected predictors such as SaIL, and the paper makes a concrete, falsifiable claim about large reduction in expanded vertices on seven benchmark maps. I credit the authors for reporting the Sparse+TD negative result instead of suppressing it, for comparing against an existing implementation on GitHub, and for including visualizations that show the jaggy-path limitation. At the same time, the reported evidence is preliminary: there are no variance or error bars, no code release, no explicit off-path accuracy measurement, and the test protocol uses a single start/goal pair. As a consequence, the strength of the main claim should be regarded as promising rather than established.","major_comments":[{"comment":"All quantitative comparisons are made on means over 100 test maps, but the tables give no standard deviations, confidence intervals, or significance tests. The text uses \"significant\" (Section 3.3) and \"no significant difference\" (Section 3.3) without supporting statistics. Given that the central claim is an order-of-magnitude reduction, the effect is likely robust, but differences such as Mazes Sparse (403) vs Sparse+TD (941) and the small path-quality gaps need distributional evidence. Please report per-map distributions or error bars and, where comparisons are made, a significance test or effect size.","section":"Section 3.3, Tables 1 and 2"},{"comment":"The Sparse model minimizes eq. (4) with M=1 only on A* path vertices, but the greedy planner queries the network at arbitrary successor vertices (eq. (3)). The paper offers no direct evaluation of off-path heuristic accuracy. Figure 3 reports only whole-map MAE and does not state the mask used for that MAE. This is a load-bearing generalization assumption: if the CNN has only learned to reconstruct values along one-dimensional paths, the reported reductions in expanded vertices may not transfer to different maps, different start/goal pairs, or to cells that the planner actually visits. I request an off-path accuracy analysis and a test with randomly sampled start/goal pairs.","section":"Section 2.2, eq. (4) and Section 3.3"},{"comment":"The evaluation uses one fixed start/goal pair, (0,0) to (201,201), for every test map, whereas training samples random start/goal pairs. Consequently, the headline numbers in Table 2 only demonstrate performance for a single query configuration per map. A learned heuristic for planning should be evaluated over a distribution of start/goal pairs; without this, the claim that the method \"significantly outperforms\" is not yet generalized. This is a correctness-risk concern with a concrete remedy: repeat the evaluation over multiple start/goal pairs and report the spread.","section":"Section 3.1 and Table 2"},{"comment":"The Sparse+TD variant was proposed specifically to compensate for sparse supervision, but Table 1 shows it is worse than Sparse in search cost on five of seven environments (e.g., Mazes 941 vs 403) and gives no consistent path-quality gain. The paper then drops it from the main comparison. The sentence \"no significant difference is observed\" is not supported by any statistical test, and no sensitivity analysis for lambda=0.001 or the three TD steps is provided. Either provide such analysis or explicitly frame Sparse+TD as an unsupported variant; as written, the contribution list overstates its role.","section":"Section 3.3 and Table 1"}],"minor_comments":[{"comment":"The multi-row header is difficult to parse; the grouping of planner and heuristic columns and the duplicated \"SaIL\" labels make it unclear which columns correspond to search cost versus path quality. Please reformat with clear column groups and a caption explaining the layout.","section":"Table 2"},{"comment":"The map is described as 201x201 and the fixed evaluation goal as (201,201); if vertices are indexed 0 to 200, (201,201) is outside the grid. Please clarify the coordinate convention.","section":"Section 3.1"},{"comment":"The training-time augmentation is described as random image translation producing 224x224 feature maps from 201x201 inputs; it should be stated whether this translation also shifts the goal coordinate and how the heuristic targets are transformed, since translation equivariance is not trivial for the distance-to-goal input channel.","section":"Section 3.2"},{"comment":"The timing comparison reports a single average for each method (e.g., 2.48 ms total for ours) with no repetitions or variance. Given that CNN inference runs on a GPU and the baselines are CPU-based, please state the measurement protocol and report error bars for the wall-clock comparison.","section":"Section 3.3, timing paragraph"},{"comment":"The selection of \"best\" and \"worst\" cases is not defined by a quantitative criterion, which makes the visual comparison anecdotal. Please specify how these cases were chosen.","section":"Figure 4"}],"recommendation":"major_revision","confidential_remarks":"The main risk is that the sparse-supervision result may not transfer beyond the fixed evaluation protocol. I would prioritize requiring off-path accuracy analysis and multi-start/goal evaluation. The lack of code release and the absence of variance reporting are also important for a learning-based methods paper. If the requested generalization tests confirm the Table 2 magnitudes, the contribution could be publishable; as it stands, the evidence is promising but not yet complete."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper does what it says, but the headline gain is smaller than the abstract implies, and the stats are thin.\n\nThe genuinely new bit is sparse target generation: training a fully convolutional network to regress a whole cost-to-go map using only A* path labels, then using that map as a heuristic for greedy search. That is a real step beyond Bhardwaj et al. 2017, which needed dense Dijkstra targets and DAgger. The experiments on the seven 2D grid worlds are consistent: learned heuristic cuts expanded vertices by one to two orders of magnitude versus Euclidean, with path quality close to optimal. The timing breakdown is honest: CNN inference 2.23ms plus 0.25ms planning, so end-to-end it is about 2.5x faster than A* Euclidean, not the dramatic gain the expansion numbers suggest.\n\nThe soft spots are real but manageable. The most important is exactly the one the stress-test flags: Sparse supervises only pixels on the A* path, and there is no direct measurement of accuracy on off-path cells. Whole-map MAE and end-to-end search cost are indirect evidence; the visualizations help, but a table with path-pixel vs off-path MAE would settle it. I don't think this is fatal—the CNN is fully convolutional with wide receptive fields, and training samples many random start/goal pairs per map, so generalization is plausible—but right now it is an assumption.\n\nThe other issues: Tables 1 and 2 report only means, with no error bars or significance tests. The phrase 'no significant difference' is asserted, not demonstrated. Sparse+TD, which was supposed to fix sparse supervision, underperforms Sparse on several environments and is dropped without explanation. That is a loose end. No code or data is released, and the evaluation uses fixed start/goal (0,0)/(201,201), consistent with prior work but limited.\n\nWho this is for: people working on learned heuristics or learning-for-planning. It is a solid incremental contribution, not a paradigm shift. It deserves peer review rather than desk rejection; a good referee would ask for error bars, off-path accuracy, a discussion of why TD didn't help, and hopefully code.","headline":"Solid incremental extension of learned heuristics with a real result, but sparse-supervision generalization is assumed rather than measured.","tokens_in":10379,"tokens_out":2919,"would_cite":true,"duration_ms":31985,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A fully convolutional network trained on optimal A* paths can learn search heuristics that cut expanded vertices by one to two orders of magnitude in seven 2D grid-world environments.","keywords":["path planning","search heuristic learning","fully convolutional network","cost-to-go","greedy search","A* algorithm","temporal difference learning","2D grid world navigation"],"falsifier":"On held-out maps from the same environment types, compute the exact cost-to-go with backward Dijkstra for cells that are not on any A* training path and compare them to the Sparse-trained network's predictions; if those off-path errors are large, the path-only supervision is not generalizing and expansion counts should approach Euclidean levels. A second test is to generate maps with obstacle layouts and trap placements outside the seven training environment types; if expansion counts return to Euclidean-scale values, the learned speedup is specific to the training distribution rather than a transferable heuristic.","tokens_in":9415,"feed_emoji":"🧭","tokens_out":8279,"duration_ms":78463,"temperature":0.7,"pith_summary":"Path planners such as A* rely on heuristic functions to focus the search, but hand-designed heuristics often fail when environments contain local traps. This paper proposes learning the heuristic directly: a fully convolutional network takes an obstacle map and a goal position as input and outputs a heuristic map of estimated cost-to-go for every cell in a single forward pass. The learned heuristic is then used inside a greedy search. On seven 2D grid-world environments, this reduces the average number of expanded vertices by one to two orders of magnitude relative to the Euclidean heuristic (for example, from 37,814 to 351 on Shifting gaps), while keeping path lengths close to optimal. The most practical training variant learns only from paths found by A*, avoiding the expensive full-map backward Dijkstra computation.","feed_headline":"Learned CNN heuristic cuts path search by two orders of magnitude","feed_subtitle":"A fully convolutional network predicts cost-to-go values, shrinking planner search by up to 100x.","key_machinery":"The central mechanism is a fully convolutional network with no fully connected layers, which maps an obstacle map, an obstacle-distance map, and a goal-distance map to an image of heuristic values, one estimated cost-to-go per grid cell, in a single forward pass. Because convolution is local, neighboring heuristic values tend to be spatially consistent, and because the network is fully convolutional, all vertices are handled simultaneously. Three training regimes are introduced: BD regresses to full cost-to-go values generated by backward Dijkstra; Sparse regresses only to cells along A* optimal paths using a masked squared-error loss; Sparse+TD adds an iterative Bellman-style value update, implemented as fixed convolution plus a minimum operation, to create denser training targets from the current prediction.","core_discovery":"The central claim is that hand-designed search heuristics can be replaced by learned convolutional heuristics. An environment with obstacles is treated as an image, and a fully convolutional network predicts a cost-to-go value for every graph vertex at once; a greedy planner using this heuristic map expands far fewer vertices than one using the Euclidean heuristic while producing near-optimal paths. The paper further claims that supervision from A* optimal paths alone (the Sparse method) is sufficient to train such heuristics, and that a temporal-difference variant can compensate for missing off-path supervision. In experiments, the learned heuristic reduces search cost from 37,814 to 351 expanded vertices on Shifting gaps, and total planning time from 6.10 ms for A* with Euclidean heuristic to 2.48 ms for greedy search with the learned heuristic, including CNN inference.","pith_inferences":["If the learned heuristic generalizes beyond the seven training environment types to unseen obstacle layouts, the same single-shot convolutional architecture could replace hand-crafted heuristics in on-board robot planners, not just 2D grids.","The success of Sparse suggests a testable hypothesis: optimal-path demonstrations alone contain enough information to regress a globally useful cost-to-go function, which connects this method to imitation learning and could be checked by measuring off-path prediction error against backward Dijkstra.","The temporal-difference variant injects Bellman consistency into the learned heuristic; one could push further by training with full value-iteration rollouts or by using the learned heuristic to initialize bidirectional or anytime search, which the paper does not test.","A stress test on maps with traps placed differently from the training distribution would clarify whether the speedup comes from memorizing environment types or from a transferable notion of obstacles and goals."],"forward_implications":["Using the learned heuristic in greedy search reduces average expanded vertices by one to two orders of magnitude on all seven tested environments, for example from 37,814 to 351 on Shifting gaps.","Because the Sparse variant needs only A* paths rather than full backward Dijkstra, training-data generation scales to larger maps and higher-dimensional planning problems.","Total planning time, including CNN inference, is lower than A* with the Euclidean heuristic on the tested hardware (2.48 ms versus 6.10 ms), indicating real-time feasibility.","Path quality stays close to optimal, for example 350 versus 311 on Shifting gaps, even though the greedy planner does not guarantee optimality; remaining jaggedness can be post-smoothed."],"supporting_citations":[{"why":"Defines A* and the additive score g+h that the paper's planners are built on, and supplies the notion of heuristic-guided search that learned heuristics replace.","marker":"Hart et al., 1968"},{"why":"Provides the seven 2D grid-world datasets, the fixed start/goal evaluation protocol, the learned-heuristic baseline SaIL, and the comparison numbers in Table 2.","marker":"Bhardwaj et al., 2017"},{"why":"Shows how to implement the iterative Bellman-style value update as a convolution with fixed kernels followed by a minimum operation, which the Sparse+TD training loss uses.","marker":"Tamar et al., 2017"},{"why":"Supplies dilated convolutions, which the encoder uses to widen spatial context while keeping full-resolution output.","marker":"Yu and Koltun, 2016"},{"why":"Motivates the input feature maps: obstacle-distance and goal-distance images are used as attractive and repulsive potential fields fed to the CNN.","marker":"Qureshi and Ayaz, 2017"},{"why":"DAgger is the interactive imitation-learning sampling technique used by the SaIL baseline, which the paper's Sparse method avoids by learning from A* paths only.","marker":"Ross et al., 2010; Ross and Bagnell, 2014"},{"why":"Adam is the optimizer used to train the convolutional heuristic networks.","marker":"Kingma and Ba, 2014"},{"why":"Hybrid A* is the non-holonomic planner cited as the motivation for learned heuristics that combine obstacle and kinematic costs.","marker":"Montemerlo et al., 2008"}],"fun_headline_variants":["Learned heuristic image cuts path search to 1%","CNN-learned cost-to-go replaces handcrafted heuristics","From A* to greedy: CNN heuristic trims planner cost 100x","Fully convolutional heuristic maps obstacles to fast paths","Robots learn pathfinding heuristics from obstacle images"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The central assumption is that a network trained with cost-to-go labels only on cells along A* optimal paths will produce accurate heuristic values for every other cell in the map at test time, because the greedy planner depends on those off-path predictions to avoid expanding many cells.","fun_headline_variants_meta":{"raw":{"variants":["Learned heuristic image cuts path search to 1%","CNN-learned cost-to-go replaces handcrafted heuristics","From A* to greedy: CNN heuristic trims planner cost 100x","Fully convolutional heuristic maps obstacles to fast paths","Robots learn pathfinding heuristics from obstacle images"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000271,"raw_usage":{"total_tokens":1625,"prompt_tokens":936,"completion_tokens":689,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":552,"completion_tokens_details":{"reasoning_tokens":606}},"tokens_in":552,"tokens_out":689,"duration_ms":7317,"temperature":1.0,"reasoning_tokens":606,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:16:16.287187+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On held-out maps from the same environment types, compute the exact cost-to-go with backward Dijkstra for cells that are not on any A* training path and compare them to the Sparse-trained network's predictions; if those off-path errors are large, the path-only supervision is not generalizing and expansion counts should approach Euclidean levels. A second test is to generate maps with obstacle layouts and trap placements outside the seven training environment types; if expansion counts return to Euclidean-scale values, the learned speedup is specific to the training distribution rather than a transferable heuristic.","supporting_citations":[{"cited_title":"Learning heuristic search via imitation","cited_arxiv_id":null,"evidence_quote":"Provides the seven 2D grid-world datasets, the fixed start/goal evaluation protocol, the learned-heuristic baseline SaIL, and the comparison numbers in Table 2."},{"cited_title":"Value iteration networks","cited_arxiv_id":null,"evidence_quote":"Shows how to implement the iterative Bellman-style value update as a convolution with fixed kernels followed by a minimum operation, which the Sparse+TD training loss uses."},{"cited_title":"Multi-Scale Context Aggregation by Dilated Convolutions","cited_arxiv_id":null,"evidence_quote":"Supplies dilated convolutions, which the encoder uses to widen spatial context while keeping full-resolution output."},{"cited_title":"Potential Functions based Sampling Heuristic For Optimal Path Planning","cited_arxiv_id":"1704.00264","evidence_quote":"Motivates the input feature maps: obstacle-distance and goal-distance images are used as attractive and repulsive potential fields fed to the CNN."},{"cited_title":"Junior: The stanford entry in the urban challenge","cited_arxiv_id":null,"evidence_quote":"Hybrid A* is the non-holonomic planner cited as the motivation for learned heuristics that combine obstacle and kinematic costs."}],"review_version":1}