RoboCupサッカーシミュレーションにおける今後の研究課題 秋山英久

Presentation on theme: "RoboCupサッカーシミュレーションにおける今後の研究課題 秋山英久"— Presentation transcript:

1 RoboCupサッカーシミュレーションにおける今後の研究課題 秋山英久

2 サッカーシミュレーションリーグ（2D） の歴史

3 RoboCup97 開催地 ： 名古屋 優勝 ： AT-Humboldt

4 〜1997 どのチームもまだプログラムを作り込めてい ない シミュレータのパラメータ調整が不十分 そもそも，サッカーのルールの実装も不十分
その代わり，研究志向の強いチームは多かっ た 強化学習によるポジション獲得 GPによる行動ルール獲得 ...

5 開催地 ： パリ （フランス） 優勝 ： CMUnited （アメリカ ） RoboCup98 キーパ導入 オフサイド導入
sserver-4.x キーパ導入 オフサイド導入

6 開催地 ： ストックホルム （ スウェーデン） 優勝 ：CMUnited （アメリカ ） RoboCup99 sserver-5.x
プレイヤのサイズ縮小 首の角度導入 オンラインコーチ導入

7 〜1999 Peter Stoneによる連覇 Layered Learning Layered ディスクロージャ ビジュアルデバッガの走り
Locker Room Agreement 結局は，個体の能力が全ての時代

8 優勝 ： FCPortugal（ポルト ガル）
RoboCup2000 開催地 ： メルボルン （オー ストラリア） 優勝 ： FCPortugal（ポルト ガル） sserver-6.x 秋山，ATeamで初参加 ３敗で終了 概ねCMUnitedベース

9 〜2000 FCPortugalが初出場初優勝 現在主流のフォーメーションシステム (SBSP)が完成 チームワークをパラメータで表現
ポジションチェンジ（DPRE）の実現 コミュニケーションの最大活用 キック列の探索を最適化問題として捉え， ランダム探索＋山登り法で解決 ビジュアルデバッガ Brainstormers 強化学習によるスキル獲得 Brainstormersがベースコードを公開

10 開催地 ： シアトル （USA） 優勝 ： TsinguAeolus（中国 ） RoboCup2001 sserver-7.x
プレイヤのキック能力向上，へテロプレ イヤの導入 コーチ言語（CLang）導入 秋山，ATeamで参加 二次予選敗退 一部CMUnitedベース + いくつかの独自 コード投入

11 〜2001 TsinguAeolusが初出場初優勝 再び，個人能力の時代 （当時としては）驚異的なドリブル能力 強力な足回り
UvA Trilearnがベースコードを公開

12 開催地 ： 福岡 優勝 ： TsinguAeolus（中国） RoboCup2002 秋山，HELIOSで参加 ベスト8 ほぼ独自開発
rcssserver-8.x 秋山，HELIOSで参加 ベスト8 ほぼ独自開発 Soccer Viewer を使用開始

13 〜2002 TsinguAeolus2001が公開したソースを使用したチ ームが大量発生 TsinguAeolusのコピーチームが準優勝
UvA Trilearnがベースコードを公開

14 優勝 ： UvA Trilearn（オラン ダ）
RoboCup2003 開催地 ： パドヴァ（イタリア ） 優勝 ： UvA Trilearn（オラン ダ） rcssserver-9.x 競技の自動実行開始 秋山，HELIOSで参加 ベスト8 完全に作り直し．ほぼ現在のlibrcscの形 に

15 〜2003 トータルバランスに優れたUvA Trilearnが優勝 優勝チームでも失点するようになった．
以降，UvA Baseとして多くのチームが利用 パーティクルフィルタによる位置測定 現在では，Brainstormersなども導入 精度は良いが，かなりCPUを食う

16 開催地 ： リスボン（ポルトガ ル） 優勝 ： STEP（ロシア） RoboCup2004 秋山，TokyoTechSFCで参加
3Dリーグ開始 秋山，TokyoTechSFCで参加 予選免除，二次予選敗退 へテロを使いはじめた以外，特に進歩無 し

17 〜2004 三度，個人能力の時代 ドリブル突破技術の向上 STEP，UvA，RoboSina などが驚異的なドリブ ル突破能力を見せる
論文化された情報は特に無し． 恐らく，オンライン探索を行っている

18 優勝 ： Brainstormers（ドイ ツ）
RoboCup2005 開催地 ： 大阪 優勝 ： Brainstormers（ドイ ツ） rcssserver-10.x 秋山，TokyoTechSFCで参加 予選１位通過， ３位 フォーメーションシステムの刷新．中盤 の支配率向上 soccerwindow2の使用開始

19 〜2005 本格的なスルーパス（WrightEagle）の登場 パスが出る前から走り込み
動的ポジショニング（Brainstormers）の登場 固定的なフォーメーションを持たない，完全なマ ンツーマンディフェンス Brainstormersがベースコードを公開

