(57)【特許請求の範囲】
【請求項１】
並列グラフ探索方法であって、
状態空間抽象化を用いてグラフの抽象化表現を構築する工程で、前記グラフの抽象化表現が重複検出作用域を有する１以上の抽象化ノードと演算子群を有する１以上の抽象化エッジとを含む工程と、
エッジ分割を用いて前記抽象化ノードの前記重複検出作用域をより小さな重複検出作用域に分割する工程で、前記抽象化エッジを用いて前記より小さな重複検出作用域を規定する工程と、
ノードを写像する前記抽象化ノードの外向性抽象化エッジの演算子群を用いてそのときの探索レイヤ内のノードを拡張する工程で、前記拡張が互いに素の前記重複検出作用域を有する前記抽象化エッジに関連する演算子群を用いて前記ノードを並列に拡張し、前記拡張が処理装置により行なわれる工程と、
そのときの探索レイヤ内の全ての演算子群を前記ノードの拡張に使い切ったときに次の探索レイヤに進む工程と、
を含み、
前記エッジ分割は、前記抽象化ノード（ｙ）の適用可能な演算子集合（Ｏｙ）を、演算子群（Ｏｙ，ｙ’）に分割することを含み、
前記抽象化ノード（ｙ）の各後続節点に１つの演算子群（Ｏｙ，ｙ’）が対応するように、前記演算子集合（Ｏｙ）が分割され、
前記演算子群（Ｏｙ，ｙ’）は、前記抽象化エッジ（ｙ，ｙ’）に関連する全ての演算子からなる前記適用可能な演算子集合（Ｏｙ）の部分集合であり、
前記拡張する工程では、前記そのときの探索レイヤのための１以上の作動可能な演算子群を有する抽象化ノードのリストを維持し、
前記演算子群が前記そのときの探索レイヤにおいて拡張のために用いられておらず且つ前記演算子群の前記重複検出作用域が現に使用されていない場合、前記演算子群が作動可能であり、
前記拡張のために用いられる前記演算子群は、前記リストから選択される、
方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本例示実施形態は、概ねグラフ探索アルゴリズムに関する。
【図面の簡単な説明】
【０００２】
【図１】探索グラフの一部を示す。
【図２】「８パズル」パネルを示す。
【図３】エッジ分割を示す。
【図４】３個の歩進ノード拡張ステージを示す。
【図５】最終探索出力を取得する行為を示す。
【図６】最終探索出力を取得する基本行為を示す。
【図７】並列エッジ分割を具現するシステムを示す。
【図８】モジュール式印刷エンジンを示す。
【図９】実験結果を示す。
【図１０】実験結果を示す。
【図１１】実験結果を示す。
【発明を実施するための形態】
【０００３】
下記は、エッジ分割を用いた並列グラフ探索アルゴリズムを記述するものであり、状態空間抽象化を用いた構造化された重複検出の上に組み立てられるものである。エッジ分割は局在性を抽象化し、並列ノード拡張を可能にする。アルゴリズムは、探索グラフの本来の局在性に依存しない。エッジ分割を用いて探索グラフの演算子集合を細分することで、アルゴリズムは固有の局在性を持たないグラフから局在性を抽出する。
【０００４】
構造化重複検出（ＳＤＤ）はグラフ内の局在的構造を梃入れし、内部メモリとディスク間で記憶ノードを分割する。重複検出は、ノード拡張期間中に遂行することができる。局在的構造は、状態空間抽象化の使用を通じて明らかにされる。
【０００５】
状態空間抽象化は、状態空間グラフを状態空間投影関数の使用を介して生成される抽象化状態空間グラフに抽象化するものであり、この関数は原状態空間から、各抽象化状態（すなわち抽象化ノード）が原状態空間内の状態群（すなわち、ノード）に対応する抽象化状態空間への多点−単点写像である。状態空間射影関数は、一部状態変数を無視することで作成される。
【０００６】
所与の状態空間グラフと状態空間射影関数が与えられると、下記の如く抽象化状態空間グラフを構成することができる。抽象化グラフ内の抽象化ノードと呼ばれるノード集合は、抽象化状態の集合に対応する。抽象化ノードｙ’は、原状態空間内に２つの状態ｘ’とｘが存在し、（ｉ）ｘ’がｘの後続節点であって、（ｉｉ）状態空間射影関数の下でｘ’とｘがそれぞれｙ’とｙに写像される場合で、かつその場合にのみ、抽象化ノードｙの後続節点となる。１つの状態ｘが抽象化状態ｙへ写像されると、そのときｙはｘの画像と呼ばれる。
【０００７】
図２の８パズル２０内の全ての駒の位置を無視し、「空欄」位置だけ考える場合、９個の抽象化状態（Ｂ０〜Ｂ８）で、１つの状態が空欄の各可能な位置に対応する抽象化状態空間グラフ２２が得られる。この状態空間射影機能により作成される抽象化状態空間グラフ２２は、空白位置にのみ基づき１つの状態を抽象化状態に写像する。各抽象化ノードＢｉは、８パズル２０の位置ｉに位置する空欄を有する状態集合に対応する。
【０００８】
ＳＤＤでは、原探索グラフ内の記憶ノードは「ｎ個のブロック」に分割されており、ここでｎ個のブロックは同じ抽象化ノードに写像されるノード集合に対応する。この分割された記憶ノードが与えられると、ＳＤＤは重複検出作用域の概念を用いて記憶基準を局在化する。原探索群内のノードｘの重複検出作用域は、射影関数の下でのノードｘの画像である抽象化ノードｙの後続節点へ写像する全記憶ノード（あるいは等価的にｎ個全てのブロック）として規定される。
【０００９】
重複検出作用域により、探索アルゴリズムは記憶ノードの一部分に対する重複の照合と、さらに全ての重複物が発見されることを保証できるようになる。外部メモリグラフ探索アルゴリズムはＲＡＭを用い、そのときの重複検出作用域内にｎ個のブロックを記憶させ、ＲＡＭが満杯であるときは他のｎ個のブロックの記憶にディスクを用いる。ＳＤＤは、幅優先探索等のノード集合を一度に拡張する探索アルゴリズムを用いて使用され、ここで群中のノードを拡張する順序はディスク入／出力部を最小化するよう調整することができる。ディスク入／出力部を最小化するＳＤＤの戦略は、重複検出作用域の変化ができる限り低頻度で行なわれ、できる限り少数のブロックの変化が含まれるようノード拡張に指示するものである。ＲＡＭが満杯であるときは、そのときの重複検出外部のｎ個のブロックはディスクに全て吐き出される。ノードを異なるｎ個のブロック内で拡張するときは、ディスクに記憶させたその重複検出作用域内のあらゆるブロックをＲＡＭへスワップする。
【００１０】
ドメイン非依存ＳＴＲＩＰＳプラニングについては、ＳＤＤが使用する状態空間射影関数を自動的に作成し、各プラニングドメインの探索グラフに適合させる。
【００１１】
並列構造重複検出（ＰＳＤＤ）は、外部メモリグラフ探索内のメモリ基準を限局化するのに用いる同一の局在的構造に梃入れし、並列グラフ探索に必要な同期処理の回数を低減するＳＤＤの拡張である。ＰＳＤＤでは、グラフ探索は各アイドルプロセッサにｎ個の拡張対象ブロックを割り当てることで並列化し、抽象化グラフを用いその重複検出作用域が対関係において互いに素であるｎ個の拡張対象ブロックを見いだすものである。何故ならそれらは同期（すなわち、ロック）無しで並列に探索できるからである。２つの重複検出作用域は、それらがｎ個のブロックを全く共有しない場合は互いに素であり、したがって拡張ブロックの重複検出作用域が対関係において互いに素であるという条件がメモリ基準の局在性を保証する。
【００１２】
処理工程間の同期は、１つの処理工程がそのときのｎ個のブロック内の全てのノードの拡張を終了し、新たなｎ個のブロックの取得が必要となった後でのみ必要となる。ｎ個のブロックｂは、後続節点が全く使用されていない（すなわち、その重複検出作用域がそのときのｎ個の拡張ブロックの重複検出作用域とは互いに素である）場合で、かつその場合にのみ、１つの処理工程に自由に割り当てられる。ｎ個の自由ブロックはσ（ｂ）、すなわち別の処理工程により使用されているｂの後続節点間のｎ個のブロックの数を系統立って追跡することで見いだされる。ｎ個のブロックは、そのσ＝０であるときにのみ取得することができる。したがって、ＰＳＤＤは単一ロックを用い、抽象化グラフの操作を制御するだけでよく、それは探索対象である新規のｎ個の自由ブロックを見いだすときにだけ処理工程が取得する。
【００１３】
ＳＤＤの適用可能性は、抽象化群の作成に用いる状態空間射影関数が原探索グラフ内の局在的構造を捕捉するかどうかに依存する。多くのプラニング問題がＳＤＤにより梃入れすることのできる局在的構造を有するが、この種の局在的構造が所与の問題に対し存在する保証は皆無である。エッジ分割は、この問題を解決し、探索グラフが見掛け上は局在的構造を持たないときですらメモリ基準を局在化できるよう保証するＳＤＤを機能強化したものである。
【００１４】
エッジ分割時に、ｎ個のブロックの重複検出作用域は抽象化グラフ内の全ての後続節点のｎ個のブロック群としてはもはや規定されず、代りに、抽象化グラフ内の具体的な外向性エッジに沿った単一の後続節点のｎ個のブロックとして規定される。エッジ分割を用いることで、ｎ個のブロック内のノードは歩進的に拡張される。各段において異なる抽象化エッジに対応する演算子群が適用され、演算子群の全ての演算子が他の任意の演算子群を検討する前にｎ個のブロック内の各ノードに適用される。次に、異なる外向性抽象化エッジを検討し、異なる演算子群を同じノード集合に適用する。その結果、全ての演算子群がｎ個のブロックのノードに適用され、ノードは完全に拡張される。ノードの全拡張には、一連の歩進的拡張が要求される。
【００１５】
図３は、エッジ分割を示すものである。そこには、Ｋ４抽象化グラフ３０（すなわち、４個のノードを有する完全連結抽象化グラフ）が図示されており、ここでは抽象化ノード３２（二重円で図示）へのノードの写像は左側から右側にかけて歩進的に拡張される。左側から右側へ追うことで、抽象化ノード３２へのノード写像は抽象化ノード３２と３４とを連結する抽象化エッジに関連する演算子群を用いて拡張される。抽象化ノード３２へのノード写像は、抽象化ノード３２と３６とを連結する抽象化エッジに関連する演算子群を用いて拡張される。最後に、抽象化ノード３２へのノード写像が抽象化ノード３２と３８を連結する抽象化エッジに関連する演算子群を用いて拡張される。各拡張ステージでは、重複検出作用域は単一の抽象化ノードだけを包含する。すなわち、関連する抽象化エッジの目的地へのノード写像である。
【００１６】
エッジ分割は、ＳＤＤを用いた外部メモリグラフ探索の性能改善に用いられてきた。各ブロック内のノード集合がＲＡＭ内に適合する限り、エッジ分割を用いるＳＤＤは抽象化グラフが局在的構造を捕捉するか否かに拘わらず効果的である。エッジ分割は、外部メモリグラフ探索の内部メモリ要件を低減し、拡張性を改善する。
【００１７】
「演算子」は、インスタンス化された（すなわち、根付き）演算子である。例えば、８パズルは、たとえインストール前はたった４個（左右上下）の演算子しかなくとも、全部で１９２個の根付き演算子を有する。
【００１８】
エッジ分割における演算子のグループ分けは、状態抽象化の頂部に構築される。Ｏを、探索問題のインスタンス化された全ての演算子の集合とする。（ｉ）ｏがｘに適用可能で、（ｉｉ）ｘがｙへ写像されるよう原状態空間内に状態ｘが存在する場合で、かつその場合にだけ、演算子ｏ∈Ｏは抽象化ノードｙに適用可能である。８パズルについて考える。空欄はパズル盤の左上隅に位置するときに右（Ｂ０→Ｂ１）または下（Ｂ０→Ｂ３）のいずれかへ移動させることができ、８パズルのどの駒を空欄位置へ移動させるかに応じて各移動が８個の異なるインスタンス化を有するため、抽象化ノードＢ０に適用可能な２×８＝１６個の演算子が存在する。同様に、各抽象化ノードＢ２，Ｂ６，Ｂ８は１６個の適用可能な演算子を有する。抽象化ノードＢ１，Ｂ３，Ｂ５，Ｂ７はそれぞれ３×８＝２４個の適用可能な演算子を有し、抽象化ノードＢ４は４×８＝３２個の適用可能な演算子を有する。したがって、Ｂ０＝１６，Ｂ１＝２４，Ｂ２＝１６，Ｂ３＝２４，Ｂ４＝３２，Ｂ５＝２４，Ｂ６＝１６，Ｂ７＝２４，Ｂ８＝６であり、これらが１９２個の根付き演算子となる。
【００１９】
各抽象化ノードの適用可能な演算子集合が一旦特定されると、演算子のグループ分けは各適用可能な演算子ごとにそれが関連する抽象化エッジを識別する。抽象化エッジ（ｙ，ｙ’）は、ｙ’がｙの後続節点である場合、その場合に限り、一対の抽象化ノードｙ，ｙ’を連結する抽象化グラフ内のエッジである。ここから先は、ｙ（ｙ’）を抽象化エッジ（ｙ，ｙ’）の始点（終点）と呼ぶ。
【００２０】
さらに、Ｏｙは抽象化ノードｙに適用可能な演算子集合となる。演算子ｏ∈Ｏｙは、原状態空間内に２つの状態ｘ，ｘ’が存在し、（ｉ）ｏがｘに適用可能で、（ｉｉ）ｘ’がｏをｘに適用した後の生成状態であり、（ｉｉｉ）ｘとｘ’がそれぞれｙとｙ’に写像される場合で、かつその場合にだけ、抽象化エッジ（ｙ，ｙ’）に関連付けられる。決定的効果を有する演算子については、各ｏ∈Ｏｙごとに、ｏに関連付けることのできる固有の抽象化エッジ（ｙ，ｙ’）が存在する。事実上、演算子空間から抽象化エッジ空間へは多点−単点写像が存在する。
【００２１】
演算子空間内で局在的構造を開拓するため、エッジ分割は抽象化ノードｙについて適用可能な演算子集合Ｏｙを、抽象化グラフ内のｙの各後続節点に１つずつ演算子群に分割する演算子グループ分けを用いる。演算子群Ｏｙ，ｙ’は、抽象化エッジ（ｙ，ｙ’）に関連する全ての演算子からなるＯｙの部分集合である。全てのｙ’≠ｙ”について、Ｏｙ，ｙ’∩Ｏｙ，ｙ”＝Φであり、かつ
【数１】
0006021305.tif 000002
であることに留意されたい。なお、後続節点（ｙ）は抽象化グループ内のｙの後続節点集合である。
【００２２】
演算子グループ分けは本願明細書では暗示表現されたグラフ（開始状態と後続節点生成用演算子集合により表わされるグラフ）の探索文脈で提示されているが、同じ技法は僅かな修正をもって明示的に表現されたグラフ（頂点群とエッジ群とで表わされるグラフ）に適用される。
【００２３】
並列エッジ分割（ＰＥＰ）は、並列グラフ探索の目的に合わせ局在性を抽出すべく、状態空間抽象化とエッジ分割の概念の上に構築される。それは、共有メモリと分散メモリの両方の並列化に用いることができる。簡単化するため、この後の説明は分散メモリ並列化における通信オーバーヘッドではなく共有メモリ並列化における同期オーバーヘッドを低減するこの手法を使用することだけに言及するものとする。何故なら両方の並列設定について原理は同じままだからである。
【００２４】
ＰＥＰは、重複検出作用域の低減がそのときの探索処理工程間の競合度を低減し、それによって並列探索において許容される同時並行度を増大させるものと認識している。並列探索の最大の同時並行性の正式な定義が、下記である。
【００２５】
定義１：並列探索の最大の同時並行性は、その処理工程において同時並行ノード拡張に同期が一切不要となるよう探索期間中に許容される並列処理の最大数である。
【００２６】
補助定理１：ＰＳＤＤの最大の同時並行性は、抽象化状態空間グラフの互いに素の重複検出作用域の最大数である。
【００２７】
上記の補助定理は、それをエッジ分割と組み合わせて使用するか否かに拘わらず、ＰＳＤＤに当てはまる。しかしながら、エッジ分割は重複検出作用域の定義を変更し、同じ抽象化状態空間グラフに見いだすことのできる互いに素の重複検出作用域の数を増大させるため、エッジ分割は最大の同時並行性を増大させる。
【００２８】
定義２：状態空間射影関数Πの下での抽象化エッジ（ｙ，ｙ’）に関する１つのノードｘのエッジ分割された重複検出作用域は、抽象化ノードｙ’に写像される記憶ノード集合に対応する。
【００２９】
抽象化エッジ（ｙ，ｙ’）に関する重複検出範囲は、下記を包含するよう保証されている。すなわち、
１）単一の抽象化ノードｙ’（抽象化エッジの終点）へ写像されるノードのみと、
２）演算子群Ｏｙ，ｙ’を抽象化ノードｙ（抽象化エッジの始点）へ写像するノード集合に適用することで生成されるこれらの後続節点に関する全ての潜在的な重複
とであり、ここで演算子群Ｏｙ，ｙ’はＯｙの部分集合、すなわち抽象化エッジ（ｙ，ｙ’）に関連する全ての演算子で構成される抽象化ノードについての適用可能な演算子ｙの集合である。
【００３０】
上記特性が、エッジ分割がＲＡＭ内に単一のｎ個のブロックのノードを記憶させるだけで済むことを保証し、その一方で最悪の場合に生ずる全ての重複を捕捉するよう保証する。この訴えは、全てがＲＡＭ内に適合する内部メモリ探索の文脈に維持される。
【００３１】
定理１：ＳＤＤ（エッジ分割を用いない）の下での互いに素の重複検出作用域の最大数は、抽象化グラフの最小出次数により除算した抽象化状態空間グラフの大きさ
｜抽象化グラフの大きさ／抽象化 グラフの最小出次数｜    （２）
により制限される。
【００３２】
証明：最小出次数を有する抽象化ノードは、最小数の後続節点を有し、そのことが片や（ブロック数の点で）最小の重複検出作用域を生み出す。抽象化グラフが、互いにｋの素の作用域に分割できると仮定する。同じ抽象化ノードを２以上の作用域内に出現させることはできないため、その値ｋは最小の作用域の大きさで除した抽象化の総数、あるいは等価的には最小の出次数を上回ることはできない。
【００３３】
全ての実用目的にとって、最小の出次数は定理１の使用時に抽象化グラフの平均出次数により置き換えねばならないが、稀な事例では、このことが真の最大同時並行性を過小評価することがある。
【００３４】
推論１：（エッジ分割を用いない）ＰＳＤＤの最大の同時並行性は、抽象化グラフの最小の出次数により除した抽象化状態空間グラフの大きさにより制限される。
【００３５】
推論２：完全に連結された抽象化状態空間グラフに対する（エッジ分割を用いない）ＰＳＤＤの最大の同時並行性は、１である（すなわち、同時並行性は皆無である）。
【００３６】
上記の２つの推論は、補助定理１と定理１に直接的に従属する。推論２によれば、ＰＳＤＤはそれが完全に連結されている場合、抽象化グラフ（および対応する探索グラフ）の並列出力を抽出するその能力を喪失し、許容される最大の同時並行性は、ノード拡張の全ての同期無縁期間を保証する必要がある場合に、単一の探索処理工程としかならない。
【００３７】
図１では、完全に連結された抽象化グラフとの問題は、全ての重複検出作用域がグラフ全体を使い尽くす筈である点にあり、それは互いに素の作用域の存在を排除する。しかし、エッジ分割を用いることで、重複検出作用域は単一バケットのノード（すなわち、ｎ個のブロック）しか含まず、一方でソースバケットの抽象化エッジに写像されるノードの拡張時に一切の同期が必要でなくなることが依然として保証される。複数の探索処理工程は、生成することのできる後続節点が全てソースバケット以外の異なるバケットに写像される限り、同じソースバケット内でノードを拡張することができる。
【００３８】
定理２：エッジ分割下の互いに素の重複検出作用域の（最大）数は、抽象化状態空間グラフの大きさである。
【００３９】
推論３：並列エッジ分割の最大の同時並行性は、抽象化状態空間グラフの大きさに等しい。
【００４０】
どのようなノードのエッジ分割重複検出作用域も常に単一のバケットであるとの特性が与えられると、これらは直接的な結果となる。それらはエッジ分割を用いないＰＳＤＤについての類似の結果よりも有意味でもある。何故ならそれらは互いに素の作用域の厳密な（最大の）数を明らかにし、これらの数に上限を設定するだけの定理１や推論２とは異なるからである。
【００４１】
定理３：所与の状態空間射影関数にとって、任意の並列探索アルゴリズムの最大の同時並行性は、重複が生成されるや否や検出しなければならない場合、抽象化状態空間グラフの大きさにより制限される。
【００４２】
証明：抽象化グラフの大きさをｋとし、さらに並列探索の最大の同時並行性がｋを上回るものと仮定する。一般性を喪失することなく、他のｋ番目の処理工程を同期を用いることなく合体させることのできる（ｋ＋１）番目の処理工程を想定する。重複はそれらが生成されるや否や捕捉しなければならないため、このことは（ｋ＋１）番目の処理工程にその重複検出作用域への排他的アクセスを与えねばならないことを意味し、それは少なくとも１つの抽象化ノードを使い尽くすものである。しかし、抽象化ノードしか存在しないため、分類棚の原理に従い、２つの処理工程により共有される１つの抽象化ノードが存在しなければならず、それらは互いに同期して重複検出を同時に遂行しなければならない。このことは、（ｋ＋１）番目の処理工程をしてはならず、代りに定理を当てはめねばならないことを証明する矛盾に通ずる。
【００４３】
定理３では、ＰＥＰは最適であり、何故なら他のアルゴリズムは、重複検出し損なったり、状態空間射影関数を変更したり、そのいずれもすることなく、より高いレベルの最大の同時並行性を全く獲得できないからである。全ての並列探索アルゴリズムが低解像度の同一の状態空間射影関数を用いるよう強いられる場合、ＰＥＰを簡単に全ての中で最良のものにできるため、定理３はまた我々の計算実験のセットアップを教示するものでもある。したがって、下記の実験に使用される各個別のアルゴリズムに最も適した射影関数が用いられる。
【００４４】
ＰＥＰは、下記の如く要約することができる。各探索レイヤに、その中の非干渉演算子群を全ての演算子群が適用されるまで複数の処理装置へ分散させる。非干渉演算子群選択用の規範とは、一方の演算子群が生成する後続節点群は他方の演算子群が生成するものと重複しえないことが保証されているからため、２つの演算子群が同一の終点抽象化状態を共有する限り、それらは並列ノード拡張期間中に同期（あるいは通信）を用いることなく同時に使用できることである。したがって、各処理装置は重複検出に局在的に（すなわち、単一の抽象化状態内で）的を絞りさえすればよく、包括的な重複検出態様はＰＥＰにより同期とは無縁の仕方で取り扱われる。
【００４５】
図４中、抽象化グラフの３個の歩進ノード拡張ステージがＰＥＰに従って図示してある。３個の歩進ノード拡張ステージは、図１に示す３個の隠れ状態を有する隠れマルコフモデルの特性を呈する抽象化グラフを拡張するものである。図１との１つの差異は、図４の各ノードが具体的な状態群（ＨＭＭではこれらは隠れ状態にある）を表わす抽象化状態にある点にあり、したがって各ノードは下位の場合の「ｓ」に代えて大文字「Ｓ」を用いて標識付けしてある。したがって、１つの抽象化状態が１０００個の具体的状態に対応する場合、そのときは図４に示した問題は図１のものよりもほぼ３桁は大きな大きさとなる。ＰＥＰは大きな問題を解くべく設計されているため、その効率は概ね探索問題の大きさに合わせて増大する。
【００４６】
図４では、抽象化状態Ｓ０，Ｓ１，Ｓ２に写像するノードは、後続節点の生成に用いられる演算子群が互いに干渉しない場合、並列に拡張することができる。演算子群は、２個の演算子群が同一の終点抽象化状態（すなわち、重複検出作用域）を共有しない限り、干渉はしない。ステージ４０２を手始めに、複数の処理装置が時刻ｔｉに抽象化状態Ｓ０，Ｓ１，Ｓ２に写像するノードを歩進拡張する。処理装置は、抽象化状態Ｓ０を自らに連結する抽象化エッジに関連する演算子群を用いて抽象化Ｓ０に写像するノードを拡張する。他の処理装置の同様に、抽象化状態Ｓ１とＳ２を拡張する。ステージ４０４と４０６において抽象化状態Ｓ０，Ｓ１，Ｓ２に写像するノードをさらに拡張するよう、異なる演算子群を選択して用いる。１つの演算子群を用いて抽象化状態に写像する全てのノードを拡張した後、全ての演算子群が用いられるまで別の演算子群を選択する。１つのノードの後続節点が全てノードの拡張時に（並列）エッジにより生成されるとは限らないため、エッジ分割におけるノード拡張は歩進的な拡張となる。一旦全ての適用可能な演算子群が適用されると、ノードは結果的に全て拡張される。
【００４７】
ＰＥＰ効率は、幾つかの因子により影響を受けることがある。一つは負荷バランスであり、それは状態空間抽象化を用いる並列探索への手法に関連するものである。静的な状態空間射影関数はバケットに対しノードを均一に分散させることは出来ない。何故なら一部のバケットは大半のノードを収容するが、その他のバケットはノードを全く持たないからである。下記に説明する実験では、全てのアルゴリズムに対し静的な射影機能を用い、負荷バランス問題に対処する能力を試験した。ＰＥＰだけでは負荷バランス問題は解決しないが、それは問題を程々のものにすることができる。同一資源のバケットはＰＥＰ内の複数の処理工程により拡張することができ、すなわちバケットが相当に大きくなると、アルゴリズムは複数の処理工程が同一のバケット上で機能するよう、大きなタスクをより小さな部分に分割するのと等価に、各適用可能な演算子群ごとに１つずつ割り当てることができ、より多くの部分があるほど、全ての探索処理工程をビジー状態に保つことのできる可能性が高くなる。
【００４８】
どのような並列アルゴリズムについても、設計義務はデットロックの不在を証明することにある。ＰＥＰにとって証明は簡単である。何故ならそれはデットロックに対する４個の必要条件、すなわち（１）相互排除、（２）保持待機、（３）専占無し、（４）循環待機のうちの１つを乱すからである。ＰＥＰでは決して満たされない条件は「保持待機」である。何故なら一旦探索処理工程が抽象化エッジの重複検出作用域である単一バケットのノード（すなわち、単位資源）の保持を取得すると、ノード拡張と共に前進する必要のある全てを手にし、デットロックが発生する期間を待機することは皆無となるからである。ＰＥＰは、設計によりデットロック無しであるため、それはデットロック検出あるいはデットロック回避用のオーバーヘッドを全く持たない。
【００４９】
ＰＥＰは同じ演算子群を歩進拡張に使用する限り、同期は一切必要ないことを保証するが、処理装置が１つの演算子群から別のものへ切り替わるときや、あるいは探索が１つの探索レイヤから次へ移行するときに、一部の軽量の同期が必要になることがある。そのときのレイヤから次へ探索を移動させる方法だけでなく、演算子群を処理装置に割り当てる複数の方法もまた存在する。他のものを用いることができるが、本願明細書では単一ロック方式（以下、単一ロック並列エッジ分割と呼ぶ）を説明する。より精細な複数ロック方式等の追加の方式が、並列エッジ分割に等しく適用可能である。
【００５０】
単一ロックＰＥＰは、下記のデータ構造を記憶する、すなわち、
・作動可能とされた演算子群の動作カウンタを、そのときの探索レイヤについてのその作動可能とされた演算子群の数の追跡を維持する各抽象化ノードに記憶させる。演算子群は、（１）そのレイヤについて後続節点を生成するのに用いられておらず、（２）その重複検出作用域が利用可能である（すなわち、何らかの処理工程に用いられていない）場合で、かつその場合にだけ、特定の探索層について作動可能とされる。先ず、抽象化ノードの動作カウンタは抽象化グラフ内に有する抽象化後続節点の数に設定され、これはそのときのレイヤ内の１以上の開放ノードを含む抽象化ノードについて果たすだけで済む。これらの抽象化ノードは、開放抽象化ノードと呼ばれる。他の全ての抽象化ノードについて、動作カウンタはゼロに設定される。
・未使用のビットが各演算子群に記憶させられ、そのときのレイヤについて後続節点を生成するのに演算子群を使い切っていないかどうか示す。
・利用可能なビットが各地演算子群に記憶され、重複検出作用域が利用可能かどうか指示する。
・包括的な動作積算カウンタは、そのときのレイヤ内の全てのノードを完全に拡張すべく適用する必要のある演算子群の総数の追跡を維持するのに用いられる。動作積算カウンタの値は抽象化グラフにおける全ての開放抽象化ノードの後続節点の数の総和として算出することができる。何故なら抽象化ノードの出次数はそれに写像するノードを完全に拡張すべく適用しなければならない演算子群の数に等しいからである。動作積算カウンタは、そのときのレイヤにおけるノードごとに後続節点の生成を演算子が果たしたときに、１だけ減数される。一旦動作積算カウンタがゼロを打つと、これが探索を新規レイヤに移動させるよう発信する。
【００５１】
新規レイヤに移動することで、ＰｅＰは全ての開放抽象化ノードについての下記の（再）初期化ステップを遂行する。
１）その動作カウンタをその出次数にリセットする。
２）その全ての演算子群に対し未使用ビットを設定する。
３）その全ての演算子群に対し利用可能ビットを設定する。
４）包括的な動作積算カウンタを再計算させる。
【００５２】
次にどの演算子群を適用するかを決定するため、アルゴリズムはそのときのレイヤ用に１以上の作動可能な演算子群を有する開放抽象化ノードのリスト（すなわち、抽象化開放リスト）を維持する。開放抽象化ノードの動作カウンタがゼロに達すると、それは抽象化開放リストから除外される。
【００５３】
抽象化ノードの動作カウンタは、（１）その演算子グラフの全てが後続節点の生成に用いられ、（２）その使用されていない演算子群のどれも利用可能な重複検出作用域を持たないという、２つの異なる理由からゼロに至ることがある。第１の場合には、抽象化ノードをそのときのレイヤについての抽象化開放リストから除外すべきである。第２の場合には、使用されていない演算子グラフの１つの重複検出作用域が利用可能となるや否や抽象化ノードを抽象化開放リスト上に戻すべきである。
【００５４】
これら２つの場合を差別化すべく、アルゴリズムは未使用で利用可能なビットを下記の如く監視する。抽象化ノードの動作カウンタは、その演算子群の未使用ビットのいずれかがリセットされたときに歩進減数される。利用可能なビットが設定されると、同じ演算子群の未使用ビットが設定されている場合で、かつその場合に限り、動作カウンタは歩進増数させられる。換言すれば、抽象化ノードの動作カウンタはその未使用ビットと利用可能ビットの両方が設定されたその演算子群の数を計数する。
【００５５】
したがって、同期メカニズムは被共有メモリの並列化用には単一ロックがありさえすればよい。包括的なミューテックスの首尾よきロック時に、探索処理工程は抽象化開放リスト上の抽象化ノードのいずれかから作動可能とされた演算子群を取り上げるが、それは正の動作回数を有するものだけがリスト上にあるからである。作動可能とされた演算子群が一旦選択されると、探索処理工程は選択されたものに干渉する全ての演算子群の利用可能なビットをリセットし、このことが一部の１（または複数）の抽象化ノードが抽象化開放リストから除外できるようにする。処理工程はロックを解放し、ロックが解放された後においても被選択演算子群の重複検出作用域におけるノードへの排他的アクセスが持てるよう保証することができる。その演算子群を用いてその処理工程を行なうときに、それはミューテックスを再度ロックし、それが以前リセットした利用可能ビット全てをセットし、このことが一部の１（または複数）のノードを抽象化開放リスト上に戻せるようにできる。抽象化グラフは原状態空間グラフの大きさに比べ極め小さいため、抽象化グラフに対し為される処理は効率的に行なうことができ、殆ど計算を必要としない。したがって、各処理工程は僅かな時間部分に対し包括的ミューテックスを保持し、その計算努力の大半をノード拡張に費やすだけで済む。
【００５６】
大半の場合、エッジ分割はＳＤＤよりも低速であり、何故ならそれはディスク（ＲＡＭ内）に保存されたノードのスワップイン（アウト）用により多くのディスク入／出力部を必要とするからである。純粋な内部メモリ探索にとっては、ディスク入／出力部は全く不要であり、興味を引く疑問点はエッジ分割をＳＤＤよりも高速に出来るかにある。
【００５７】
エッジ分割に関する従来の知恵は、それが純粋な構造重複検出よりも低速であるというものである。下記の実験に示される如く、これは事実でない。これらの実験結果をよりよく理解すべく、エッジ分割に有利に機能させることのできる効率因子を考察する。
【００５８】
エッジ分割は、単一バケットのノードに対する探索アルゴリズムの重複検出作業に的を絞るものである。したがって、そのコードはより良質のメモリ基準局在性を呈し、より少ない保存ミスを有し、最新のプロセッサでのより高速のルーチン性能に繋がる。第２に、エッジ分割はノードの拡張時にどの演算子を適用できるかを特定する事前条件の照合に費やされる計算量の相当な節約をもたらす。
【００５９】
特定ドメインソルバーと異なり、ドメイン非依存プランナの後続節点生成関数は問題の記述から自動的に抽出される。しかしながら、より汎用の後続節点生成器では、演算子集合は、特に根付け後に相当に大きくなることがある。
【００６０】
下記の実験に用いられるプランナはコンパクトな状態表現に対し直接に前提条件試験を遂行するが、数百あるいは数千の演算子集合中の各個別の演算子の適用可能性を試験するのに依然相当の時間を要しうることが判っている。各エッジ分割は、どの演算子が適用可能かを特定するのに演算子テーブルの線形走査を遂行するとは限らない。
【００６１】
エッジ分割は、状態抽象化の頂部で演算子抽象化を行なう。抽象化エッジ（ｙ，ｙ’）については、エッジ分割は（１）抽象化ノードｙに適用可能で、（２）抽象化ノードｙ’に写像するそれらの後続節点を生成するだけの演算子の集合Ｏｙ，ｙ’を算出する。このことは、抽象化ノードｙにおいて１つの演算子ｏが適用可能でない場合、そのときは全てのｙ’についてＯｙ，ｙ’内にｏが存在しないことを意味し、それはエッジ分割が試験無しで演算子を安全に無視できることを意味する。
【００６２】
先の１５パズルの例では、空欄を抽象化ノードＢ０から右に移動させる演算子をエンコードする集合
【数２】
0006021305.tif 000003
には、１５個の演算子しか存在しない。空欄をＢ０からＢ４へ下方に移動させる演算子をエンコードする集合
【数３】
0006021305.tif 000004
には、別の１５個の演算子が存在する。したがって、抽象化ノードＢ０へ写像する状態については、試験する必要のある演算子の総数は３０であり、１５パズルの全状態空間に亙り規定された元々の７２０個の根付き演算子に比べ２４分の１の低減となる。低減された演算子集合
【数４】
0006021305.tif 000005
は、
【数５】
0006021305.tif 000006
と
【数６】
0006021305.tif 000007
との和集合であり、抽象化ノードＢ０へ写像する１５パズルの部分空間に設定された全演算子集合Ｏの射影として視認され、そのことが演算子集合を左上隅に位置する空欄を有する状態にて適用可能なものだけに制約する。各抽象化ノードに関する適用可能な演算子の数は、状態空欄抽象化の解像度が増大するのに合わせ減少し、したがって演算子抽象化の能力も減少する。
【００６３】
図５は、ＰＥＰを用いた最終的な探索出力を取得する行為を示す。この線図には、グラフの抽象化表現の構築（行為５０２）と、抽象化ノードの重複検出作用域の分割（行為５０４）と、そのときの探索レイヤ内のノードの拡張（行為５０６）と、全ての演算子群を使い切ったときに次の探索レイヤに進むこと（行為５０８）が含まれる。
【００６４】
本開示は、図５の行為あるいは事象の例示配列に限定はされない。
【００６５】
グラフの抽象化表現は状態空間抽象化を用いて構築（行為５０２）され、これは概ねグラフに対する状態空間射影関数の適用を通じて構築され、ここでは状態空間射影関数は原状態空間から抽象化状態空間への多点−単点写像とされる。グラフの抽象化表現が一旦構築されると、その各抽象化ノードは重複検出作用域を含む。さらに、各抽象化エッジは演算子群を含んでいる。
【００６６】
エッジ分割を用いることで、抽象化ノードの重複検出作用域はより小さな重複検出作用域に分割される（行為５０４）。より小さな検出作用域のそれぞれが、抽象化エッジの１つに対応する。好都合なことに、これらのより小さな抽象化検出作用域により、たとえグラフが固有の局在性を持たないときでもグラフの並列探索が可能になる。
【００６７】
そのときの探索レイヤ内のノードを、拡張する（行為５０６）。ノードの拡張は、そのときの探索レイヤ内のノードを写像する抽象化ノードに属する演算子群の使用を通じて達成される。ノードは、全ての演算子群が使用されるまでこれらの演算子群を用いて拡張される。互いに素の重複検出作用域に関連する演算子群だけ任意の時点で使用する限り、ノードは並列に拡張することができる。グラフを探索している間、互いに素の重複検出作用域を有する演算子群は変化する。
【００６８】
そのときの探索レイヤについて全ての演算子群を使い切ると、探索は次の探索レイヤへ進み、前述の行為が反復される（行為５０８）。この行為を含む上記した行為は、終了条件（例えば、目的ノード）に達するまで反復される。前述の行為間には、一時的な関係は必ずしも存在しない。むしろ、それらは同時並行的に発生し、多数回反復することができる。
【００６９】
図６は、グラフの抽象化表現の構築（行為６０２）と、抽象化ノードの重複検出作用域の分割（行為６０４）と、そのときの探索レイヤ内のノードの拡張（行為６０６）と、全ての演算子群を使い切ったときに次の探索レイヤへ進むこと（行為６０８）とを含むＰＥＰを用いた最終的な探索出力を取得する行為を示す。
【００７０】
本開示は、図６の図示の順序の行為あるいは事象に限定はされない。
【００７１】
グラフの抽象化表現は、状態空間抽象化を用いて構築（行為６０２）され、概ねグラフに対する状態空間射影関数の適用を通じて構築され、ここで状態空間射影関数は原状態空間から抽象化状態空間への多点−単点写像である。一旦構築されると、グラフの抽象化表現の各抽象化ノードには重複検出作用域が含まれる。
【００７２】
グラフの外向性エッジは、グラフの抽象化表現に基づいて分割される（行為６０４）。分割には、１つの演算子群として抽象化表現の同じ抽象化エッジへ併せ写像するグループ分けエッジが含まれる。これらの演算子群により、たとえグラフが固有の局在性を持たないときでもグラフの並列探索が可能とされる。
【００７３】
異なる演算子群（すなわち、互いに素の重複検出作用域を有する演算子）が、終了条件に合致（行為６０６）するまで処理装置に割り当てられる。処理装置は、これらの異なる重複検出作用域を用い、後続節点ノードを並列に生成する。
【００７４】
後続節点ノードが生成されるのに合わせ、グラフを探索する（行為６０８）。そのときの探索レイヤ内の各ノードを試験し、それが探索規範に合致するか特定することができる。
【００７５】
上記に記載した行為は、終端条件（例えば、終端ノード）に達するまで反復される。前述の行為間には、一時的な関係は必ずしも存在しない。むしろ、それらは同時並行的に発生し、何回となく反復することができる。
【００７６】
図７は、ＰＥＰシステム７００を示すものである。記憶装置とデジタルプロセッサを含むコンピュータや他のデジタル処理装置７０２は、システム７００を組み入れている。他の実施形態では、システム７００はデジタルプロセッサを含み、さらにデジタルデータ記憶装置へのアクセスを含むかもしくは有するサーバにより具現され、この種サーバはインターネットあるいはローカル・エリア・ネットワークを介して適切にアクセスされる。
【００７７】
コンピュータやデジタル処理装置７０２は例示キーボード７０４等の１以上のユーザ入力装置に作動的に接続され、制御システム７００へのユーザ入力を受け取り、さらにシステム７００の出力に基づき生成される出力を表示するディスプレイ７０６等の１以上のディスプレイ装置を含むか、あるいはこれに作動的に接続される。他の実施形態では、システム７００への入力はコンピュータ７０２上のシステム７００よりも先にあるいは同時並行的に実行し、もしくはネットワーク接続からの別のプログラムから受け取る。
【００７８】
システム７００は、ＰＥＰを遂行するＰＥＰモジュール７０８を含む。ＰＥＰモジュール７０８は、モジュール７０８外部のソースからグラフを受け取り、ＰＥＰを実行する。外部ソースは、例えばコンピュータ７０２あるいはコンピュータ７０２のユーザが記憶するファイルとすることができ、ここではユーザはキーボード７０４を介してＰＥＰモジュール７０８と相互作用する。
【００７９】
実施形態では、ＰＥＰモジュール７０８はＰｅＰを実行するための実行可能な命令を記憶する記憶媒体（例えば、デジタルプロセッサ）により具現される。記憶媒体には、例えば、磁気ディスクや他の磁気記憶媒体、光ディスクや他の光学式記憶媒体、ランダム・アクセス・メモリ（ＲＡＭ）やリード・オンリー・メモリ（ＲＯＭ）や他の電子記憶デバイスやチップあるいは作動的に相互連結されたチップ群、記憶する命令をインターネットあるいはローカル・エリア・ネットワークを介して検索することのできるインターネットサーバを含めることができる。
【００８０】
図８は、図７のＰＥＰシステムの一つの実用的なアプリケーションを例証する印刷システム８００を示す。システム８００は、給送器８０２、マーキング（印刷）エンジン８０４、方向転換器あるいは反転器８０６、仕上げ器、出力トレイ８０８等を含む１９７個の独立モジュールを含む。モジュールは一丸となって動作し、様々な印刷製品を生み出す。
【００８１】
ＰＥＰは、印刷エンジン８０４全体に印刷ジョブの分散をプラニングする（すなわち、プラニング問題を解く）のに適している。例えば、ＰＥＰは幾つかの印刷エンジン８０４を内部配置できる点を考慮し、給送器８０２から出力トレイ８０８まで最短の経路を見いだすことができる。ＰＥＰは、遅れを最小化すべく印刷ジョブをスケジューリングするのにも用いることができる。プラニング問題をグラフに写像するのに、システム状態はグラフのノードとして取り扱われ、システム状態間の関係はグラフのエッジとして取り扱われる。エッジの重みは、時間や距離やコスト等とすることができる。プランは、そこでシステム状態の一構成を含む。
【００８２】
グラフ探索を用いて他システム内にＰＥＰシステムが採用できることも、理解されたい。例えば、ＰＥＰシステム７００は、別の選択肢として経路プラニングシステムおよび／または方法にて用い、２つの位置間で最短かつ最速の経路を見いだすことができる。
【００８３】
その下敷きとなる探索アルゴリズムとして幅優先ヒューリスティック探索を用いるドメイン非依存ＳＴＲＩＰＳプランナ内に、ＰＥＰを実験的に実装した。
【００８４】
探索アルゴリズムが、順方向状態空間プラニングを用い、許容可能なパターンデータペースによりヒューリスティックに誘導される最適な一連のプラニングを見いだす。プランナは、隔年プラニング競争に基づき８個のベンチマークドメインにて試験した。実験に用いた全てのプランナは、Ｃ言語にて実装し、ｇｃｃを用いて同一の最適化レベルにてコンパイルしたものである。実験は、大まかには２ＧＢのＲＡＭに制限された３．０ＧＨｚ版のデュアル・クワッドコア・インテルキセノンＸ５４５０プロセッサ上で行なった。
【００８５】
少なくとも２つの理由から、単に並列高速化比を根拠に、幅優先探索ヒューリスティックアルゴリズムと最良優先探索アルゴリズムとを比較することは公平ではない。
【００８６】
理由＃１：ヒューリスティック探索への最良優先手法ではなく幅優先ヒューリスティック探索を用いる下敷きとなる理論的根拠は、前者が後者よりも小さな探索最前線を誘発する点にある。この種の差異は、ヒューリスティック探索がより正確になるにつれ増大する。最前線（すなわち、オープンリスト）は探索アルゴリズムの「作業負荷」のスナップショットとして見ることができるため、Ａ＊はより少ない開放ノードを用いて作業することを強制される幅優先ヒューリスティック探索よりも多量の処理作業を（場合によっては同時並行的に）有する当然の利点を有する。
【００８７】
理由＃２：本願明細書に記載する幅優先ヒューリスティック探索の並列版は、レイヤ準拠同期を用いてメモリを節約するものである。したがって、探索スレッドはそれらがレイヤの端部に接近するにつれ飢餓状態となる可能性が高くなる。ＨＤＡ＊とＰＢＮＦは、他方で影響を受けない。何故ならそれらはレイヤに準拠しないからである。ＰＥＰと異なり、メモリ要件は使用するスレッドの数に合わせ増大させることができる。
【００８８】
これらの欠点にも拘わらず、実験はＰＥＰが好都合なことに全てのスレッドについて他の全てのアルゴリズムに比肩することを示すものである。唯一の例外は、生成されたノードの数を上回るより多くの歩進的拡張をＰＥＰが必要とするブロック−１０である。
【００８９】
図９は、ＰＳＤＤの性能とＰＥＰの性能とを比較するテーブル９００を含む。これらの問題は、２ＧＢのＲＡＭ内で解くことのできる８個のドメインのそれぞれで最大となる。テーブル９００は、ＰＥＰが全ノード拡張を必要とするＰＳＤＤを平均で１桁は上回る歩進的ノード拡張を必要とし、しかも依然として相当に高速であり、ＰＥＰはＰＳＤＤよりも粗い抽象化機能と共に等しくあるいはより優れて効果的とすることができる。平均して、ＰＥＰに使用する抽象化グラフ（欄内に
【数７】
0006021305.tif 000008
として標識付けして図示）の大きさは、ＰＳＤＤ内のそれの１／１０を下回る。ＰＥＰは、６４個ほどの少数の抽象化ノードを用いて抽象化グラフに対し十分な同時並行性を梃入れすることができる。ＰＳＤＤ（あるいはＰＢＮＦ）がその小ささの抽象化グラフを用いた場合、その実際の（ＣＰＵ内クロックによらない）実行時間はテーブル９００内に提示されたものよりも相当に劣化する筈である。
【００９０】
図１０は、同じプラニング問題集合についてのＨＤＡ＊とＰＢＮＦ（ライブロック無縁版）のルーチン性能を示すテーブル１０００を含むものである。全てのアルゴリズムは、（同じＣコードで計算する）同じ容認可能なヒューリスティック法を用いた。テーブル１０００は、ＨＤＡ＊とＰＢＮＦが幅優先ヒューリスティック探索よりもメモリ効率が劣るものであり、それらがＰＥＰよりも相当に低速で実行されることを示すものである。ＰＢＮＦは、２スレッドではなく７スレッドを用いるサテライト−５上でメモリを使い切ってしまった。ＰＥＰと異なり、ＰＢＮＦのメモリ要件は使用するスレッドの数に合わせ増大させることができる。サテライト−５については、ＲＡＭが記憶するノードのＰＢＮＦピーク数が１，２，４の各スレッドについて大まかには１６００万，３２００万，５４００万個のノードとなる。
【００９１】
ＰＥＰは、ＳＴＲＩＰＳプラニング問題として定式化された１５パズルのハードインスンタス上でも実行させた。図１１のテーブル１１００に示すインスタンスは、Ｋｏｒｆの１００個の１５パズルインスタンス（「＃」を標識付けした欄がインスタンス番号を示す）の中でも最も難しい１０個に含まれる。以前は、最良ドメイン非依存ソルバーは数時間でそれらのうちの９３個を解くことが出来た。しかしながら、ＰＥＰはドメイン非依存パターンデータベースをヒューリスティックに用い（特定ドメインソルバー向けのヒューリスティックなマンハッタン距離と等価）、数分でそれらのうちの９５個を解くことが出来る。表１１００内のどのインスンタスもＨＤＡ＊あるいはＰＢＮＦでは解くことは出来ない。何故なら両方ともインスンタスが一つでも解けるよりも相当前にメモリを使い切ってしまうからである。
【図１】
0006021305.tif 000009
【図２】
0006021305.tif 000010
【図３】
0006021305.tif 000011
【図４】
0006021305.tif 000012
【図５】
0006021305.tif 000013
【図６】
0006021305.tif 000014
【図７】
0006021305.tif 000015
【図８】
0006021305.tif 000016
【図９】
0006021305.tif 000017
【図１０】
0006021305.tif 000018
【図１１】
0006021305.tif 000019