ObjectSquare [2002 年 9 月号]

[技術講座]



ちょこっとマルチ・エージェント(前)

株式会社オージス総研
ES事業部PDチーム
国正聡

〜〜〜 目次 〜〜〜

1 はじめに
2 マルチ・エージェント、その前に・・・
3 エージェントって?
 3.1 エージェントに必要な機能
 3.2 エージェント技術の現状
4 続く・・・
参考文献

〜〜〜〜〜〜〜〜〜〜
1 はじめに

マルチ・エージェントと聞いて、その意味するところがすぐに思いつく人はなかなかいないのではないでしょうか。『エージェント』という言葉自体は、最近でこそソフトウェアの分野でもよく聞かれるようになってきましたが、私がエージェントという言葉をはじめて聞いたのは、大学でAI(人工知能)周りの調査をしているときでした。当時は、将来自分がソフトウェア業界に身を置くことを想像すらせずに、エージェントと付き合っていたのですが、どうも最近になり、自分の身の回りで「エージェント」「自律分散」「協調」といった、当時毎日のように頭を悩ましていたキーワードが巷をにぎわしているようです。 そこで記憶の奥底に眠っているそれらの知識を、今更ながらに掘り起こそうと、筆(キーボード)をとった次第であります。人工知能というと、ちょっと敬遠気味になるかもしれませんが、難しい数式などは一切でてきません(出せない?)ので、読み物を読むノリで目を通していただければと思います。


2 マルチ・エージェント、その前に・・・

さて、今回取り上げるマルチ・エージェントとはどのようなものなのでしょうか?紹介する前に、以下の問題を考えてみてください(問題の答えというより、答えの出し方に焦点を当ててください)。

[問題]
あるところに横断歩道があります。横断歩道をわたろうとしている人が、両端にそれぞれ20人(計40人)いるとします。信号が青になったとき、一斉に人々が横断をはじめるわけですが、できるだけ早くすべての人が、横断歩道を渡り終えるためには、個々の人はどのように行動すればよいでしょうか?(ただし、横断歩道は10人分の幅であり、横断歩道の外を渡ることはないものとします。)

さあ、あなたならどう考えますか?たとえば
「神様がいて、人と人が衝突しないように、一人一人の動き(進行方向や歩く速度)を決定する」
というのはどうでしょうか?ちょっと現実離れしているので、こうしましょう
「神様は間違うことなく、てきぱき仕事をこなす。この世の中でそのようなことができるのはコンピュータである。問題と同じ状況のシミュレーションプログラムを作成し、その中で人は、コンピュータが持つある戦略に基づく制御の下で行動する。戦略を変更しながらの複数回の試行の後、最も早く人が渡り終えた戦略が最適な行動パターンである」
若干現実的になってきたように思えます。オブジェクト指向で考えるならば、人クラスと神様クラスを用意して、神様オブジェクトが、横断歩道の占有状況と横断歩道上の人オブジェクトの流れ(以降、これを環境と呼びます)を見ながら、各々の人オブジェクトに指示を与えるという考え方ができます。もしくは人オブジェクトのほうから、次の行動を神様オブジェクトに問い合わす、という考え方もありですね。いずれにせよ環境の情報は、神様オブジェクトが知っており、人オブジェクトは指示された、もしくは問い合わせた結果どおりに行動するということになります。この方法を採用して問題を解決しようとした場合、神様オブジェクトがどのようなルールに従って人オブジェクトの行動を決定するかがミソとなることは疑いのないところでしょう。
しかしですよ、ちょっと考えてみてください。ある一人の人の行動を決定するのに、他の39人の状態全て(全てでなくてもよいのですが)を確認して、「人1が状態Aで、人2が状態Bで、・・・、人3が状態Cだから、あなたのとるべき行動は”止まれ”です。」なんてことをやっていると、とてもじゃないですが、考えられるルールを全部洗い出す作業で、人生の大部分を消費してしまいます。しかもせっかく考え出したルールなのに「目の前の人がこけた」という予想していない状態が発生してしまうと、コンピュータの中の神様オブジェクトは正しい行動を指示してくれません(なんとも頼りのない神様ですが・・・)。さあ、困りましたね。


