(57)【要約】      （修正有）【課題】設計アーキテクチャを再利用し、設計アーキテクチャの派生を自動生成する技術の提供。【解決手段】自動設計装置１００は、階層構造で表現されるシステムの設計アーキテクチャのグラフの可変ノードを書き換える書き換え規則の集合を格納する規則格納部１０５と、設計対象とするシステムの設計アーキテクチャの構成要素のグラフを探索木を用いて探索し、規則の適用対象とすべき可変ノードを順次決定する探索部１１０と、決定した可変ノードに対して、書き換え規則を適用可能であるか否かを判定する判定部１１５と、適用可能との判定結果に応答して、書き換え規則に従って、決定した可変ノードを、固定ノード又は前記可変ノードの少なくとも一方を含む部分グラフに書き換える規則適用部１２０とを含む。ここで探索部は、設計対象のグラフ内に未確定の可変ノードが存在しなくなるまで探索を繰り返し、可変ノードが見つからない場合はバックトラックする。【選択図】図１
2011013750.tif 000002
【特許請求の範囲】
【請求項１】
システムの構成要素の設計アーキテクチャを自動設計する自動設計装置であって、
階層構造で表現される前記システムの設計アーキテクチャのグラフの可変ノードを書き換える書き換え規則の集合を格納する規則格納部であって、前記書き換え規則は、設計済みの前記システムの設計アーキテクチャの書き換え可能な部分を可変ノード及び書き換え不可な部分を固定ノードとみなして記述されたものである、前記規則格納部と、
設計対象とする前記システムの設計アーキテクチャの構成要素のグラフ内に未確定の可変ノードが存在しなくなるまで、前記設計対象の前記構成要素のグラフを、該グラフに対応する探索木を用いて繰り返し探索することにより、書き換え規則の適用対象とすべき可変ノードを順次決定し、前記適用対象とすべき可変ノードが見つからない場合はバックトラックする探索部と、
決定した前記可変ノードに対して、前記規則格納部から書き換え規則を読み出し、該書き換え規則を適用可能であるか否かを判定する判定部と、
適用可能との判定結果に応答して、前記読み出した書き換え規則に従って、前記決定した可変ノードを、前記固定ノード又は前記可変ノードの少なくとも一方を含む部分グラフに書き換える規則適用部と、
を含む設計データ自動生成装置。
【請求項２】
前記探索部は、前記設計対象の構成要素のグラフを、前記探索木を用いて深さ優先で探索し、同一の深さに対しては左優先で探索する、請求項１に記載の設計データの自動設計装置。
【請求項３】
前記規則格納部に格納される各書き換え規則は、書き換え元となる可変ノードを識別するための書換元識別情報を含み、前記判定部は、前記決定した可変ノードを識別する前記書換元識別情報を含む１以上の書き換え規則を前記規則格納部から読み出す、請求項１に記載の設計データ自動生成装置。
【請求項４】
前記各書き換え規則に含まれる前記書換元識別情報は、ＸＰａｔｈを用いて書き換え元となる可変ノードを指し示し、前記判定部は、前記対応する探索木内にある、前記決定した可変ノードに対応するノードを指し示す前記書換元識別情報を含む１以上の書き換え規則を前記規則格納部から読み出す、請求項３に記載の設計データ自動生成装置。
【請求項５】
前記規則格納部に格納される各書き換え規則は、書き換え元となる可変ノードを識別するための書換元識別情報を含み、前記規則適用部は、一度使用した書き換え規則に該規則を適用した可変ノードの識別情報を含む使用済みのマークを付け、前記判定部は、前記規則格納部から、前記決定した可変ノードを識別する前記書換元識別情報を含み、かつ前記決定した可変ノードの識別情報を含む使用済みマークの付いていない１以上の書き換え規則を読み出す、請求項１に記載の設計データ自動生成装置。
【請求項６】
前記規則格納部に格納される各書き換え規則は、前記書き換え元の前記可変ノードと置き換えるべき、固定ノード又は可変ノードの少なくとも一方を含む部分グラフを示す部分グラフ情報を更に含み、前記規則適用部は、前記部分グラフ情報に従って前記決定した可変ノードを書き換える、請求項１に記載の設計データ自動生成装置。
【請求項７】
前記規則格納部に格納される各書き換え規則は、該書き換え規則を適用するための条件を示す適用条件を含み、前記判定部は、前記適用条件が満たされる場合に読み出した前記書き換え規則の適用が可能であると判定する、請求項１に記載の設計データ自動生成装置。
【請求項８】
前記各書き換え規則に含まれる前記適用条件は、該適用条件の判定対象となる可変ノードを識別するための判定対象識別情報と、固定ノード又は可変ノードの少なくとも一方を含む所定の部分グラフを示す部分グラフ条件とを含み、前記判定部は、前記判定対象識別情報を参照して前記設計対象の構成要素のグラフ内の可変ノードを識別し、該可変ノードと置き換えられた部分グラフと、前記部分グラフ条件により示される所定の部分グラフとをグラフマッチングしてマッチした場合に、読み出した前記書き換え規則の適用が可能であると判定する、請求項７に記載の設計データ自動生成装置。
【請求項９】
前記探索木は、前記設計対象の構成要素のグラフに含まれる全可変ノードをそのノードとし、前記設計対象の構成要素のグラフの階層構造に対応する木構造を有する、請求項１に記載の設計データの自動生成装置。
【請求項１０】
前記規則適用部は、前記決定した可変ノードの書き換えに応じて前記探索木を更新する、請求項１に記載の設計データ自動生成装置。
【請求項１１】
階層構造で表現されるシステムの設計アーキテクチャのグラフの可変ノードを書き換える書き換え規則の集合を記憶する記憶部へアクセス可能なコンピュータの計算処理により、前記システムの構成要素の設計アーキテクチャを自動設計する自動設計方法であって、前記書き換え規則は、設計済みの前記システムの設計アーキテクチャの書き換え可能な部分を可変ノード及び書き換え不可な部分を固定ノードとみなして記述されたものであり、前記自動設計方法は、
（ａ）設計対象とする、前記システムの設計アーキテクチャの構成要素のグラフを作業領域に記憶するステップと、
（ｂ）前記コンピュータの計算処理により、前記設計対象の前記構成要素のグラフを、該グラフに対応する探索木を用いて探索することにより、書き換え規則の適用対象とすべき可変ノードを決定し、該可変ノードに対応する前記探索木上のノードの位置を現在の探索位置として記憶するステップと、
（ｃ）前記記憶部から書き換え規則を読み出し、前記コンピュータの計算処理により、決定した前記可変ノードに対して、読み出した前記書き換え規則を適用可能であるか否かを判定するステップと、
（ｄ）適用可との判定結果に応答して、前記コンピュータの計算処理により、前記決定した可変ノードを、前記読み出した書き換え規則に従って、固定ノード又は可変ノードの少なくとも一方を含む部分グラフに書き換え、書き換え後の前記設計対象となる構成要素のグラフを前記作業領域に記憶するステップと、
（ｅ）前記設計対象となる構成要素のグラフ内に未確定の可変ノードが存在しなくなるまで、前記現在の探索位置を更新しながら前記ステップ（ｂ）乃至ステップ（ｄ）を繰り返すステップとを含み、ステップ（ｂ）において前記適用対象とすべき可変ノードが見つからない場合は、前記現在の探索位置を１つ前に戻ってバックトラックする、自動設計方法。
【請求項１２】
階層構造で表現される前記システムの設計アーキテクチャのグラフの可変ノードを書き換える書き換え規則の集合を記憶する記憶部へアクセス可能なコンピュータにおいて実行される、前記システムの構成要素の設計アーキテクチャを自動設計する自動設計プログラムであって、前記書き換え規則は、設計済みの前記システムの設計アーキテクチャの書き換え可能な部分を可変ノード及び書き換え不可な部分を固定ノードとみなして記述されたものであり、記自動設計プログラムは前記コンピュータに、
（ａ）設計対象とする、前記システムの設計アーキテクチャの構成要素のグラフを作業領域に記憶するステップと、
（ｂ）前記コンピュータの計算処理により、前記設計対象の前記構成要素のグラフを、該グラフに対応する探索木を用いて探索することにより、書き換え規則の適用対象とすべき可変ノードを決定し、該可変ノードに対応する前記探索木上のノードの位置を現在の探索位置として記憶するステップと、
（ｃ）前記記憶部から書き換え規則を読み出し、前記コンピュータの計算処理により、決定した前記可変ノードに対して、読み出した前記書き換え規則を適用可能であるか否かを判定するステップと、
（ｄ）適用可との判定結果に応答して、前記コンピュータの計算処理により、前記決定した可変ノードを、前記読み出した書き換え規則に従って、固定ノード又は可変ノードの少なくとも一方を含む部分グラフに書き換え、書き換え後の前記設計対象となる構成要素のグラフを前記作業領域に記憶するステップと、
（ｅ）前記設計対象となる構成要素のグラフ内に未確定の可変ノードが存在しなくなるまで、前記現在の探索位置を更新しながら前記ステップ（ｂ）乃至ステップ（ｄ）を繰り返すステップとを実行させ、前記自動設計プログラムは前記コンピュータに、ステップ（ｂ）において前記適用対象とすべき可変ノードが見つからない場合は、前記現在の探索位置を１つ前に戻ってバックトラックさせる、自動設計プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、階層構造で表現されるシステムの設計アーキテクチャを再利用して、システムの構成要素の新たなアーキテクチャをコンピュータ処理により自動で生成する技術に関する。
【背景技術】
【０００２】
電機・自動車等の製造業においては、開発資産の再利用によって派生製品の開発の生産性を向上させることが緊急の課題となっている。
【０００３】
例えば開発資産を再利用する従来技術として、特許文献1が存在する。特許文献１は、システムのモデルの作成に用いられるパラメタ、ツール、システムを構成する複数の部品についてのモデルテンプレートをそれぞれ記憶する記憶装置を設け、ユーザから入力された指示内容に応じて、複数の部品のモデルテンプレート及びパラメタを読み出し、複数の部品のモデルテンプレートにパラメタを付与することによって各部品のモデルを作成し、ツールを読み出して実行することにより複数の部品のモデルを組み合わせて１つのシステムのモデルを作成する技術を開示する。
【０００４】
開発資産を再利用する他の従来技術として、非特許文献１が存在する。非特許文献１は、可変なモデルフラグメントを、アノテーションを付けてベースモデルに重ねて記述しておき、ユーザに、重ねて記述された可変なモデルフラグメントから希望するモデルフラグメントを選択させ及びこれをベースモデルに合成して派生のモデルを生成する技術を開示する。
【０００５】
開発資産を再利用する更に他の従来技術として、非特許文献２が存在する。非特許文献２は、ベースモデルの変更可能な箇所をグラフ書き換え規則として予め表現して用意しておき、選択された規則でベースモデルを書き換えることにより派生のモデルを生成する技術を開示する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００６−３４３８５８号公報
【非特許文献】
【０００７】
【非特許文献１】K. Czarnecki, M. Antkiewicz, “MappingFeatures to Models: A Template Approach Based on Superimposed Variants”,Generative Programming and ComponentEngineering, 2005.
【非特許文献２】P. Jayaraman, J. Whittle, A. Elkhodary, H. Gomaa, “ModelComposition in Product Lines and Feature Interaction Detection Using CriticalPair Analysis”, Model Driven Engineering Languages and Systems, 2007
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら特許文献１の技術は、一部コンピュータによる計算処理を利用可能であるものの、既存のアーキテクチャをどのように組み合わせるかについては、人間にその選択を委ねている。また、特許文献１の技術では、組み合わせたものがシステムに課される要求を満たしていることの確認も人間が行う必要があり、設計アーキテクチャの再利用をより効率的に行うことができない。
【０００９】
一方非特許文献１や非特許文献２の技術は、コンピュータによる計算処理を利用可能である。しかし非特許文献１の技術は、１つのグラフにすべての可変点を重ねて表現するので、可変点が多くなったときに可読性悪くなり、追加や変更が難しい。このため大規模な設計アーキテクチャの再利用を効率的に行なうことができない。
【００１０】
また非特許文献２の技術は、書き換え規則の適用対象をグラフの具体的な構成要素（設計が確定した固定点として記述された頂点及びその属性、辺及びその属性）に限定している。そこでかかる限定を緩和し、書き換え規則の適用対象を、設計が未確定の可変点として記述される頂点に広げようとすると、書き換え規則の記述方法が複雑になり、また時間計算量が大きくなるという別の問題を生じてしまう。
【００１１】
この発明は、上記の問題点を解決するためになされたものであって、コンピュータの計算処理により設計アーキテクチャの再利用を効率的に行うことのできる技術を提供することを目的とする。また本発明は、設計が未確定の可変点を適用対象としたグラフ書き換え規則により派生アーキテクチャを導出する技術であって、書き換え規則の記述を簡潔にし、かつ時間計算量を少なくすることのできる技術を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記目的を達成する本発明は、次のような、システムの構成要素の設計アーキテクチャを自動設計する自動設計装置によって実現される。前記自動設計装置は、階層構造で表現される前記システムの設計アーキテクチャのグラフの可変部分を書き換える書き換え規則の集合を格納する規則格納部であって、前記書き換え規則は、設計済みの前記システムの設計アーキテクチャの書き換え可能な部分を可変ノード及び書き換え不可な部分を固定ノードとみなして記述されたものである、前記規則格納部と、前記システムの設計アーキテクチャの設計対象となる構成要素のグラフ内に未確定の可変ノードが存在しなくなるまで、前記設計対象の構成要素のグラフを、該グラフに対応する探索木を用いて繰り返し探索することにより、書き換え規則の適用対象とすべき可変ノードを順次決定し、前記適用対象とすべき可変ノードが見つからない場合はバックトラックする探索部と、決定した前記可変ノードに対して、前記規則格納部から書き換え規則を読み出し、該書き換え規則を適用可能であるか否かを判定する判定部と、適用可能との判定結果に応答して、前記読み出した書き換え規則に従って、前記決定した可変ノードを、固定ノード又は可変ノードの少なくとも一方を含む部分グラフに書き換える規則適用部とを備える。
【００１３】
なお、設計済みの前記システムの設計アーキテクチャの書き換え可能な部分を可変ノード及び書き換え不可な部分を固定ノードとみなして記述された前記書き換え規則は、人手により又は人手とコンピュータの計算処理により、作成されたものであってよい。
【００１４】
好ましくは前記探索部は、前記設計対象の構成要素のグラフを、前記探索木を用いて深さ優先で探索し、同一の深さに対しては左優先で探索する。
【００１５】
また好ましくは、前記規則格納部に格納される各書き換え規則は、書き換え元となる可変ノードを識別するための書換元識別情報を含む。そして、前記判定部は、前記決定した可変ノードを識別する前記書換元識別情報を含む１以上の書き換え規則を前記規則格納部から読み出す。
【００１６】
更に好ましくは、前記各書き換え規則に含まれる前記書換元識別情報は、ＸＰａｔｈを用いて書き換え元となる可変ノードを指し示す。そして、前記判定部は、前記対応する探索木内にある、前記決定した可変ノードに対応するノードを指し示す前記書換元識別情報を含む１以上の書き換え規則を前記規則格納部から読み出す。
【００１７】
また好ましくは、前記規則格納部に格納される各書き換え規則は、書き換え元となる可変ノードを識別するための書換元識別情報を含む。また前記規則適用部は、一度使用した書き換え規則に該規則を適用した可変ノードの識別情報を含む使用済みのマークを付ける。そして前記判定部は、前記規則格納部から、前記決定した可変ノードを識別する前記書換元識別情報を含み、かつ前記決定した可変ノードの識別情報を含む使用済みマークの付いていない１以上の書き換え規則を読み出す。
【００１８】
また好ましくは、前記規則格納部に格納される各書き換え規則は、前記書き換え元の前記可変ノードと置き換えるべき、固定ノード又は可変ノードの少なくとも一方を含む部分グラフを示す部分グラフ情報を更に含む。そして前記規則適用部は、前記部分グラフ情報に従って前記決定した可変ノードを書き換える。
【００１９】
また好ましくは、前記規則格納部に格納される各書き換え規則は、該書き換え規則を適用するための条件を示す適用条件を含む。そして前記判定部は、前記適用条件が満たされる場合に読み出した前記書き換え規則の適用が可能であると判定する。
【００２０】
更に好ましくは、前記各書き換え規則に含まれる前記適用条件は、該適用条件の判定対象となる可変ノードを識別するための判定対象識別情報と、固定ノード又は可変ノードの少なくとも一方を含む所定の部分グラフを示す部分グラフ条件とを含む。そして前記判定部は、前記判定対象識別情報を参照して前記設計対象の構成要素のグラフ内の可変ノードを識別し、該可変ノードと置き換えられた部分グラフと、前記部分グラフ条件により示される所定の部分グラフとをグラフマッチングしてマッチした場合に、読み出した前記書き換え規則の適用が可能であると判定する。
【００２１】
また好ましくは、前記探索木は、前記設計対象の構成要素のグラフに含まれる全可変ノードをそのノードとし、前記設計対象の構成要素のグラフの階層構造に対応する木構造を有する。
【００２２】
また好ましくは、前記規則適用部は、前記決定した可変ノードの書き換えに応じて前記探索木を更新する。
【００２３】
以上、システムの構成要素の設計アーキテクチャを自動設計する自動設計装置として本発明を説明した。しかし、本発明は、コンピュータの計算処理により、システムの構成要素の設計アーキテクチャを自動設計する自動設計方法、及びコンピュータにおいて実行される、システムの構成要素の設計アーキテクチャを自動設計する自動設計プログラムとして把握することもできる。
【発明の効果】
【００２４】
本発明によれば、設計済みのシステムの設計アーキテクチャの書き換え可能な部分を可変ノード及び書き換え不可な部分を固定ノードとみなして、設計済みのシステムの設計アーキテクチャから設計アーキテクチャのパターンを書き換え規則として記述し、設計アーキテクチャの派生の生成をグラフの書き換え問題として処理するので、コンピュータの計算処理により自動で派生アーキテクチャを導出できる。
【００２５】
また本発明によれば、書き換え規則の適用順が、設計対象の構成要素のグラフの木構造となるので、探索空間が限定され、現実的な計算量で書き換え規則の適用順を探索できる。その結果、トータルの時間計算量も大幅に少なくなる。更に、書き換え規則の適用順が、設計対象の構成要素のグラフの木構造となることで、書き換え規則の記述をシンプルなものにすることができる。本発明のその他の効果については、各実施の形態の記載から理解される。
【図面の簡単な説明】
【００２６】
【図１】図１は、本実施形態に係る自動設計装置１００の機能構成の一例を示す。
【図２】図２は、自動車ドアロックの設計アーキテクチャのグラフの一例を示す。
【図３】図３は、図２に示す設計アーキテクチャのグラフの階層構造を表すツリーを示す。
【図４】図４（ａ）は、書き換え規則の記述方法の一例を示す。図４（ｂ）は、書き換え規則の右辺の例を示す。図４（ｃ）は、書き換え規則の一例を示す。図４（ｄ）は、条件式付き書き換え規則の一例を示す。
【図５】図５（ａ）は、本実施例の規則格納部１０５に格納される書き換え規則の一例を示す。図５（ｂ）は、本実施例の規則格納部１０５に格納される書き換え規則の他の例を示す。図５（ｃ）は、本実施例の規則格納部１０５に格納される書き換え規則の他の例を示す。図５（ｄ）は、本実施例の規則格納部１０５に格納される書き換え規則の他の例を示す。
【図６】図６（ａ）は、自動車ドアロックのアーキテクチャのグラフの一例を示す。図６（ｂ）は、図６（ａ）に示すグラフを構成する階層ごとのグラフを示す。
【図７】図７（ａ）は、図６（ａ）に示すグラフの一部としてコンピュータ内で管理されるノード表の一例を示す。図７（ｂ）は、図６（ａ）に示すグラフの他の一部としてコンピュータ内で管理されるエッジ表の一例を示す。
【図８】図８（ａ）は、書き換え規則の例を示す。図８（ｂ）は、コンピュータ内で維持される、書き換え規則を管理する規則管理テーブルの一例を示す。
【図９】図９（ａ）は、書き換え規則８０２のノード表の一例を示す。図９（ｂ）は、書き換え規則８０２のエッジ表の一例を示す。
【図１０】図１０（ａ）は、書き換え開始時の設計対象のグラフの一例を示す。図１０（ｂ）は、図１０（ａ）に示すグラフに対応する探索木の一例を示す。図１０（ｃ）は、図１０（ｂ）に示す現在位置の矢印が示す可変ノードに適用可能な書き換え規則を示す。
【図１１】図１１（ａ）は、図１０（ａ）に示すグラフに図１０（ｃ）に示す書き換え規則を適用した後のグラフを示す。図１１（ｂ）は、図１１（ａ）に示すグラフに対応する探索木の一例を示す。図１１（ｃ）は、図１１（ｂ）に示す現在位置の矢印が示す可変ノードに適用可能な書き換え規則を示す。
【図１２】図１２（ａ）は、図１１（ａ）に示すグラフに図１１（ｃ）に示す書き換え規則を適用した後のグラフの一例を示す。図１２（ｂ）は、図１２（ａ）に示すグラフに対応する探索木の一例を示す。
【図１３】図１３（ａ）は、図１２（ａ）に示すグラフの状態からバックトラックした後のグラフの一例を示す。図１３（ｂ）は、図１３（ａ）に示すグラフに対応する探索木の一例を示す。図１３（ｃ）は、図１３（ｂ）に示す現在位置の矢印が示す可変ノードに適用可能な書き換え規則を示す。
【図１４】図１４（ａ）は、図１３（ａ）に示すグラフに図１３（ｃ）に示す書き換え規則を適用した後のグラフを示す。図１４（ｂ）は、図１４（ａ）に示すグラフに対応する探索木の一例を示す。図１４（ｃ）は、図１４（ｂ）に示す現在位置の矢印が示す可変ノードに適用可能な書き換え規則を示す。
【図１５】図１５（ａ）は、図１４（ａ）に示すグラフに図１４（ｃ）に示す書き換え規則を適用した後のグラフを示す。図１５（ｂ）は、図１５（ａ）に示すグラフに対応する探索木の一例を示す。
【図１６】図１６（ａ）は、図１５（ａ）に示すグラフに図５（ｃ）及び（ｄ）に示す複数の書き換え規則を適用した後のグラフを示す。図１６（ｂ）は、図１６（ａ）に示すグラフに対応する探索木の一例を示す。
【図１７】図１７は、本実施形態に係る設計アーキテクチャを自動設計する処理の流れの一例を示すフローチャートを示す。
【図１８】図１８は、本発明の実施形態に係るコンピュータ５０のハードウェア構成の一例を示す。
【発明を実施するための形態】
【００２７】
以下、本発明を実施するための最良の形態を図面に基づいて詳細に説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。なお、実施の形態の説明の全体を通じて同じ要素には同じ番号を付している。
【００２８】
図１は、本発明の実施形態に係る、システムの構成要素の設計アーキテクチャを自動設計する自動設計装置１００の機能構成の一例を示す図である。本発明の実施形態に係る自動設計装置１００は、規則格納部１０５と、探索部１１０と、判定部１１５と、規則適用部１２０と、派生データ格納部１２５とを備える。
【００２９】
規則格納部１０５は、階層構造で表現されるシステムの設計アーキテクチャのグラフの可変部分を書き換える書き換え規則の集合を格納する。本実施例に係る書き換え規則は、設計済みの階層構造で表現されるシステムの設計アーキテクチャの書き換え可能な部分を可変ノード及び書き換え不可な部分を固定ノードとみなして記述される。
【００３０】
ここで図２乃至図５を参照して、本実施例に係る書き換え規則を説明する。図２は、自動車ドアロックのアーキテクチャのグラフの一例を示す図である。一般にシステム設計のアーキテクチャは階層構造で表現することができる。階層構造による表現は種々の観点からなすことができ、例えば、仕事分けの階層や、企画、要求、設計、実装といった対象の詳細度の階層などがある。そこで本発明では、階層構造で表現されるシステムの設計アーキテクチャを、該設計アーキテクチャの書き換え可能な部分を可変ノード、書き換え不可な部分を固定ノードとみなすことにより、階層化されたシステムの設計アーキテクチャのグラフとして捉えた。
【００３１】
図２に示すグラフは、仕事仕分けの観点から階層化されたシステムの設計アーキテクチャを、書き換え可能な部分を可変ノード、書き換え不可な部分を固定ノードとみなすことにより、階層化されたシステムの設計アーキテクチャのグラフとして描いたものである。なお、図２において矩形は可変ノードを示し、楕円は固定ノードを示す。図２を見ると、内側の矩形ほどより具体的な設計アーキテクチャを示し、矩形間及び矩形と楕円との間の包含関係を、上位の階層の矩形で示された可変ノードを、包含関係にある下位の階層の矩形で示された可変ノード又は楕円で示された固定ノードに置き換える規則とみなすことが可能であることが分る。
【００３２】
図３に、図２に示すグラフの階層構造を示すツリーを示す。但し同図では簡単のため固定ノードを省略している。図３のツリーを見ると、図２に示すグラフの上下の階層のノード間の関係がより明確になる。ここで、例えば可変ノードＥＣＵ１と、その下の可変ノードＤｒｉｖｅｒＬｏｃｋ、ＰａｓｓｅｎｇｅｒＬｏｃｋ及びＲＭｇｒとの包含関係に注目する。すると該包含関係から、可変ノードＥＣＵ１を、３つの可変ノードＤｒｉｖｅｒＬｏｃｋ、ＰａｓｓｅｎｇｅｒＬｏｃｋ及びＲＭｇｒに書き換える書き換え規則を作成することが出来ることが分る。このように、本願発明では、複数の設計済みの階層構造で表現されるシステムの設計アーキテクチャを基にして、書き換え可能な部分を可変ノード及び書き換え不可な部分を固定ノードとみなすことで、設計アーキテクチャのパターンをグラフ書き換え規則として記述する。
【００３３】
具体的には、本実施例にかかる規則格納部１０５に格納される書き換え規則は、書き換え元となる可変ノードを識別するための書換元識別情報を含む。好ましくは、書換元識別情報は、ＸＰａｔｈを用いて書き換え元となる可変ノードを指し示す。また、書き換え規則は、書き換え元の可変ノードと置き換えるべき、固定ノード又は可変ノードの少なくとも一方を含む部分グラフを示す部分グラフ情報を含む。
【００３４】
また書き換え規則は、該書き換え規則を適用するための条件を示す適用条件を含んでもよい。好ましくは、適用条件は、該適用条件の判定対象となる可変ノードを識別するための判定対象識別情報と、固定ノード又は可変ノードの少なくとも一方を含む所定の部分グラフを示す部分グラフ条件とを含む。そして適用条件付きの書き換え規則は、適用条件の判定対象となる可変ノードが、部分グラフ条件が示す所定の部分グラフにグラフマッチすることを適用条件として要求する。このように記述される書き換え規則の記述方法の例を、図４に示す。
【００３５】
図４（ａ）は、書き換え規則の記述形式の一例を示す。図４（ａ）において、右辺Ｌは書換元識別情報を示し、左辺Ｒは書き換え元の可変ノードと置き換えられる部分グラフを示す。そして真ん中の矢印は、右辺Ｌが左辺Ｒに置き換えられることを示す。  図４（ｂ）は、ＸＰａｔｈを用いて書き換え元となる可変ノードを指定する書換元識別情報の例を示す。書換元識別情報４００は、現在位置からの相対パスにより、書き換え元となる可変ノードＥＣＵ１を指定する書換元識別情報である。
【００３６】
書換元識別情報４０２は、ルートＤｏｏｒＬｏｃｋからの絶対パスにより、書き換え元となる可変ノードＥＣＵ２を指定する書換元識別情報である。書換元識別情報４０４は、括弧で示される述部において書き換え規則を適用するための条件を示す、適用条件付きの書換元識別情報である。具体的には、書換元識別情報４０４は、ルートＤｏｏｒＬｏｃｋの下の可変ノードＥＣＵ１が、グラフパターンＧ１にマッチすることを適用条件とする、ルートＤｏｏｒＬｏｃｋからの絶対パスにより、書き換え元となる可変ノードＥＣＵ２を指定する書換元識別情報である。
【００３７】
図４（ｃ）及び（ｄ）は、本実施例に係る書き換え規則の例を示す。図４（ｃ）に示す書き換え規則は、現在位置から直接辿ることができる可変ノードＥＣＵ１を、グラフＧで書き換えることを指示する。図４（ｄ）に示す書き換え規則は、最上位の可変ノードＤｏｏｒＬｏｃｋから辿ることができるＥＣＵ１がグラフＧ２とマッチすることを条件に、最上位の可変ノードＤｏｏｒＬｏｃｋから辿ることができる可変ノードＥＣＵ２を、グラフＧ３で書き換えることを指示する。
【００３８】
図５は、規則格納部１０５に格納される書き換え規則の集合の一例を示す。図５に示す書き換え規則の集合は、複数の設計済みのシステムのアーキテクチャのグラフを基にして作成されたものである。なお、図５（ａ）乃至図（ｄ）に示す書き換え規則は、それぞれ異なる階層間の包含関係に基づいている。このように本発明では、グラフの可変性を書き換え規則の単位で独立して記述するので、非特許文献２におけるような可変点が多くなることによる可読性悪化の問題はなく、また追加や変更も書き換え規則の単位で容易に行うことができる。
【００３９】
探索部１１０は、システムの設計アーキテクチャの設計対象となる構成要素のグラフ内に未確定の可変ノードが存在しなくなるまで、設計対象の構成要素のグラフを、該グラフに対応する探索木を用いて繰り返し探索することにより、書き換え規則の適用対象とすべき可変ノードを順次決定する。なお、設計対象となる構成要素のグラフは、例えばキーボードやマウス等の入力装置や記録媒体読み込み装置、また通信インタフェースを介して、自動設計装置１００に提供できる。
【００４０】
また、対応する探索木は、設計対象の構成要素のグラフに含まれる全可変ノードをそのノードとし、設計対象の構成要素のグラフの階層構造に対応する木構造を有する探索木である。また好ましくは、探索部１１０は、設計対象の構成要素のグラフを、対応する探索木を用いて深さ優先で探索し、同一の深さに対しては左優先で探索する。
【００４１】
適用対象とすべき可変ノードが見つからない場合、探索部１１０は、バックトラックして１つ前のグラフ書き換えをキャンセルし、探索を１つ前の状態に戻す。バックトラックができない場合、即ち、キャンセルすべき１つ前のグラフ書き換えが無い場合は、派生アーキテクチャの導出は失敗となる。一方、構成要素のグラフ内に未確定の可変ノードが存在しなくなった場合、派生アーキテクチャの導出は成功となる。
【００４２】
一般的にグラフ書き換え（Ｇｒａｐｈ  Ｒｅｗｒｉｔｉｎｇ）では、書き換え規則の適用順序が計算量に直結する。そこで本発明は時間計算量を少なくするために、書き換え規則の適用順を、階層構造を有する設計対象となる構成要素のグラフの木構造に設定した。探索順を木構造とすることで、探索空間が限定され、現実的な計算量で書き換え規則の適用順を探索できる。なお、係る書き換え規則の適用順の採用により、先に説明した書き換え規則の記述、即ち、書き換え元となる可変ノードと、該可変ノードと置き換えるべき部分グラフを指示する、非常にシンプルな書き換え規則の記述が可能となることに留意されたい。
【００４３】
判定部１１５は、探索部１１０により決定された可変ノードに対して、規則格納部１０５から書き換え規則を読み出し、該書き換え規則を適用可能であるか否かを判定する。具体的には、判定部１１５は、決定した可変ノードを識別する書換元識別情報を含む１以上の書き換え規則を規則格納部１０５から読み出す。
【００４４】
なお、図４（ｂ）を参照して説明したように、規則格納部１０５に格納される書き換え規則に含まれる書換元識別情報は、ＸＰａｔｈを利用して相対パス又は絶対パスのいずれかにより書き換え元となる可変ノードを指定している可能性がある。そこで判定部１１５は、探索部１１０により決定された可変ノードを、設計対象の構成要素のグラフに対応する探索木を利用して相対パス及び絶対パスの両方で表現し、これと書き換え規則の右辺の書換元識別情報とが一致する規則を規則格納部１０５から読み出す。
【００４５】
なお、詳細は後述するが、本実施例では一度使用した書き換え規則は後述する規則適用部１２０により、該規則を適用された可変ノードの識別情報を含む使用済みのマークが付けられる。従って判定部１１５は、好ましくは探索部１１０により決定された可変ノードを識別する書換元識別情報を含む１以上の書き換え規則であって、かつ決定された可変ノードの識別情報を含む使用済みマークの付いていない書き換え規則を、規則格納部１０５から読み出す。
【００４６】
そして判定部１１５は、読み出した書き換え規則に、該書き換え規則を適用するための条件を示す適用条件が含まれているか否かを判定する。適用条件が含まれていない場合、判定部１１５は、該書き換え規則を、探索部１１０により決定された可変ノードに対して適用可能な書き換え規則であると判定する。
【００４７】
一方、読み出した書き換え規則に適用条件が含まれている場合、判定部１１５は、指定された適用条件が満たされることを条件に、探索部１１０により決定された可変ノードに対して読み出した書き換え規則の適用が可能であると判定する。なお、上述したように、本実施例に係る適用条件は、該適用条件の判定対象となる可変ノードを識別するための判定対象識別情報と、固定ノード又は可変ノードの少なくとも一方を含む所定の部分グラフを示す部分グラフ条件とを含む。
【００４８】
そこで判定部１１５は、判定対象識別情報を参照して設計対象の構成要素のグラフ内の可変ノードを識別する。そして判定部１１５は、識別した可変ノードと置き換えられた部分グラフと、部分グラフ条件により示される所定の部分グラフとをグラフマッチングし、マッチした場合に、探索部１１０により決定された可変ノードに対して読み出した書き換え規則の適用が可能であると判定する。なお、適用条件の判定対象となる可変ノードの識別も、書き換え元となる可変ノードの識別と同様にＸＰａｔｈを利用して識別できる。
【００４９】
ここで図６乃至図９を参照して、判定部１１５によるグラフマッチングの方法を説明する。そのためにまず、設計対象の構成要素のグラフ情報がどのようにしてコンピュータ内で管理されるかを、図６及び図７を参照して説明する。図６（ａ）は、３つの階層からなる自動車ドアロックのアーキテクチャのグラフの一例を示す。そして図６（ｂ）は、図６（ａ）に示すグラフを、階層ごとに分けて示したものである。図６（ｂ）を見ると分るように、３つの階層のグラフの間には、Ｇ１のグラフがＧ２のグラフに置き換えられ、Ｇ２のグラフがＧ３のグラフに置き換えられるという関係がある。このように階層構造で表現されるシステムの設計アーキテクチャのグラフのグラフ情報を、本実施例では図７に示すように、ノード情報とエッジ情報に分けて管理する。
【００５０】
図７（ａ）は、図６（ａ）に示すグラフの一部としてコンピュータ内で管理されるノード表の一例を示す。図７（ａ）を見ると分るようにノード表には、ノードごと、該ノードが属する階層に与えられたグラフ名、ノード名、可変ノード又は固定ノードの区別、及びノードが属する階層のグラフと置き換えられるグラフのグラフ名が登録される。
【００５１】
一方、図７（ｂ）は、図６（ａ）に示すグラフの他の一部としてコンピュータ内で管理されるエッジ表の一例を示す。図７（ｂ）を見ると分るようにエッジ表には、エッジごと、該エッジが属する階層に与えられたグラフ名、エッジ名、エッジの一端のノード名、及びエッジの他端のノード名が登録される。なお、エッジ名は該エッジが属する階層内において識別するために使用されるＩＤである。エッジ名ｅ４及びｅ５のそれぞれの他端のノード名も同様であり、エッジ名ｅ４及びｅ５の括弧はそのことを示す。
【００５２】
次に、書き換え規則がどのようにしてコンピュータ内で管理されるかを、図８及び図９を参照して説明する。図８（ａ）は、適用条件のない書き換え規則８００と、適用条件付きの書き換え規則８０２の例を示す。そして、図８（ｂ）は、図８（ａ）に示す書き換え規則を登録した、書き換え規則の表の一例を示す。本実施例では、書き換え規則は表を用いて管理され、表には、書き換え規則に割り当てた規則ＩＤと、文字列で表した書き換え規則とが登録される。
【００５３】
なお、適用条件でパターンマッチングに使用するグラフは、図６及び図７を参照して説明したのと同様の方法により管理する。そして、書き換え規則の表に適用条件付き書き換え規則を登録する場合には、グラフ部分はグラフ名に置き換える。例えば適用条件付きの書き換え規則８０２の適用条件に含まれるグラフＧ５は、図９（ａ）に示すノード表及び図９（ｂ）に示すエッジ表により管理し、書き換え規則の表には、「Ｇ５］のグラフ名を登録する。そして実際に書き換え規則を使用する際には、グラフ名をキーにしてノード表及びエッジ表から該当するグラフ情報を読み出す。なお、書き換え規則の表に登録する文字列の代わりに、該文字列を構文解析した結果を登録するようにしてもよい。
【００５４】
ここで再び図６乃至図９を参照して、判定部１１５によるグラフマッチングの方法を具体的に説明する。現在、設計対象の構成要素のグラフが図６（ａ）に示す状態にあり、探索部１１０により次に書き換え規則を適用すべき可変ノードとして、Ｄｏｏｒｌｏｃｋの下の可変ノードＥＣＵ２が決定されたとする。そして、判定部１１５は、可変ノードＥＣＵ２に対し、規則格納部１０５から図８（ａ）に示す書き換え規則８０２を読み出したとする。すると判定部１１５は、書き換え規則８０２の適用可能性を判定するため、適用条件「／Ｄｏｏｒｌｏｃｋ／ＥＣＵ１  〜  ＜Ｇ５＞」を検討する。
【００５５】
即ち、判定部１１５は、まず適用条件に含まれる判定対象識別情報／Ｄｏｏｒｌｏｃｋ／ＥＣＵ１を参照して、図７（ａ）に示すノード表からノード名がＤｏｏｒｌｏｃｋであるエントリを検索し、Ｄｏｏｒｌｏｃｋと置き換えられたグラフのグラフ名Ｇ２を得る。続いて判定部１１５は、同ノード表からグラフ名がＧ２であってノード名がＥＣＵ１のエントリを検索し、ＥＣＵ１と置き換えられたグラフのグラフ名Ｇ３を得る。そして最後に判定部１１５は、グラフＧ３とグラフＧ５をグラフマッチングする。  
【００５６】
グラフマッチングは、グラフＧ３とグラフＧ５の両グラフのノード表（図７（ａ）及び図９（ａ））及びエッジ表（図７（ｂ）及び図９（ｂ））を参照して、対応するノード及び対応するエッジを各々順に比較することにより行われる。好ましくは、グラフマッチングは、固定ノードを先にマッチさせ、その後可変ノードのマッチングを行う。これにより計算時間が短縮される。また、グラフマッチングは、マッチングするグラフ同士が完全に一致する場合だけでなく、適用条件に含まれる所定のグラフに、設計対象の構成要素のグラフ内の判定対象の可変ノードと置き換えられたグラフが包含される場合も、マッチしたと判断することができる。グラフＧ３とグラフＧ５のグラフマッチングは、グラフＧ３のエッジｅ４と、グラフＧ５のエッジｅ４‘の不一致により、最終的にマッチしないと決定される。
【００５７】
規則適用部１２０は、判定部１１５による適用可能との判定結果に応答して、読み出した書き換え規則に従って、探索部１１０により決定された可変ノードを、固定ノード又は可変ノードの少なくとも一方を含む部分グラフに書き換える。具体的には規則適用部１２０は、読み出した書き換え規則に含まれる部分グラフ情報に従って、該部分グラフ情報が示す部分グラフで、探索部１１０により決定された可変ノードを置き換える。
【００５８】
規則適用部１２０は書き換え規則を適用した場合、使用した書き換え規則に該書き換え規則を適用した可変ノードの識別情報を含む使用済みのマークを付ける。規則適用部１２０はまた、決定した可変ノードの書き換えに応じて、対応する探索木を更新する。具体的には対応する探索木において、探索部１１０により決定された可変ノードの下に、書き換えた部分グラフに含まれる可変ノードを子ノードとして追加する。
【００５９】
派生データ格納部１２５は、探索部１１０により、構成要素のグラフ内に未確定の可変ノードが存在しなくなったと判断された時点の設計対象の構成要素のグラフを格納する。なお、派生データ格納部１２５に格納されるグラフのグラフ情報は、図７（ａ）及び（ｂ）を参照して説明したように、ノード表とエッジ表とにより構成される。
【００６０】
次に図１１乃至図１６に示す図を参照しつつ、図１７に示す、本発明の実施形態に係る自動設計装置１００による自動設計処理の流れの一例を説明する。図１７において処理はステップ１００から開始し、探索部１１０は、可変ノードＧ０を１つ含む、設計対象の構成要素のグラフを受け取り、設計対象の構成要素のグラフに対応する探索木Ｔを、可変ノードＧ０をルート・ノードとして初期化する。なお、設計対象の構成要素のグラフが、複数の可変ノード、又は可変ノードと固定ノードとを含む複数のノードを含む場合、対応する探索木Ｔは、設計対象の構成要素のグラフの階層構造をその木構造とする、可変ノードのみからなる探索木Ｔとして初期化される。またステップ１００において探索部１１０は、探索木における探索位置Ｐをルート・ノードに初期化する。
【００６１】
次に探索部１１０は、書き換え規則を次に適用すべき、設計対象の構成要素のグラフ内の未確定の可変ノードを決定するために、探索木Ｔを深さ優先かつ左優先で探索する（ステップ１０５）。そして探索部１１０は、未確定の可変ノードがあるか否かを判定し（ステップ１１０）、未確定の可変ノードがない場合（ステップ１１０：ＮＯ）、処理は成功して終了する。ステップ１１０の判定を初めて行う場合、未確定の可変ノードは必ず見つかるため、ステップ１１０の判定はＹＥＳになり、探索部１１０は、探索した未確定の可変ノードをｖとして、可変ノードｖの情報を判定部１１５へ渡す（ステップ１１５）。
【００６２】
可変ノードｖの情報を受け取った判定部１１５は、規則格納部１０５に格納される書き換え規則の中に、可変ノードｖに適用可能な書き換え規則があるか否か判定する（ステップ１２０）。適用可能な書き換え規則がある場合（ステップ１２０：ＹＥＳ）、判定部１１５は、適用可能な書き換え規則の情報を規則適用部１２０へ渡す。
【００６３】
書き換え規則を受け取った規則適用部１２０は、設計対象の構成要素のグラフ内の探索された可変ノードｖ、言い換えると受け取った書き換え規則に含まれる書換元識別情報により識別される可変ノードｖを、受け取った書き換え規則に含まれる部分グラフ情報が示す部分グラフで置き換える（ステップ１２５）。
【００６４】
続いて規則適用部１２０は、対応する探索木Ｔの現在の探索位置Ｐのノードの下に、部分グラフ情報が示す部分グラフに含まれる全可変ノードを追加する（ステップ１３０）。規則適用部１２０はまた、適用した書き換え規則に該書き換え規則を適用した可変ノードの識別情報を含む使用済みのマークを付ける（ステップ１３５）。その後処理はステップ１０５へ戻り一連の処理を繰り返す。
【００６５】
ここでステップ１００からステップ１３５までの処理を、図１０乃至図１２を参照して説明する。なお規則格納部１０５には、図５（ａ）乃至（ｄ）に示す書き換え規則が格納されているとする。まず探索部１１０は、ステップ１００において、図１０（ａ）に示すグラフを設計対象の構成要素のグラフとして受け取るとする。すると該グラフに対応する探索木Ｔは、図１０（ｂ）に示す、可変ノードＤｏｏｒｌｏｃｋをルートとする探索木に初期化される。この際、現在の探索位置Ｐの初期値は、図１０（ｂ）に示すようにルート・ノードに設定される。
【００６６】
次にステップ１０５からステップ１１５までの処理を経て、探索部１１０は、探索木を深さ優先かつ左優先で探索し、ルート・ノードである可変ノードＤｏｏｒｌｏｃｋを未確定の可変ノードｖとして決定する。そしてステップ１２０において判定部１１５は、ルート・ノードである可変ノードＤｏｏｒｌｏｃｋに適用可能な書き換え規則として、可変ノードＤｏｏｒｌｏｃｋを識別する書換元識別情報を含む書き換え規則５００（図５（ａ）及び図１０（ｃ）参照）を規則格納部１０５から読み出す。
【００６７】
ステップ１２５において、書き換え規則５００は規則適用部１２０に渡され、規則適用部１２０は、書き換え規則５００を、現在の探索位置Ｐが指し示すルート・ノードのＤｏｏｒｌｏｃｋに対応するグラフ内のＤｏｏｒｌｏｃｋ（図１０（ａ）参照）に適用し、新たな設計対象の構成要素のグラフを得る（図１１（ａ）参照）。またステップ１３０において、規則適用部１２０は、現在の探索位置Ｐが指し示すルート・ノードのＤｏｏｒｌｏｃｋ（図１０（ｂ）参照）の下に、書き換え規則５００（図１０（ｃ）参照）に含まれる２つの可変ノードＥＣＵ１及びＥＣＵ２を追加し、探索木を更新する（図１１（ｂ）参照）。この際規則適用部１２０は、書き換え規則５００に該規則を適用した可変ノードのＤｏｏｒｌｏｃｋの識別情報を含む使用済みのマークを付ける。
【００６８】
その後処理はステップ１０５へ戻り、上記説明したのと同様の処理が繰り返される。即ち、探索部１１５は、更新後の探索木Ｔ（図１１（ｂ）参照）を用いて、深さ優先かつ左優先で次に書き換え規則の適用対象とすべき未確定の可変ノードｖを探索する。そして探索部１１５は、図１１（ｂ）に示すようにＤｏｏｒｌｏｃｋの下のＥＣＵ１を、次に書き換え規則を適用すべき未確定の可変ノードｖとして決定する。この際探索部１１５は、現在の探索位置ＰをＤｏｏｒｌｏｃｋの下のＥＣＵ１に更新する。
【００６９】
続いて判定部１１５は、規則格納部１０５から適用可能な書き換え規則として、可変ノードＥＣＵ１を識別する書換元識別情報を含む書き換え規則５０２を読み出す（図５（ｂ）及び図１１（ｃ）参照）。なお、未確定の可変ノードＥＣＵ１に適用可能な書き換え規則は、書き換え規則５０２の他に書き換え規則５０４もあるが、ここでは先に書き換え規則５０２が読み出されるものとする。そして規則適用部１２０は、現在の探索位置Ｐが指し示すＤｏｏｒｌｏｃｋの下のＥＣＵ１（（図１１（ｂ）参照）に対して書き換え規則５０２（図１１（ｃ）参照）を適用し、図１２（ａ）に示すグラフと、図１２（ｂ）に示す探索木を新たに得る。なお、書き換え規則５０２には該規則を適用した可変ノードのＤｏｏｒｌｏｃｋの下のＥＣＵ１の識別情報を含む使用済みのマークが付けられる。
【００７０】
再び図１７に示すフローチャートに戻って、次にステップ１２０において、可変ノードｖの情報を受け取った判定部１１５が、規則格納部１０５に格納される書き換え規則の中に、可変ノードｖに適用可能な書き換え規則がないと判定した場合（ステップ１２０：ＮＯ）を説明する。この場合、判定部１１５は処理を探索部１１０に戻す。処理を戻された探索部１１０は、バックトラック可能であるか否かを判定する（ステップ１４０）。
【００７１】
バックトラックは直前に行ったグラフ書き換えをキャンセルして１つ前の状態に戻すことであるため、探索部１１０は取り消すべきグラフ書き換えがあるか否かを判定する。取り消すべきグラフ書き換えが無い場合、探索部１１０はバックトラック不可と判定し（ステップ１４０：ＮＯ）、処理は失敗して終了する。一方取り消すべきグラフ書き換えが有る場合、探索部１１０は、１回前の書き換え規則適用の結果であるグラフの書き換えと、探索木の更新、即ち子ノードの追加を取り消す（ステップ１４５）。そして処理はステップ１０５へ戻り、一連の処理を繰り返す。
【００７２】
ここでステップ１２０からステップ１４５までの処理を、図１２乃至図１３を参照して説明する。なお現在の設計対象の構成要素のグラフ、及び該グラフに対応する探索木は各々図１２（ａ）、及び図１２（ｂ）に示す状態にあるとする。また、探索部１１０により探索が行われ、現在の探索位置ＰはＤｏｏｒｌｏｃｋの下のＥＣＵ２に更新されているものとする。判定部１１５は、探索部１１０から処理を渡され、Ｄｏｏｒｌｏｃｋの下のＥＣＵ２に適用可能な書き換え規則として、Ｄｏｏｒｌｏｃｋの下のＥＣＵ２を識別する書換元識別情報を含む書き換え規則５０６（図５（ｂ）参照）を規則格納部１０５から読み出す。
【００７３】
続いて判定部１１５は、読み出した書き換え規則５０６が条件付書き換え規則であることから、その述部に示される適用条件が、図１２（ａ）に示される現在の設計対象の構成要素のグラフにより満たされるか否かを判定する。即ち判定部１１５は、書き換え規則５０６の適用条件に含まれる判定対象識別情報を参照して、設計対象の構成要素のグラフ内の可変ノードＥＣＵ１を識別する。そして判定部１１５は、識別した可変ノードＥＣＵ１と置き換えられた部分グラフと、部分グラフ条件により示される所定の部分グラフとをグラフマッチングし、マッチするか否かを判定する。なお、グラフマッチングの具体的な方法は、図６乃至図９を参照して説明したのと同じであるため、繰り返しを避けるためここでは説明を省略する。
【００７４】
先に説明したように、この場合グラフマッチングは失敗するため、判定部１１５は処理を探索部１１０に戻し、探索部１１０は、バックトラック可能であるか否かを判定する。なおこの時点における設計対象の構成要素のグラフは、図１２（ａ）に示すグラフである。上述したように、図１２（ａ）に示すグラフは、コンピュータ内では、図７（ａ）に示すノード表と図７（ｂ）に示すエッジ表として維持されている。そこで探索部１１０は、図７（ａ）に示すノード表の置き換えられるグラフ名の欄を参照し、最後に行われた置換えがグラフＧ３であることを見つける。
【００７５】
即ち探索部１１０は、取り消すべき書き換えがあることからバックトラック可能と判断し、グラフＧ３の置き換えを取り消す。具体的には、図７（ａ）に示すノード表においてグラフ名がＧ３のエントリを削除し、グラフ名Ｇ２のエントリの「置き換えられるグラフ名」の欄の「Ｇ３］を、「未定」に変更する。また探索部１１０は、図１２（ｂ）に示す探索木において、１つ前に現在の探索位置ＰであったＥＣＵ１の子ノード２つを削除する。図１３（ａ）及び（ｂ）は、各々、バックトラック後の現在の設計対象の構成要素のグラフと探索木とを示す。なお、現在の探索位置Ｐは１つ戻ってＤｏｏｒｌｏｃｋの下のＥＣＵ１に更新される。そして再び一連の処理が繰り返される。
【００７６】
なお、図１３（ａ）に示す構成要素のグラフは、図１１（ａ）に示す構成要素のグラフと同じであるが、バックトラック後の処理では、図５（ｂ）に示す書き換え規則５０２は既に使用されており、可変ノードのＤｏｏｒｌｏｃｋの下のＥＣＵ１の識別情報を含む使用済みマークが付けられている。そのため、図１３（ａ）に示すグラフ内の未確定の可変ノードＥＣＵ１に対しては、適用可能な書き換え規則として、規則格納部１０５から未だ使用されていない書き換え規則５０４（図５（ｂ）及び図１３（ｃ）参照）が読み出される。そして書き換え規則５０４の適用の結果、図１４（ａ）に示す構成要素のグラフと、図１４（ｂ）に示す更新された探索木が得られる。そして再び、図１４（ａ）に示すグラフ内の未確定の可変ノードＥＣＵ２に対して、判定部１１５により書き換え規則５０６（図５（ｂ）及び図１４（ｃ）参照）が読み出され、書き換え規則５０６に含まれる適用条件が満たされるか否かが判定される。
【００７７】
図１４（ａ）に示すグラフでは、該グラフのＥＣＵ１と置き換えられたグラフと、書き換え規則５０６（図１４（ｃ）参照）の適用条件に含まれる所定のグラフとのグラフマッチングは成功するため、図１４（ａ）に示すグラフ内の未確定の可変ノードＥＣＵ２に対して、書き換え規則５０６（図１４（ｃ）参照）が適用される。そして書き換え規則５０６の適用の結果、図１５（ａ）に示す構成要素のグラフと、図１５（ｂ）に示す更新された探索木が得られる。
【００７８】
現在の構成要素のグラフが図１５（ａ）に示す状態になった後、図５（ｃ）及び（ｄ）に示される書き換え規則が、書き換え規則５０８、５１０、５１２、５１４、５１６、５１６、５１６、５１６の順に順次適用され、最終的に図１６（ａ）に示す構成要素のグラフが得られる。なおその際の対応する探索木を図１６（ｂ）に示す。このようにして、本発明では既存のアーキテクチャを書き換え規則として効率的に再利用して、派生のアーキテクチャを得る。なお、すべての可変ノードが確定した最終的なアーキテクチャは、探索部１１０によって派生データ格納部１２５に格納される。
【００７９】
図１８は、本発明の実施の形態による自動設計装置１００を実現するのに好適なコンピュータのハードウェア構成の一例を示した図である。コンピュータは、バス２に接続されたメインＣＰＵ（中央処理装置）１とメインメモリ４を含んでいる。ハードディスク装置１３、３０、およびＣＤ−ＲＯＭ装置２６、２９、フレキシブル・ディスク装置２０、ＭＯ装置２８、ＤＶＤ装置３１のようなリムーバブル・ストレージ（記録メディアを交換可能な外部記憶システム）がフレキシブル・ディスクコントローラ１９、ＩＤＥコントローラ２５、ＳＣＳＩコントローラ２７などを経由してバス２へ接続されている。
【００８０】
フレキシブル・ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭのような記憶メディアが、リムーバブル・ストレージに挿入される。これらの記憶メディアやハードディスク装置１３、３０、ＲＯＭ１４には、オペレーティング・システムと協働してＣＰＵ等に命令を与え、本発明を実施するためのコンピュータ・プログラムのコードを記録することができる。即ち、自動設計装置１００としてのコンピュータの上記説明した数々の記憶装置には、上記説明した書き換え規則、書き換え規則の適用条件に含まれる部分グラフのグラフ情報、結果として得られる派生の設計アーキテクチャ等のデータや、自動設計プログラムを格納できる。そして複数のコンピュータ・プログラムはメインメモリ４にロードされることによって実行される。コンピュータ・プログラムは圧縮し、また複数に分割して複数の媒体に記録することもできる。
【００８１】
コンピュータは、キーボード／マウス・コントローラ５を経由して、キーボード６やマウス７のような入力デバイスからの入力を受ける。コンピュータは、オーディオコントローラ２１を経由して、マイク２４からの入力を受け、またスピーカー２３から音声を出力する。コンピュータは、視覚データをユーザに提示するための表示装置１１に、グラフィックスコントローラ１０を経由して接続される。コンピュータは、ネットワーク・アダプタ１８（イーサネット（Ｒ）・カードやトークンリング・カード）等を介してネットワークに接続し、他のコンピュータ等と通信を行うことが可能である。
【００８２】
以上の説明により、本発明の実施の形態による自動設計装置１００を実現するのに好適なコンピュータは、通常のパーソナルコンピュータ、ワークステーション、メインフレームなどの情報処理装置、または、これらの組み合わせによって実現されることが容易に理解されるであろう。なお、上記説明した構成要素は例示であり、そのすべての構成要素が本発明の必須構成要素となるわけではない。
【００８３】
以上、実施形態を用いて本発明の説明をしたが、本発明の技術範囲は上記実施形態に記載の範囲には限定されない。上記の実施形態に、種々の変更または改良を加えることが可能であることが当業者に明らかである。従って、そのような変更または改良を加えた形態も当然に本発明の技術的範囲に含まれる。
【図１】
2011013750.tif 000003
【図２】
2011013750.tif 000004
【図３】
2011013750.tif 000005
【図４】
2011013750.tif 000006
【図５】
2011013750.tif 000007
【図６】
2011013750.tif 000008
【図７】
2011013750.tif 000009
【図８】
2011013750.tif 000010
【図９】
2011013750.tif 000011
【図１０】
2011013750.tif 000012
【図１１】
2011013750.tif 000013
【図１２】
2011013750.tif 000014
【図１３】
2011013750.tif 000015
【図１４】
2011013750.tif 000016
【図１５】
2011013750.tif 000017
【図１６】
2011013750.tif 000018
【図１７】
2011013750.tif 000019
【図１８】
2011013750.tif 000020