(57)【特許請求の範囲】
【請求項１】
目標値探索を用いるモデルベース制御システムのための目標経路を決定する方法であって、前記モデルベース制御システムは非巡回有向グラフを有し、前記非巡回有向グラフは複数の辺により相互連結された複数の頂点を有し、
前記方法が、
（ａ）前記目標経路のための非巡回有向グラフの深さ優先探索を実行するステップであって、深さ優先探索では陽解または陰解のいずれかが返され、該陰解はヒューリスティックを用いて決定し、深さ優先探索のメモリ必要量が目標値によって制限され、目標値に関して線形である、ステップと、
（ｂ）前記陽解または陰解から目標経路を構築するステップと、を含み、前記方法が少なくとも１つのデジタル処理装置を用いて実行される方法。
【請求項２】
請求項１に記載の方法であって、さらに、
前記複数の頂点の異なる経路長さの境界を含むパターンデータベースを作成するステップを含む、方法。
【請求項３】
請求項１に記載の方法において、
前記ヒューリスティックがパターンデータベースを使用する、方法。
【請求項４】
請求項１に記載の方法において、
前記深さ優先探索が、前記ヒューリスティックにより制限される、方法。
【請求項５】
請求項１に記載の方法において、
前記深さ優先探索によって現在の探索プレフィクスと先頭頂点とが求められ、該現在の探索プレフィクスが前記複数の頂点からの１つ以上の連結された頂点を含み、該先頭頂点が現在の探索プレフィクスにおける最も深い頂点である、方法。
【請求項６】
請求項５に記載の方法において、
前記深さ優先探索が、
（１）前記現在の探索プレフィクスが陽解であるかを判定するステップと、
（２）前記現在の探索プレフィクスが陽解であると判定されると、該現在の探索プレフィクスを目標経路として返し、深さ優先探索を終了するステップと、
を実行する方法。
【請求項７】
請求項５に記載の方法において、
前記深さ優先探索が、
（１）前記現在の探索プレフィクスがこれまでの現在探索プレフィクスより良好であるかを判定するステップと、
（２）前記現在の探索プレフィクスがこれまでの現在探索プレフィクスより良好であると判定されると、該現在の探索プレフィクスを保存するステップと、
を実行する方法。
【請求項８】
請求項５に記載の方法において、
前記複数の頂点が初期頂点と、目標頂点と、１以上の中間頂点とを含み、前記１以上の中間頂点が前記初期頂点の子孫及び前記目標頂点の先祖の両方である、方法。
【請求項９】
請求項１に記載の方法において、
前記実行するステップと構築するステップとが、深さ優先目標値探索として実行される、方法。
【請求項１０】
請求項１に記載の方法において、
前記陽解は、初期頂点から目標頂点まで延びる経路であり、かつ、前記陽解の経路長さは、（１）目標値に等しいことと、（２）初期頂点から目標頂点まで伸びる他のすべての経路長さに比べて前記目標値に最も近いこととのいずれか１つである、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本例示的実施形態は、生産計画システム及び消費者に目標の探索結果を提供するシステムに関するオンライン診断など、様々な設定で利用可能な目標値探索についてのシステム及び方法に関する。
【背景技術】
【０００２】
自動生産計画システムでは、ある生産資源を知能的に用いて、特定の資源に欠陥がある確率を示す診断情報を得ながら、所与の製品を製造するため工場資源を選択することが必要である可能性がある。この状況では、製品製造のための資源の最短または最速の組を単に選択することでなく、非ゼロである欠陥の確率を試験しながら、製品を組み立てる一連の資源を規定する計画を選択することにより、計画者の診断目標が実現容易となる可能性がある。別の例では、消費者が計画者に対し、ある期間（または期間の範囲、例えば所定の月内に開始及び期末日がある５〜７日）を有し所与の目標費用または費用範囲がある、ある目的地（または複数の期待される目的地）への休暇プランを特定することを望む場合がある。さらなる用途では、消費者が１０月の日中に公園を通る３〜５時間続く旅行プランを求めている場合に、紅葉を見るドライブを計画するための目標距離及び目標時間の一方または両方の値とともに出発及び終点場所を受容可能なマッピングシステムが望まれる場合がある。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
過去において、探索の問題は、開始状態と目標状態との間の最短経路を求めるための最小化アルゴリズムを用いて解決されていた。しかしながら、ある用途における目標は必ずしも最小の長さまたは費用の経路を求めることではなく、その代わりに、所望の経路は非ゼロまたは非最小の費用または期間を有する。これらの状況における最短経路探索技術を用いることは、最短経路を特定することと、目標値範囲内に入らないそれらの特定された経路を除外または排除することとが必要になる。このプロセスは、所望の領域内にある経路が特定されるまで繰り返される。この方式は、所与の目標値に最も近い値を有する１以上の経路の特定に用いられる効率的な目標値経路探索技法及びシステムが必要となる、多くの実生活用途において非実用的である。
【課題を解決するための手段】
【０００４】
本発明に係る方法は、目標値探索を用いるモデルベース制御システムのための目標経路を決定する方法であって、前記モデルベース制御システムは非巡回有向グラフを有し、前記非巡回有向グラフは複数の辺により相互連結された複数の頂点を有し、前記方法が、（ａ）前記目標経路のための非巡回有向グラフの深さ優先探索を実行するステップであって、深さ優先探索では陽解または陰解のいずれかが返され、該陰解はヒューリスティックを用いて決定し、深さ優先探索のメモリ必要量が目標値によって制限され、目標値に関して線形である、ステップと、（ｂ）前記陽解または陰解から目標経路を構築するステップと、を含み、前記方法が少なくとも１つのデジタル処理装置を用いて実行される方法である。
【図面の簡単な説明】
【０００５】
【図１】連結グラフを示す図である。
【図２】ｓとｇとの間の（‖Ｖ‖において）指数関数的な数の経路を有する連結グラフを示す図である。
【図３】非巡回有向グラフを示す図である。
【図４】図３の非巡回有向グラフからの頂点の部分集合に関する連結グラフを示す図である。
【図５】パターンデータベースを生成する方法を示す図である。
【図６】深さ優先目標値探索を実施する方法を示す図である。
【図７】図６の深さ優先目標値探索の深さ優先探索により実行されるロジックのフローチャートである。
【図８】連結グラフを示す図である。
【図９】連結グラフを示す図である。
【図１０】本願の深さ優先目標値探索（ｄｅｐｔｈ−ｆｉｒｓｔ  ｔａｒｇｅｔ  ｖａｌｕｅ  ｓｅａｒｃｈ（ＤＦＴＶＳ））を用いる深さ優先目標値探索エンジンを示す図である。
【図１１】プランナと、プラントモデルと、診断エンジンと、ＤＦＴＶＳエンジンとを備えるモデルベース制御システムと、生産システムと、操作インタフェースとを示す概略図である。
【発明を実施するための形態】
【０００６】
目標値経路問題では、我々は、グラフ内の２つのノード、すなわち頂点の間の、その辺（エッジ）の重み、すなわち辺の値の合計が、ある目標値にできる限り近い経路を見出すことに関心がある。そのような問題は、従業員の所与の労働時間に関する相互依存タスクのスケジューリング、所与の期間の自転車旅行の計画、または適切なナイトリービルド（ｎｉｇｈｔｌｙ−ｂｕｉｌｄ）プロセスの決定など様々な分野で生じる。
【０００７】
辺の値をもつ非巡回有向グラフＧ＝（Ｖ，Ｅ）が与えられると、目標値ｔｖを有する２つの頂点ｖ0，ｖg∈Ｖ間の目標値経路は、ｖ0及びｖgの間の、値がｔｖに最も近いある経路である。経路pの値g(p)はその辺の値の合計として定義される。Ｐｖ0，ｖgがｖ0及びｖgの間のすべての経路の集合であるとすると、
【数１】
0005552382.tif 000002
は、ｖ0，ｖg，ｔｖに関する目標値経路の集合としての、ｔｖ からの偏差が最小のｖ0及びｖgの間の経路の集合として定義される。以下において、目標値探索（ｔａｒｇｅｔ−ｖａｌｕｅ  ｓｅａｒｃｈ、略してｔｖｓ）とは
【数２】
0005552382.tif 000003
のある要素に対するタプル（ｖ0，ｖg，ｔｖ）のマッピングをいう。
【０００８】
ｔｖｓは、クーン（Ｋｕｈｎ）らの「目標値経路問題に関する発見的探索（Ｈｅｕｒｉｓｔｉｃ  Ｓｅａｒｃｈ  ｆｏｒ  Ｔａｒｇｅｔ−ｖａｌｕｅ  Ｐａｔｈ  Ｐｒｏｂｌｅｍ）」、人工知能及びロボット工学における探索技法に関する第１回国際シンポジウム（Ｆｉｒｓｔ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｓｅａｒｃｈ  Ｔｅｃｈｎｉｑｕｅｓ  ｉｎ  Ａｒｔｉｆｉｃｉａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ  ａｎｄ  Ｒｏｂｏｔｉｃｓ）（２００８年７月１３−１４日）において導入されたものであり、その全体がここに編入されている。ｔｖｓは、これを（代表的に最短経路問題に関して影響を与えるように）動的計画法に順応させる重なり下位問題及び最適下部構造双方の特性を一般には示さないので困難な問題となる。「目標値経路問題に関する発見的探索」においてクーンらは、この問題は分解可能であり、そのある部分は前記特性を示すことを示した。この考えは、 vgまでの頂点の異なる経路長さの境界を含むパターンデータベースpdを事前計算するものである。プレフィクスp（Ｇにおけるv0からある頂点までのある経路）及びｔｖ を仮定すると、pdを用いて最適完了ｔｖ−g(p)がpdに記憶された境界の外側となるかどうかを判定可能である。外側の場合、pに関する最適完了を求める問題は最短経路問題または最長経路問題のいずれかに分解され、その双方は（ＤＡＧにおける）動的計画法を用いて解決可能である。
【０００９】
まず、動的計画探索において、（ｖ0，ｖgを含むｖ0の子孫及びｖgの先祖両方である頂点のみで構成される部分グラフである）ｖ0及びｖgの連結グラフ内の各頂点が、この頂点からｖg8までの経路の値を含む領域の集合により注釈付けされる。すなわち、インプリメンテーションはｐｄを生成することにより開始される。ある頂点ｖの領域は、頂点ｖからｖgまでの経路の長さの漸進近似を表わす（すなわち、すべての経路長さが前記領域内にあることが保証される）。このｐｄは、ｖ0及びｖgの間のいかなるｔｖｓに関しても再利用可能である。
【００１０】
ｐｄの生成は、ｐｄ（ｖg）＝［０；０］を初期化しｖgのみで構成されるキューを設定することにより開始される。各ステップにおいて、ある頂点がキューから除外される。次に各入辺ｅに関して、領域がvalue（ｅ）によりシフト（ｓｈｉｆｔ）され、ｅを通してそれぞれのプレデセッサ（先行）に伝播される。領域集合を受け取ると、プレデセッサはその領域集合が受け取った領域を含むものであるかを確認する。含むものである場合、さらなる作用は不要である。含まない場合、プレデセッサはその領域集合に新しい領域を一時的に付加し、両方の領域の和と交換することにより対の間の重なりを解決する。このプロセスの終端において、領域集合の大きさが許容最大値を超えている場合、大きさの制約条件が満たされるまで２つの最も近い領域が融合される。このプロセスは、定常状態が実現される（すなわちキューが空になる時）まで繰り返される。
【００１１】
パターンデータベースを構築するこのプロセスは、ｔｖｓの大きなグラフへのスケーリングを妨げる２つの主要な原因のうちの１つである。以下の仮定の下で図１の例を考察する。ａ0は現在キューの先頭であり、頂点はそれらの番号付け順序における先祖関数により返され、各更新はそれぞれの頂点に関するパターンデータベース入力を変更するものである。まず、ａ0が展開され、それによりａ1及びａ2が更新され、それらが（この順序で）キュー上に配置される。さらに、ａ1が展開され、そのすべてのプレデセッサ（図１では不図示）がキュー上に配置される。次がａ2となる。ここで、ａ1が更新され、ａ3とともにキュー上に配置される。さらに、ａ1が再びキュー上に現われるまでａ1のすべてのプレデセッサが処理され、その結果、その更新されたプレデセッサが再びキューに加えられる。以下同様である。最悪の場合、各頂点は目標頂点との間の明確な経路ごとに１回更新され、その結果、パターンデータベースを構築する実行時間が（頂点の数において、図２参照）指数関数的な最悪のケースとなる。
【００１２】
パターンデータベースｐｄがどのように生成されるかに関わらず、その後Ａ＊の変種がｖ0から開始され、ここで探索ノードは（ある頂点及びその先祖ノードへのポインタとして表わされる）プレフィクスと、当初の ｔｖからプレフィクスの値（ｇ（ｐ））を差し引いた、その残り目標値（以下ｔｖ´として示す）とで構成されている。ｔｖ´及びプレフィクスの最後の頂点に関するｐｄ入力に基づき、そのプレフィクスの最良完了に関する最小偏差が計算可能であり、これは以下のヒューリスティックにより表わされる。
【数３】
0005552382.tif 000004
distはスカラーが領域境界内にある場合は０として定義され、そうでない場合は
【数４】
0005552382.tif 000005
として定義される。heur関数は以下の特性を有する。Ｇにおけるｐの最良（したがってすべて）の可能な完了に関する目的関数の値の下界を表わす。またすべてのプレフィクスに関し、
【数５】
0005552382.tif 000006
は目的関数に等しい。これにより、heurをＡ＊におけるｆ関数として用いることが可能になる。
【００１３】
ヒューリスティックは、プレフィクスのｔｖ´をその最後の頂点の領域集合と比較することによりパターンデータベースを使用する。ｔｖ´がある領域の内側に存する場合、プレフィクスの最適完了が正確に初期のｔｖを与える見込みがある。したがって、許容可能とするためには、ヒューリスティックはそのようなプレフィクスを最高に評価して０を返さねばならず、さもなければヒューリスティックは最近の領域に ｔｖ´距離を返す。すべての可能な完了長さは前記領域内にあり、各領域の境界は実際の経路長さを表わすので、これは前記プレフィクスの完了が初期の目標値に到達可能な最近のものである。そのため本質的に、ヒューリスティックは完全な誘導（heur＞０）を与えるか、まったく誘導を与えない（heur＝０）かのいずれかである。直観的に、グラフの経路長さの領域にわたり均一に分布したｔｖｓを仮定すると、前者のケースの確率は領域に含まれる「面積」に反比例する。ＤＡＧにおいて、この面積は、各頂点の領域集合が少なくともそのサクセッサの各々と同じ大きさの表面を覆うので、目標ノードからのリンク距離において単調増加する。
【００１４】
最適性を保証するため、ヒューリスティックの「盲点」（すなわちheur＝０である頂点におけるそれらの終端）におけるすべてのプレフィクスを処理しなければならない。最悪の場合、これはグラフの最大部分となる場合がある。さらに、これらプレフィクスの数は、盲点の大きさにおいて指数関数的となる場合がある（図２を想起のこと）。これは最良優先ｔｖｓの、より大きなグラフの大きさへのスケーリングを妨げる第２の原因である。ある点において、これらプレフィクスの大きな占有率をＡ＊のオープンリスト内で維持しなければならず、その結果、最悪例のメモリ必要量はＣ内の頂点の数において指数関数的となる。これにより重複検出の問題が残される。
【００１５】
ｔｖｓの状況において、プレフィクスを余分としうる２つの方法がある。第１に、等しい ｔｖ´とともに同じ頂点で終わるプレフィクスのいかなる対も、同じ最適完了を共有することになり、初期の目標値からの偏差が等しくなる。言い換えれば、前記対から生じるそれぞれの最良解はｔｖｓの目的関数に関して等しくなるので、プレフィクスの１つを余分と見なし廃棄することができる。これは重複検出に対するｔｖｓのアナログである。heurは、heur（ｐ，ｔｖ´）＞０となるいかなるプレフィクスｐに関してもheur（ｐ，ｔｖ´）が初期のｔｖ からのｐの最良完了の実際の偏差を表わす特性を有するので、第２の態様は、はるかに普遍的である。このように、
【数６】
0005552382.tif 000007
のいかなるノードの対
（ｐ1，ｔｖ´1），（ｐ2，ｔｖ´2）
に関しても、（ｐ1，ｔｖ´1）を余分と見なし、その結果、無視することができる。Ａ＊の導関数は、heur＞０の最初の入力後、そのオープンリストを枝刈りするまたは取り除くことによりこれを利用する。
【００１６】
Ａ＊は（heurなどの）許容可能ヒューリスティックに関するノード展開の数において最適であることが周知であるが、重複検出は、（最悪例において）以前に訪れたすべてのノードを保持しなければならないので、メモリ及び計算オーバーヘッドの点で費用がかかることがある。これはｔｖｓなど重複がまれにしか生じない領域において特にあてはまるものであり、そこでは（それらの定義により）重複は同じグラフ上の最短経路探索技法と比較（長さが等しい経路を通って同じ頂点を訪れることと単に同じ頂点を訪れること）して、はるかにまれである。
【００１７】
このオーバーヘッドを回避してスケーラビリティに関する２つの主要な問題に対処するため、heur関数の特性を利用する深さ優先枝探索及び境界探索に基づくｔｖｓに対する新規の方式が提示される。この新方式は、パターンデータベースを生成する改良された方法と深さ優先目標値探索を実施する方法とを含むものである。
【００１８】
図３から１１を参照し、本開示のいくつかの実施形態またはインプリメンテーションを図面とともに以下に説明するが、同様の参照数字はそれらの図面を通じて同様の要素を示すために用いられ、様々な特徴、構造、及び図形表現は必ずしも同じ縮尺で描かれてはいない。
【００１９】
図３を参照すると、非巡回有向グラフ３００が本発明の深さ優先目標値探索に必要とされるものとして図示されている。このグラフは、例えば辺３０６などの複数の辺により相互連結された頂点（例えば３０２及び３０４）など複数の頂点を含んで構成されている。このグラフは、グラフ内のどの頂点も別の頂点の先祖及び子孫の両方になることがない非巡回のものである。これら頂点はシステム状態、物理的目的地、またはプロセス内のステップを表わすものでもよいが、それらに限られない。同様に、辺は頂点間の作用、または時間的、空間的または物理的連結を表わすものでもよいが、それらに限られない。複数の辺は有向であり、辺重み（または値）を有している。例えば辺３０６の場合、辺重み３０８は１．５である。辺重みは距離、確率、時間、または速度を表わすものでもよいが、それらに限られない。
【００２０】
図４は、初期頂点ｖ0及び目標頂点ｖ6の連結グラフを示している。初期頂点及び目標頂点の連結グラフはあるグラフの部分集合であり、初期頂点、目標頂点、及び初期頂点の子孫及び目標頂点の先祖の両方である頂点のみを含んでいる。図４に示すように、各頂点は近接する領域境界を有している。領域境界は［下限，上限］の形で示されており、以下で論じるようにパターンデータベースの一部分である。この連結グラフを用いて、初期頂点と目標頂点との間のパターンデータベースを生成する改良された方法を説明する。
【００２１】
図５は、パターンデータベースを生成する改良された方法５００を示す。方法５００は図４の連結グラフのような連結グラフ上で動作し、連結グラフから頂点を選択するステップ（ステップ５０２）と、選択された頂点を処理するステップ（ステップ５０４）と、連結グラフ内のすべての頂点が処理されるまで前述のステップを繰り返すステップ（ステップ５０６）とを有する。
【００２２】
改良された方法５００は、連結グラフから、処理の準備ができた１以上の頂点を選択することにより開始される（ステップ５０２）。この選択プロセスは、逆位相順で実施される。すなわち、グラフの底から始まって、準備のできた頂点が選択される。グラフの底は目標頂点によって定義される。処理の準備ができた頂点が複数存在する場合、頂点が選択される順番または、いかなる数の頂点を選択するかは問題とならない。
【００２３】
ある頂点はその隣接する子孫のすべてが処理されると、処理の準備ができる。家族との類推によれば、親は、その親の子供すべてが処理されると、処理の準備ができる。この方法が最初に開始される際、方法５００は連結グラフ上で動作し、連結グラフは目標頂点の先祖である頂点を含むだけなので、この基準を満たす頂点のみが目標頂点となる。言い換えれば、目標頂点はいかなる子孫も有しない。したがって、この方法は、目標頂点を選択することにより開始される。
【００２４】
１以上の頂点が選択（ステップ５０２）された後、頂点が処理される（ステップ５０４）。選択された頂点が複数存在する場合、選択された頂点は連続的または同時に処理してもよい。この例示的方法は一般にソフトウェアで実施されるので、新しいスレッドを生成するか分岐することと解釈してもよいが、必須ではない。処理は、処理されている頂点の各先祖の領域境界をシフトすることと、処理されている頂点の子孫のシフトされた領域境界を、ある組み合わされた領域境界と組み合わせることと、処理されている頂点に、組み合わされた領域境界を割り当てることとを含んでいる。
【００２５】
処理されている頂点の各子孫の領域境界は、処理されている頂点とそれぞれの子孫とを連結する辺の辺重みによりシフトされる。すなわち、対応する辺重みが各子孫の領域境界に付加される。ある領域境界は、図４で用いられる同じ表示法［x,y］に従って記述される。領域境界の下限はxであり、領域境界の上限はyである。したがって、もし処理されている頂点が、領域境界が［２，５］の第１の子孫を有する場合、処理されている頂点と第１の子孫とを連結する辺の辺重みは０．５である。さらに、もし処理されている頂点が領域境界が［３，６］の第２の子孫を有する場合、処理されている頂点と第２の子孫とを連結する辺の辺重みは２である。そのような場合、第１の子孫及び第２の子孫に関するシフトされた領域境界はそれぞれ［２．５，５．５］及び［５，８］である。シフトされた境界は、現在処理されている頂点の先祖に関する既存の領域境界に代わるものではないことを理解されるべきである。
【００２６】
処理されている頂点の子孫の領域境界がシフトされた後、シフトされた領域境界が組み合わされる。シフトされた領域境界は、子孫のシフトされた領域境界から最小の下限及び最大の上限を単に得ることにより組み合わされる。例えば、前述の例に戻り、第１の子孫及び第２の子孫それぞれのシフトされた領域境界［２．５，５．５］及び［５，８］を組み合わせると、組み合わされた領域境界は［２．５，８］である。最初に選択、したがって最初に処理される目標頂点の場合、目標頂点の境界は［０，０］である。これは領域境界が目標頂点までの経路長さに関する下限及び上限を含むことにより生じる。目標頂点からそれ自身までの経路長さは０である。
【００２７】
組み合わされた領域境界はその後、処理されている頂点に割り当てられる。すなわち、パターンデータベースに記憶される。パターンデータベースはグラフの一部分またはそれ自身の別個の実体であってもよい。すなわち、連結グラフが基礎づけられているパターンデータベース及びグラフは一般に電子的形態で実現され、グラフを形成する頂点及び辺は何らかの電子データベースの方式で記憶される。頂点に関する領域境界は頂点とともに記憶するか、または別個のデータベースに記憶してもよい。本明細書において、データベースは、（コンピュータシステムに記憶された）記録の構造化されたコレクションを指すものとして弛緩的に用いられる。記録の構造化されたコレクションは、ハードドライブなど電子的形態の記憶装置により実現してもよい。データベースはステートレスまたはステートフルであってもよく、パターンデータベースを生成する改良された方法を実現する装置に対しローカルまたはリモートであってもよい。
【００２８】
理解されるように、各頂点は代替的に複数の領域境界（または間隔）を利用してもよい。このような場合、ある頂点の子孫の領域境界すべてが上記のようにシフトされる。相違するのは、各子孫がシフトすべき複数の領域境界を有してよいということのみである。その後、シフトされた領域境界は、所定数の領域境界と組み合わされる。領域境界は、重なり合う領域境界がまず組み合わされ、その後、最近の２つの領域境界が組み合わされるように組み合わされる。
【００２９】
選択された頂点が処理（ステップ５０４）された後、処理が繰り返される（ステップ５０６）。すなわち新規の１以上の頂点が選択され、処理される。この繰り返しは、連結グラフの頂点のすべてが処理されるまで続く。処理すべき最後の頂点は、上記初期頂点である。これは連結グラフ内のあらゆる頂点が初期頂点の子孫であることにより生じる。
【００３０】
ある実施形態では、インプリメンテーションは、目標頂点を有するキューと各頂点に関するカウンタとを初期化することにより開始され、この場合、カウンタは連結グラフ内の子孫のそれぞれの頂点の数に初期化される。代替的に、カウンタは局所的な維持が可能である。各ステップにおいて、以下のことが実施される。第１の頂点をキューから除外し、頂点のすべての子孫からの領域を組み合わせ、頂点のすべての先祖の子孫カウンタがディクリメントされる。カウンタが０に達すると、先祖がキューに加えられる。カウンタは、逆位相順での処理を可能とする。本方式は、従来の方式が区分的に先祖に領域をプッシュするものであったのに対し、本方式が子孫からすべての子孫領域を同時にプルすることを除いて、従来の方式と類似である。
【００３１】
このインプリメンテーションでは、Ｃ内の各頂点は１回だけ処理される。これは帰納的証明を通して示すことが可能である。すなわち、ｖのすべての子孫が１回だけアクセスされた場合、ｖのサクセッサのカウンタは０となりｖがキューに加えられ、それによりvが１回処理される（帰納ステップ）。ｖgはキュー上で開始されＣに子孫を有しないので、ｖg（大域的子孫）は１回アクセスされるのみとなる（基本的ケース）。これに続いて、各辺が２回（プレデセッサの方向に計数更新のため、反対方向に領域内のプルのため）アクセスされ、その結果、実行時間がＣ(Ｏ(｜Ｎ｜＋｜Ｅ｜)の頂点及び辺の数において線形になる。例示的グラフ（図２）に関し、これは処理順序ａ0、ａ1、・・・、ａn、ａ1を賦課するものである。この方式ではなお１つの潜在的問題がある。キューの大きさには何ら一定の境界が課されない。格子グラフがほとんど位相構造を示さない（すなわちｖ0及びｖg以外のすべての頂点がまさしくプレデセッサとしてｖ0、サクセッサ（後継）としてｖgを有する）場合、キューは格子グラフ内の｜Ｎ｜−２個の頂点まで成長可能である。補完的に、経路の数は｜Ｎ｜−２に等しいので、ｔｖｓはそのようなグラフにおいては自明である。
【００３２】
図４の連結グラフにパターンデータベースを生成する改良された方法５００を適用すると、この方法は、目標頂点ｖ6を選択することにより開始される。目標頂点ｖ6はいかなる子孫も有しない連結グラフ内の唯一の頂点なので、処理の準備ができている唯一の頂点である。子孫が存せず、かつ上記のように、領域境界は処理されている頂点から目標頂点までの経路長さの境界に対応しているので、目標頂点ｖ6を処理すると、領域境界は［０，０］になる。
【００３３】
処理準備ができている次の頂点は、その唯一の子孫が、処理されている目標頂点ｖ6なので、頂点ｖ4となる。頂点ｖ4を処理すると、目標頂点ｖ6の領域境界は、頂点ｖ4を目標頂点ｖ6と連結する辺に関連する辺重みによりシフトされる。これにより、シフトされた領域境界は［３，３］となる。頂点ｖ4は１つの子孫を有するだけなので、領域境界を組み合わせる必要はない。これにより、シフトされた領域境界［３，３］が頂点ｖ4に割り当てられる。
【００３４】
処理準備ができている次の頂点は、その子孫の双方、目標頂点ｖ6及び頂点ｖ4が処理されているので、頂点ｖ5となる。頂点ｖ5を処理すると、頂点ｖ4及びｖ6の領域境界は対応する辺重みによりシフトされる。頂点ｖ4の領域境界は、辺重み３によりシフトされ、シフトされた領域境界は［６，６］となり、頂点ｖ6の領域境界は、辺重み２によりシフトされ、シフトされた領域境界は［２，２］となる。頂点ｖ4及び頂点ｖ6のシフトされた領域境界を組み合わせると、頂点ｖ5に領域境界［２，６］が与えられる。
【００３５】
処理すべき次の頂点は、その子孫の双方、頂点ｖ5及び頂点ｖ4が処理されているので、頂点ｖ3となる。頂点ｖ3を処理すると、頂点ｖ4及びｖ5の領域境界は対応する辺重みによりシフトされる。頂点ｖ4の領域境界は、辺重み１．５によりシフトされ、シフトされた領域境界は［４．５，４．５］となり、頂点ｖ5の領域境界は、辺重み１によりシフトされ、シフトされた領域境界は［３，７］となる。頂点ｖ4及び頂点ｖ5のシフトされた領域境界を組み合わせると、頂点ｖ3に領域境界［３，７］が与えられる。頂点ｖ4のシフトされた領域境界は頂点ｖ5のシフトされた領域境界内に完全に収まるので、頂点ｖ3の領域境界には何の影響も及ぼさない。
【００３６】
この時点で、処理準備ができている２つの頂点、頂点ｖ1及び頂点ｖ2が存在する。頂点ｖ1は、その子孫の双方、頂点ｖ3及び頂点ｖ4が処理されているので、処理の準備ができている。同様に、頂点ｖ2は、その子孫の双方、頂点ｖ3及び頂点ｖ5が処理されているので、処理の準備ができている。どの頂点が最初に処理されるかは問題とならないので、頂点ｖ1が任意に最初に選択される。頂点ｖ1を処理すると、頂点ｖ4及びｖ3の領域境界が、対応する辺重みによりシフトされる。頂点ｖ4の領域境界は、辺重み２によりシフトされ、シフトされた領域境界は［５，５］となり、頂点ｖ3の領域境界は、辺重み３によりシフトされ、シフトされた領域境界は［６，１０］となる。頂点ｖ4及び頂点ｖ3のシフトされた領域境界を組み合わせると、頂点ｖ1に領域境界［５，１０］が与えられる。頂点ｖ2を次に処理すると、頂点ｖ3及びｖ5の領域境界は対応する辺重みによりシフトされる。頂点ｖ3の領域境界は、辺重み０．５によりシフトされ、シフトされた領域境界は［３．５，７．５］となり、頂点ｖ5の領域境界は、辺重み２によりシフトされ、シフトされた領域境界は［４，８］となる。頂点ｖ3及び頂点ｖ5のシフトされた領域境界を組み合わせると、頂点ｖ2に領域境界［３．５，８］が与えられる。
【００３７】
まだ処理されていない唯一の頂点、頂点ｖ0が存在する。頂点ｖ0は、その子孫、頂点ｖ1、頂点ｖ3及び頂点ｖ2がすべて処理されているので、処理の準備ができている。頂点ｖ0を処理すると、頂点ｖ1、ｖ3及びｖ2の境界が、対応する辺重みによりシフトされる。頂点ｖ1の領域境界は、辺重み１によりシフトされ、シフトされた領域境界は［６，１１］となり、頂点ｖ3の領域境界は、辺重み１．５によりシフトされ、シフトされた領域境界は［４．５，８．５］となり、頂点ｖ2の領域境界は、辺重み２によりシフトされ、シフトされた領域境界は［５．５，１０］となる。頂点ｖ1、頂点ｖ3及び頂点ｖ2のシフトされた領域境界を組み合わせると、頂点ｖ0に領域境界［４．５，１１］が与えられる。
【００３８】
パターンデータベースを生成する改良された方法に関する前述の論議を考察すると、この改良された方法は、ある頂点を１回訪れるだけであることが明らかである。
【００３９】
このように、この改良された方法を実施するのにかかる時間は、連結グラフ内の頂点の数に比例している。すなわち、この改良された方法の時間計算量は線形である。これにより、そのような方式は指数関数的な時間計算量によりパターンデータベースを生成する方法に依存するものであったので、パターンデータベースを利用する目標値探索方式が有利に改善されるものである。
【００４０】
図６の方法６００は、初期頂点と目標頂点との間の深さ優先目標値探索の実施を示している。パターンデータベースを生成する改良された方法（図５の５００を参照）と同様、方法６００は連結グラフ上で動作する。方法６００は、深さ優先探索を実施するステップ（ステップ６０４）と、深さ優先探索により返された解が陰解であるか否かを判定するステップ（ステップ６０６）と、返された解が陰解である場合、その陰解を展開するステップ（ステップ６０８）とを含む。この方法は選択的に、パターンデータベースを生成するステップ（ステップ６０２）を含む。深さ優先探索が、深さ優先目標値探索とは異なるものであることは、理解されるべきである。
【００４１】
方法６００は選択的に、初期頂点及び目標頂点に関するパターンデータベースを生成することにより開始される（ステップ６０２）。パターンデータベースがすでに存在する場合、パターンデータベースを生成し直すことは不要である。しかしパターンデータベースは、ステップ６０４の深さ優先探索が実施される前に生成される。
【００４２】
パターンデータベースが存在すると（ステップ６０２）、深さ優先目標値探索は目標値に関する深さ優先探索を行なう（ステップ６０４）。深さ優先探索は帰納的形態、反復形態、または他の同様の形態で実施可能である。目標値を探索する間、深さ優先探索は好ましくは現在の探索プレフィクスを維持する。現在の探索プレフィクスは初期頂点から先頭頂点まで延びる経路である。先頭頂点は深さ優先探索が現在実施されている頂点である。例えば、図４を参照すると、深さ優先探索が頂点ｖ1を経由して頂点ｖ3までトラバースされると、現在の探索プレフィクスは頂点ｖ0、頂点ｖ1及び頂点ｖ3（頂点ｖ3は先頭頂点）を含む頂点の集合となる。先頭頂点は現在の探索プレフィクスにおける、その他の頂点すべての子孫である。
【００４３】
処理されている各先頭頂点において、深さ優先探索は完全な解が見出されたかどうかを確認する。すなわち、深さ優先探索は、現在の探索プレフィクスの経路長さが目標値に等しいかどうか、また先頭頂点が目標頂点であるかどうかを確認する。完全な解が見出された場合、深さ優先探索は好ましくは終了して、現在の探索プレフィクスを返す。例えば、帰納的なインプリメンテーションにおいて、インプリメンテーションは、そのコールスタックをトラバースして直ちに終了することによりｔｖｐを構築してもよい。しかし、異なる実施形態では、深さ優先探索は他の完全な解を求め続けてもよい。
【００４４】
完全な解が発見されていないと仮定すると、深さ優先探索は以下の式に従って先頭頂点に関するヒューリスティック値を決定する。
【数７】
0005552382.tif 000008
ヒューリスティックは、残り目標値ｔｖ´をプレフィクスｐの先頭頂点に関する領域境界ｒと比較し、領域境界からの残り目標値ｔｖ´の最小偏差を返す。残り目標値 ｔｖ´は単に、目標値と現在の探索プレフィクスｐの経路長さとの差である。上記のように、領域境界ｒはパターンデータベースに記憶され、先頭頂点から目標頂点まで延びる経路長さの下限ｒ．ｌｂ及び上限ｒ．ｕｂを与えるものである。以下、先頭頂点から目標頂点まで延びる経路長さをサフィックス（ｓｕｆｆｉｘ）と呼称する。よって、残り目標値 ｔｖ´は完全なサフィックス長さに対応しており、領域境界ｒは実際のサフィックス長さの境界を与える。明らかなように、プレフィクス及びサフィックスは共に、初期頂点から目標頂点までの経路を定義する。
【００４５】
残り目標値 ｔｖ´が領域境界ｒの内側になる場合、サフィックスが残り目標値 ｔｖ´に等しい経路長さを有しうる、すなわち、完全な解が存在しうるので、ヒューリスティックはゼロの最小偏差を返す。しかし、解が存在する可能性以外に、誘導は与えられない。残り目標値 ｔｖ´が領域境界ｒの外側になる場合、完全な解につながりうるサフィックスは存在しない。したがって、ヒューリスティックは、先頭頂点の領域境界ｒからの残り目標値 ｔｖ´の最小偏差を返す。この最小偏差により、現在の探索プレフィクスを有する実現可能な最良の経路長さの決定が可能になる。すなわち、現在の探索プレフィクスの経路長さは最善の状態において、目標値プラスマイナス最小偏差に等しい経路長さを有しうる。
【００４６】
上記ヒューリスティックは、各頂点が単一の領域境界を割り当てられているパターンデータベースに関係するものであるが、このヒューリスティックは以下に示すように、各頂点が複数の領域境界（すなわち複数の間隔）を割り当てられているパターンデータベースを説明するように変形させてもよい。
【数８】
0005552382.tif 000009
本質的に、ヒューリスティックは上記と同じタスクを実行するが、 ｔｖ´が先頭頂点の領域境界のいずれかの内側にある場合にはゼロを返す。同様に、 ｔｖ´が領域境界のいずれかの内側にない場合には、ヒューリスティックは、 ｔｖ´に最も近い先頭頂点の領域境界からの ｔｖ´の最小偏差を返す。
【００４７】
ヒューリスティック値が決定されると、深さ優先探索は連結グラフを少なくとも２つの経路でトラバースし続けてもよい。まず、ゼロのヒューリスティック値が返されると、完全な解を提示するサフィックスが存在しうるが、これは未知である。これにより、深さ優先探索は、現在の探索プレフィクスに沿って連結グラフをトラバースし続けるとともに、対応するサフィックスを探求する。深さ優先探索がサフィックス探求を開始するとすぐに現在の探索プレフィクスが変化して、探求すべきサフィックスの新しい集合が潜在的に存在することは、理解されるべきである。第２に、正のヒューリスティック値が返される場合、完全な解を提示するサフィックスは存在しないので、現在の探索プレフィクスのサフィックスを探求する必要はない。しかしながら、完全な解は連結グラフ内の他の場所には存在しないかもしれないので、現在の探索プレフィクスがなお最良のプレフィクスである場合がある。したがって、現在の探索プレフィクスのヒューリスティック値がこれまでの現在探索プレフィクスのヒューリスティック値と比較される。現在の探索プレフィクスがこれまでの現在探索プレフィクスより小さい場合、現在の探索プレフィクスはこれまでの現在探索プレフィクスより良好な解を提示するので保存すべきである。
【００４８】
図７のフローチャート７００は、処理された各先頭頂点に関する深さ優先探索により実行される例示的ロジックを示す。最初に、深さ優先探索は、先頭頂点が目標頂点であるかどうかを確認する（ステップ７０２）。先頭頂点が目標頂点である場合、深さ優先探索は、残り目標値がゼロであるかどうかを確認する（ステップ７０４）。残り目標値は単に、現在の探索プレフィクスの経路長さから目標値を差し引いたものである。残り目標値がゼロである場合は、完全な解が見出されており、深さ優先探索を終了させることができる（ステップ７０６）。代替的に、深さ優先探索は連結グラフの残りを探索し続けるとともに他の完全な解を求め続けることが可能である。先頭頂点が目標頂点でありかつ残り目標値がゼロでないか、または先頭頂点が目標頂点でない場合、ヒューリスティック値がゼロであるかどうかが確認される（ステップ７０８）。もしそれがゼロである場合、完全な解が存在するかもしれないので、深さ優先探索は、現在の探索プレフィクスに沿って探索を続けなければならない（ステップ７１０）。しかし、ヒューリスティックが正の値を返す場合、現在の探索プレフィクスの目標値からの最良完了が得られる。したがって、現在の探索プレフィクスに沿って目標値を探索し続ける必要はない（ステップ７１２）。しかし、完全な解が見出されないかもしれないので、現在の探索プレフィクスがこれまで経験された最良の現在探索プレフィクスであるか否かを決定する必要がある（ステップ７１４）。よって、現在の探索プレフィクスがこれまで経験された最良の現在探索プレフィクスである場合、保存されなければならない（ステップ７１６）。さもなければ、現在の探索プレフィクスは廃棄してもよい（ステップ７１８）。前述の論議から、残り目標値は停止条件でないことが理解されるべきである。残り目標値がゼロということは、残り目標値がゼロの目標頂点を見出すことが、完全な解の発見と探索が終了可能であることとを意味するのみである。
【００４９】
前記ロジックがいかに実現されるかに関わらず、深さ優先探索は陽解または陰解のいずれかを返す。陽解は完了解、すなわち初期頂点から目標頂点まで延びる経路であり、かつ最適解である。最適解は実現可能な最良解である。陽解は完全解であってもよく、これは、現在の探索プレフィクスが目標頂点と等しい先頭頂点を有し、現在の探索プレフィクスの経路長さが目標値に等しい場合（すなわち陽解の経路長さが目標値に等しい場合）、深さ優先探索により返される。代替的に、完全解が存在しない場合、陽解を発見された最良のプレフィクスとしてもよい。これに対し陰解は未完了の解、すなわち初期頂点から目標頂点の先祖まで延びる経路であり、陽解がない場合に存在する。陰解は連結グラフをトラバースする間に発見された最良の解に対応しており、陽解の一部分を含むものである。深さ優先探索は、ヒューリスティックがゼロとなる連結グラフの経路を通ってトラバースするのみである。陽解が見出された場合、目標経路は完了のものであり、さらに行なうべきことはない。しかし、陰解が返された場合、目標経路は未完了であり、前記陰解をある陰解まで展開しなければならない。すなわち、プレフィクスを完成させるようなサフィックスを見出す必要がある。図６を参照すると、深さ優先探索が完了（ステップ６０４）した後、深さ優先探索により陰解が返されたか否かについて判定を行なわなければならない（ステップ６０６）。代替的に、このステップを実施せず、返された解をその種類（陽解または陰解）にかかわらず単に展開することも可能である。すなわち、すでに完了の陽解を展開したものが前記陽解となる。
【００５０】
深さ優先探索により陰解が返された場合、プレフィクスが展開される（ステップ６０８）。プレフィクスを展開して最良のサフィックスを求めるため、連結グラフに関する単純な最良優先探索が実施される。すなわち、最良プレフィクスの先頭頂点で始まり、ヒューリスティック値が最小の先頭頂点の子孫を付加することにより、最良プレフィクスの展開が開始される。すなわち、それぞれヒューリスティック値が０．１及び０．２の第１子孫及び第２子孫を先頭頂点が有する場合、第１子孫がプレフィクスに付加される。これにより、新たな先頭頂点が定義される。前記ステップは、目標頂点がプレフィクスに付加されるまで反復される。この時点で、陰解は目標経路に展開されている。この最良優先展開は、ｐｄが構築される方式により、heurが単調なゆえに機能する。すなわち、いかなるプレフィクスｐ及びその子孫p´に関しても、
【数９】
0005552382.tif 000010
が成立する。特に、いかなるプレフィクスｐ、heur（ｐ）＞０に関しても、等しいヒューリスティック値を有する少なくとも１つの直接の子孫が存することになり、これはｐの最適完了の一部分を表わすことを意味する。
【００５１】
前記ステップを用いるインプリメンテーションは、以下の擬似コードで実現される。以下に示すように、アルゴリズム１は本願の深さ優先目標値探索（ＤＦＴＶＳ）である。アルゴリズム１は連結グラフを設定し、ｖgに関するパターンデータベースを計算する。その後、アルゴリズム２の深さ優先探索を呼び出し、アルゴリズム２はｐｒｅopt、ｆopt、及びｔｖ´optを計算する。次にｐｒｅopt及び ｔｖ´optはアルゴリズム３の最良優先展開に与えられ、（必要な場合）ｐｒｅoptがｔｖｐに展開される。最後に、アルゴリズム１はｔｖｐ及びそのｔｖからの偏差を返す。
【００５２】
アルゴリズム２の深さ優先探索は、その深さ優先トラバーサルを終了させるべきかどうか、すなわち、ｐｒｅが目標頂点ｖgまでの経路であるか、盲領域（ｆ（ｐｒｅ）＞０）外の先頭までの経路であるかをまず確認する。さらにｐｒｅが現在のｐｒｅoptを支配している場合、ｐｒｅは後者になり代わる。そうでない場合、トラバーサルは続行され、反復して、ｖから発する各辺がｐｒｅに連結され、対応する目標値ｔｖ´が計算され、その後、それ自身への帰納的呼出しが行なわれる。この子孫が完全な目標値経路ｔｖｐを生成した場合、反復が終了してｖの残りの子孫の不要な探索が防止される。最後に、次の辺に備えてｐｒｅがその従来の値に戻される。
【００５３】
アルゴリズム３、展開手順の終了テストは、ｐｒｅが目標頂点ｖgで終わるか否かである。そうでない場合、ｐｒｅの最終頂点の最良外向辺及びその対応する目標値ｔｖ´が計算され、この辺がｐｒｅに連結され、それ自身が新しいｐｒｅ上に呼び出される。深さ優先探索により生成されたプレフィクスは陽解（ｖgで終わり完全なｔｖｐを表わす場合）または陰解のいずれかであり、その最良完了は最適解につながる。後者の場合、その最良のサクセッサによるｐｒｅの貪欲（ｇｒｅｅｄｙ）展開は目標値経路を十分に再構築しうる。
【００５４】
［アルゴリズム１］
【数１０】
0005552382.tif 000011
【００５５】
［アルゴリズム２］
【数１１】
0005552382.tif 000012
【００５６】
［アルゴリズム３］
【数１２】
0005552382.tif 000013
【００５７】
前述の論議を考慮すると、深さ優先目標値探索の様々な態様が図４、８の連結グラフに適用される。図４及び８の連結グラフに関し、パターンデータベースが計算され、各頂点に関する領域境界が対応する頂点の隣に示されている。図９において、破線枠により示されるプレフィクス内の各頂点にヒューリスティック値が与えられている。
【００５８】
図４においては、深さ優先目標値探索が、完全な解を返すシナリオに適用される。目標値８．５が望ましいと仮定すると、第１のステップは頂点ｖ0が目標頂点であるかどうかを確認することであり、残り目標値はゼロとなる。目標頂点ではないので、ｖ0に関するヒューリスティック値が決定される。ここで残り目標値は領域境界内となるので、ヒューリスティック値は０となる。したがって、トラバーサルは続行される必要がある。
【００５９】
確認すべき次の頂点は、頂点ｖ1である。この頂点は任意に選択され、頂点ｖ3及び頂点ｖ2も妥当な選択肢である。頂点ｖ1は目標頂点ではないので、ヒューリスティック値を計算することが必要になる。残り目標値は７．５であり、頂点ｖ1の領域境界内となるので、この場合のヒューリスティック値も０となる。したがって、トラバーサルは続行される必要がある。
【００６０】
確認すべき次の頂点は、再び任意に選択される頂点ｖ4である。頂点ｖ4は目標頂点ではないので、ヒューリスティック値が計算される。残り目標値は５．５であり、頂点ｖ4の領域境界外となるので、この場合のヒューリスティック値は２．５である。この時点で、頂点ｖ0、頂点ｖ1及び頂点ｖ4の現在探索プレフィクスでは、目標値プラスマイナス２．５よりも良好な経路長さを得られないことが分かる。したがって、現在の探索プレフィクスのサフィックスを探求する必要はない。
【００６１】
プレフィクスを通ってバックトラッキングすると、探求されていない子孫を有する次の頂点は、頂点ｖ1である。したがって、頂点ｖ3、すなわち頂点ｖ1の子孫が次に探求される。頂点ｖ3は目標頂点ではないので、ヒューリスティックが決定される。残り目標値は４．５であり、頂点ｖ3の領域境界内となるので、ヒューリスティックは０を返す。したがって、頂点ｖ3のサフィックスに関するさらなるトラバーサルが必要である。
【００６２】
頂点ｖ4は任意に選択され次に訪問される。頂点ｖ4は目標頂点ではないので、ヒューリスティック値が計算される。残り目標値は３であり、頂点ｖ4の領域境界内となるので、ヒューリスティックは０の値を返す。したがって、さらなるトラバーサルが必要である。
【００６３】
頂点ｖ6は、頂点ｖ4の唯一の子孫なので次に探求される。明らかなように、頂点ｖ6は目標頂点である。さらに、残り目標値は０なので、完全な解が見出されている。すなわち、頂点ｖ0、頂点ｖ3、頂点ｖ4及び頂点ｖ6で構成されるプレフィクスは、経路長さが目標値と等しい経路をもたらす。したがって、深さ優先探索を終了させ、現在の探索プレフィクスを陽解として返すことができる。
【００６４】
図８において、深さ優先目標値探索が、最良解を返すシナリオに適用される。目標値４．２５が望ましいと仮定すると、第１のステップは頂点ｖ0が目標頂点であるかどうか、また残り目標値が０であるかどうかを確認することである。明らかにこれら条件のどちらも満たされていないので、ｖ0に関するヒューリスティック値が決定される。ここで残り目標値は頂点ｖ0の領域境界内となるので、ヒューリスティック値は０となる。したがって、トラバーサルは続行される必要がある。
【００６５】
頂点ｖ1は、頂点ｖ0の唯一の子孫なので次に選択される。明らかに頂点ｖ0は目標頂点ではないので、ヒューリスティックが決定される。ここで、残り目標値は３．２５であり、頂点ｖ1の領域境界内となる。したがって、ヒューリスティックは０の値を返すことになり、連結グラフをトラバースし続ける必要がある。
【００６６】
頂点ｖ2は次に任意に選択される。頂点ｖ2は目標頂点ではなく、その残り目標値は２．２５である。頂点ｖ2は目標頂点ではないので、ヒューリスティックが決定される。残り目標値は頂点ｖ2の領域境界内には入らないので、ヒューリスティックは１．２５の最小偏差を返す。すなわち、現在のプレフィクスを用いて実現可能な最良の経路長さは、目標値プラスマイナス１．２５である。これは、これまで経験された最良のプレフィクスなので保存される。さらに、最良完了が知られているので、現在のプレフィクスに沿ってトラバースを続ける必要はない。このように、深さ優先探索は、確認されていない子孫を有する頂点、この場合、頂点ｖ1を発見するまでバックトラックを行なう。
【００６７】
頂点ｖ5は、頂点ｖ1の子孫なので次に任意に選択される。明らかに頂点ｖ5は目標ノードである。しかし、残り目標値は０．２５なので、現在のプレフィクスは完全な解ではない。したがって、ヒューリスティック値が決定され、明らかなように０．２５である。この最小偏差は頂点ｖ2の最小偏差より良好なので、現在のプレフィクスが保存され、連結グラフのトラバーサルが続行される。
【００６８】
任意に選択される次の頂点は頂点ｖ3である。頂点ｖ3は目標頂点ではなく、その残り目標値は１．２５である。したがって、ヒューリスティック値は０．７５である。この値は現在の最良プレフィクスのヒューリスティック値より大きいので、現在のプレフィクスを保存する必要はない。これにより、深さ優先探索は、連結グラフの残りを探索し続ける。
【００６９】
選択される最後の頂点は頂点ｖ4である。頂点ｖ4は目標頂点ではなく、その目標値は１．２５である。ヒューリスティックを決定すると、ヒューリスティック値１．７５が得られる。この値は再び現在の最良プレフィクスのヒューリスティック値より大きいので、現在のプレフィクスを保存する必要はない。さらに、連結グラフ全体が探索されているので、深さ優先トラバーサルは完了している。
【００７０】
深さ優先探索は不完全解にもかかわらず陽解で完了、すなわち完了解で完了した。したがって、解はすでに完全に展開されていて、目標経路が発見されている。
【００７１】
図９において、陰解の展開を説明する。前記で論じた深さ優先探索が、破線で囲まれたプレフィクスに等しい陰解を返すものとすると、陰解を展開することが必要になる。これを行なうため、先頭頂点の子孫が、ヒューリスティック値が最小の子孫を決定するために調査される。図９において、ヒューリスティック値が頂点ｖ3の子孫の隣に示されており、頂点ｖ6が最小のヒューリスティック値を有している。頂点ｖ6がプレフィクスに付加され、さらに目標頂点がプレフィクスに付加されるまで、上記手順が反復される。頂点ｖ6の唯一の子孫は頂点ｖ10なので、明らかに最小のヒューリスティック値を有している。したがってこの頂点がプレフィクスに付加され、それにより目標経路が完成する。
【００７２】
深さ優先目標値探索は、目標値に関して線形であるメモリ必要量をもつ。すなわち、従来のＡ＊方式とは異なり、メモリ必要量は目標値によって制限される。正の辺の値を仮定してＥ＞０をＣにおける最小の辺の値とすると、最悪でも、あるｔｖに関する目標値経路ｔｖｐは、
【数１３】
0005552382.tif 000014
の頂点から構成される。その結果、アルゴリズムの空間必要量はＯ（ｔｖ）である。さらに、最悪例の計算量はＣ内の頂点の数において指数関数的のままであるが、上記パターンデータベースを適用すると、深さ優先探索が探索空間を枝刈りまたは取り除くことが可能になり、その結果、実行時間における改善が得られる。
【００７３】
本願の深さ優先目標値探索について論じてきたが、以降、深さ優先目標値探索エンジンやモデルベース制御システムなどのシステムへの、その適用について論じるものとする。
【００７４】
図１０は、深さ優先目標値探索（ＤＦＴＶＳ）エンジン１０００を示す。ＤＦＴＶＳエンジン１０００は、コンピュータ１００８または、マイクロプロセッサ、マイクロコントローラ、グラフィックプロセシングユニット（ＧＰＵ）などのデジタルプロセッサ及び記憶装置を含む他のデジタル処理装置により適切に実現される。他の実施形態では、ＤＦＴＶＳエンジン１０００は、デジタルプロセッサを備えデジタルデータ記憶装置にアクセスを行なうサーバであってインターネットまたはローカルエリアネットワーク経由で適切にアクセスされるサーバ、またはデジタルプロセッサ及びデジタルデータ記憶装置を備える携帯情報端末（ＰＤＡ）により実現してもよい。コンピュータまたは他のデジタル処理装置は、ユーザ入力を受けてＤＦＴＶＳエンジン１０００を制御するためのキーボード１０１２など１以上のユーザ入力装置を適切に備えるか、それらに作用可能に接続され、またディスプレイ１０１０など１以上の表示装置をさらに備えるか、それらに作用可能に接続されている。他の実施形態では、ＤＦＴＶＳエンジン１０００を制御するための入力は、コンピュータ１００８上でＤＦＴＶＳエンジン１０００の前またはそれと同時に動作する別のプログラム、またはネットワーク接続などから受信される。同様に他の実施形態では、出力は、コンピュータ上でＤＦＴＶＳエンジン１０００の後またはそれと同時に動作する別のプログラムに対する入力として作用するか、またはネットワーク接続などを経由して伝送されてもよい。
【００７５】
ＤＦＴＶＳエンジン１０００は、パターンデータベースモジュール１００２と、深さ優先探索モジュール１００４と、解準備モジュール１００６とを有する。パターンデータベースモジュール１００２は、ＤＦＴＶＳエンジン１０００外部の供給源から連結グラフを受け取り、連結グラフに関するパターンデータベースを生成する。パターンデータベースは、好ましくは上記パターンデータベースを生成する改良された方法を用いて実現される。深さ優先探索モジュール１００４は、パターンデータベースモジュール１００２からパターンデータベース及び連結グラフを受け取る。深さ優先探索モジュール１００４はさらに、キーボード１０１２などの、ＤＦＴＶＳエンジン１０００外部の供給源から目標値を受け取る。深さ優先探索モジュール１００４は、受け取った目標値、パターンデータベース及び連結グラフを用いて、目標値に最も近似する経路長さを有する連結グラフ内の暗黙または明示の目標経路を求める。深さ優先探索モジュールは、本発明の例示的深さ優先目標値探索を用いて目標経路を探索する。解準備モジュール１００６は、深さ優先探索モジュール１００４から明示または暗黙の目標経路を受け取り、受け取った目標経路がさらなる処理を必要とするか否かを判定する。これは暗黙の目標経路を受け取った場合である。そのような場合、解準備モジュールは、上記深さ優先展開を用いて暗黙の目標経路を展開する。展開された暗黙の目標経路または明示の目標経路は、表示、印刷及び／またはプランナなどの付加的意志決定機構へのインプリメンテーションのため出力される。
【００７６】
実施形態によっては、本発明の上記例示的方法、この方法を採用するＤＦＴＶＳエンジンなどは、深さ優先目標値探索を実現するため（例えばデジタルプロセッサにより）実行可能な命令を記憶する記憶媒体により実現される。記憶媒体は、例えば、磁気ディスクまたは他の磁気記憶媒体、光学ディスクまたは他の光学的記憶媒体、ランダムアクセス記憶装置（ＲＡＭ）、読取り専用記憶装置（ＲＯＭ）、または他の電子記憶装置またはチップまたは作用可能に相互接続されたチップのセット、記憶された命令をインターネットまたはローカルエリアネットワーク経由で検索可能なインターネットサーバなどを含んでもよい。
【００７７】
図１１に進むと、ＤＦＴＶＳエンジンがシステム１１００に用いられている。システム１１００は、顧客１１０８から生産ジョブ１１０６を受け取る生産者要素１１０４を有する生産システム１１０２を含んでいる。生産システムは、１以上の計画１１１４に従って選択的に操作または運用可能な複数の資源１１１２を有するプラント１１１０をさらに有しており、顧客１１０８への提供のため１以上の製品１１１６を生産するようになっている。計画１１１４は、１以上の生産目標を達成するための一連の活動により構成される。生産者１１０４は、モデルベース制御システム１１２０の複数目標プランナ１１２２にジョブ及び目標１１１８を提供し、生産システム１１０２はプラント１１１０での実行のためプランナ１１２２から計画１１１４を受け取る。計画１１１４は、生産目標及び診断目標のうち一方または双方を含むことがある。
【００７８】
図１１に示すように、制御システム１１２０は、プラント１１１０のプラントモデル１１２４と、意見モデル１１２８を備える診断エンジン１１２８と、ＤＦＴＶＳモジュール１１３０とをさらに有する。診断エンジン１１２６は、プラント１１１０からの観測１１３４に対応する１以上の以前に実行された計画１１１４とモデル１１２４とに基づき、現在のプラント状態１１３２を判定及び更新する。また診断エンジン１１２６は、観測１１３４及びプラントモデル１１２４に基づき、１以上の実現可能な計画１１１４に関しプランナ１１２２に期待情報ゲインデータ１１３６を提供する。深さ優先目標値探索（ＤＦＴＶＳ）エンジン１１３０は、例示的深さ優先目標値探索を実現して、広範な診断を容易にする計画構築において複数目標プランナを補助する。
【００７９】
広範な診断の主要な目的は、診断エンジンの意見を用い、計画によってプラント１１１０の状態に関する付加的情報を得ることである。ある計画は診断エンジンの意見に情報を与える場合に有益であり、計画の結果には合理的な量の不確実性が伴う。モデルベース制御システム１１２０により、プラント状態１１３２及び／または期待情報ゲイン１１３６に従って、向上した診断情報を提供する計画の構築及び実行を通じた知的オンライン診断の選択的利用を伴う広範な診断が容易になる。さらにモデルベース制御システム１１２０により、少なくとも１つの診断目標及びプラント状態１１３２及び／または期待情報ゲイン１１３６に基づき、プラント１１１０で実行される１以上の専用診断計画の生成を伴う広範な診断が容易になることがある。このようにして、モデルベース制御システム１１２０は、生産目標及び診断目標を達成する計画を求めようとする。
【００８０】
図１１の実施形態はまた、コンピュータまたは他のプラットフォームの形態で実現されるオペレータインタフェース１１３８を有する。オペレータインタフェース１１３８は診断エンジン１１２６に作用可能に連結され、診断エンジン１１２６にオペレータ観測１１４０を与えるようになっており、診断エンジン１１２６は、あるインプリメンテーションでオペレータ観測１１４０に少なくとも部分的に基づき、現在のプラント状態１１３２を判定する。さらに、例示的なオペレータインタフェース１１３８により、オペレータは診断ジョブ記述言語１１４４を用いて診断ジョブ１１４２を定義することが可能になり、診断エンジン１１２６は生産者１１０４に診断ジョブ１１４６を提供してもよい。このインプリメンテーションにおける診断エンジン１１２６は、１以上の自己生成診断ジョブ１１４６及び／またはオペレータ定義診断ジョブ１１４２を生産者１１０４に選択的に提供するように動作し、生産者はプランナ１１２２にジョブ及び目標１１１８を提供する。
【００８１】
ＤＦＴＶＳエンジン１１３０に戻ると、エンジン１１３０は、プランナ１１２２に対する最適量の診断情報を生成するように動作する計画を返す。これを行なう際、エンジン１１３０は目標値問題に広範な診断の問題を写像する。ＤＦＴＶＳエンジン１１３０は、本願の例示的深さ優先目標値探索を用いて以下の式を解決するとともに、最適量の不確実性を有する計画を作成する。
【数１４】
0005552382.tif 000015
、ｐopt最適な計画に相当する。さらに、Ｐｒ（ａｂ（ｐ））は計画ｐの失敗確率であり、Ｔは最適な不確実性である。Ｐは最適計画ｐoptに関する目標を達成する１組の計画である。最適量の不確実性を有する計画は、最適量の情報を生成する計画である。
【００８２】
目標値問題に広範な診断の問題を写像するため、グラフ及び、このグラフに由来する連結グラフが構築される。このグラフの頂点はシステムの状態に対応しており、グラフの辺は作用に対応している。ある計画は複数の作用に対応している。さらに、辺重みは対応する辺（または作用）の失敗確率に対応しており、最適量の不確実性は目標値に対応している。
【００８３】
本願の深さ優先目標値探索は２つの仮定の成立を必要としている。すなわち、所与の時間にシステム内に多くて１つの誤りが存することと、ある作用が単一の計画内に多くて一度出現することである。もし、ある計画内に同じ作用が複数回出現する場合に、その計画の失敗確率は持続的な誤りの事例において増大することがないので、これら２つの仮定は必要であり、この問題は分解不可能である。すなわち、パターンデータベースは利用不可能である。しかし、もし、これら仮定が成立する場合は、本願の深さ優先目標値探索は、最適量の診断情報を生成する最適な計画に到達するであろう。
【符号の説明】
【００８４】
５００  パターンデータベースを生成する改良された方法、６００  方法、７００  フローチャート、１０００  深さ優先目標値探索（ＤＦＴＶＳ）エンジン、１１００  システム。
【図１】
0005552382.tif 000016
【図２】
0005552382.tif 000017
【図３】
0005552382.tif 000018
【図４】
0005552382.tif 000019
【図５】
0005552382.tif 000020
【図６】
0005552382.tif 000021
【図７】
0005552382.tif 000022
【図８】
0005552382.tif 000023
【図９】
0005552382.tif 000024
【図１０】
0005552382.tif 000025
【図１１】
0005552382.tif 000026