RoboCup サッカーにおけるセットプレイのマーク割当手法に関する検討

RoboCup

サッカーにおける

セットプレイのマーク割当手法の性能調査

A Study of Marking Assignment Methods in Set-Plays for

RoboCup Soccer

田中 翔

1∗

_{中島 智晴}

1

_{秋山 英久}

2

Sho Tanaka

1

_{and Tomoharu Nakashima}

1

_{and Hidehisa Akiyama}

2 1

_{大阪府立大学 工学研究科}

1

_{Graduate School of Engineering,   Osaka Prefecture University}

2

_{福岡大学 工学部電気情報工学科}

2

_{Depature of Electronics Engineering and Computer Science, Fukuoka University}

Abstract: RoboCup Soccer Simulation 2D League challenges teams to smartly and stably out-perform their opponents. Designing a reliable defense is important for reducing opportunities of the opponent to score points. The team developed by the authors uses a defense system called one-to-one mark system. During a set-play, the system builds assignment plans providing guidelines to the players about which opponent’s player to mark. From one assignment plan to another, targets that players have to mark can be reconsidered. If too much modification occurs, the markers only wander around the soccer field without having the possibility to reach their target. So, minimizing it would result in a more reliable defense. In this paper, we propose a method for reducing this time as lower as possible. First, the system groups opponent players according to their role and their distance to the ball. Then, the players are assigned to mark these groups while considering the distance separating them. Actually, experiments have been conducted to examine the performance of the proposed method. We observed promising results about the reduction of assignment modi-fication ’s frequency. On the other hand, the players seem to consume more stamina than before, due to not so effective opponent grouping method. Furthermore, the number of ball interceptions is not so advantageous than results of previous researches.

1

はじめに

ロボット工学と人工知能の領域横断型研究プロジェ クトとして RoboCup [1] が知られている．RoboCup に は様々なリーグが存在しており，それぞれ活発に研究， 開発が行われている．その中の 1 つである RoboCup サッカーでは，競技で勝利することが重要視され，た だ単に勝利するだけではなく，賢く安定して勝利する ことが望まれる．しかし，毎年各チームが変化を加え ることにより，多種多様な戦術が存在している．そのた め，安定した勝利のためにどのようなチームにも対応 できるよう手作業で改良を行っているが，改良は複雑 であり多大な労力を必要とする．そこで，試合中に相手 のチームに対応した意思決定を行う必要がある．チー ム戦略を決定する要因の一つとしてプレイヤの配置が ∗_{連絡先：〒 599-8531 大阪府堺市中区学園町 1 − 1} 大阪府立大学大学院工学研究科 田中 翔        E-mail: [email protected] ある．RoboCup サッカーでは，プレイヤの配置などに 関する研究が積極的に行われている．例えば，Luis ら [2] が提案した，Situation Based Strategic Positioning では，チームの戦術に応じたポジショニングが可能で ある．Akiyama ら [3] は，Delaunay 三角分割を用いた ボールの位置に基づく直観的にわかりやすいポジショ ニング手法を提案した．Kyrylov ら [4] は，守備時にお けるマンマークの最適化問題を多基準割り当て問題と して扱いパレート最適性を用いた協調的ポジショニン グ手法を提案している．Stone ら [5] は，マーク割当問 題において移動時の衝突を無くし，全プレイヤが到達 するまでに必要な時間の最小化を行う割当手法を提案 した．本論文では，RoboCup サッカーシミュレーショ ン 2D リーグにおける，相手側セットプレイ時のマー ク割当手法について考察する． 研究室で開発を進めているチームでは，相手側セッ トプレイにおいてグラフ理論における最小費用流問題

にフォード・フルカーソンのアルゴリズムを用いること でマーク割当案を作成している．しかし，マーク割当 案が味方プレイヤの移動中に変更されることで無駄な 移動をしているという問題がある．そこで，安定した マーク割当案を作成する必要がある．本研究では，マー ク対象となる敵プレイヤを分類し，その結果を用いる ことで安定した割当案の作成する．数値実験では，繰 り返し相手側のセットプレイを再現することで，マー ク割当手法の性能を調査する．