しかし、この問題は、普段私たちが身近で経験している問題でもあります。私たちの中で、横断歩道を渡るときに、誰かから指示を受けて渡る人はいませんよね。それでも、横断歩道を渡る人達は、お互いぶつからないように、そこそこの速さで渡り終えることができています。これは、私達一人一人が自分の周りを見て、その時々に対応する適切な行動を取っていることの結果によるものです。その時に各々の人は、自分の行動決定に影響を及ぼさないような、遠くで歩いている人の行動は気にしないでしょうし、自分のみならず、全ての人が早く渡り終えるようにと思って行動する人は、恐らくいないでしょう。強いて挙げれば

ぐらいではないでしょうか。それでも個々の人々が、ある意味自分自身の問題を解決する行動の結果、実は全体として問題が解決されるというのは面白いところです。
そこでこのように、問題を構成する各要素がそれぞれ自分自身の問題を解決するという考えを、シミュレーションに取り入れてみたら面白そうだと思いませんか?そうです、この考え方がマルチ・エージェントなのです。マルチ・エージェントの考え方を取り入れたマルチ・エージェントシステムでは、システムを構成する要素を集中的に管理するような階層構造はとらず、各要素がお互いに通信し協調しあうことにより、システム全体としての機能を果たすことを目的としています。


従来の中央集権的な制御構造をとるシステム


マルチ・エージェントの考えに基づくシステム


3 エージェントって?

マルチ・エージェント = マルチ(な)エージェントという言葉からも想像がつくように、マルチ・エージェントとは、複数のエージェントが存在することを表しています。まずはエージェントについて、説明をしておきたいと思います。エージェントは、自分の知る限りでは、「代理人」から「知能を持ったオブジェクト」まで、使われる場所によってさまざまな意味が当てはめられているようです。「オブジェクト指向の次はエージェント指向だ」という言葉がだいぶ前から言われてきましたが、ここでのオブジェクト指向、エージェント指向というのは、ものの考え方や設計の指針であることに違いはないですが、システムの分析/開発の方針とはちょっと異なる気がします。
そうは言っても、あいまいなままでは話が進みませんので、ここでは「自律的に意思決定・行動のできる最小単位」と定義することにします。イメージが沸きにくいかもしれませんが、そこはぐっとこらえて次に進むことにしましょう。


3.1 エージェントに必要な機能

エージェントには、以下の機能が必要であるといわれています。



環境認識機能
エージェントは、自身が存在する環境(自身が存在する"場"や、同じ場に存在する他のエージェントの存在情報など)に応じて動作する必要があります。そのためには、エージェントは環境情報を認識できなければなりません。各エージェントが環境情報を認識する範囲(環境全体の情報を必要とするのか、自身の周りの必要最小限の情報だけでよいのか、等)は、対処すべき問題に応じて決定すべきです。

行動決定・選択機能
エージェントは自身のとるべき行動を、自分自身で決定しなければなりません。その決定のメカニズムは、IF〜THENルールのような単純なものから、実行可能な行動の中から、重み付けされた行動を確率的に選択するような複雑なものまで多種多様です。

学習機能
エージェントは、環境に合わせて自分自身を進化させる必要があります。同じ失敗を何度も繰り返しているようでは、一人前の(?)エージェントとはいえません。この学習という機能を、どのようにシステムで実現するかですが、人工知能、人工生命の研究分野でよく使われている方法として「強化学習法(*1)」「遺伝的アルゴリズム(*2)」などがあります。これらの手法により、上述の行動決定・選択機能を進化させる、すなわちエージェントに学習をさせるわけです。

