ロボットが単にスクリプトに従うだけでなく、他のロボットが何を考えているかを実際に考える世界を想像してみてください。これは、機械が互いに衝突することなく混雑した空間をナビゲートできるようにすることに特化した、マルチエージェント・モーションプランニングというロボット工学の一分野です。この課題を理解するために、信号機がなく、誰も会話をしていない忙しい交差点を思い浮かべてください。車が左折しようとする際、対向車が加速するのか、それとも減速するのかを推測しなければなりません。かつて、ロボットはしばしば「慎重すぎるドライバー」のように振る舞い、100%確信が持てるまで決して動こうとしませんでした。これが、交通渋滞（グリッドロック）を引き起こします。これを解決するために、科学者たちは経済学の概念である「ゲーム理論」、特に「ナッシュ均衡」を探求しています。これは、他の全員が何をしているかを踏まえた上で、自分の動きを変えても状況が悪化するだけなので、誰も戦略を変えたくない状態のことを指します。それは、誰も足をふみつけないように、完璧にリハーサルされたダンスのように、全員の戦略が完璧に調和している絶妙なバランスの状態です。

大きな疑問は、物理法則（車の曲がりやすさなど）によって数学が非常に複雑になる中で、どのようにしてロボットにこの「完璧なステップ」をリアルタイムで見つけさせるかということです。イスラエル工科大学の研究者による新しい論文は、「ゲーム理論的ネステッド・サーチ（GTNS）」と呼ばれる巧妙な解決策を紹介しています。彼らは、従来の手法が局所的な「行き止まり」に陥るか、あるいはあらゆる可能な動きを計算するのに時間がかかりすぎる一方で、彼らの新しいアプローチは「超スマートな探偵」のように機能することを発見しました。膨大でスキャン不可能なライブラリの中からすべての可能性をチェックする代わりに、GTNSは「ネステッド（入れ子構造）」戦略を使用します。これは、最適な全体経路を探す「外側の探索」を行いますが、同時に、単一のロボットが勝手に動きを変えて自分だけより良くできるかどうかを確認する素早い「内側のテスト」を常に実行します。もしロボットが「逸脱してより良い結果を得られる」可能性があるなら、その経路は即座に破棄されます。これにより、システムは、車が積極的に車線に割り込んだり、レーサーが他の車を追い越したりといった、複雑で現実的な相互作用を、標準的なノートパソコン上でわずか数秒で見つけることができます。

問題点：ロボットのジレンマ

3人の友人とビデオゲームをしている場面を想像してください。皆がゴールを目指していますが、道は狭く、お互いに会話をすることはできません。もし全員が前へ突進しようとすれば、衝突してしまいます。もし全員が止まって待っていたら、ゴールには一生たどり着けません。現実の世界では、自動運転車やレーシングドローンがまさにこの問題に直面しています。彼らは他者が何をしようとしているかを予測し、即座に反応する必要があります。

長い間、ロボットは「リーダーに従う」か、あるいは過度に慎重に振る舞うことでこの問題を解決してきました。彼らは他者が何をしようとしているかを推測し、安全な経路を選び、あとはうまくいくことを祈るだけでした。しかし、これは、空の交差点で動くのを恐れて永遠に待ち続ける車のような、愚かな状況を招くことがよくありました。他の手法は、完璧なバランス（ナッシュ均衡）を見つけるために複雑な数学を使用しようとしましたが、局所的な罠に陥ったり、ロボットが障害物やトリッキーなターンを扱えないほど世界を簡略化しすぎたりすることがよくありました。

解決策：2つの虫眼鏡を持つ探偵

この論文の著者であるアヴィシャブ・エンゲルとそのチームは、**ゲーム理論的ネステッド・サーチ（GTNS）**と呼ばれる新しいアルゴリズムを構築しました。その仕組みを理解するために、巨大な多層ビル（「探索空間」）の中で謎を解こうとしている探偵を想像してみてください。