2

RoboCup

2.1

RoboCup サッカー

RoboCup は，ロボット工学と人工知能の発展を目 的とした自律移動型ロボットによるサッカーなどを題 材とした研究プロジェクトである．RoboCup には「西 暦 2050 年までに，サッカーの世界チャンピオンチー ムに勝てる自律型ロボットチームを作る」という目標 があり，この目標に向けて盛んに研究が行われている． RoboCup にはサッカーの他に，大規模災害への対応の シミュレーションや災害現場で活躍するロボットの開発 を促進するレスキュー，日常生活で人間を支援する自律 ロボットによる競技を通じて，人とコミュニケーション しながらより役に立つ仕事を行うロボットの実現を目 指す＠ホーム，次世代のロボット技術者育成を目的とし ているジュニアなどのリーグが存在する．本論文では， RoboCup サッカーシミュレーションリーグを研究の対 象とする．シミュレーションリーグは，RoboCup 創設 当初から存在する最も古いリーグの 1 つである．サッ カーシミュレーションでは，実機を使用せずに，コン ピュータ内に用意された仮想フィールド上でサッカー 競技を行う．サッカーシミュレーションはモデル化の 形式によって 2D リーグと 3D リーグに分けられる．図 1，図 2 に 2D リーグと 3D リーグの試合の様子を示す． 2D リーグでは，基本的な動作（キックやドリブルなど） はコマンドとして実装されている．そのため 2D リー グでは高レベルな意思決定を主な研究対象としている． 一方，3D リーグでは，エージェントはヒューマノイド ロボットで形成されているため，基本的な動作を関節 から制御する必要があり，基本的な動作が非常に重要 である．本論文では 2D リーグを扱う．

2.2

RoboCup サッカーシミュレーション

2D リーグ

2D リーグでは，二次元平面で表わされる仮想サッ カーフィールド上を，円形のプレイヤが競技している． x 軸はタッチラインと平行で，それに対し垂直な方向 図 1: 2D リーグの試合の様子 図 2: 3D リーグの試合の様子 を y 軸とする．また，タッチラインの長さは 105m で あり，ゴールラインの長さは 64m である．図 1 におい て左側のゴールを自陣側のゴール，右側のゴールを敵 陣側のゴールとし，自陣側から敵陣側へ行くに従い，x は増加するものとする．y 軸の値は上から下に行くに 従い増加するものとする．ボールやプレイヤの位置と 速度は全て二次元のベクトルとして表される．試合は 前後半 3000 サイクルずつ合計 6000 サイクルからなる． 1 サイクルは 0.1 秒で離散化されている．エージェント には，プレイヤ，オンラインコーチ，オフラインコーチ の 3 種類が存在する．これらはそれぞれ独立したエー ジェントとしてプログラムされる．プレイヤは，制限 された視覚情報や聴覚情報からドリブルやパス等の行 動選択を行う．オンラインコーチは，正確な情報の取 得やプレイヤへの情報伝達が可能であるが，プレイヤ への情報伝達において遅延の発生や回数などの制限が ある．オフラインコーチは，競技会での使用は不可能 であるが，チーム開発時にボールやプレイヤの再配置 による試合の再現が可能である．本論文では，プレイ ヤとオンラインコーチを使用する．現状，競技会に参 加するチームの多くは agent2d[6] をベースチームとし ている．agent2d には，競技会に参加するチームとし ての最低限の機能が備えられている．本論文の実験に

使用するチームの多くにもベースチームとして採用さ れている．

3

セットプレイ時のマーク割当問題

3.1

セットプレイ

セットプレイとは，一度ゲームを止めボールがセット された状態で再開するゲーム状態であり，ボールアウ ト，プレイヤによる反則，点の獲得時などに行われる． 本論文では，ボールアウトによって始まるセットプレ イを対象とする．特に，相手チームのキックでゲーム が再開されるセットプレイのみを取り扱う．通常，コー チの指示は発声コマンド発行後 50 サイクルの遅延後に プレイヤに届く．しかし，セットプレイではゲームが 一時停止しているため，遅延なしで指示を与えること が許されている．そのため，セットプレイにおいてオ ンラインコーチがフィールド情報を基にしたマーク割 当案をプレイヤに提供することで，プレイヤは各時点 における完全な情報に基づく意思決定が可能である．

