(57)【要約】【課題】実環境で複数のタスクを実行するシステムおける、非同期で発生するタスクに対し干渉のないプランニングを可能にすること、そして、そのプランニングを実時間内に完了可能にすることを両立させることのできるマルチ・エージェントシステムを実現することにある。【解決手段】本発明のマルチ・エージェントシステムは、複数のパーソナル・エージェント１と、共有メモリ装置２とを備え、上記共有メモリ装置２は、パーソナル・エージェント１から受け取ったプランの干渉を、既に格納している他のパーソナル・エージェント１から受け取ったプランから判定し、判定結果をプランの干渉情報として上記パーソナル・エージェント１に送信し、上記パーソナル・エージェント１は、発生するタスクに対応する環境から取得した環境情報と、上記共有メモリ装置２から受け取ったプランの干渉情報とを考慮して、上記プランを作成する。【選択図】図１
2009134652.tif 000002
【特許請求の範囲】
【請求項１】
非同期で発生する複数のタスクそれぞれに対応して設けられ、タスク実行のための複数のアクションで構成されたプランを作成するエージェントと、
上記エージェントによって作成されたプランを、他のエージェントから参照可能に格納する共有メモリ装置とを備え、
上記共有メモリ装置は、
エージェントから受け取ったプランの干渉を、既に格納している他のエージェントから受け取ったプランから判定し、判定結果をプランの干渉情報として上記エージェントに送信し、
上記エージェントは、
発生するタスクに対応する環境から取得した環境情報と、上記共有メモリ装置から受け取ったプランの干渉情報とを考慮して、上記プランを作成することを特徴とするマルチ・エージェントシステム。
【請求項２】
上記エージェントは、
上記プランを作成すると共に、該プランを構成するアクション毎に、作成したプランからアクションの重要度を示すアクション値を算出するプランニング部を備え、
上記プランニング部で作成したプランと算出したアクション値とを上記共有メモリ装置に格納し、
上記共有メモリ装置は、
受け取ったプランを構成するアクションが、既に格納されている他のエージェントのプランを構成するアクションと干渉するか否かを判定する干渉判定部と、
上記干渉判定部によって干渉すると判定されたとき、干渉有りと判定されたアクションの実行を、該アクションのアクション値と、該アクションと干渉しているアクションのアクション値とを比較することで行う実行判定部とを備え、
上記実行判定部の判定結果をプランの干渉情報として、上記エージェントに送信することを特徴とする請求項１に記載のマルチ・エージェントシステム。
【請求項３】
コンピュータを、請求項１または２の何れかに記載のマルチ・エージェントシステムに備えられた各部として機能するプログラム。
【請求項４】
請求項３に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、非同期で発生するタスクに対して干渉のないプランニングを行うための技術、特に、複数のエージェントを用いて上記プランニングを行うマルチ・エージェントシステムに関するものである。
【背景技術】
【０００２】
実環境で複数のタスクを実行するシステムには、非同期で発生するタスクに対し干渉のないプランニングが可能であること、そのプランニングを実時間内に完了可能であることの二点が必要である。ここで、実時間内で完了（実行）するとは、例えば、自律移動型ロボットなどが実環境の動的な変化に対して自然に対応しそのプランを実行することを意味する。
【０００３】
前者を行う方法として非特許文献１，２などが挙げられる。
【０００４】
また、後者を行う方法として非特許文献３，４などが挙げられる。
【非特許文献１】Jeffrey S. Cox and Edmund H. Durfee. An efficient algorithm for multiagent plan coordination. (AAMAS-06), 2006.
【非特許文献２】Yannis Dimopoulos and Pavlos Moraitis. Multiagent coordination and cooperation through classical planning. (IAT’06), 2006.
【非特許文献３】Michael P. Georgeff and Amy L. Lansky. Reactive reasoning and planning. (AAAI-87), 1987.
【非特許文献４】Shlomo Zilberstein. Using anytime algorithms in intelligent systems. AI Mag, No. 17, pp. 73.83, 1996.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記非特許文献１，２は、静的環境を想定した技術であり、また、上記非特許文献３，４は、一つのタスクのプランニングを行う技術であるので、実環境で複数のタスクを実行するようなシステムに適用することができない。
【０００６】
従って、上記の各非特許文献では、実環境で複数のタスクを実行するシステムおける、非同期で発生するタスクに対し干渉のないプランニングを可能にすること、そして、そのプランニングを実時間内に完了可能にすることを両立させることができないという問題が生じる。
【０００７】
本発明は、上記の問題点に鑑みてなされたものであり、その目的は、実環境で複数のタスクを実行するシステムおける、非同期で発生するタスクに対し干渉のないプランニングを可能にすること、そして、そのプランニングを実時間内に完了可能にすることを両立させることのできるマルチ・エージェントシステムを実現することにある。
【課題を解決するための手段】
【０００８】
本発明に係るマルチ・エージェントシステムは、上記課題を解決するために、非同期で発生する複数のタスクそれぞれに対応して設けられ、タスク実行のための複数のアクションで構成されたプランを作成するエージェントと、上記エージェントによって作成されたプランを、他のエージェントから参照可能に格納する共有メモリ装置とを備え、上記共有メモリ装置は、エージェントから受け取ったプランの干渉を、既に格納している他のエージェントから受け取ったプランから判定し、判定結果をプランの干渉情報として上記エージェントに送信し、上記エージェントは、発生するタスクに対応する環境から取得した環境情報と、上記共有メモリ装置から受け取ったプランの干渉情報とを考慮して、上記プランを作成することを特徴としている。
【０００９】
上記の構成によれば、各エージェントは、共有メモリ装置内において他のエージェントが作成したプランとの比較の結果得られたプランの干渉情報を考慮して、プランを実行できるようになっているので、他のエージェントのプランと干渉しない状況にてプランを実行することが可能となる。このように、各エージェントは、常にプランを完成させた状態で他のエージェントのプランとの干渉を回避するようになっているので、実時間内で協調を完了することが可能となる。
【００１０】
以上のことから、実環境で複数のタスクを実行するシステムおける、非同期で発生するタスクに対し干渉のないプランニングを可能にすること、そして、そのプランニングを実時間内に完了可能にすることを両立させることのできるマルチ・エージェントシステムを実現することができる。
【００１１】
また、上記エージェントは、上記プランを作成すると共に、該プランを構成するアクション毎に、作成したプランからアクションの重要度を示すアクション値を算出するプランニング部を備え、上記プランニング部で作成したプランと算出したアクション値とを上記共有メモリ装置に格納し、上記共有メモリ装置は、受け取ったプランを構成するアクションが、既に格納されている他のエージェントのプランを構成するアクションと干渉するか否かを判定する干渉判定部と、上記干渉判定部によって干渉すると判定されたとき、干渉有りと判定されたアクションの実行を、該アクションのアクション値と、該アクションと干渉しているアクションのアクション値とを比較することで行う実行判定部とを備え、上記実行判定部の判定結果をプランの干渉情報として、上記エージェントに送信するようにしてもよい。
【００１２】
この場合、上記のアクション値は、プランの更新と連動して再計算されるので、より良いプランに改善することができる。そして、この結果は、共有メモリ装置において、他のエージェントにとって間接的に共有されるので、プラン生成とプラン協調の両方を時間制約下で実行可能とする。
【発明の効果】
【００１３】
本発明に係るマルチ・エージェントシステムは、以上のように、実環境で複数のタスクを実行するシステムに必要となる二つの性質の両立が可能となる。また、本発明のマルチ・エージェントシステムは、高い汎用性をもつため、今後幅広い分野への適用が期待できるという効果を奏する。
【発明を実施するための最良の形態】
【００１４】
本発明の一実施形態について説明すると以下の通りである。
【００１５】
すなわち、本実施の形態に係るマルチ・エージェントシステムは、図１に示すように、複数のパーソナル・エージェント１・・・・と一つの共有メモリ装置２から構成される。
【００１６】
各パーソナル・エージェント１は、他のパーソナル・エージェント１と直接結びついて情報を交換するのではなく、共有メモリ装置２を介して間接的に情報の共有を図るようになっている。また、各パーソナル・エージェント１は、他のパーソナル・エージェント１の動作と独立した形で環境情報を取得することや、環境に対してアクションを実行することが可能である。
【００１７】
上記パーソナル・エージェント１は、プランナー１１とエグゼキューター１２で構成され、次のように動作する。
【００１８】
プランナー１１は、目標状態へのプランを生成し、エグゼキューター１２のプラン要求に応じて一度共有メモリ装置２に生成したプランを渡して干渉の有無を確認し、確認したプランをエグゼキューター１２に渡す。
【００１９】
エグゼキューター１２は、プランナー１１から渡されたプランに従って環境に対してアクションを実行したり、アクションの効果を含めた環境情報を観察したりする。
【００２０】
ここで、上記プランナー１１は、エグゼキューター１２からの想定していないイベントや共有メモリ装置２からのプラン干渉を受け付けない限り、現在のプランを最適なプランになるよう更新し続ける。
【００２１】
上記プランナー１１のプランニング過程について説明すると以下のようになる。
【００２２】
ここで、時間制約下でのプランニング方法として、任意時間アルゴリズムを採用する。
【００２３】
任意時間アルゴリズムは, プランニングに与えられた時間の長短に関わらず, 常にその時点での最善のプランを返すようなアルゴリズムの総称である。任意時間アルゴリズムは３つの性質からなる次のａｎｙｔｉｍｅ性を満たす。
【００２４】
・プランの評価：プランの質を明確に評価できる。
【００２５】
・プランの単調性：プランの質が, 時間の経過に対
して単調に増加する。
【００２６】
・割り込み可能性：任意のタイミングで有効なプラ
ンを返す。
【００２７】
まず、ａｎｙｔｉｍｅ性のあるプランニング方法でＳsubgoalまでのプラン及び初期アクション値を求める。そして、プランとアクション値を共有メモリ装置２ に渡す。
【００２８】
エグゼキューター１２からの想定していないイベントや共有メモリ装置２ からのプラン干渉の通知がない限り、プランナー１１は、未展開ノード（Ｏｐｅｎ  Ｎｏｄｅｓ）中の各状態から目標状態Ｓsubgoalまでの推定コストＥ_ＣＯＳＴ(s,subgoal)(s∈Ｏｐｅｎ  Ｎｏｄｅｓ）の再計算を行う。ここでも、ａｎｙｔｉｍｅ性のある計算を行い制約時間内でより正確な推定コストを求める。この再計算された推定コストを用いてアクション値の再計算を行い共有メモリ装置２上のその値を更新する。共有メモリ装置２ でのプラン協調はこのアクション値を用いて行われるため、この更新作業の進展に応じて協調がより合理的に行われるようになる。
【００２９】
以上のように、本実施の形態におけるマルチ・エージェントシステムは、各パーソナル・エージェント１がプランとそのアクション値を繰り返し改善し、その結果を間接的に共有することでプラン生成と協調の両方を時間制約下で実行可能なものとなっている。
【００３０】
以下に、パーソナル・エージェント１における各構成要素について詳細に説明する。
【００３１】
上記プランナー１１は、図２に示すように、環境情報問合せ部１１１、プランニング及びアクション値算出部１１２、アクション実行判定部１１３、推定コスト算出部１１４を含んでいる。
【００３２】
上記環境情報問合せ部１１１は、エグゼキューター１２に対して環境情報取得要求の指示を与える。
【００３３】
上記プランニング及びアクション値算出部１１２は、上記環境情報問合せ部１１１による問合せによってエグゼキューター１２から送られた環境情報から、本パーソナル・エージェント１が実行するべきタスクのプランを生成する一方、生成したプランを構成する各アクションに設定されるアクション値を算出する。ここでのプラン生成及びアクション値の算出についての詳細は後述する。
【００３４】
上記プランニング及びアクション値算出部１１２は、上記の共有メモリ装置２に生成したプラン及び算出したアクション値を渡し、上記エグゼキューター１２にはプランを渡す。
【００３５】
そして、プランニング及びアクション値算出部１１２は、生成したプランをアクション実行判定部１１３にも渡す。
【００３６】
上記アクション実行判定部１１３は、取得したプランと共有メモリ装置２からの干渉結果とに基づいて、該プランを構成しているアクションが実行可能か否かを判定し、判定結果を推定コスト算出部１１４に渡す。
【００３７】
上記推定コスト算出部１１４は、取得したアクション実行の判定結果から目標状態まで遷移する場合の推定コストを算出し、算出した推定コストをプランニング及びアクション値算出部１１２に渡す。
【００３８】
上記エグゼキューター１２は、図３に示すように、環境情報取得部１２１、アクション実行判定部１２２、アクション実行部１２３、状態判定部１２４を含んでいる。
【００３９】
上記環境情報取得部１２１は、プランナー１１からの環境情報取得の要求を受け付けて、環境から環境情報を取得し、取得した環境情報を上記プランナー１１に渡すと共に、アクション実行判定部１２２に渡す。
【００４０】
上記アクション実行判定部１２２は、取得した環境情報およびプランナー１１からのプランとからアクションが実行可能か否かを判定し、判定結果をアクション実行部１２３に渡す。なお、実行不可の場合には、プランナー１１にプラン再生成の要求を出す。
【００４１】
上記アクション実行部１２３は、取得した判定結果からプランを構成するアクションの実行が可能であれば、環境に対してアクションの実行を行う。
【００４２】
上記状態判定部１２４は、上記アクション実行部１２３によって環境に対して行われたアクションの結果を受け取り、現状態が目標状態であるか否かを判定する。
【００４３】
上記共有メモリ装置２は、各パーソナル・エージェント１から非同期であがってくるプランの干渉の確認、干渉回避策の決定、プラン調整結果のパーソナル・エージェント１への通知を行い、図４に示すように、プラン及びアクション値記憶部２０１、干渉アクション判定部２０２、プラン変更判定部２０３、干渉アクションリスト２０４を含んでいる。
【００４４】
上記プラン及びアクション値記憶部２０１は、パーソナル・エージェント１から送られるプラン及びアクション値をパーソナル・エージェント１と対応付けて格納するところである。
【００４５】
上記干渉アクション判定部２０２は、プラン及びアクション値記憶部２０１に格納されたプラン内の干渉するアクションの有無を判定し、干渉するアクションがある場合に、当該干渉アクションが消去すべきアクションであれば、上記干渉アクションリスト２０４にリストアップする。
【００４６】
上記プラン変更判定部２０３は、上記干渉アクション判定部２０２において干渉するアクションがないと判定されたときに、他のパーソナル・エージェント１にプランの変更が行われたか否かを判定し、変更が行われていれば、上記干渉アクションリスト２０４をもとに他のパーソナル・エージェント１に通知する。
【００４７】
ここで、上記共有メモリ装置２において、プランを構成する各アクションは、前提条件と効果を持つ。その関係により次の二つの場合にプランの干渉が起こる。
【００４８】
（１）一方のプラン中のアクションが他方のプラン中のアクションの効果を否定する場合
（２）一方のプラン中のアクションが他方のプラン中のアクションの前提条件を否定する場合
共有メモリ装置２は、各パーソナル・エージェント１から受け取ったプラン中にこのような関係のアクションが存在していないかを常に確認する。
【００４９】
干渉があった場合、共有メモリ装置２はそのアクションのアクション値に基づきどちらのアクションを優先すべきかを判断する。この時に、プランナー１１によるアクション値の更新が進んでいればいるほど合理的な判断が可能となる。
【００５０】
上記共有メモリ装置２は、実行すべきではないと判断されたアクションを含むプランを渡してきたプランナー１１に対しては干渉及び干渉箇所を通知する。
【００５１】
上記の通知を受けたプランナー１１は、干渉アクションではなく代替案の中から次に高いアクション値を持つアクションをプラン及びアクション値記憶部２０１から選択し、そこから目標状態までの再プランニングを行う。各プランナー１１は制約時間内で最善の代替案を準備できているため、その影響は最小限に留まる。
【００５２】
上記アクション値について図５（ａ）（ｂ）を参照しながら以下に説明する。
【００５３】
上記パーソナル・エージェント１におけるプランナー１１は、状態をノードとして、またその状態から実行可能なアクションをリンクとして作成したグラフを状態空間グラフとし、この状態空間グラフ上で初期状態から目標状態までの経路を構成するリンクの系列（プラン）を求める。また、状態ｓから状態ｓ0への遷移を生じさせるアクションのコストはＣＯＳＴ(ｓ,ｓ0)で表され、初期状態から目標状態までのある経路が存在し、その経路上のリンクのコストの総和より小さいコストの経路が存在しなければ、その経路は最適であると言う。
【００５４】
アクション値は、この状態空間グラフ上のアクションの重要性に相当し、その値はそのアクションを選択し目標状態まで遷移する場合の推定コストと代替アクションを選択し目標状態まで遷移する場合の推定コストとを比較し定義する。図５（ａ）を用いてその方法について説明する。
【００５５】
この図５（ａ）において、Ｓ(k)iは現状態、ａ(j)i+1は状態Ｓ(k)iから状態Ｓ(j)i+1への遷移を起こすアクション、Ｓ(j)i+1は次状態、Ｓsubgoalは最終目標状態Ｓgoalまでの経路上に設定された中間目標状態、Ｅ_ＣＯＳＴ（Ｓ(j)i+1,subgoal）は次状態から中間目標状態までの推定コストを表す。
【００５６】
ａ(j)i,i+1のアクション値は次状態の総状態数をｎとした場合、図５（ｂ）に示す式で定義する。
【００５７】
次状態が一つしかない場合（ｎ＝１）のアクション値は１とし、その他の場合（ｎ＞１）では、アクションの中間目標状態までの推定コスト（Ｔｏｔａｌ  Ｃｏｓｔ）が小さいアクションほどより大きなアクション値をとるように定義する。具体的には、全アクションのＴｏｔａｌ  Ｃｏｓｔの和からそのアクションのＴｏｔａｌ  Ｃｏｓｔを除いた値を、全アクションのＴｏｔａｌ  Ｃｏｓｔの総和で割って定義する。なお、分母のｎ-１の項は、アクション値を０から１の範囲内の数値とするための項である。
【００５８】
このようにアクション値を定義することで、プランの協調時にどちらのアクションを実行すべきかという判断基準を得ることができる。すなわち、アクション値が１のアクションは代替案が存在しないためプラン実行に必須のアクション、高アクション値のアクションは代替案が非効率的であるため競合する他のアクションよりも優先すべきアクション、低アクション値のアクションは代替案との差が小さいため競合する他のアクションより優先する必要のないアクションといった判断が可能となる。
【００５９】
次に、上記構成のマルチ・エージェントシステムにおける各処理について以下に説明する。
【００６０】
はじめに、パーソナル・エージェント１による処理の流れについて図６のフローチャートを参照しながら以下に説明する。
【００６１】
まず、プランナー１１は、エグゼキューター１２に環境情報を問い合わせ（ステップＳ１）、エグゼキューター１２から環境情報を受け取る（ステップＳ２）。
【００６２】
次いで、プランナー１１は、受け取った環境情報に基づいて実行するタスクのプランニング及びアクション値の算出を行う（ステップＳ３）。ここの詳細は、後述する図７に示すフローチャートを参照しながら行う。
【００６３】
続いて、生成したプランを共有メモリ装置２にコピーする（ステップＳ４）。ここでは、プランナー１１が、生成したプランを共有メモリ装置２に転送するようになっている。
【００６４】
転送先の共有メモリ装置２では、後述する処理によりプランを構成するアクションの干渉の有無を知らせる干渉結果をプランナー１１に対して送出するようになっている。
【００６５】
つまり、プランナー１１は、共有メモリ装置２からの干渉結果を受け取り（ステップＳ５）、プランの先頭のアクションが実行できるか否かを判定する（ステップＳ６）。ここで、プランの先頭のアクションが実行できないと判定されれば、再度、環境情報を取得して、プランニングを行う必要があるので、ステップＳ１に移行する。
【００６６】
一方、ステップＳ６において、先頭のアクションが実行可能であると判定されれば、そのプランをエグゼキューター１２に渡し、プランナー１１と共に並列動作を開始させる（ステップＳ７）。
【００６７】
プランナー１１側では、エグゼキューター１２に対して再度環境情報を問い合わせ（ステップＳ８）、エグゼキューター１２から再度環境情報を受け取る（ステップＳ９）。
【００６８】
次に、プランナー１１内のプランニング及びアクション値算出部１１２において、プランニングを行う際に、Ｏｐｅｎ  Ｎｏｄｅｓから遷移元状態でのアクション実行が既に完了している状態を取り除く（ステップＳ１０）。
【００６９】
そして、プランニング及びアクション値算出部１１２は、Ｏｐｅｎ  Ｎｏｄｅｓの各状態から目標状態までの推定コストを再計算する（ステップＳ１１）。このとき、プランニング及びアクション値算出部１１２では、再計算した推定コストから新たなアクション値を算出する。
【００７０】
続いて、その算出した新たなアクション値を共有メモリ装置２にコピーする（ステップＳ１２）。ここでは、プランナー１１が、生成したプランを共有メモリ装置２に転送するようになっている。
【００７１】
転送先の共有メモリ装置２では、後述する処理によりプランを構成するアクションの干渉の有無を知らせる干渉結果をプランナー１１に対して送出するようになっている。
【００７２】
つまり、プランナー１１は、共有メモリ装置２からの干渉結果を受け取り（ステップＳ１３）、干渉が存在しているか否かを判定する（ステップＳ１４）。ここで、干渉が存在している判定されれば、再度、環境情報を取得して、プランニングを行う必要があるので、ステップＳ１に移行する。
【００７３】
一方、ステップＳ１４において、干渉が無いと判定されれば、ステップＳ８に移行して、エグゼキューター１２に対して環境情報を問い合わせる。
【００７４】
一方、エグゼキューター１２側では、ステップＳ７によって、プランナー１１から受け取ったプランをキューに追加する（ステップＳ１５）。なお、このキューの長さは、プランナー１１が生成したプランに含まれる未実行のアクションの数を示す。
【００７５】
次に、上記キュー長が０よりも大きいか否かを判定する（ステップＳ１６）。ここで、キュー長が０であると判定されれば、プランを構成するアクションに実行可能なアクションが一つも存在しないことを意味するので、再度プランを構築するために、ステップＳ１に移行する。
【００７６】
一方、ステップＳ１６において、キュー長が０よりも大きければ、該キューからアクションを一つ取り出し（ステップＳ１７）、環境情報を取得する（ステップＳ１８）。
【００７７】
次いで、ステップＳ１７において取り出したアクションが、ステップＳ１８において取得した環境情報から実行可能か否かを判定する（ステップＳ１９）。ここで、アクションが実行可能でないと判定されれば、実行可能なアクションを含むプランを再構築するために、ステップＳ１に移行する。
【００７８】
一方、ステップＳ１９において、アクションが実行可能であると判定されれば、そのアクションを実行し（ステップＳ２０）、実環境からアクションの効果を受け取る（ステップＳ２１）。
【００７９】
そして、受け取ったアクションの効果から、現状態が目標状態であるか否かを判定する（ステップＳ２２）。ここで、現状態が目標状態であれば、処理を終了し、現状態が目標状態でなければ、目標状態にするために、ステップＳ１６に移行する。ここで、実行したアクションの効果によって、現状態が目標状態でないと判定されているので、アクションの実行を継続する。よって、このアクションをキューから消去して、残りのアクションの中から一つアクションを取り出して同様の処理を行う。そして、ステップＳ１６において、キュー長が０、すなわちアクションの数が０になれば、プランを再構築する必要があるので、ステップＳ１に移行する。
【００８０】
続いて、プランナー１１のプランニング及びアクション値算出部１１２で行われるプランニングおよびアクション値の計算処理の流れを図７に示すフローチャートを参照しながら以下に説明する。
【００８１】
まず、状態Ｓを現在の状態で初期化、すなわち集合Ｏｐｅｎ  Ｎｏｄｅｓを空集合にする（ステップＳ３１）。
【００８２】
次に、状態Ｓが目標状態であるか否かを判定する（ステップＳ３２）。ここで、状態Ｓが目標状態でないと判定されれば、目標状態にするために、状態Ｓの全ての隣接状態Ｓｉについてｆ（Ｓ，Ｓｉ）について、ｆ（Ｓ，Ｓｉ）＝Ｃ（Ｓ，Ｓｉ）＋ｈ（Ｓｉ）を計算する（ステップＳ３３）。ただし、Ｃ（Ｓ，Ｓｉ）はＳからＳｉのコスト、ｈ（Ｓｉ）はヒューリスティック関数を示す。
【００８３】
そして、状態Ｓで実行できる全てのアクションについてそのアクション値を計算し、アクション値を設定する（ステップＳ３４）。
【００８４】
続いて、ｆ（Ｓ，Ｓt）＝ｍｉｎi ｆ（Ｓ，Ｓｉ）となる状態Ｓtに移動する（ステップＳ３５）。この場合、最小となる状態が複数の場合ランダムに選択する。
【００８５】
そして、ｈ（Ｓt）をｆ（Ｓ，Ｓｉ）の二番目に小さい値に更新し（ステップＳ３６）、再度、状態Ｓが目標状態であるか否かを判定する（ステップＳ３２）。
【００８６】
ステップＳ３２において、状態Ｓが目標状態であると判定されれば、経路上の各状態で選択されなかったアクションの遷移状態をＯｐｅｎ  Ｎｏｄｅｓに設定し（ステップＳ３７）、処理を終了する。
【００８７】
ここで、求めたプラン及びアクション値は、プランナー１１から共有メモリ装置２に転送される。
【００８８】
次に、共有メモリ装置２における処理の流れを図８に示すフローチャートを参照しながら以下に説明する。
【００８９】
まず、プランナー１１から受け取ったプランをプランニング及びアクション値算出部１１２に格納する（ステップＳ４１）。
【００９０】
次に、プランニング及びアクション値算出部１１２内に、干渉するアクションがあるか否かを判定する（ステップＳ４２）。ここで、干渉するアクションがあると判定されれば、プランニング及びアクション値算出部１１２から干渉するアクションのグループを取得する（ステップＳ４３）。
【００９１】
そして、取得したグループ内で最大のアクション値を持つアクション以外をプランニング及びアクション値算出部１１２から消去する（ステップＳ４４）。
【００９２】
さらに、消去したアクションを干渉アクションリスト２０４に追加し（ステップＳ４５）、再び、プランニング及びアクション値算出部１１２内に、干渉するアクションがあるか否かを判定する（ステップＳ４２）。
【００９３】
ステップＳ４２において、干渉するアクションが無ければ、他のパーソナル・エージェント１においてプラン変更が発生したか否かを判定する（ステップＳ４６）。ここで、プラン変更が発生していると判定すれば、干渉アクションリスト２０４をもとに他のパーソナル・エージェント１にプラン変更を通知し（ステップＳ４７）、ステップＳ４８において、干渉結果をプランナー１１へ送信し、処理を終了する。
【００９４】
一方、ステップＳ４６において、プラン変更が発生していないと判定すれば、ステップＳ４８において、干渉結果をプランナー１１へ送信し、処理を終了する。
【００９５】
以下では、本発明のマルチ・エージェントシステムを、実環境におけるリスクを回避するためのリスク回避インタラクションシステムに適用した例について説明する。
【００９６】
本シミュレータは、図９に示すように、人々(People)、目的地(Goal)、リスク(Risk)、家具(Table 等)、壁(Wall) から構成される。
【００９７】
まず、各人に目的地とリスク回避能力を設定する。
【００９８】
人々は、通路（家具のない部分）を通り最短経路で目的地への移動を行う。
【００９９】
人々は、経路上のリスクを完全には知覚できないため、リスクのあるグリッドに入ることがある。この時、リスクの大きさが各人のリスク回避能力よりも大きければ事故が発生する。
【０１００】
環境は、すべてのリスクや人々の場所を知覚可能であり、また人々が通過することのできない壁を任意のグリッド間に生成/撤去し人々の移動経路を制御することも可能である。
【０１０１】
本シミュレータによれば、多くの人々を事故リスクから回避させ、可能な限り少ない移動コストで目的地まで誘導するようなインタラクションを実施できることが分かる。
【０１０２】
続いて、図１０に示すように、二人の人（Ｐ１,Ｐ２）が目的地(それぞれＧ１,Ｇ２） に向かい移動するシナリオを用いて、（１）パーソナル・エージェントの動作プロセス(ステップ１，２)、（２）協調プロセス(ステップ３〜５) について説明する。
【０１０３】
（１）パーソナル・エージェントの動作プロセス
Ｐ１がＧ１に向け動作を開始すると、専属のパーソナル・エージェントが生成される(ステップ１)。このパーソナル・エージェント内のプランナー が四角形ＡＢＣＤの辺ＤＣに沿う通路の入り口をサブゴールとし、そこまでＰ１が移動できるようにサブプランを生成する。なお、この時のプランは隣接するグリッドに人が移動できるように移動先グリッドを確保するアクションから成る。
【０１０４】
次に、プランナーは、生成プランを共有メモリに渡す。他にパーソナル・エージェントがおらずプラン干渉が起きないため、そのプランはそのままエグゼキューターに渡る。プランを受けたエグゼキューターは、一つずつアクションを実行し、平行してプランナーは、アクション値の更新を行う(ステップ２)。
【０１０５】
（２）パーソナル・エージェントの協調プロセス
Ｐ１がサブゴールに到着後、Ｐ１のパーソナル・エージェント内のプランナーはＧ１までＰ１を誘導するためのプランを生成する。そのプランを共有メモリ上に置いたとき、既にＰ２のプランナーが同じ通路を通るプランを置いていたためプラン干渉が起こる(ステップ３) 。
【０１０６】
具体的には、通路上の同じグリッドを確保しようとするＰ１, Ｐ２のアクション（それぞれａ１,ｂ１）が干渉する。代替アクションａ２を実行してＧ１まで(辺ＡＢ経由で) 移動するときのコストとａ１を実行してＧ１まで(辺ＤＣ経由で) 移動するときのコストの差が大きいのに対してｂ１はｂ２とのその差が小さい。そのためａ１とｂ１のアクション値の比較を行うと、ａ１の方が大きくなりａ１の実行を優先する方が合理的であると判断される。共有メモリからｂ１を実行すべきではないと干渉通知を受けたＰ２のパーソナル・エージェント内のプランナーは生成済みのプランを破棄し、情報を更新して現在位置からＧ２にＰ２を誘導するための再プランニングを行う。
【０１０７】
なお、ここでは、通路に侵入するであろうＰ２の行動を制止するため壁をＰ２の前に生成するアクションがプランの先頭に組み込まれ、エグゼキューターはそのプランに従い壁を生成する(ステップ４)。
【０１０８】
以上のプロセスを経てＰ１は当初のプラン通りにａ１を実行し、Ｐ２は通路への侵入をやめ、辺ＡＢに沿う通路を経てＧ２へ向かう(ステップ５)。なお、各アクションは時間情報を持っているため、Ｐ１が角Ｃに着くまでには壁は撤収されており問題はない。
【０１０９】
本発明によれば、実環境で複数のタスクを実行するシステムに必要となる二つの性質の両立が可能となる。また、本手法のアーキテクチャは高い汎用性をもつため、今後幅広い分野への適用が期待できる。
【０１１０】
本発明は上述した実施形態に限定されるものではなく、請求項に示した範囲で種々の変更が可能である。すなわち、請求項に示した範囲で適宜変更した技術的手段を組み合わせて得られる実施形態についても本発明の技術的範囲に含まれる。
【０１１１】
最後に、パーソナル・エージェント１の各ブロック、特にプランナー１１およびエグゼキューター１２は、ハードウェアロジックによって構成してもよいし、次のようにＣＰＵを用いてソフトウェアによって実現してもよい。
【０１１２】
すなわち、パーソナル・エージェント１は、各機能を実現する制御プログラムの命令を実行するＣＰＵ（central processing unit）、上記プログラムを格納したＲＯＭ（read only memory）、上記プログラムを展開するＲＡＭ（random access memory）、上記プログラムおよび各種データを格納するメモリ等の記憶装置（記録媒体）などを備えている。そして、本発明の目的は、上述した機能を実現するソフトウェアであるパーソナル・エージェント１の制御プログラムのプログラムコード（実行形式プログラム、中間コードプログラム、ソースプログラム）をコンピュータで読み取り可能に記録した記録媒体を、上記パーソナル・エージェント１に供給し、そのコンピュータ（またはＣＰＵやＭＰＵ）が記録媒体に記録されているプログラムコードを読み出し実行することによっても、達成可能である。
【０１１３】
上記記録媒体としては、例えば、磁気テープやカセットテープ等のテープ系、フロッピー（登録商標）ディスク／ハードディスク等の磁気ディスクやＣＤ−ＲＯＭ／ＭＯ／ＭＤ／ＤＶＤ／ＣＤ−Ｒ等の光ディスクを含むディスク系、ＩＣカード（メモリカードを含む）／光カード等のカード系、あるいはマスクＲＯＭ／ＥＰＲＯＭ／ＥＥＰＲＯＭ／フラッシュＲＯＭ等の半導体メモリ系などを用いることができる。
【０１１４】
また、パーソナル・エージェント１を通信ネットワークと接続可能に構成し、上記プログラムコードを通信ネットワークを介して供給してもよい。この通信ネットワークとしては、特に限定されず、例えば、インターネット、イントラネット、エキストラネット、ＬＡＮ、ＩＳＤＮ、ＶＡＮ、ＣＡＴＶ通信網、仮想専用網（virtual private network）、電話回線網、移動体通信網、衛星通信網等が利用可能である。また、通信ネットワークを構成する伝送媒体としては、特に限定されず、例えば、ＩＥＥＥ１３９４、ＵＳＢ、電力線搬送、ケーブルＴＶ回線、電話線、ＡＤＳＬ回線等の有線でも、ＩｒＤＡやリモコンのような赤外線、Ｂｌｕｅｔｏｏｔｈ（登録商標）、８０２．１１無線、ＨＤＲ、携帯電話網、衛星回線、地上波デジタル網等の無線でも利用可能である。なお、本発明は、上記プログラムコードが電子的な伝送で具現化された、搬送波に埋め込まれたコンピュータデータ信号の形態でも実現され得る。
【産業上の利用可能性】
【０１１５】
本発明は、実環境で複数のタスクを実行する多くのシステム、例えば家庭用万能ロボットやユビキタスホームシステムなどで適用できる。家庭用万能ロボットは、部屋の掃除や不審者の警戒、自身のエネルギー補充など様々なタスクを実行しなければならない。本発明により非同期で発生するこれらのタスクを合理的に実行可能になる。また、家庭内のセンサネットが我々の行動をモニターし、生活支援・リスク回避をインタラクションデバイスによって実行するようなユビキタスホームシステムでも、非同期に起こる複数人の行動に対し、より安心・安全・快適なインタラクションが可能となる。この場合本手法のアーキテクチャの高い拡張性を用いて、個人の行動を学習しより的確なプランニングを行うエージェントを導入することも考えられる。
【図面の簡単な説明】
【０１１６】
【図１】本発明の実施形態を示すものであり、マルチ・エージェントシステムの概略構成を示すブロック図である。
【図２】図１に示すマルチ・エージェントシステムを構成するパーソナルエージェントのプランナーの概略構成を示すブロック図である。
【図３】図１に示すマルチ・エージェントシステムを構成するパーソナルエージェントのエグゼキューターの概略構成を示すブロック図である。
【図４】図１に示すマルチ・エージェントシステムを構成する共有メモリの概略構成を示すブロック図である。
【図５】（ａ）はアクション値を求めるための状態遷移図であり、（ｂ）は（ａ）のアクション値の定義を示す図である。
【図６】図１に示すマルチ・エージェントシステムを構成するパーソナルエージェントによる処理の流れを示すフローチャートである。
【図７】図６に示すフローチャートにおけるプランニング及びアクション値算出の処理の流れを示すフローチャートである。
【図８】図１に示すマルチ・エージェントシステムを構成する共有メモリによる処理の流れを示すフローチャートである。
【図９】本発明のマルチ・エージェントシステムをリスク回避インタラクションシミュレータに適応したときのシミュレータの概略図である。
【図１０】パーソナル・エージェントの動作プロセスを説明する図である。
【符号の説明】
【０１１７】
１  パーソナル・エージェント
２  共有メモリ
１１  プランナー
１２  エグゼキューター
１１２  アクション値算出部
１１３  アクション実行判定部
１１４  推定コスト算出部
１２１  環境情報取得部
１２２  アクション実行判定部
１２３  アクション実行部
１２４  状態判定部
２０１  アクション値記憶部
２０２  干渉アクション判定部
２０３  プラン変更判定部
２０４  干渉アクションリスト
【図１】
2009134652.tif 000003
【図２】
2009134652.tif 000004
【図３】
2009134652.tif 000005
【図４】
2009134652.tif 000006
【図５】
2009134652.tif 000007
【図６】
2009134652.tif 000008
【図７】
2009134652.tif 000009
【図８】
2009134652.tif 000010
【図９】
2009134652.tif 000011
【図１０】
2009134652.tif 000012