エージェントは、環境認識器より外部情報を取得し、自身が持つ決定規則に従い行動します。またその際に、自身が持つ学習機能を利用して、より環境に適した行動を選択するようになります。そのおかげで、与えられた環境の中で自律的に行動することができるだけでなく、動的に変化するような環境に対しても、柔軟に対応することができます。

(*1)強化学習法(Reinforcement Learning)
行動に対する結果に対して、報酬とペナルティを与えることにより、より優れた行動を選択するように、行動選択の方法を強化していく。報酬(ペナルティ)の与え方として、行動を起こす度に報酬(ペナルティ)を与える方法や、最終的な結果に対して、それまでにとってきた一連の行動に対して報酬(ペナルティ)を割り振る方法、またそれらを組み合わせた方法などがある。
簡単な例を以下に示す。、エージェントが以下のような(環境、行動、報酬値)という行動の候補を持っているとする。
−−−−−−−−−−−−−−−−−−−
(目の前の情報:何もない、前進する、70)
(目の前の情報:何もない、右を向く、15)
(目の前の情報:何もない、左を向く、10)
(目の前の情報:何もない、立ち止まる、5)
−−−−−−−−−−−−−−−−−−−−
このエージェントが、以後”目の前に何もない”という状態になった時、選択される行動は、70%の確率で”前進する”ことになる(確率的に行動を選択するのが一般的だが、そのときの報酬地がもっとも多い行動を選択するという戦略もある、)。
また、その行動の結果、このエージェントが有益な結果を導き出すことになれば、さらにその行動の報酬値は増大し、”目の前に何もない”という状況下で”前進する”という行動が選択される確率は大きくなる。逆に望まれない結果となってしまった場合には、ペナルティを与えることで、以後その行動が選択される確率を減少させていく。このように、エージェントが強化されるのである。
(*2)遺伝的アルゴリズム(Genetic Algorithms)
生物の進化過程を模倣した学習アルゴリズム。各個体(エージェント)は、行動を決定するための遺伝子情報を保持しており、交叉、淘汰、突然変異と呼ばれる演算処理により、遺伝子情報を進化させていく。多点探索法のひとつであり、巡回セールスマン問題に代表される組み合わせ最適化問題などで、現実的な時間内で準最適解を見つけ出すことができる。もちろん場合によっては、その解が最適解となり得る。
遺伝的アルゴリズムを採用する場合は、解決すべき問題をどのように遺伝子情報にマッピングさせるかがミソとなるが、ビット列により状態と行動の組み合わせを表現する方法が一般的のようである。
例えば、最初の2bitを自身の現在の進行方向(00:上(画面から見て上ということ)、01:左、10:下、11:右))、次の2bitを自身の目の前の情報(00:何もない、01:他のエージェントがいる、10:壁がある、11:その他)、さらにその次の2bitを、自身が次に取る行動(00:前進、01:左旋回、10:右旋回、11:停止)とすると、
000101
という遺伝子情報は、自身が上を向いており、目の前に他のエージェントが存在する場合は左旋回する、という行動を意味することになる。基本的に各エージェントは遺伝子情報をひとつだけ持つのではなく、多数の遺伝子情報を持っており、採用する行動の候補は複数存在し、また同じ遺伝子情報が多数存在することも考えられる(というより、そのように遺伝子情報を、ある決まった構成に収束させることが、解の発見となる)。
エージェントがある状態(0001)にある時、その環境情報に合致する遺伝子情報として
−−−−−−−−−−−−−−−−−−−
000100…10個
000101…70個
000110…10個
000111…10個
−−−−−−−−−−−−−−−−−−−
を持っていた場合は、70%の確率で左旋回が選択され、残り10%ずつの確率でそれぞれの行動が選択される。(もちろん、一番多くの遺伝子情報が存在する行動を決定するという戦略もある)
強化学習同様に、この遺伝子情報を進化させていくためには、良い遺伝子と悪い遺伝子を評価するための評価手法が必要となる。決まった手法が確立されているわけではないが、遺伝子ごとに評価値を設けたり、エージェントの目標達成度にあわせて、そのエージェントが持つ遺伝子情報を評価するなどの方法が考えられる。後は、交叉演算、遺伝子情報の淘汰を繰り返し、また時には局所解に陥ることを防ぐための突然変異を取り入れたりしながら、全ての遺伝子を良い遺伝子に収束させていくアルゴリズムである。ある程度の収束が確認できれば、生き残った遺伝子情報を分析することで、問題の解を発見することができるが、問題の性質や演算処理のパラメータ如何では、解が発散してしまう事も(私の経験上)珍しくない。特に今回焦点を当てているマルチ・エージェント環境においては、他のエージェントそのものも外部環境となる(環境が動的に変化する。巡回セールスマン問題に当てはめると、セールスマンが複数存在することになる?)ため、解を収束させることは非常に難しいと予想される。しかしながら、組み合わせをひとつひとつ調べていくよりかは、遥かに現実的な解法であることはいうまでもない。
3.2 エージェント技術の現状