3.2

マーク割り当ての重要性

研究室で開発を進めているチームでは，3.1 節で述 べた相手側セットプレイにおいて毎サイクルマーク割 当案を作成している．これは，ある時点で決定した割 当案が数サイクル後敵プレイヤが移動したときに適切 とは限らないためである．毎サイクル割当案を作成し ているため，マーキング担当が前サイクルから変更さ れることが頻繁に起こりうる．変更が頻繁に発生する と無駄な移動が多くなり，敵プレイヤのマークに付く 前にゲームが再開してしまう可能性がある．そのため， 作成したマーク割当案の変更回数が多ければ相手に有 利な状況になる可能性がある．実際に相手側に有利な 状況が生じた一場面を図 3 に示す．図 3 において，赤 い円形のエージェントが敵プレイヤであり，黄色い円 形のエージェントが味方プレイヤ，黒い円形の物体が ボールである．このとき味方プレイヤは決められた割 当案に従って目標位置に移動を試みたが，数サイクル 後に違う割当案が作成されたため，相手がボールを蹴 るまでに目標位置に移動が出来なかった．図 3 のよう な味方プレイヤと相手プレイヤとの位置関係では，相 手プレイヤ同士でのパスが容易であり，相手にとって 有利な状況である．そのため，安定したマーク割当案 を作成する必要がある．そこで，本研究では味方プレ イヤにマーク対象プレイヤを最適に割当する手法を提 案する． 図 3: 相手側に有利な状況例

4

マーク割当手法

従来手法 [7] では，マーク割当問題をグラフ理論にお ける最小費用流問題として定式化する．提案手法では， 従来手法を拡張したものである．まず，最小費用流問 題について述べ，その後に提案手法について述べる．

4.1

最小費用流問題

V を点集合，E を辺集合とする重み付き有向グラ フ G(V, E) があり，各辺 eij∈E (i = 1, 2, . . . , n，j = 1, 2, . . . , m，また n, m∈N) に対して容量 u(eij) とコス ト c(eij) が存在する．この有向グラフに対して始点 s∈V から終点 t∈V に流すフロー f が与えられたとき，コス ト最小化となる最大フローを求める問題である．辺 eij に流れるフローを x(eij) とすると，最小費用流問題は 次のように定式化される． min ( n ∑ i=1 m ∑ j=1 c(eij)x(eij)) (1) 0≤ x(eij)≤ u(eij) (2) n ∑ i=1 m ∑ j=1 x(eij)≤ f (3)

4.2

マーク割当問題に対する最小費用流問

題の適用

マーク割当問題において，点集合 V はマーキング担当 の味方プレイヤ i∈I(i = 1, 2, · · · , n，I は点集合，n∈N)， マーク対象となる敵プレイヤ j∈J(j = 1, 2, · · · , m，J は 点集合，m∈N)，および始点 s および終点 t を含むもの とし，辺集合 E は異なる点集合の要素を結ぶ辺 eijで 構成されている．また，s は i のみと辺を持ち，t は j

