(57)【要約】【課題】複数のエージェントが、各々のプランを階層的に生成する際に発生するバックトラックが避けられるなど、より容易に競合解消を行いながらプランが作成できるようにする。【解決手段】競合パターン照合部１０３は、発見された競合する部分に一致（近似）する競合の状況より構成された競合パターンを競合情報記憶部１０７より検索（照合）する。また、競合コスト予想部１０４は、まず、予め設定されている効用関数Ｕの値を求める。また、競合コスト予想部１０４は、競合解消のためにプランを追加するための予想追加コストを算出し、競合情報記憶部１０７より発見された（取り出された）競合パターンに対応づけられているコストとの和をとる。これらの後、競合コスト予想部１０４は、算出した効関数Ｕの値より、上記コストの和を減じて効用値Ｕ’とする。【選択図】  図１
2007026343.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークで接続された複数のエージェントにより生成可能な複数のプランの中から、予め規定されている効用関数の値を指標として階層毎に１つのプラン選択することで前記エージェントの行動を規定するための実行プランを階層的に構築する階層型プラン構築装置において、
前記エージェントが生成した実行プランの実行により発生した競合の状況に、この競合の解消に要するコストが対応づけられた競合パターンを記憶した競合情報記憶部と、
特定のエージェントから通知された所定の階層のプランと、すでに通知されている他のエージェントから通知された所定の階層のプランとを比較して競合の可能性のある競合可能性部分を発見する競合発見手段と、
この競合発見手段が発見した競合可能性部分に対応する競合パターンを前記競合情報記憶部より取り出す競合パターン照合手段と、
前記競合可能性部分による競合の可能性を解消するためのプランの追加に必要とされる予想コストと、前記競合パターン照合手段により取り出された競合パターンに対応づけられたコストとの和を、前記効用関数の値より減じて効用値を算出する競合コスト予想手段と、
この競合コスト予想手段が算出した効用値を前記特定のエージェントに通知する効用値通知手段と
を少なくとも備えることを特徴とする階層型プラン構築装置。
【請求項２】
請求項１記載の階層型プラン構築装置において、
前記エージェントは、通知された前記効用値を指標として所定の階層のプランの中より１つを選択するプラン決定部を備え、このプラン決定部が選択したプランを元に前記実行プランが生成される
ことを特徴とする階層型プラン構築装置。
【請求項３】
ネットワークで接続された複数のエージェントにより生成可能な複数のプランの中から、予め規定されている効用関数の値を指標として階層毎に１つのプラン選択することで前記エージェントの行動を規定するための実行プランを階層的に構築する階層型プラン構築方法において、
前記エージェントが生成した実行プランの実行により発生した競合の状況に、この競合の解消に要するコストが対応づけられた競合パターンを競合情報記憶部に記憶し、
特定のエージェントから通知された所定の階層のプランと、すでに通知されている他のエージェントから通知された所定の階層のプランとを比較して競合の可能性のある競合可能性部分を発見し、
発見した競合の可能性のある競合可能性部分に対応する競合パターンを前記競合情報記憶部より取り出し、
前記競合可能性部分による競合の可能性を解消するためのプランの追加に必要とされる予想コストと、取り出された前記競合パターンに対応づけられたコストとの和を、前記効用関数の値より減じて効用値を算出し、
算出した前記効用値を前記特定のエージェントに通知する
ことを特徴とする階層型プラン構築方法。
【請求項４】
請求項３記載の階層型プラン構築方法において、
前記特定のエージェントは、通知された前記効用値を指標として前記所定の階層のプランを選択して前記実行プランを生成する
ことを特徴とする階層型プラン構築方法。
【請求項５】
ネットワークで接続された複数のエージェントにより生成可能な複数のプランの中から、予め規定されている効用関数の値を指標として階層毎に１つのプラン選択することで前記エージェントの行動を規定するための実行プランを階層的に構築する階層型プラン構築をコンピュータに実行させるプログラムにおいて、
コンピュータに
前記エージェントが生成した実行プランの実行により発生した競合の状況に、この競合の解消に要するコストが対応づけられた競合パターンを競合情報記憶部に記憶させるステップと、
特定のエージェントから通知された所定の階層のプランと、すでに通知されている他のエージェントから通知された所定の階層のプランとを比較して競合の可能性のある競合可能性部分を発見するステップと、
発見した競合の可能性のある競合可能性部分に対応する競合パターンを前記競合情報記憶部より取り出すステップと、
前記競合可能性部分による競合の可能性を解消するためのプランの追加に必要とされる予想コストと、取り出された前記競合パターンに対応づけられたコストとの和を、前記効用関数の値より減じて効用値を算出すステップと、
算出した前記効用値を前記特定のエージェントに通知するステップと
を実行させることを特徴とするプログラム。
【請求項６】
請求項５記載のプログラムにおいて、
前記通知された前記効用値は、前記特定のエージェントにおいて、前記所定の階層のプランを選択して前記実行プランを生成するための指標として用いられるものである
ことを特徴とするプログラム。
【請求項７】
請求項５又は６に記載されたプログラムが記憶されたことを特徴とする記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークの上に分散する情報の処理などを行うエージェントが生成するプランを構築するための階層型プラン構築装置、階層型プラン構築方法、及びプログラム並びに記憶媒体に関するものである。
【背景技術】
【０００２】
近年のインターネット(特にＷＷＷ−ＨＴＭＬ)の発展、普及により、インターネット上で動作するエージェントが複数設置され、配置された複数のエージェントが協調あるいは相互に調整しながらタスクを実行するマルチエージェントシステムが提案されている。さらに、ユビキタスネットワーク、ユビキタスコンピューティングに関連するアプリケーションも、このシステムの例として考えられ、近年、実現化されつつある。このようなシステムでは、人間の多様な要求に応えるために、予め決められた行動やプログラム系列ではなく、行動やプログラムのプリミティブ（要素式）を用意し、人間が要求するレベルに合わせて動的にこれらを組み立て、システム側からの知的な行動や行為を発現することが要求される。
【０００３】
このような要求に応えるため、プログラムのプリミティブを組み立てるプランニングと呼ばれる処理が必要とされる。さらに、人間にとって意味ある時間内に完了させる必要があり、実時間性や効率性も同時に要求される。効率性を実現する一手法として、高速化のために予めある程度組み立てておいたプランを複数用意し(プランライブラリという)、これらの中から選択するという形でプランを生成する手法がある。しかし、このようなプランライブラリの考え方は、インターネットやユビキタスネットワークのアプリケーションでは合わないことも多い。
【０００４】
実際、ユビキタスネットワークの環境であれば、これらはさまざまな部屋、場所で実現されるため、用意すべきプランライブラリの内容が異なる。もちろん、個別に用意することも考えられるが、これには多くの人間の行動の解析と人手によるプランライブラリ作成という負荷がかかる。またこれらを統合するために、独立に用意されたエージェントが、機能拡張や改変によりライブラリの内容が意味をなさなくなることがある。このためすべてのプランライブラリを修正することが必要となる。いずれにしても、人手による多大な労力が要求される。
【０００５】
このほかに効率性を実現する手段として、階層プランニングがある。階層プランニングでは、問題領域を、例えば地図の縮尺のようにさまざまな詳細度のモデルで表現し、抽象度の高いレベルで大枠でのプランの内容を定め、以降は階層に基づいて順に具体化する。この際に、各段階での具体化の方法はいくつかあり、これらの中から適切なものを選択する。例えば、縮尺の大きな地図の上で東京から横浜までの移動経路を大体定めたとしても、具体的に移動する段階では、「どこの交差点で曲がるか」などはいくつかの選択肢がある。しかし、階層の高いものが、自然に、下位の具体的なプランに自然なスコープ（必要項目）を与えるため、プランを生成するための探索領域が劇的に減少し、効率化が実現されるようになる。また、エージェントの機能が変わっても、このエージェントに関する機能の表現のみを変えればよく、以降のプランの組み立てはエージェントが自動的に行うため実用的である。
【０００６】
ところで、上述しているプランとは、抽象的に表された行為の列(正式には半順序集合)である。プランには、達成（到達）すべきゴールがあり、このゴールへの到達を実現するためにプランが生成される。換言すれば、プランを順序にしたがって実行すれば、ゴールへ到達できるようにプランが生成される。階層的プランニングでは、抽象度の高いレベルでは、抽象度の高い行為の列であり、これらが詳細化されるにしたがって、より細かく具体的な行動に置き換わる。最も詳細なレベル(プリミティブレベル)では、装置などの一つ一つの操作に対応し、行為が発現される。各レベルにおいて、１つの行為の単位をタスクと呼ぶ。階層プランでは、上位の１つのタスクを実現するために、下位のタスクをいくつか組み立てることとなる。
【０００７】
階層プランニングにおいては、効率化を図る方法がいくつか提案されており、例えば、「ＭＡＸＱ」あるいは「ＨＥＸＱ」と呼ばれる方式がある（非特許文献１，非特許文献２参照）。また、複数のエージェントによる階層プランニングで競合発生を予測し効率化をねらった方式も提案されている（非特許文献３参照）。
【０００８】
【非特許文献１】T.G.Dietterich,"The MAXQ Method for Hierarchical Reinforcement Learning", In Proc. of lCML-98, pp.118-126, 1998.
【非特許文献２】B.Hengst, "Model Approximation for HEXQ Hierarchical Reinforcement Learning",In ECML 2004, pp.144-155, 2004.
【非特許文献３】B. J. Clement and E. H. Durfee, "Theory for coordinating concurrent hierarchical planning agents using summary information", In Proc. of AAAI-99, pp. 495-502, 1999.
【発明の開示】
【発明が解決しようとする課題】
【０００９】
ところが、従来では、主に、階層プランニングは、単一のエージェントの場合に適用されてきたため、階層プランニングを、複数のプログラム(エージェント)が動作する可能性のあるマルチエージェントシステムに利用するには、いくつかの問題がある。まず、非特許文献１及び非特許文献２の方式は、各階層でそれ以下の詳細なプランの生成を速めるものであるが、複数のエージェントが関連するプランは対象外である。
【００１０】
また、マルチエージェントシステムでは、複数のエージェントが同時にプランに基づいて行動を発現する可能性があるので、同じ場所で作業する，同じセンサーを使う，同じ機械を使うなどの競合が発生する可能性がある。しかしながら、実際に、競合の発生が確定できるのは、プランが十分に詳細化・具体化されてからである。また、ある行動を具体化する方法は複数あり、抽象的なレベルでは、資源の使用の可能性は指摘できるが、どの資源をどのくらいの量あるいはどれだけの時間使用するのかは、タスクの順序なども決定した最も詳細なレベルの段階で確定される。
【００１１】
従って、詳細レベルの段階到達してから、競合を発見して解消するためのプラン修正を行うこととなる。ところが、如何なる修正方法でも競合が解消ができない場合、このプランを破棄し、プランのレベルをある程度戻り、再度プラン生成を行うバックトラックを行う必要が出てくる。このバックトラックは、プランの破棄が決定されるまでのプランニング処理が無駄になるため、可能な限り避けなくてはならない。しかしながら、これまでは、このようなバックトラックを避ける手法は無く、プランニング処理が無駄になる場合が多かった。また、非特許文献３の方式では、事前に可能性のあるすべてのプランを解析しているため、事前の処理に負荷がかかる他、実際には使われる可能性のないプランまで解析されるという問題がある。また、これらの分野では、各プログラムであるエージェントが、必ずしも同一デザインのもとで生成されているわけではなく、相手のプランニングの制御までできるとは限らないという問題もある。
【００１２】
本発明は、以上のような問題点を解消するためになされたものであり、複数のエージェントが、各々のプランを階層的に生成する際に発生するバックトラックが避けられるなど、より容易に競合解消を行いながらプランが作成できるようにすることを目的とする。
【課題を解決するための手段】
【００１３】
本発明に係る階層型プラン構築装置は、ネットワークで接続された複数のエージェントにより生成可能な複数のプランの中から、予め規定されている効用関数の値を指標として階層毎に１つのプラン選択することでエージェントの行動を規定するための実行プランを階層的に構築する階層型プラン構築装置において、エージェントが生成した実行プランの実行により発生した競合の状況に、この競合の解消に要するコストが対応づけられた競合パターンが記憶された競合情報記憶部と、特定のエージェントから通知された所定の階層のプランと、すでに通知されている他のエージェントから通知された所定の階層のプランとを比較して競合の可能性のある競合可能性部分を発見する競合発見手段と、この競合発見手段が発見した競合可能性部分に対応する競合パターンを競合情報記憶部より取り出す競合パターン照合手段と、競合可能性部分による競合の可能性を解消するためのプランの追加に必要とされる予想コストと、競合パターン照合手段により取り出された競合パターンに対応づけられたコストとの和を、効用関数の値より減じて効用値を算出する競合コスト予想手段と、この競合コスト予想手段が算出した効用値を特定のエージェントに通知する効用値通知手段とを少なくとも備えるようにしたものである。
【００１４】
上記階層型プラン構築装置において、エージェントは、通知された効用値を指標として所定の階層のプランの中より１つを選択するプラン決定部を備え、このプラン決定部が選択したプランを元に実行プランが生成される。従って、エージェントにおいては、記憶されている競合パターンに対応する競合の可能性がある競合可能性部分を含むプランが生成されると、通知された効用値を新たな指標として生成可能な複数のプランの中から適切と思われるものを選択することで階層的に構築して実行プランを生成する。
【００１５】
また、本発明に係る階層型プラン構築方法は、ネットワークで接続された複数のエージェントにより生成可能な複数のプランの中から、予め規定されている効用関数の値を指標として階層毎に１つのプラン選択することでエージェントの行動を規定するための実行プランを階層的に構築する階層型プラン構築方法において、エージェントが生成した実行プランの実行により発生した競合の状況に、この競合の解消に要するコストが対応づけられた競合パターンを競合情報記憶部に記憶し、特定のエージェントから通知された所定の階層のプランと、すでに通知されている他のエージェントから通知された所定の階層のプランとを比較して競合の可能性のある競合可能性部分を発見し、発見した競合可能性部分に対応する競合パターンを競合情報記憶部より取り出し、競合可能性部分による競合の可能性を解消するためのプランの追加に必要とされる予想コストと、取り出された競合パターンに対応づけられたコストとの和を、効用関数の値より減じて効用値を算出し、算出した効用値を特定のエージェントに通知するようにしたものである。なお、特定のエージェントは、通知された効用値を指標として所定の階層のプランを選択して実行プランを生成する。
【００１６】
また、本発明に係るプログラムは、ネットワークで接続された複数のエージェントにより生成可能な複数のプランの中から、予め規定されている効用関数の値を指標として階層毎に１つのプラン選択することでエージェントの行動を規定するための実行プランを階層的に構築する階層型プラン構築をコンピュータに実行させるプログラムにおいて、コンピュータに、エージェントが生成した実行プランの実行により発生した競合の状況に、この競合の解消に要するコストが対応づけられた競合パターンを競合情報記憶部に記憶させるステップと、特定のエージェントから通知された所定の階層のプランと、すでに通知されている他のエージェントから通知された所定の階層のプランとを比較して競合の可能性のある競合可能性部分を発見するステップと、発見した競合可能性部分に対応する競合パターンを競合情報記憶部より取り出すステップと、競合可能性部分による競合の可能性を解消するためのプランの追加に必要とされる予想コストと、取り出された競合パターンに対応づけられたコストとの和を、効用関数の値より減じて効用値を算出すステップと、算出した効用値を特定のエージェントに通知するステップとを実行させるようにしたものである。なお、通知された効用値は、特定のエージェントにおいて、所定の階層のプランを選択して実行プランを生成するための指標として用いられるものである。また、このプログラムは、記憶媒体に記憶されていてもよい。
【発明の効果】
【００１７】
以上説明したように、本発明では、エージェントが生成した実行プランの実行により発生した競合の状況にこの競合の解消に要するコストが対応づけられた競合パターンが競合情報記憶部に記憶されているようにし、この競合パターンを元に効用値を算出し、算出された効用値を新たな指標として用いるようにした。この結果、本発明によれば、複数のエージェントが、各々のプランを階層的に生成する際に発生するバックトラックが避けられるなど、より容易に競合解消を行いながらプランが作成できるようになるという優れた効果が得られる。
【発明を実施するための最良の形態】
【００１８】
以下、本発明の実施の形態について図を参照して説明する。図１は、本発明の実施の形態における階層型プラン構築装置の構成例を示す構成図である。図１に示す階層型プラン構築装置は、マネージャーエージェント１００と、複数のエージェント１３０とを備える。これらは、ブルートゥース（Bluetooth：登録商標）などの無線ＬＡＮや、インターネットなどの広域通信網を含むネットワークで接続されている。マネージャーエージェント１００は、競合パターン生成部１０１，競合発見部１０２，競合コスト予想部１０４，効用値通知部１０５，通知プラン記憶部１０６，及び競合情報記憶部１０７を備える。また、各エージェント１３０は、基本プラン生成部１３１，詳細プラン選択部１３２，記憶部１３３，プラン決定部１３４，競合情報生成部１３５，及び通知部１３６を備える。
【００１９】
まず、エージェント１３０について説明する。各エージェント１３０では、新たなゴール（目標）が与えられると、与えられたゴールへ到達するためのプランを生成する。エージェント１３０において、基本プラン生成部１３１は、与えられた目標の情報を元に組み合わせ可能な行為（タスク）の範囲が規定されたプランの大枠となる基本プランを生成する。このようにして基本プランが生成されると、詳細プラン選択部１３２は、基本プラン生成部１３１により生成された基本プランの範囲内で、よく知られたプラン生成法により、１レベル（階層）詳細な複数のプランを生成し、この中より、効用関数Ｕの値により適切と予想されるプラン（１レベルプラン）を選択する。このレベルは、各エージェント１３０において適宜設定されているものである。ところで、効用関数Ｕは、生成可能な複数のプランの中から適切と思われるものを選択の指標を与えるものであり、基本プランの効率や質（精度）を表現するものであり、記憶部１３３に記憶されている。
【００２０】
１レベル詳細なプランが選択決定されると、詳細プラン選択部１３２は、上記基本プランの範囲内で、上記同様のプラン生成法により、２レベル詳細な複数のプランを生成し、これらの中より、上記効用関数Ｕの値により適切とされる２レベルプラン選択する。これらを繰り返しながら、各エージェント１３０は、プランを具体化する。例えば、プランを生成する際に、プランの各要素であるタスクは、これを実行するための前提条件、実行した結果として得られる効果が論理式（あるいは同等の表現方式）で表されており、さらに、上記タスクには、使用（消費）される資源、道具が記述されている。これらの表現は、タスクに対応するレベル（階層）に相当した表現となっており、階層の高いレベルでは抽象的な資源表現になっている。
【００２１】
例えば、ビルの例であれば、抽象度が高ければ「２階フロアで作業する」ということになるが、これより詳細なレベルでは、「２階の２０３号室の窓側で作業をする」となる。また、例えば、あるビルの構造をプランとして表現する場合、抽象度の高いモデルでは、部屋単位程度の大きなブロックで表され、次のレベルでは、１メートル四方程度での配置図、詳細レベルでは、１０ｃｍ単位の細かさで設備品や機器の配置図を表すなどが考えられる。これは地図における縮尺の表現をイメージすると分かりやすい。さらにこれらの階層にあわせてタスクも階層表現され（例えば、縮尺の大きな抽象度の高い地図で、「ガソリンスタンドのある交差点で右折する」というようなタスクはない）、各々のレベルでのモデルに対応するタスクがあり、対応するタスクで各々のレベルでのタスク列、つまりプランが表現されている。なお、プランの生成法については、多くの手法が提案されており、いずれの手法を用いてもよい。
【００２２】
このような詳細化を進めて、予め設定されているスクリーニングレベル（所定の階層）とされたレベルのプランがいくつか生成されると、エージェント１３０では、通知部１３６が、生成されたスクリーニングレベルプランをマネージャーエージェント１００に通知する。スクリーニングレベルプランの通知がなされた後、エージェント１３０では、プラン決定部１３４が、マネージャーエージェント１００より通知された効用値に基づき、生成されている複数のスクリーニングレベルプランより１つを選択し、また、数レベルバックトラックして別のプランを生成し、これらいずれかのプランを元に、詳細プラン選択部１３２が詳細化を行い、最終的なプラン（実行プラン）を生成する。以上に説明したように、プランは、各エージェント１３０の行動を規定して階層的に構築されたものである。
【００２３】
また、エージェント１３０では、生成された最終的なプランを実行した結果、プランに競合が発生すると、競合の発生箇所と、競合発生箇所毎の競合解消のためのプラン変更に要したコストと、競合発生箇所毎に競合解消のために追加された行為のコスト（競合がない場合のプランとの差）を含む競合情報を、競合情報生成部１３５が生成する。競合情報生成部１３５が生成した競合情報は、通知部１３６によりマネージャーエージェント１００に通知される。なお、実際に発生した競合解消のためのプラン変更に要したコストは、競合を解消するためにエージェントにおいて追加されたプラン生成の行為のコストの追加分である。また、競合解消のために追加された行為のコストは、遅延や解の質（精度）の低下といわれているものである。
【００２４】
次に、マネージャーエージェント１００について説明する。マネージャーエージェント１００では、前述したエージェント１３０から通知された複数のスクリーニングレベルプランが、対応するエージェント１３０を識別する識別子とともに通知プラン記憶部１０６に記憶される。また、マネージャーエージェント１００では、競合パターン生成部１０１が、エージェント１３０から通知された競合情報より得られる競合の関係から競合パターンを生成し、また、競合情報に含まれている競合解消のためのプラン変更に要したコスト及び競合解消のために追加された行為のコストを、生成した競合パターンに対応づける。このようにして競合の解消に要するコストが競合の状況（関係）に対応づけられた競合パターンが、競合情報記憶部１０７に記憶される。
【００２５】
また、競合発見部１０２は、エージェント１３０より通知されたスクリーニングレベルプランと、通知プラン記憶部１０６に記憶されている他のスクリーニングレベルプランとを、比較することで、競合の可能性を発見する。競合発見部１０２は、通知されたスクリーニングレベルプランの各部分毎に、実行される順番に競合性の可能性を発見する。例えば、スクリーニングレベルプランの中で、１つしかない道具などの同時刻に分割できない資源を使用しようとしている、また、電池などの資源の有無を確認することで、競合の可能性のある部分（競合可能性部分）を発見する。なお、比較の対象となる他のスクリーニングレベルプランは、比較を行う時点ですでに実行されている、もしくは、実行が承認されて実行が予定されているプランにおけるスクリーニングレベルのものである。
【００２６】
ここで、資源についてより詳細に説明する。前述したように、エージェント（プログラムやロボット、センサーなど）が使用する資源，道具，また例えば、電力やセンサーデータの取得タイミングなどをすべて含めてエージェントが利用する資源と呼ぶ。資源にはいくつかのタイプがあり、共用できるものできないもの、分割できるものできないもの、消費されるものされないものなどのタイプ分けがある。共用に関しては、例えば、照明や空調などは（同じ温度設定であれば）同じ部屋で共用できるが、のこぎりやドライバーなどは特定のエージェントのみが使えるので同時には使用できない。分割については、例えば、電流は分割可能であるが、共用の場合と異なり、総容量がありこれを超えることはできない。消費されるものについては、電池などある程度使うと使えなくなるものが対応する。
【００２７】
次に、競合パターン照合部１０３は、発見された競合する部分（競合可能性部分）に一致（近似）する競合の状況より構成された競合パターンを競合情報記憶部１０７より検索（照合）する。また、競合コスト予想部１０４は、まず、予め設定されている効用関数Ｕの値を求める。また、競合コスト予想部１０４は、競合解消のためにプランを追加するための予想追加コストを算出し、競合情報記憶部１０７より発見された（取り出された）競合パターンに対応づけられているコストとの和をとる。これらの後、競合コスト予想部１０４は、算出した効関数Ｕの値より、上記コストの和を減じて効用値Ｕ’とする。
【００２８】
なお、競合が解消されるとプランに余分な行為が追加される場合もあるので、競合コスト予想部１０４は、競合解消のための行為が追加された場合における遅延を考慮し、プラン内の競合が発見された行為（部分）以降の部分の遅延を計算し、この値に基づいて実行予定時間を変更し、これ以降のプランにおいて競合パターンに一致する部分の発見を行い、一致する部分毎に上記効用値Ｕ’を算出する。ここで、前述した競合解消のためのコストや生成されたプランの差分の値は、統計的に計算する必要がある。例えば、平均値を利用することや、それまでのコストの値ｃ［ｎ］に対してｎ番目のコストの観測値ｏ［ｎ］をとしたときに、「ｃ［ｎ］＝（１−λ）ｃ［ｎ］＋λｏ［ｎ］（０＜λ＜１）」として計算を行えばよい。
【００２９】
ところで、一致する競合パターンがない場合、競合コスト予想部１０４は、求めた実効関数Ｕの値をこのまま効用値Ｕ’する。また、一致する競合パターンがない場合、競合パターン照合部１０３は、発見された競合の可能性のある部分（競合可能性部分）の状態を新たな競合パターンとして前述同様に、競合情報記憶部１０７に登録（記憶）する。効用値通知部１０５は、上述したように、競合コスト予想部１０４により算出された効用値Ｕ’を、競合が発見されたスクリーニングレベルプランを通知してきたエージェント１３０に通知する。
【００３０】
なお、図１に示す階層型プラン構築装置（マネージャーエージェント１００及びエージェント１３０）は、例えば、ＣＰＵと主記憶装置と外部記憶装置とネットワーク接続装置となどを備えたコンピュータ機器であり、主記憶装置に展開されたプログラムによりＣＰＵが動作することで、上述した各機能が実現される。また、各機能は、複数のコンピュータ機器に分散させるようにしてもよい。
【００３１】
ここで、マネージャーエージェント１００の動作例について図２のフローチャートを用いて説明する。まず、ステップＳ２０１で、競合コスト予想部１０４が、対象となるスクリーニングレベルプランより実効関数Ｕの値を算出する。ついで、ステップＳ２０２で、競合発見部１０２が、スクリーニングレベルプランの先頭の部分にポインタを設定する。次に、ステップＳ２０３で、競合発見部１０２は、ポインタが設定されている部分から以降を、通知プラン記憶部１０６に記憶されている他のスクリーニングレベルプランと比較し、競合の可能性のある場所を発見する。
【００３２】
競合の可能性のある場所が発見されると、ステップＳ２０４で、競合パターン照合部１０３が、発見された競合する部分（競合可能性部分）に一致（近似）する競合パターンを競合情報記憶部１０７より探し出す。ついで、一致する競合パターンが発見されると（ステップＳ２０４）、ステップＳ２０５で、競合コスト予想部１０４が、効用値Ｕ’を算出し、発見された競合の可能性のある場所（ポインタ）以降のタスクの実行予定時間を変更（移動）する。一方、一致する競合パターンが発見されない場合（ステップＳ２０４）、ステップＳ２０６で、競合パターン照合部１０３は、発見された競合の可能性のある部分の状態を新たな競合パターンとして、競合情報記憶部１０７に登録（記憶）する。
【００３３】
この後、ステップＳ２０７で、競合発見部１０２が、発見された競合の可能性のある箇所の直後の場所にポインタを移動する。上述したステップＳ２０３からステップＳ２０７を繰り返す中で、ステップＳ２０３の判断において、競合の可能性のある場所が発見されない場合、ステップＳ２０８で、得られている効用値を、競合の可能性のある箇所とともに対応するエージェント１３０に通知する。この結果、エージェント１３０では、エージェント１３０では、プラン決定部１３４が、通知された上記効用値に基づき、生成されている複数のスクリーニングレベルプランより１つを選択し、また、数レベルバックトラックして別のプランを生成し、これらいずれかのプランを元に、詳細プラン選択部１３２が詳細化を行い、最終的なプラン（実行プラン）を生成する。
【００３４】
このように、エージェント１３０では、通知された効用値を元に、競合が回避されるようにプランの一部分を修正する。例えば、エージェント１３０では、タスクの順序を入れ替える，いくつかのタスクを別のものに置き換える，資源が利用可能になるまで待つ、基本プラン自体を作り直すなどのことによりプランの一部を修正する。
【００３５】
以上に説明したように、図１に示す階層型プラン構築装置によれば、経験をベースにしており、特定の環境では使われないものは学習されず、逆に多く発生するものは、集中的に解析されるので、各々の環境に適合した形で適応することができる。また、最終的な事項プランが生成される前に競合の解消が可能となるので、バックトラックが抑制された状態でより適切なプランの作成が可能となる。また、これらのことが、各エージェントにおける多種多様なプランニングのプロセスに立ち入ることなく行える。また、各エージェントにおいては、従来より行っている抽象的なタスクの表現と一般的操作のみで、競合解消を行いながらプランが作成できる。
【００３６】
次に、競合パターンについてより詳細に説明する。競合パターンとは、他のエージェントのプランとの競合の様式をパターンとして表現したものである。例えば、図３においては、すでに許可されている他のエージェントのプラン（ａ）とプラン（ｂ）とに関連し、新しいプランのタスクｔl-1とタスクｔlが、各々プラン（ａ）のタスクｔn’とタスクｔn+1’と競合の可能性があり、また、タスクｔlとタスクｔl+1は、プラン（ｂ）のタスクｔm-1"とタスクｔm”と競合がある例が示されている。
【００３７】
上述した図３に示す競合パターンは、次の（１）式に示されるように表現される。
【００３８】
ＣＰ2（ｔl）＝（ｔl，（ｔn+1 ’，ｒl’），（ｔm+1 ”，ｒl”）・・・（１）
【００３９】
ここで、r1’及びr1”は、補助データであり、競合パターンをさらに詳細に分類する場合に利用する。例えば、競合するエージェント名，またはエージェントのタイプ（役割や能力に応じた分類）、タスクの相対時間などを必要に応じて追加する。例えば、時間を予想できるのであれば、tlの実行時の前半か後半かなどの情報が、タスクの相対時間である。これらの具体的な使用法については後述する。なお、タスクの相対時間については、非特許文献４（J.F.Allen,"Maintaining knowledge about temporal intervals", Communications of the ACM, Vol.26, No.11, pp.832-843,1983.）を参照されたい。
【００４０】
ところで、上述した競合パターンの記述では、同時に起こるタスク間の競合のみが表現されているが、競合は、以降のタスクにも依存する場合もある。このために、タスクの対象を広げて分類を可能とする。例えば、図３において、ｔl-1は競合の可能性があるが、この後のｔl，ｔl+1も競合を起こす可能性がある。この場合には、上記（１）式を拡張し、以下の（２）式により表す。
【００４１】
ＣＰ（ｔl-1）＝［（ｔl-1，（ｔn-1 ’，ｒl-1’），・・・），
（ｔl，（ｔn ’，ｒl’），・・・），
（ｔl+1，（ｔn+1 ’，ｒl+1’），・・・）］・・・（２）
【００４２】
上記（２）式は、tl-1を中心に、２タスク先まで上記の表現を羅列したものである。この場合、全部で３タスクを参照しているので、ウインドウサイズ（参照領域）が３であると言うこととする。また、これを行列表現として、各列に「同じエージェント」のプラン内のタスクが並ぶように表現できる。図３の例では以下の（３）式で示されるようになる。
【００４３】
ＣＰ（ｔl-1）＝［（ｔl-1，（ｔn’，ｒl-1’），（）），
（ｔl，（ｔn+1 ’，ｒl’），（ｔm-1 ’，ｒl’）），
（ｔl+1，（），            （ｔm”，ｒl+1”））］，・・・（３）
【００４４】
前述した説明では、ウインドウサイズは１としているが、ウインドウサイズは１以外の他の場合でも同様である。なお、上述した「同じエージェント」は、まったく同じエージェントという意味だけではなく、同じタイプのエージェントであることも含む。また、すべてのエージェントが同じタイプのエージェントで構成されている場合、適切な順序づけを行い、同じ競合パターンが複数の異なるパターンに展開されることを防ぐものとする。これらの詳細は、エージェントのシステムに依存する。
【００４５】
以下、部屋を動く複数ロボットの行動プランの生成に、上述した本発明を適用した例について説明する。まず、図４の平面図に示すような部屋を考える。この部屋のレイアウトが与えられているが、階層プランでは、地図のように最も詳細なレベル（図４（ａ））、これらをまとめた中間レベル（図４（ｂ））、さらに抽象的な上位レベル（図４（ｃ））がある。これらはまとめて、最上位でより広範囲なモデル（図４（ｄ））としてまとめられる。最も抽象的なレベルでの行為は、図４（ｄ）を利用し、例えば「１２３号室で作業をする」といったものになり、これらを順に詳細化し、拡大して示す図５の平面図に示すような、ロボットαとロボットβが、部屋を移動するというようなプラン（このプランは詳細である一方、全体の一部分でしかない）に展開される。
【００４６】
この例題では、図５の座標（Ｃ，Ｄ）の付近で、ロボットαとロボットβとの衝突が起こる可能性がある。なお、すでにロボットβのプランは決定しており、ロボットαのプランが新規に作られるものとする。以下の説明において、最も詳細なレベルの行為は、図５に示されている横が０，１，２，・・・３１，縦が０，１，２，・・・２７間での数字で表された座標を用い、（８,１３）→（９,１３）という移動のみを対象とする。
【００４７】
図５に示す階層をスクリーニングレベルとすると、可能性のある競合の発見は、ロボットαとロボットβとが、同時に同じ場所にいる（衝突の可能性がある）ことを見つけることにある。この例では、ほぼ同時刻にロボットαの行為（Ｂ，Ｃ）→（Ｂ，Ｄ）とロボットβの行為（Ｂ，Ｅ）→（Ｂ，Ｄ）が発生し、（Ｂ，Ｄ）付近で競合の可能性がある。同様に、ロボットαの行為、（Ｂ，Ｄ）→（Ｃ，Ｄ），（Ｃ，Ｄ）→（Ｄ，Ｄ）が、ロボットβの同じ行為と競合すると判断される。この場合、ウインドウサイズ１の競合パターンＣＰは、以下の（４）式で示されるものとなる。
【００４８】
ＣＰ＝｛（Ｂ，Ｃ）→（Ｂ，Ｄ），｛（Ｂ，Ｅ）→（Ｂ，Ｄ），ｒｅｌｔｉｍｅ｝｝・・・（４）
【００４９】
また、ウインドウサイズ２であれば、競合パターンＣＰは、以下の（５）式で示されるものとなる。
【００５０】
ＣＰ＝｛（Ｂ，Ｃ）→（Ｂ，Ｄ），｛（Ｂ，Ｅ）→（Ｂ，Ｄ），ｒｅｌｔｉｍｅ｝（Ｂ，Ｄ）→（Ｃ，Ｄ），｛（Ｂ，Ｄ）→（Ｃ，Ｄ）ｒｅｌｔｉｍｅ｝｝・・・（５）
【００５１】
ここで、「ｒｅｌｔｉｍｅ」は、オプション部分であり、非特許文献４に示されている相対時間を示している。例えば、上記式（４）について、２つのプランで競合の発生のあるのは、（Ｂ，Ｃ）→（Ｂ，Ｄ）を基準として、行為を実行している時間の前半のみである場合には、「ｒｅｌｔｉｍｅ」の部分には、「ｆｉｒｓｔｈａｌｆ」が入る。このほかに、後半が重なる「ｌａｓｔｈａｌ」、ほぼ同時刻に開始される「ｏｖｅｒｌａｐ」などが、「ｒｅｌｔｉｍｅ」の部分に入る。
【００５２】
以下、単純化のためにウインドウサイズは１とする。また、特徴的な場面である、座標（Ｃ，Ｄ）で起こる競合について考える。この場合の競合パターンＣＰは、以下の（６）式で示されるものとなる。
【００５３】
ＣＰ＝｛（Ｃ，Ｄ）→（Ｄ，Ｄ），｛（Ｃ，Ｄ）→（Ｄ，Ｄ），ｒｅｌｔｉｍｅ｝｝・・・（６）
【００５４】
上述した競合パターンで表現されるのものは、競合の場所，行為の種類（ここでは移動方向が重要となる），及び行為を行っている相対的時間である。すべてスクリーニングレベルでは競合の可能性が示唆されている。ここで大切なことは、第１に、「ｒｅｌｔｉｍｅ」が、「ｆｉｒｓｔｈａｌｆ」か「ｌａｓｔｈａｌｆ」であるときには競合は発生しない。なぜなら、同じ方向への移動であり、時間（時刻）がずれていれば同時刻に同じ場所を通ることはないからである。第２に、「ｒｅｌｔｉｍｅ」が「ｏｖｅｒｌａｐ」であったとしても、最も狭い部分で２コマのスペースがあるので、ロボットのサイズが１コマで済むのであれば、衝突しないルートを発見でき、結果として競合解消も容易（低コスト）で新たなプランによるコストも発生しない。仮に、ロボットのサイズが１コマ以上の大きさでも、同じ方向なので、１単位秒だけ停止し（相手が過ぎ去るのを待ってから）、続きを行えばよい。この場合には、停止するので新しいプランにコストが発生するが、大きいものとはいえない。
【００５５】
上述のことは、実際の何回かの試行（つまり経験）から判断できるので、結果的には上記の競合がスクリーニングレベルで検出されても、検出された競合を考慮せず詳細化を進めてよいことがわかる。
【００５６】
しかし、例えばロボットβの移動向きが逆である場合、上述したように簡単ではない。この場合の競合パターンＣＰは、以下の（７）式で示されるものとなる。
【００５７】
ＣＰ＝｛（Ｃ，Ｄ）→（Ｄ，Ｄ），｛（Ｃ，Ｄ）→（Ｂ，Ｄ），ｒｅｌｔｉｍｅ｝｝・・・（７）
【００５８】
この場合、「ｒｅｌｔｉｍｅ」が「ｆｒｓｔｈａｌｆ」であるすると、競合は、領域（Ｃ，Ｄ）の左側部分で起こり、十分なスペースがあるので大きな損失はない。しかし、「１ａｓｔｈａｌｆ」の場合には、ロボットαの行為の後半で発生することになり、これは領域（Ｃ，Ｄ）の右側の狭い部分で起こる。スペースが２コマ分あるので、ロボットのサイズが小さければ競合のコストは高くない。しかし、ロボットのサイズが２コマの場合には、相手が狭い部分を完全に通過するまで数単位時間は、退避して待つことになる。この退避の時間のコストは、大きくなる。
【００５９】
このように退避が発生する場合には、相対時間に応じて、コストの発生の可能性が違うので、例えば、ロボットαは、ソファ（Ｓｏｆａ）とコピー（Ｃｏｐｉｅｒ）の間のルートを通るなどの別ルートを利用するプランを再生成するなどの方策をとるように判断できる。このようにすれば、スクリーニングレベルで、競合の可能性と解消のためのコスト、解消の結果得られたプランの追加コストが分かり、早期に適切な判断ができる。これは、効率的なプランニングを可能とする。
【００６０】
以上に説明したように、本発明では、階層型プランニングにおいて、抽象度が減るように１階層づつ具体化する中のある中間位置で、この後の他のエージェントのプランとの競合を、過去の履歴である競合パターンより統計的に推定し、より適切なプランが生成できるようにしたものである。これは、中間位置では、ある性質を持たす行動がまとめられているとの考えを基本としている。例えば、東京から大阪まで移動する場合を考える。最も抽象的なプランは、東京から大阪へ移動するという行為であり、これだけから如何なる行動になるかあるいは競合が発生するのかを推定することは容易ではない。
【００６１】
しかし、上記行動が具体化された中間段階では、例えば、「新幹線で移動する」、「飛行機で移動する」、「夜行バスで移動する」などの段階があり、詳細レベルでは、「のぞみ１２３号に乗る」という具体的行為まで選択される。この際に、中間状態であれば、前述したようにすることで、他のエージェントとの競合や協調の可能性を推定すること可能となる。例えば、費用の総額が決められているとき、新幹線の運賃が全体の費用の枠内に納まるかなどはこの段階で（ある程度の範囲内で）決定できる。また、仮に、問題が発生しても、新幹線は頻繁に出ているので、少しの時間増で対応できるなどのことも判断可能である。
【図面の簡単な説明】
【００６２】
【図１】本発明の実施の形態における階層型プラン構築装置の構成例を示す構成図である。
【図２】マネージャーエージェント１００の動作例を説明するフローチャートである。
【図３】競合パターンについて説明するための説明図である。
【図４】部屋を動く複数ロボットの行動プランの生成対象となる部屋の状態を示す平面図である。
【図５】部屋を動く複数ロボットの行動プランの生成対象となる部屋の状態を示す平面図である。
【符号の説明】
【００６３】
１００…マネージャーエージェント、１０１…競合パターン生成部、１０２…競合発見部、１０３…競合パターン照合部、１０４…競合コスト予想部、１０５…効用値通知部、１０６…通知プラン記憶部、１０７…競合情報記憶部、１３０…エージェント、１３１…基本プラン生成部、１３２…詳細プラン選択部、１３３…記憶部、１３４…プラン決定部、１３５…競合情報生成部、１３６…通知部。
【図１】
2007026343.tif 000003
【図２】
2007026343.tif 000004
【図３】
2007026343.tif 000005
【図４】
2007026343.tif 000006
【図５】
2007026343.tif 000007