20 開催地 ： ブレーメン（ドイツ ） 優勝 ： WrightEagle（中国） RoboCup2006 秋山，TokyoTechSFCで参加
予選免除， 4位 フォーメーションシステムを改良するも ，他は特に進歩無し 全ソースコードをリリース

21 〜2006 WrightEagle2005の影響により，全体的に中盤での守 備が向上 個体の基本スキルはほぼ頭打ち
〜2006  WrightEagle2005の影響により，全体的に中盤での守 備が向上 個体の基本スキルはほぼ頭打ち しかし，戦略的な進歩は停滞気味 恐らく，ほとんどのチームが守備に注力していた ため

22 2007〜  より人間の現代サッカーに近付いて，動 的なポジショニングを行えるかどうかが 重要になるのではと予想

23 チーム開発における課題

24 ワールドモデルの再構成 プレイヤのマッチング ゴーストオブジェクトの検出 コミュニケーションによる更新 認識精度の向上は極めて重要であるはず なのに，何故かあまり研究対象になって いない

25 サッカープレイヤとしての基本スキル インターセプト（ボール捕捉） キック パス，シュート探索 マーク ．．．

26 インターセプト もっとも重要なスキル ボールの軌道，及び，自分を含めた全プ レイヤの位置の予測 高速計算するアルゴリズムが必要 ノイズ処理 戦略的に有利な位置でトラップ（スマー トインターセプト）するためのプランニ ングが必要

27 スマートインターセプト 主に二つの目的 ターン回数を減らし，先回りすること で，ミスを減らす 攻撃的プレイヤがより前方でトラップ 戦術的に有利なトラップ位置を求めるこ とはかなり難しい

28 敵に妨害されるかも知れないが，あえて トラップ動作を遅れさせた方が良い場合 も
有利なトラップ位置を求めるには 敵に妨害されない範囲の予測 敵に妨害されるかも知れないが，あえて トラップ動作を遅れさせた方が良い場合 も 普通に学習させようとしても獲得できない そもそも，敵の妨害範囲を予測すること 自体が難しい 厳密に予測しようとすると，選択肢が無く なる

29 キック ボールに必要な速度を与えるために，複 数回の連続したキックが要求される 適切なキック列の動的な探索が必要 敵の妨害を回避するための予測が必要

30 キック列の例

31 キック列の例（敵の回避）

32 TsinguAeolusの方法がほぼベスト Q学習によるヒューリスティック獲得 オンラインでのA*探索
キック列の探索アルゴリズム TsinguAeolusの方法がほぼベスト Q学習によるヒューリスティック獲得 オンラインでのA*探索 資料の準備が間に合わなかったので説明は割 愛 librcscでは割と単純な再帰的探索 敵による妨害範囲の予測が必要

33 ドリブル 局面の打開のために必要なスキル 敵の妨害を回避するためのプランニング
最近は，ゴール前で密集するディフェンダ を回避できるかいなかが得点能力に直結 動的な探索が必要 へテロプレイヤへの対応 スムーズな移動 敵の妨害を回避するためのプランニング

34 最近は，複数のパターンを予測して，も っとも遠くへ辿り着けるキックを探索す る手法が主流
ドリブルの探索 最近は，複数のパターンを予測して，も っとも遠くへ辿り着けるキックを探索す る手法が主流 Branstormers05のベースソースなど CPUは消費するが，確実 回避の判断に改良の余地が大いに有り 回避動作が必要かいなか どの方向に回避するか 敵による妨害範囲の予測が必要

35 探索時に観測されていなかったプレイヤ の予測が困難
パス，シュートの探索 基本的に， 複数のボール初速度のパターンを生成し， ある初速度のボールに対して，敵の方が味 方よりも早く到達するかどうかを， 可能なかぎり厳密に計算しなければならな い 計算量が膨大 Newton法による高速計算 探索時に観測されていなかったプレイヤ の予測が困難

36 特定のチームやプレイヤの癖を検出でき れば更に有利 意思決定の全てに関わる重要な情報のは ずなのに，ほとんど研究されていない
敵の行動範囲の予測 良くある対処 妨害動作をしそうなプレイヤへの注目 コミュニケーションによる情報共有 最後に観測した位置から移動範囲を予測 特定のチームやプレイヤの癖を検出でき れば更に有利 意思決定の全てに関わる重要な情報のは ずなのに，ほとんど研究されていない

37 プレイヤの意図の予測 パスの誘発 行動のサポート レシーバ側の動きをパサーが察知でき
スタミナ切れで動けない味方とのポジショ ン チェンジ，など 敵プレイヤのマーク 対象プレイヤがどこに向かおうとしている のか，など

38 その他の課題

