(57)【特許請求の範囲】
【請求項１】
マルチエージェントシステムにおけるエージェント間通信に用いられるメッセージキューを管理するメッセージキュー管理装置であって、
前記エージェントは、他のエージェントから送信されたメッセージを保管する前記メッセージキューと、
前記メッセージキューに含まれるメッセージの個数が所定値を超えた場合に、前記メッセージの種類毎に前記メッセージキューに含まれるメッセージの個数を数え、その個数の相対的な大小に応じて、前記メッセージキューに残すメッセージの個数を前記メッセージの種類毎に決定し、前記メッセージキューに残すメッセージの個数および前記メッセージの種類毎に異なるメッセージ選択手法により前記メッセージキューに残すメッセージを選択して、前記残すメッセージ以外を削除することで前記メッセージキューに含まれるメッセージを現在よりも少数のメッセージに集約するメッセージ集約手段とを備えることを特徴とするメッセージキュー管理装置。
【請求項２】
前記メッセージ集約手段は、前記メッセージの種類毎に数えた前記メッセージキューに含まれるメッセージの個数の相対的な大小に基づく所定の選択規準に従って、前記メッセージキューに含まれるメッセージを現在よりも少数のメッセージに集約することを特徴とする請求項１記載のメッセージキュー管理装置。
【請求項３】
前記所定の選択規準は、前記種類毎のメッセージの個数の相対的な大小関係と、前記メッセージキューに残すメッセージの個数及び前記メッセージ選択手法とが対応付けられた集約処理選択マップとして表され、
前記メッセージ集約手段は、前記集約処理選択マップを参照することにより、前記メッセージキューに残すメッセージの個数及び前記メッセージ選択手法を選択することを特徴とする請求項１又は２記載のメッセージキュー管理装置。
【請求項４】
前記メッセージ集約手段は、前記メッセージキューに残すメッセージをランダムに選択して、前記残すメッセージ以外を削除することを特徴とする請求項１乃至３何れか１項記載のメッセージキュー管理装置。
【請求項５】
前記メッセージ集約手段は、前記メッセージキューに残すメッセージを最新のものから順番に選択して、前記残すメッセージ以外を削除することを特徴とする請求項１乃至４何れか１項記載のメッセージキュー管理装置。
【請求項６】
前記メッセージ集約手段によるメッセージ集約の前後における前記マルチエージェントシステムの前記エージェントの行動変化に基づいて、前記エージェントの行動変化が大きく変化したときに、前記メッセージの集約結果が不適切であると評価する集約評価手段を備えることを特徴とする請求項１乃至５何れか１項記載のメッセージキュー管理装置。
【請求項７】
前記集約評価手段による評価結果を画面上に表示する評価結果表示手段を備えることを特徴とする請求項６記載のメッセージキュー管理装置。
【請求項８】
前記メッセージ集約手段によるメッセージ集約の前後における前記マルチエージェントシステムの前記エージェントの行動変化に基づいて、前記エージェントの行動変化が大きく変化したときに、前記メッセージの集約結果が不適切であると評価する集約評価手段と、
前記集約評価手段が前記メッセージの集約結果が不適切であると評価したとき、前記所定の集約規準を変更する集約規準変更手段と、
を備えることを特徴とする請求項２記載のメッセージキュー管理装置。
【請求項９】
マルチエージェントシステムにおけるエージェント間通信に用いられるメッセージキューを管理するメッセージキュー管理装置におけるメッセージキュー管理方法であって、
前記エージェントは、他のエージェントから送信されたメッセージを前記メッセージキューに保管するメッセージ保管ステップと、
前記メッセージキューに含まれるメッセージの個数が所定値を超えた場合に、前記メッセージの種類毎に前記メッセージキューに含まれるメッセージの個数を数え、その個数の相対的な大小に応じて、前記メッセージキューに残すメッセージの個数を前記メッセージの種類毎に決定し、前記メッセージキューに残すメッセージの個数および前記メッセージの種類毎に異なるメッセージ選択手法により前記メッセージキューに残すメッセージを選択して、前記残すメッセージ以外を削除することで前記メッセージキューに含まれるメッセージを現在よりも少数のメッセージに集約するメッセージ集約ステップと
を備えることを特徴とするメッセージキュー管理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、マルチエージェントシステムにおけるエージェント間通信に用いられるメッセージキュー管理装置及びメッセージキュー管理方法に係り、特に、メッセージキューのオーバーフローを防止するうえで好適なメッセージキュー管理装置及びメッセージキュー管理方法に関する。
【０００２】
【従来の技術】
マルチエージェントシステムは、自らの判断に基づいて自律的に行動する複数のエージェントが互いに協調動作することにより一定の目的を達成するシステムである。各々のエージェントは、システムの動作状態に関する情報（環境モデル）を保持しており、この情報に基づいて所定の目的を達成するための自律的な行動計画を立てることができる。かかるエージェントの機能を実現するため、エージェント間ではメッセージの通信が行われ、このメッセージ通信にはメッセージキューが用いられる。各エージェントは、他エージェントから受信したメッセージをいったんメッセージキューに入れる。そして、各エージェントは、メッセージキューから順次取り出したメッセージに基づいて環境モデルを修正していく。上記の如く、エージェントは、各々の判断に基づいて自律的に行動するものであるため、各エージェントがそれぞれ独自のメッセージキューを有することが望ましい。
【０００３】
【発明が解決しようとする課題】
一般に、エージェントは、コンピュータ上のプロセス又はスレッドとして実現される。ここで、コンピュータの処理能力により実行可能なプロセス又はスレッドの数には限界があり、また、半導体メモリやハードディスク等の記憶容量にも限界がある。従って、各エージェントに設けることが可能なメッセージキューの大きさにも制限が課せられる。一方、マルチエージェントシステムにおいて、エージェントの数が増加すると、エージェント間の通信量もそれに応じて大きくなるのに対し、各エージェントに割り当て可能なメッセージキューの大きさは小さくなる。このため、エージェント間の通信量が過大になると、メッセージキューがオーバフローし、メッセージ間通信を適切に実行することができなくなってしまう。従来では、このようなメッセージキューのオーバフローを回避するため、システムを大規模化し、又は、各メッセージキューに蓄えられるメッセージ数が一定値を超えた場合にシステムの動作を禁止するなどの措置を取る必要があった。
【０００４】
本発明は、上述の点に鑑みてなされたものであり、マルチエージェントシステムでのエージェント間通信に用いられるメッセージキューのオーバフローを、システムの大規模化やシステムの動作禁止等の措置を取ることなく適切に防止することが可能なメッセージキュー管理装置を提供することを目的とする。
【０００５】
【課題を解決するための手段】
上記の目的を達成するため、請求項１に記載された発明は、マルチエージェントシステムにおけるエージェント間通信に用いられるメッセージキューを管理するメッセージキュー管理装置であって、前記エージェントは、他のエージェントから送信されたメッセージを保管する前記メッセージキューと、前記メッセージキューに含まれるメッセージの個数が所定値を超えた場合に、前記メッセージの種類毎に前記メッセージキューに含まれるメッセージの個数を数え、その個数の相対的な大小に応じて、前記メッセージキューに残すメッセージの個数を前記メッセージの種類毎に決定し、前記メッセージキューに残すメッセージの個数および前記メッセージの種類毎に異なるメッセージ選択手法により前記メッセージキューに残すメッセージを選択して、前記残すメッセージ以外を削除することで前記メッセージキューに含まれるメッセージを現在よりも少数のメッセージに集約するメッセージ集約手段とを備えることを特徴とする。
【０００６】
また、請求項９に記載された発明は、マルチエージェントシステムにおけるエージェント間通信に用いられるメッセージキューを管理するメッセージキュー管理装置におけるメッセージキュー管理方法であって、前記エージェントは、他のエージェントから送信されたメッセージを前記メッセージキューに保管するメッセージ保管ステップと、前記メッセージキューに含まれるメッセージの個数が所定値を超えた場合に、前記メッセージの種類毎に前記メッセージキューに含まれるメッセージの個数を数え、その個数の相対的な大小に応じて、前記メッセージキューに残すメッセージの個数を前記メッセージの種類毎に決定し、前記メッセージキューに残すメッセージの個数および前記メッセージの種類毎に異なるメッセージ選択手法により前記メッセージキューに残すメッセージを選択して、前記残すメッセージ以外を削除することで前記メッセージキューに含まれるメッセージを現在よりも少数のメッセージに集約するメッセージ集約ステップとを備えることを特徴とする。
【０００７】
請求項１及び９記載の発明によれば、メッセージキューに含まれるメッセージを現在よりも少数のメッセージに集約することにより、メッセージキューのオーバフローを適切に防止できる。
【０００８】
また、請求項２に記載された発明は、請求項１記載のメッセージキュー管理装置において、前記メッセージ集約手段は、前記メッセージの種類毎に数えた前記メッセージキューに含まれるメッセージの個数の相対的な大小に基づく所定の選択規準に従って、前記メッセージキューに含まれるメッセージを現在よりも少数のメッセージに集約することを特徴とする。
【０００９】
また、請求項３に記載された発明は、請求項１又は２記載のメッセージキュー管理装置において、前記所定の選択規準は、前記種類毎のメッセージの個数の相対的な大小関係と、前記メッセージキューに残すメッセージの個数及び前記メッセージ選択手法とが対応付けられた集約処理選択マップとして表され、前記メッセージ集約手段は、前記集約処理選択マップを参照することにより、前記メッセージキューに残すメッセージの個数及び前記メッセージ選択手法を選択することを特徴とする。
【００１０】
また、請求項４に記載された発明は、請求項１乃至３何れか１項記載のメッセージキュー管理装置において、前記メッセージ集約手段は、前記メッセージキューに残すメッセージをランダムに選択して、前記残すメッセージ以外を削除することを特徴とする。
【００１１】
また、請求項５に記載された発明は、請求項１乃至４何れか１項記載のメッセージキュー管理装置において、前記メッセージ集約手段は、前記メッセージキューに残すメッセージを最新のものから順番に選択して、前記残すメッセージ以外を削除することを特徴とする。
【００１２】
また、請求項６に記載された発明は、請求項１乃至５何れか１項記載のメッセージキュー管理装置において、前記メッセージ集約手段によるメッセージ集約の前後における前記マルチエージェントシステムの前記エージェントの行動変化に基づいて、前記エージェントの行動変化が大きく変化したときに、前記メッセージの集約結果が不適切であると評価する集約評価手段を備えることを特徴とする。
【００１３】
また、請求項７に記載された発明は、請求項６記載のメッセージキュー管理装置において、前記集約評価手段による評価結果を画面上に表示する評価結果表示手段を備えることを特徴とする。
【００１４】
また、請求項８に記載された発明は、請求項２記載のメッセージキュー管理装置において、前記メッセージ集約手段によるメッセージ集約の前後における前記マルチエージェントシステムの前記エージェントの行動変化に基づいて、前記エージェントの行動変化が大きく変化したときに、前記メッセージの集約結果が不適切であると評価する集約評価手段と、前記集約評価手段が前記メッセージの集約結果が不適切であると評価したとき、前記所定の集約規準を変更する集約規準変更手段と、を備えることを特徴とする。
【００１５】
本発明によれば、メッセージ集約手段は、メッセージ集約が不必要に行われるのを防止できる。
【００１６】
本発明によれば、集約前にメッセージキューに含まれる情報を、集約後にメッセージキューに含まれる情報へ、より大きく反映させることができる。
【００１７】
本発明によれば、状況に応じた適切な手法でメッセージの集約を行うことができる。
【００１８】
本発明によれば、メッセージの内容に応じた適切なメッセージ集約処理を実行できる。
【００１９】
本発明によれば、各種類のメッセージの個数に応じた適切なメッセージ集約処理を実行できる。
【００２０】
本発明によれば、集約手段の選択が簡易な処理で実現できる。また、本発明によればメッセージキューに含まれるメッセージの内容にばらつきが大きい場合に、効果的なメッセージ集約処理を実現できる。また、本発明によれば新しいメッセージほど信頼性が高い場合に、効果的なメッセージ集約処理を実現できる。また、本発明によればメッセージ集約処理の適否を判定できる。また、システム操作者は、評価の結果を知ることができる。従って、システム操作者は、評価の結果に基づいて、手動でこの選択規準を変更することができる。また、本発明によれば選択規準を、より適切な集約手段が選択されるように自動的に修正することができる。また、本発明によればメッセージの集約結果を適正に評価することができる。
【００２１】
【発明の実施の形態】
図１は、本発明に係るメッセージキュー管理装置が適用されるマルチエージェントシステムを示す概念図である。図１に示すマルチエージェントシステムにおいて、複数のエージェント１０はそれぞれコンピュータ上のスレッド又はプロセスとして構成されており、互いに協調動作しながら移動する自律移動ロボットの動作をシミュレートする。エージェント１０の目的は、互いに協調動作することによりターゲット１２を囲い込んで捕獲する（つまり、動けなくする）ことである。ターゲット１２は、エージェント１０の囲いから逃れるように移動する。なお、図１における縦横の座標は各エージェント１０及びターゲット１２の現在位置を表している。また、図１において、エージェント１０及びターゲット１２は、それらの現在位置までの移動経路と共に示されている。
【００２２】
上記の協調動作を実現するため、各エージェント１０は、自エージェントがターゲット１２に対してどの方向から接近しようとしているかを示すメッセージ（以下、移動予告メッセージと称す）、及び、他エージェントにターゲットに対してどの方向から接近してほしいかを示すメッセージ（以下、移動依頼メッセージと称す）を送信する。後述の如く、各エージェント１０は、他エージェントから受信した移動予告メッセージ及び移動依頼メッセージに基づいて、環境モデルを逐次修正し、その環境モデルに基づいて自己の行動計画を立てる。そして、その行動計画に応じた移動予告メッセージ及び移動依頼メッセージを他エージェントに向けて送信する。
【００２３】
図２は、各エージェント１０の構成を示す概念図である。図２に示す如く、エージェント１０は、処理部１４、データ保持部１６、通信部１８、及びメッセージキュー２０を備えている。他エージェントから送信されたメッセージは通信部１８により受信され、メッセージキュー２０に保管される。データ保持部１６には、システムの動作状態（即ち、ターゲット１２及び各エージェント１０の位置や移動方向等の状態）を表す環境モデルが記憶されている。処理部１４は、メッセージキュー２０から順次受信メッセージを取り出し、そのメッセージの内容と、ターゲット１２及び自エージェントの現在位置及び移動方向とに基づいて環境モデルを修正する。そして、修正された環境モデルに基づいて、エージェント１０の行動計画を立てる（即ち、自分自身がどの方向からターゲット１２に接近するか、及び、他のエージェント１０がどの方向からターゲット１２に接近してほしいかを決定する）と共に、通信部１８を介して、行動計画に応じた移動予告メッセージ及び移動依頼メッセージを送信する。なお、処理部１４はターゲット１２の位置及び移動方向を常時認識できるものとする。ターゲット１２の位置及び移動方向の認識は、物理的なロボットにおいて、距離センサやテレビカメラ等によってターゲット１２の位置及び移動方向を検出することに対応する。
【００２４】
図１に示すシステムにおいて、エージェント１０間のメッセージ通信は、ブロードキャストでメッセージを他エージェントに対して一斉に送信することにより行われる。ブロードキャストでの通信によれば、エージェント１０の故障又は追加によりエージェント１０の個数が変動した場合にも、その影響を受けることなくエージェント間通信を適切に行うことができる。このため、各エージェント１０間に個別の通信路を確立して通信を行う場合に比べて、エージェント数の変化に適応し得る柔軟性に富んだシステムを実現できる。また、通信を集中管理する主エージェントが存在しないため、そのような主エージェントの故障により通信が行なえなくなることを防止できる。
【００２５】
図３は、エージェント間通信で用いられるメッセージの内容を示す。図３に示す如く、メッセージは、発信者識別情報２２、メッセージ識別情報２４、及び、接近方向識別情報２６を含んでいる。発信者識別情報２２は、メッセージを送信したエージェント１０を識別するための情報である。メッセージ識別情報２４は、当該メッセージが移動予告メッセージ又は移動依頼メッセージの何れであるかを識別するための情報である。また、接近方向識別情報は、ターゲット１２に対する移動方向を識別するための情報である。なお、本実施例において、ターゲット１２に対する接近方向は、例えば、上、下、左、右、左上、左下、右上、及び右下の８方向のうちの何れかで表されるものとする。ただし、上下左右の４方向に簡略化してもよく、あるいは、上記の８方向よりも更に細かく方向を規定してもよい。
【００２６】
ところで、各エージェント１０が備えるメッセージキュー２０に保管し得るメッセージの個数は、システムの資源（システムが動作するコンピュータの処理能力やメモリ容量等）によって制限される。このため、エージェント１０の個数が増大すると、メッセージ間通信の頻度が高くなった場合に、各メッセージキュー２０に保管すべきメッセージ数が過大となり、メッセージキュー２０がオーバーフローすることが起こり得る。メッセージキュー２０がオーバフローすると、メッセージ間の通信が正常に行われなくなることで、システムの動作に不具合が生ずる可能性がある。
【００２７】
これに対して、本実施例のマルチエージェントシステムは、メッセージキュー２０に含まれるメッセージの個数が一定値を超えた場合に、所定の手法により少数のメッセージに集約することで、システム動作に対する影響を最小限に抑えつつ、メッセージキュー２０のオーバフローを防止するものである。以下、本実施例において、メッセージキュー２０のメッセージを集約する手法について説明する。
【００２８】
図４は、本実施例において、メッセージの集約処理を行うべく各エージェント１０が参照するマップ（以下、集約処理選択マップと称す）の一例を示す。図３において、横軸はメッセージキュー２０に含まれる移動依頼メッセージの個数Ｎ１を示し、縦軸はメッセージキュー２０に含まれる移動予告メッセージの個数Ｎ２を示す。エージェント１０は、メッセージキュー２０に含まれるメッセージ数が所定値を超えると、移動依頼メッセージ及び移動予告メッセージの個数Ｎ１、Ｎ２を数え、図４に示す集約処理選択マップを参照することにより、処理Ｉ〜IVの何れの処理を実行すべきかを判断する。図４に示す如く、集約処理選択マップによれば、移動予告メッセージの個数Ｎ２と移動依頼メッセージの個数Ｎ１との相対的な大小に応じて、移動予告メッセージの個数Ｎ２が大きい側から順に、処理Ｉ、II、III 、及びIVが選択され実行される。
【００２９】
移動予告メッセージの個数Ｎ２が移動依頼メッセージの個数Ｎ１より十分に大きい場合（例えば、Ｎ２＞α・Ｎ１が成立する場合；ただし、αは１より大きい所定値）には、処理Ｉが実行される。処理Ｉでは、メッセージキュー２０に含まれる移動予告メッセージのうち最新の３個の移動予告メッセージのみが残され、他の移動予告メッセージ及び移動依頼メッセージは全て削除される。
【００３０】
移動予告メッセージの個数Ｎ２が移動依頼メッセージの個数Ｎ１よりもある程度大きい場合（例えば、α・Ｎ１≧Ｎ２＞Ｎ１が成立する場合）には、処理IIが実行される。処理IIでは、メッセージキュー２０に含まれる移動予告メッセージのうち最新の２個の移動予告メッセージ、及び、メッセージキュー２０に含まれる移動依頼メッセージのうちランダムに選択した１個の移動依頼メッセージのみが残され、他のメッセージは全て削除される。
【００３１】
移動依頼メッセージの個数Ｎ１が移動予告メッセージの個数Ｎ２よりある程度大きい場合（例えば、α・Ｎ２＞Ｎ１≧Ｎ２が成立する場合）には、処理III が実行される。処理III では、メッセージキュー２０に含まれる移動予告メッセージのうち最新の１個の移動予告メッセージ、及び、メッセージキュー２０に含まれる移動依頼メッセージのうちランダムに選択した２個の移動依頼メッセージのみが残され、他のメッセージは全て削除される。
【００３２】
移動依頼メッセージの個数Ｎ１が移動予告メッセージの個数Ｎ２より十分に大きい場合（例えば、Ｎ１≧α・Ｎ２が成立する場合）には、処理IVが実行される。処理IVでは、メッセージキュー２０に含まれる移動依頼メッセージのうちランダムに選択された３個の移動依頼メッセージのみが残され、他の移動依頼メッセージ及び移動予告メッセージは全て削除される。
【００３３】
上記した処理Ｉ〜IVにおいて、移動予告メッセージについては最新のメッセージを残し、移動依頼メッセージについてはランダムに選択したメッセージを残すこととしているのは、以下の理由による。
即ち、移動予告メッセージは、各エージェント１０が移動しようとする方向を予告するものであり、送信元のエージェント１０は移動予告メッセージに含まれる情報の通りに行動する蓋然性が高い。即ち、移動予告メッセージが発せられた時点での、その信頼性は高い。従って、移動予告メッセージは、新しいものほど情報としての有用性が大きいといえる。そこで、移動予告メッセージについては、最新のメッセージを優先して残すこととしているのである。
【００３４】
また、各エージェント１０は、他エージェントの行動計画とは無関係に自己の行動計画を立て、それぞれの行動計画に適合するように他エージェントに対して移動依頼メッセージを発信する。このため、他エージェントから送られてくる移動依頼メッセージの内容は、その発信元によってばらつくこととなり、メッセージが新しいほど情報として有用であるとは必ずしもいえない。また、常に一定の手法でメッセージの集約を行うものとすると、システムの作動状態が一定の状態に陥ったまま逃れられなくなり、その結果、各エージェント１０がデッドロック状態となったり、ターゲット１２にいつも同じ方向からに逃げられる等の不都合を招く可能性がある。これに対して、メッセージ集約処理にランダムな要素を含めることとすれば、システムの作動状態を新たな局面に変化させることができるため、上記の如き不都合を回避することが可能となる。これらの観点より、移動依頼メッセージについては、ランダムに選択したメッセージを残すこととしているのである。
【００３５】
上記の如く、本実施例では、移動依頼メッセージ及び移動予告メッセージについて、それぞれ、各メッセージの性質に応じた方法で集約後に残すべきメッセージを選択することにより、メッセージ集約がエージェント１０の行動計画に与える影響を小さく抑えることができる。更に、各メッセージの個数Ｎ１、Ｎ２に応じて、集約後に残すべき各メッセージの個数が定められることで、メッセージ集約前にメッセージキュー２０に含まれる情報を、メッセージ集約後のメッセージキュー２０に含まれる情報へ、より大きく反映させることができる。
【００３６】
なお、メッセージの集約をより効果的に行う上では、より少数のメッセージに集約することが好ましいといえる。しかし、集約により残すべきメッセージの個数が少な過ぎると、メッセージ集約処理の前後で各エージェント１０の動作が急変し、システムの安定な動作を確保できなくなる可能性がある。そこで、本実施例では、これらの点を勘案し、上記の如く、処理Ｉ〜IVにおいてメッセージを３個に集約することとしている。ただし、集約後のメッセージの個数は３個に限らず、メッセージキュー２０の容量等に応じて４個以上又は２個以下のメッセージに集約することとしてもよい。また、処理に応じて集約後のメッセージ数を変えることとしてもよい。なお、集約処理によりメッセージキュー２０に残すべき各種類のメッセージの個数は、例えば、上記処理Ｉ〜IVと同様に集約前にメッセージキュー２０に含まれていた各種類のメッセージの個数に応じて配分すればよい。
【００３７】
ところで、図４に示す集約処理選択マップは、システム設計者により予め設定される。このため、集約処理選択マップは、初期状態では必ずしも最適なものとはいえず、システムの動作状況に応じて集約処理マップを適宜修正することが望ましい。そこで、本実施例では、以下の手法により、メッセージの集約が適切に行われたか否かを判別し、適切に行われていないと判別された場合には、集約処理選択マップを修正することとしている。
【００３８】
図５は、メッセージの集約処理の結果に基づいて集約判定処理マップを修正する手法を説明するための図である。図５に示す如く、例えば、メッセージキュー２０の現在の状態が点Ｐで表される場合、処理IIが選択されることになる。この処理IIによりメッセージが集約された結果、エージェント１０の行動計画が大きく変化した場合（例えば、エージェント１０の移動方向がメッセージ集約前後で所定角度以上変化した場合）には、処理IIによるメッセージの集約は不適切と判定される。即ち、マルチエージェントシステムが適切に動作している場合は、各エージェント１０は頻繁に方向を変えることなく比較的スムーズに移動すると考えられるため、メッセージ集約処理によってエージェント１０の移動方向が大きく変化した場合には、その集約処理は不適切であると判断できるのである。
【００３９】
上記のように処理IIが不適切と判定されると、処理IIと隣接する処理との境界が変更される。具体的には、例えば図５に破線で示す如く、処理IIに隣接する処理Ｉ及び処理III のうち、点Ｐに近い方の処理III との境界が点Ｐに近づくように（つまり、処理III の領域が広がるように）変更される。なお、エージェント１０の現在の状態が図５に示す点Ｑのように領域間の境界に近い場合は、点Ｑが、領域IIに隣接する領域（処理III ）に含まれるように境界線を変更してもよい。また、図５に一点鎖線で示す如く、点Ｐ又はＱに近い境界線の一部が点Ｐに接近するように（又は点Ｑを含むように）、境界線を部分的に変更してもよい。
【００４０】
このように、メッセージ集約処理の前後でエージェント１０の行動計画が大きく変化した場合に、マップ上で隣接する領域が現在位置に近づくように境界線が変更されることで、集約処理選択マップは、不適切な集約処理が行われ難いように自動的に調整されることとなる。
以下、図６乃至図９を参照して、本実施例において各エージェント１０の動作をシミュレートすべく実行される処理の内容について説明する。図６〜図８は、エージェント１０によるターゲット１２の囲い込み動作をシミュレートするルーチンのフローチャートである。また、図９は、図６〜図８に示すルーチンにおいて、メッセージキュー２０のメッセージ集約処理を行うべく実行されるサブルーチンのフローチャートである。
【００４１】
先ず、図６〜図８に示すルーチンについて説明する。なお、上記の如く、各エージェント１０はコンピュータ上のスレッドとして実現される。同様に、ターゲット１２もコンピュータ上のスレッドとして実現される。図６〜図８に示すフローチャートでは、各エージェント１０に対するスレッド（以下、エージェントスレッドと称す）を図７に、ターゲット１２に対するスレッド（以下、ターゲットスレッドと称す）を図８に、それぞれ示している。図６〜図８に示すルーチンが起動されると、先ずステップ１００の処理が実行される。
【００４２】
ステップ１００では、ターゲット１２の初期位置が設定され、続くステップ１０２では、各エージェント１０の初期位置が設定される。
ステップ１０４では、エージェントスレッド及びターゲットスレッドがそれぞれ起動される。先ず、エージェントスレッドにおける処理について説明する。なお、エージェントスレッドは各エージェント１０毎に起動される。エージェントスレッドが起動されると、先ずステップ１１０の処理が実行される。
【００４３】
ステップ１１０では、メッセージキュー２０が空であるか否かが判別される。その結果、メッセージキュー２０が空でなければ、次にステップ１１２の処理が実行される。一方、メッセージキュー２０が空であれば、次にステップ１１４の処理が実行される。
ステップ１１２では、メッセージキュー２０に含まれるメッセージの個数Ｎが所定値Ｎr 以上であるか否かが判別される。その結果、Ｎ≧Ｎr が成立する場合は、次に、ステップ１１６において、フラグＦが「１」にセットされた後、ステップ１１８において、メッセージキュー２０のメッセージを集約するための処理、即ち、図９に示すサブルーチンが起動される。一方、ステップ１１２において、Ｎ≧Ｎr が不成立であれば、次にステップ１２０において、フラグＦが「０」にリセットされた後、ステップ１２２の処理が実行される。即ち、フラグＦは、メッセージ集約処理が実行される場合にのみ「１」にセットされる。ステップ１１８において図９に示すサブルーチンが起動されると、先ずステップ２００の処理が実行される。
【００４４】
ステップ２００では、メッセージキュー２０に含まれる移動依頼メッセージの個数Ｎ１及び移動予告メッセージの個数Ｎ２が求められる。
ステップ２０２では、上記図４に示す集約処理選択マップを参照することにより、上記個数Ｎ１及びＮ２に基づいて処理I 〜IVのうち何れかの処理が選択される。例えば、移動依頼メッセージの個数Ｎ１が９、移動予告メッセージの個数Ｎ２が１０である場合は、処理IIが選択される。
【００４５】
ステップ２０４では、上記ステップ２０２で選択された処理が実行されることにより、メッセージキュー２０に含まれるメッセージが３個に集約される。
ステップ２０６では、変数Ｐに、処理Ｉ〜IVのうち実行された処理を示す識別番号が代入される。ステップ２０６の処理が終了すると、図７に示すルーチンへ戻り、ステップ１２２の処理が実行される。
【００４６】
ステップ１２２では、メッセージキュー２０の所定位置（例えば先頭）にある１個のメッセージが取り出され、続くステップ１２４では、取り出されたメッセージの内容に基づいて、エージェント１０に記憶された環境モデルが更新される。
ステップ１２６では、更新された環境モデルに基づいて行動計画が再計算され、自エージェントがターゲット１２に対してどの方向から接近するか、及び、他エージェントにターゲット１２に対してどの方向からの接近を要求するかが決定される。そして、自エージェントのターゲット１２に対する接近方向と、自エージェントの現在位置に基づいて、自エージェントの移動方向が決定される。
【００４７】
ステップ１２８では、フラグＦが「１」にセットされているか否か（即ち、メッセージ集約処理が実行されたか否か）が判別される。その結果、Ｆ＝１が不成立であれば、再び上記ステップ１１０の処理が実行される。一方、Ｆ＝１が成立する場合は、次にステップ１３０の処理が実行される。
ステップ１３０では、上記ステップ１２６で決定された行動計画が、前回のルーチンで決定された行動に対して大きく変化しているか否か、即ち、メッセージ集約処理の実行前後で、エージェント１０の行動計画が大きく変化したかが判別される。具体的には、行動計画に基づいて決定された自エージェントの移動方向が所定角度以上（例えば１８０゜）変化した場合に、行動計画が大きく変化したと判断される。その結果、メッセージ集約処理の前後で行動計画が大きく変化したと判断された場合は、次にステップ１３２の処理が実行される。一方、ステップ１３０で、行動計画は大きく変化していないと判別された場合は、再び上記ステップ１１０の処理が実行される。
【００４８】
ステップ１３２では、変数Ｐの値に基づいて、メッセージ集約処理において実行された処理が識別され、上記図５を参照して説明した手法に従って、集約処理選択マップが修正される。即ち、実行された処理に集約判定処理マップ上で隣接する領域のうち、メッセージ集約前の各メッセージの個数Ｎ１及びＮ２で規定される点に近い方の領域との境界がこの点に近づくように（又は隣接領域がこの点を含むように）、集約処理選択マップが修正される。ステップ１３２の処理が終了すると、再び上記ステップ１１０の処理が実行される。
【００４９】
上記ステップ１１０でメッセージキュー２０が空である場合に実行されるステップ１１４では、現在の行動計画に基づいて、他エージェントに向けて移動依頼メッセージ及び移動予告メッセージが送信され、続く、ステップ１３４では、現在の行動計画に従って、エージェント１０を移動させる（即ち、エージェント１０の現在位置を更新する）処理が実行される。ステップ１３４の処理が終了すると、再びステップ１１０の処理が実行される。
【００５０】
一方、上記ステップ１０４において、図８に示すターゲットスレッドが起動されると、先ずステップ１５０の処理が実行される。
ステップ１５０では、所定時間Ｔ0 が経過するまで待機する処理が実行される。この所定時間Ｔ0 は、ターゲット１２の移動時間間隔に相当する。
ステップ１５２では、ターゲット１２に対してエージェント１０の存在密度が最も小さい方向が演算される。
【００５１】
ステップ１５４では、ターゲット１２が、ステップ１５２で演算された方向へ、エージェント１０に阻まれることなく移動できるか否かが判別される。その結果、否定判別された場合は、ターゲット１２がエージェント１０により囲まれたと判断できる。この場合、ターゲット１２の囲い込みが成功したことになり、次にステップ１５６において、囲い込みが成功した旨の表示がなされた後、本シミュレーションは終了する。
【００５２】
一方、ステップ１５４において、肯定判別された場合は、次にステップ１５８において、ステップ１５２で計算された方向へターゲット１２を移動させる処理が実行され、続くステップ１６０において、ターゲット１２の移動回数を示すカウンタＣＴがインクリメントされる。
ステップ１６２では、カウンタＣＴが所定値Ｃ0 を超えたか否かが判別される。その結果、ＣＴ＞Ｃ0 が成立する場合は、ターゲット１２の囲い込みは失敗したと判断され、ステップ１６４において、囲い込みに失敗した旨の表示がなされた後、本シミュレーションは終了する。一方、ステップ１６２において、ＣＴ＞Ｃ0 が不成立であれば、再びステップ１５０の処理が実行される。
【００５３】
上述の如く、本実施例によれば、メッセージキュー２０に含まれるメッセージの個数が所定値以上となった場合に、移動依頼メッセージの個数Ｎ1 及び移動予告メッセージの個数Ｎ2 に応じた適切なメッセージ集約処理が実行されることで、システム動作への影響を小さく抑えつつ、メッセージキュー２０のオーバーフローを防止できる。この場合、メッセージの個数が所定値未満の場合には、メッセージ集約処理が実行されないため、メッセージ集約処理が不必要に（即ち、メッセージキュー２０がオーバフローする可能性がないのに）実行されるのを防止することができる。
【００５４】
また、集約処理選択マップの参照という簡便な処理でメッセージ集約処理の選択が行われるため、各エージェント１０（あるいは、エージェント１０を実現するコンピュータ）への処理負担を軽減することができる。更に、メッセージ集約処理の結果に基づいて集約処理選択マップが変更されることで、より最適なメッセージ集約処理を実行することが可能となる。
【００５５】
なお、上記実施例では、本発明が、ターゲットの囲い込み動作を行う自律移動ロボットをシミュレートするマルチエージェントシステムに適用された場合について説明したが、本発明はこれに限定されるものではなく、複数のエージェントが協調動作して共通の目的を達成すべく自律的に動作する任意のマルチエージェントシステムに適用可能である。
【００５６】
また、上記実施例では、メッセージとして移動依頼メッセージ及び移動予告メッセージの２種類のメッセージが用いられるものとしたが、本発明は、１種類又は３種類以上のメッセージが用いられる場合にも適用が可能である。この場合、集約処理選択マップは、メッセージの種類の数に応じた次元（例えば、３種類のメッセージが用いられる場合は３次元）のマップとして表されることになる。
【００５７】
ところで、上記実施例では、メッセージ集約処理において、移動予告メッセージについては最新のメッセージを選択し、また、移動依頼メッセージについてはランダムにメッセージを選択し、これらを組み合わせて処理Ｉ〜IVを実現することとしたが、メッセージを集約する方法はこれらに限定されるものではない。例えば、メッセージキュー２０に含まれる各種類のメッセージについて：
▲１▼接近方向識別情報２６を平均した値の接近方向識別情報を有するメッセージに集約する；
▲２▼同じ接近方向識別情報を有するメッセージが多数含まれるほど、その接近方向識別情報を有するメッセージが多数残る（即ち、接近方向識別情報の方向別の頻度に応じて残すメッセージが決定される）ように集約する；
▲３▼最新の所定個のメッセージについて▲１▼又は▲２▼の手法で集約する；等、種々の方法でメッセージを集約することが可能である。何れの方法を用いてメッセージを集約するかは、適用されるシステム及び通信されるメッセージの性質に応じて、システムがより効果的に動作するように定めることとすればよい。
【００５８】
また、上記実施例では、各メッセージの個数Ｎ１、Ｎ２に応じて、４種類の処理Ｉ〜IVから何れかの処理が選択されるものとしたが、これに限らず、３種類以下、又は、５種類以上の集約処理の中から何れかの処理を選択することとしてもよい。
更に、上記実施例では、各エージェント１０が同じコンピュータ上のスレッド又はプロセスにより構成されるものとしたが、これに限らず、各エージェントは互いに異なるコンピュータ上で動作し、コンピュータ間でエージェント同士の通信が行われることとしてもよい。
【００５９】
また、上記実施例では、メッセージの集約結果に基づいて、集約処理選択マップを自動的に変更するものとしたが、例えば、図５に示す如きマップをメッセージ集約が適切に行われなかった点Ｐ又はＱと共に画面上に表示し、システム操作者がこの画面を参照しながら集約処理選択マップを手動で変更することとしてもよい。
【００６０】
【発明の効果】
本発明によれば、メッセージキューのオーバフローを適切に防止できる。また、本発明によれば、メッセージの集約が不必要に行われるのを防止できる。
【００６１】
本発明によれば、集約前にメッセージキューに含まれる情報を、集約後にメッセージキューに含まれる情報へ、より大きく反映させることができる。また、本発明によれば、状況に応じた適切な手法でメッセージの集約を行うことができる。
【００６２】
本発明によれば、メッセージの内容に応じた適切なメッセージ集約処理を実行できる。また、本発明によれば、各種類のメッセージの個数に応じた適切なメッセージ集約処理を実行できる。
【００６３】
本発明によれば、集約手段の選択が簡易な処理で実現できる。また、本発明によれば、メッセージキューに含まれるメッセージの内容にばらつきが大きい場合に、効果的なメッセージ集約処理を実現できる。
【００６４】
本発明によれば、新しいメッセージほど信頼性が高い場合に、効果的なメッセージ集約処理を実現できる。また、本発明によれば、メッセージ集約処理の適否を判定できる。
【００６５】
本発明によれば、システム操作者は評価の結果を知ることができる。したがぅて、所定の選択規準に基づいて集約手段が選択される場合、システム操作者は、評価の結果に基づいて、手動でこの選択規準を変更することができる。また、本発明によれば、この選択規準を、より適切な集約手段が選択されるように自動的に修正することができる。
【００６６】
本発明によれば、メッセージの集約結果を適正に評価することができる。
【図面の簡単な説明】
【図１】本発明に係るメッセージキュー管理装置が適用されるマルチエージェントシステムを示す概念図である。
【図２】各エージェント１０の構成を示す概念図である
【図３】エージェント間通信で用いられるメッセージの内容を示す図である。
【図４】メッセージの集約処理を行うべく各エージェントが参照する集約処理選択マップの一例を示す図である。
【図５】メッセージ集約処理の結果に基づいて集約判定処理マップを修正する手法を説明するための図である。
【図６】エージェントによるターゲットの囲い込み動作をシミュレートするメインルーチンのフローチャートである。
【図７】図６に示すルーチンで起動されるエージェントスレッドのフローチャートである。
【図８】図６に示すルーチンで起動されるターゲットスレッドのフローチャートである。
【図９】図７に示すルーチンにおいて、メッセージキューのメッセージ集約処理を行うべく実行されるサブルーチンのフローチャートである。
【符号の説明】
１０  エージェント
１２  ターゲット
１４  処理部
１６  データ保持部
１８  通信部
２０  メッセージキュー
【図１】
0003898860.tif 000002
【図２】
0003898860.tif 000003
【図３】
0003898860.tif 000004
【図４】
0003898860.tif 000005
【図５】
0003898860.tif 000006
【図６】
0003898860.tif 000007
【図７】
0003898860.tif 000008
【図８】
0003898860.tif 000009
【図９】
0003898860.tif 000010