pith. sign in

arxiv: 2607.01454 · v1 · pith:O6UMJWKXnew · submitted 2026-07-01 · 💻 cs.RO

SE(2) Navigation Mesh

Shuyang Shi , Kaixian Qu , Changan Chen , Ines Kast , Yuntao Ma , Marco Hutter This is my paper

Pith reviewed 2026-07-03 19:55 UTC · model grok-4.3

classification 💻 cs.RO
keywords SE(2) Navigation Meshyaw-dependent traversabilitynavigation meshpath planningground robotsfootprint masksonline mappingA* planning
0
0 comments X

The pith

SE(2) Navigation Mesh encodes yaw-dependent traversability via footprint masks to support non-circular ground robots in tight spaces.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Classical navigation meshes treat traversability as independent of heading, which fails for robots whose shape changes effective clearance with yaw. The paper introduces a layered polygonal mesh that evaluates each candidate region with a yaw-specific footprint mask and links the layers with explicit translation and rotation edges. This representation feeds an A*-String Pulling-A* planner that jointly optimizes position and heading. The resulting system reports over 50 percent more usable area than standard meshes in simulation and real-time performance on physical robots. A reader cares because many tracked, legged, or rectangular platforms are currently forced into overly conservative paths or outright blocked by the yaw-invariance assumption.

Core claim

We propose SE(2) Navigation Mesh (SE(2) NavMesh), a polygonal representation of traversable regions that encodes yaw-dependent traversability. Our method evaluates traversability using footprint masks and constructs a graph over yaw-specific layers with explicit translational and rotational connectivity. Grounded in this representation, we develop an A*-String Pulling-A* (ASA) pathfinding strategy that hierarchically optimizes robot position and heading. We also present an online method that incrementally updates the SE(2) NavMesh from streaming point clouds during concurrent geometry reconstruction.

What carries the argument

The SE(2) Navigation Mesh: a yaw-layered polygonal abstraction whose edges and faces are labeled by footprint-mask traversability and connected by both translational and rotational transitions.

If this is right

  • In simulation the representation captures over 50 percent more traversable area than yaw-invariant meshes.
  • The combined SE(2) NavMesh plus ASA planner consistently beats sampling-based baselines inside constrained environments.
  • An incremental online builder maintains the mesh in real time from streaming point clouds while the robot moves.
  • Real-world trials on a physical platform confirm successful navigation across multiple indoor and outdoor settings.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same layered-mask idea could be applied to 3-D aerial vehicles whose clearance also varies with pitch and roll.
  • Replacing static footprint masks with learned or sensor-driven masks would test whether the representation remains useful under heavy occlusion or deformable terrain.
  • The explicit rotational edges already present in the graph offer a natural substrate for adding dynamic obstacle avoidance that accounts for heading.

Load-bearing premise

Footprint masks evaluated on the underlying geometry provide a sufficient and accurate model of yaw-dependent traversability without systematic under- or over-estimation in real geometry or sensor noise.

What would settle it

A physical robot test in which the SE(2) NavMesh predicts a feasible heading-specific path but the robot collides or gets stuck while the same path is infeasible under a classical NavMesh would falsify the core claim.

Figures

Figures reproduced from arXiv: 2607.01454 by Changan Chen, Ines Kast, Kaixian Qu, Marco Hutter, Shuyang Shi, Yuntao Ma.