のみと辺を持つものとし，I∩J = ϕ とする．マーク割 当問題を，味方プレイヤ i が敵プレイヤ j をマークす るのに必要なコストを c(eij) とし，i が j のマーキング 担当候補であるかを表す容量 u(eij) とする最小費用流 問題とみなす．また，辺 eijは各点集合内に辺を持たな いため，有向グラフ G(V, E) は重み付き 2 部グラフと なる．この重み付き 2 部グラフにおいて，容量 u(esi) は i がマーキング担当であるかを表し，容量 u(ejt) は j をマークするのに必要な人数を表す．そして，この 2 部グラフに流すフロー f はマーキング担当である味方 プレイヤの人数を表す．このとき，マーク割当問題は 以下のように定式化される． min ( n ∑ i=1 m ∑ j=1 c(eij)x(eij)) (4) 0≤ x(eij)≤ u(eij) (5) n ∑ i=1 m ∑ j=1 x(eij)≤ f (6) u(epq) = { k if p∈J, q = t 1 otherwise (7) x(eij) = { 0 : i に j を割り当てない 1 : i に j を割り当てる (8) このとき，0≤ k ≤ m かつ k∈N である．このマーク 割当問題をフォード・ファルカーソンのアルゴリズム を用いることで解き，マーク割当案を作成する．

4.3

フォード・ファルカーソンのアルゴリズム

有向グラフにおいて最大フローを求めるために，フ ォード・ファルカーソンのアルゴリズム [8] を使用する． これは，重み付き 2 部グラフで表されるマーク割当問 題にも適用可能である．フォード・ファルカーソンの アルゴリズムの手順を以下に示す． 手順 1 ネットワークフローから残余ネットワークを作 成する． 手順 2 残余ネットワークを用いて始点 s から終点 t に フローを流すことの出来る経路（増加路）を探 索する． 手順 3 探索した経路にフローを流す． 手順 4 手順 1∼3 をフローが流れなくなるまで繰り返 す． 上記の手順 2 における増加路の探索では最短路探索を 行う．

4.4

提案手法

提案手法では，マーク対象となる敵プレイヤを分類 し，各グループに対して味方プレイヤを割り当てる．そ の後，各グループ内で敵プレイヤに味方プレイヤを割 り当てることにより割当案を作成する．提案手法の詳 細な手順を以下に示す．また，分類した際の状態を図 4 に示す． 手順 1 マーク対象となる敵プレイヤをボールとの距離 により分類（20m 間隔） 手順 2 分類したグループ内において，敵プレイヤ間で の x 座標の差が 10m 以上であるか確認し，10m 以上であれば敵プレイヤに FW，MF，DF と ラベルを付けさらにそのグループ内でラベル毎 に分割 手順 3 グループに対し味方プレイヤを割り当てる．こ のとき，グループ毎の容量はそのグループ内の 敵プレイヤの人数とする． 手順 4 割り当てた各グループ内でさらに敵プレイヤと 味方プレイヤを割り当てる． 上記の手順 3，手順 4 における味方プレイヤの割当に は従来手法を用いる． 図 4: 敵プレイヤの分類例 敵プレイヤのラベル付けの方法を以下に示す． • FW : 下記の手順に従ってラベル付けする． 手順 1 敵プレイヤの中で最も自陣側の敵プレイ ヤの x 座標を offense x とする． 手順 2 敵プレイヤそれぞれにおいて，offense x と敵プレイヤの x 座標の差に 1 を加えて たものを半径とする半円を作成する．こ

の時，半円の中心は（ offense x - 1, 敵 プレイヤそれぞれの y 座標 ）とし，弦は y 軸に対して平行であり，弧は敵陣側に 向かっているものとする． 手順 3 作成した半円内に注目している敵プレイ ヤ以外が存在していなければそのプレイ ヤを FW とする． • DF : 下記の手順に従ってラベル付けする． 手順 1 敵プレイヤの中で最も敵陣側の敵プレイ ヤの x 座標を defense x とする． 手順 2 敵プレイヤそれぞれにおいて，defense x と敵プレイヤの x 座標の差に 1 を加えて たものを半径とする半円を作成する．こ の時，半円の中心は（ defense x + 1, 敵 プレイヤそれぞれの y 座標 ）とし，弦は y 軸に対して平行であり，弧は自陣側に 向かっているものとする． 手順 3 作成した半円内に注目している敵プレイ ヤ以外が存在していなければそのプレイ ヤを DF とする． • MF : FW，DF 以外のプレイヤを MF とラベル 付けする．

5

数値実験

5.1

実験設定

提案手法と従来手法の性能を調査するため，提案手 法，従来手法をそれぞれ組み込んだ HELIOS2015 と 対戦相手 5 チーム（ CSU Yunlu（2015）, Gliders2015 （2015）, HfutEngine2015（2015）, Oxsy（2015）, YuSh an（2015））とのセットプレイを 1000 回再現する実 験を行った．実験用データとして，HELIOS2015 と対 戦相手 5 チームとの試合中に発生したセットプレイ開 始時の敵プレイヤ，味方プレイヤ，ボールの位置情報 をチーム毎に 100 種類用意した．用意した実験データ を，マーク割当手法毎に実験を行った．この際，味方 プレイヤへのマーク割当は毎サイクル行うものとし， 用いたコストは現在の敵プレイヤと味方プレイヤの 距離と現在の味方プレイヤと現在の味方プレイヤの フォーメーション位置の距離の線形和を用いた．HE-LIOS2015 は，本研究室で開発を行っているチームであ る．CSU Yunlu, Gliders2015, HfutEngine2015, Oxsy,

YuShan は，RoboCup 2015 に参加したチームである．

5.2

実験結果

移動効率を図る指標として味方プレイヤのマーク割 当変更回数とスタミナ消費量について調査し，守備能 力を図る指標としてボール奪取回数について調査した． まず，味方プレイヤのマーク割当変更回数について 調査した．味方プレイヤはセットプレイ開始後，相手 プレイヤがボールを蹴るまで毎サイクルマーク対象プ レイヤを割り当てられているため，マーク対象プレイ ヤの変更が生じる．マーク割当変更回数を，セットプレ イ開始からボールが蹴られるまでの間に生じた全味方 プレイヤにおける変更回数と定義する．マーク割当変 更回数が増加することで，無駄な移動によるスタミナ 消費量の増加や適切な位置への移動に必要なサイクル 数の増加が生じると考えられる．用意された実験デー タによる結果を，セットプレイ 1 回分の平均値として マーク割当変更回数をチーム，割当手法毎にまとめた 結果を表 1 に示す．

表 1: Number of changing assignment

Opponent Previous method Proposed method CSU Yunlu 27.62±13.58 16.81±9.79 Gliders2015 29.49±18.62 21.21± 14.67 HfutEngine2015 27.68±14.07 14.86±8.76 Oxsy 14.17±10.15 8.06±6.38 YuShan 15.61±10.35 9.91±7.90 表 1 より，従来手法と比較して提案手法のほうがマー ク割当変更回数が改善されていることがわかる．これ は，提案手法ではグループに対し割り当てを行うこと で割り当て対象数が削減されているためであると考え られる． 次に，スタミナ消費量について調査した．スタミナ消 費量をセットプレイが開始後，相手プレイヤがボールを 蹴るまでに消費したスタミナ量とする．適切にマーク 対象プレイヤが割当されていれば，無駄な移動がなく なるためスタミナ消費量は減少すると考えられる．用 意された実験データによる結果を，セットプレイ 1 回 分の平均値としてスタミナ消費量をチーム，割当手法 毎にまとめた結果を表 2 に示す． 表 2: Stamina consumption

Opponent Previous method Proposed method CSU Yunlu 1292.85± 464.46 1352.28±457.24 Gliders2015 1396.55± 442.23 1492.76±431.84 HfutEngine2015 1327.01± 466.14 1411.21±461.40 Oxsy 1485.49± 496.20 1474.01±470.89 YuShan 1188.71± 457.55 1234.82±457.90

表 2 より，スタミナ消費量において従来手法より提 案手法のほうが悪化していることがわかる．従来手法 では，敵プレイヤに対して味方プレイヤを割り当てる ことにより，味方プレイヤ移動距離の最小化を図って いた．しかし，今回の提案手法ではグループに対して 味方プレイヤを割り当て，その後敵プレイヤに対して 味方プレイヤを割り当てている．グループに対して割 り当てを行う際の基準がグループの中心と味方プレイ ヤの距離であるため，味方プレイヤの移動距離が最小 化されていないことが考えられる． 次に，ボール奪取回数について調査した．ボール奪 取回数を，セットプレイが開始し，相手プレイヤがボー ルを蹴ってから 50 サイクル以内にボールを奪った際 1 とし，一度も奪えなかった際 0 と定義する．ボール奪 取回数が増加することで，相手側の攻撃回数が減少し， 自チームの攻撃の機会が増加すると考えられる．用意 された実験データによる結果を，セットプレイ 1 回分の 平均値としてボール奪取回数をチーム毎に，またフィー ルドの範囲毎にまとめた．Corner を自陣コーナーから のセットプレイと定義する．また，Attacking をフィー ルドを x 軸に関して 3 分割した際の自陣側, Middle を 中央, Defensive を敵陣側から発生したセットプレイと 定義する．従来手法における結果を表 3，提案手法に おける結果を表 4 に示す．

表 3: Ball intercepts by the previous method

Opponent Corner Attacking Middle Defensive CSU Yunlu 0.604 0.344 0.228 0.0 Gliders2015 0.663 0.479 0.232 0.116 HfutEngine2015 0.619 0.486 0.312 0.244 Oxsy 0.645 0.46 0.389 0.0 YuShan 0.636 0.298 0.22 0.103

表 4: Ball intercepts by the proposed method

Opponent Corner Attacking Middle Defensive CSU Yunlu 0.638 0.349 0.230 0.0 Gliders2015 0.651 0.509 0.194 0.192 HfutEngine2015 0.600 0.476 0.330 0.345 Oxsy 0.625 0.522 0.421 0.0 YuShan 0.642 0.215 0.174 0.178 表 3，表 4 より，提案手法は従来手法と比較して大きな 差がないことがわかる．ただし，Oxsy 戦での Attacking や，Gliders2015 戦，HfutEngine2015 戦，YuShan 戦 での Defensive においては改善されており，YuShan 戦 での Attacking では悪化していることがわかる．これ は，マーク割当変更回数の面で改善されていることと 移動距離の最適化が出来ていないことに起因すると考 える．

6

おわりに

本論文では，相手側セットプレイの再現実験により 割当手法による性能変化を調査した．実験結果から，提 案手法のマーク割当変更回数の削減に関して有効性を 示した．また，グループを作成し割当案を作成するこ とで味方プレイヤの移動距離の最小化が出来ていない ことが考えられる．しかし，今回の提案手法により同 一グループ内の敵プレイヤは似通った位置にいるため， 味方プレイヤがカバーしなければいけない敵プレイヤ の割り当てなども可能であると考える．今後の課題と して，敵選手のグループ作成方法の改善，多対一の割 当のコストの導入や，プレイヤの動きの洗練などが挙 げられる．

参考文献

[1] Hiroaki Kitano, Minoru Asada, Yasuo Kuniyoshi, Itsuki Noda, Eiichi Osawa and Hitoshi Matsubara, “RoboCup: A Challenge Problem for AI”, AI

Mag-azine , Vol.18, No.1, pp.73-85, 1997.

[2] Luis Paulo Reis, Nuno Lau and Eugenio Oliveira, “Situation Based Strategic Positioning for Coordi-nating a Simulated RoboSoccer Team”, Balancing Reactivity and Social Deliberation in MAS, 175–197, 2001

[3] Hidehisa Akiyama and Itsuki Noda, “Multi-Agent Positioning Mechanism in the Dynamic Environ-ment”, RoboCup 2007 : Robot Soccer World Cup XI, 2008.

[4] V. Kyrylov and E. Hou, “Pareto-Optimal Collabora-tive Defensive Player Positioning in Simulated Soc-cer”, RoboCup 2009: Robot Soccer World Cup XIII, 2009.

[5] Patrick MacAlpine, Eric Price and Peter Stone, “SCRAM: Scalable Collision-Avoiding Role Assign-ment with Minimal-Makespan for Formational Po-sitioning”, In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI),

pp.2096-2102, 2015. [6] 秋山英久, “RoboCupサッカーシミュレーション2D必 勝ガイド”,秀和システム, 2006. [7] 山下 雄大，田中 翔，三舩 哲史，中島 智晴，秋山 英久， “RoboCupにおけるセットプレイのマーク割当に関す る検討 ”， 第25回ソフトサイエンス・ワークショップ 講演論文集，2015.

[8] Ford.L.R, and Fulkerson,D.R., “Maximum Flow through a Network,” Canadian Journal of Mathe-matics, Vol 8,pp.399-404, 1956.