RRT（Rapidly-exploring Random Trees：ランダムに木を伸ばして経路を探す経路計画アルゴリズム）を生成AIに書かせると、スタートからゴールまで線が繋がったコードが返ってきます。図も出ます。動いたように見えます。
では、その経路は正しいのでしょうか。
この記事では、左右いっぱいに壁で塞いで、通り抜けが物理的に不可能な環境を用意し、そこにRRTを入れました。正解は「経路なし」です。ところが、教科書どおりの衝突判定を素直に書いたRRTは、壁の厚みに対してステップ幅（1回に木を伸ばす距離）が大きい条件で、50回中50回とも「経路を見つけました」と答えました。
図：正解が「経路なし」の環境で返ってきた経路。赤い辺が壁をまたいでいる（右は拡大）
そして、同じ検査をQiitaの連載記事で公開してきた自作のRRT実装にかけたら、同じ場所が抜けていました。壊れていたのは、AIが書いたからではありませんでした。
この記事の実験について（先に断っておきます）
比較対象は「Claude Code の特定の1回の出力」ではなく、RRTの擬似コードを素直にコードへ起こした素朴実装です。AIの出力は毎回変わるので、特定の1回を貼っても読者が再現できませんし、都合の良い出力を選んだと言われても反論できません。代わりに「AIに一発で書かせるとだいたいこの形になる」という骨格を固定し、乱数シードまで固定して300回回しました。掲載したコードはすべて実行して数値を取っています。
同じ測定データを「その差をどう報告するか」の側から扱った姉妹記事を Zenn に書きました（「Aのほうが速い」と書く前に：経路計画ベンチマークを信頼区間で報告する）。この記事が「実装のどこが壊れていたか」で、姉妹記事が「出た差を信頼区間でどう書くか」の担当です。
この記事で分かること
- RRTの生成コードのうち、当たる部分と当たらない部分の境目（実測ベース）
- 経路長と探索ノード数だけを見ても、実装の正しさは判定できないこと（数字で示します）
- 返ってきた経路を後から検査して、衝突判定の取りこぼしを本数で数える方法（コードあり）
- ステップ幅と障害物の最小寸法から、すり抜けが起きるかどうかを事前に計算する式
想定読者は、AIコーディングを実務で試し始めた中級エンジニアと、経路計画をこれから学ぶ人です。RRTを知らなくても読めるように書きました。
1. 「線が繋がる」ところまでは、たぶん当たる
RRTの骨格は4手順しかありません。
図：RRTの1周ぶんの流れ。この4手順は教科書にも論文にも同じ形で載っている
サンプリング（探索領域の中からランダムに1点選ぶこと）して、最近傍（今ある木の中で、その点にいちばん近いノード）を探して、ステップ幅ぶん伸ばして、当たらなければ追加する。世に出回っている擬似コードは、どれもこの形をしています。だから生成モデルがこの骨格を外すことは、まずないはずです。
当たらないのは、この図の4番だけです。「障害物に当たるか」の判定は、環境の表し方（円か、多角形か、点群か、メッシュか）、ロボットの形（点か、円か、多関節か）、そしてどの空間で探索しているか（手先の位置を座標とみなす作業空間か、各関節の角度を座標とみなす関節角空間か）に依存します。擬似コードには if CollisionFree(x_new) then としか書かれていません。その中身は、書く人の環境ごとに違うからです。
生成モデルにとっては、ここが学習した一般解と、目の前の環境の個別解がズレる場所になります。しかも 4番が壊れても、1〜3番が正しければ線は繋がります。図は出ます。
2. 実験設計：何を固定して、何を測るか
比較の条件を先に開示します。
| 種類 | 項目 | 値 |
|---|---|---|
| 固定 | 探索領域 | 2次元、x も y も 0〜6 の正方形 |
| 固定 | 始点 / 終点 | (0.5, 0.5) / (5.5, 5.5)（直線距離 7.071） |
| 固定 | ロボット | 半径 r = 0.05 の円 |
| 固定 | ステップ幅 Δ | 0.25（自作実装の既定値） |
| 固定 | 乱数シード（乱数の出方を再現するための種） | 0〜299 の300本を、どの実装にも同じ順で与える |
| 変える | 実装 | 自作版 / 素朴版 / 素朴版＋線分補間チェック |
| 変える | 環境 | 環境A（右に抜け道あり）/ 環境B（左右いっぱいに塞ぐ） |
測る指標は3つです。
- 経路長：返ってきた経路の折れ線の長さ
- 探索ノード数：木に追加されたノードの数
- 衝突判定の取りこぼし件数：返ってきた経路の各辺を後から厳密に再検査して、障害物に食い込んでいる辺を数える
3つ目がこの記事の本体です。1と2は「実装が違っても似た値になってしまう」ことを示すために測ります。
障害物は円を等間隔に並べて壁にしました。円だけで作るのは、後の計算で線分と障害物の最短距離を解析的に解けるようにするためです。刻み幅に依存しない厳密な判定器を持っておかないと、審判側が信用できません。
図：左が環境A（右に抜け道があるので経路は存在する）、右が環境B（左右いっぱいに塞いだので経路は存在しない）。壁は半径 0.20 の円を間隔 0.20 で並べて作っている
環境Bには経路が存在しません。正解は「失敗」です。 ここで「成功しました」と答える実装は、答え合わせをするまでもなく間違っています。
実験に入る前に、環境が実験に耐えるかを先に確認しました（始点と終点が無衝突であること、始点と終点を直線で結ぶと衝突すること、線分補間チェック付きなら環境Aを359反復で解けること）。塞がれた構成を引いたまま探索アルゴリズムを回すと、失敗の原因が環境なのか実装なのか分からなくなります。
3. 指標①②：経路長と探索ノード数は、揃ってしまう
環境Aで300回ずつ回した結果です。
| 実装 | 成功 | 経路長（平均±標準偏差） | 探索ノード数 | 平均計算時間 |
|---|---|---|---|---|
| 自作版（端点のみ判定） | 300/300 | 9.692 ± 0.727 | 398.8 ± 170.9 | 21.4 ms |
| 素朴版（端点のみ判定） | 300/300 | 9.836 ± 0.780 | 292.7 ± 131.5 | 7.6 ms |
| 素朴版（サンプリング範囲を自作版に合わせる） | 300/300 | 9.720 ± 0.689 | 384.7 ± 163.8 | 10.0 ms |
| 素朴版 ＋ 線分補間チェック | 300/300 | 9.840 ± 0.783 | 293.1 ± 131.7 | 29.6 ms |
経路長の差は 9.692 と 9.836 で 1.5% です。標準偏差が 0.7 以上あるので、この差は乱数のばらつきに埋もれています。
図：環境Aで同じ乱数シード（6番）を与えたときの経路。左が自作版、右が素朴版。どちらも抜け道を通っている
一方、探索ノード数は 398.8 と 292.7 で 36% も違いました。これは実装の優劣ではありません。自作版はサンプリング範囲を「始点と終点の外接矩形＋余白0.2」に絞っており、素朴版は探索領域の全域から一様にサンプリングしていたからです。3行目のとおりサンプリング範囲を自作版に合わせると 384.7 になり、差は約4%まで縮みます。経路長の差も1.5%から0.3%に縮みました。
つまり、指標①②で出た差は衝突判定とは何の関係もない、サンプリング範囲という別のパラメータの影響でした。ここが「見た目と数字だけでは実装の正しさを判定できない」という主張の裏付けになります。経路長も、ノード数も、揃うときは揃うのです。
計算時間の列は参考値です。自作版は木の配列を np.append で毎回作り直す実装なので、ノード数が増えるほど不利になります。アルゴリズムの速さを比べた数字ではありません。
4. 指標③：衝突判定の取りこぼしを数える
同じ300回の経路を、今度は線分そのもので再検査しました。
RRTが木を伸ばすとき、判定しているのは「新しく作った点」だけです。しかし実際にロボットが通るのは、親ノードから新しい点までの線分です。この差を絵にするとこうなります。
図：両端が無衝突でも、その間が障害物に食い込むことがある。左は端点しか見ていないので通してしまう。右は線分を刻んで並べた補間点が破線の内側に入るので検出できる
まず、RRTが実際にやっている判定はこれです。点と円の距離を測って、半径の和より近ければ当たり。
import numpy as np
def is_collision_point(point: np.ndarray, obstacles: np.ndarray, robot_radius: float) -> bool:
"""点が障害物に当たっているか
パラメータ
point: 判定したい位置 (x, y)
obstacles: 各行が (中心x, 中心y, 半径) の障害物
robot_radius: ロボットを円とみなしたときの半径
戻り値
当たっていれば True
"""
distance = np.linalg.norm(obstacles[:, :2] - point, axis=1)
return bool(np.any(distance <= obstacles[:, 2] + robot_radius))
この式自体は正しく動きます。問題は、判定している場所が点しかないことです。
そこで、再検査には線分と円の最短距離を使います。刻み幅に依存しない形で書けます。
def segment_to_circle_distance(p: np.ndarray, q: np.ndarray, centers: np.ndarray) -> np.ndarray:
"""線分 p-q と各円の中心との最短距離
パラメータ
p: 線分の始点
q: 線分の終点
centers: 各行が (中心x, 中心y) の円中心
戻り値
各円中心までの最短距離
"""
d = q - p
denom = float(d @ d)
# 線分上で最も近い点のパラメータ t を [0, 1] に丸める（丸めないと無限に伸びる直線の扱いになる）
t = np.zeros(len(centers)) if denom == 0.0 else np.clip((centers - p) @ d / denom, 0.0, 1.0)
closest = p + t[:, None] * d
return np.linalg.norm(centers - closest, axis=1)
これを使って、経路の各辺を検査します。両端は無衝突なのに、線分としては当たっている辺を数えれば、それが取りこぼしです。
def audit_path(path: np.ndarray, obstacles: np.ndarray, robot_radius: float) -> dict:
"""経路の各辺を再検査し、端点だけの判定が取りこぼした辺を数える
パラメータ
path: 各行が (x, y) の経路
obstacles: 各行が (中心x, 中心y, 半径) の障害物
robot_radius: ロボットの半径
戻り値
辺の総数・取りこぼし辺数・最大めり込み量・該当する辺の番号
"""
missed_index = []
max_depth = 0.0
for i in range(len(path) - 1):
p, q = path[i], path[i + 1]
if is_collision_point(p, obstacles, robot_radius):
continue
if is_collision_point(q, obstacles, robot_radius):
continue
distance = segment_to_circle_distance(p, q, obstacles[:, :2])
# 障害物をロボット半径ぶん膨らませた円に、どれだけ食い込んだか
depth = float(np.max(obstacles[:, 2] + robot_radius - distance))
if depth > 0.0:
missed_index.append(i)
max_depth = max(max_depth, depth)
return {"edges": len(path) - 1, "missed": len(missed_index),
"max_depth": max_depth, "missed_index": missed_index}
結果です。
| 実装 | 経路の辺の総数 | 取りこぼした辺 | 取りこぼしが出た試行 | 最大めり込み量 |
|---|---|---|---|---|
| 自作版（端点のみ判定） | 11,738 | 22本（0.187%） | 20 / 300（6.7%） | 0.0279 |
| 素朴版（端点のみ判定） | 11,903 | 12本（0.101%） | 12 / 300（4.0%） | 0.0300 |
| 素朴版（サンプリング範囲を揃える） | 11,775 | 24本（0.204%） | 22 / 300（7.3%） | 0.0284 |
| 素朴版 ＋ 線分補間チェック | 11,909 | 0本 | 0 / 300 | 0.0000 |
素朴版が 0.101%、自作版が 0.187%。サンプリング範囲を揃えた素朴版は 0.204% で、自作版とほぼ同じでした。素朴版のほうが壊れている、という結果にはなりませんでした。
図：300試行のうちめり込みが最大だった辺（赤）。破線がロボット半径ぶん膨らませた障害物。両端の青点は破線の外側にあるので、端点判定では通ってしまう
めり込み量の最大は 0.0279 で、ロボット半径 0.05 の 56% でした。これは理論値とも合います。ステップ幅 $\Delta$ の線分が、半径 $\rho$（障害物半径＋ロボット半径）の円に食い込める深さの上限は
d_{\max} = \rho - \sqrt{\rho^2 - (\Delta/2)^2}
で、$\rho = 0.25,\ \Delta = 0.25$ を入れると 0.0335 になります。実測の最大 0.0279（自作版）と 0.0300（素朴版）は、どちらもこの上限の内側でした。
5. 正解が「経路なし」の環境に入れると、嘘が数えられる
0.187% という数字は、小さいと読めてしまいます。めり込み量も 0.03 程度で、ロボット半径の半分ちょっと。実害があるのかどうか、この数字だけでは判断がつきません。
そこで環境Bです。壁で完全に塞いだので、正解は「経路なし」。ここで成功を返したら、それは全部が嘘です。数えやすい。
素朴版でステップ幅 $\Delta$ を振った結果と、壁を作る円の半径 $R$ を振った結果です（各点50試行）。
図：環境Bで「経路を見つけた」と答えた割合。破線は後述の理論しきい値
| $\Delta$（$R$=0.20 固定） | 0.15 | 0.25 | 0.35 | 0.45 | 0.50 | 0.60 | 0.80 | 1.00 |
|---|---|---|---|---|---|---|---|---|
| 「見つけた」と答えた回数 | 0/50 | 0/50 | 0/50 | 0/50 | 50/50 | 50/50 | 50/50 | 50/50 |
| $R$（$\Delta$=0.25 固定） | 0.03 | 0.04 | 0.06 | 0.08 | 0.10 | 0.15 | 0.20 |
|---|---|---|---|---|---|---|---|
| 「見つけた」と答えた回数 | 50/50 | 50/50 | 50/50 | 6/50 | 0/50 | 0/50 | 0/50 |
0 か 50 かで、途中がほとんどありません。境目は計算できます。半径 $R$ の円を間隔 $R$ で並べた壁を、ロボット半径 $r$ ぶん膨らませたときの最も薄い場所の厚みは
T = 2\sqrt{(R + r)^2 - (R/2)^2}
です。ステップ幅 $\Delta$ がこの $T$ 以上なら、1辺で壁をまたげてしまいます。$R = 0.20,\ r = 0.05$ なら $T = 0.4583$。表の切り替わりは $\Delta = 0.45$ と $0.50$ の間で、式と一致しました。$\Delta = 0.25$ 固定で $R$ を振ったほうの境目は $R = 0.0815$ で、こちらも $R = 0.06$（すり抜ける）と $R = 0.10$（すり抜けない）の間に入っています。境目のすぐ内側にあたる $R = 0.08$ が 6/50 と中途半端な値になったのも、「またげるが確率は低い」という理屈と合います。
念のため、この式が本当に壁の厚みを表しているかは、壁を縦に走査して実測と突き合わせました（差は最大 0.0008）。
さて、本題です。同じ環境Bに、自作実装をそのまま入れます。 ステップ幅は既定の 0.25 のまま、タイムアウトも既定の10秒のままです。
| 壁の円半径 $R$ | しきい値 $T$ | 「経路を見つけた」と答えた回数 | 平均計算時間 |
|---|---|---|---|
| 0.06 | 0.2117 | 50 / 50 | 0.13 秒 |
| 0.08 | 0.2474 | 28 / 50 | 5.79 秒 |
| 0.20 | 0.4583 | 0 / 20 | 10.00 秒（＝正しくタイムアウト） |
壁が太ければ（$R=0.20$）、自作実装は10秒粘って正しく失敗します。壁が細ければ（$R=0.06$）、0.13秒で「見つけました」と嘘をつきます。 この差はステップ幅と壁の厚みの関係だけで決まっていて、コードを書いたのが人間かAIかは1ミリも関係していません。
$R = 0.08$ の 28/50 という数字にも意味があります。素朴版の同条件は 6/50 でした。違いは試行予算です。素朴版は4000反復で打ち切り、自作版は10秒間ずっと試し続けます。探索を粘るほど、低確率のすり抜けを引き当てる確率が上がるわけです。「タイムアウトを伸ばしたら解けるようになった」は、疑ってかかったほうがいい兆候でした。
図：自作実装が環境B（$R$=0.06）で返した「成功」経路。右の拡大図で、赤い1辺が壁を突き抜けている。めり込み量 0.1044
そして、直し方は1か所です。木を伸ばすときに、線分を刻んで判定する。
def is_collision_segment_sampled(p: np.ndarray, q: np.ndarray, obstacles: np.ndarray,
robot_radius: float, resolution: float) -> bool:
"""線分を resolution 刻みで補間し、各点で点判定を繰り返す
パラメータ
p: 線分の始点
q: 線分の終点
obstacles: 各行が (中心x, 中心y, 半径) の障害物
robot_radius: ロボットの半径
resolution: 補間の刻み幅。ステップ幅の 1/10 程度にする
戻り値
当たっていれば True
"""
n = max(int(np.ceil(np.linalg.norm(q - p) / resolution)), 1)
for i in range(n + 1):
if is_collision_point(p + (q - p) * (i / n), obstacles, robot_radius):
return True
return False
すり抜けが起きていた条件（Δ=0.50 と 1.00、および R=0.03 / 0.04 / 0.06）で試し直すと、すべて 0/50 になりました。環境Aの取りこぼしも 22本から 0本、300試行中0試行です。代償は計算時間で、素朴版の 7.6 ms が 29.6 ms になりました（約3.9倍）。刻み幅をステップ幅の 1/10 にしたので、1辺あたり11回の点判定が走ります。
線分補間チェックも万能ではありません。刻み幅より薄い障害物は、補間点の隙間をすり抜けます。刻み幅は「環境にある最も薄い障害物の厚み」より細かくする必要があります。今回は $\Delta/10 = 0.025$ に対して壁の最小厚みが 0.157（$R$=0.03 のとき）だったので余裕がありました。厚みの読みが立たない環境では、線分と物体の距離を解析的に解くか、python-fcl（Flexible Collision Library の Python版：3D形状どうしの干渉を判定するライブラリ）のように、動きの途中まで含めて判定する仕組みに任せるほうが安全です。
6. 生成コードを信じる前に走らせる、4つの検査
ここまでの実測から、そのまま持ち帰れる形にまとめます。自作実装という物差しを持っていなくても、全部できます。
検査1：塞がれた環境を1つ用意して、失敗するかを見る
いちばん効きました。正解が分かっている環境（経路が存在しない環境）を1つ作って、経路生成が失敗を返すかを確認します。成功を返したら、その時点でアウトです。壁は円を並べるだけで作れます。
def make_blocked_wall(radius: float, y: float, x_min: float, x_max: float) -> np.ndarray:
"""円を半径ぶんの間隔で並べて、隙間なく塞いだ壁を作る"""
n = int(np.floor((x_max - x_min) / radius)) + 1
xs = x_min + radius * np.arange(n)
return np.stack([xs, np.full(n, y), np.full(n, radius)], axis=1)
このとき、壁を探索領域より外まで伸ばしておくのを忘れないでください。RRTは新しいノードを「最近傍から $\Delta$ だけ伸ばした位置」に置くので、サンプリング範囲の外にはみ出せます。壁が探索領域と同じ幅だと、木が壁の端を回り込んで「正しく」ゴールに着いてしまい、テストとして成立しません。この記事の実験でも、最初は壁を狭く作っていて、回り込みとすり抜けが混ざりました。
検査2：返ってきた経路を、後から再検査する
4章の audit_path をそのまま使えます。経路生成の中身に一切手を入れずに、返ってきた出力だけを検査できるのが利点です。生成されたコードを読む前に、まずこれを回すのが速いと思います。
検査3：ステップ幅と、障害物の最小寸法を突き合わせる
$T = 2\sqrt{(R+r)^2 - (R/2)^2}$ は円を並べた壁に特化した式ですが、考え方は一般に使えます。障害物のいちばん薄いところの厚みと、ステップ幅（および衝突判定の刻み幅）を比べる。前者が後者より薄ければ、すり抜けは起きます。薄い板や柵、テーブルの天板のような障害物がある環境では、この比較を先にやっておいたほうがいいです。
検査4：ロボット半径をゼロにして、成功率が変わるかを見る
衝突判定が本当にロボットの形を使っているかの確認です。半径を 0 にしても結果が変わらないなら、生成コードはロボットを点として扱っている疑いがあります。
ただし、この検査は環境を選びます。壁の途中に狭い隙間だけを開けた環境で試した成功率です。ロボットの直径は 0.10 なので、隙間が 0.10 未満なら本来は通れません。
| 隙間の幅 | r = 0.05 | r = 0.00 |
|---|---|---|
| 0.05 | 7 / 50 | 50 / 50 |
| 0.08 | 27 / 50 | 50 / 50 |
| 0.12 | 50 / 50 | 50 / 50 |
隙間が狭いときだけ、はっきり差が出ました。一方、抜け道が広い環境Aで同じことをすると、経路長は 9.773 と 9.729 でほとんど動きません（100試行）。半径を効かせたいなら、半径が効く狭さの環境を用意する必要があります。
ついでに言うと、r = 0.05 で 7/50 が通ってしまっているのも、ここまで見てきた端点判定のすり抜けです。通れないはずの隙間を、1辺でまたいでいます。
関節角空間（各関節の角度を座標とみなした空間）と作業空間（手先の位置を座標とみなした空間）の取り違えも、この検査で表に出ることがあります。ただしそちらは今回測っていません。
まとめ
- RRTの骨格（サンプリング、最近傍探索、伸長、追加）は教科書どおりに書けるので、生成コードでもほぼ当たる。当たらないのは環境依存の衝突判定だけだった
- 経路長は 9.692 と 9.836 で 1.5% 差。探索ノード数の 36% 差は、衝突判定ではなくサンプリング範囲の違いが原因だった。指標①②では正しさを判定できない
- 経路を後から再検査すると、端点だけの衝突判定は 11,738 辺のうち 22 辺（0.187%）を取りこぼしていた。300試行中20試行で発生
- 正解が「経路なし」の環境に入れると、壁が細い条件では素朴版も自作版も50回中50回「経路を見つけた」と答えた。境目は $T = 2\sqrt{(R+r)^2 - (R/2)^2}$ とステップ幅の大小で決まる
- 木を伸ばすときに線分を刻んで判定すると、すり抜けていた条件がすべて 0/50 になった。計算時間は約3.9倍
結論を一行にすると、AIが書いたコードは信用できない、という話にはなりませんでした。端点だけを見る衝突判定という設計が、書いた主体によらず同じ穴を開けるという話です。実際、自作実装の衝突判定メソッドが受け取る引数は、新しく作った点1つだけでした。線分を渡す口がそもそもありません。
生成AIを使うと、コードの量は簡単に増えます。増えたぶんだけ、正しさを数字で判定する手段が要ります。経路計画の場合は、それが「塞がれた環境を1つ用意する」という、数行で書ける検査でした。
終わりに
RRTそのものの実装と、干渉判定の詳しい話は既存の記事に書いています。
- 経路生成手法の自作記事まとめ：RRT系アルゴリズムの実装記事の一覧
- 経路生成 (RRT) を実装してみた Part1：この記事で「自作版」として使った実装の解説
- 経路生成 (RRT*) を実装してみた Part1：経路長を縮める改良版（Rewire＝一度作った木の枝を繋ぎ替えて経路を短くする処理）
- 干渉判定用ライブラリ python-fcl の使用方法：2Dの円で済まなくなったときの選択肢
- なぜダイクストラは最短を保証できるのか？：グリッド系の探索と比べたい人向け
検証は、環境定義と素朴RRT、再検査器、走査スクリプト、図の生成まで一式を書いて回しました。記事中のコードはすべてヘッドレス（画面を開かずに実行すること。matplotlib.use("Agg") を指定）で動かし、実行時の警告が出ないことも確認しています（Python 3.10.9 / numpy 1.26.4 / matplotlib 3.7.0）。