39 良いものができれば，論文でも参照され まくっておいしいはず
評価方法 標準と言える評価基準が存在しない ツールはいくつか存在するが，基準はまっ たく統一されていない 実際のサッカーにも定量的な評価指標があ るのだから，できるはず 行動の識別ルールが存在しない パスの定義，ドリブルの定義…などなど 良いものができれば，論文でも参照され まくっておいしいはず なので，誰かやりませんか?

40 開発用リソース ライブラリ開発サイト 配布サイト
配布サイト

41 最近やっていること Delaunay三角分割を利用した フォーメーション獲得

42 問題設定 入力 ： 注目点の座標(x,y) 出力 ： プレイヤが移動すべき位置座標(x,y) × N
今のところ，多次元入出力を扱わない．3 次元への拡張は，恐らく問題無く可能

43 適用方法 ２入力，２出力の関数近似器を用意 関数近似器はエージェントごとに独立に獲 得
関数近似器は全エージェントでまとめて管 理，ユーザからは，2入力，2 x N出力の関 数に見える． 人間が教師データを作成 GUIの専用ツールを使用 現在，ふたつの手法を実装済み ニューラルネットによる関数近似 Delaunay三角分割＋線形補間

44 GUIの教示ツール

45 ニューラルネットによる関数近似 非常に一般的なフィードフォワード型の3層 ニューラルネットワークを使用 入力層ユニット数: ２
中間層ユニット数: （シグモイド関数） 出力層ユニット数: ２ （シグモイド関数 ）

46 利点と欠点 利点 実装が容易な割りにそこそこ上手く動く 欠点 学習パラメータの手動調整が必要 学習率，中間層のユニット数，など
細かい修正が効かない．思いどおりに動か せない． 過学習 ひとつの訓練データが全体へ影響 サンプルの間隔に結果の精度が大きく影 響される．サンプルを与えすぎてもダメ

47 三角分割を利用した関数近似 領域の三角形分割と線形補間を組合せ，離散 的なサンプルから近似関数を得る方法を提案 ．
領域の分割法として，Delaunay三角分割を 使用 補間法として，3DCGのシェーディングアル ゴリズムを使用

48 三角分割の例 赤点と赤線がDelaunay三角分割 破線がVoronoi図

49 線形補間の手順 ボールを含む三角形を探す 三角形の各頂点が保持する，プレイヤの移動 目標位置座標を得る．
それら3出力を，3頂点からの距離に応じた線 形補間で合成する．

50 線形補間の手法 グローシェーディングアルゴリズム 3DCGにおける陰影付け手法の一つ Icを求める
𝐼 𝑎 = 𝐼 1  𝐼 2 − 𝐼 1  𝑦 𝑎 − 𝑦 1 𝑦 2 − 𝑦 1 𝐼 𝑏 = 𝐼 1  𝐼 3 − 𝐼 1  𝑦 𝑏 − 𝑦 1 𝑦 3 − 𝑦 1 𝐼 𝑐 = 𝐼 𝑎  𝐼 𝑏 − 𝐼 𝑎  𝑥 𝑐 − 𝑥 𝑎 𝑥 𝑏 − 𝑥 𝑎

51 特徴 k-NN法とは異なり，必ずしも最近傍のサンプ ルが選ばれるわけでは無い． 現在の注目点を含む三角形の3頂点しか考 慮されない．
個々のサンプルの独立性が非常に高くなり ，局所的な変更が極めて容易 概念的には，基底関数による関数近似に近い 人間が見ても理解できる 逐次追加が可能

52 利点と欠点 利点 学習にかかるコストは，三角分割にかかる 計算だけ． 100%の再現性．教師データが確実に反映さ れる．
任意の対象領域に対応可能 人間が容易に介在可能 欠点 ボールと移動目標位置 との対応が一意に定 まっている教師データが必要． 複雑な非線型関数を精度良く近似しようと すると，必要な三角形の数が膨大になる．

53 現在，取り組み中 フォーメーションの自動獲得 チーム戦術との融合

54 サーバとの通信と同期 純粋にソフトウェア開発の問題 rcssserverの仕様や環境に合わせたチューニン グが必要 librcscで実装済み

55 メッセージ解析 純粋にソフトウェア開発の問題 S式パーザが必要 librcscで実装済み flex/bisonで作り直したい
(see 187 ((g r) ) ((f g r b) ) ((f g r t) ) ((f p r c) ) ((f r 0) ) ((f r t 10) ) ((f r t 20) ) ((f r t 30) ) ((f r b 10) ) ((b) ) ((p "HELIOS" 10) –39 t) ((p "YowAI2002") ) ((p "YowAI2002" 3) ) ((p "YowAI2002") 30 -6) ((p "YowAI2002" 6) ) ((P) 2 130) ((l r) ))

56 位置測定 世界的にはUvAのパーティクルフィルタが有 YowAIのテーブル方式が高速でお薦め

57