Figure 1
Figure 1. Figure 1: Real-world robot navigation on the SE(2) NavMesh. [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Overview of the SE(2) NavMesh system. The offline pipeline constructs the mesh from a pre-built map, whereas the [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Robot geometry approximations and footprint masks. (a) Cylindrical approximation. (b) Cuboid approximation. (c) [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Classical NavMesh representation and graph con [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Generation of layer-specific regions and the navigation graph. Each yaw channel corresponds to a yaw-specific [PITH_FULL_IMAGE:figures/full_fig_p006_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Tile-based SE(2) NavMesh generation. Generating the [PITH_FULL_IMAGE:figures/full_fig_p007_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Overview of the ASA pathfinding strategy. The method consists of three stages: (1) an initial A* search that obtains a [PITH_FULL_IMAGE:figures/full_fig_p009_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Slab-based online SE(2) NavMesh update. (a) A tile is [PITH_FULL_IMAGE:figures/full_fig_p010_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Offline mesh generation results across six simulation scenes. The first row shows the 3D scene models: (a1) [PITH_FULL_IMAGE:figures/full_fig_p011_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Close-up views of voxel classification (top row) and [PITH_FULL_IMAGE:figures/full_fig_p011_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Comparison of traversable regions generated by the NavMesh and SE(2) NavMesh across simulation scenes. [PITH_FULL_IMAGE:figures/full_fig_p012_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Pathfinding tasks and example solutions in constrained environments. For each task, the left image in the first row [PITH_FULL_IMAGE:figures/full_fig_p014_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Trends of SR and SPC over planning time for different planners in constrained environments. ASA achieves the best [PITH_FULL_IMAGE:figures/full_fig_p014_13.png] view at source ↗
Figure 15
Figure 15. Figure 15: Path quality analysis of the ASA pipeline. Path [PITH_FULL_IMAGE:figures/full_fig_p015_15.png] view at source ↗
Figure 14
Figure 14. Figure 14: Pathfinding performance in Task 5, an open-space [PITH_FULL_IMAGE:figures/full_fig_p015_14.png] view at source ↗
Figure 16
Figure 16. Figure 16: Online SE(2) NavMesh generation in a garden. The left panel shows the real-world scene. The middle panel shows [PITH_FULL_IMAGE:figures/full_fig_p016_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: Comparison of local and global SE(2) NavMesh update times during online generation. Local updates maintain the [PITH_FULL_IMAGE:figures/full_fig_p016_17.png] view at source ↗
Figure 18
Figure 18. Figure 18: Real-world navigation in an outdoor multi-level environment. Starting from the lower level, the robot follows a path [PITH_FULL_IMAGE:figures/full_fig_p017_18.png] view at source ↗
Figure 19
Figure 19. Figure 19: Real-world navigation in an indoor single-level environment. The reconstructed scene and generated SE(2) NavMesh [PITH_FULL_IMAGE:figures/full_fig_p017_19.png] view at source ↗
read the original abstract

Global navigation for ground robots in complex multi-level environments requires representations that accurately capture traversable regions while enabling efficient path planning. Current approaches present key limitations: Point clouds and volumetric occupancy maps lack explicit surface structure for traversability estimation, whereas direct pathfinding on dense triangle meshes is computationally prohibitive. Navigation meshes mitigate these challenges through polygonal abstraction of the underlying mesh, but assume yaw-invariant traversability, rendering them unsuitable for non-circular robots in constrained spaces. We propose SE(2) Navigation Mesh (SE(2) NavMesh), a polygonal representation of traversable regions that encodes yaw-dependent traversability. Our method evaluates traversability using footprint masks and constructs a graph over yaw-specific layers with explicit translational and rotational connectivity. Grounded in this representation, we develop an A*-String Pulling-A* (ASA) pathfinding strategy that hierarchically optimizes robot position and heading. We also present an online method that incrementally updates the SE(2) NavMesh from streaming point clouds during concurrent geometry reconstruction. In simulation, the SE(2) NavMesh captures over 50% more traversable area than classical NavMeshes, and the SE(2) NavMesh + ASA pipeline consistently outperforms sampling-based baselines in constrained environments. Extensive real-world experiments on a physical robot validate real-time online generation and successful navigation across multiple environments.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proposes the SE(2) Navigation Mesh, a polygonal abstraction of traversable space that encodes yaw-dependent traversability via footprint-mask evaluation on underlying geometry. It constructs a layered graph with explicit translational and rotational edges, introduces an A*-String Pulling-A* (ASA) hierarchical planner, and provides an incremental online update procedure from streaming point clouds. Simulation results claim >50% more traversable area than yaw-invariant NavMeshes and consistent outperformance versus sampling-based planners in constrained settings; real-robot experiments are said to confirm real-time generation and successful navigation.

Significance. If the footprint-based yaw modeling and performance claims are substantiated with quantitative controls, the representation could usefully extend classical navigation meshes to non-circular robots without incurring the cost of full SE(2) sampling or dense volumetric search. The online reconstruction component would be a practical addition for field deployment.

major comments (2)
  1. [Abstract / Method description] Abstract and method description: the central 50% area-gain and outperformance claims rest on footprint-mask traversability evaluation being an accurate proxy for yaw-specific collisions. No cross-validation against executed robot trajectories, sensor-noise injection, or partial-occlusion cases is reported, leaving open the possibility of systematic false-positive or false-negative area estimates.
  2. [Results / Experiments] Results section (implied by abstract claims): quantitative details on baselines, exact metrics (e.g., success rate, path length, clearance), environment selection criteria, number of trials, and statistical tests are absent, so the statements that the SE(2) NavMesh + ASA pipeline “consistently outperforms” sampling-based methods cannot be assessed for robustness.
minor comments (2)
  1. [Method] Clarify the precise discretization of yaw layers and the definition of inter-layer rotational edges; the connectivity construction is described at a high level but lacks an explicit algorithm or complexity statement.
  2. [Figures] Figure captions and axis labels should explicitly state the robot footprint dimensions and mask resolution used in the reported experiments.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on validation and experimental reporting. We address each major comment below and indicate the corresponding revisions.

read point-by-point responses

  1. Referee: [Abstract / Method description] Abstract and method description: the central 50% area-gain and outperformance claims rest on footprint-mask traversability evaluation being an accurate proxy for yaw-specific collisions. No cross-validation against executed robot trajectories, sensor-noise injection, or partial-occlusion cases is reported, leaving open the possibility of systematic false-positive or false-negative area estimates.

    Authors: The SE(2) NavMesh defines traversability directly via footprint-mask evaluation on the input geometry, which is the basis for both the simulated area comparison and the incremental point-cloud reconstruction. Real-robot experiments demonstrate collision-free navigation using paths from this representation, providing indirect support. We agree that explicit cross-validation against executed trajectories, injected sensor noise, and partial occlusions is not reported and would strengthen the claims. We will add a dedicated limitations subsection discussing these assumptions and the potential for discrepancies in noisy or occluded settings. revision: partial

  2. Referee: [Results / Experiments] Results section (implied by abstract claims): quantitative details on baselines, exact metrics (e.g., success rate, path length, clearance), environment selection criteria, number of trials, and statistical tests are absent, so the statements that the SE(2) NavMesh + ASA pipeline “consistently outperforms” sampling-based methods cannot be assessed for robustness.

    Authors: We will revise the results section to provide the requested quantitative details, including the specific baselines, metrics (success rate, path length, clearance), environment selection criteria, number of trials, and any statistical tests performed. This will enable a clearer assessment of the robustness of the reported outperformance. revision: yes

Circularity Check

0 steps flagged

No significant circularity; central claims rest on external empirical comparisons

full rationale

The SE(2) NavMesh is constructed directly from footprint-mask traversability checks on the input geometry and standard graph layering; the reported >50% area gain and navigation improvements are measured against the independently defined classical (yaw-invariant) NavMesh baseline in simulation and real-robot experiments. No equations, fitted parameters, or self-citations are shown to reduce these quantities to the inputs by construction. The derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only the abstract is available; no explicit free parameters, ad-hoc axioms, or invented physical entities are described. The representation itself is a new algorithmic construct rather than a postulated physical object.

axioms (1)
  • domain assumption Footprint masks evaluated against surface geometry yield reliable yaw-dependent traversability labels
    Central to the construction of yaw-specific layers as stated in the method overview.

pith-pipeline@v0.9.1-grok · 5770 in / 1285 out tokens · 29537 ms · 2026-07-03T19:55:28.622077+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

67 extracted references · 67 canonical work pages · 2 internal anchors

  1. [1]

    Review of robotic infrastructure inspection systems,

    D. Lattanzi and G. Miller, “Review of robotic infrastructure inspection systems,”Journal of Infrastructure Systems, vol. 23, no. 3, p. 04017004, 2017

    work page 2017

  2. [2]

    Robots in inspection and monitoring of buildings and infrastructure: A systematic review,

    S. Halder and K. Afsari, “Robots in inspection and monitoring of buildings and infrastructure: A systematic review,”Applied Sciences, vol. 13, no. 4, p. 2304, 2023

    work page 2023

  3. [3]

    Plant inspection by using a ground vehicle and an aerial robot: lessons learned from plant disaster prevention challenge in world robot summit 2018,

    H. Miura, A. Watanabe, M. Okugawa, T. Miura, and T. Koganeya, “Plant inspection by using a ground vehicle and an aerial robot: lessons learned from plant disaster prevention challenge in world robot summit 2018,” Advanced Robotics, vol. 34, no. 2, pp. 104–118, 2020

    work page 2018

  4. [4]

    Uav-assisted autonomous mobile robot navigation for as-is 3d data collection and registration in cluttered environments,

    P. Kim, J. Park, Y . K. Cho, and J. Kang, “Uav-assisted autonomous mobile robot navigation for as-is 3d data collection and registration in cluttered environments,”Automation in Construction, vol. 106, p. 102918, 2019

    work page 2019

  5. [5]

    Evaluation of a smart mobile robotic system for industrial plant inspection and supervision,

    G. K. Fischer, M. Bergau, D. A. G ´omez-Rosal, A. Wachaja, J. Graeter, M. Odenweller, U. Piechottka, F. H ¨oflinger, N. Gosala, N. Wetzel et al., “Evaluation of a smart mobile robotic system for industrial plant inspection and supervision,”IEEE Sensors Journal, vol. 24, no. 12, pp. 19 684–19 697, 2024

    work page 2024

  6. [6]

    Learning robust perceptive locomotion for quadrupedal robots in the wild,

    T. Miki, J. Lee, J. Hwangbo, L. Wellhausen, V . Koltun, and M. Hutter, “Learning robust perceptive locomotion for quadrupedal robots in the wild,”Science Robotics, vol. 7, no. 62, p. eabk2822, 2022

    work page 2022

  7. [7]

    Legged locomotion in challenging terrains using egocentric vision,

    A. Agarwal, A. Kumar, J. Malik, and D. Pathak, “Legged locomotion in challenging terrains using egocentric vision,” inConference on robot learning. PMLR, 2023, pp. 403–415

    work page 2023

  8. [8]

    Towards autonomous inspection of concrete deterioration in sewers with legged robots,

    H. Kolvenbach, D. Wisth, R. Buchanan, G. Valsecchi, R. Grandia, M. Fallon, and M. Hutter, “Towards autonomous inspection of concrete deterioration in sewers with legged robots,”Journal of field robotics, vol. 37, no. 8, pp. 1314–1327, 2020

    work page 2020

  9. [9]

    Funda- mentals and prospects of four-legged robot application in construction progress monitoring,

    K. Afsari, S. Halder, M. Ensafi, S. DeVito, and J. Serdakowski, “Funda- mentals and prospects of four-legged robot application in construction progress monitoring,”EPiC series in built environment, vol. 2, pp. 274– 283, 2021

    work page 2021

  10. [10]

    3d exploration and navigation with optimal-rrt planners for ground robots in indoor incidents,

    N. P ´erez-Higueras, A. Jard ´on, ´A. Rodr ´ıguez, and C. Balaguer, “3d exploration and navigation with optimal-rrt planners for ground robots in indoor incidents,”Sensors, vol. 20, no. 1, p. 220, 2019

    work page 2019

  11. [11]

    Far planner: Fast, attemptable route planner using dynamic visibility update,

    F. Yang, C. Cao, H. Zhu, J. Oh, and J. Zhang, “Far planner: Fast, attemptable route planner using dynamic visibility update,” in2022 ieee/rsj international conference on intelligent robots and systems (iros). IEEE, 2022, pp. 9–16

    work page 2022

  12. [12]

    Marsim: A light-weight point-realistic simulator for lidar- based uavs,

    F. Kong, X. Liu, B. Tang, J. Lin, Y . Ren, Y . Cai, F. Zhu, N. Chen, and F. Zhang, “Marsim: A light-weight point-realistic simulator for lidar- based uavs,”IEEE Robotics and Automation Letters, vol. 8, no. 5, pp. 2954–2961, 2023

    work page 2023

  13. [13]

    Robotic online path planning on point cloud,

    M. Liu, “Robotic online path planning on point cloud,”IEEE transac- tions on cybernetics, vol. 46, no. 5, pp. 1217–1228, 2015

    work page 2015

  14. [14]

    Driving on point clouds: Motion planning, trajectory optimization, and terrain assessment in generic nonplanar environments,

    P. Kr ¨usi, P. Furgale, M. Bosse, and R. Siegwart, “Driving on point clouds: Motion planning, trajectory optimization, and terrain assessment in generic nonplanar environments,”Journal of Field Robotics, vol. 34, no. 5, pp. 940–984, 2017

    work page 2017

  15. [15]

    Efficient global nav- igational planning in 3-d structures based on point cloud tomography,

    B. Yang, J. Cheng, B. Xue, J. Jiao, and M. Liu, “Efficient global nav- igational planning in 3-d structures based on point cloud tomography,” IEEE/ASME Transactions on Mechatronics, vol. 30, no. 1, pp. 321–332, 2025

    work page 2025

  16. [16]

    V oxblox: Incremental 3d euclidean signed distance fields for on-board mav planning,

    H. Oleynikova, Z. Taylor, M. Fehr, R. Siegwart, and J. Nieto, “V oxblox: Incremental 3d euclidean signed distance fields for on-board mav planning,” in2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2017, pp. 1366–1373

    work page 2017

  17. [17]

    Octomap: An efficient probabilistic 3d mapping framework based on octrees,

    A. Hornung, K. M. Wurm, M. Bennewitz, C. Stachniss, and W. Burgard, “Octomap: An efficient probabilistic 3d mapping framework based on octrees,”Autonomous robots, vol. 34, no. 3, pp. 189–206, 2013

    work page 2013

  18. [18]

    Ego-planner: An esdf- free gradient-based local planner for quadrotors,

    X. Zhou, Z. Wang, H. Ye, C. Xu, and F. Gao, “Ego-planner: An esdf- free gradient-based local planner for quadrotors,”IEEE Robotics and Automation Letters, vol. 6, no. 2, pp. 478–485, 2020. 19

    work page 2020

  19. [19]

    Rog-map: An efficient robocentric occupancy grid map for large-scene and high- resolution lidar-based motion planning,

    Y . Ren, Y . Cai, F. Zhu, S. Liang, and F. Zhang, “Rog-map: An efficient robocentric occupancy grid map for large-scene and high- resolution lidar-based motion planning,” in2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2024, pp. 8119–8125

    work page 2024

  20. [20]

    Towards efficient trajectory generation for ground robots beyond 2d environment,

    J. Wang, L. Xu, H. Fu, Z. Meng, C. Xu, Y . Cao, X. Lyu, and F. Gao, “Towards efficient trajectory generation for ground robots beyond 2d environment,” in2023 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2023, pp. 7858–7864

    work page 2023

  21. [21]

    Locomotion policy guided traversability learning using volumetric representations of com- plex environments,

    J. Frey, D. Hoeller, S. Khattak, and M. Hutter, “Locomotion policy guided traversability learning using volumetric representations of com- plex environments,” in2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2022, pp. 5722–5729

    work page 2022

  22. [22]

    Using occupancy grids for mobile robot perception and navigation,

    A. Elfes, “Using occupancy grids for mobile robot perception and navigation,”Computer, vol. 22, no. 6, pp. 46–57, 2002

    work page 2002

  23. [23]

    Robot-centric elevation mapping with uncertainty estimates,

    P. Fankhauser, M. Bloesch, C. Gehring, M. Hutter, and R. Siegwart, “Robot-centric elevation mapping with uncertainty estimates,” inMobile Service Robotics. World Scientific, 2014, pp. 433–440

    work page 2014

  24. [24]

    Probabilistic terrain mapping for mobile robots with uncertain localization,

    P. Fankhauser, M. Bloesch, and M. Hutter, “Probabilistic terrain mapping for mobile robots with uncertain localization,”IEEE Robotics and Automation Letters, vol. 3, no. 4, pp. 3019–3026, 2018

    work page 2018

  25. [25]

    Elevation mapping for locomotion and navigation using gpu,

    T. Miki, L. Wellhausen, R. Grandia, F. Jenelten, T. Homberger, and M. Hutter, “Elevation mapping for locomotion and navigation using gpu,” in2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2022, pp. 2273–2280

    work page 2022

  26. [26]

    Habitat-Matterport 3D Dataset (HM3D): 1000 Large-scale 3D Environments for Embodied AI

    S. K. Ramakrishnan, A. Gokaslan, E. Wijmans, O. Maksymets, A. Clegg, J. Turner, E. Undersander, W. Galuba, A. Westbury, A. X. Changet al., “Habitat-matterport 3d dataset (hm3d): 1000 large-scale 3d environments for embodied ai,”arXiv preprint arXiv:2109.08238, 2021

    work page internal anchor Pith review Pith/arXiv arXiv 2021

  27. [27]

    Habitat Synthetic Scenes Dataset (HSSD-200): An Analysis of 3D Scene Scale and Realism Tradeoffs for ObjectGoal Navigation,

    M. Khanna*, Y . Mao*, H. Jiang, S. Haresh, B. Shacklett, D. Batra, A. Clegg, E. Undersander, A. X. Chang, and M. Savva, “Habitat Synthetic Scenes Dataset (HSSD-200): An Analysis of 3D Scene Scale and Realism Tradeoffs for ObjectGoal Navigation,”arXiv preprint, 2023

    work page 2023

  28. [28]

    Ovpc mesh: 3d free-space representation for lo- cal ground vehicle navigation,

    F. Ruetz, E. Hern ´andez, M. Pfeiffer, H. Oleynikova, M. Cox, T. Lowe, and P. Borges, “Ovpc mesh: 3d free-space representation for lo- cal ground vehicle navigation,” in2019 International Conference on Robotics and Automation (ICRA). IEEE, 2019, pp. 8648–8654

    work page 2019

  29. [29]

    Continuous shortest path vector field navigation on 3d triangular meshes for mo- bile robots,

    S. P ¨utz, T. Wiemann, M. K. Piening, and J. Hertzberg, “Continuous shortest path vector field navigation on 3d triangular meshes for mo- bile robots,” in2021 IEEE International Conference on Robotics and Automation (ICRA), 2021, pp. 2256–2263

    work page 2021

  30. [30]

    A comparative study of navigation meshes,

    W. Van Toll, R. Triesscheijn, M. Kallmann, R. Oliva, N. Pelechano, J. Pettr´e, and R. Geraerts, “A comparative study of navigation meshes,” inProceedings of the 9th International Conference on Motion in Games, 2016, pp. 91–100

    work page 2016

  31. [31]

    Navigation overview,

    Unity Technologies, “Navigation overview,” https://docs.unity3d.com/ Packages/com.unity.ai.navigation@2.0/manual/NavigationOverview. html, 2026

    work page 2026

  32. [32]

    Navigation system,

    Epic Games, “Navigation system,” https://dev. epicgames.com/documentation/en-us/unreal-engine/ navigation-system-in-unreal-engine, 2024

    work page 2024

  33. [33]

    Habitat challenge 2023,

    K. Yadav, J. Krantz, R. Ramrakhya, S. K. Ramakrishnan, J. Yang, A. Wang, J. Turner, A. Gokaslan, V .-P. Berges, R. Mootaghi, O. Maksymets, A. X. Chang, M. Savva, A. Clegg, D. S. Chaplot, and D. Batra, “Habitat challenge 2023,” https://aihabitat.org/challenge/2023/, 2023

    work page 2023

  34. [34]

    GaitMesh: Controller-aware navigation meshes for long-range legged locomotion planning in multi- layered environments,

    M. Brandao, O. B. Aladag, and I. Havoutis, “GaitMesh: Controller-aware navigation meshes for long-range legged locomotion planning in multi- layered environments,”IEEE Robotics and Automation Letters, vol. 5, no. 2, pp. 3596–3603, 2020

    work page 2020

  35. [35]

    Recast Navigation,

    M. Mononen, “Recast Navigation,” https://github.com/recastnavigation/ recastnavigation, 2014

    work page 2014

  36. [36]

    Processing and interactive editing of huge point clouds from 3d scanners,

    M. Wand, A. Berner, M. Bokeloh, P. Jenke, A. Fleck, M. Hoffmann, B. Maier, D. Staneker, A. Schilling, and H.-P. Seidel, “Processing and interactive editing of huge point clouds from 3d scanners,”Computers & Graphics, vol. 32, no. 2, pp. 204–220, 2008

    work page 2008

  37. [37]

    X-icp: Localizability-aware lidar registration for robust localization in extreme environments,

    T. Tuna, J. Nubert, Y . Nava, S. Khattak, and M. Hutter, “X-icp: Localizability-aware lidar registration for robust localization in extreme environments,”IEEE Transactions on Robotics, vol. 40, pp. 452–471, 2023

    work page 2023

  38. [38]

    Open3d slam: Point cloud based mapping and localization for education,

    E. Jelavic, J. Nubert, and M. Hutter, “Open3d slam: Point cloud based mapping and localization for education,” inRobotic Perception and Mapping: Emerging Techniques, ICRA 2022 Workshop. ETH Zurich, Robotic Systems Lab, 2022, p. 24

    work page 2022

  39. [39]

    Tensor voting: Theory and applications,

    G. Medioni, C.-K. Tang, and M.-S. Lee, “Tensor voting: Theory and applications,” inProceedings of RFIA, vol. 2000. Hermes, Lavoisier Paris, France, 2000

    work page 2000

  40. [40]

    A note on two problems in connexion with graphs,

    E. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol. 1, no. 1, pp. 269–271, 1959

    work page 1959

  41. [41]

    Rapidly-exploring random trees: Progress and prospects,

    S. M. LaValle, “Rapidly-exploring random trees: Progress and prospects,”Algorithmic and Computational Robotics: New Directions 2000 WAFR, p. 293, 2001

    work page 2000

  42. [42]

    Sampling-based algorithms for optimal motion planning,

    S. Karaman and E. Frazzoli, “Sampling-based algorithms for optimal motion planning,”The international journal of robotics research, vol. 30, no. 7, pp. 846–894, 2011

    work page 2011

  43. [43]

    Surface reconstruction from unorganized points,

    H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle, “Surface reconstruction from unorganized points,” inProceedings of the 19th annual conference on computer graphics and interactive techniques, 1992, pp. 71–78

    work page 1992

  44. [44]

    Real-time 3d reconstruction at scale using voxel hashing,

    M. Nießner, M. Zollh ¨ofer, S. Izadi, and M. Stamminger, “Real-time 3d reconstruction at scale using voxel hashing,”ACM Transactions on Graphics (ToG), vol. 32, no. 6, pp. 1–11, 2013

    work page 2013

  45. [45]

    Memory-efficient boundary map for large-scale occupancy grid mapping,

    B. Tang, Y . Ren, Y . Cai, F. Kong, W. Liu, F. Zhu, L. Yin, L. Shi, and F. Zhang, “Memory-efficient boundary map for large-scale occupancy grid mapping,”The International Journal of Robotics Research, p. 02783649261425266, 2026

    work page 2026

  46. [46]

    Ufomap: An efficient probabilistic 3d mapping framework that embraces the unknown,

    D. Duberg and P. Jensfelt, “Ufomap: An efficient probabilistic 3d mapping framework that embraces the unknown,”IEEE Robotics and Automation Letters, vol. 5, no. 4, pp. 6411–6418, 2020

    work page 2020

  47. [47]

    Smug planner: A safe multi- goal planner for mobile robots in challenging environments,

    C. Chen, J. Frey, P. Arm, and M. Hutter, “Smug planner: A safe multi- goal planner for mobile robots in challenging environments,”IEEE Robotics and Automation Letters, vol. 8, no. 11, pp. 7170–7177, 2023

    work page 2023

  48. [48]

    Real-time multi-level terrain-aware path planning for ground mobile robots in large-scale rough terrains,

    Y . Li, K. Chen, Y . Wang, W. Zhang, J. Wang, H. Chen, and Y . Liu, “Real-time multi-level terrain-aware path planning for ground mobile robots in large-scale rough terrains,”IEEE Transactions on Robotics, 2025

    work page 2025

  49. [49]

    Normal distributions trans- form traversability maps: lidar-only approach for traversability mapping in outdoor environments,

    J. Ahtiainen, T. Stoyanov, and J. Saarinen, “Normal distributions trans- form traversability maps: lidar-only approach for traversability mapping in outdoor environments,”Journal of Field Robotics, vol. 34, no. 3, pp. 600–621, 2017

    work page 2017

  50. [50]

    Layered costmaps for context-sensitive navigation,

    D. V . Lu, D. Hershberger, and W. D. Smart, “Layered costmaps for context-sensitive navigation,” in2014 IEEE/RSJ International Confer- ence on Intelligent Robots and Systems. IEEE, 2014, pp. 709–715

    work page 2014

  51. [51]

    Rough terrain navigation for legged robots using reachability planning and template learning,

    L. Wellhausen and M. Hutter, “Rough terrain navigation for legged robots using reachability planning and template learning,” in2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2021, pp. 6914–6921

    work page 2021

  52. [52]

    Lazy collision checking in asymptotically-optimal motion planning,

    K. Hauser, “Lazy collision checking in asymptotically-optimal motion planning,” in2015 IEEE international conference on robotics and automation (ICRA). IEEE, 2015, pp. 2951–2957

    work page 2015

  53. [53]

    Real-time optimal navigation planning using learned motion costs,

    B. Yang, L. Wellhausen, T. Miki, M. Liu, and M. Hutter, “Real-time optimal navigation planning using learned motion costs,” in2021 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2021, pp. 9283–9289

    work page 2021

  54. [54]

    Surface recon- struction from arbitrarily large point clouds,

    T. Wiemann, I. Mitschke, A. Mock, and J. Hertzberg, “Surface recon- struction from arbitrarily large point clouds,” in2018 Second IEEE International Conference on Robotic Computing (IRC). IEEE, 2018, pp. 278–281

    work page 2018

  55. [55]

    Rrt-connect: An efficient approach to single-query path planning,

    J. J. Kuffner and S. M. LaValle, “Rrt-connect: An efficient approach to single-query path planning,” inProceedings 2000 ICRA. Millennium conference. IEEE international conference on robotics and automation. Symposia proceedings (Cat. No. 00CH37065), vol. 2. IEEE, 2000, pp. 995–1001

    work page 2000

  56. [56]

    A formal basis for the heuristic determination of minimum cost paths,

    P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,”IEEE transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100–107, 1968

    work page 1968

  57. [57]

    A*-based pathfinding in modern computer games,

    X. Cui and H. Shi, “A*-based pathfinding in modern computer games,” International Journal of Computer Science and Network Security, vol. 11, no. 1, pp. 125–130, 2011

    work page 2011

  58. [58]

    Use of watersheds in contour detection,

    S. Beucher, “Use of watersheds in contour detection,” inProc. Int. Workshop on Image Processing, Sept. 1979, 1979, pp. 17–21

    work page 1979

  59. [59]

    Triangulation by ear clipping,

    D. Eberly, “Triangulation by ear clipping,”Geometric Tools, pp. 2002– 2005, 2008

    work page 2002

  60. [60]

    Simple Stupid Funnel Algorithm,

    M. Mononen, “Simple Stupid Funnel Algorithm,” https://digestingduck. blogspot.com/2010/03/simple-stupid-funnel-algorithm.html, 2010

    work page 2010

  61. [61]

    Marching cubes: A high resolution 3d surface construction algorithm,

    W. E. Lorensen and H. E. Cline, “Marching cubes: A high resolution 3d surface construction algorithm,”ACM SIGGRAPH Computer Graphics, vol. 21, no. 4, pp. 163–169, 1987

    work page 1987

  62. [62]

    Anymal-a 20 highly mobile and dynamic quadrupedal robot,

    M. Hutter, C. Gehring, D. Jud, A. Lauber, C. D. Bellicoso, V . Tsounis, J. Hwangbo, K. Bodie, P. Fankhauser, M. Bloeschet al., “Anymal-a 20 highly mobile and dynamic quadrupedal robot,” in2016 IEEE/RSJ in- ternational conference on intelligent robots and systems (IROS). IEEE, 2016, pp. 38–44

    work page 2016

  63. [63]

    Anymal technical specifications,

    ANYbotics, “Anymal technical specifications,” https://www.anybotics. com/anymal-technical-specifications.pdf, 2022

    work page 2022

  64. [64]

    Prob- abilistic roadmaps for path planning in high-dimensional configuration spaces,

    L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars, “Prob- abilistic roadmaps for path planning in high-dimensional configuration spaces,”IEEE transactions on Robotics and Automation, vol. 12, no. 4, pp. 566–580, 2002

    work page 2002

  65. [65]

    The open motion planning library,

    I. A. Sucan, M. Moll, and L. E. Kavraki, “The open motion planning library,”IEEE Robotics & Automation Magazine, vol. 19, no. 4, pp. 72–82, 2012

    work page 2012

  66. [66]

    On Evaluation of Embodied Navigation Agents

    P. Anderson, A. Chang, D. S. Chaplot, A. Dosovitskiy, S. Gupta, V . Koltun, J. Kosecka, J. Malik, R. Mottaghi, M. Savvaet al., “On evalu- ation of embodied navigation agents,”arXiv preprint arXiv:1807.06757, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  67. [67]

    Success weighted by completion time: A dynamics-aware evaluation criteria for embodied navigation,

    N. Yokoyama, S. Ha, and D. Batra, “Success weighted by completion time: A dynamics-aware evaluation criteria for embodied navigation,” in2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2021, pp. 1562–1569

    work page 2021