"並列グラフ探索方法であって、状態空間抽象化を用いてグラフの抽象化表現を構築する工程で、グラフの抽象化表現が重複検出作用域を有する1以上の抽象化ノードと演算子群を有する1以上の抽象化エッジとを含む工程と、エッジ分割を用いて抽象化ノードの重複検出作用域をより小さな重複検出作用域に分割する工程で、抽象化エッジを用いてより小さな重複検出作用域を規定する工程と、ノードを写像する抽象化ノードの外向性抽象化エッジの演算子群を用いてそのときの探索レイヤ内のノードを拡張する工程で、拡張が互いに素の重複検出作用域を有する抽象化エッジに関連する演算子群を用いてノードを並列に拡張し、この拡張が処理装置により行なわれる工程と、そのときの探索レイヤ内の全ての演算子群をノード拡張に使い切ったときに次の探索レイヤに進む工程とを含む、方法。抽象化ノードはグラフのノードで構成され、状態射影関数の下でグラフのノードを抽象化ノードへ写像する、請求項1に記載の方法。グラフの第1のノードがグラフの第2のノードの後続節点である場合、抽象化ノードの第1の抽象化ノードは抽象化ノードの第2の抽象化ノードの後続節点であり、状態空間射影関数の下で第1のノードを第1の抽象化ノードへ写像し、状態空間射影関数の下で第2のノードを第2の抽象化ノードへ写像する、請求項2に記載の方法。抽象化エッジ用の重複検出作用域は、抽象化エッジの終点へ写像するグラフのノードで構成される、請求項1に記載の方法。グラフ探索実行システムであって、少なくとも1つの計算部と入/出力部とメモリとを有する計算システムで、計算部が、状態空間抽象化を用いてグラフの抽象化表現を構築する工程で、グラフの抽象化表現が重複検出作用域を有する1以上の抽象化ノードと演算子群を有する1以上の抽象化エッジとを含む工程と、エッジ分割を用いて抽象化ノードの重複検出作用域をより小さな重複検出作用域に分割する工程で、抽象化エッジを用いてより小さな重複検出作用域を規定する工程と、ノードを写像する抽象化ノードの外向性抽象化エッジの演算子群を用いてそのときの探索レイヤ内のノードを拡張する工程で、拡張が互いに素の重複検出作用域を有する抽象化エッジに関連する演算子群を用いてノードを並列に拡張し、この拡張が処理装置により行なわれる工程と、そのときの探索レイヤ内の全ての演算子群をノード拡張に使い切ったときに次の探索レイヤに進む工程とを実行するようプログラムされている、システム。下記は、エッジ分割を用いた並列グラフ探索アルゴリズムを記述するものであり、状態空間抽象化を用いた構造化された重複検出の上に組み立てられるものである。エッジ分割は局在性を抽象化し、並列ノード拡張を可能にする。アルゴリズムは、探索グラフの本来の局在性に依存しない。エッジ分割を用いて探索グラフの演算子集合を細分することで、アルゴリズムは固有の局在性を持たないグラフから局在性を抽出する。構造化重複検出SDDはグラフ内の局在的構造を梃入れし、内部メモリとディスク間で記憶ノードを分割する。重複検出は、ノード拡張期間中に遂行することができる。局在的構造は、状態空間抽象化の使用を通じて明らかにされる。状態空間抽象化は、状態空間グラフを状態空間投影関数の使用を介して生成される抽象化状態空間グラフに抽象化するものであり、この関数は原状態空間から、各抽象化状態すなわち抽象化ノードが原状態空間内の状態群すなわち、ノードに対応する抽象化状態空間への多点-単点写像である。状態空間射影関数は、一部状態変数を無視することで作成される。所与の状態空間グラフと状態空間射影関数が与えられると、下記の如く抽象化状態空間グラフを構成することができる。抽象化グラフ内の抽象化ノードと呼ばれるノード集合は、抽象化状態の集合に対応する。抽象化ノードy’は、原状態空間内に2つの状態x’とxが存在し、ix’がxの後続節点であって、ii状態空間射影関数の下でx’とxがそれぞれy’とyに写像される場合で、かつその場合にのみ、抽象化ノードyの後続節点となる。1つの状態xが抽象化状態yへ写像されると、そのときyはxの画像と呼ばれる。図2の8パズル20内の全ての駒の位置を無視し、空欄位置だけ考える場合、9個の抽象化状態B0~B8で、1つの状態が空欄の各可能な位置に対応する抽象化状態空間グラフ22が得られる。この状態空間射影機能により作成される抽象化状態空間グラフ22は、空白位置にのみ基づき1つの状態を抽象化状態に写像する。各抽象化ノードBiは、8パズル20の位置iに位置する空欄を有する状態集合に対応する。SDDでは、原探索グラフ内の記憶ノードはn個のブロックに分割されており、ここでn個のブロックは同じ抽象化ノードに写像されるノード集合に対応する。この分割された記憶ノードが与えられると、SDDは重複検出作用域の概念を用いて記憶基準を局在化する。原探索群内のノードxの重複検出作用域は、射影関数の下でのノードxの画像である抽象化ノードyの後続節点へ写像する全記憶ノードあるいは等価的にn個全てのブロックとして規定される。重複検出作用域により、探索アルゴリズムは記憶ノードの一部分に対する重複の照合と、さらに全ての重複物が発見されることを保証できるようになる。外部メモリグラフ探索アルゴリズムはRAMを用い、そのときの重複検出作用域内にn個のブロックを記憶させ、RAMが満杯であるときは他のn個のブロックの記憶にディスクを用いる。SDDは、幅優先探索等のノード集合を一度に拡張する探索アルゴリズムを用いて使用され、ここで群中のノードを拡張する順序はディスク入/出力部を最小化するよう調整することができる。ディスク入/出力部を最小化するSDDの戦略は、重複検出作用域の変化ができる限り低頻度で行なわれ、できる限り少数のブロックの変化が含まれるようノード拡張に指示するものである。RAMが満杯であるときは、そのときの重複検出外部のn個のブロックはディスクに全て吐き出される。ノードを異なるn個のブロック内で拡張するときは、ディスクに記憶させたその重複検出作用域内のあらゆるブロックをRAMへスワップする。ドメイン非依存STRIPSプラニングについては、SDDが使用する状態空間射影関数を自動的に作成し、各プラニングドメインの探索グラフに適合させる。並列構造重複検出PSDDは、外部メモリグラフ探索内のメモリ基準を限局化するのに用いる同一の局在的構造に梃入れし、並列グラフ探索に必要な同期処理の回数を低減するSDDの拡張である。PSDDでは、グラフ探索は各アイドルプロセッサにn個の拡張対象ブロックを割り当てることで並列化し、抽象化グラフを用いその重複検出作用域が対関係において互いに素であるn個の拡張対象ブロックを見いだすものである。何故ならそれらは同期すなわち、ロック無しで並列に探索できるからである。2つの重複検出作用域は、それらがn個のブロックを全く共有しない場合は互いに素であり、したがって拡張ブロックの重複検出作用域が対関係において互いに素であるという条件がメモリ基準の局在性を保証する。処理工程間の同期は、1つの処理工程がそのときのn個のブロック内の全てのノードの拡張を終了し、新たなn個のブロックの取得が必要となった後でのみ必要となる。n個のブロックbは、後続節点が全く使用されていないすなわち、その重複検出作用域がそのときのn個の拡張ブロックの重複検出作用域とは互いに素である場合で、かつその場合にのみ、1つの処理工程に自由に割り当てられる。n個の自由ブロックはσb、すなわち別の処理工程により使用されているbの後続節点間のn個のブロックの数を系統立って追跡することで見いだされる。n個のブロックは、そのσ=0であるときにのみ取得することができる。したがって、PSDDは単一ロックを用い、抽象化グラフの操作を制御するだけでよく、それは探索対象である新規のn個の自由ブロックを見いだすときにだけ処理工程が取得する。SDDの適用可能性は、抽象化群の作成に用いる状態空間射影関数が原探索グラフ内の局在的構造を捕捉するかどうかに依存する。多くのプラニング問題がSDDにより梃入れすることのできる局在的構造を有するが、この種の局在的構造が所与の問題に対し存在する保証は皆無である。エッジ分割は、この問題を解決し、探索グラフが見掛け上は局在的構造を持たないときですらメモリ基準を局在化できるよう保証するSDDを機能強化したものである。エッジ分割時に、n個のブロックの重複検出作用域は抽象化グラフ内の全ての後続節点のn個のブロック群としてはもはや規定されず、代りに、抽象化グラフ内の具体的な外向性エッジに沿った単一の後続節点のn個のブロックとして規定される。エッジ分割を用いることで、n個のブロック内のノードは歩進的に拡張される。各段において異なる抽象化エッジに対応する演算子群が適用され、演算子群の全ての演算子が他の任意の演算子群を検討する前にn個のブロック内の各ノードに適用される。次に、異なる外向性抽象化エッジを検討し、異なる演算子群を同じノード集合に適用する。その結果、全ての演算子群がn個のブロックのノードに適用され、ノードは完全に拡張される。ノードの全拡張には、一連の歩進的拡張が要求される。図3は、エッジ分割を示すものである。そこには、K4抽象化グラフ30すなわち、4個のノードを有する完全連結抽象化グラフが図示されており、ここでは抽象化ノード32二重円で図示へのノードの写像は左側から右側にかけて歩進的に拡張される。左側から右側へ追うことで、抽象化ノード32へのノード写像は抽象化ノード32と34とを連結する抽象化エッジに関連する演算子群を用いて拡張される。抽象化ノード32へのノード写像は、抽象化ノード32と36とを連結する抽象化エッジに関連する演算子群を用いて拡張される。最後に、抽象化ノード32へのノード写像が抽象化ノード32と38を連結する抽象化エッジに関連する演算子群を用いて拡張される。各拡張ステージでは、重複検出作用域は単一の抽象化ノードだけを包含する。すなわち、関連する抽象化エッジの目的地へのノード写像である。エッジ分割は、SDDを用いた外部メモリグラフ探索の性能改善に用いられてきた。各ブロック内のノード集合がRAM内に適合する限り、エッジ分割を用いるSDDは抽象化グラフが局在的構造を捕捉するか否かに拘わらず効果的である。エッジ分割は、外部メモリグラフ探索の内部メモリ要件を低減し、拡張性を改善する。演算子は、インスタンス化されたすなわち、根付き演算子である。例えば、8パズルは、たとえインストール前はたった4個左右上下の演算子しかなくとも、全部で192個の根付き演算子を有する。エッジ分割における演算子のグループ分けは、状態抽象化の頂部に構築される。Oを、探索問題のインスタンス化された全ての演算子の集合とする。ioがxに適用可能で、iixがyへ写像されるよう原状態空間内に状態xが存在する場合で、かつその場合にだけ、演算子o∈Oは抽象化ノードyに適用可能である。8パズルについて考える。空欄はパズル盤の左上隅に位置するときに右B0→B1または下B0→B3のいずれかへ移動させることができ、8パズルのどの駒を空欄位置へ移動させるかに応じて各移動が8個の異なるインスタンス化を有するため、抽象化ノードB0に適用可能な2×8=16個の演算子が存在する。同様に、各抽象化ノードB2,B6,B8は16個の適用可能な演算子を有する。抽象化ノードB1,B3,B5,B7はそれぞれ3×8=24個の適用可能な演算子を有し、抽象化ノードB4は4×8=32個の適用可能な演算子を有する。したがって、B0=16,B1=24,B2=16,B3=24,B4=32,B5=24,B6=16,B7=24,B8=6であり、これらが192個の根付き演算子となる。各抽象化ノードの適用可能な演算子集合が一旦特定されると、演算子のグループ分けは各適用可能な演算子ごとにそれが関連する抽象化エッジを識別する。抽象化エッジy,y’は、y’がyの後続節点である場合、その場合に限り、一対の抽象化ノードy,y’を連結する抽象化グラフ内のエッジである。ここから先は、yy’を抽象化エッジy,y’の始点終点と呼ぶ。さらに、Oyは抽象化ノードyに適用可能な演算子集合となる。演算子o∈Oyは、原状態空間内に2つの状態x,x’が存在し、ioがxに適用可能で、iix’がoをxに適用した後の生成状態であり、iiixとx’がそれぞれyとy’に写像される場合で、かつその場合にだけ、抽象化エッジy,y’に関連付けられる。決定的効果を有する演算子については、各o∈Oyごとに、oに関連付けることのできる固有の抽象化エッジy,y’が存在する。事実上、演算子空間から抽象化エッジ空間へは多点-単点写像が存在する。演算子空間内で局在的構造を開拓するため、エッジ分割は抽象化ノードyについて適用可能な演算子集合Oyを、抽象化グラフ内のyの各後続節点に1つずつ演算子群に分割する演算子グループ分けを用いる。演算子群Oy,y’は、抽象化エッジy,y’に関連する全ての演算子からなるOyの部分集合である。全てのy’≠yについて、Oy,y’∩Oy,y=Φであり、かつであることに留意されたい。なお、後続節点yは抽象化グループ内のyの後続節点集合である。演算子グループ分けは本願明細書では暗示表現されたグラフ開始状態と後続節点生成用演算子集合により表わされるグラフの探索文脈で提示されているが、同じ技法は僅かな修正をもって明示的に表現されたグラフ頂点群とエッジ群とで表わされるグラフに適用される。並列エッジ分割PEPは、並列グラフ探索の目的に合わせ局在性を抽出すべく、状態空間抽象化とエッジ分割の概念の上に構築される。それは、共有メモリと分散メモリの両方の並列化に用いることができる。簡単化するため、この後の説明は分散メモリ並列化における通信オーバーヘッドではなく共有メモリ並列化における同期オーバーヘッドを低減するこの手法を使用することだけに言及するものとする。何故なら両方の並列設定について原理は同じままだからである。PEPは、重複検出作用域の低減がそのときの探索処理工程間の競合度を低減し、それによって並列探索において許容される同時並行度を増大させるものと認識している。並列探索の最大の同時並行性の正式な定義が、下記である。定義1:並列探索の最大の同時並行性は、その処理工程において同時並行ノード拡張に同期が一切不要となるよう探索期間中に許容される並列処理の最大数である。補助定理1:PSDDの最大の同時並行性は、抽象化状態空間グラフの互いに素の重複検出作用域の最大数である。上記の補助定理は、それをエッジ分割と組み合わせて使用するか否かに拘わらず、PSDDに当てはまる。しかしながら、エッジ分割は重複検出作用域の定義を変更し、同じ抽象化状態空間グラフに見いだすことのできる互いに素の重複検出作用域の数を増大させるため、エッジ分割は最大の同時並行性を増大させる。定義2:状態空間射影関数Πの下での抽象化エッジy,y’に関する1つのノードxのエッジ分割された重複検出作用域は、抽象化ノードy’に写像される記憶ノード集合に対応する。抽象化エッジy,y’に関する重複検出範囲は、下記を包含するよう保証されている。すなわち、1単一の抽象化ノードy’抽象化エッジの終点へ写像されるノードのみと、2演算子群Oy,y’を抽象化ノードy抽象化エッジの始点へ写像するノード集合に適用することで生成されるこれらの後続節点に関する全ての潜在的な重複とであり、ここで演算子群Oy,y’はOyの部分集合、すなわち抽象化エッジy,y’に関連する全ての演算子で構成される抽象化ノードについての適用可能な演算子yの集合である。上記特性が、エッジ分割がRAM内に単一のn個のブロックのノードを記憶させるだけで済むことを保証し、その一方で最悪の場合に生ずる全ての重複を捕捉するよう保証する。この訴えは、全てがRAM内に適合する内部メモリ探索の文脈に維持される。定理1:SDDエッジ分割を用いないの下での互いに素の重複検出作用域の最大数は、抽象化グラフの最小出次数により除算した抽象化状態空間グラフの大きさ|抽象化グラフの大きさ/抽象化グラフの最小出次数|2により制限される。証明:最小出次数を有する抽象化ノードは、最小数の後続節点を有し、そのことが片やブロック数の点で最小の重複検出作用域を生み出す。抽象化グラフが、互いにkの素の作用域に分割できると仮定する。同じ抽象化ノードを2以上の作用域内に出現させることはできないため、その値kは最小の作用域の大きさで除した抽象化の総数、あるいは等価的には最小の出次数を上回ることはできない。全ての実用目的にとって、最小の出次数は定理1の使用時に抽象化グラフの平均出次数により置き換えねばならないが、稀な事例では、このことが真の最大同時並行性を過小評価することがある。推論1:エッジ分割を用いないPSDDの最大の同時並行性は、抽象化グラフの最小の出次数により除した抽象化状態空間グラフの大きさにより制限される。推論2:完全に連結された抽象化状態空間グラフに対するエッジ分割を用いないPSDDの最大の同時並行性は、1であるすなわち、同時並行性は皆無である。上記の2つの推論は、補助定理1と定理1に直接的に従属する。推論2によれば、PSDDはそれが完全に連結されている場合、抽象化グラフおよび対応する探索グラフの並列出力を抽出するその能力を喪失し、許容される最大の同時並行性は、ノード拡張の全ての同期無縁期間を保証する必要がある場合に、単一の探索処理工程としかならない。図1では、完全に連結された抽象化グラフとの問題は、全ての重複検出作用域がグラフ全体を使い尽くす筈である点にあり、それは互いに素の作用域の存在を排除する。しかし、エッジ分割を用いることで、重複検出作用域は単一バケットのノードすなわち、n個のブロックしか含まず、一方でソースバケットの抽象化エッジに写像されるノードの拡張時に一切の同期が必要でなくなることが依然として保証される。複数の探索処理工程は、生成することのできる後続節点が全てソースバケット以外の異なるバケットに写像される限り、同じソースバケット内でノードを拡張することができる。定理2:エッジ分割下の互いに素の重複検出作用域の最大数は、抽象化状態空間グラフの大きさである。推論3:並列エッジ分割の最大の同時並行性は、抽象化状態空間グラフの大きさに等しい。どのようなノードのエッジ分割重複検出作用域も常に単一のバケットであるとの特性が与えられると、これらは直接的な結果となる。それらはエッジ分割を用いないPSDDについての類似の結果よりも有意味でもある。何故ならそれらは互いに素の作用域の厳密な最大の数を明らかにし、これらの数に上限を設定するだけの定理1や推論2とは異なるからである。定理3:所与の状態空間射影関数にとって、任意の並列探索アルゴリズムの最大の同時並行性は、重複が生成されるや否や検出しなければならない場合、抽象化状態空間グラフの大きさにより制限される。証明:抽象化グラフの大きさをkとし、さらに並列探索の最大の同時並行性がkを上回るものと仮定する。一般性を喪失することなく、他のk番目の処理工程を同期を用いることなく合体させることのできるk1番目の処理工程を想定する。重複はそれらが生成されるや否や捕捉しなければならないため、このことはk1番目の処理工程にその重複検出作用域への排他的アクセスを与えねばならないことを意味し、それは少なくとも1つの抽象化ノードを使い尽くすものである。しかし、抽象化ノードしか存在しないため、分類棚の原理に従い、2つの処理工程により共有される1つの抽象化ノードが存在しなければならず、それらは互いに同期して重複検出を同時に遂行しなければならない。このことは、k1番目の処理工程をしてはならず、代りに定理を当てはめねばならないことを証明する矛盾に通ずる。定理3では、PEPは最適であり、何故なら他のアルゴリズムは、重複検出し損なったり、状態空間射影関数を変更したり、そのいずれもすることなく、より高いレベルの最大の同時並行性を全く獲得できないからである。全ての並列探索アルゴリズムが低解像度の同一の状態空間射影関数を用いるよう強いられる場合、PEPを簡単に全ての中で最良のものにできるため、定理3はまた我々の計算実験のセットアップを教示するものでもある。したがって、下記の実験に使用される各個別のアルゴリズムに最も適した射影関数が用いられる。PEPは、下記の如く要約することができる。各探索レイヤに、その中の非干渉演算子群を全ての演算子群が適用されるまで複数の処理装置へ分散させる。非干渉演算子群選択用の規範とは、一方の演算子群が生成する後続節点群は他方の演算子群が生成するものと重複しえないことが保証されているからため、2つの演算子群が同一の終点抽象化状態を共有する限り、それらは並列ノード拡張期間中に同期あるいは通信を用いることなく同時に使用できることである。したがって、各処理装置は重複検出に局在的にすなわち、単一の抽象化状態内で的を絞りさえすればよく、包括的な重複検出態様はPEPにより同期とは無縁の仕方で取り扱われる。図4中、抽象化グラフの3個の歩進ノード拡張ステージがPEPに従って図示してある。3個の歩進ノード拡張ステージは、図1に示す3個の隠れ状態を有する隠れマルコフモデルの特性を呈する抽象化グラフを拡張するものである。図1との1つの差異は、図4の各ノードが具体的な状態群HMMではこれらは隠れ状態にあるを表わす抽象化状態にある点にあり、したがって各ノードは下位の場合のsに代えて大文字Sを用いて標識付けしてある。したがって、1つの抽象化状態が1000個の具体的状態に対応する場合、そのときは図4に示した問題は図1のものよりもほぼ3桁は大きな大きさとなる。PEPは大きな問題を解くべく設計されているため、その効率は概ね探索問題の大きさに合わせて増大する。図4では、抽象化状態S0,S1,S2に写像するノードは、後続節点の生成に用いられる演算子群が互いに干渉しない場合、並列に拡張することができる。演算子群は、2個の演算子群が同一の終点抽象化状態すなわち、重複検出作用域を共有しない限り、干渉はしない。ステージ402を手始めに、複数の処理装置が時刻tiに抽象化状態S0,S1,S2に写像するノードを歩進拡張する。処理装置は、抽象化状態S0を自らに連結する抽象化エッジに関連する演算子群を用いて抽象化S0に写像するノードを拡張する。他の処理装置の同様に、抽象化状態S1とS2を拡張する。ステージ404と406において抽象化状態S0,S1,S2に写像するノードをさらに拡張するよう、異なる演算子群を選択して用いる。1つの演算子群を用いて抽象化状態に写像する全てのノードを拡張した後、全ての演算子群が用いられるまで別の演算子群を選択する。1つのノードの後続節点が全てノードの拡張時に並列エッジにより生成されるとは限らないため、エッジ分割におけるノード拡張は歩進的な拡張となる。一旦全ての適用可能な演算子群が適用されると、ノードは結果的に全て拡張される。PEP効率は、幾つかの因子により影響を受けることがある。一つは負荷バランスであり、それは状態空間抽象化を用いる並列探索への手法に関連するものである。静的な状態空間射影関数はバケットに対しノードを均一に分散させることは出来ない。何故なら一部のバケットは大半のノードを収容するが、その他のバケットはノードを全く持たないからである。下記に説明する実験では、全てのアルゴリズムに対し静的な射影機能を用い、負荷バランス問題に対処する能力を試験した。PEPだけでは負荷バランス問題は解決しないが、それは問題を程々のものにすることができる。同一資源のバケットはPEP内の複数の処理工程により拡張することができ、すなわちバケットが相当に大きくなると、アルゴリズムは複数の処理工程が同一のバケット上で機能するよう、大きなタスクをより小さな部分に分割するのと等価に、各適用可能な演算子群ごとに1つずつ割り当てることができ、より多くの部分があるほど、全ての探索処理工程をビジー状態に保つことのできる可能性が高くなる。どのような並列アルゴリズムについても、設計義務はデットロックの不在を証明することにある。PEPにとって証明は簡単である。何故ならそれはデットロックに対する4個の必要条件、すなわち1相互排除、2保持待機、3専占無し、4循環待機のうちの1つを乱すからである。PEPでは決して満たされない条件は保持待機である。何故なら一旦探索処理工程が抽象化エッジの重複検出作用域である単一バケットのノードすなわち、単位資源の保持を取得すると、ノード拡張と共に前進する必要のある全てを手にし、デットロックが発生する期間を待機することは皆無となるからである。PEPは、設計によりデットロック無しであるため、それはデットロック検出あるいはデットロック回避用のオーバーヘッドを全く持たない。PEPは同じ演算子群を歩進拡張に使用する限り、同期は一切必要ないことを保証するが、処理装置が1つの演算子群から別のものへ切り替わるときや、あるいは探索が1つの探索レイヤから次へ移行するときに、一部の軽量の同期が必要になることがある。そのときのレイヤから次へ探索を移動させる方法だけでなく、演算子群を処理装置に割り当てる複数の方法もまた存在する。他のものを用いることができるが、本願明細書では単一ロック方式以下、単一ロック並列エッジ分割と呼ぶを説明する。より精細な複数ロック方式等の追加の方式が、並列エッジ分割に等しく適用可能である。単一ロックPEPは、下記のデータ構造を記憶する、すなわち、作動可能とされた演算子群の動作カウンタを、そのときの探索レイヤについてのその作動可能とされた演算子群の数の追跡を維持する各抽象化ノードに記憶させる。演算子群は、1そのレイヤについて後続節点を生成するのに用いられておらず、2その重複検出作用域が利用可能であるすなわち、何らかの処理工程に用いられていない場合で、かつその場合にだけ、特定の探索層について作動可能とされる。先ず、抽象化ノードの動作カウンタは抽象化グラフ内に有する抽象化後続節点の数に設定され、これはそのときのレイヤ内の1以上の開放ノードを含む抽象化ノードについて果たすだけで済む。これらの抽象化ノードは、開放抽象化ノードと呼ばれる。他の全ての抽象化ノードについて、動作カウンタはゼロに設定される。未使用のビットが各演算子群に記憶させられ、そのときのレイヤについて後続節点を生成するのに演算子群を使い切っていないかどうか示す。利用可能なビットが各地演算子群に記憶され、重複検出作用域が利用可能かどうか指示する。包括的な動作積算カウンタは、そのときのレイヤ内の全てのノードを完全に拡張すべく適用する必要のある演算子群の総数の追跡を維持するのに用いられる。動作積算カウンタの値は抽象化グラフにおける全ての開放抽象化ノードの後続節点の数の総和として算出することができる。何故なら抽象化ノードの出次数はそれに写像するノードを完全に拡張すべく適用しなければならない演算子群の数に等しいからである。動作積算カウンタは、そのときのレイヤにおけるノードごとに後続節点の生成を演算子が果たしたときに、1だけ減数される。一旦動作積算カウンタがゼロを打つと、これが探索を新規レイヤに移動させるよう発信する。新規レイヤに移動することで、PePは全ての開放抽象化ノードについての下記の再初期化ステップを遂行する。1その動作カウンタをその出次数にリセットする。2その全ての演算子群に対し未使用ビットを設定する。3その全ての演算子群に対し利用可能ビットを設定する。4包括的な動作積算カウンタを再計算させる。次にどの演算子群を適用するかを決定するため、アルゴリズムはそのときのレイヤ用に1以上の作動可能な演算子群を有する開放抽象化ノードのリストすなわち、抽象化開放リストを維持する。開放抽象化ノードの動作カウンタがゼロに達すると、それは抽象化開放リストから除外される。抽象化ノードの動作カウンタは、1その演算子グラフの全てが後続節点の生成に用いられ、2その使用されていない演算子群のどれも利用可能な重複検出作用域を持たないという、2つの異なる理由からゼロに至ることがある。第1の場合には、抽象化ノードをそのときのレイヤについての抽象化開放リストから除外すべきである。第2の場合には、使用されていない演算子グラフの1つの重複検出作用域が利用可能となるや否や抽象化ノードを抽象化開放リスト上に戻すべきである。これら2つの場合を差別化すべく、アルゴリズムは未使用で利用可能なビットを下記の如く監視する。抽象化ノードの動作カウンタは、その演算子群の未使用ビットのいずれかがリセットされたときに歩進減数される。利用可能なビットが設定されると、同じ演算子群の未使用ビットが設定されている場合で、かつその場合に限り、動作カウンタは歩進増数させられる。換言すれば、抽象化ノードの動作カウンタはその未使用ビットと利用可能ビットの両方が設定されたその演算子群の数を計数する。したがって、同期メカニズムは被共有メモリの並列化用には単一ロックがありさえすればよい。包括的なミューテックスの首尾よきロック時に、探索処理工程は抽象化開放リスト上の抽象化ノードのいずれかから作動可能とされた演算子群を取り上げるが、それは正の動作回数を有するものだけがリスト上にあるからである。作動可能とされた演算子群が一旦選択されると、探索処理工程は選択されたものに干渉する全ての演算子群の利用可能なビットをリセットし、このことが一部の1または複数の抽象化ノードが抽象化開放リストから除外できるようにする。処理工程はロックを解放し、ロックが解放された後においても被選択演算子群の重複検出作用域におけるノードへの排他的アクセスが持てるよう保証することができる。その演算子群を用いてその処理工程を行なうときに、それはミューテックスを再度ロックし、それが以前リセットした利用可能ビット全てをセットし、このことが一部の1または複数のノードを抽象化開放リスト上に戻せるようにできる。抽象化グラフは原状態空間グラフの大きさに比べ極め小さいため、抽象化グラフに対し為される処理は効率的に行なうことができ、殆ど計算を必要としない。したがって、各処理工程は僅かな時間部分に対し包括的ミューテックスを保持し、その計算努力の大半をノード拡張に費やすだけで済む。大半の場合、エッジ分割はSDDよりも低速であり、何故ならそれはディスクRAM内に保存されたノードのスワップインアウト用により多くのディスク入/出力部を必要とするからである。純粋な内部メモリ探索にとっては、ディスク入/出力部は全く不要であり、興味を引く疑問点はエッジ分割をSDDよりも高速に出来るかにある。エッジ分割に関する従来の知恵は、それが純粋な構造重複検出よりも低速であるというものである。下記の実験に示される如く、これは事実でない。これらの実験結果をよりよく理解すべく、エッジ分割に有利に機能させることのできる効率因子を考察する。エッジ分割は、単一バケットのノードに対する探索アルゴリズムの重複検出作業に的を絞るものである。したがって、そのコードはより良質のメモリ基準局在性を呈し、より少ない保存ミスを有し、最新のプロセッサでのより高速のルーチン性能に繋がる。第2に、エッジ分割はノードの拡張時にどの演算子を適用できるかを特定する事前条件の照合に費やされる計算量の相当な節約をもたらす。特定ドメインソルバーと異なり、ドメイン非依存プランナの後続節点生成関数は問題の記述から自動的に抽出される。しかしながら、より汎用の後続節点生成器では、演算子集合は、特に根付け後に相当に大きくなることがある。下記の実験に用いられるプランナはコンパクトな状態表現に対し直接に前提条件試験を遂行するが、数百あるいは数千の演算子集合中の各個別の演算子の適用可能性を試験するのに依然相当の時間を要しうることが判っている。各エッジ分割は、どの演算子が適用可能かを特定するのに演算子テーブルの線形走査を遂行するとは限らない。エッジ分割は、状態抽象化の頂部で演算子抽象化を行なう。抽象化エッジy,y’については、エッジ分割は1抽象化ノードyに適用可能で、2抽象化ノードy’に写像するそれらの後続節点を生成するだけの演算子の集合Oy,y’を算出する。このことは、抽象化ノードyにおいて1つの演算子oが適用可能でない場合、そのときは全てのy’についてOy,y’内にoが存在しないことを意味し、それはエッジ分割が試験無しで演算子を安全に無視できることを意味する。先の15パズルの例では、空欄を抽象化ノードB0から右に移動させる演算子をエンコードする集合には、15個の演算子しか存在しない。空欄をB0からB4へ下方に移動させる演算子をエンコードする集合には、別の15個の演算子が存在する。したがって、抽象化ノードB0へ写像する状態については、試験する必要のある演算子の総数は30であり、15パズルの全状態空間に亙り規定された元々の720個の根付き演算子に比べ24分の1の低減となる。低減された演算子集合は、ととの和集合であり、抽象化ノードB0へ写像する15パズルの部分空間に設定された全演算子集合Oの射影として視認され、そのことが演算子集合を左上隅に位置する空欄を有する状態にて適用可能なものだけに制約する。各抽象化ノードに関する適用可能な演算子の数は、状態空欄抽象化の解像度が増大するのに合わせ減少し、したがって演算子抽象化の能力も減少する。図5は、PEPを用いた最終的な探索出力を取得する行為を示す。この線図には、グラフの抽象化表現の構築行為502と、抽象化ノードの重複検出作用域の分割行為504と、そのときの探索レイヤ内のノードの拡張行為506と、全ての演算子群を使い切ったときに次の探索レイヤに進むこと行為508が含まれる。本開示は、図5の行為あるいは事象の例示配列に限定はされない。グラフの抽象化表現は状態空間抽象化を用いて構築行為502され、これは概ねグラフに対する状態空間射影関数の適用を通じて構築され、ここでは状態空間射影関数は原状態空間から抽象化状態空間への多点-単点写像とされる。グラフの抽象化表現が一旦構築されると、その各抽象化ノードは重複検出作用域を含む。さらに、各抽象化エッジは演算子群を含んでいる。エッジ分割を用いることで、抽象化ノードの重複検出作用域はより小さな重複検出作用域に分割される行為504。より小さな検出作用域のそれぞれが、抽象化エッジの1つに対応する。好都合なことに、これらのより小さな抽象化検出作用域により、たとえグラフが固有の局在性を持たないときでもグラフの並列探索が可能になる。そのときの探索レイヤ内のノードを、拡張する行為506。ノードの拡張は、そのときの探索レイヤ内のノードを写像する抽象化ノードに属する演算子群の使用を通じて達成される。ノードは、全ての演算子群が使用されるまでこれらの演算子群を用いて拡張される。互いに素の重複検出作用域に関連する演算子群だけ任意の時点で使用する限り、ノードは並列に拡張することができる。グラフを探索している間、互いに素の重複検出作用域を有する演算子群は変化する。そのときの探索レイヤについて全ての演算子群を使い切ると、探索は次の探索レイヤへ進み、前述の行為が反復される行為508。この行為を含む上記した行為は、終了条件例えば、目的ノードに達するまで反復される。前述の行為間には、一時的な関係は必ずしも存在しない。むしろ、それらは同時並行的に発生し、多数回反復することができる。図6は、グラフの抽象化表現の構築行為602と、抽象化ノードの重複検出作用域の分割行為604と、そのときの探索レイヤ内のノードの拡張行為606と、全ての演算子群を使い切ったときに次の探索レイヤへ進むこと行為608とを含むPEPを用いた最終的な探索出力を取得する行為を示す。本開示は、図6の図示の順序の行為あるいは事象に限定はされない。グラフの抽象化表現は、状態空間抽象化を用いて構築行為602され、概ねグラフに対する状態空間射影関数の適用を通じて構築され、ここで状態空間射影関数は原状態空間から抽象化状態空間への多点-単点写像である。一旦構築されると、グラフの抽象化表現の各抽象化ノードには重複検出作用域が含まれる。グラフの外向性エッジは、グラフの抽象化表現に基づいて分割される行為604。分割には、1つの演算子群として抽象化表現の同じ抽象化エッジへ併せ写像するグループ分けエッジが含まれる。これらの演算子群により、たとえグラフが固有の局在性を持たないときでもグラフの並列探索が可能とされる。異なる演算子群すなわち、互いに素の重複検出作用域を有する演算子が、終了条件に合致行為606するまで処理装置に割り当てられる。処理装置は、これらの異なる重複検出作用域を用い、後続節点ノードを並列に生成する。後続節点ノードが生成されるのに合わせ、グラフを探索する行為608。そのときの探索レイヤ内の各ノードを試験し、それが探索規範に合致するか特定することができる。上記に記載した行為は、終端条件例えば、終端ノードに達するまで反復される。前述の行為間には、一時的な関係は必ずしも存在しない。むしろ、それらは同時並行的に発生し、何回となく反復することができる。図7は、PEPシステム700を示すものである。記憶装置とデジタルプロセッサを含むコンピュータや他のデジタル処理装置702は、システム700を組み入れている。他の実施形態では、システム700はデジタルプロセッサを含み、さらにデジタルデータ記憶装置へのアクセスを含むかもしくは有するサーバにより具現され、この種サーバはインターネットあるいはローカルエリアネットワークを介して適切にアクセスされる。コンピュータやデジタル処理装置702は例示キーボード704等の1以上のユーザ入力装置に作動的に接続され、制御システム700へのユーザ入力を受け取り、さらにシステム700の出力に基づき生成される出力を表示するディスプレイ706等の1以上のディスプレイ装置を含むか、あるいはこれに作動的に接続される。他の実施形態では、システム700への入力はコンピュータ702上のシステム700よりも先にあるいは同時並行的に実行し、もしくはネットワーク接続からの別のプログラムから受け取る。システム700は、PEPを遂行するPEPモジュール708を含む。PEPモジュール708は、モジュール708外部のソースからグラフを受け取り、PEPを実行する。外部ソースは、例えばコンピュータ702あるいはコンピュータ702のユーザが記憶するファイルとすることができ、ここではユーザはキーボード704を介してPEPモジュール708と相互作用する。実施形態では、PEPモジュール708はPePを実行するための実行可能な命令を記憶する記憶媒体例えば、デジタルプロセッサにより具現される。記憶媒体には、例えば、磁気ディスクや他の磁気記憶媒体、光ディスクや他の光学式記憶媒体、ランダムアクセスメモリRAMやリードオンリーメモリROMや他の電子記憶デバイスやチップあるいは作動的に相互連結されたチップ群、記憶する命令をインターネットあるいはローカルエリアネットワークを介して検索することのできるインターネットサーバを含めることができる。図8は、図7のPEPシステムの一つの実用的なアプリケーションを例証する印刷システム800を示す。システム800は、給送器802、マーキング印刷エンジン804、方向転換器あるいは反転器806、仕上げ器、出力トレイ808等を含む197個の独立モジュールを含む。モジュールは一丸となって動作し、様々な印刷製品を生み出す。PEPは、印刷エンジン804全体に印刷ジョブの分散をプラニングするすなわち、プラニング問題を解くのに適している。例えば、PEPは幾つかの印刷エンジン804を内部配置できる点を考慮し、給送器802から出力トレイ808まで最短の経路を見いだすことができる。PEPは、遅れを最小化すべく印刷ジョブをスケジューリングするのにも用いることができる。プラニング問題をグラフに写像するのに、システム状態はグラフのノードとして取り扱われ、システム状態間の関係はグラフのエッジとして取り扱われる。エッジの重みは、時間や距離やコスト等とすることができる。プランは、そこでシステム状態の一構成を含む。グラフ探索を用いて他システム内にPEPシステムが採用できることも、理解されたい。例えば、PEPシステム700は、別の選択肢として経路プラニングシステムおよび/または方法にて用い、2つの位置間で最短かつ最速の経路を見いだすことができる。その下敷きとなる探索アルゴリズムとして幅優先ヒューリスティック探索を用いるドメイン非依存STRIPSプランナ内に、PEPを実験的に実装した。探索アルゴリズムが、順方向状態空間プラニングを用い、許容可能なパターンデータペースによりヒューリスティックに誘導される最適な一連のプラニングを見いだす。プランナは、隔年プラニング競争に基づき8個のベンチマークドメインにて試験した。実験に用いた全てのプランナは、C言語にて実装し、gccを用いて同一の最適化レベルにてコンパイルしたものである。実験は、大まかには2GBのRAMに制限された3.0GHz版のデュアルクワッドコアインテルキセノンX5450プロセッサ上で行なった。少なくとも2つの理由から、単に並列高速化比を根拠に、幅優先探索ヒューリスティックアルゴリズムと最良優先探索アルゴリズムとを比較することは公平ではない。理由1:ヒューリスティック探索への最良優先手法ではなく幅優先ヒューリスティック探索を用いる下敷きとなる理論的根拠は、前者が後者よりも小さな探索最前線を誘発する点にある。この種の差異は、ヒューリスティック探索がより正確になるにつれ増大する。最前線すなわち、オープンリストは探索アルゴリズムの作業負荷のスナップショットとして見ることができるため、Aはより少ない開放ノードを用いて作業することを強制される幅優先ヒューリスティック探索よりも多量の処理作業を場合によっては同時並行的に有する当然の利点を有する。理由2:本願明細書に記載する幅優先ヒューリスティック探索の並列版は、レイヤ準拠同期を用いてメモリを節約するものである。したがって、探索スレッドはそれらがレイヤの端部に接近するにつれ飢餓状態となる可能性が高くなる。HDAとPBNFは、他方で影響を受けない。何故ならそれらはレイヤに準拠しないからである。PEPと異なり、メモリ要件は使用するスレッドの数に合わせ増大させることができる。これらの欠点にも拘わらず、実験はPEPが好都合なことに全てのスレッドについて他の全てのアルゴリズムに比肩することを示すものである。唯一の例外は、生成されたノードの数を上回るより多くの歩進的拡張をPEPが必要とするブロック-10である。図9は、PSDDの性能とPEPの性能とを比較するテーブル900を含む。これらの問題は、2GBのRAM内で解くことのできる8個のドメインのそれぞれで最大となる。テーブル900は、PEPが全ノード拡張を必要とするPSDDを平均で1桁は上回る歩進的ノード拡張を必要とし、しかも依然として相当に高速であり、PEPはPSDDよりも粗い抽象化機能と共に等しくあるいはより優れて効果的とすることができる。平均して、PEPに使用する抽象化グラフ欄内にとして標識付けして図示の大きさは、PSDD内のそれの1/10を下回る。PEPは、64個ほどの少数の抽象化ノードを用いて抽象化グラフに対し十分な同時並行性を梃入れすることができる。PSDDあるいはPBNFがその小ささの抽象化グラフを用いた場合、その実際のCPU内クロックによらない実行時間はテーブル900内に提示されたものよりも相当に劣化する筈である。図10は、同じプラニング問題集合についてのHDAとPBNFライブロック無縁版のルーチン性能を示すテーブル1000を含むものである。全てのアルゴリズムは、同じCコードで計算する同じ容認可能なヒューリスティック法を用いた。テーブル1000は、HDAとPBNFが幅優先ヒューリスティック探索よりもメモリ効率が劣るものであり、それらがPEPよりも相当に低速で実行されることを示すものである。PBNFは、2スレッドではなく7スレッドを用いるサテライト-5上でメモリを使い切ってしまった。PEPと異なり、PBNFのメモリ要件は使用するスレッドの数に合わせ増大させることができる。サテライト-5については、RAMが記憶するノードのPBNFピーク数が1,2,4の各スレッドについて大まかには1600万,3200万,5400万個のノードとなる。PEPは、STRIPSプラニング問題として定式化された15パズルのハードインスンタス上でも実行させた。図11のテーブル1100に示すインスタンスは、Korfの100個の15パズルインスタンスを標識付けした欄がインスタンス番号を示すの中でも最も難しい10個に含まれる。以前は、最良ドメイン非依存ソルバーは数時間でそれらのうちの93個を解くことが出来た。しかしながら、PEPはドメイン非依存パターンデータベースをヒューリスティックに用い特定ドメインソルバー向けのヒューリスティックなマンハッタン距離と等価、数分でそれらのうちの95個を解くことが出来る。表1100内のどのインスンタスもHDAあるいはPBNFでは解くことは出来ない。何故なら両方ともインスンタスが一つでも解けるよりも相当前にメモリを使い切ってしまうからである。"