REVIEW 4 major objections 5 minor 28 references
Ground-Aware Octree-A* Hybrid Path Planning for Memory-Efficient 3D Navigation of Ground Vehicles
T0 review · 4 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read An octree-compressed A* planner produces near-optimal 3D ground-robot paths while using roughly 92 percent less computation and up to 95 percent less memory than uniform-grid A*, according to the paper's benchmarks.
desk verdict Octree+A* gives real memory/time savings, but the optimality claim is contradicted by the paper's own conclusion and the adjacency construction can cut through occupied space. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the octree-compressed grid, in which obstacle-free or start/goal regions are merged into cubic leaf nodes of varying size. Two procedures make the search work on this irregular graph: a coordinate-driven descent that returns the leaf node containing any 3D point, and a neighbor search that samples candidate coordinates at half the leaf side length plus the minimum grid resolution and keeps only obstacle-free leaf neighbors. The modified A* cost g(n)+h(n)+alpha*r(n) ties the search to the ground: the penalty r(n), vertical distance from a node center to the nearest surface, makes ground-level and low traversable-obstacle routes cheaper than high detours.
What would settle it
Run Octree-A* and uniform-grid A* on a batch of randomly generated or dense real terrain maps at the same 128^3 resolution. If any octree result is meaningfully longer (say >5%) than the grid result, or if the coarse graph misses a feasible ground route that grid A* finds, the near-optimality claim is refuted. A cheaper check: find one node where the Manhattan heuristic overestimates the true remaining cost once the alpha*r penalty is active—that single violation would break A*'s optimality guarantee.
Extended reading notes
Core claim
The central claim is that the optimality property of A* survives a coarse octree representation. The planner minimizes g(n)+h(n)+alpha*r(n), where g is distance traveled, h is Manhattan distance to the goal, and r is the vertical distance from the node center to the nearest surface; alpha weights how strongly the robot should stay near the ground. Algorithms 1 and 2 map any 3D coordinate to the leaf node containing it and find valid obstacle-free neighbor leaf nodes by sampling center offsets at half the leaf side length plus the grid resolution. Running A* on the resulting coarse graph, the paper reports 92.63% and 91.18% reductions in computation time, 95.50% and 92.73% reductions in memor
Load-bearing premise
The load-bearing premise is that the coarse octree graph of leaf-node centers still contains a route essentially as short as the one found on the full-resolution grid, and that the Manhattan heuristic stays admissible when the height penalty is added; the paper tests this on only two hand-built 128^3 scenarios.
Editorial extensions
If this is right
- On a 128x128x128 map, the planner completes in 68-661 ms including octree construction, versus 928-7495 ms for uniform-grid A*, so onboard real-time planning becomes feasible on modest CPUs.
- Memory use drops to below 10% of the uniform grid's footprint, so a robot can hold a larger or higher-resolution map in the same RAM.
- Compression is strongest where obstacles are sparse: Scenario 1 (fewer obstacles) showed the larger savings, so the benefit grows in open terrain.
- The height penalty turns traversable obstacles into path options instead of pure avoidance, which is what lets the planner find a shorter route in the obstacle-leveraging scenario.
- Post-processing such as spline fitting, suggested by the paper, could shorten and smooth the center-to-center leaf-node trajectories.
Reading between the lines
- Editorial inference: the 'optimal path' claim is best read as optimality on the compressed octree graph, not on the original grid. The paper does not prove that every grid-optimal route survives compression, so randomized terrain tests are needed to measure how often the compressed graph omits the best route.
- Editorial inference: the savings should shrink in cluttered terrain, because occupied cells force octree subdivision toward grid resolution; the reported 92-95% figures are likely upper bounds for open environments.
- Editorial inference: alpha is a single scalar with no robot-specific meaning in the paper. Tuning it per robot mobility model (step height, traction) would make the cost function more physically grounded.
- Editorial inference: the neighbor search using leaf center offsets plus grid resolution only checks one sample per candidate direction, so diagonal or off-axis passages may be missed; a denser sampling scheme would trade speed for completeness.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes Octree-A*, a path-planning method that compresses a uniform 3D grid into an octree and runs a modified A* over octree leaf nodes. The cost function (Eq. 1) adds a height penalty α·r(n) to encourage ground-level paths. Neighbor leaf nodes are found by Algorithm 2, which probes coordinates at half the leaf side length plus the minimum grid resolution. Benchmarks on two 128×128×128 hand-built scenarios report 92.63% and 91.18% reductions in computation time, 95.50% and 92.73% reductions in memory, and path lengths +0.41% and −0.80% relative to uniform-grid A*. The abstract claims the octree representation 'ensures an optimal path' while reducing resource usage.
Significance. If the claims are sound, the memory and time reductions would be practically valuable for deploying 3D path planning on computationally limited ground robots. A clear strength is that the resource-usage benchmark is measured against an external uniform-grid A* baseline, so the headline savings are not circular. The two scenarios also show that path lengths are within about 1% of the baseline in those cases. However, the central optimality claim is not supported: the paper neither proves that the compressed graph preserves the optimal route nor that the chosen heuristic is admissible under the modified cost, and Algorithm 2's neighbor test can create edges that pass through occupied space. The resource savings may survive a corrected treatment, but the optimality guarantee as stated is likely false.
major comments (4)
- [Section 3.3, Algorithm 2; Section 5] The adjacency construction does not verify that the straight segment between the two leaf centers is collision-free. Algorithm 2 only probes points at ds+r and accepts a neighbor leaf if the leaf containing that coordinate is obstacle-free. The line between two obstacle-free leaves can cross a thin occupied leaf that the probe skips, so the planned path can pass through an obstacle. This is not merely a missing optimality proof; the derived graph can contain infeasible edges. The abstract's claim that Octree-A* 'ensures an optimal path' is therefore unsupported, and Section 5 itself concedes that center-to-center trajectories 'may not be shortest for ground vehicles.' The algorithm should either collision-check every edge (e.g., by ray traversal through the octree) or be explicitly reframed as a heuristic, near-optimal method.
- [Section 4, Table 1; Section 5] The empirical support for near-optimality is limited to two hand-built scenarios. Table 1 reports path-length differences of +0.41% and −0.80% in those two maps, but this is insufficient to establish that the octree graph preserves near-optimal paths across obstacle densities, leaf-size distributions, or start/goal placements. The paper should test on several randomized or systematically varied terrains, compare against a full-resolution grid A* as ground truth, and report the distribution of path-length ratios. Without this, the claim of 'comparable' path lengths is anecdotal.
- [Section 3.2, Eq. (1); Section 4] The optimality argument for A* is incomplete. Section 4 states that g(n) accumulates 'the distances between the midpoints of adjacent nodes,' but the paper does not specify whether this is Euclidean, Manhattan, or another metric. If edges are straight center-to-center segments, a Manhattan heuristic h(n) can overestimate the remaining Euclidean cost, violating the admissibility condition needed for A* optimality. In addition, the extra α·r(n) term changes the optimization objective, so even an admissible heuristic for the underlying distance does not automatically make the weighted cost admissible. The paper should define the exact edge cost, state the heuristic, and prove or empirically verify admissibility; otherwise the statement in Section 5 that the method does not compromise 'the characteristics of A*' is not justified.
- [Section 3.2, Eq. (1); Section 4] The physical model behind the height penalty is under-specified. r(n) is defined as 'the vertical distance from the center of node n to the nearest surface,' but what constitutes a surface, how traversable obstacles are distinguished from impassable ones, and how the weight α is chosen are not stated. α is a free parameter and its value is never reported, which affects reproducibility. The absence of a robot mobility model also makes it unclear whether a path produced by the soft penalty is actually executable by a UGV or legged robot. At minimum, the authors should give a formal definition of traversable surface and report the α value used in the benchmarks.
minor comments (5)
- [Section 1] Typo in the introduction: 'Section 4e presents' should read 'Section 4 presents.'
- [Section 4] The grid cell dimensions are given as '0.5m×0.5m×0.5cm'; this is likely a typo for 0.5m×0.5m×0.5m or 0.5m×0.5m×? Please correct.
- [Section 3.3, Algorithm 2] Several symbols are not defined: the variable ds is given as 'ds←s/2∈N L' with an unclear type; ComputeAdjacents(x,y,z,ds+r) is explained only textually; isValid is not defined; and the child-index symbol '⟩' in Algorithm 1 is nonstandard. Please define all notation precisely.
- [Section 3.3, Algorithm 1] The modulo update '(x,y,z)←(x mod s, y mod s, z mod s)' may be ambiguous if coordinates are signed or if s is a float. Please clarify the coordinate system and the intended arithmetic.
- [Section 5] The conclusion says 'the trajectories may not be shortest for ground vehicles' but the abstract claims 'ensures an optimal path.' These statements are contradictory and should be harmonized.
Circularity Check
No circularity: the efficiency benchmark is external and the optimality claim is an A* property applied to an independently defined graph; the main risks are correctness of the adjacency construction and overclaiming, not circular reasoning.
full rationale
The paper's derivation chain is not circular. Eq. (1) defines a cost function g+h+alpha*r; A* is then run on the octree graph whose edges are defined by Algorithm 2. The claim that A* returns a minimum-cost path is a standard, externally grounded property of A* under an admissible heuristic, not a conclusion that reduces to the paper's own inputs. The octree graph and the cost function are defined before any path is computed, and the benchmark comparisons in Table 1 measure Octree-A* against uniform-grid A* on two scenarios; the path lengths and reductions are empirical outputs, not fitted parameters disguised as predictions. The height penalty alpha is a design weight, not calibrated to the benchmark outcomes. The only self-citations (refs [5], [7]) appear in related-work context and do not carry any load-bearing argument. The conclusion's admission that center-to-center trajectories 'may not be shortest for ground vehicles' contradicts the abstract's phrasing but is a correctness/validity caveat, not evidence of circularity. The skeptic's concern that Algorithm 2 may create edges through occupied space is a legitimate feasibility gap, but that is a soundness error, not a circular derivation.
Assumptions & free parameters
free parameters (1)
- alpha (penalty weight in Eq. 1) =
not disclosed
assumptions (4)
- domain assumption Manhattan distance remains an admissible heuristic for the modified cost g(n)+h(n)+alpha*r(n) and the chosen neighbor connectivity, so A* retains its optimality guarantee.
- ad hoc to paper The compressed octree graph (leaf-node centers connected via Algorithm 2) contains a path whose cost is within about 1% of the uniform-grid optimum for arbitrary obstacle layouts.
- domain assumption Straight center-to-center segments between neighboring leaf nodes are collision-free when both endpoints are valid nodes.
- ad hoc to paper Traversability of obstacles is adequately captured by the soft height penalty alpha*r(n) plus valid-surface membership, without a robot mobility model.
Cite this review
Pith. "Pith review of Ground-Aware Octree-A* Hybrid Path Planning for Memory-Efficient 3D Navigation of Ground Vehicles." pith.science (2026). https://pith.science/paper/KOQHLA4R
@misc{pith2026250904950,
author = {Pith},
title = {Pith review of: Ground-Aware Octree-A* Hybrid Path Planning for Memory-Efficient 3D Navigation of Ground Vehicles},
year = {2026},
howpublished = {\url{https://pith.science/paper/KOQHLA4R}},
note = {Machine review of arXiv:2509.04950}
}
read the original abstract
In this paper, we propose a 3D path planning method that integrates the A* algorithm with the octree structure. Unmanned Ground Vehicles (UGVs) and legged robots have been extensively studied, enabling locomotion across a variety of terrains. Advances in mobility have enabled obstacles to be regarded not only as hindrances to be avoided, but also as navigational aids when beneficial. A modified 3D A* algorithm generates an optimal path by leveraging obstacles during the planning process. By incorporating a height-based penalty into the cost function, the algorithm enables the use of traversable obstacles to aid locomotion while avoiding those that are impassable, resulting in more efficient and realistic path generation. The octree-based 3D grid map achieves compression by merging high-resolution nodes into larger blocks, especially in obstacle-free or sparsely populated areas. This reduces the number of nodes explored by the A* algorithm, thereby improving computational efficiency and memory usage, and supporting real-time path planning in practical environments. Benchmark results demonstrate that the use of octree structure ensures an optimal path while significantly reducing memory usage and computation time.
Figures
Reference graph
Works this paper leans on
-
[1]
W.-S. Park, M.-S. Park, and H.-W. Yang, “The op- timal design scheme of an sugv for surveillance and reconnaissance missions in urban and rough ter- rain,”International Journal of Control, Automation and Systems, vol. 10, pp. 992–999, 2012
work page 2012
-
[2]
Y . Tang, X. Xu, L. Zhang, G. Chen, K. Luo, and L. Yan, “Structure design and configuration opti- mization of the reconfigurable deformed tracked wheel based on terramechanics characteristics,” Journal of Intelligent & Robotic Systems, vol. 108, no. 1, p. 7, 2023
work page 2023
-
[3]
Highly dynamic quadruped locomotion via whole- body impulse control and model predictive control,
D. Kim, J. Di Carlo, B. Katz, G. Bledt, and S. Kim, “Highly dynamic quadruped locomotion via whole- body impulse control and model predictive control,” arXiv preprint arXiv:1909.06586, 2019
arXiv 1909
-
[4]
Perceptive locomotion through nonlin- ear model-predictive control,
R. Grandia, F. Jenelten, S. Yang, F. Farshidian, and M. Hutter, “Perceptive locomotion through nonlin- ear model-predictive control,”IEEE Transactions on Robotics, vol. 39, no. 5, pp. 3402–3421, 2023
work page 2023
-
[5]
J. Kang, H.-B. Kim, B.-I. Ham, and K.-S. Kim, “External force adaptive control in legged robots through footstep optimization and disturbance feed- back,”IEEE Access, 2024
work page 2024
-
[6]
Development of quadruped walking robots: A review,
P. Biswal and P. K. Mohanty, “Development of quadruped walking robots: A review,”Ain Shams Engineering Journal, vol. 12, no. 2, pp. 2017–2031, 2021
work page 2017
-
[7]
Development of re- mote piping inspection system with dual-mode lo- comotion quadruped robot,
H.-B. Kim, C. Kim, B.-I. Ham, J. Kang, M. Choi, K.-H. Choi, and K.-S. Kim, “Development of re- mote piping inspection system with dual-mode lo- comotion quadruped robot,” inInternational Con- ference on Robot Intelligence Technology and Ap- plications, pp. 307–319, Springer, 2024
work page 2024
-
[8]
Z. Zhuang, Z. Fu, J. Wang, C. Atkeson, S. Schwert- feger, C. Finn, and H. Zhao, “Robot parkour learn- ing,”arXiv preprint arXiv:2309.05665, 2023
arXiv 2023
Show all 28 references
-
[9]
Di- jkstra’s and a-star in finding the shortest path: a tu- torial,
A. Candra, M. A. Budiman, and K. Hartanto, “Di- jkstra’s and a-star in finding the shortest path: a tu- torial,” in2020 International Conference on Data Science, Artificial Intelligence, and Business Ana- lytics (DATABIA), pp. 28–32, IEEE, 2020
2020
-
[10]
Path planning using an improved a-star algorithm,
C. Ju, Q. Luo, and X. Yan, “Path planning using an improved a-star algorithm,” in2020 11th interna- tional conference on prognostics and system health management (PHM-2020 Jinan), pp. 23–26, IEEE, 2020
2020
-
[11]
Sampling-based algo- rithms for optimal motion planning,
S. Karaman and E. Frazzoli, “Sampling-based algo- rithms for optimal motion planning,”The interna- tional journal of robotics research, vol. 30, no. 7, pp. 846–894, 2011
2011
-
[12]
Revisiting the asymptotic optimal- ity of rrt,
K. Solovey, L. Janson, E. Schmerling, E. Frazzoli, and M. Pavone, “Revisiting the asymptotic optimal- ity of rrt,” in2020 IEEE international conference on robotics and automation (ICRA), pp. 2189–2195, IEEE, 2020
2020
-
[13]
A comparison of a* and rrt* al- gorithms with dynamic and real time constraint sce- narios for mobile robots,
J. Braun, T. Brito, J. Lima, P. G. d. Costa, P. Costa, and A. Y . Nakano, “A comparison of a* and rrt* al- gorithms with dynamic and real time constraint sce- narios for mobile robots,” in9th International Con- ference on Simulation and Modeling Methodolo- gies, Technologies a...
2019
-
[14]
Narrow pas- sage rrt*: a new variant of rrt,
A. Belaid, B. Mendil, and A. Djenadi, “Narrow pas- sage rrt*: a new variant of rrt,”International journal of computational vision and robotics, vol. 12, no. 1, pp. 85–100, 2022
2022
-
[15]
Adaptive informed rrt*: Asymptotically optimal path planning with ellipti- cal sampling pools in narrow passages,
Y . Huang and H.-H. Lee, “Adaptive informed rrt*: Asymptotically optimal path planning with ellipti- cal sampling pools in narrow passages,”Interna- tional Journal of Control, Automation and Systems, vol. 22, no. 1, pp. 241–251, 2024
2024
-
[16]
Improved rrt global path planning algorithm based on bridge test,
H. Tu, Y . Deng, Q. Li, M. Song, and X. Zheng, “Improved rrt global path planning algorithm based on bridge test,”Robotics and Autonomous Systems, vol. 171, p. 104570, 2024
2024
-
[17]
Three- dimensional path planning for autonomous under- water vehicles based on a whale optimization al- gorithm,
Z. Yan, J. Zhang, J. Zeng, and J. Tang, “Three- dimensional path planning for autonomous under- water vehicles based on a whale optimization al- gorithm,”Ocean engineering, vol. 250, p. 111070, 2022
2022
-
[18]
Three-dimensional path planning for auvs in ocean currents environment based on an improved compression factor particle swarm opti- mization algorithm,
X. Li and S. Yu, “Three-dimensional path planning for auvs in ocean currents environment based on an improved compression factor particle swarm opti- mization algorithm,”Ocean Engineering, vol. 280, p. 114610, 2023
2023
-
[19]
Adapted-rrt: novel hybrid method to solve three-dimensional path planning problem using sampling and metaheuristic-based algorithms,
F. Kiani, A. Seyyedabbasi, R. Aliyev, M. U. Gulle, H. Basyildiz, and M. A. Shah, “Adapted-rrt: novel hybrid method to solve three-dimensional path planning problem using sampling and metaheuristic-based algorithms,”Neural Comput- ing and Applications, vol. 33, no. 22, pp. 1556...
2021
-
[20]
Efficient motion planning based on kinodynamic model for quadruped robots following persons in confined spaces,
Z. Zhang, J. Yan, X. Kong, G. Zhai, and Y . Liu, “Efficient motion planning based on kinodynamic model for quadruped robots following persons in confined spaces,”IEEE/ASME Transactions on Mechatronics, vol. 26, no. 4, pp. 1997–2006, 2021
1997
-
[21]
Path planning of quadrupedal robot based on improved rrt-connect algorithm,
X. Xu, P. Li, J. Zhou, and W. Deng, “Path planning of quadrupedal robot based on improved rrt-connect algorithm,”Sensors, vol. 25, no. 8, p. 2558, 2025
2025
-
[22]
Safe and robust motion planning for autonomous navigation of quadruped robots in cluttered environments,
H. Liu and Q. Yuan, “Safe and robust motion planning for autonomous navigation of quadruped robots in cluttered environments,”IEEE Access, 2024
2024
-
[23]
Path planning based on adfa* algorithm for quadruped robot,
L. Zhe, L. Yibin, R. Xuewen, and Z. Hui, “Path planning based on adfa* algorithm for quadruped robot,”IEEE Access, vol. 7, pp. 111095–111101, 2019
2019
-
[24]
A quadruped robot obstacle avoidance and person- nel following strategy based on ultra-wideband and three-dimensional laser radar,
Z. Li, B. Li, Q. Liang, W. Liu, L. Hou, and X. Rong, “A quadruped robot obstacle avoidance and person- nel following strategy based on ultra-wideband and three-dimensional laser radar,”International Jour- nal of Advanced Robotic Systems, vol. 19, no. 4, p. 17298806221114705, 2022
2022
-
[25]
Grid map construction and terrain prediction for quadruped robot based on c-terrain path,
Z. Li, Y . Li, X. Rong, and H. Zhang, “Grid map construction and terrain prediction for quadruped robot based on c-terrain path,”IEEE Access, vol. 8, pp. 56572–56580, 2020
2020
-
[26]
Research on path planning of quadruped robot based on globally mapping localization,
Y . Liu, L. Jiang, F. Zou, B. Xing, Z. Wang, and B. Su, “Research on path planning of quadruped robot based on globally mapping localization,” in 2020 3rd International Conference on Unmanned Systems (ICUS), pp. 346–351, IEEE, 2020
2020
-
[27]
Anymal parkour: Learning agile navigation for quadrupedal robots,
D. Hoeller, N. Rudin, D. Sako, and M. Hut- ter, “Anymal parkour: Learning agile navigation for quadrupedal robots,”Science Robotics, vol. 9, no. 88, p. eadi7566, 2024
2024
-
[28]
Octree-based point- cloud compression.,
R. Schnabel and R. Klein, “Octree-based point- cloud compression.,”PBG@ SIGGRAPH, vol. 3, no. 3, 2006
2006
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.