Comments
Description
Transcript
A3-2 ファジィ契約ネットに基づくマルチエージェントロボット のための
A3-2 A3-2 ファジィ契約ネットに基づくマルチエージェントロボット のためのタスク割当に関する研究 福井大学大学院 工学研究科 知能システム工学専攻 進化ロボット研究室 梅 亮 (主指導教員 : 前田 陽一郎) 1. 緒言 コンピュータまたはエージェント間の通信によって 協調行動を実現させる手法は多く提案されている。 R.G.Smith の提案した契約ネットプロトコル (CNP) [1] はもともとコンピュータネットワークの効率的運用が 目的で考察されたタスク分散手法である。J.A.Kensler ら [2] は CNP に基づいてニューラルネットワークを用 いたタスク分配手法を提案している。また、菅原ら [3] は CNP による大規模自律エージェントシステムにおけ る効率とその性質を解析している。しかしながら、従 来の CNP における入札、落札といった判断の処理基準 として一定の条件のみを用いているため、複雑で動的 な環境に適応的にタスク割当を行うのは困難である。 そこで本研究では、自律移動ロボットが複数存在す るマルチエージェントシステムにおいて、タスク割当 問題を解決するために、ファジィ推論を組み込んだ契 約ネットプロトコルを用いたロボット間通信によって、 適応的なタスク割当を実現する手法を提案する [4–7]。 本手法では、実際の人間が行うような複雑な環境にお ける柔軟な判断を模擬するために、契約ネットの入札、 落札の判断にファジィ推論を使用した。また、提案手 法の有効性を検証するため、ロボットサッカーを例題 としていくつの環境条件についてシミュレーション実 験を行ったので、これについても報告する。 2. ファジィ契約ネットに基づくタスク割当 手法 従来の契約ネットにおける入札、落札といった判断 に用いられる基準は固定的であるため、刻々と変化す る複雑な環境に柔軟に対応するのは困難である。そこ で本研究では契約ネットの入札、落札に際し、ファジィ 推論を用いて入札適合度と落札適合度を算出する手法 を提案する。契約ネットにおける各判断をファジィ推 論を用いて行うことで、複雑な環境にも柔軟な対応を することができる。さらに、入札と落札の両方の判断 を基に最終的な各エージェントのタスクへの総合適合 度を決定し、その値によって落札者の決定を行う。 2·1 ファジィ契約ネットのアルゴリズム 本研究では入札と落札といった判断の難しい意思決定 をファジィ推論で判断する契約ネット (Fuzzy Contract Net: FCN) を用いて、タスク割当を適応的に行う手法 を提案する。本手法におけるアルゴリズムフローを図 1 に示す。 本手法では契約ネットの入札、落札に際しファジィ 推論を用いてタスクへの適合度を算出し、その値を基 にエージェント選択の判断を行っている。本手法にお ける大まかな処理手順は、入札時に使用する適合度を マネージャ メッセージ通 ージ通信 タスク発生 タスク発 全エージェン ジェント へタスク へタスク告知 No 入札があっ 入札が あったか？ Yes a 契約者 マネージャからの マネージャ タスク告知 タスク 告知 入札判断 入札条件に 入札条 件に 適合するか 適合するか？ No Yes 入札処理 b 落札判断 落札者選択 落札者選 全エージ 全エ ージェン ェントに トに 落札メッ メッセー セージ送 ジ送信 落札 告知待ち 落札者告知待 自分が落札 自分が 落札したか？ たか？ No Yes 実行報告待ち 実行報告 No 一定時間内に報告 一定時間内 があったか？ があったか タスク実行 タスク実 実行報告 YES 契約終了 契約終了 図 1: ファジィ契約ネットのアルゴリズムフロー (図中 a、b の部分がファジィ推論を示す) 「入札適合度」、落札時に使用する適合度を「落札適合 度」とし、入札適合度は入札エージェントが、落札適 合度はマネージャがそれぞれファジィ推論を用いて算 出する。本研究では例題として、サッカーロボットを 想定し、タスクとして味方へのパスタスクを設定する。 2·2 入札適合度 Fa 入札適合度とは、タスク告知を受け取ったエージェ ントが入札に際して算出する値であり、入札するかど うかの基準で、範囲を 0 ≤Fa ≤ 100 に設定した。入札 適合度は、まずパスを味方にすることができるかどう かを主に判断するため、味方エージェントの敵からの 影響の大小に従って算出され、ボールパスが敵に遮ら れる可能性の低さを示す。複数の環境情報から総合的 に判断するために、ファジィ推論により、入札適合度 を算出する。ここでは 160cm × 120cm のミニチュア サッカーコートを想定して図 2 のようなメンバーシッ プ関数とシングルトンの値を設定した。 図 3 は入札適合度 Fa の説明図である。A1 はパサー、 A2 はレシーバー、B1 と B2 は敵である。この時、A1 は ボールを持っているので、このパスタスクではマネー ジャとなる。 本手法では、パスを敵エージェントに断たれない可 能性の大きさを示すために、パス成立度を定義する。パ LM LS PM PS LL 70 40 90 SS 0.35 0.4 30 40 40 TS (cm) (d) 入札適合度 Fa 表 1: 入札適合度決定ファジィルール LS LA M MD LL L LC MC (cm) 0.35 0.4 0.55 (b) 最小パス成立度 Pmin L LA LB LC LD M MA MB MC MD H TL LS LB M L SM LM LA LD MC LL L LC MB LS LB MC L 40 60 ( º) 0 10 20 30 40 50 60 70 80 90 100 (c) シュートの角度範囲 θg (d) 落札適合度 Fb 図 4: 落札のメンバーシップ関数とシングルトン 表 2: 落札適合度決定ファジィルール SL LM LA MA MD LL L M MC DS DM DL ス成立度 P は以下の式で算出する（図 3 参照）。 θ d P = α + (1 − α) l π/2 (1) l: パサーからレシーバーまでの距離 θ: パサーとレシーバーと敵との角度 d: レシーバーから敵までの距離 α: 距離と方位の重要度 入札時のメンバーシップ関数、シングルトン、ファ ジィルールを図 2、表 1 に示す。入力はボールまでの 距離 l、最小パス成立度 Pmin 、敵までの最小距離 dmin で、出力は入札適合度 Fa である。本実験においては α=0.5 とした。入札条件として、δ を一定値として以 下の式で決める。 (δ : 一定値, 0 ≤ δ ≤ 100) TS L L L PS TM LA LA L TL LB LA LA TS LD LD LB PM TM MA LD LB TL MA LD LD TS MC MB M PL TM H MC MA TL H MD MB 図 5: 落札適合度 Fb の決定パラメータ 図 3: 入札適合度 Fa の決定パラメータ Fa ≥ δ 90 TM 20 0 10 20 30 40 50 60 70 80 90 100 図 2: 入札のメンバーシップ関数とシングルトン PS PM PL PL 1 (c) 敵までの最小距離 dmin SS LM L LD MC 60 (a) 敵ゴールまでの距離 D L LA LB LC LD M MA MB MC MD H 1 20 PM PS 1 0.55 (b) 最小パス成立度 Pmin SL SM DL 1 (cm) (a) ボールまでの距離 l DM DS PL 1 1 (2) 2·3 落札適合度 Fb 落札適合度 Fb とは、入札のあったエージェントの中 からタスクの落札者を決定する際にマネージャ側で計 算される値である。ここでは落札適合度の範囲を入札 適合度と同じく 0 ≤Fb ≤ 100 に設定した。落札適合度 Fb を用いることで、マネージャが入札者とは違った視 点でエージェントのタスクへの適合度を算出すること ができる。ここでも 160cm × 120cm のミニチュアサッ カーコートを想定してメンバーシップ関数とシングル トンの値を設定した (図 4 参照)。落札適合度はレシー バーが場面中の状況の優劣に従って、複数の情報から 総合的にファジィ推論で算出される (図 5 参照)。A1 は パサー、A2 はレシーバー、B1 と B2 は敵である。 2·4 総合適合度 Ff 総合適合度 Ff はマネージャ側で最終落札者を決定す るために計算される値である。マネージャは、入札者 から送られてきた入札適合度 Fa と自分で算出した各入 札者の落札適合度 Fb の両方に基づいて最終的な各エー ジェントへのタスクの総合適合度 Ff を以下の式に従っ て決定する。 Ff = βFa + (1 − β)Fb (β = D ) L (3) D: 敵ゴールまでの距離 L: サッカーフィールドの長さ β: 入札と落札の重み係数 最終的に maxFf を持つエージェントが落札者として 決定される。上式より、入札エージェント、マネージャ それぞれの基準で算出したタスクへの適合度を総合的 に判断してタスクを割り当てることが可能となる。β は 入札適合度を重視するか落札適合度を重視するかを示 す重み係数である。本手法では図 6 に示すように、敵 ゴールまでの距離 D=ls を限界として、入札重視領域 Ta と落札重視領域 Tb に分けた。(本実験では ls =40cm とした) Ta Tb ls Robot (パターン 1) 入札、落札共にファジィ推論なし (パターン 2) 入札時のみファジィ推論あり (パターン 3) 落札時のみファジィ推論あり (パターン 4) 入札、落札両方でファジィ推論あり さらに実験 2 として、異なる環境において入札重視 と落札重視がある場合と通常のファジィ契約ネットと の比較実験を行った (図 8 参照)。通常のファジィ契約 ネットではレシーバーの位置に関わらず、入札条件が Fa ≥ 50 と設定した。入札重視と落札重視がある場合で は、タスク入札の際の入札条件がレシーバーの位置に よって異なる。図 6 の Ta 領域 (入札重視領域) にある ロボットのタスク入札の際の入札条件は Fa ≥ 50 とし た。また、図 6 の Tb 領域 (落札重視領域) にあるロボッ トがタスク入札の際の入札条件は Fa ≥ 30 に緩和させ た。ここでは、入札重視領域 Ta と落札重視領域 Tb の 境界を敵ゴールまでの距離 ls (実験では ls =40cm) を基 準として用いた。 D A3 A4 L A0 図 6: 入札及び落札重視の境界領域 A2 A1 • 入札重視 レシーバーの敵ゴールまでの距離が D ＞ ls にな ると (図 6 の Ta 領域)、ロボットがシュートしにく い位置にあるため、パスの安全性が高くなり、入 札重視になる。入札適合度を計算する際には、敵 ゴールまでの距離、最小パス成立度、敵までの最小 距離などの要素を含んでいるため、敵からの影響 を最も考慮している。Ta 領域にある味方は攻撃へ のチャンスが少ないため、入札条件が厳しくなる。 • 落札重視 ロボットの敵ゴールまでの距離が D≤ls になると (図 6 の Tb 領域)、ロボットがシュートに有利な位 置にあるため、実際の人間の試合のように、リス クがあっても、シュートチャンスをつかんでシュー トすべきである。その場合には、敵からの影響を あまり考えずに、レシーバーのシュート行動を主 に考える。落札適合度は、シュートへの可能性を優 先して落札重視にし、Tb 領域にある味方はシュー トへのチャンスを多くするため、入札条件を緩和 する。 3. シミュレーション実験 提案手法の有効性を検証するため、AI-RCJ 4.0 サッ カーシミュレータを利用し、これを用いていくつかの 環境条件によるシミュレーション実験を行った。 3·1 実験条件 本実験では、サッカーロボットシミュレータにおい て、5 対 5 の対戦環境を想定し、タスクとしてパスタ スクを設定した。まず実験 1 として、ファジィ推論を 用いた契約ネットと通常の契約ネットとの比較実験を 行った (図 7 参照)。契約ネットの入札、落札といった 判断において、以下 4 つのパターンを比較した。 図 7: エージェントの初期位置 (実験 1) A3 A2 A4 A1 A0 図 8: エージェントの初期位置 (実験 2) 3·2 実験結果 シミュレーション実験の結果、ファジィ推論を用い る場合と用いない場合とで、最終の落札者も異なるこ とがわかった (表 3 参照)。パターン 1 では、マネージャ のタスク告知に対して、入札条件を満たしたエージェ ント A3 と A4 が共に入札者になる。落札の際には、マ ネージャが最も敵ゴールと距離が近い味方エージェン トにパスするため、エージェント A3 が落札者になる (図 9 の (a) 参照)。 パターン 2 では、すべてのエージェントがファジィ 推論による自分の入札適合度を持って入札する。この 場合最も高い入札適合度を持っているエージェントが A3 4. A3 A4 A4 A0 A0 A2 A2 A1 A1 (a) 実験 1:パターン 1 (b) 実験 1:パターン 2 A3 A3 A4 A4 A0 A0 A2 A2 A1 A1 (c) 実験 1:パターン 3 (d) 実験 1:パターン 4 A3 A3 A2 A2 A4 A1 A4 A1 A0 A0 (e) 実験 2:入札/落札重視なし (f) 実験 2:入札/落札重視あり 図 9: 実験結果 表 3: 入札および落札エージェント ファジィ推論なし 入札時にファジィ推論使用 落札時にファジィ推論使用 入札、落札にファジィ推論使用 入札重視と落札重視なし 入札重視と落札重視あり 入札者 A3、A4 A1、A2、A3、A4 A1、A2、A3、A4 A1、A2、A3 A1、A2 A1、A2、A4 結言 本研究では、自律移動ロボットが複数存在するマル チエージェント環境において、サッカーの対戦状況を 想定して、ファジィ契約ネットに基づいたロボット間 通信と、ファジィ推論を用いた柔軟な判断によるタス ク分配制御を実現する手法を提案した。提案手法の有 効性を検証するため、ロボットサッカーシミュレータ を用いて異なる環境条件によるシミュレーション実験 を行った。 実験結果より、ファジィ推論を用いた契約ネットによ り、環境の複数の状況を総合し、柔軟なタスク分配が できることが分かった。敵エージェントの影響が弱い 場合、適切な位置にいる味方エージェントを選択する ことができた。また、入札重視と落札重視を用いるこ とによって、マネージャが味方エージェントの場面中 の位置の優劣に従って、入札戦略を変えることができ、 より柔軟なタスク割当てをできることが確認された。 しかしながら、今回は静止環境による実験のみを行 ない、動的な状況における検証は行っていない。その ため、適切なエージェントにタスクが分配されること は確認できたが、動的な環境では実際のサッカーと異 なることも十分考えられる。人間はサッカーをすると き、行動と判断が連続して交互に起こるが、複数の動 的な情報に基づいて、前後の行動に関係付けを行って タスク分配するのは今後の課題と考えている。 参考文献 落札者 A3 A3 A2 A1 A1 A4 A3 であるため、エージェント A3 にパスされる (図 9 の (b) 参照)。 パターン 3 では、すべてのエージェントが入札する が、エージェント A2 が敵ゴールの近くにいて、シュー ト角度も大きいため、一番高い落札適合度を与えられ て、パスを受け取っている (図 9 の (c) 参照)。 パターン 4 では、エージェント A1、A2、A3 が入札で きる。さらに、最も高い総合適合度を持っているエー ジェント A1 に落札される (図 9 の (d) 参照)。 入札重視と落札重視なしの場合では、入札条件が Fa ≥ 50 である。ここでは入札条件を満たしたエージェント が A1、A2 の 2 つであった。その結果、エージェント A1 が最も高い総合適合度となり、最終の落札者になっ た。よってボールがマネージャA0 から A1 にパスされ た (図 9 の (e) 参照)。 入札重視と落札重視ありの場合、エージェント A4 が 敵ゴールの近くにあるため、落札重視領域となり、落 札重視モードになる。そのため、入札条件が Fa ≥ 30 に 緩和され、エージェント A1、A2 と共に入札者になる。 さらに、この場合エージェント A4 が最も高い総合適合 度となり落札した。その結果、ボールがマネージャA0 から A4 にパスされた (図 9 の (f) 参照)。 [1] R. G. Smith, “ Fuzzy Algorithms, ”The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver, IEEE Trans. on Computers, Vol.C-29, pp.11041113 (1980) [2] J.A.Kensler and A.Agah, “ Neural networksbased adaptive bidding with the contract net protocol in multi-robot systems, ”Springer Science+Business Media, Appl Intell 31, pp.347-362 (2009) [3] 菅原 俊治, 福田 健介, 廣津 登志夫, 栗原 聡,“ 大規 模自律エージェントシステムにおける契約ネットプ ロトコルの効率特性, ”第 6 回情報科学技術フォー ラム, FIT2007, pp.165-168 (2007) [4] 藤田 陽平, 前田 陽一郎,“ 契約ネットプロトコルを 用いたロボット間通信による協調行動制御, ”第 24 回日本ロボット学会学術講演会, CD-ROM, 2I11 (2006) [5] 梅 亮, 前田 陽一郎,“ファジィ契約ネットを用いた自 律分散ロボットの協調行動制御,”第 27 回日本ロボッ ト学会学術講演会, CD-ROM, RSJ2009AC1F1-04 (2009) [6] 梅 亮, 前田 陽一郎, 高橋 泰岳,“ ファジィ契約ネッ トに基づくマルチエージェントロボットのための タスク割当, ”第 26 回ファジィシステムシンポジウ ム, CD-ROM, MD4-2 (2010) [7] 梅 亮, 前田 陽一郎, 高橋 泰岳,“ ファジィ契約ネッ トに基づくマルチエージェントロボットのタスク 割当手法, ”日本知能情報ファジィ学会合同シンポ ジウム 2010, HKH10-13 (2010)