Does RRT* Work on Uneven Terrain Meshes?
Organizations: Laboratório de Engenharia de Sistemas e Robótica, Universidade Federal da Paraíba (UFPB), João Pessoa 58055-000, Paraíba, Brazil
Abstract
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).
Figures & tables
| Primitive in [ 4 ] | On the manifold | Chord implementation | Faithful? |
|---|---|---|---|
| SampleFree (uniform in ) | uniform by area on | area-weighted face, uniform barycentric point | yes |
| Nearest (Euclidean) | geodesic nearest | Euclidean nearest | approximation; on a heightfield with slope , |
| Steer (move along a line) | move along the geodesic | chord step, projected back onto , pulled back to | approximation; node lies on |
| Near (ball, radius ) | geodesic disk, radius | Euclidean ball , same radius law, | superset of the geodesic disk ( ) |
| Line and its cost | geodesic segment, length | straight chord, length | no : not on , and below |
| CollisionFree | segment inside | chord within a tolerance of , optional slope limit | proxy for holes and forbidden faces |
| Ampl. | Chord | Chord | Surf. opt. | Surf. |
|---|---|---|---|---|
| 1 | 0.9975 | 1.0025 | 1.0020 | 1.0019 |
| 2 | 0.9890 | 1.0043 | 1.0026 | 1.0024 |
| 4 | 0.9733 | 1.0044 | 1.0029 | 1.0019 |
| Ampl. | Ratio per doubling | ||||
|---|---|---|---|---|---|
| 0.5 | 0.0003 | 0.0007 | 0.0015 | 0.0034 | 2.1–2.3 |
| 1 | 0.0009 | 0.0018 | 0.0039 | 0.0091 | 1.9–2.3 |
| 2 | 0.0020 | 0.0042 | 0.0068 | 0.0145 | 1.6–2.1 |
| 4 | 0.0043 | 0.0077 | 0.0116 | 0.0211 | 1.5–1.8 |
| Ampl. | Rej. | Solved 500/2000/5000 | First sol. | Reported | ||
|---|---|---|---|---|---|---|
| 2 | 0.15 | 0.1% | 15/15/15 | 71/120 | 0.9888 | 1.0033 |
| 2 | 0.05 | 21% | 5/14/15 | 734/2114 | 0.9938 | 1.0023 |
| 2 | 0.02 | 58% | 0/1/10 | 4318/8304 | 0.9999 | 1.0032 |
| 4 | 0.15 | 1.4% | 15/15/15 | 140/385 | 0.9729 | 1.0055 |
| 4 | 0.05 | 32% | 1/15/15 | 1168/1948 | 0.9870 | 1.0042 |
| 4 | 0.02 | 63% | 0/2/11 | 3889/6411 | 0.9963 | 1.0060 |
| Ampl. | Edges | |||
|---|---|---|---|---|
| 2 | 0.15 | 288 136 | 0.9890 | 1.0043 |
| 2 | 0.05 | 241 075 | 0.9966 | 1.0039 |
| 2 | 0.02 | 154 320 | 1.0066 | 1.0101 |
| 2 | 0.005 | 72 814 | 1.1429 | 1.1441 |
| 4 | 0.15 | 374 856 | 0.9733 | 1.0044 |
| 4 | 0.05 | 284 247 | 0.9898 | 1.0048 |
| Ampl. | Slope | 500 it. | 2000 it. | First sol. mean / worst | Rej. |
|---|---|---|---|---|---|
| 0 | 15/15 | 15/15 | 72 / 114 | 0 | |
| 0.5 | 15/15 | 15/15 | 73 / 110 | 0 | |
| 1 | 15/15 | 15/15 | 73 / 116 | 0 | |
| 2 | 15/15 | 15/15 | 71 / 120 | 0.1% | |
| 4 | 15/15 | 15/15 | 140 / 385 | 1.4% |
| Ampl. | 1 | 2 | 3 | 4 | 8 | 16 | 32 | ||
|---|---|---|---|---|---|---|---|---|---|
| 1 | surf. | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 |
| surf. time | 1.23 | 1.23 | 1.26 | 1.31 | 1.31 | 1.44 | 1.62 | 1.95 | |
| chord | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | |
| chord time | 0.93 | 0.97 | 0.98 | 1.00 | 1.02 | 1.06 | 1.14 | 1.30 | |
| 2 | surf. | 11 | 11 | 12 | 11 | 11 | 12 | 12 | 12 |
| surf. time | 1.39 | 1.40 | 1.43 | 1.53 | 1.55 | 1.62 | 1.88 | 2.31 |
| Ampl. | A ∗ length | Theta ∗ |
|---|---|---|
| 0 | 1.100 | 1.000 |
| 0.5 | 1.088 | 1.019 |
| 1 | 1.070 | 1.024 |
| 2 | 1.085 | 1.039 |
| 4 | 1.087 | 1.059 |
Motion Planning
Motion planning finds safe, feasible paths and trajectories for robots and vehicles amid geometric, dynamic, and task constraints.
See all 439 papers