エージェントに要求される機能を列挙してみました。それら全てを満たすものが存在したら、何でもできそうだと思いませんか?ここでは、そのエージェント技術を使ったらどのようなことができるのか、そしてその研究はどこまで進んでいるのかについて触れようと思います。あらかじめ断っておきますが、昨今の研究はどんどん進んでおり、私が認識している情報はもう時代遅れとなっていることは否めません。

ネットワーク・エージェント
近年で、最もエージェント技術が日の目を見ている分野が、このネットワークエージェントでしょう。何かほしい情報をエージェントに指示しておけば、インターネットの中を駆け回り、必要な情報を取ってきてくれるようなエージェントの応用技術です。一度エージェントに命令をすれば、あとはユーザはネットワークから接続を切断しても、エージェントはネットワークの中から該当する情報を探し出してくれます。また、単に探すだけでなく、他のエージェントと情報交換しながら、より効率的に情報を探してくれることも考えられます。モバイル・エージェントとしても知られています。
インタフェース・エージェント
一言で言えば、システムの操作を手助けするエージェント。また、インタフェース・エージェントは感情を持っており、その表情により、ユーザは操作しているシステムの状況を把握したり、逆に、エージェントがユーザの操作からその目的を推測し、アドバイスや忠告をするような、ユーザとシステムとのインタフェースに適用されるエージェント技術です。
マルチ・エージェント
エージェントの研究が「如何に自分自身を進化させ、問題により適したエージェントとなれるか」に焦点を当てているのに対して、マルチ・エージェントは、個々の進化よりも、各エージェントが協調することにより、問題を解決することに焦点を当てています。詳細は次回に譲りますが、このマルチ・エージェントの面白いところは、個々のエージェントの行動ロジックを、単純にすればするほど柔軟性のあるシステムとなり、複雑にすればするほど最適性は追求されるが、トラブルなどに対応できないシステムになるという点と、当初予測もしなかったエージェント達の群行動が自律的に形成される(創発現象といいます)場合があるという点です。

4 続く・・・

「マルチ・エージェントとは?」の前に、簡単にですが”エージェント”そのものについて紹介しました。3章の最後にも書きましたが、エージェントとマルチ・エージェントとはそのねらいとするところが若干異なります。次回はマルチ・エージェントによりどのようなシステムが構築できるのか?最初に示した横断歩道の問題はマルチ・エージェントによってどのような解が導き出されるのか?について触れてみようと思います。
また、オブジェクトの広場では、以前にもエージェント関連の記事として、「エージェント指向が目指すもの」を取り上げていますので、ぜひこちらもご参照ください。


- 参考文献 -

知の創発 ロボットは知恵を獲得できるか
  伊藤宏司 編著

「マッチ箱の脳」 使える人工知能のお話
  森川幸人 編著

オブジェクト指向からエージェント指向へ
  本位田真一/大須賀昭彦 著

©2002 OGIS-RI Co., Ltd.
Index Next
Index Next