【Grasper】逃走者をAIで追跡する新技術

Multiagent Systems 2024年10月09日

3つの要点
✔️ 初期条件の異なる追跡・逃走ゲームに対応できる、GNN、ハイパーネットワーク、観測表現層から成る一般化フレームワーク「Grasper」を提案しました。
✔️ GraphMAEによる事前学習、ヒューリスティック誘導マルチタスク事前学習(HMP)などから成る、効率的な3段階学習手順を開発しました。
✔️ 実験により、Grasperが従来手法を上回る高い性能と汎用性を持つことを実証し、初期条件の違いに強い追跡者方策を短時間で生成できることを示しました。

Grasper: A Generalist Pursuer for Pursuit-Evasion Problems
written by Pengdeng Li, Shuxin Li, Xinrun Wang, Jakub Cerny, Youzhi Zhang, Stephen McAleer, Hau Chan, Bo An
(Submitted on 19 Apr 2024)
Comments: To appear in the 23rd International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2024)
Subjects: Artificial Intelligence (cs.AI); Computer Science and Game Theory (cs.GT); Multiagent Systems (cs.MA)

code：

本記事で使用している画像は論文中のもの、紹介スライドのもの、またはそれを参考に作成したものを使用しております。

はじめに

近年、多くの追跡者チームと逃げ回る1人の逃走者の間の追跡ゲームをモデル化した、「追跡・逃走ゲーム」が注目を集めています。都市の道路網などのグラフ上で行われるこのゲームの戦略を効率的に見つけることは、実世界の都市セキュリティにおける犯罪者の早期検挙など、様々な応用が期待できます。

しかし、従来の手法は特定の初期条件(プレイヤーの初期位置や出入り口の設定など)に依存しており、現実の犯罪現場ではこれらの条件が常に変化するため、現行のアルゴリズムでは毎回計算しなおす必要があり非効率的でした。そこで本論文では、「Grasper」と名付けられた新しいフレームワークを提案しています。

Grasperは初期条件に応じて追跡者の戦略を生成できる、汎用性の高いシステムです。グラフニューラルネットワークで初期条件を埋め込みベクトルに変換し、ハイパーネットワークでその埋め込みから追跡者の行動方針を生成します。さらに、効率的な3段階学習手順と、ヒューリスティック法で導かれる参照方針を用いた新規の事前学習法を開発しています。

様々なマップ上での実験で、Grasperは従来手法を大きく上回る性能と汎用性を示しました。初期条件が変わっても、ワンクリックで新しい状況に特化した戦略を生成できるGrasperは、実社会への実装が期待できる革新的な追跡・逃走ゲームソルバーなのです。

提案手法(Grasper)

Grasperは追跡・逃走ゲームの初期条件の違いに対応できる、汎用的な追跡者方策生成フレームワークです。主な構成要素は以下の3つです。

グラフニューラルネットワーク(GNN)

追跡・逃走ゲームの初期条件(プレイヤーの開始位置、出入り口の位置など)をグラフに埋め込み、そのグラフをGNNに入力することで隠れ状態ベクトルを得ます(図1(a)(b))。

ハイパーネットワーク

上記の隠れ状態ベクトルと時間horizonを入力とし、そのゲームに特化した追跡者の基本方策をパラメータ生成します(図1(c))。

観測表現層

追跡者の観測(プレイヤーの位置など)を埋め込みベクトルに変換する層です。

Grasperでは、以下の3段階の効率的な学習手順を採用しています。

(1) 事前事前学習：GraphMAEなどのSelf-Supervised法を用いてGNNをグラフデータから予め学習します。
(2) 事前学習：新規のヒューリスティック誘導マルチタスク事前学習(HMP)により、ハイパーネットワークと観測表現層を学習します。ヒューリスティクス(ダイクストラ法など)から導出した参照方策を用いて追跡者方策を正則化することで、探索効率を高めています。
(3) 微調整：PSROアルゴリズムの各イテレーションにおいて、ハイパーネットワークから生成された基本方策を初期化に用いて、追跡者の最適応答方策を微調整します。

このように、Grasperはグラフ表現、ハイパーネットワーク、効率的な学習手順を組み合わせることで、追跡・逃走ゲームの一般化問題に取り組む革新的な手法となっています。

実験

図3は、Grasperと従来手法の性能を比較した結果です。縦軸が追跡者の最悪ケース効用値、横軸が実行時間を表しています。
- Grasperは全てのマップにおいて、事前学習時間を加えた上でも従来手法より高い収束値と安定した性能を示しています。
- 特に分布外テストセット(I2)において、Grasperの汎化性能が際立っています。
- 図の傾きから、Grasperは従来手法に比べ、PSROの各イテレーションでの方策改善が格段に速いことが分かります。

表1は、提案手法の重要な構成要素であるHMP(ヒューリスティック誘導マルチタスク事前学習)と観測表現層(Rep.)の有効性を確認した結果です。
- HMPと観測表現層の両方を使った場合のみ、高い効用値と小さな標準偏差が得られていることが分かります。
- つまり、これら2つの新規手法が両方とも不可欠であることが示されています。

考察

- Grasperの高性能と安定性は、初期条件に応じて追跡者の方策を出力できる構造的な特長に由来します。
- 特に、初期条件の異なるゲームにおいて、従来手法の性能が大きく低下するのに対し、Grasperは頑健に高精度な解を出力できています。
- 事前学習時間を加えても最終的な収束時間が従来手法より速いのは、高品質な初期化と高速な方策改善が可能なためです。- HMPにより、無作為探索を抑え、ヒューリスティクスに基づく探索効率の改善が達成されています(図2)。- さらに図5は、Grasperが逃走者の初期位置の違いに応じて、合理的な追跡者の効用値を出力できていることを示しています。