遺伝的アルゴリズムを用いた自己駐車可能な車 (2021)

TL;DRこの記事では、遺伝的アルゴリズムを用いて車を自己駐車できるように訓練します。ランダムなゲノムを持つ車の第1世代を作成し、それがどのように振る舞うかを示します。 約40世代になると、車は自己駐車を学習し始め、駐車スペースに近づくようになります。 より挑戦的な開始点での別の例です。 ええ、車は途中で他の車にぶつかったり、駐車スペースに完璧に収まらなかったりしますが、これは彼らにとって世界の創造以来わずか40世代目なので、寛容になって成長する余地を与えてください :D ブラウザで直接進化のプロセスを確認できる🚕 Self-parking Car Evolution Simulator を起動できます。 シミュレーターは以下の機会を提供します。 ゼロから車を訓練し、遺伝的パラメータを自分で調整できます。 訓練された自己駐車車が動作している様子を見ることができます。 手動で車を駐車することも試すことができます。 このプロジェクトの遺伝的アルゴリズムはTypeScriptで実装されています。完全な遺伝的ソースコードはこの記事で示しますが、Evolution Simulator リポジトリで最終的なコード例を見つけることもできます。 特定のタスクである車のゲノムを進化させるために遺伝的アルゴリズムを使用します。しかし、この記事はアルゴリズムの基本に触れるだけで、遺伝的アルゴリズムのトピックに関する完全なガイドではありません。それを踏まえた上で、さらに詳しく見ていきましょう... 計画 自己駐車車を作成するという高レベルのタスクを、180ビットの最適な組み合わせを見つける（最適な車のゲノムを見つける）という単純な低レベルの最適化問題に段階的に分解していきます。以下に、私たちがこれから行うことを示します。 💪🏻 車に筋肉（エンジン、ステアリングホイール）を与え、駐車スペースに向かって移動できるようにします。 👀 車に目（センサー）を与え、周囲の障害物を見えるようにします。 🧠 車が見ているもの（センサー経由の障害物）に基づいて筋肉（動き）を制御する脳を与えます。脳は単純に pure function movements = f(sensors) となります。 🧬 正しい動きをできるように脳を進化させます。ここで遺伝的アルゴリズムを適用します。世代を重ねるごとに、私たちの脳の関数 movements = f(sensors) は、車を駐車スペースに向かって動かす方法を学習します。 車に筋肉を与える 移動できるようにするために、車には「筋肉」が必要です。車に2種類の筋肉を与えましょう。 エンジン筋肉 - 車を ↓ 後退、↑ 前進、または ◎ ニュートラル（停止）させることができます。 ステアリングホイール筋肉 - 車を ← 左折、→ 右折、または ◎ 直進させることができます。 これらの2つの筋肉により、車は以下の動きを実行できます。 私たちのケースでは、筋肉は100ミリ秒（ms）ごとに脳から送られてくる信号の受信機です。脳からの信号の値に基づいて、筋肉は異なるように動作します。以下で「脳」の部分を説明しますが、今のところ、私たちの脳は各筋肉に -1、0、または +1 の3つの可能な信号しか送れないとしましょう。 type MuscleSignal = -1 | 0 | 1; 例えば、脳がエンジン筋肉に +1 の値を持つ信号を送ると、車は前進し始めます。エンジンへの信号 -1 は車を後退させます。同時に、脳がステアリングホイール筋肉に -1 の信号を送ると、車は左に曲がります。 ここでは、筋肉信号の値が筋肉の動作にどのようにマッピングされるかを示します。 MuscleSignal = -1 Signal = 0 Signal = +1 Engine ↓ 後退 ◎ ニュートラル ↑ 前進 Steering wheel ← 左折 ◎ 直進 → 右折 Evolution Simulator を使用して、車を自分で手動で駐車してみてください。車の筋肉がどのように機能するかを確認できます。WASDキー（またはタッチスクリーンのジョイスティック）を押すたびに、これらの -1、0、+1 の信号がエンジンとステアリングホイールの筋肉に送信されます。 車に目を与える 私たちの車が筋肉を使って自己駐車を学習する前に、「周囲」を見ることができるようになる必要があります。8つの距離センサーの形で8つの目を与えましょう。 各センサーは、0〜4メートルの距離範囲で障害物を検出できます。各センサーは、100ミリ秒ごとに、それが「見ている」障害物に関する最新情報を車の「脳」に報告します。センサーが障害物を見つけられない場合、値0を報告します。逆に、センサーの値がゼロではないが小さい場合（例: 0.01m）、障害物が近いことを意味します。 Evolution Simulator を使用して、障害物との近さに応じて各センサーの色がどのように変化するかを確認できます。 type Sensors = number[]; 車に脳を与える この時点で、私たちの車は「見ること」と「動くこと」ができますが、「目」からの信号を「筋肉」の適切な動きに変換する「コーディネーター」がいません。車に「脳」を与える必要があります。 脳の入力 センサーからの入力として、100ミリ秒ごとに脳は8つの浮動小数点数を受け取ります。それぞれが [0...4] の範囲です。例えば、入力は次のようになります。 const sensors: Sensors = [s0, s1, s2, s3, s4, s5, s6, s7]; // 例: 🧠 ← [0, 0.5, 4, 0.002, 0, 3.76, 0, 1.245] 脳の出力 100ミリ秒ごとに、脳は2つの整数を出力する必要があります。 エンジンの信号となる1つの数値: engineSignal ステアリングホイールの信号となる1つの数値: wheelSignal 各数値は MuscleSignal 型であり、-1、0、または +1 の3つの値のいずれかを取ることができます。 脳の数式/関数 上記で述べた脳の入力と出力を念頭に置くと、脳は単なる関数であると言えます。 const { engineSignal, wheelSignal } = brainToMuscleSignal( brainFunction(sensors) ); // 例: { engineSignal: 0, wheelSignal: -1 } ← 🧠 ← [0, 0.5, 4, 0.002, 0, 3.76, 0, 1.245] ここで、brainToMuscleSignal() は生の脳信号（任意の浮動小数点数）を筋肉信号（-1、0、または +1 の数値）に変換する関数であり、筋肉がそれを理解できるようにします。この変換関数は以下で実装します。 主な疑問は、brainFunction() がどのような種類の関数であるかということです。車をより賢く、その動きをより洗練されたものにするために、多層パーセプトロン（Multilayer Perceptron）を使用することができます。名前は少し怖いかもしれませんが、これは単純なニューラルネットワークのアーキテクチャです（多くのパラメータ/係数を持つ大きな数式と考えてください）。私は homemade-machine-learning、machine-learning-experiments、nano-neuron プロジェクトで多層パーセプトロンについて詳しく説明しました。簡単なネットワークで、書かれた数字を認識するように挑戦することもできます。 しかし、ニューラルネットワークという全く新しい概念を導入するのを避けるために、はるかに単純なアプローチを採用し、複数の変数を持つ2つの線形多項式を使用します（より正確には、各多項式は8つのセンサーがあるため、ちょうど8つの変数を持つことになります）。これは次のようになります。 engineSignal = brainToMuscleSignal( (e0 * s0) + (e1 * s1) + ... + (e7 * s7) + e8 // <- brainFunction ) wheelSignal = brainToMuscleSignal( (w0 * s0) + (w1 * s1) + ... + (w7 * s7) + w8 // <- brainFunction ) ここで： [s0, s1, ..., s7] - 8つの変数であり、8つのセンサー値です。これらは動的です。 [e0, e1, ..., e8] - エンジン多項式の9つの係数です。これらは車が学習する必要があり、静的です。 [w0, w1, ..., w8] - ステアリングホイール多項式の9つの係数です。これらは車が学習する必要があり、静的です。 脳に単純な関数を使用することの代償は、車が洗練された動きを学習できず、未知の環境への一般化や適応もあまりできないことです。しかし、私たちの特定の駐車場のタスクと、遺伝的アルゴリズムのデモンストレーションという目的のためには、これで十分でしょう。 ジェネリックな多項式関数は次のように実装できます。 type Coefficients = number[]; // 係数と変数に基づいて線形多項式の値を計算します。 const linearPolynomial = (coefficients: Coefficients, variables: number[]): number => { if (coefficients.length !== (variables.length + 1)) { throw new Error('Incompatible number of polynomial coefficient