このプロジェクトについて

自動駐車車両の進化に関するブログ記事のカバー画像。駐車スペースへ車が操縦している様子を示す
ブログ記事のカバーは、自動駐車車両の進化プロジェクトをイラスト化しており、駐車場を走行する車を示している。trekhleb.dev

冒頭の段落でTrekhlebのブログ記事とその遺伝的アルゴリズムによる駐車車両のTypeScript実装が紹介されており、カバー画像は読者にプロジェクトの即時的な視覚的アンカーを与える。

Trekhlebのブログ記事(2021年9月)は、遺伝的アルゴリズムを使って車に自動駐車を教える過程を解説している。プロジェクトはTypeScriptで実装され、完全なソースコードは500行未満に収まっている。

自動駐車車両の仕組み

車には8つの距離センサー(「目」)が搭載されており、それぞれが0〜4メートルの範囲で障害物までの距離を報告する。センサーは100ミリ秒ごとに更新され、値が0なら障害物が検出されていないことを、小さな正の値なら接近していることを示す。車には2つの「筋肉」がある:エンジン筋が前進、後退、ニュートラルを制御し、ステアリング筋が移動中の左折、右折、直進を制御する。各筋肉は100ミリ秒ごとに-1、0、+1の3信号のいずれかを受け取る。

車の「脳」は2つの線形多項式で構成され、一方はエンジン信号を、もう一方はステアリング信号を制御する。各多項式は8つのセンサー値を変数とし、9つの係数をパラメータとして持つ(係数×変数の8つの積に、乗算なしで加算される1つの定数項)。合計18個の係数が車の振る舞いを定義し、これがゲノムとなる。

ゲノム構造

18個の10進数係数はそれぞれ10ビットの二進数(符号ビット1、指数ビット4、仮数部ビット5)に変換され、180ビットのゲノム(18係数×10ビット)が生成される。つまり、車の完全なDNAは180個の0と1で構成される。

浮動小数点10進数が二進数表現に変換される様子を示す図
車の180ビットゲノムで使用される二進形式へ、浮動小数点係数が変換される例。trekhleb.dev

ゲノム構造の段落で、18個の10進数係数それぞれが10ビットの二進数として符号化されることが説明されており、この変換図はまさにその符号化ステップを示している。

進化のプロセス

開始時、車にはランダムなゲノムが与えられ、無秩序な振る舞いを示す。約40世代を経ると、車は自動駐車の意味を学び始め、駐車スペースに接近するようになるが、他の車に衝突したり、スペースにうまく収まらなかったりすることもある。プロジェクトにはブラウザベースの進化シミュレーターが用意されており、ユーザーはゼロから車を学習させたり、遺伝的パラメータを調整したり、最も性能の良いゲノムの係数と値を検査したりできる。

ランダムなゲノムを持つ第1世代の車が駐車場で無秩序に走行し衝突している様子
ランダムなゲノムで初期化された第1世代の車は、無秩序に振る舞い、ほとんど駐車に成功しない。trekhleb.dev

進化の段落で、車がランダムなゲノムから始まり無秩序な振る舞いを生むことが説明されており、この第1世代のアニメーションがそれを鮮明に示している。

第40世代の車が衝突せずに駐車スペースへ操縦することを学習した様子
第40世代になると、車は自動駐車の方法を学び始め、目標のスペースにより確実に接近するようになる。trekhleb.dev

同じ進化の段落で、約40世代後に車が自動駐車を理解し始めると記載されており、このアニメーションはその開発段階を捉えている。

不明な点

情報源は、世代ごとの正確な駐車成功率を報告しておらず、終了条件や最終的なパフォーマンスベンチマークも指定していない。ブログでは、単純な多項式の脳が未知の環境への汎化能力を制限していることに言及しているが、定量的な結果は示されていない。

証拠

1. 遺伝的アルゴリズムが世代を重ねて車のゲノムを進化させ、およそ第40世代で車が自動駐車行動を学び始める。これは主要情報源であるブログ記事の抜粋(「彼らにとって世界が創造されてからまだ40世代しか経っていない」)と、GitHubリポジトリ(support-2)の説明(車が第40世代までに学習を始めると記載)によって裏付けられている。

2. 車の脳は18個の係数を持つ2つの線形多項式として実装され、各係数を10ビットで符号化すると完全なゲノムは180ビットになる。これは、主要情報源の多項式構造、係数変換、ゲノム符号化の詳細な説明によって直接的に裏付けられている。

各主張は、厳密に関連する提供済み情報源IDのみにマッピングされている。HNの議論、コメント、無関係な情報源は引用されていない。