1. 外側の探索（探偵）： 探偵は建物の中を歩き回り、出口への最適なルートを探します。これが「外側」のレイヤーです。これは、最短経路を見つけようとする標準的なGPSのようなものです。
2. 内側の探索（尋問）： しかし、ここにはひねりがあります。探偵が新しいルートを検討するたびに、立ち止まって決定的な問いを投げかけます。「もし私がこのシナリオの一人だったら、他の全員が元の経路を維持しているとしても、もっと速くなるようなショートカットを使ってこっそり抜け出すことはできるだろうか？」
   • これが「内側」のレイヤーです。これは、関与するすべてのロボットに対する、素早く焦点を絞ったチェックです。
   • もし答えが「はい、私は逸脱して勝利できる」であれば、探偵はこのルートが真のナッシュ均衡ではないと判断します。そして、そのルートは即座に破棄されます。
   • もし答えが「いいえ、これ以上良くすることはできない」であれば、そのルートは安全でバランスが取れています。

この「ネステッド（入れ子）」アプローチが強力なのは、明らかに不安定な経路に時間を浪費しないからです。植物がより速く成長できるように、庭師が枯れた枝を切り落とすように、悪い選択肢を早期に排除（プルーニング）します。

彼らが発見したこと：積極的な合流から礼儀正しい譲り合いまで

研究者たちは、高速道路での合流からレーストラックでの追い越しまで、さまざまなシナリオでアルゴリズムをテストしました。彼らは、システムのいくつかの「つまみ」を調整することで、ロボットの性格を変えられることを見出しました。

• 「ジップ・マージ（連続合流）」： ある実験では、設定を調整してロボット1（青い車）をより攻撃的にしました。その結果、ロボット1は2台の車の間の狭い隙間にうまく入り込むことに成功しました。これは「ジップ・マージ」として知られる操縦です。
• 「ポライト・イールド（礼儀正しい譲り合い）」： 設定を逆にして、ロボット1をより慎重にした場合、ロボット1は他の車が通り過ぎるのを待ってから合流しました。
• 「レーストラック」： レースのシミュレーションでは、優先順位の数値を変更するだけで、誰がレースに勝つかを決定できました。もしロボット1が高い優先順位を持っていれば、インコースを取って勝利しました。もしロボット2が優先順位を持っていれば、役割は逆転しました。

これらが特別なのは、これらが単なるランダムな推測ではないからです。アルゴリズムは、その解が真のナッシュ均衡であることを保証します。これは、一度ロボットが動き出せば、他の全員が行っている最善の策を踏まえた上で、突然考えを変えて進路を逸脱する理由が誰もなくなることを意味します。

スピードと現実性

チームは、強力なプロセッサ（Intel Core i9）を搭載した標準的なノートパソコンでこれらのシミュレーションを実行しました。結果は素晴らしいものでした。

• 単純なシナリオでは、コンピュータは1秒足らずで解を見つけました。
• より複雑なマルチロボットの高速道路合流などのシナリオでは、数秒（いくつかのケースでは約3〜4秒）かかりました。
• ロボットの数を増やしたり、経路を長くしたりしても、古い手法ほど速度は低下しませんでした。

論文では、数学を成立させるためにロボットの物理特性を簡略化する（例えば、瞬時に回転できる点として扱うなど）必要はないという考えを明確に否定しています。GTNSは、車の速度制限や旋回半径を含む、車の物理的な複雑さを扱います。

なぜ重要なのか

これは単なる理論上のゲームではありません。これらの相互作用を迅速に計算できる能力は、将来、自動運転車が交通渋滞や事故を引き起こすことなく、混雑した街路をナビゲートできることを意味します。彼らは、信号機や無線信号を必要とせずに、交差点での優先権を交渉できる可能性があります。

研究者たちはまた、彼らの手法がAIの学習データ生成にも利用できると指摘しています。これらの「完璧にバランスの取れた」相互作用を数千回シミュレートすることで、他のAIシステムに安全かつ予測可能な振る舞い方を教えることができます。

現在のシステムは、ロボットの経路が事前に計画されている（「オープンループ」の設定）場合に最もよく機能しますが、著者らはこれが大きな前進であると述べています。初期のマッピングを作成するには時間がかかることを認めていますが、一度構築されれば、システムは高速で信頼できます。彼らは、より多くのロボットを用いた、あるいはロボットが変化に即座に反応しなければならないリアルタイムの「クローズドループ」状況において、さらに性能を向上させる方法をすでに模索しています。

要約すると、GTNSはロボットに「場の空気」を読み、誰も衝突したり永遠に待ったりすることなく、全員が勝利できる解決策を見つける能力を与えます。それは、混沌とした交通のダンスを、瞬時に計算された振り付けのあるパフォーマンスへと変えるのです。