(57)【特許請求の範囲】
【請求項１】
コンピュータネットワークに接続された複数のコンピュータを備え、
前記各コンピュータは、各コンピュータ上においてアプリケーションを実行させると共に、各アプリケーション間の協調を仲介するモバイルエージェントを生成、移動、実行及び消滅させ、前記アプリケーションの有する変数に対して予め決められた制約条件に反しない値を割り付けることで、与えられた対象に関する制約充足問題の解を得るものであって、
前記各コンピュータは、アプリケーションとモバイルエージェント間で通信を実行させる通信手段と、前記対象に関する変数及びその制約条件を含む知識を格納する対象知識格納手段と、問題解決に当たって前記対象知識格納手段に格納されている対象知識に対するアプリケーション及びモバイルエージェントのアクセスを管理するための対象知識管理手段と、アプリケーションの有する変数にどのような基準で値を設定するかを選択する戦略を含む問題解決のための知識を格納する問題解決知識格納手段と、問題解決に当たって前記問題解決知識格納手段に格納されている問題解決知識に対するアプリケーション及びモバイルエージェントのアクセスを管理する問題解決知識管理手段と、モバイルエージェントをネットワークに接続された他のコンピュータに移動させるネットワーク移動手段とを備え、
前記コンピュータは、前記コンピュータ上で生成、移動、実行及び消滅されるモバイルエージェントに、モバイルエージェントの消滅をモバイルエージェントによる解の生成処理の終了もしくは各コンピュータからの通知により判定させる終了判定ステップと、前記対象知識格納手段にアクセスしてその変数及び制約条件を取得させる制約取得ステップと、前記問題解決知識格納手段にアクセスしてその問題解決知識に従い、対象知識格納手段より取得した制約条件に合うようにアプリケーションの変数に値を割り付けることで部分解を作成させ、その後はその時点までの部分と違反しないように更に変数に値を割り付けることで部分解を拡張させる制約解消ステップとを実行させることを特徴とする情報処理システム。
【請求項２】
前記制約解消ステップが、どの制約条件にも違反せずに現在の部分解を拡張することができなくなったときに、部分解に含まれる変数に代替値の割り付けを試みるためのバックトラック制御ステップを備え、
前記制約解消ステップが、前記変数に値を割り付けることについて複数の選択肢があるとき、それぞれの選択肢に対応して他のモバイルエージェントを生成し、それぞれの選択肢に対応して生成された各モバイルエージェントを互いに独立して、その選択肢にしたがって解の探索を行わせるものであることを特徴とする請求項１に記載の情報処理システム。
【請求項３】
前記制約解消ステップが、前記変数に値を割り付けることについて複数の選択肢があるとき、それぞれの選択肢に対応して他のモバイルエージェントを生成する生成消滅ステップを備え、この生成消滅ステップによってそれぞれの選択肢に対応して生成された各モバイルエージェントを互いに独立して、その選択肢に従って解の探索を行わせることを特徴とする請求項２に記載の情報処理システム。
【請求項４】
前記生成消滅ステップが、変数に割り付けることができる値が複数あるときにどのような基準で割り付ける値を選ぶかの戦略が複数あるとき、それぞれの戦略に対応してモバイルエージェントを生成させるクローン処理ステップを備え、このクローン処理ステップによって生成されたそれぞれの戦略に対応する各モバイルエージェントを互いに独立して同時並行的にその戦略にしたがって変数に値を割り付けさせることで、前記解の探索を行わせることを特徴とする請求項３に記載の情報処理システム。
【請求項５】
前記生成消滅ステップが、前記各モバイルエージェントの１つが前記解を得たとき、他の戦略に対応する各モバイルエージェントを消滅させることを特徴とする請求項４に記載の情報処理システム。
【請求項６】
前記生成消滅ステップが、前記各戦略に対応する各モバイルエージェントが得たそれぞれの前記解のうち、あらかじめ決められた基準にしたがって最良のものを選ぶものであることを特徴とする請求項４に記載の情報処理システム。
【請求項７】
前記生成消滅ステップが、複数の変数に同程度の優先度が与えられた場合に、この優先度に応じて変数値の割付を調整する必要がある変数を有するコンピュータが複数あるとき、それぞれの変数に対応して複数のモバイルエージェントを生成するマージ処理ステップを備え、
このマージ処理ステップは、それぞれの変数に対応する各モバイルエージェントに対して互いに独立して同時並行的にその変数に値を割り付けさせることで前記解の探索を行い、次いで、各変数の変更が最小になるように各変数を変化させながら、前記各モバイルエージェントをマージすることを特徴とする請求項４に記載の情報処理システム。
【請求項８】
コンピュータネットワークに接続された複数のコンピュータと、各コンピュータに設けられた通信手段、ネットワーク移動手段、知識格納手段及び知識管理手段を使用して、各コンピュータ上においてアプリケーションを実行させると共に、各アプリケーション間の協調を仲介するモバイルエージェントを生成、移動、実行及び消滅させ、前記アプリケーションの有する変数に対して予め決められた制約条件に反しない値を割り付けることで、与えられた対象に関する制約充足問題の解を得るための情報処理方法において、
前記各コンピュータの通信手段により、アプリケーションとモバイルエージェント間で通信を実行させる通信ステップと、
前記ネットワーク移動手段により、各コンピュータ上で生成したモバイルエージェントを他のコンピュータに移動させるネットワーク移動ステップと、
前記知識格納手段に、前記対象に関する変数及びその制約条件を含む知識を格納する対象知識格納ステップと、アプリケーションの有する変数にどのような基準で値を設定するかを選択する戦略を含む問題解決のための知識を格納する問題解決知識格納ステップと、
問題の解決に当たって、前記管理手段を使用して、前記対象知識格納手段に格納されている対象知識に対するアプリケーション及びモバイルエージェントのアクセスを管理するための対象知識管理ステップと、前記問題解決知識格納手段に格納されている問題解決知識に対するアプリケーション及びモバイルエージェントのアクセスを管理する問題解決知識管理ステップと、
前記コンピュータにより、モバイルエージェントの消滅をモバイルエージェントによる解の生成処理の終了もしくは各コンピュータからの通知により判定させる終了判定ステップと、前記対象知識格納手段にアクセスしてその変数及び制約条件を取得させる制約取得ステップと、前記問題解決知識格納手段にアクセスしてその問題解決知識に従い、対象知識格納手段より取得した制約条件に合うようにアプリケーションの変数に値を割り付けることで部分解を作成させ、その後はその時点までの部分と違反しないように更に変数に値を割り付けることで部分解を拡張させる制約解消ステップとを実行させることを特徴とする情報処理方法。
【請求項９】
前記制約解消ステップが、どの制約条件にも違反せずに現在の部分解を拡張することができなくなったときに、部分解に含まれる変数に代替値の割り付けを試みるためのバックトラック制御ステップを備え、
前記制約解消ステップが、前記変数に値を割り付けることについて複数の選択肢があるとき、それぞれの選択肢に対応して他のモバイルエージェントを生成し、それぞれの選択肢に対応して生成された各モバイルエージェントを互いに独立して、その選択肢にしたがって解の探索を行わせるものであることを特徴とする請求項８に記載の情報処理方法。
【請求項１０】
前記制約解消ステップが、前記変数に値を割り付けることについて複数の選択肢があるとき、それぞれの選択肢に対応して他のモバイルエージェントを生成し、かつ変数に割り付けることができる値が複数あるときにどのような基準で割り付ける値を選ぶかの戦略が複数あるとき、それぞれの戦略に対応してモバイルエージェントを生成するクローン処理ステップを備え、
前記制約解消ステップが、このクローン処理ステップによって生成されたそれぞれの戦略に対応する各モバイルエージェントを、互いに独立して同時並行的に、その戦略にしたがって変数に値を割り付けさせることで前記解の探索を行わせるステップを有するものである請求項９に記載の情報処理方法。
【請求項１１】
前記制約解消ステップが、複数の変数に同程度の優先度が与えられた場合に、この優先度に応じて変数値の割付を調整する必要がある変数を有するコンピュータが複数あるとき、それぞれの変数に対応して複数のモバイルエージェントを生成するマージ処理ステップを備え、
このマージ処理ステップは、それぞれの変数に対応する各モバイルエージェントに対して互いに独立して同時並行的にその変数に値を割り付けさせることで前記解の探索を行い、次いで、各変数の変更が最小になるように各変数を変化させながら、前記各モバイルエージェントをマージすることを特徴とする請求項９に記載の情報処理方法。
【請求項１２】
コンピュータネットワークに接続された複数のコンピュータと、各コンピュータに設けられた通信手段、ネットワーク移動手段、知識格納手段及び知識管理手段を使用して、各コンピュータ上においてアプリケーションを実行させると共に、各アプリケーション間の協調を仲介するモバイルエージェントを生成、移動、実行及び消滅させ、前記アプリケーションの有する変数に対して予め決められた制約条件に反しない値を割り付けることで、与えられた対象に関する制約充足問題の解を得るためのアプリケーション及びモバイルエージェントを備えた情報処理用プログラムを記録したコンピュータによる読取可能な記録媒体において、
前記各コンピュータの通信手段により、アプリケーションとモバイルエージェント間で通信を実行させる通信ステップと、
前記ネットワーク移動手段により、各コンピュータ上で生成したモバイルエージェントを他のコンピュータに移動させるネットワーク移動ステップと、
前記知識格納手段に、前記対象に関する変数及びその制約条件を含む知識を格納する対象知識格納ステップと、アプリケーションの有する変数にどのような基準で値を設定するかを選択する戦略を含む問題解決のための知識を格納する問題解決知識格納ステップと、
問題の解決に当たって、前記管理手段を使用して、前記対象知識格納手段に格納されている対象知識に対するアプリケーション及びモバイルエージェントのアクセスを管理するための対象知識管理ステップと、前記問題解決知識格納手段に格納されている問題解決知識に対するアプリケーション及びモバイルエージェントのアクセスを管理する問題解決知識管理ステップと、
前記コンピュータにより、モバイルエージェントの消滅をモバイルエージェントによる解の生成処理の終了もしくは各コンピュータからの通知により判定させる終了判定ステップと、前記対象知識格納手段にアクセスしてその変数及び制約条件を取得させる制約取得ステップと、前記問題解決知識格納手段にアクセスしてその問題解決知識に従い、対象知識格納手段より取得した制約条件に合うようにアプリケーションの変数に値を割り付けることで部分解を作成させ、その後はその時点までの部分と違反しないように更に変数に値を割り付けることで部分解を拡張させる制約解消ステップとを、
コンピュータに実行させることを特徴とする情報処理用プログラムを記録した記録媒体。
【請求項１３】
前記制約解消ステップが、どの制約条件にも違反せずに現在の部分解を拡張することができなくなったときに、部分解に含まれる変数に代替値の割り付けを試みるためのバックトラック制御ステップを備え、
前記制約解消ステップが、前記変数に値を割り付けることについて複数の選択肢があるとき、それぞれの選択肢に対応して他のモバイルエージェントを生成し、それぞれの選択肢に対応して生成された各モバイルエージェントを互いに独立して、その選択肢にしたがって解の探索を行わせるものであることを特徴とする請求項１２に記載の情報処理用プログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、制約充足問題などにかかわる分散処理技術の改良に関するもので、より具体的には、複数のアプリケーション間の協調をエージェントに仲介させるようにしたものである。
【０００２】
【従来の技術】
近年、生産スケジューリング問題をはじめとし、設備や部品のレイアウト問題など現実の様々な問題に対して制約充足問題（Constraint Satisfaction Problem,CSP ）の枠組みを用いた実用的なアプローチが進んでいる。制約充足問題とは、複数の変数について、変数間の制約条件を満たす値の組み合わせを解として見いだす問題である。
【０００３】
この制約充足問題では、現実の問題を構成する設備や部品といった個々の要素を変数で表す。この場合、設備や部品同士の間には、一定の距離を確保しなければならないなどといったいろいろな制約条件が存在するので、そのような制約条件は変数の間の制約条件として表す。そして、個々の要素として何種類かある選択肢のうちどれを使うか、また、平面や時間軸などの上でどこに配置するか、といった具体的な事柄は変数の具体的な値として表す。そのうえで、上に述べた制約条件が満たされるように個々の変数の値を決定してゆくことで問題の解を得る。
【０００４】
すなわち、解とは、制約条件を満たすことができる変数の値の組み合わせを得ることであり、そのような変数の値の組み合わせは、具体的には例えば、作業のスケジュールや半導体素子のレイアウトなどを表す。また、このような全体としての解の一部分、例えば、いくつかの変数の値の組み合わせは部分解と呼ばれる。また、このような制約充足問題の処理は、ある変数の値をいくつかとりうる分岐があるとき、どれを取ると次にはどのような選択肢の分岐があるかといった分岐探索が基本となる。
【０００５】
また、制約充足問題の解決に使う処理手順のような知識を問題解決知識と呼び、制約充足問題として解こうとするスケジュールやレイアウトのような対象について、どのような要素すなわち変数があるか、要素即ち変数同士の間にどのような制約条件があるかといった知識を対象知識と呼ぶ。
【０００６】
このような制約充足問題の解法の１つとして、問題に関する知識を単一の問題解決器が持ち、この問題解決器が全ての制約条件を解消するものが従来から知られている。なお、制約条件を「解消」するとは、制約条件に違反しない具体的な値を変数に割り当てることである。ここで、図９は、単一の問題解決器が問題解決知識と対象知識を全て持っている状態を示す概念図であり、それぞれの対象知識に対するいろいろな処理（メソッド）を呼び出しながら問題解決を行う状態を示している。
【０００７】
しかしながら、現実のスケジューリング問題などの大規模な制約充足問題では、問題解決の対象は物理的に分散されており、様々なレベルの意思決定に関連する行為も並行的に行なわれることが一般的である。また、単一の問題解決器に全てを行わせようとすると、大量のデータを一元的に管理しなければならないという負担が発生したり、問題のローカルな部分にかかわる固有の情報が１個所に集中して開示されるためセキュリティの確保が難しいといった問題がある。
【０００８】
特に、現実の大規模な問題に対して、上に述べたような単一の集中型システムを適用することは困難である。例えば、制約充足問題の一例として、電力系統設備作業停止計画がある。この電力系統設備作業停止計画とは、電力系統内に存在する様々な設備（母線、送電線、発電機、変圧器など）に関して、メンテナンスやリプレース、増設などの作業を行なうために、送電を一時的に停止する日時を規定するものである。
【０００９】
従来の電力系統設備作業停止計画支援システムでは、全ての電力所のスケジュールを１箇所に集中させて解いている場合が多い（参考文献：大坪  昭友、高橋敏雄、斎藤  正、島田  和恵、小野  雅也、中野  宏隆、大佐古  佳明、「作業停止計画支援システムの開発」、平９電学全大、no.1448, pp.138-139, 1997.）。しかし、このような従来技術では、規模の問題から集中計算の負荷は甚大であり多大な処理時間を要するという問題があった。また、集中計算の結果を各電力所がよしとせずに再度集中計算を繰り返すこともあり、通信のボトルネックなどの問題も発生していた。
【００１０】
さらに、このように処理や通信負荷の集中が生じると、それによって現実の動的な環境に対する適応性が低下する、などの問題点も指摘されている。そのため、現実の大規模な制約充足問題のモデル化や効率的解決の手段として、複数の問題解決器が分散協調的に問題解決を行なう手法も検討されている。
【００１１】
このように複数の問題解決器が分散協調的に問題解決を行なう手法では、潮流計算などの全体情報を必要とする制約を除いて、各電力所同士でローカルに調整可能な制約は電力所同士の分散協調によって解決するので、集中計算の負荷が軽減され、調整全体にかかる処理時間も短縮でき、各電力所の作成したスケジュールからの変更がより少なくなるなどのメリットが期待される。
【００１２】
特に近年では、現実の様々な問題に対して、大規模な制約充足問題としてモデル化したうえで、そのような問題を効率的に解決する手段として、上に述べたような分散協調的な制約充足解法が注目されている。
【００１３】
このように分散協調的な解法を使って制約充足を図る手法は分散制約充足や分散制約充足問題と呼ばれ、分散制約充足の手法として、複数の均質なエージェント（問題解決器）を使うものがある。また、この場合の代表的なアルゴリズムとしては、同期バックトラックアルゴリズムや非同期バックトラックアルゴリズムが挙げられる（参考文献：横尾  真、「チュートリアル分散探索とその周辺」、コンピュータソフトウェア、Vol.12, No.1, pp.31-86, Jan. 1995.／横尾  真、平山  勝敏、「ＣＳＰの新しい展開：分散／動的／不完全ＣＳＰ」、人工知能誌、Vol.12, No.3, pp.381-389, May. 1997.）。
【００１４】
まず、同期バックトラックアルゴリズムは、バックトラック型の探索アルゴリズムを複数のエージェントで実行するものである。このアルゴリズムでは、エージェントが変数を決定する順序が予め決定されていて、具体的には例えば、最初のエージェントが自分の変数の値を一時的に決定し、その値（部分解）を次のエージェントに送信する。そして、次のエージェントは、部分解と制約とを満たすように自分の変数の値を決定し、それを部分解に加えて次のエージェントにさらに送信する。
【００１５】
そして、あるエージェントが変数の値を決定しようとするとき、もし、部分解と制約を満たす値が存在しない場合、そのエージェントは一つ前のエージェントに対して値の変更要求（バックトラック）メッセージを送信する。このような同期バックトラックアルゴリズムでは、エージェントが逐次的な順序で部分解を送信することにより、各エージェントの持つ部分的な知識が統合されて全体の制約を満たす解が得られる。
【００１６】
また、Sycaraらは、上に述べたようなバックトラックアルゴリズムの探索効率を改善したバックジャンピングアルゴリズムを提案し、スケジューリング問題に適用した研究を行なっている（参考文献：Sycara,K.P., Roth,S.F., Sadeh,N. and Fox,M.S. 、"Distributed constrained heuristic search", IEEE Transactions on Systems, Man and Cybernetics, Vol.21, No.6, pp.1446-1461, 1991. Sycara,K.P., Roth,S.F., Sadeh,N. and Fox, M.S., "Resource Allocation in Distributed Factory Scheduling", IEEE Expert, Vol.6, No.1, pp.29-40, 1991. ）。
【００１７】
また、非同期バックトラックアルゴリズムは、上に述べたバックトラックアルゴリズムと異なり、エージェントは非同期かつ並行的に、自分の局所的な情報に基づいて自らの変数の値を決定する。そして、このような各エージェントが新しい制約条件（nogood）を互いに送信し合うことにより、全体の制約を満足する変数の値の組合わせを得るものである。
【００１８】
また、このような分散制約充足にかかわる技術として、ＯＭＧ(Object Management Group) によるＯＲＢ(Object Request Broker) であるＣＯＲＢＡ(Common Object Request Broker Architecture) などを挙げることできる。ＯＲＢは、機能単位に分割したアプリケーションを分散システムで実行・通信・管理させる仕組みであり、各アプリケーションをオブジェクトで構成し、オブジェクトの基本的な操作をアプリケーションに提供するだけでなく、印刷やデータ変換のように高度な機能をそれぞれのアプリケーションから共通かつ汎用的に利用させるほか、ビジネス用のアプリケーションには、各業種に共通の又は特化したサービスを提供する。
【００１９】
ここで、図１０は、上に述べたＣＯＲＢＡのように、それぞれのオブジェクトが問題解決知識と対象知識とを持ち、自分の持つ対象知識との関係で必要な処理を行うために、他のオブジェクトにメッセージを送ることで、他のオブジェクトが持つメソッドを利用する状態を示す概念図である。
【００２０】
また、分散制約充足にかかわる他の技術として、特開平７−６１５７、特開平９−９１４３１のように、いくつかのノードにそれぞれ固定されたエージェント（ステーショナリエージェントと呼ぶ）を個々のスケジューラとし、それらスケジューラ同士が直接交渉する例（以下「直接交渉モデル」と呼ぶ）が知られている。
【００２１】
ここで、図１１は、直接交渉モデルにおいて、複数のステーショナリエージェントＳＡ同士が直接交渉をする状態を示す概念図である。なお、オブジェクトではなくエージェントを使う直接交渉モデルでは、各エージェントが自律性を持っていることから、図１２の概念図に示すように、各エージェントは、他のエージェントからメッセージが送られてきた場合、自分が持っているどのメソッドをどのように実行するかは、自分が持っている対象知識を処理する都合などに基づいて自律的に判断する。
【００２２】
また、ＤＡＲＰＡの知識共有活動(The DARPA Knowledge Sharing Effort)によるファシリテータモデルのように、複数のエージェントが協調促進器（ファシリテータ／facilitator ）を介して、共通の知識交換用の共通言語でやり取りすることで知識の共有を計る例も知られている（西田  豊明、「協調アーキテクチャによる知識の共有と再利用」、人工知能学会誌、Vol.9, No.1, Jan. 1994, pp.23-28）。すなわち、ファシリテータモデルは、１ケ所のファシリテータを中心としてエージェント同士がやり取りを行うモデルである。
【００２３】
【発明が解決しようとする課題】
しかしながら、上に述べたような分散制約充足にかかわる従来技術には、次のような問題点が存在していた。まず、ＣＯＲＢＡのようなＯＲＢや、上に述べた直接交渉モデルでは、個々のスケジューラに対して高度なメッセージルーティング機能や通信プロトコルのような通信機能をあらかじめ組み込んでおく必要があるため、分散型のスケジューリングシステムの開発が困難である。また、既存のスケジューリングシステムの有効活用が困難という問題があった。
【００２４】
また、このように個々のスケジューラにこれら通信機能を組み込むと、スケジューラ間の協調プロトコルがあらかじめ組み込まれたものに限定されるため、プロトコルの追加や変更が困難になる。このため、例えば、様々な制約の種類に応じて、最適な制約充足アルゴリズムを協調プロトコルとして実装したり使い分けるといった効果的な使い方が困難という問題があった。なお、協調プロトコルは、複数の主体間で、ある目的を達成するために交わされる一連のやり取りを規定したプロトコルであり、一般に状態遷移図で表すことができる。
【００２５】
さらに、直接交渉モデルを構成する個々のスケジューラに、スケジューラ間の通信や分岐探索などといった複雑な処理を組み込むと、スケジューラ間で互いに持っている変数を少しずつ調整してゆくような場合、スケジューラ間で頻繁にデータをやり取りすることになり、個々のスケジューラの処理負荷が大きくなるだけでなく、スケジューラを結んでいるネットワーク上での通信量が非常に多くなるといった問題があった。
【００２６】
また、上に述べたようなＯＲＢや直接交渉モデルでは、上に述べた分岐探索の途中にネットワークトラブルなどによってある部分の探索処理が異常終了したような場合は、その影響で全体の処理に支障が生じるという問題があった。
【００２７】
また、上に述べたファシリテータモデルでも、１ケ所のファリシテータに通信や処理が集中することがシステム上のボトルネックになるという問題があった。また、ファシリテータは単純なメッセージルーティングを行うが、処理全体の進め方を導いたり、個々のスケジューラに次に何をすればよいかを指示するといった実質的な協調処理を行うものではなかったため効果的に処理を促進することができないという問題があった。
【００２８】
また、上に述べたような、分散協調的な解法を使って制約充足を図る手法では、いゆわるヒューリスティクスが解法に反映されないという問題点も存在した。ここで、ヒューリスティクスは、このような場合はこのようにすれば大抵うまくいく、といったように、経験から学んだ手法であり発見的方法とも呼ばれる。
【００２９】
そして、一般に制約充足問題では、個々のエージェントの変数の決定方法に関する戦略や、エージェント間の変数の決定順序に関する優先度といったヒューリスティクスによって、解の探索効率が大きく左右されることが指摘されている（参考文献：宮下  和雄、「制約に基づく探索とその応用」、人工知能誌、Vol.12, No.3, pp.374-380, May, 1997.）。さらに、このようなヒューリスティクスは、複数の解が存在する制約充足問題の場合には、最終的な解の質にも大きく影響する。
【００３０】
代表的なヒューリスティクスとしては、上に述べたような戦略や優先度などを場合によって切り替えるなどが挙げられる。しかし、分散制約充足について上に述べた従来のアルゴリズムでは、これら戦略や優先度として、システムの構成に応じて固定されたものを使っていたため、ヒューリスティクスを処理に効果的に反映させることはできず、探索効率や解の質を向上させることが困難であった。
【００３１】
一例として、上に述べた電力系統設備作業停止計画では、電力所同士の調整は固定的なものではなく、年間を通じての繁忙期と閑散期、電力所同士の力関係、または作業会社の処理能力などによって変化する性質のものである。そして、このような変化の結果、日程調整時の件名の優先度や作業期間の移動量の最小化、作業の平準化、停止回数の低減など複数の目的関数の取捨選択あるいは重みづけが動的に変化する。
【００３２】
そのため、状況に応じて異なる調整方式や戦略を用いるなど柔軟な調整が本来的には求められる。また、近い将来、日本の電力会社も欧米の様に発電部門と送電部門とが分離し、中小発電業者の新規参入など分散化が進むことが予想される。そういった場合、従来の固定的な調整方法よりも、各電力所や各部門といった要求元のニーズにより忠実にかつ簡単に対応できる柔軟な調整方法が望まれる。
【００３３】
しかしながら、従来技術では、上に述べたように、戦略や優先度は固定とされているか、例えば戦略を変更することができても１回毎に戦略を変えて処理の全体を再実行するしかなかった。しかし、１回毎に戦略を変えて全体を再実行するのは時間がかかるうえ、より速く解が求まる戦略を選択したい、といった要求には対応できないという問題があった。
【００３４】
また、従来では、同程度に高い優先度をもつエージェントが複数存在している場合でも、そのうちのどれかを優先させて順番に決定していくといった固定的な手法をとっていたため、必ずしも個々のエージェントにとって満足のいく解が得られるとは限らず、解の質の向上が求められていた。
【００３５】
この発明は、上に述べたような従来技術の問題点を解決するために提案されたもので、その目的は、スケジューラなど複数のアプリケーション間の協調をエージェントが仲介することで全体の処理を円滑に進めることである。また、この発明の他の目的は、アプリケーション間の協調を行わせる機能をエージェントに持たせることで、既存のアプリケーションの活用や協調プロトコルの追加や変更を容易にすることである。また、この発明の他の目的は、アプリケーション間の協調の仲介をモバイルエージェントに行わせることで処理や通信の集中を無くし、また、一部に障害が発生したときの影響が及ぶ範囲を抑えることである。
【００３６】
また、この発明の他の目的は、ヒューリスティクスをモバイルエージェントの振る舞いとして容易に分散充足問題に反映させることで柔軟な処理を実現し、探索効率と解の質を向上させることである。より具体的には、この発明の目的は、個々のスケジューラにおける変数の決定方法に関する戦略や、スケジューラ間の変数の決定順序に関する優先度に応じて、複数のモバイルエージェントを使い分けることで、分散充足問題の探索効率と解の質を向上させることである。
【００３７】
【課題を解決するための手段】
上に述べた目的を達成するため、請求項１の情報処理システムは、コンピュータネットワークに接続された複数のコンピュータを備え、前記各コンピュータは、各コンピュータ上においてアプリケーションを実行させると共に、各アプリケーション間の協調を仲介するモバイルエージェントを生成、移動、実行及び消滅させ、前記アプリケーションの有する変数に対して予め決められた制約条件に反しない値を割り付けることで、与えられた対象に関する制約充足問題の解を得るものであって、前記各コンピュータは、アプリケーションとモバイルエージェント間で通信を実行させる通信手段と、前記対象に関する変数及びその制約条件を含む知識を格納する対象知識格納手段と、問題解決に当たって前記対象知識格納手段に格納されている対象知識に対するアプリケーション及びモバイルエージェントのアクセスを管理するための対象知識管理手段と、アプリケーションの有する変数にどのような基準で値を設定するかを選択する戦略を含む問題解決のための知識を格納する問題解決知識格納手段と、問題解決に当たって前記問題解決知識格納手段に格納されている問題解決知識に対するアプリケーション及びモバイルエージェントのアクセスを管理する問題解決知識管理手段と、モバイルエージェントをネットワークに接続された他のコンピュータに移動させるネットワーク移動手段とを備え、前記コンピュータは、前記コンピュータ上で生成、移動、実行及び消滅されるモバイルエージェントに、モバイルエージェントの消滅をモバイルエージェントによる解の生成処理の終了もしくは各コンピュータからの通知により判定させる終了判定ステップと、前記対象知識格納手段にアクセスしてその変数及び制約条件を取得させる制約取得ステップと、前記問題解決知識格納手段にアクセスしてその問題解決知識に従い、対象知識格納手段より取得した制約条件に合うようにアプリケーションの変数に値を割り付けることで部分解を作成させ、その後はその時点までの部分と違反しないように更に変数に値を割り付けることで部分解を拡張させる制約解消ステップとを実行させることを特徴とする。
また、請求項８，１２の発明は、請求項１の発明を方法またはコンピュータプログラムを記録した記録媒体の観点から把握したものである。
請求項１，８，１２の発明では、複数のアプリケーションの間の協調をエージェントが仲介することで、アプリケーション間のやりとりや処理全体の管理が実現されるので、個々のアプリケーションには、複雑な協調プロトコルなどの高度な自律性を与える必要がない。このため、単体で使用されている既存のコンピュータなどのアプリケーションをベースに、それらを複数組み合わせて分散協調的なスケジューリングシステムなどを構築することが容易になる。また、協調プロトコルはエージェントの中にカプセル化されるため、プロトコルの追加や変更が容易である。具体的には、様々な種類の制約を解消するために最も適した制約充足アルゴリズムなどを協調プロトコルとして実装し、目的や状況などに応じて使い分けることなどが考えられる。また、モバイルエージェント毎に異なる協調プロトコルを組み込んで状況に応じてそれらを使い分けることで、個々のコンピュータに対して新しい協調機能を動的に追加することが可能である。これは、コンピュータ間の協調プロトコルを隠蔽し、既存のプロトコルに縛られずに容易に新しいプロトコルを使用することが可能であることを意味している。
【００３９】
請求項２の発明は、前記請求項１の情報処理システムにおいて、前記制約解消ステップが、どの制約条件にも違反せずに現在の部分解を拡張することができなくなったときに、部分解に含まれる変数に代替値の割り付けを試みるためのバックトラック制御ステップを備え、前記制約解消ステップが、前記変数に値を割り付けることについて複数の選択肢があるとき、それぞれの選択肢に対応して他のモバイルエージェントを生成し、それぞれの選択肢に対応して生成された各モバイルエージェントを互いに独立して、その選択肢にしたがって解の探索を行わせるものであることを特徴とする。
請求項９及び請求項１３の発明は、請求項２の発明を方法またはコンピュータプログラムを記録した記録媒体の観点から把握したものである。
請求項２または請求項１３の発明では、同期バックトラックアルゴリズムに準じた処理手順で、部分解の拡張や代替値の割付を試みることで、効果的な制約充足問題の解決が図られる。
【００４０】
請求項３の発明は、前記請求項２の情報処理システムにおいて、前記制約解消ステップが、前記変数に値を割り付けることについて複数の選択肢があるとき、それぞれの選択肢に対応して他のモバイルエージェントを生成する生成消滅ステップを備え、この生成消滅ステップによってそれぞれの選択肢に対応して生成された各モバイルエージェントを互いに独立して、その選択肢に従って解の探索を行わせることを特徴とする。また、請求項９の発明は、請求項３の発明を方法の観点から捉えたものである。
請求項３，９の発明では、変数の値の候補が複数あるときどのような基準で値を選ぶかの基準や、どの変数の値を先に決めるかの順序といった選択肢が複数あるとき、それぞれの選択肢を選んだ場合の解の探索を別々のエージェント（クローンと呼ぶ）に同時並行的に行わせたり、その結果を１つに統合（マージ）したりすることで、ヒューリスティクスを分散制約充足問題の処理に反映させ、解の探索効率や解の品質を改善できる。なお、「選択肢に対応してエージェントを生成する」とは、選択肢と同数のエージェントを新しく生成することには限定されず、既存のエージェントに選択肢の１つを割り当て、残りの選択肢の数だけ新しくエージェントを生成する場合を含む。
【００４１】
請求項４の発明は、前記請求項３の発明において、前記生成消滅ステップが、変数に割り付けることができる値が複数あるときにどのような基準で割り付ける値を選ぶかの戦略が複数あるとき、それぞれの戦略に対応してモバイルエージェントを生成させるクローン処理ステップを備え、このクローン処理ステップによって生成されたそれぞれの戦略に対応する各モバイルエージェントを互いに独立して同時並行的にその戦略にしたがって変数に値を割り付けさせることで、前記解の探索を行わせることを特徴とする。請求項１０の発明は、請求項４の発明を方法の観点で捉えたものである。
請求項４，１０の発明では、変数に割り付けることができる値が複数あるときにどのような基準で割り付ける値を選ぶかの戦略が複数あるとき、それぞれの戦略にしたがって複数のエージェントが互いに独立して同時並行的に解の探索を行う。これによって、変数の決定方法（変数を候補から選ぶ基準）に関する戦略というヒューリスティクスを分散制約充足問題の解法に反映させ、解の探索効率や解の品質を改善できる。
【００４２】
請求項５の発明は、請求項４記載の情報処理システムにおいて、前記生成消滅ステップが、前記各モバイルエージェントの１つが前記解を得たとき、他の戦略に対応する各モバイルエージェントを消滅させることを特徴とする。
請求項５の発明では、変数を候補から選ぶ基準に関するそれぞれの戦略に対応したエージェントのうち、１つが解を得ると他のエージェントは消滅するので、処理が迅速に終了し、システム上の負荷が軽減される。
【００４３】
請求項６の発明は、請求項４記載の情報処理システムにおいて、前記生成消滅ステップが、前記各戦略に対応する各モバイルエージェントが得たそれぞれの前記解のうち、あらかじめ決められた基準にしたがって最良のものを選ぶものであることを特徴とする。
請求項６の発明では、変数を候補から選ぶ基準に関するそれぞれの戦略に基づいた複数の解のなかから最良のものが選ばれるので、解の品質が向上する。
【００４４】
請求項７の発明は、請求項４に記載の情報処理システムにおいて、前記生成消滅ステップが、複数の変数に同程度の優先度が与えられた場合に、この優先度に応じて変数値の割付を調整する必要がある変数を有するアプリケーションを備えたコンピュータが複数あるとき、それぞれの変数に対応して複数のモバイルエージェントを生成するマージ処理ステップを備え、このマージ処理ステップは、それぞれの変数に対応する各モバイルエージェントに対して互いに独立して同時並行的にその変数に値を割り付けさせることで前記解の探索を行い、次いで、各変数の変更が最小になるように各変数を変化させながら、前記各モバイルエージェントをマージすることを特徴とする。また、請求項１１の発明は、請求項７の発明を方法の観点で捉えたものである。
請求項７，１１の発明では、複数のコンピュータの間で、どちらのコンピュータのアプリケーションの持っている変数の値を先に決めるかの順序に関する優先度が同程度のとき、それぞれを先に決めた場合について、複数のエージェントが互いに独立して同時並行的に解の探索を行う。この場合、それぞれのエージェントは、変数の決定順序という分岐の先に続く解の可能性の空間を同時並行的に探索することになる。そして、それぞれのエージェントが得た解に含まれる変数を漸次調整して探索結果を統合（マージ）することで、変数の決定順序に関する優先度というヒューリスティクスを分散制約充足問題の解法に反映させ、解の探索効率や解の品質を改善できる。なお、上に述べたマージでは、変数値の割り付けを漸次調整する点では制約解消に多少時間を要する可能性もあるが、上に述べたクローンを用いた探索効率の改善と併用すれば所要時間も短縮され、一層効果的である。
【００４７】
【発明の実施の形態】
以下、この発明の情報処理システムの実施の形態（以下「実施形態」という）として、電力系統設備作業停止計画の作成を支援する電力系統設備作業停止計画支援システムについて図面を参照しながら説明する。なお、この発明は、周辺機器を持つコンピュータを、ソフトウェアで制御することによって実現されることが一般的と考えられる。この場合、そのソフトウェアは、この明細書の記載にしたがった命令を組み合わせることで作られ、上に述べた従来技術と共通の部分には従来技術で説明した手法も使われる。また、そのソフトウェアは、プログラムコードだけでなく、プログラムコードの実行のときに使うために予め用意されたデータも含む。
【００４８】
そして、そのソフトウェアは、ＣＰＵ、コプロセッサ、各種チップセットといった処理装置、キーボードやマウスといった入力装置、メモリやハードディスク装置といった記憶装置、ディスプレイやプリンタといった出力装置などの物理的な資源を活用することでこの発明の作用効果を実現する。
【００４９】
但し、この発明を実現する具体的なソフトウェアやハードウェアの構成はいろいろ変更することができる。例えば、ソフトウェアの形式には、コンパイラ、インタプリタ、アセンブラなどいろいろあり、外部との情報をやり取りするにも、フロッピーディスクなどの着脱可能な記録媒体、ネットワーク接続装置などいろいろ考えられる。また、この発明を実現するソフトウェアやプログラムを記録したＣＤ−ＲＯＭのような記録媒体は、単独でもこの発明の一態様である。さらに、この発明の機能の一部をＬＳＩなどの物理的な電子回路で実現することも可能である。
【００５０】
以上のように、コンピュータを使ってこの発明を実現する態様はいろいろ考えられるので、以下では、この発明や実施形態に含まれる個々の機能を実現する仮想的回路ブロックを使って、この発明と実施形態とを説明する。
【００５１】
〔１．構成〕
〔１−１．大まかな構成〕
まず、図１は、この実施形態の構成を示す概念図である。すなわち、この実施形態は、各電力所に対応する複数のスケジューラＳ（前記アプリケーションにあたる）と、各スケジューラ間の協調を仲介するモバイルエージェントＭＡと、を備えている。
【００５２】
このうち、各スケジューラＳは、単体で使用される既存のスケジューリングシステムをベースに、モバイルエージェントＭＡとの接続のためのラッパーが付加されたものであり、このような既存のアプリケーションとしては各種パッケージソフトウェアなどを自由に選んで使うことができる。また、この実施形態では、ユーザは、個々のスケジューラに対して必要に応じ、電力所ごとの設備の内容などスケジューリングに使うスケジューリングデータの入力を行なうものとする。
【００５３】
この実施形態では、各電力所ごとに分散した電力系統内に存在する様々な設備（母線、送電線、発電機、変圧器など）を上に述べた「対象」とし、上に述べた「問題解決」として、それら設備についてメンテナンスやリプレース、増設などの作業を行なうために、送電を一時的に停止する日時のスケジュールすなわち作業停止計画を作成する。
【００５４】
なお、この実施形態では、図２の概念図に示すように、各スケジューラＳは、他のスケジューラＳが持っている対象知識やメソッドを利用するような協調が必要な場合、そのような他のスケジューラＳに対して直接交渉したりメッセージを送るのではなく、モバイルエージェントＭＡが協調を仲介し、協調相手となるスケジューラＳは、この仲介に基づいて、自分が部分的な作業停止計画を作成する都合に応じて、どのようなメソッドを利用させるか、また、どのような対象知識に対応する変数の値を変更するかを決定する。
【００５５】
〔１−２．スケジューラとモバイルエージェントの構成〕
ここで、図３は、コンピュータネットワークＮに接続された各スケジューラＳと、ネットワークＮ上を移動するモバイルエージェントＭＡとについて、大まかな構成を示したものである。なお、この実施形態では、スケジューラＳは、他のスケジューラＳとの協調が必要な場合、この実施形態を実現しているソフトウェアに対してシステムコールのようなリクエストを出し、協調を仲介するモバイルエージェントＭＡは、このようなリクエストに基づいて生成されるものとする。
【００５６】
そして、各スケジューラＳは、図３に示すように、ネットワークＮを介してモバイルエージェントＭＡと通信するための通信手段Ｓ１と、対象知識格納手段Ｓ２と、対象知識管理手段Ｓ３と、問題解決知識格納手段Ｓ４と、問題解決知識管理手段Ｓ５と、を備えている。
【００５７】
このうち、通信手段Ｓ１は、移動してきたモバイルエージェントＭＡと接続してデータをやり取りするための必要最低限の簡単なドライバであり、特に、他のスケジューラＳとメッセージをやり取りするための複雑なメッセージルーティング機能や協調プロトコルの機能は備えていない。また、対象知識格納手段Ｓ２は、対象である電力系統設備に関する構成などの知識、すなわち対象知識を格納する手段である。また、対象知識管理手段Ｓ３は、上に述べた対象知識に対する読み出しや更新などといったアクセスを管理する手段である。
【００５８】
また、問題解決知識格納手段Ｓ４は、どのように問題解決を行うかを表す問題解決知識を格納する手段であり、問題解決知識としては、主に、電力所を単位とした部分的な作業停止計画を作成するための処理手順などがある。また、問題解決知識管理手段Ｓ５は、上に述べた問題解決知識に対する読み出しなどのアクセスを管理する手段であり、ここでは、問題解決のための処理を行う手段、すなわち、対象知識と問題解決知識とを使って、上に述べた部分的な作業停止計画を作成する手段を兼ねているものとする。
【００５９】
また、モバイルエージェントＭＡは、協調プロトコルを実行することで各アプリケーション間の協調を仲介する手段として、通信手段Ｍ１と、協調問題解決知識格納手段Ｍ２と、協調問題解決知識管理手段Ｍ３と、ネットワーク移動手段Ｍ６と、を備えている。
【００６０】
このうち、通信手段Ｍ１は、各スケジューラＳと通信するための手段である。また、協調問題解決知識格納手段Ｍ２は、複数のスケジューラに対して、どのように協調させることで全体としての電力系統設備作業停止計画を作成させればよいかを表す協調問題解決知識を格納する手段である。また、協調問題解決知識管理手段Ｍ３は、上に述べた協調問題解決知識に対する読み出しなどのアクセスを管理する手段であり、ここでは、協調問題解決知識にしたがって協調プロトコルを実行することで、複数のスケジューラＳ間の協調を仲介する手段を兼ねているものとする。
【００６１】
つまり、モバイルエージェントＭＡでは、上に述べた協調問題解決知識格納手段Ｍ２と、協調問題解決知識管理手段Ｍ３と、ネットワーク移動手段Ｍ６とによって協調プロトコルが実現されることで、スケジューラＳ間の協調が行われるが、このような協調を実現するための仮想的回路ブロックという見方から、モバイルエージェントＭＡの具体的な構成を図４に示す。
【００６２】
〔１−３．モバイルエージェントの具体的な構成〕
ここで、図４に示す構成を説明する前提として、この実施形態における制約充足問題である電力系統設備作業停止計画について説明する。すなわち、電力系統設備作業停止計画は、どの電力所のどの設備をいつからいつまで停止するといった内容であり、設備や停止期間などを表す変数に、設備のＩＤや停止の日付や時刻などの値を割り当てたものとして作成される。また、これらの変数は、各電力所を担当する個々のスケジューラＳが複数ずつ持っているが、変数によって、他のスケジューラＳが持っている変数との間に制約条件があるものもあれば、他のスケジューラＳが持っている変数との間に制約条件がないものもある。
【００６３】
電力系統設備作業停止計画の作成は、最終的には、これら変数の全てに、変数の間にあらかじめ決められている制約条件に反しない値を割り付けることで解を得ることである。このため、各スケジューラＳは、少なくとも、他のスケジューラＳが持っている変数との間に制約条件のない変数に値を割り付けるように構成されている。他のスケジューラＳが持っている変数との間に制約条件のある変数については、必要に応じて、モバイルエージェントＭＡの仲介によって他のスケジューラＳとの間で、値のすり合わせのような協調を行って値を割り付ける。
【００６４】
このような協調を仲介するため、モバイルエージェントＭＡは、移動部３と、終了判定部４と、制約取得部５と、制約解消部６と、バックトラック制御部８と、クローン処理部９と、マージ処理部１０と、生成消滅部１１と、を備えている。このうち、移動部３は、図３に示すネットワークＮ上でモバイルエージェントＭＡを移動させることで、各スケジューラＳを巡回させるための部分であり、モバイルエージェントＭＡがどのスケジューラＳを巡回するかは、巡回リスト２として記録されていて、この巡回リスト２は協調プロトコルの進捗状況に応じて更新される。
【００６５】
また、終了判定部４は、協調プロトコルの終了条件を判定する手段であり、例えば、スケジューラＳからのリクエストで生成されたモバイルエージェントＭＡは、必要な協調プロトコルの実行を終了した場合は、自主的に消滅し又はリクエストを出したスケジューラＳからシステムへの通知などによって消去される。
【００６６】
また、制約取得部５は、スケジューラＳから、複数のスケジューラＳの持つ変数にまたがるような制約条件や、各スケジューラＳの持つ変数を受け取る手段であり、このように受け取られた制約条件１はモバイルエージェントＭＡ内に保存される。また、制約解消部６は、制約条件に合うように変数に値を割り付けることで、部分解を作成し、その後は、その時点までの部分解と違反しないように、さらに変数に値を割り付けることで部分解を拡張する手段である。
【００６７】
〔１−４．バックトラック制御にかかわる構成〕
このように、モバイルエージェントＭＡがスケジューラＳを巡回しながら、制約解消部６が変数に順次値を割り付けてゆくことで、電力系統設備作業停止計画の全体が完成に近づいてゆく。なお、新しく変数に値が割り付けられることで部分解が拡張されるたびに、直前の古い部分解は、元状態７としてモバイルエージェントＭＡ内に保存される。なお、元状態７は例えばステーショナリエージェントに保存しても良い。
【００６８】
ここで、制約充足問題で解の探索空間はツリー構造であった場合、変数に新しく値を割り付けることはツリーの分岐を１つ先に進むことを意味する。これに対応して、この元状態７はスタック形式で保存されるようになっていて、変数に値を割り付けるごとに古い部分解をスタックのトップにプッシュして（積んで）ゆき、変数に値を割り付けることができずに探索が手詰まりになったときは、スタックに積んであった元状態７をポップして（取り出して）ゆくことで、ツリーの分岐をいくつでも後戻り、すなわちバックトラックできるようになっている。
【００６９】
すなわち、バックトラック制御部８は、どの制約条件にも違反せずに現在の部分解を拡張することができなくなったときに、部分解に含まれる変数に代替値の割り付けを試みることでバックトラックを行う手段である。
【００７０】
また、生成消滅部１１は、変数に値を割り付けることについて複数の選択肢があるとき、それぞれの選択肢に対応して他のエージェントＭＡを生成する手段である。ここで、どのような選択肢がある場合にどのような他のエージェントＭＡ２を生成するか、また、どのような場合にどのエージェントＭＡをどのように消滅させるかといった解の探索アルゴリズムにかかわる判断は、クローン処理部９とマージ処理部１０が行う。
【００７１】
〔１−５．クローン処理部〕
すなわち、クローン処理部９は、変数に割り付けることができる値が複数あるときにどのような基準で割り付ける値を選ぶかの戦略が複数あるとき、生成消滅部１１に指示することで、それぞれの戦略に対応してモバイルエージェントＭＡのクローンを生成させる手段である。この場合、それぞれの戦略に対応する各モバイルエージェントＭＡは、互いに独立して同時並行的に、その戦略にしたがって変数に値を割り付けることで解の探索を行う。
【００７２】
なお、この実施形態では、クローン処理部９及び生成消滅部１１は、このように一連の戦略に対応したモバイルエージェントＭＡの１つが解を得たときは、状況に応じて、他の戦略に対応する各モバイルエージェントＭＡを消滅させるか、又は、全てのモバイルエージェントＭＡが解を得るまで一連のモバイルエージェントＭＡを消滅させずにおき、各戦略に対応する各モバイルエージェントＭＡが得たそれぞれの解のうち、あらかじめ決められた基準にしたがって最良のものを選ぶ手段を兼ねているものとする。
【００７３】
〔１−６．マージ処理部〕
また、マージ処理部１０は、値の決定順序について同程度の優先度の変数を有するスケジューラＳが複数あるとき、生成消滅部１１に指示することで、それぞれの変数に対応して他のモバイルエージェントＭＡを生成させる手段である。この場合、それぞれの変数に対応する各モバイルエージェントＭＡは、互いに独立して同時並行的に、その変数に値を割り付けることで解の探索を行う。
【００７４】
なお、この実施形態では、マージ処理部１０及び生成消滅部１１は、このように一連の変数に対応した各モバイルエージェントＭＡが、あらかじめ決められた基準を満たすまで解の探索を進めると、それら変数間の制約条件に合わせて、各変数の変更が最小になるように各変数を変化させることでそれら複数のモバイルエージェントＭＡを１つに統合、すなわちマージする手段を兼ねているものとする。
【００７５】
〔２．作用〕
次に、上に述べたように構成されたこの実施形態の作用を示す。
〔２−１．大まかな作用〕
まず、この実施形態における問題解決の大まかな流れを図５に示す。すなわち、この図に示すように、各スケジューラＳが問題解決の実行を行っているとき（ステップ５１）、他のスケジューラＳとの協調が必要になると（ステップ５２）、システムにリクエストを送ってモバイルエージェントＭＡを生成させる（ステップ５３）。このように生成されたモバイルエージェントＭＡは、協調プロトコルを実行することでスケジューラＳ間の協調を仲介し（ステップ５４）、協調プロトコルの実行が済むと例えば自動的に自己消滅する（ステップ５５）。
【００７６】
なお、モバイルエージェントＭＡがこのように協調プロトコルの機能を備えていため、モバイルエージェントＭＡに協調を仲介させるスケジューラＳの側では、協調の相手先スケジューラＳのネットワークＮ上の場所が不明であったり、協調の相手先スケジューラＳがどのようなメソッドを持っていて、それをどのようにすれば利用できるかが不明であっても、モバイルエージェントＭＡを仲介役とすることで、相手先スケジューラＳの持っている必要な機能を呼び出し利用することができる。
【００７７】
例えば、相手先スケジューラＳがステーショナリエージェントとして生成される場合、生成時にステーショナリエージェントが自分のシステム上の場所すなわちアドレスなどをシステムに登録するので（アドバタイズ）、モバイルエージェントＭＡは、このように登録された情報を参照することで、仲介の相手先スケジューラＳの位置を確認することができる。
【００７８】
〔２−２．具体的な作用〕
続いて、モバイルエージェントＭＡの作用を中心として、この実施形態の作用をより具体的に説明する。まず、上に述べたように、個々のスケジューラＳは各々幾つかの変数を有しており、各変数の値を管理している。各々のスケジューラＳが有する変数には、そのスケジューラＳにとってローカルな制約条件と、他のスケジューラＳとの間をまたがるような制約条件とが存在する。そのため、各スケジューラＳは変数の値を決定するために他のスケジューラＳと協調し、変数間の制約条件を満足するように変数の具体的な値を決めていかなければならない。
【００７９】
このように、スケジューラＳは他のスケジューラＳとの協調を必要とした際（ステップ５２）、スケジューラＳ間を仲介するためのモバイルエージェントＭＡを生成する（ステップ５３）。このように生成されたモバイルエージェントＭＡは、協調プロトコルを実行することでスケジューラＳ間の協調を仲介する。
【００８０】
このようにモバイルエージェントＭＡが実行する協調プロトコルの一例を図６に示す。この協調プロトコルは、スケジューラＳの持っている制約を取得し（ステップ６１）、巡回リストにしたがって（ステップ６３，６４）各スケジューラＳ間を巡回しながら（ステップ６５）、制約の解消、すなわち制約条件に違反しないように変数に値を割り当ててゆくことで解を探索し（ステップ６２）、探索が手詰まりになると直前のものから値の割当を取り消して処理をバックトラックさせ（ステップ６７，６８）、別の解を探索するものである（ステップ６９，７０）。
【００８１】
すなわち、この実施形態における協調プロトコルを実行するとき、モバイルエージェントＭＡでは、制約取得部５が、リクエストを出したスケジューラＳからスケジューラＳ間をまたぐ制約条件１としてどのようなものがあるのかを取得する（ステップ６１）。なお、図示はしないが、図４に示した巡回リスト２には、少なくとも、制約条件で関連づけられているそれぞれの変数を持っている各スケジューラＳが登録される。
【００８２】
そして、移動によって制約解消が可能な場合は（ステップ６２）、巡回リストを参照し（ステップ６３）、移動部３の働きによって、解消しようとする制約条件１に関連するスケジューラＳ間を移動する（ステップ６５）。なお、それ以上移動せずに制約解消が可能な場合は、制約解消部６は、ステップ６２で実際に変数に値を割り当てることで制約を解消し、ステップ６３では、この解消を受けて巡回リスト２に対して追加更新を行う。
【００８３】
このようにモバイルエージェントＭＡが移動して行くと、個々のスケジューラＳはモバイルエージェントＭＡに対して、自分の有している変数と制約条件とを開示する（ステップ６１）。モバイルエージェントＭＡは、このようにスケジューラＳ間を移動する度に、制約取得部５から新しい変数と制約条件を取得し（ステップ６１）、制約解消部６が、現在までの部分解と違反しないように各変数に対して値を割り付けていく（ステップ６２）。この流れは完全な解が生成されるか、もしくは行き詰まり状態に到達するまで繰り返す。
【００８４】
行き詰まり状態とは、全ての制約に違反することなく、現在の部分解を拡張することができない状態である（ステップ６２）。行き詰まり状態になった場合、バックトラック制御部８は、処理を１つ前の段階に戻し（ステップ６７）上に述べたスタックから元状態７をポップすることで最後に行った制約解消を取り消す（ステップ６８）。
【００８５】
そして、制約解消部６は、スタックにプッシュした１つ前の部分解におけるある変数に対して、すでに試みたものとは別の代替値を割り付けることで制約条件の解消を試みる（ステップ７０）。ステップ７０で制約が解消できたときは、それまでとは別の解を探索する処理が続けられることになる。但し、これはモバイルエージェントＭＡにおける制約充足アルゴリズムとして同期バックトラックを用いた場合であり、他の制約充足アルゴリズムを用いることもできる。
【００８６】
なお、相互に関連しない変数や制約に関しては、複数のモバイルエージェントＭＡを用いて同時並行的に解の探索を進めることが可能である。このような協調プロトコルの実行が終わると、モバイルエージェントＭＡは、自己消滅するか（図５のステップ５５）、又は、アプリケーション側からの指示によって消去される。なお、図６に示した協調プロトコルの手順には、必要に応じて、仲介の相手先スケジューラＳの位置情報や名前情報の取得、巡回先の優先度設定といった処理が加えられる。
【００８７】
〔２−３．クローンを用いた解法〕
次に、個々のスケジューラＳにおける変数の決定方法に関する戦略というヒューリスティクスを、モバイルエージェントＭＡの動作によって、分散制約充足の解法に取り入れる例を示す。
【００８８】
ここで、スケジューラＳにおける変数の決定方法に関する戦略とは、各スケジューラＳが自分の有している変数に値を設定する際に、取り得る値が複数存在した場合に、どの値を割り付けるかをどのような基準で選ぶかという戦略である。スケジューリングにおけるこのような戦略の具体例としては、前詰め／後詰め、納期優先、在庫最少など様々な観点や基準からの戦略が挙げられる。
【００８９】
従来技術では、これらの戦略はあらかじめ固定されているか、あるスケジューラの戦略を替えるためには探索全体を初めからやり直さなければならなかった。しかし、この実施形態では、各スケジューラＳの取る戦略に応じてモバイルエージェントＭＡのクローンを動的に生成し処理を分岐することで、複数の戦略に基づく解の探索を同時並行的に実行することができる。
【００９０】
例えば、主に動的な環境において即応性やリアルタイム性が要求されるような場合、スケジューラＳ間にまたがる解の探索過程において、あるスケジューラＳにおいて取り得る戦略が２通り存在し、より早く解の求まる戦略を取りたいという要求が存在する場合を考える。そのような場合、この実施形態では、複数の戦略を有するスケジューラＳにモバイルエージェントＭＡが移動してきた時点で、クローン処理部９が生成消滅部１１に指示を与えることで、モバイルエージェントＭＡのクローンを生成し、もとのモバイルエージェントＭＡと新しく生成したモバイルエージェントＭＡとにそれぞれ異なる戦略を持たせる。
【００９１】
このようにそれぞれ違った戦略を与えられた各モバイルエージェントＭＡは、与えられた戦略に基づいて変数の値の決定を行ない、それ以降の解の探索過程を全く独立に行う。そして、例えば一方の探索過程で解が見つかった時点で、クローン処理部９が生成消滅部１１に指示を与えることで他方の探索過程を行っているモバイルエージェントＭＡを消滅させれば、結果的により早く解の求まる戦略を選択したこととなる。
【００９２】
あるいは、例えば、取り得る複数の戦略の中からより質の良い解が求まる戦略を取りたい場合は、上に述べた一方の探索過程で解が見つかった時点で他方を消滅させずに探索を続けさせ、クローン処理部９が、双方の探索過程によって得られた解を比較し、良い方を選択することで、結果的により良い解の求まる戦略を選択することができる。
【００９３】
なお、上に述べたように戦略に応じて解の探索を分岐するという点だけに着目すれば、スケジューラ間のメッセージ通信によって実現することも可能である。しかし、あるスケジューラで戦略が分かれる度に、個々の協調プロトコル（制約充足アルゴリズム）に基づく一連のメッセージ通信を新たに開始し、それらを同時並行的に処理するためには、個々のスケジューラに対してメッセージ処理機能などの高度な協調機能を組み込むことが必要である。また、あらかじめ全てのスケジューラに必要な協調プロトコルを全て組み込んでおくことも必要である。
【００９４】
一方で、この実施形態では、いわば協調機能をカプセル化したモバイルエージェントＭＡによって動的なクローン生成や移動を行うことで、探索の分岐を実現するので、個々のスケジューラＳは、モバイルエージェントＭＡとの必要最小限なやり取りをサポートするのみでよい。また、モバイルエージェントＭＡによってスケジューラＳ間の協調プロトコルが隠蔽されるため、あらかじめ全ての協調プロトコルを組み込むことなく、必要に応じて新しい協調プロトコルを用いることも可能である。
【００９５】
〔２−４．マージを用いた解法〕
次に、スケジューラＳ間の変数の決定順序に関する優先度というヒューリスティクスを、モバイルエージェントＭＡによって解法の中に取り入れる例を示す。
【００９６】
ここで、スケジューラＳ間の変数の決定順序に関する優先度とは、複数の変数を、それぞれ違うスケジューラＳが持っていて、それぞれ決定順序に関して持っている優先度が同程度の高さの場合、それら複数のスケジューラが持っている各変数のうち、どの変数に優先的に値を割り付けていくか、を決定するものである。スケジューリングにおける典型的な優先度設定の例としては、若い工程から順に割り付けていく場合や、製品に近い工程から順に割り付けていく場合などが挙げられる。
【００９７】
従来技術では、同程度の優先度をもつ変数が複数存在した場合も何かしらの基準により各変数に固定的な順番を振り、それにしたがって値を割り付けていたため、同程度の優先度であるにもかかわらず、先に値を割り当てた変数に比べて、後で値を割り当てた変数は非常に条件の悪いものになるという問題があった。しかし、この実施形態では、複数のスケジューラＳからモバイルエージェントＭＡを同時発生させて各変数の値を独立に決定していき、探索の途中でモバイルエージェントＭＡ同士を１つにマージ（統合）し、このとき、互いの変数間の制約を両者にとって最も変更の少ない形で解消することで、解の探索効率と解の質を改善することができる。
【００９８】
ここで、このようにマージを使う解法について、簡単な例を挙げる。例えば、同程度の優先度を持つ変数（ｘ，ｙ）を仮定し、両者の間には（ｘ＋ｙ＝４）という制約が存在するものとする。また、各変数はそれぞれ（０〜４）の間で取り得る最も大きな値を取るという制約を有するものとする。ここで各変数に固定的な優先度を設定し、その順番にしたがって値を割り付けた場合、変数ｘとｙのどちらを優先しても（（ｘ，ｙ）＝（０，４））または（（ｘ，ｙ）＝（４，０））となり、一方にとっては非常に有利だが他方にとっては不利な状況が発生するため、最終的に得られる解も片寄ったものとなる。
【００９９】
同じ例に対してこの実施形態を適用する場合は、マージ処理部１０が生成消滅部１１に指示を与えることで、変数（ｘ）を有するスケジューラＳおよび変数（ｙ）を有するスケジューラＳのそれぞれからモバイルエージェントＭＡを生成し、まず、それぞれ独立に（ｘ＝４）および（ｙ＝４）という値を割り付ける。その後、マージ処理部１０が生成消滅部１１に指示を与えることでモバイルエージェントＭＡ同士をマージする際に、制約（ｘ＋ｙ＝４）に合わせて両者にとって最も変更が少なくなるように各変数の値を変更する。上の例では、各変数の値を徐々に小さくすることで、最終的に各変数の値（（ｘ，ｙ）＝（２，２））を決定する。
【０１００】
なお、このように優先度に応じて変数値の割り付けを漸次調整することについても、この点だけに着目すれば、スケジューラ間のメッセージ通信によって同様な処理を実現することは可能である。しかし、そのためにはやはり個々のスケジューラに対してメッセージ処理機能などの高度な協調機能を組み込むことが必要になる。また、関連するスケジューラ同士の直接的なメッセージ通信によって実現した場合には、スケジューラ間のメッセージ通信量が非常に多くなるといった問題が生じる。
【０１０１】
これに対して、この実施形態では、同様なヒューリスティクスの反映を、モバイルエージェントＭＡの移動とマージによって実現するので、個々のスケジューラＳはモバイルエージェントＭＡとの必要最小限なやり取りをサポートするのみでよく、メッセージ通信量の増大も抑えることができる。
【０１０２】
〔３．適用例と実験結果〕
続いて、上に説明したようなシステムを実際の電力系統設備作業停止計画へ適用した事例と、その事例における実験について説明する。
〔３−１．適用例の内容〕
このシステムでは、上に述べた実施形態を、Ｗｉｎｄｏｗｓ９５／ＮＴ（商標）上でＪａｖａ（商標）言語を用いて実装したもので、電力所毎に存在するスケジューラをモバイルエージェントが仲介することで、エージェント型で分散協調型の問題解決を実現する電力系統設備作業停止計画支援システムである。そして、このシステムにおけるスケジューラは、個々の電力所の意向や戦略を反映してローカルな停止計画を管理し、モバイルエージェントは、これらスケジューラ間の協調方式や交渉戦略をカプセル化したものである。また、スケジューラのインターフェースとしては、各設備の停止計画を表示するガントチャートウィンドウ、スケジューリングデータの入力や変更を行なうダイアログ、および作業員数の割り当て状況を示すウィンドウなどを用いた。
【０１０３】
また、対象となる電力系統設備作業停止計画において、電力系統は２４時間電力供給を続けなければならないため、各設備を停止させるにあたっては関連する他の設備との間の様々な制約条件を満たさなければならない。また、各設備は地域毎に存在する電力所によって分散管理されているため、それぞれが属する電力所のローカルな制約も満たさなければならない。
【０１０４】
このような電力系統設備作業停止計画を分散制約充足問題として表現する場合、変数は系統内に存在する設備に相当し、変数の値は各設備を停止させる日時に相当する。より具体的には、停止開始日時と停止終了日時の２組の変数として表現される。また、一般的に以下のような制約条件が挙げられる。
【０１０５】
（１）同時停止禁止制約
同時停止禁止設備リスト内にある設備を２箇所以上同時に停止してはならない。
（２）グループ化制約
２箇所以上の設備の停止期間を可能な限り同一期間とする。
（３）作業員数制約
設備毎に作業に要する人員数を定義し、必要な人員数が作業会社の該当日の作業員数を超えてはならない。
（４）作業禁止日制約
長期休暇期間や高負荷が予想される期間（盆、正月など）は、設備を停止してはならない。
【０１０６】
また、この適用例で使用したデータは、電力会社が有する現実の電力系統への適用を前提に、系統構成および規模共に実際の系統データを基にして作成した。具体的には、電力所数は１０、設備総数は約２００である。また、各設備に関して停止計画は月１回のペースで発生し、作業期間は内容に応じて１日から１週間の間とした。また、スケジュール立案期間は１年分とした。これらの設定は、実問題と比較しても何ら一般性を失っておらず、分散制約充足問題の一例としても妥当なものである。
【０１０７】
次に、このような適用例において、上に述べた実施形態におけるクローンを使って解を求めた実験（実験１）と、マージを使って解を求めた実験（実験２）のそれぞれについて実験の内容と実験結果とを示す。
【０１０８】
〔３−２．クローンを用いた実験１〕
〔３−２−１．実験１の内容〕
実験１では、上に述べた適用例において、個々のスケジューラにおける変数の決定方法に関する戦略というヒューリスティクスを、実施形態に示したクローンを使って解法に取り入れることで、解の探索効率を改善できることを示す。
【０１０９】
この実験では、モバイルエージェントは、各スケジューラの取り得る戦略に応じて自らのクローンを生成して探索処理を分岐し、複数の戦略に基づく解の探索を同時並行的に実行する。そこで、この適用例を、単一のモバイルエージェントがクローンによる分岐を行わずに解の探索を行った場合と比較し、制約解消までに要した実測時間の比較を行う。
【０１１０】
この実験１では、各スケジューラの初期スケジュールはランダムに作成し、スケジューラ間にまたがる全設備の内、約１０設備（変数）に関わる幾つかの制約条件の解消を試みる。但し、できるだけ個々の電力所によって作成された元スケジュールを優先するという立場を採り、各設備の配置（各変数の値）の移動量は最小になるようにする。単一のモバイルエージェントが分岐を行わずに解の探索を行う場合、各スケジューラにおける探索は、前方向、後方向の順に移動量が最小になる配置を順次探索する。制約を満たす配置が存在しない場合、モバイルエージェントはバックトラックして１つ前スケジューラへ戻る。
【０１１１】
モバイルエージェントがクローンを生成して探索処理を分岐する場合、エージェントは同様に探索を進め、バックトラックにより１つ前のスケジューラへ戻った時点で複数の戦略が選択可能であれば、自らのクローンを生成し処理を分岐する。
【０１１２】
この実験１では、スケジューラにおける変数の決定方法に関する戦略として、同時停止禁止制約に違反していた場合に設備配置を前方向にシフトするか、後方向にシフトするか、の２つを選択できるものとする。また、この実験１では、他に作業員数制約と作業禁止日制約を扱っているが、これらに関しては戦略の分岐はないものとする。
【０１１３】
〔３−２−２．実験１の結果〕
上に述べたような実験１の結果として、クローンを用いて探索を分岐した場合と単一エージェントによる探索の場合の解の探索効率の比較を図７のグラフに示す。このグラフにおいて、縦軸は、クローンを用いて探索を分岐した場合に制約解消までに要した実測時間を、単一のエージェントによって探索した場合に要した時間を１として、その何割に短縮されたかという割合で表したものである。また、横軸は戦略の分岐数、つまりエージェントがクローンを発生した回数を表している。分岐数０の場合、すなわち単一のエージェントによって探索を実行した場合の実測時間が１（１０割）である。
【０１１４】
実験結果からは、クローンを用いて探索を分岐した場合、単一のエージェントによるシーケンシャルな探索と比較して、実問題クラスの規模の問題においても実用的なクローン数である５〜１０で、処理時間を３−４割短縮することが可能であることが示された。
【０１１５】
なお、今回の実験ではクリティカルパスが優先度の高い変数にあった場合と低い変数にあった場合とで、最終的に必要なエージェント数と制約解消に要する時間の短縮率が大きく異なる。一般にクリティカルパスが優先度の高い変数にあった場合、今回の実験方法ではバックトラックにより１つ前のスケジューラに戻った時点でクローンを発生させるため、優先度の低い変数から順に分岐させていくことになり、多くのモバイルエージェントが必要とされる。
【０１１６】
しかし、優先度の高い変数から分岐するほど制約解消に要する時間の短縮率は高く、５０％に近くなっていく。一方で、クリティカルパスが優先度の低い変数にあった場合はクローンの発生数は少なくなる代わりに制約解消に要する時間の短縮率も低い。但し、これらはあくまで今回の実験方法において、バックトラックにより１つ前のスケジューラに戻った時点でクローンを発生させているためである。より実際の問題においては、ドメイン領域の知識などからクリティカルパスの位置を予測し、その周辺で積極的にクローンを発生させるなどの方法が効率的であると考えられる。
【０１１７】
〔３−３．マージを用いた実験２〕
実験２では、スケジューラ間の変数の決定順序に関する優先度というヒューリスティクスを、解法に取り入れることで解の質を向上させることができることを示す。
【０１１８】
〔３−３−１．実験２の内容〕
この適用例において、モバイルエージェントは同程度の優先度をもつ複数のスケジューラから同時発生し、各変数の値を独立に決定していく。そして、探索の途中でモバイルエージェント同士がマージして、互いの変数間の制約を両者にとって最も変更の少ない形で解消する。そこで、この適用例を次のような比較対象と比較する。この比較対象は、単一のモバイルエージェントが同程度の優先度をもつ複数のスケジューラに何かしらの基準により順番を振り、それにしたがって値を割り付けていく場合である。
【０１１９】
現実において、同程度の優先度を有する設備を持つ電力所が複数存在した場合、片方の電力所にとっては非常に有利だが、もう片方にとってはかなり努力を必要とするようなスケジュールを立てることは好ましくない。そこで、この実験２では、上に述べたグループ化制約を例にとり、同一優先度を持つ複数の設備の停止計画をグループ化した際の各設備の元配置からの移動日数を分布と見なし、標準偏差を算出する。そして、単一のモバイルエージェントによる実行に対して、マージを伴った実行の場合にどれだけ電力所間で移動量のばらつきが少なくなるかを示す。
【０１２０】
但し、各設備に対する優先度は予め規定されているものとする。また、電力所と設備の対応も既知であるものとする。また、この実験２では、他に同時停止禁止制約と作業員数制約、作業禁止日制約を扱っているが、これらに関してはマージ等の操作は行わないものとする。
【０１２１】
〔３−３−２．実験２の結果〕
上に述べたような実験２の結果として、マージを用いて変数間の制約を解消した場合と、単一エージェントによって順番に割付けを行った場合の解の質の比較を図８のグラフに示す。このグラフにおいて、縦軸は、マージを用いてグループ化制約を解消した場合の各設備の元配置からの移動日数のばらつき（標準偏差）を、単一のエージェントによって順番に割付けた場合のばらつきを１として、その何割まで縮小されたかという割合で表したものである。また、横軸はマージされた設備の総数を表している。すなわち、マージ数０の場合、すなわち単一のエージェントによって順番に割付けを行った場合のばらつきが１（１０割）である。
【０１２２】
この実験結果からは、マージを用いて変数間の制約を解消した場合、単一のエージェントによって順番に割付けを行った場合と比較して、スケジューラ（電力所）間の移動日数のばらつきを大きく減少させることが可能であることが示された。このことは、同程度の優先度を有する設備を持つ電力所が複数存在した場合、各電力所にとって平等なスケジュールを立てることが可能であることを示している。
【０１２３】
〔４．効果〕
以上説明したように、この実施形態では、複数のスケジューラＳ（アプリケーション）の間の協調をエージェントが仲介することで、スケジューラＳ間のやりとりや処理全体の管理が実現されるので、個々のスケジューラＳには、複雑な協調プロトコルなどの高度な自律性を与える必要がない。このため、単体で使用されている既存のスケジューラなどのアプリケーションをベースに、それらを複数組み合わせて分散協調的なスケジューリングシステムなどを構築することが容易になる。
【０１２４】
また、この実施形態では、協調プロトコルはエージェントの中にカプセル化されるため、プロトコルの追加や変更が容易である。具体的には、様々な種類の制約を解消するために最も適した制約充足アルゴリズムなどを協調プロトコルとして実装し、目的や状況などに応じて使い分けることなどが考えられる。
【０１２５】
また、モバイルエージェント毎に異なる協調プロトコルを組み込んで状況に応じてそれらを使い分けることで、個々のスケジューラに対して新しい協調機能を動的に追加することが可能である。これは、スケジューラ間の協調プロトコルを隠蔽し、既存のプロトコルに縛られずに容易に新しいプロトコルを使用することが可能であることを意味している。
【０１２６】
また、この実施形態では、スケジューラＳが必要に応じてエージェントを生成することで所望の協調プロトコルを利用できるので、運用の柔軟性が向上する。また、この実施形態では、同期バックトラックアルゴリズムに準じた処理手順で、部分解の拡張や代替値の割付を試みることで、効果的な制約充足問題の解決が図られる。
【０１２７】
また、この実施形態では、変数の値の候補が複数あるときどのような基準で値を選ぶかの基準や、どの変数の値を先に決めるかの順序といった選択肢が複数あるとき、それぞれの選択肢を選んだ場合の解の探索を別々のエージェントのクローンに同時並行的に行わせたり、その結果を１つに統合（マージ）したりすることで、ヒューリスティクスを分散制約充足問題の処理に反映させ、解の探索効率や解の品質を改善できる。
【０１２８】
特に、この実施形態では、変数に割り付けることができる値が複数あるときにどのような基準で割り付ける値を選ぶかの戦略が複数あるとき、それぞれの戦略にしたがって複数のエージェントが互いに独立して同時並行的に解の探索を行う。これによって、変数の決定方法（変数を候補から選ぶ基準）に関する戦略というヒューリスティクスを分散制約充足問題の解法に反映させ、解の探索効率や解の品質を改善できる。
【０１２９】
この場合、変数を候補から選ぶ基準に関するそれぞれの戦略に対応したエージェントのうち、１つが解を得たときに他のエージェントを消滅させるようにすれば、処理が迅速に終了しシステム上の負荷が軽減される。また、この実施形態における別の例として、変数を候補から選ぶ基準に関するそれぞれの戦略に基づいた複数の解のなかから最良のものを選ぶようにすれば、解の品質が向上する。
【０１３０】
また、この実施形態では、スケジューラＳの間で、どちらのスケジューラＳの持っている変数の値を先に決めるかの順序に関する優先度が同程度のとき、それぞれを先に決めた場合について、複数のエージェントが互いに独立して同時並行的に解の探索を行う。この場合、それぞれのエージェントは、変数の決定順序という分岐の先に続く解の可能性の空間を同時並行的に探索することになる。そして、それぞれのエージェントが得た解に含まれる変数を漸次調整して探索結果を統合（マージ）することで、変数の決定順序に関する優先度というヒューリスティクスを分散制約充足問題の解法に反映させ、解の探索効率や解の品質を改善できる。
【０１３１】
なお、上に述べたマージでは、変数値の割り付けを漸次調整する点では制約解消に多少時間を要する可能性もあるが、上に述べたクローンを用いた探索効率の改善と併用すれば所要時間も短縮され、一層効果的である。
【０１３２】
また、この実施形態では、エージェントとして、各スケジューラＳまで移動できるモバイルエージェントＭＡを使うので、個々のスケジューラＳに対して高度なメッセージルーティング機能を組み込むことが不要になり、既存のスケジューリングシステムを流用して分散型のスケジューリングシステムを構築することが容易になる。また、個々のスケジューラＳにメッセージルーティング機能を組み込む必要がないことから、スケジューラＳ間の協調プロトコルがあらかじめ組み込まれたものに限定されることがなく、目的に応じた協調プロトコルをモバイルエージェントＭＡに実行させるなど柔軟な運用が可能となる。
【０１３３】
さらに、変数の漸次調整などスケジューラＳ間で頻繁にデータをやり取りするような処理を行う場合、モバイルエージェントＭＡがそのようなデータのやり取りを代替する。このため、スケジューラＳの処理負荷が軽減され、ネットワークＮ上の通信量も削減できるので、これらがシステム上のボトルネックになることがなく、システムのスループットが向上する。
【０１３４】
特に、上に述べたような変数の値を候補から選ぶ基準となる戦略や変数の決定順序といったヒューリスティクスを制約充足問題の解法に組み込む場合、これらヒューリスティクスにかかわる処理は局所性が強いため並列実行が可能である。そして、この実施形態では、このように並列実行が可能な処理をそれぞれ別々のモバイルエージェントＭＡの自律的な動作として自然な形でモデル化し容易に実装できる。このため、ヒューリスティクスを制約充足問題の解法に反映させるためのソフトウェア構築が容易であり、ソフトウェアの保守性や拡張性も向上する。
【０１３５】
加えて、ネットワークトラブルなどのため、あるモバイルエージェントＭＡがある戦略に基づいて行っていた分岐探索処理が途中で異常終了したような場合でも、影響はそのモバイルエージェントＭＡやその戦略といった最小限の範囲にとどまり、他のスケジューラＳや他の戦略を持つモバイルエージェントなどには波及しないので、処理全体に及ぶ影響が最小限となる。
【０１３６】
〔５．他の実施形態〕
なお、この発明は上に述べた実施形態に限定されるものではなく、次に例示するような他の実施形態をも含むものである。例えば、この発明は制約充足問題だけでなく、他の所望の分野に適用することができる。また、各アプリケーションの種類も自由であり、例えば、エージェントでも、オブジェクトでも自由に選択することができる。また、アプリケーション間の仲介を行うエージェントは必ずしもモバイルエージェントである必要はなく、さらに、エージェントを１つだけ使うか複数使うかも自由である。
【０１３７】
また、図１から図４に示す構成や図５，図６に示す処理手順などは一例に過ぎず、この発明の範囲内で構成や処理手順は自由に変更することができる。例えば、対象知識や、問題解決知識、協調問題解決知識などの内容や形式は自由に定めることができる。また、複数の選択肢に対応してエージェントを生成するなどしてヒューリスティクスを分散制約問題の解法に反映させることも必須ではない。また、このようにヒューリスティクスを取り入れる場合も、変数について値を選ぶ基準や決定順序などはヒューリスティクスの一例に過ぎず、他の所望のヒューリスティクスを同様に解法に反映させることができる。
【０１３８】
また、上に述べた実施形態では、協調プロトコルの具体例として同期バックトラックを使った制約充足アルゴリズムを挙げたが、協調プロトコルは同期バックトラックを使ったものには限定されず、さらに、制約充足アルゴリズムにも限定されない。すなわち、協調プロトコルとして契約ネットアルゴリズムなど所望のものを使うことが可能である。
【０１３９】
例えば、一例として、この契約ネットアルゴリズムを使う場合、タスクアナウンス（処理を依頼するための入札公告）をしようとするスケジューラなどのステーショナリエージェントがモバイルエージェントを生成し、生成されたモバイルエージェントは、入札する可能性がある他のステーショナリエージェントを巡回する。このとき、モバイルエージェントは、依頼したい内容を個々のステーショナリエージェントに知らせるとともに入札内容を集めて周り、自分を生成したステーショナリエージェントのところに戻って入札内容を渡す。ステーショナリエージェントは、モバイルエージェントが集めてきた入札を互いに比較して落札者を決め、実際のタスクをモバイルエージェントに託して落札者のところへもう一度派遣し、実際の処理が行われる。
【０１４０】
また、上に述べた実施形態では、制約条件の解消にかかわる手段、すなわち、スケジューラから制約条件と変数を受け取る手段、部分解を作成し拡張する手段、部分解を拡張できなくなると代替値の割り付けを試みる手段、を直接備えている例を示したが、これらの手段はエージェント本体が必ずしも直接備えている必要はない。すなわち、制約条件の解消にかかわるこれらの処理を専門に行うアプリケーションなどとエージェントが協調して問題を解決する場合もあり、このような例もこの発明の範囲に含まれるものである。
【０１４１】
【発明の効果】
以上のように、この発明によれば、アプリケーション間の協調を行わせる機能をエージェントに持たせることで、既存のアプリケーションの活用や協調プロトコルの追加や変更が容易になる。
【図面の簡単な説明】
【図１】この発明の実施形態を示す概念図。
【図２】この発明の実施形態において、スケジューラＳ間の協調をモバイルエージェントが仲介する状態を示す概念図。
【図３】この発明の実施形態の構成を示す機能ブロック図。
【図４】この発明の実施形態におけるモバイルエージェントの具体的な構成を示す機能ブロック図。
【図５】この発明の実施形態における大まかな処理手順を示すフローチャート。
【図６】この発明の実施形態における協調プロトコルを示すフローチャート。
【図７】この発明の実施形態の適用例における実験１の結果を示すグラフ。
【図８】この発明の実施形態の適用例における実験２の結果を示すグラフ。
【図９】従来技術の一例として、単一の問題解決器が集中的に処理を行う例を示す概念図。
【図１０】従来技術の一例として、オブジェクト同士が直接やり取りする場合を示す概念図。
【図１１】従来技術の一例として、直接交渉モデルを示す概念図。
【図１２】従来技術の一例として、エージェントが直接交渉を行う例を示す概念図。
【符号の説明】
ＭＡ…モバイルエージェント
Ｍ１，Ｓ１…通信手段
Ｍ２…協調問題解決知識格納手段
Ｍ３…協調問題解決知識管理手段
Ｓ…スケジューラ
Ｓ２…対象知識格納手段
Ｓ３…対象知識管理手段
Ｓ４…問題解決知識格納手段
Ｓ５…問題解決知識管理手段
１…制約条件
２…巡回リスト
３…移動部
４…終了判定部
５…制約取得部
６…制約解消部
７…元状態
８…バックトラック制御部
９…クローン処理部
１０…マージ処理部
１１…生成消滅部
ＳＴＥＰ…手順の各ステップ
【図１】
0003943710.tif 000002
【図２】
0003943710.tif 000003
【図３】
0003943710.tif 000004
【図４】
0003943710.tif 000005
【図５】
0003943710.tif 000006
【図６】
0003943710.tif 000007
【図７】
0003943710.tif 000008
【図８】
0003943710.tif 000009
【図９】
0003943710.tif 000010
【図１０】
0003943710.tif 000011
【図１１】
0003943710.tif 000012
【図１２】
0003943710.tif 000013