Metraipolis › archive › dc_5f4792fe77d7

Does RRT* Work on Uneven Terrain Meshes? — arXiv:2611.05885

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.05885
License (as archived): CC0-1.0
Archived: 2026-11-05T18:30:35.085Z
SHA-256 of the archived text: a2e31ebf7edddbecc56c97a287be87a52dfa37c13d305e30b324366da336586d
Stable URL of this page: https://metraipolis.com/documento/dc_5f4792fe77d7

How to cite

Does RRT* Work on Uneven Terrain Meshes? — arXiv:2611.05885 — arXiv (en), https://arxiv.org/abs/2611.05885 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5f4792fe77d7 (Metraipolis archive dc_5f4792fe77d7, sha256 a2e31ebf7edddbecc56c97a287be87a52dfa37c13d305e30b324366da336586d)

BibTeX

@misc{dc5f4792fe77d7,
  title = {Does RRT* Work on Uneven Terrain Meshes? — arXiv:2611.05885},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.05885},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5f4792fe77d7; sha256 a2e31ebf7edddbecc56c97a287be87a52dfa37c13d305e30b324366da336586d},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05885. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The optimal rapidly exploring random tree (RRT*) is proven asymptotically optimal on open subsets of Euclidean space with straight-line local planning. We ask whether it works on a triangle-mesh terrain, a two-dimensional surface in R^3. First, the original RRT* cannot run on a mesh: the surface has zero volume, so uniform sampling never hits it, no clearance ball fits in it, and chords across a fold leave it. Second, the surface reformulation we call Mesh RRT*, with its naive edge, the chord costed by its length, solved every run on heightfields with slopes up to 75 degrees but minimises the wrong objective: its cost, the straight-line length of a polyline whose vertices lie on the surface while its segments may leave it by a tolerance tau, is the length of no route on the surface and lies strictly below the geodesic length on any curved mesh. In numeric simulation and after 30,000 iterations the reported cost is on average up to 2.7% below the exact geodesic, a cost no path attains, and the returned route on average 0.1-0.5% longer than it. Rewiring keeps the biased edges, the bias decays only linearly with the step on polyhedral surfaces, and shrinking tau trades bias for connectivity. Third, replacing each chord by a path on the surface above it, built from projected points joined across the mesh edges they straddle and costed by its own length, makes every edge cost the exact length of a feasible path; with no other change the exact length of the returned routes is on average within 0.07-0.16% of the geodesic at every roughness tested, two to 3.4 times closer than with chords on the rougher terrains. The planner is in MeshNav3D 0.2.0 (release pending).

Tema degli esploratori: statistica e scienza dei dati (elenco arXiv cs.RO, nuovi lavori del giorno).
Categorie arXiv: Robotics (cs.RO) ; Computational Geometry (cs.CG).
Pagina del lavoro: https://arxiv.org/abs/2611.05885 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-05T18:20:03.982Z dalla pagina https://arxiv.org/list/cs.RO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).