RRT*は不均一地形メッシュ上で機能するか？

- triangle-mesh terrain（R^3内の2次元曲面）上でRRT*が動作するかを問う研究。 - 元のRRT*はmesh上で直接は動かない（曲面は体積ゼロで一様サンプリングが当たらず、clearance ballも収まらず、foldを横切るchordは曲面を離れる）と指摘。 - 曲面向け再定式化Mesh RRT*を提案し、chordをその長さでコスト化する素朴版と、chordを曲面上の経路に置換する改良版を比較。 - 実装はMeshNav3D 0.2.0（release pending）。

- RRT*がEuclidean空間の開部分集合上でstraight-line local planningによりasymptotically optimalであるという既存の理論的出発点に対し、triangle-mesh terrainへ拡張できるかを検証した点。 - 素朴なMesh RRT*は75度までのslopeのheightfieldで全run成功するが、目的関数が誤りであることを示した点が新しい。 - chordベースのコストは曲面上のどの経路の長さでもなく、任意のcurved meshでgeodesic lengthを厳密に下回ることを明示。 - chordを曲面上経路に置換すると、他の変更なしでgeodesicに平均0.07-0.16%以内まで接近し、chord版より2〜3.4倍近いことを示した。

- 曲面をtriangle meshとして扱い、RRT*をmesh上向けに再定式化（Mesh RRT*）。 - 素朴版：edgeをchordとし、そのstraight-line lengthでコスト化。頂点は曲面上、segmentsはtolerance tauまで曲面を離れてよい。 - 改良版：各chordをその上の曲面上の経路に置換。跨ぐmesh edgeごとにprojected pointsを接続して経路を構築し、その経路自身の長さでコスト化。 - これにより全edgeコストがfeasible pathのexact lengthになる。rewiringも同枠組みで実施。

- numeric simulationで30,000 iterations後のコストをexact geodesicと比較。 - 素朴版：報告コストは平均で最大2.7%geodesicを下回る（どの経路も達成しないコスト）。返却経路は平均0.1-0.5%geodesicより長い。 - 改良版：返却経路のexact lengthが全roughnessで平均0.07-0.16%以内、rougher terrainsではchord版より2〜3.4倍近い。 - 素朴版はslope 75度までのheightfieldで全run成功したと報告。

- 素朴版のbiasはrewiringでも残り、polyhedral surfaceではstepに対して線形にしか減衰しない。 - tauを小さくするとbiasとconnectivityのトレードオフが生じる。 - chordコストは曲面上の経路長ではなく、curved meshでgeodesic lengthを厳密に下回るため目的関数として不適切。 - 改良版でも残差（0.07-0.16%）の要因や計算コスト、一般のmesh形状への適用性は要旨からは不明。

- 元のRRT*（asymptotically optimalなoptimal rapidly exploring random tree）。 - geodesic lengthのexact計算（exact geodesic）に関する研究。 - triangle-mesh上の経路計画・geodesic computationの定番手法（例：fast marching法系のgeodesic計算）。 - MeshNav3D 0.2.0の実装・関連ドキュメント。