(57)【要約】      （修正有）【課題】グラフを並列探索する方法及びシステムの提供。【解決手段】状態空間抽象化を用いてＡＮＤ／ＯＲグラフの抽象的表現が構築される。このグラフの抽象的表現には、重複検出範囲を有する１つ以上の抽象ノードと、ＡＮＤノード結果に対して調整済みの演算子グループを有する１つ以上の抽象エッジと、が含まれる。エッジ分割を用いて、抽象ノードの重複検出範囲を、より小さい重複検出範囲に分割し、この抽象エッジはより小さい重複検出範囲を規定するために用いられる。処理ユニットにより、最新の探索層内のノードを、そのノードにマッピングされる抽象ノードの出発する抽象エッジの調整済み演算子グループを用いて拡張し、同時に拡張されるノードが、独立した重複検出範囲を有する抽象エッジに関連した調整済みの演算子グループを用いる。全ての最新の探索層内の演算子グループが、ノード拡張のために、使用された後に、この方法は次の探索層に進む。【選択図】図１
2013089236.tif 000002
【特許請求の範囲】
【請求項１】
電子コンピュータ環境で実行されるＡＮＤ／ＯＲグラフを探索するための並列ＡＮＤ／ＯＲグラフ探索の方法であって、
探索空間及び演算子空間の局所性を利用するステップと、
前記利用される局所性を用いて、前記ＡＮＤ／ＯＲグラフの効率的な探索を実行するステップと、を含み、前記ＡＮＤ／ＯＲグラフ探索は少なくとも１つのプロセッサ装置を使用することにより実行される、方法。
【請求項２】
前記利用するステップ、及び実行するステップが、非決定性プランニング問題に対応する、請求項１に記載の方法。
【請求項３】
前記並列グラフ探索上の前記探索方法が、ビジネスプロセス管理内のワークフローと、一連の動作と、を自動的に合成する、請求項１に記載の方法。
【請求項４】
グラフを並列探索する方法であって、
状態空間抽象化を用いてＡＮＤ／ＯＲグラフの抽象的表現を構築するステップであって、前記グラフの前記抽象的表現は、重複検出範囲を有する１つ以上の抽象ノードと、結果調整済み演算子グループを有する１つ以上の抽象エッジと、を含み、前記演算子グループはＡＮＤノード結果に対して調整される、ステップと、
エッジ分割を用いて、前記抽象ノードの前記重複検出範囲を、より小さい重複検出範囲に分割するステップであって、前記抽象エッジは前記より小さい重複検出範囲を規定するために用いられる、ステップと、
電子プロセッシングシステムにより、前記最新の探索層内のノードを、そのノードによりマッピングされた前記抽象ノードのうちの出発する抽象エッジの前記結果調整済み演算子グループを用いて、拡張するステップであって、同時に拡張されるノードが、独立した重複検出範囲を有する抽象エッジに関連する結果調整済み演算子グループを用いる、ステップと、
前記最新の探索層内の全ての前記結果調整済み演算子グループが、ノード拡張のために、使用された後、次の探索層に進むステップと、を含み、
グラフを並列探索する前記方法が、少なくとも１つのプロセッサ装置を用いて実行される、方法。
【請求項５】
前記抽象ノードには、前記グラフのＯＲノード、及びＡＮＤノードが含まれ、前記グラフの前記ＯＲノード及び前記ＡＮＤノードは、前記状態空間の投射関数のもとで前記抽象ノードにマッピングする、共に連鎖された後続ノードを有する、請求項４に記載の方法。
【請求項６】
前記グラフの第１のノードが、前記グラフの第２のノードの後続要素であり、それがＯＲノードである場合、前記抽象ノードのうちの第１の抽象ノードは、前記抽象ノードのうちの第２の抽象ノードの後続要素であり、前記第１のノードは、前記状態空間投射関数のもとで、前記第１の抽象ノードへマッピングし、前記第２のノードは、前記状態空間投射関数のもとで、前記第２の抽象ノードにマッピングし、
前記グラフの第１のノードが、前記グラフの第２のノードの後続要素で、それがＡＮＤノードある場合、前記抽象ノードのうちの第１の抽象ノードは、前記抽象ノードのうちの第２の抽象ノードの後続要素であり、前記第１のノードは、前記第２のノードの全ての後続要素に連鎖され、前記第１のノード及び前記第１のノードに連鎖されるノードは、前記状態空間投射関数のもとで、前記第１の抽象ノードへマッピングし、前記第２のノードは、前記状態空間投射関数のもとで、前記第２の抽象ノードにマッピングする、請求項５に記載の方法。
【請求項７】
前記エッジ分割には、演算子グループ分けの手順を用いて、抽象ノードｙに関する一連の適用可能な演算子０ｙを、抽象ノードｙの後続要素ごとに１つの、演算子グループに分割することが含まれ、演算子グループ０ｙ，ｙ’は、前記抽象エッジ（ｙ，ｙ’）に関連する、全ての演算子及びＡＮＤノード結果に対して調整済みの演算子から成る、前記適用可能な演算子０ｙの小集団である、請求項４に記載の方法。
【請求項８】
グラフ探索を実行するシステムであって、
不揮発性メモリと、
揮発性メモリと、
１つ以上のプロセッサであって、
状態空間抽象化を用いて前記グラフの抽象的表現を構築するためにプログラムされ、前記グラフの前記抽象的表現は、重複検出範囲を有する１つ以上の抽象ノードと、ＡＮＤノードの結果に対して調整済みの演算子グループを有する１つ以上の抽象エッジと、を含み、
エッジ分割を用いて、前記抽象ノードの前記重複検出範囲をより小さい重複検出範囲に分割するためにプログラムされ、前記抽象エッジは、前記より小さい重複検出範囲を規定するために用いられ、
処理ユニットにより、最新の探索層内のノードを、そのノードによりマッピングされた前記抽象ノードのうちの出発する抽象エッジの前記調整済み演算子グループを用いて、拡張するためにプログラムされ、同時に拡張される前記ノードが、独立した重複検出範囲を有する抽象エッジに関連する調整済み演算子グループを用い、
前記最新の探索層内の全ての前記調整済みの演算子グループが、ノード拡張のために、使用された後、次の探索層に進むためにプログラムされる、１つ以上のプロセッサと、を含むシステム。
【請求項９】
前記エッジ分割には、演算子グループ分けの手順を用いて、抽象ノードｙに関する一連の適用可能な演算子、及び結果調整済み演算子０ｙを、抽象ノードｙの後続要素ごとに１つ、演算子グループに分割することが含まれ、演算子グループ０ｙ，ｙ’は、前記抽象エッジ（ｙ，ｙ’）に関連する全ての演算子から成る前記適用可能な演算子０ｙの小集団である、請求項８に記載の方法。
【請求項１０】
グラフを探索する方法であって、
状態空間抽象化を用いて、前記グラフの抽象的表現を構築するステップであって、前記グラフの前記抽象的表現は、重複検出範囲を有する１つ以上の抽象ノードと、１つ以上の抽象エッジとを含む、ステップと、
前記グラフの前記抽象的表現に基づいて、前記グラフの前記出発するエッジを分割するステップであって、前記分割するステップは、共に前記抽象的表現の同じ抽象エッジへマッピングするエッジ、又は結果調整済み演算子を、結果調整済み演算子グループとして、グループ分けすることを含む、ステップと、
異なる結果調整済み演算子グループを、終了条件に合うまで、処理ユニットに割り当てるステップであって、前記処理ユニットが、前記結果調整済み演算子グループを用いて、後続ノードを同時に生成するステップと、
前記グラフの前記抽象的表現を用いて、前記グラフを探索するステップと、を含み、前記方法が、少なくとも１つのプロセッサ装置を使用することにより実行される、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、プランニング領域内でのグラフ探索に関し、より具体的には、現実世界の多くの用途で発生する、ビジネスプロセス管理（ＢＰＭ）を含む、非決定性環境におけるプランニングに関する。
【背景技術】
【０００２】
古典的プランニング及び非決定性プランニングを含むプランニング領域には、異なるプランニングの種類が存在する。古典的プランニングでは一連の動作が生成され、これらの動作が最終目標へ向かって移動する。非決定性プランニングでは、古典的プランニングとは異なり１つの動作により、多くの結果のうちの１つが導き出され、それらの結果は、意思決定者の制御を超える。その結果、非決定性プランニング問題（即ちプラン）に対する解決法は、もはや一連の動作ではなく、木、即ちグラフの形態をとる。それに応じて、（エージェントのオプションに対応して）古典的プランニング問題の探索空間内で一般に見出されるＯＲノードに加えて、非決定性プランニング問題の探索空間を、ＡＮＤノードと呼ばれる新しい種類の探索ノードで強化しなければならず、このノードは複数の結果に対応し、これらの結果をすべて判断しなければならない。
【０００３】
図１には、２つの動作ａ１とａ２を含むＡＮＤ／ＯＲ探索グラフ１００の一例が示されている。探索グラフの開始状態は、動作ａ１とａ２に対応する２本の出発する枝を有するＯＲノードであり、これらの枝に対してプランナーは、それらのうちの１方を選択することができる。開始状態からの各枝は、２つの後続ＯＲノードを有するＡＮＤノードに繋がり、このＡＮＤノードはあり得る  結果状態ごとに１つ存在する。因習により、ＯＲノード（即ち、選択ノード）を正方形で表し、ａ１又はａ２の非決定性結果から生じるＡＮＤノード（即ち、確率ノード）を円で表す。完全に不確実なプランでは、プランを実行した結果として全てのあり得る結果又は偶然性のもとに行われる動作を規定しなくてはならない。ｋ−コネクタにより、状態が、あり得る直近の結果ごとに、一連のｋ個の後続の状態へ接続される。ＡＮＤ／ＯＲ探索問題に対する解決法は、解グラフと呼ばれる非巡回グラフの形態をとり、以下の特徴を有する。
・開始状態は、解グラフの一部である。
・全ての非目標状態に関して、唯一の出発するｋ−コネクタだけが解グラフの一部であり、その後続の各状態も解グラフの一部である。
【０００４】
最終的に解グラフ内の全ての経路が目標状態で終了する場合、そのプランを強いプランと呼ぶ。全ての経路でなく、いくつかの経路が目標状態で終了する場合、そのプランを弱いプランと呼ぶ。強いプランでは、何があろうと目標状態に達することが保証され、一方、弱いプランでは、それは保証されない。プランニング問題が、強いプラン、又は弱いプランを受け入れるかどうかは、以下の項目に依存する。（ａ）ある状態を別の状態に変換する一連の演算子、（ｂ）開始状態、及び（ｃ）目標状態。一般には強いプランは弱いプランよりも好まれるが、非常に長い強いプランよりもより短い弱いプランが望まれる可能性のあるビジネスプロセス管理（ＢＰＭ）等、用途によっては例外もある。
【０００５】
問題、及びグラフが、より複雑になると、並列処理を加えて、問題を解決する時間を短縮させる。電子コンピュータ装置上で動作するコンピュータのアプリケーションが、問題を示すグラフを構築することでグラフを使用し、次いで、アルゴリズムを用いて、解決法に対するグラフを探索する。一般に、これらの動作は同時に行われる。ノードを拡張することにより、最初の開始状態のグラフが、動的に構築される。解決法を探すために、グラフを構築しながら、グラフ探索を行うが、このような探索では、グラフ内に周期性又は冗長性があるかどうかを考慮しなければならない。
【０００６】
ＡＮＤ／ＯＲグラフ探索問題は、ＡＯ＊アルゴリズムにより解決することができ、このアルゴリズムは明示的な探索グラフを構築する。この探索グラフは、最初は開始状態であり、以下のアルゴリズムのステップに従って徐々に拡張する。
１．各ＯＲノードにて最適な動作を、非目標の葉ノードに到達するまで、追いかけることにより、最適な非目標の葉ノードを見つける。
２．自己の後続要素を生成し、全ての新しい後続状態を明示的な探索グラフに加えることにより、最適な非目標の葉ノードを拡張する。新しい状態「ｓ」ごとに、ｆ（ｓ）＝ｈ（ｓ）と設定する。但し、ｈ（ｓ）は、受け入れ可能なヒューリスティックであり、「ｓ」から目標状態に到達するまでの費用を決して多く見積もらない。
３．拡張したばかりの状態より前の先行ノードの費用関数（ｆ‐ｃｏｓｔ）を、開始状態に到達するまで再帰的に更新し、途中に遭遇する先行状態ごとに最適な動作にマークをつける。状態「ｓ」のｆ‐ｃｏｓｔを更新するために、ｆ（ｓ）＝ｍｉｎｓ’［ｃ（ｓ、ｓ’）＋ｆ（ｓ’）］と設定する。但し、「ｓ’」は「ｓ」の状態の後続状態であり、ｃ（ｓ、ｓ’）は状態「ｓ」から状態「ｓ’」へ移る費用である。状態「ｓ」を最適な後続状態に変換する動作、ａｒｇｍｉｎｓ’［ｃ（ｓ、ｓ’）＋ｆ（ｓ’）］は、状態「ｓ」に関する最適な動作としてマークされる（ここでａｒｇｍｉｎｓとは、最小の引数の略である）。
【０００７】
ＡＯ＊では、最適な動作を追いかけることにより、到達可能な全ての葉ノードが、全て目標ノードになるまで上記のステップを繰り返す。より正確に言うと、ＡＯ＊の終了条件は以下のように規定される。
ａ．ＯＲノードが目標ノードである場合、そのＯＲノードが解決される、又はそのＯＲノードの子供のうちの１つが解決される、さもなければ、そのＯＲノードは不履行となる。
ｂ．ＡＮＤノードの全ての子供が解決された場合、そのＡＮＤノードが解決される、さもなければ、そのＡＮＤノードは不履行となる。
ｃ．開始状態が解決される、又は不履行となると、ＡＯ＊は終了する。
【０００８】
ＡＯ＊アルゴリズムの変形型では、ＡＯ＊の終了条件うちのステップ「ｂ」の規定を以下のように修正することで、弱いプラン（即ち全ての環境において目標ノードに到達することが保証されていないプラン）に対処しようとする取り組みがなされる。
ｂ’．ＡＮＤノードの全ての子供が、解決されているか、不履行のいずれかで、且つ、少なくとも１つの子供が解決される場合、そのＡＮＤノードは解決される、さもなければ、そのＡＮＤノードは不履行となる。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
強いプランが実行不可能、又は費用が掛かりすぎて、演算や実行ができないうちのどちらかの場合は、上記のｂ’の規定により、ＡＯ＊探索においてＢＰＭに対する弱いプランに対応する試みがなされる。ＢＰＭのプランニングでは、プランナーがビジネスユーザと、リアルタイム、又はセミリアルタイムで、やり取りを行わなければならないため、応答時間が重要である（人間の忍耐力に影響される）。したがって、高速のプランニングでは、自動プランニングをＢＰＭにおいて実用化するめの重要な要求事項として見なされる。しかし、単一のプロセッサコアが経時的に飛躍的に改善されることは期待できないため、ＡＯ＊の効率的な並列化、及び複数のコア又はコンピュータ上で動作する並列化の変形型が、それらの速度を著しく向上るための唯一の方法である。
【課題を解決するための手段】
【００１０】
非決定性環境において全ての可能な動作の結果を記録することにより、探索空間の組合せ爆発につながる可能性がある。したがって、並列処理を介して解決法を見つける速度を速めるために並列ＡＯ＊（又はＰＡＯ＊）の探索技術が開発された。この技術では、同時に作業をする複数のワーカに、マスターが作業を割り当てるマスター・ワーカ方式が用いられる。具体的には、
１．構築される明示的な探索グラフが著しく大きくなるまで、マスタープロセスで根ノードから順次探索する。
２．マスタープロセスで、明示的な探索グラフの末端である、並列化の最先端を分割し、下位の問題としてワーカに分配して並列解決を行う。
３．複数のワーカが、逐次的ＡＯ＊を用いて、それぞれ自己に割り当てられた下位の問題を同時に解決し、最適な下位の問題の解決法をマスタープロセスに送り戻す。
４．マスタープロセスで、全てのワーカからの解決法を組み合わせて、全体の解決法を取得する。
【００１１】
この技術を実用化するときの問題点は、明示的な探索グラフが十分に大きくなり、グラフの構築を停止（ステップ１）し、ワーカに下位の問題を分配することができる（ステップ２）時期を判定することである。さらに、複数のワーカがアクセスできる探索空間に冗長部分がある場合、どのように探索作業を調整して、ワーカ間で繰り返される作業を最小に抑えるかという別の問題もある。
【図面の簡単な説明】
【００１２】
【図１】図１は、ＡＮＤ／ＯＲグラフの一例を示す図である。
【図２】図２は、並列エッジ分割を用いて最終探索結果を得るための基本動作を示すフロー図である。
【図３】図３は、並列エッジ分割を用いて最終探索結果を得るための基本動作を示す別のフロー図である。
【図４】図４は、結果調整済み演算子を示すＡＮＤ／ＯＲグラフの一例である。
【図５Ａ】図５Ａは、Ｆコストを示すＡＮＤ／ＯＲグラフの一例であり、このＡＮＤ／ＯＲグラフが拡張する様子を示す。
【図５Ｂ】図５Ｂは、Ｆコストを示すＡＮＤ／ＯＲグラフの一例であり、このＡＮＤ／ＯＲグラフが拡張する様子を示す。
【図５Ｃ】図５Ｃは、Ｆコストを示すＡＮＤ／ＯＲグラフの一例であり、このＡＮＤ／ＯＲグラフが拡張する様子を示す。
【図５Ｄ】図５Ｄは、Ｆコストを示すＡＮＤ／ＯＲグラフの一例であり、このＡＮＤ／ＯＲグラフが拡張する様子を示す。
【図６】図６は、ＰＥＰ−ＡＯ＊におけるステップのフロー図である。
【図７】図７は、ＰＥＰ−ＡＯ＊を好適に用いたシステムの説明図である。
【図８】図８は、並列エッジ分割の特定な用途を見出した、例示的なモジュール式冗長印刷エンジンの側面図である。
【図９】図９は、ＢＰＭ問題を解決するＡＯ＊に関する実行結果を示す表である。
【図１０】図１０は、ＢＰＭ問題を解決するＰＡＯ＊に関する実行結果を示す表である。
【図１１】図１１は、ＢＰＭ問題を解決するＰＥＰ−ＡＯ＊に関する実行結果を示す表である。
【図１２】図１２は、ＢＰＭ問題を解決するための種々の技術の結果の比較を示すグラフである。
【発明を実施するための形態】
【００１３】
以下の開示では、プランニングの非決定性問題に対する、効果的な並列化ＡＮＤ／ＯＲグラフ探索の技術を説明する（図１のグラフ１００を参照）。これから説明する技術は、本明細書ではＰＥＰ−ＡＯ＊と呼ばれ、非決定性問題の解決においてＡＯ＊アルゴリズムと共に使用するための、拡張並列エッジ分割（ＰＥＰ）、つまり先進グラフ探索アルゴリズムに基づき、例えば、ＡＮＤ／ＯＲグラフの中で説明される。
【００１４】
既存のＰＥＰを実行することで、一連の特定な問題に対応してきたが、これらの実行は、ＯＲグラフだけに適用可能であった。ＰＥＰでは、状態空間抽象化、演算子空間抽象化の両方を使用し、即時の重複検出、及び低い同期化のためのオーバヘッドを提供している。ＰＥＰでは、ノード（同じ抽象状態をマッピングする一連のノード）の重複検出範囲を、抽象エッジごとに１つの、複数の区分に再分割し、これらの抽象エッジにより、抽象グラフ内で抽象状態をその後続要素のうちの１つと接続させる。抽象エッジの重複検出範囲は、抽象エッジの目的地へマッピングする一連のノードとして規定される。各抽象エッジは、オリジナルの探索問題からの一連の演算子を含む演算子グループと関連し、これらの演算子は、（１）抽象エッジのソースへマッピングするノードに適用可能であり、（２）これらの演算子を適用することにより生成される後続ノードは全て、抽象エッジの目的地である同じ抽象状態にマッピングされる。１つ演算子グループだけを１回に使用して、抽象エッジのソースにマッピングするノードに対する後続要素を生成する場合、重複検出範囲をさらに削減して１つの抽象状態にすることができ、ノードはその１つの抽象状態にマッピングされる。探索アルゴリズムの制御のもとで、どの演算子グループを使用するかが選択されるので、下層の探索グラフが局所性を全く持たなかったとしてもＰＥＰを適用することができる。
【００１５】
図２に移ると、ＯＲグラフ状態で並列エッジ分割（ＰＥＰ）を用いて最終探索結果を得るための動作のフロー図２００が示されている。このフロー図２００には、グラフの抽象的表現を構築するステップ（動作２０２）と、抽象ノードの重複検出範囲を分割するステップ（動作２０４）と、最新の探索層内のノードを拡張するステップ（動作２０６）と、全ての演算子グループが使用された後に、次の探索層に進むステップ（動作２０８）と、が含まれる。
【００１６】
図２のフロー図２００では、一連の動作又は事象として、下記に図示、説明されているが、本開示は、図示されている動作又は事象のこれらの順序には限定されない。例えば、いくつかの動作は、本明細書に図示される、及び／又は、説明される動作とは異なり、繰り返し、及び／又は、異なる順序で、及び／又は、別の動作又は事象と同時に起こる可能性があり、また図示されている全てのステップが、本開示による方法を実行する必要がなくてもよい。
【００１７】
グラフの抽象的表現は、状態空間の抽象化を用いて構築される（動作２０２）。周知の通り、このグラフの抽象的表現は、状態空間の投射関数をグラフに適用することで、徐々に構築され、この状態空間の投射関数とは、オリジナルの状態空間から抽象状態空間への多対１のマッピングのことである。グラフの抽象的表現が構築されると、その抽象ノードはそれぞれ重複検出範囲を有する。さらに、抽象エッジは、それぞれ演算子グループを含む。
【００１８】
エッジ分割を用いて、抽象ノードの重複検出範囲を、より小さい重複検出範囲に分割する（動作２０４）。これらのより小さい重複検出範囲は、それぞれ抽象エッジのうちの１つに対応する。好都合にも、これらの小さい重複検出範囲により、グラフが固有の局所性を持っていないときでも、グラフの並列探索が可能となる。
【００１９】
最新の探索層内のノードを拡張する（動作２０６）。ノードの拡張は演算子グループを用いて実現され、この演算子グループは抽象ノードに属し、最新の探索層内のノードは、この抽象ノードへマッピングする。全ての演算子グループが使用されるまで、これらの演算子グループを用いてノードを拡張する。どの時点においても独立した重複検出範囲に関する演算子グループだけが使用されている限り、複数のノードを同時に拡張することができる。グラフを探索中、重複検出範囲を有する一連の演算子グループは変化していることを理解されたい。
【００２０】
最新の探索層に対する演算子グループが全て使用された後、探索は次の探索層に進み、上記の動作を繰り返す（動作２０８）。もちろん、この動作を含む上記に説明した動作は、終了条件（例えば、目標ノード）に達するまで繰り返される。したがって、上記の動作の間で時間的関係は、必ずしも存在しないことを理解されたい。むしろ、それらの動作は同時に行われ、何度も繰り返される可能性がある。
【００２１】
図３を参照すると、並列エッジ分割を用いて最終の探索結果を得るための動作のフロー図３００が示されている。このフロー図３００には、グラフの抽象的表現を構築するステップ（動作３０２）と、抽象ノードの重複検出範囲を分割するステップ（動作３０４）と、最新の探索層内のノードを拡張するステップ（動作３０６）と、全ての演算子グループが使用された後、次の探索層に進むステップ（動作３０８）と、が含まれる。
【００２２】
図３のフロー図では、一連の動作又は事象として、下記に図示、説明されているが、本開示は、図示されている動作又は事象のこれらの順序には限定されない。例えば、いくつかの動作は、本明細書に図示される、及び／又は、説明される動作とは異なり、繰り返し、及び／又は、異なる順序で、及び／又は、別の動作又は事象と同時に起こる可能性があり、また図示されている全てのステップが、本開示による方法を実行する必要がなくてもよい。
【００２３】
状態空間抽象化を用いてグラフの抽象的表現を構築する（動作３０２）。上記で詳細に議論した通り、このグラフの抽象的表現は、状態空間への投射関数をグラフへ適用することで、徐々に構築され、この状態空間への投射関数とは、オリジナルの状態空間から抽象状態空間への多対１のマッピングのことである。グラフの抽象的表現が構築されると、それらの各抽象ノードは重複検出範囲を有する。
【００２４】
出発するグラフのエッジを、グラフの抽象的表現に基づいて分割する（動作３０４）。この分割には、同じ抽象的表現の抽象エッジに共にマッピングするエッジを、演算子のグループとして、グループ化することも含まれる。好都合にも、グラフが固有の局所性をもっていないときでも、これらの演算子グループにより、グラフの並列探索が可能となる。動作３０４は、図２の動作２０４と非常に類似していることを理解されたい。
【００２５】
終了条件に合うまで、異なる演算子グループ（即ち、独立した重複検出範囲を有する演算子グループ）を処理ユニットに割り当てる（動作３０６）。処理ユニットは、異なる重複検出範囲を用いて、複数の後続ノードを同時に生成する。この動作は、図２の動作２０６に類似しており、これにより、そちらの方を注目することを理解されたい。
【００２６】
後続ノードが生成されると、グラフが探索される（動作３０８）。例えば、最新の探索層内の各ノードをテストして探索基準に合っているかどうかを判定することができる。
【００２７】
図２と同様に、上記で説明した動作は、終了条件（例えば、終了ノード）に達するまで繰り返される。したがって、上記の動作の間に時間的関係は、必ずしも存在しないことを理解されたい。むしろ、それらは同時に行われ、何度も繰り返される可能性がある。
【００２８】
エッジ分割に関連して、抽象ノードの重複検出範囲は、もはや一連の抽象グラフ内の全ての後続抽象ノードとしては理解されず、その代り、特定な抽象グラフ内の出発するエッジを伴う単一の後続抽象ノードとして規定されることを理解されたい。このことは、抽象ノードにマッピングするノードが、エッジ分割に伴って増加的に拡張されるという事実を反映する。各ステージで、異なる抽象エッジに対応する演算子グループが適用される。その他の演算子グループが考慮される前に、演算子グループ内の全ての演算子は、抽象ノードにマッピングする全てのノードに適用される。次のステージでは、異なる出発する抽象エッジが考慮され、異なる演算子グループが、その同じ一連のノードに適用される。最終的に、その同じ抽象ノードにマッピングされる一連のノードに、全ての演算子グループが適用され、そのノードは十分に拡張する。但し、拡張ノードが十分に拡張するには、一連の増分拡張が必要である。
【００２９】
完全に接続した抽象グラフに伴う問題は、独立した範囲の存在を排除した、全ての重複検出範囲により、グラフ全体が使い尽くされる可能性があることである。しかし、エッジ分割により、全ての重複検出範囲には、ノードの単一のバケットだけが含まれるが、それでもなお、ノードを拡張し、そのノードが抽象エッジのソースバケットにマッピングするとき、同期させる必要ないことが保証される。全ての生成され得る後続要素が、ソースバケット以外の異なるバケットにマッピングする限り、複数の探索プロセスにより、同じソースバケット内のノードを拡張することができることに留意されたい。
【００３０】
したがって、並列エッジ分割は、状態空間抽象化及びエッジ分割のコンセプトの上に作られて、並列グラフ探索のために局所性を抽出する。並列エッジ分割（ＰＥＰ）の発想は、重複検出範囲を削減し、同時に発生する探索プロセス同士の衝突のレベルも削減するという認識から生じている。並列エッジ分割には、同時並行のレベルを効率的に高める効果があり、これは並列探索で可能となる。
【００３１】
上記に説明した通り、既存のＰＥＰ技術は、ＯＲグラフだけに適用可能である。この後、どのようにしてＰＥＰを探索ＡＮＤ／ＯＲグラフへ拡張させるかについて説明する。
【００３２】
既存のＰＥＰの第１の拡張は、決定性プランニングにおいて、ソース状態及び動作が後続状態を一意的に識別するという認識に関する。したがって、ＯＲグラフに関する重複検出範囲を分割するとき、並列エッジ分割だけが、それらの後続状態を考慮する。しかし、同じアプローチでは、同じ状態に適用される同じ動作により、異なる結果が導かれるため、ＡＮＤ／ＯＲグラフに対しては不十分となる。したがって、ＡＮＤ／ＯＲグラフに対する抽象エッジは、異なる結果を考慮する必要があり、それは、演算子グループについても同様であり、演算子の結果に基づいて演算子のよりきめの細かいグループ分け用いる必要がある。したがって、ＰＥＰ−ＡＯ＊では、ソース状態、動作、及びさらに、導き出される結果を考慮する。
【００３３】
図４に移ると、このＰＥＰ−ＡＯ＊に関するコンセプトが、ＡＮＤ／ＯＲグラフ４００に関連して示されている（ＡＮＤノードは円として表され、ＯＲノードは正方形として表されている）。混乱をさけるために、本明細書では、ＡＮＤ／ＯＲグラフに対する、よりきめの細かい演算子グループを「結果調整済み演算子グループ」と呼ぶ。したがって図４では、Ｓ１、即ち、最初の状態は、２つのあり得る動作、即ち、Ｏ１又はＯ２のうちの１方を行う。Ｓ２はＯ１から導かれた状態であるが、暫定的な状態であり、外部効果により２つのあり得る結果Ｓ４又はＳ５のうちの１方に導かれる。Ｓ４及びＳ５はそこからさらに動作を行うことができる状態を表す。動作演算子Ｏ１は、その目的地の状態に基づく２つのあり得る結果を含む。状態Ｓ４を導くＯ１と、とＳ５を導くＯ１とは分化している。結果調整済み演算子Ｏ１’及びＯ１’’はこの変更を反映し、結果調整済み演算子グループ内に結果調整済み演算子として含まれる。これは、ＰＥＰの場合よりもきめの細かい演算子グループ分けである。ＰＥＰの演算子グループの抽象グループをＰＥＰ−ＡＯ＊において修正してこれらの変更を結果調整済み演算子グループとして含む。このような結果調整済み演算子グループ内の演算子は、以下の特徴を共有する。
１．これらの演算子は、抽象エッジのソースにマッピングするノードに適用可能である。
２．これらの演算子を適用することにより生じる後続ノードが、同じ抽象状態にマッピングするように少なくとも１つの結果が存在し、この同じ抽象状態は抽象エッジの目的地である。
【００３４】
結果調整済み演算子グループ内の演算子には、目的地の抽象状態に繋がる一連の結果の注釈が付けられる。ＰＥＰ−ＡＯ＊がノード拡張を行うとき、特定の抽象状態に関する演算子に関連するこれらの結果だけが考慮されて、ＡＮＤ探索ノードのＯＲ後続要素が生成される。
【００３５】
ＰＥＰの第２の拡張では、同じＡＮＤノードの複数の後続ＯＲノードが共に「連鎖」されて、状態抽象化のために必要なｋ−コネクタの動作を実行する。この例では、状態Ｓ４及びＳ５が共に連鎖され、状態Ｓ６及びＳ７が共に連鎖されている。連鎖は、結合リスト等のデータ構造内で実行される。連鎖が専用のプロセスで行われる場合は、並列索探の障害となる。というのも、そのような動作はデータ破損を回避するために、潜在的に全ての他のプロセスを停止しなければならないためである。これを避けるために、結果調整済み演算子グループが使用された後、及び次のグループがワーカプロセスに割り当てられる前後に、連鎖動作を複数の増分連鎖動作に分割する。演算子の割り当ての上に連鎖動作を便乗させることで、抽象グラフをロックしなければならなくなる回数を増やすことはなく、その回数は、抽象グラフのサイズ及び探索の深さに比例する。演算子グループの割り当ては、下層の探索グラフの種類に関係なくＰＥＰに関して必要な動作である。
【００３６】
図５Ａ〜図５Ｄを参照すると、ＰＥＰの第３の拡張が示されており、ＡＮＤ／ＯＲグラフが拡張され、Ｆコストが更新される様子が示されている。より具体的には、図５Ａは、コストに関連する状態Ｓ１及び後続状態Ｓ２を示す。エッジ即ち演算子のコストと、ノードのコストとが存在する。ノードのコストはＦコストであり、これらの新しいＦコストが分かると、先行要素が更新されて後続要素のＦコストが反映される。Ｓ２はトータルＦコスト８に対する見積もられたＦコスト７と、演算子コスト１と、を有する。Ｓ２はＳ１の唯一のノードであるため、Ｓ１コストが更新されて、既知のトータルコスト８が反映される。受け入れられるＦコストは、決して多く見積もられることはない。
【００３７】
図５Ｂは、第１のレベルでの拡張を示し、ＡＮＤノードを含む。Ｓ２からＳ３への演算子コストは２であり、Ｓ３に対する見積もりは、トータルコスト６に対して４である。Ｓ２からＳ４への演算子コストは１であり、Ｓ４に対する見積もりは、トータルコスト４に対して３である。説明のために、ＡＮＤコストは全てのＡＮＤノードの後続要素に対して蓄積されるものと仮定する。Ｓ２の後続要素に対する新しいトータルコストはｓ１０である。Ｓ２に対する前のコスト７は、この拡張に基づいて１０に修正される。
【００３８】
図５Ｃを参照すると、Ｓ４がノードＳ５及びＳ６に拡張される様子が示されている。０の演算子コストが両方の状態に関連する。Ｓ５はコスト９を有し、Ｓ６はコスト８を有する。Ｓ５及びＳ６は、ＯＲノード又はその代替物であり、したがって最も安いコストが用いられる。Ｓ４は修正されて演算子コストを含むその後続状態のうちで最も安くなって、新しいＦコスト８を反映する。これを再帰的にグラフ内にフィードバックしなくてはならない。Ｓ４のＦコストは３から８に増加し、したがって、Ｓ２及びＳ１も更新されてこの新しいコストを反映する。Ｓ２に対するＦコストは、この段階で１５であり、Ｓ１に対してＦコストは、この段階で１６である。
【００３９】
図５Ｄを参照すると、ＯＲノードＳ３が拡張する様子が示されている。Ｓ７は、コスト１０及びトータルコスト１３に対して演算子コスト３を有する。Ｓ８は、コスト５及びトータルコスト７に対する演算子コスト２を有する。これは、Ｓ３に対する見積もり４よりも大きい。Ｓ３は、修正されて２つのノード拡張（１０＋３）又は（５＋２）のうちの小さい方となり、この場合は７である。Ｓ１対するＦコストは再帰的に、１９に修正される。
【００４０】
後続要素のＡＮＤノードへの連鎖と同様に、ｆ−ｃｏｓｔの更新でも障害を起こす可能性がある。ｆ−ｃｏｓｔの更新が新しい演算子グループの割り当てと組み合わされる、同様の便乗する戦略がとられる。更新済みで先行要素にまだ伝わっていないＦコストを後続要素が有する場合は、後続要素は、ＰＥＰ−ＡＯ＊がそれらのｆ−ｃｏｓｔを先行要素又は親要素にバックアップしたことを記録し、先行要素のｆ−ｃｏｓｔだけを更新する。プロセッサが重複検出範囲外の先行要素のｆ−ｃｏｓｔを更新しないように、バックアップされたｆ−ｃｏｓｔ、又は更新されていないｆ−ｃｏｓｔを適用する動作は状態空間抽象化を確認して行われる。
【００４１】
図６に移ると、上記で議論した通りＡＮＤ／ＯＲグラフにおいて、ＰＥＰをＰＥＰ−ＡＯ＊に拡張することにより、最終探索結果を得るための動作のフロー図６００が示されている。この図６００には、グラフの抽象的表現を構築するステップ（動作６０２）と、エッジ分割を用いて抽象ノードの重複検出範囲を分割し、複数の潜在的な結果を考慮するステップ（動作６０４）と、結果調整済み演算子グループを用いて、最新の探索層内のノードを拡張するステップ（動作６０６）と、次の結果調整済み演算子グループが割り当てられる前に、結果調整済み演算子グループが終了したときに、複数の後続ＯＲノードを全て、ＡＮＤノードへ共に連鎖させるステップ（動作６０８）と、新しいｆ−ｃｏｓｔが分かると、ｆ−ｃｏｓｔ及び先行要素を更新して、後続要素のｆ−ｃｏｓｔを反映させるステップ（動作６１０）と、及び全ての演算子グループが使用された後、次の探索層に進むステップ（動作６１２）と、が含まれる。図６には、ＰＥＰをＰＥＰ−ＡＯ＊に拡張するために用いられるステップが示されているが、これらの同じ拡張に図３のステップが追加されることもあり得ることを理解されたい。図６内のフロー図６００は、一連の動作又は事象として上記に図示・説明されているが、本開示は、図示されている動作又は事象のこのような順序には限定されない。例えば、いくつかの動作は、本明細書に図示される、及び／又は、説明される動作とは異なり、繰り返し、及び／又は、異なる順序で、及び／又は、別の動作又は事象と同時に起こる可能性もある、また図示されている全てのステップが、本開示による方法を実行する必要がなくてもよい。
【００４２】
図７に移ると、ＰＥＰ−ＡＯ＊を用いたシステム７００が示され、その中ではＰＥＰ−ＡＯ＊の動作を実行することができる。システム７００は、好適に、記憶装置及びデジタルプロセッサを含むコンピュータ７０２、又はその他のデジタル／電子プロセッシング／コンピュータ装置又は一連の装置により具体化され、これらのデジタルプロセッサには、単一、及び／又は、複数のコア等を有するマイクロプロセッサ、マイクロ制御装置、グラフィックス・プロセッシング・ユニット（ＧＰＵ）等が含まれる。別の実施形態では、システム７００は、サーバにより具体化され、これらのサーバは、デジタルプロセッサを備え、デジタルデータ記憶装置へのアクセス手段を含む、又は有する。また、これらのサーバには、インターネット、又はローカル・エリア・ネットワークを介して、若しくは、デジタルプロセッサ部、及びデジタルデータ記憶装置を含む携帯用通信装置等により、好適にアクセスすることができる。
【００４３】
コンピュータ７０２、又はその他のデジタルプロセッシング装置は、図示されたキーボード７０４等の１つ以上のユーザ入力装置を好適に含む、又はそのユーザ入力装置に動作可能に接続し、このユーザ入力装置が、ユーザ入力を受信してシステム７００を制御する。さらにコンピュータ７０２、又はその他のデジタルプロセッシング装置は、図示されたディスプレイ７０６等の１つ以上の表示装置を含む、又はその表示装置に操作可能に接続し、この表示装置がシステム７００の出力信号に基づいて生成される出力を表示する。別の実施形態では、システム７００を制御するための入力信号は、コンピュータ７０２上のシステム７００より、前に動作している、又はシステム７００と同時に動作する別のプログラムから、若しくはネットワーク接続部等から受信される。同様に、他の実施形態では、この出力信号はコンピュータ上のシステム７００に続いて動作する、又はシステム７００と同時に動作する別のプログラムへの入力信号として機能する、あるいはこの出力信号を、ネットワーク接続部等を介して送信することもできる。
【００４４】
システム７００はＰＥＰ−ＡＯ＊のモジュール７０８を含み、このモジュール７０８が現状の用途に従ってＰＥＰ−ＡＯ＊の動作を実行する。好適に、ＰＥＰ−ＡＯ＊モジュール７０８は外部ソースからＰＥＰ−ＡＯ＊モジュール７０８に（明示的又は暗黙的のいずれかで表された）グラフを受信し、そのＰＥＰ−ＡＯ＊を実行する。この外部ソースは、例えば、コンピュータ７０２上に記憶されたファイル、又はコンピュータ７０２のユーザでよく、このユーザがキーボード７０４を介して、ＰＥＰ−ＡＯ＊モジュール７０８とやり取りを行う。
【００４５】
いくつかの実施形態では、ＰＥＰ−ＡＯ＊モジュール７０８は、（例えば、デジタルプロセッサにより）実行可能な命令を記憶する記憶媒体により具体化されて、並列エッジ分割を実行する。この記憶媒体には、例えば、磁気ディスク又はその他の磁気記憶媒体、光ディスク又はその他の光記憶媒体、ランダム・アクセス・メモリ（ＲＡＭ）、リード・オンリ・メモリ（ＲＯＭ）、若しくはその他の電子メモリ装置又はチップ、又は動作可能に相互接続する一連のチップ、インターネット、又はローカル・エリア・ネットワークを介して命令を受信することができるインターネットサーバ等が含まれ得る。
【００４６】
図８に移ると、モジュール式の冗長プリントシステム８００が示されており、このシステム８００は、上記で議論した図７のＰＥＰ−ＡＯ＊システムの実用例の１つを例示する。このシステム８００は、１９７個の独立モジュールを含み、これらの独立モジュールは給紙装置８０２、マーキング（印刷）エンジン８０４、方向変更装置、即ち反転装置８０６、仕上げ装置、及び出力トレイ８０８等を含む。これらのモジュールが、共に動作して様々な印刷製品を作り出す。
【００４７】
印刷エンジン８０４全般にわたる印刷作業を分配するためのプランニングでＰＥＰ−ＡＯ＊を用いることができる。例えば、ＰＥＰ−ＡＯ＊を用いて、特定の印刷エンジン８０４調子が悪くなる可能性を考慮して、給紙装置８０２から出力トレイ８０８までの最短経路を見つけることができる。別の例では、ＰＥＰ−ＡＯ＊を用いて、遅れが最小となるように、印刷作業の予定を組むことができる。プランニングの問題をグラフにマッピングするために、システム状態をグラフのノードとして扱い、システム状態間の関係をグラフのエッジとして扱う。エッジの重みは、時間、距離、コスト等でよいが、それらである必要はない。次いで、プランによりシステム状態が準備される。
【００４８】
図７のＰＥＰ−ＡＯ＊のシステム７００は、印刷システム内で好適に使用されていたとしても、グラフ探索を用いる別のシステム内で、このＰＥＰ−ＡＯ＊システムを好適に用いることが可能であることを理解されたい。例えば、図７のＰＥＰ−ＡＯ＊システム７００を、ルートプランニングシステム内で、及び／又は方法で、交互に用いることもできる。つまり、あるいはＰＥＰ−ＡＯ＊を用いて２か所の場所の間の最短、又は最速の経路を見つけ出すことができる。
【００４９】
図９を参照すると、そこではＢＰＭのサンプル問題を用いて行われたテスト結果が示されている。ＢＰＭの問題領域は、状態と動作の管理と呼ばれ、ビジネスオブジェクトに影響を与えるＩＴレベルのトランザクションを実行するとき、ビジネスオブジェクトの状態の変化により、それらの値がどのように変動するかを示す。これらは、もともとトランザクションの前提条件をチェックするための宣言型の方法を提供することを目的としていた。状態と動作の管理の領域を用いることで、高いレベルのレベルビジネスオブジェクトの目標に基づくプロセスが生成される。図９には、異なるＢＰＭタイプの問題を解決するときにＡＯ＊により作り出された結果が示されている。
【００５０】
図１０を参照すると、同じ問題セット及びＰＡＯ＊、即ち並列ＡＯ＊を用いて行われたテスト結果が示されている。スレッドは、同時に動作して問題を解決するプロセッサの数を表している。一連のＡＯ＊では、並列化よる結果の改善はなされていない。というのは、必ずしも拡張されないノードが拡張されたために、余計な探索オーバヘッドが発生したためである。各下位の問題がワーカプロセスに割り当てられる時点では、並列化最先端の下で必要とされる探索深度が分からないため、負荷バランスが問題となってしまう可能性がある。非効率な負荷バランスとは、あるワーカプロセスには作業がなく、別のワーカプロセスには過剰に負荷がかかる状態である。１つの問題セットでＰＡＯ＊の余計なノードを拡張することで、プロセッサがメモリ不足となる。
【００５１】
図１１を参照すると、異なる数のスレッド、即ち並列のプロセッサを有するＰＥＰ−ＡＯ＊を用いて行われた同じテストの結果が示されている。テストされるＢＰＭ問題にとっては重要ではない、重複検出に重点を置かないことでＰＥＰ−ＡＯ＊を簡略化した。この結果では、それぞれ問題セットにおいて、スレッドの数が増えるとともに、経過時間における改善がみられている。
【００５２】
図１２を参照すると、問題ｐ−１３７に関する全てのテスト結果が、互い対比され、及び理論的に最適な並列アルゴリズムと対比される形で示されている。理論的に最適なアルゴリズムでは、完璧なスピードアップが実現されている。問題ｐ−１３７は、５つのテストされた問題の中では、平均的なパフォーマンスを示したため、これを選択した。ＰＥＰ−ＡＯ＊のオーバヘッドは、１つのスレッドを有するＰＥＰ−ＡＯ＊のパフォーマンスとＡＯ＊のパフォーマンスとの間の差で表されている。より多くのスレッドが加えられると、ＰＥＰ−ＡＯ＊は、理論的な最大値に漸近的に接近する。ＰＥＰ−ＡＯ＊は、一意的なメモリアクセスパターンを有し、メモリ監視ユーティリティを用いて監視することができる。ＰＥＰ−ＡＯ＊に関するメモリのワーキングセットは、大抵は、並列グラフ探索アルゴリズムの中で最も小さいもののうちの１つである。ＰＥＰ−ＡＯ＊は、周知の通り、探索問題が局所性を殆んど持たなくても、並列探索の間、メモリ参照をローカライズすることができる。ディスクを補足の記憶装置として用いるために、メモリ及びプロセッサを用いて行うアプローチを変更することができる。
【００５３】
ビジネスプロセス管理（ＢＰＭ）を含む多くの現実世界の用途では、非決定性環境でのプランニングが行われており、そこでは、プランナーの制御を超えて、同じ動作から異なる結果を導き出すことができる。異なる環境下で動作する強固なプランを合成するために、プランナーは異なる実行結果に基づく、異なる動作を行うコンティンジェンシープランを見出さなければならない。しかし、あり得る動作結果を記録し続けることが、即時に探索空間の組合せ爆発に繋がる可能性があるため、良好なコンティンジェンシープランはコンピュータ的に費用が掛かり得る。本開示では、ＡＮＤ／ＯＲグラフ探索として形式化された、非決定性プランニングに関する効果的な並列化方式を説明してきた。ＳＡＰからのＢＰＭ問題に対する実験により、新しいアプローチはプロセッサコアの数で線形速度向上を実現し、プランニングの時間を著しく短くすると同時に、使用されるメモリの量は同じままであることが示されている。
【００５４】
本開示で説明された並列化技術は、強い技術及び弱いプランの両方を見出すのに有効であることに留意されたい。
【００５５】
上述のＡＮＤノードを用いて、動作のあり得る偶然性、即ち結果を示し、この動作はＯＲノードからＡＮＤノードへのエッジとして表される。ＡＮＤノードの出発するエッジは、評価される、あり得る結果を表す。
【００５６】
ＰＥＰ−ＡＯ＊の一態様では、ＰＥＰ−ＡＯ＊は、抽象化判定により、並列化の最先端に関して正しいサイズ及び正しい探索ノードを避ける。
【００５７】
別の態様では、一方が明確に他方に支配されている場合、並列化の最先端で抽出される下位の問題は、各ワーカプロセスで正確に解決されなくてもよいため、ＰＥＰ−ＡＯ＊は、準最適な探索ノードの拡張を避けることにより、並列探索のオーバヘッドを削減する。
【００５８】
別の態様では、ＰＥＰ−ＡＯ＊は一連のＡＯ＊アルゴリズムよりも、著しく多くノードを拡張させない。
【００５９】
別の態様では、ＰＥＰ−ＡＯ＊は、複製物が生成されるとすぐに、その複製物を検知することができ、これにより、高度に結合されたグラフ探索問題に対して、探索効率を著しく向上させることができる。
【００６０】
別の態様では、ＰＥＰ−ＡＯ＊は、ワーカ間の通信を最小にする。
【００６１】
別の態様では、ＰＥＰ−ＡＯ＊は、メモリ参照をローカライズする。
【００６２】
上記で開示の変化物、及びその他の特徴、並びに機能、又はその代替物は、様々なシステム又は用途と組み合わせることが可能でることを理解されたい。現時点で予測できないあるいは予期しないさまざまな代替物、修正物、変更物、又は、改良物が、当業者によって、今後生み出される可能性があり、それらもまた以下の請求項により包含されることを意図する。
【図１】
2013089236.tif 000003
【図２】
2013089236.tif 000004
【図３】
2013089236.tif 000005
【図４】
2013089236.tif 000006
【図５Ａ】
2013089236.tif 000007
【図５Ｂ】
2013089236.tif 000008
【図５Ｃ】
2013089236.tif 000009
【図５Ｄ】
2013089236.tif 000010
【図６】
2013089236.tif 000011
【図７】
2013089236.tif 000012
【図８】
2013089236.tif 000013
【図９】
2013089236.tif 000014
【図１０】
2013089236.tif 000015
【図１１】
2013089236.tif 000016
【図１２】
2013089236.tif 000017