(57)【要約】【課題】遷移条件を含む状態マシン群から、効率的な計算アルゴリズムを用いて変更計画を作成できる変更計画システムを提供する。【解決手段】変更計画システム１０は、１または複数の状態マシンから構成される状態マシン群を、１または複数の状態を含む単一状態マシンに変換する状態マシン群変換部１１を含み、状態マシン内の状態を、状態マシン群に含まれる状態マシン以外の状態マシン内の状態が指定された遷移条件に従って他の状態に遷移させ、単一状態マシン内の状態は、状態マシン群内の全状態マシンの一状態に対応し、単一状態マシン内の状態を、状態マシン内の状態に所定の遷移をさせる時に従う遷移条件を満たしながら、所定の遷移により生じる全状態マシンの他の一状態に対応する他の状態に遷移させる。【選択図】図２３
2015215885.tif 000002
【特許請求の範囲】
【請求項１】
１または複数の状態マシンから構成される状態マシン群を、１または複数の状態を含む単一状態マシンに変換する状態マシン群変換部を含み、
前記状態マシン内の状態を、前記状態マシン群に含まれる前記状態マシン以外の状態マシン内の状態が指定された遷移条件に従って他の状態に遷移させ、
前記単一状態マシン内の状態は、前記状態マシン群内の全状態マシンの一状態に対応し、
前記単一状態マシン内の状態を、前記状態マシン内の状態に所定の遷移をさせる時に従う遷移条件を満たしながら、前記所定の遷移により生じる前記全状態マシンの他の一状態に対応する他の状態に遷移させる
ことを特徴とする変更計画システム。
【請求項２】
状態マシン内の状態を、複数の条件が組合せられた遷移条件に従って遷移させる
請求項１記載の変更計画システム。
【請求項３】
状態マシン群変換部は、単一状態マシン内の状態に、状態マシン群に含まれる各状態マシンの現在状態および要求状態を入力する
請求項１記載の変更計画システム。
【請求項４】
単一状態マシン内の状態が遷移させられる時の順序の基準である、１または複数の所定の遷移から構成される遷移順序を作成する経路探索部を含む
請求項１記載の変更計画システム。
【請求項５】
遷移条件によって関連付けられる複数の状態マシン内の状態それぞれの遷移間のみに順序性を付与することによって、全順序集合としての遷移順序を半順序集合としての遷移順序に変換する経路順序変換部を含む
請求項４記載の変更計画システム。
【請求項６】
状態が遷移させられるように誘発される可能性がない状態マシンを特定し、状態マシン群から前記状態マシンおよび前記状態マシンに関連する遷移条件を除去する状態マシン簡略化部を含む
請求項１記載の変更計画システム。
【請求項７】
状態マシン簡略化部は、単一状態マシン内の状態の中で、現在状態が遷移不可能な状態を除去する
請求項６記載の変更計画システム。
【請求項８】
１または複数の状態マシンから構成される状態マシン群を、１または複数の状態を含む単一状態マシンに変換する変更計画システムにおいて実行される変更計画方法であって、  前記状態マシン内の状態を、前記状態マシン群に含まれる前記状態マシン以外の状態マシン内の状態が指定された遷移条件に従って他の状態に遷移させ、
前記単一状態マシン内の状態は、前記状態マシン群内の全状態マシンの一状態に対応し、
前記単一状態マシン内の状態を、前記状態マシン内の状態に所定の遷移をさせる時に従う遷移条件を満たしながら、前記所定の遷移により生じる前記全状態マシンの他の一状態に対応する他の状態に遷移させる
ことを特徴とする変更計画方法。
【請求項９】
コンピュータで実行されるときに、
１または複数の状態マシンから構成される状態マシン群を、１または複数の状態を含む単一状態マシンに変換し、
前記状態マシン内の状態を、前記状態マシン群に含まれる前記状態マシン以外の状態マシン内の状態が指定された遷移条件に従って他の状態に遷移させ、
前記単一状態マシン内の状態は、前記状態マシン群内の全状態マシンの一状態に対応し、
前記単一状態マシン内の状態を、前記状態マシン内の状態に所定の遷移をさせる時に従う遷移条件を満たしながら、前記所定の遷移により生じる前記全状態マシンの他の一状態に対応する他の状態に遷移させる
変更計画プログラム
を記録した非一時的なコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、変更計画システム、変更計画方法および変更計画プログラムに関する。
【背景技術】
【０００２】
変更管理の目的は、あるシステムを変更する際に生じる、変更するシステムの管理者および変更作業者の手間と、変更するシステムの利用者への影響を少なくすることである。変更するシステムが、例えば、複数の部品から構成されるような複雑なシステムである場合、変更作業は複雑になる。変更作業が複雑になると、作業者の手間や、作業者の作業を監督する管理者の手間は増大する。その結果、システム利用者への影響も増大する。
【０００３】
特に、システムを構成する部品間に依存性が存在する場合、各部品に対する変更作業の順序が問題になるため、作業が複雑になりやすい。部品間の依存性は、例えば、部品Ａと部品Ｂがある場合、部品Ａが正しく機能するためには部品Ｂが正しく機能することが必要であるというような、２つの要素間の関係性である。
【０００４】
上記の例の場合、部品Ａは部品Ｂに依存するという。このような部品Ａと部品Ｂから構成されるシステムを構築する作業では、最初に部品Ｂを構築し、次に部品Ａを構築するというように、実施する作業に順序性が求められる。
【０００５】
このような依存性を考慮しつつ、システムの変更に必要な作業の計画を自動的に作成するシステムを変更計画システムと呼ぶ。ただし、本発明における変更計画システムは、各部品の現在の状態（現在状態）と、変更後の要求される状態（要求状態）とを入力データとして、必要な作業と適切な作業手順を導出するシステムである。変更計画システムでは、予め部品間の依存性に関する情報、および部品に対する作業に関する情報が定義されている。
【０００６】
上記の変更計画システムを用いることで、管理者は、複雑な変更作業の実施に効果的な作業手順を効率的に作成できる。また、作業者も、作成された効果的な作業手順に基づいて、効率的に作業を実施できる。その結果、変更されるシステムの利用者への影響も少なくなることが期待される。
【０００７】
このような変更計画システムに関して、既に多数の関連研究や関連製品が知られている。関連研究として、例えば、非特許文献１〜５に記載されている研究がある。また、関連製品として、例えば、非特許文献６〜９に記載されている製品がある。
【０００８】
上記の関連技術は、次の観点で大きく２種類に分類される。すなわち、一つの部品を現在状態から要求状態に変更するために必要な作業は、高々１回とすることを前提にしているか否かである。
【０００９】
例えば、全てソフトウェアで構成されているシステムを対象に作業を計画する場合や、専ら何もない状態からシステムの構築を始めるにあたって構築作業を計画する場合であれば、上記の前提を置く妥当性が期待される場合が多い。しかし、例えば以下のような事例において、上記の前提を置くと問題が生じるおそれがある。
【００１０】
あるミドルウェアＡを含むシステムを構築する作業を計画する場合を例にする。システムに含まれるミドルウェアＡは、一時ファイルＢに依存している。ミドルウェアＡが構築された後、一時ファイルＢは、除去されることが望ましい。
【００１１】
このようなシステムの構築で求められる作業手順は、「１．一時ファイルＢの設置」、「２．ミドルウェアＡの構築」、「３．一時ファイルＢの削除」である。この作業手順を採用すると、一時ファイルＢに対する作業が２回求められる。すなわち、採用された作業手順は、上記の前提から逸脱している。
【００１２】
非特許文献３、６に記載されている研究や製品は、上記の前提に則っている。よって、非特許文献３、６に記載されている研究や製品を使用した場合、作業者は、上記の作業手順に従ってシステムを構築できない。上記の作業手順に従ってシステムを構築する場合、追加的なプログラムの指定が求められる。すなわち、研究や製品の本来の利用方法から逸脱した方法による対処が求められる。
【００１３】
非特許文献１、２、４、５に記載されている研究は、上述したような制約なしに、システム変更計画を作成できる。すなわち、本来の利用方法から逸脱した方法による対処なしに、一つの部品に対する作業が１回であるシステム変更計画を作成できる。
【００１４】
しかし、非特許文献１、２、４に記載されている研究では、作業の定義の仕方が複雑であることが問題になる。非特許文献１、２、４に記載されている研究において、作業は、部品とは別に定義される。作業の定義内容は、複数の部品や、部品の状態に影響する。
【００１５】
非特許文献６に記載されている製品であれば、作業は、特定の部品と結びついた形で定義される。また、定義される作業は、特定の部品の状態を変更する作業に限定される。非特許文献６に記載されている作業の定義の仕方と比較すると、非特許文献１、２、４に記載されている作業の定義の仕方は、一つの作業に対する定義内容が多く、複雑である。
【００１６】
非特許文献１、２、４に記載されている作業の定義の仕方は、定義内容に基づいた変更計画を作成する際の計算方法が複雑になりやすいことと、定義内容の再利用可能性が低いことが問題になる。定義内容の再利用可能性が低くなる理由は、多くの部品に影響する作業の定義内容は、影響される多くの部品を同時に必要とする変更要求を処理する場合にしか利用されないためである。
【００１７】
また、非特許文献５には、管理対象のシステムを複数の状態マシン群として定義する方法が記載されている。非特許文献５に記載されている方法では、各状態マシン群が持つ遷移の遷移条件は、遷移が含まれる状態マシン以外の状態マシン内の状態を用いて記述される。
【００１８】
状態マシンは、システムを構成する部品を表す。状態マシン内の状態は、部品がとり得る状態を表す。また、遷移には、部品の状態を変更する際の作業の情報が含まれる。遷移条件は、遷移に含まれる情報に対応する作業が持つ依存性を表す。
【００１９】
以上のようなシステムの定義方法に基づく変更計画は、計画可能な状況が広範である点や、定義が再利用可能な点において、他の手法を用いた変更計画よりも有効であると期待される。本発明において、上記の定義方法に基づくシステムが対象のシステムになる。以下、対象になるシステムを単に変更計画システムと呼ぶ。
【００２０】
状態マシン群として記述されたシステムの変更計画は、全ての状態マシンが現在状態を持ち、少なくとも一つの状態マシンが要求状態を持つとき、遷移条件を満たしつつ要求状態が指定された全ての状態マシンを現在状態から要求状態に遷移させる遷移順序を求めることによって作成される。非特許文献５には、このような変更計画の作成方法が記載されている。
【先行技術文献】
【非特許文献】
【００２１】
【非特許文献１】A. Keller, J. Hellerstein, J. Wolf, K.-L. Wu, and V. Krishnan, “Thechamps system: change management with planning and scheduling,” inNetwork Operations and Management Symposium, 2004. NOMS 2004.IEEE/IFIP, vol. 1, April 2004, pp. 395-408 Vol.1.
【非特許文献２】K. El Maghraoui, A. Meghranjani, T. Eilam, M. Kalantar, and A. V.Konstantinou, “Model driven provisioning: Bridging the gap betweendeclarative object models and procedural provisioning tools,” in Proceedingsof the 7th ACM/IFIP/USENIX International Conference onMiddleware, ser. Middleware’06. Berlin, Heidelberg: Springer-Verlag,2006, pp. 404-423.
【非特許文献３】T. Eilam, M. Elder, A. Konstantinou, and E. Snible, “Pattern-basedcomposite application deployment,” in Integrated Network Management(IM), 2011 IFIP/IEEE International Symposium on, 2011, pp. 217-224.
【非特許文献４】U. Breitenb¨ucher, T. Binz, O. Kopp, and F. Leymann, “Pattern-basedRuntime Management of Composite Cloud Applications,” in Proceedingsof the 3rd International Conference on Cloud Computing andService Science, CLOSER 2013. SciTePress Digital Library, May 2013,Conference Paper.
【非特許文献５】S. Hagen and A. Kemper, “Model-based planning for state-relatedchanges to infrastructure and software as a service instances in largedata centers,” in Cloud Computing (CLOUD), 2010 IEEE 3rd InternationalConference on, July 2010, pp. 11-18.
【非特許文献６】puppet labs,“Learning Puppet,” 2013, pp. 1-76.
【非特許文献７】"An Overview of Chef"、［online］、CHEF DOCUMENTS、［平成 26年 7月 15日検索］、インターネット〈 URL：http://docs.opscode.com/chef_overview.html〉
【非特許文献８】I. Redbooks, Virtualization With IBM Workload Deployer: Designingand Deploying Virtual Systems. Vervante, 2011.
【非特許文献９】T. Binz, G. Breiter, F. Leyman, and T. Spatzier, “Portable cloud servicesusing tosca,” Internet Computing, IEEE, vol. 16, no. 3, pp. 80-85, 2012.
【発明の概要】
【発明が解決しようとする課題】
【００２２】
非特許文献５に記載されている技術の計算アルゴリズムには、最適解を発見するための計算手順が非効率である点や、解が存在しても求まらない場合がある点などの問題点がある。
【００２３】
非特許文献５に記載されている計算アルゴリズムは、遷移条件を満たす実施可能な遷移をランダムに試行し、失敗した場合にはやり直すというトライアンドエラーを計算の基本方法にしている。よって、無駄な探索を繰り返してしまうために、計算手順が非効率になる。
【００２４】
また、存在する解が求まらない場合がある理由は、計算アルゴリズムが、計算の効率化のために所定の基準に基づいて、最適でないと予測される解の探索ケースを省略するためである。
【００２５】
そこで、本発明は、遷移条件を含む状態マシン群から、効率的な計算アルゴリズムを用いて変更計画を作成できる変更計画システム、変更計画方法および変更計画プログラムを提供することを目的とする。
【課題を解決するための手段】
【００２６】
本発明による変更計画システムは、１または複数の状態マシンから構成される状態マシン群を、１または複数の状態を含む単一状態マシンに変換する状態マシン群変換部を含み、状態マシン内の状態を、状態マシン群に含まれる状態マシン以外の状態マシン内の状態が指定された遷移条件に従って他の状態に遷移させ、単一状態マシン内の状態は、状態マシン群内の全状態マシンの一状態に対応し、単一状態マシン内の状態を、状態マシン内の状態に所定の遷移をさせる時に従う遷移条件を満たしながら、所定の遷移により生じる全状態マシンの他の一状態に対応する他の状態に遷移させることを特徴とする。
【００２７】
本発明による変更計画方法は、１または複数の状態マシンから構成される状態マシン群を、１または複数の状態を含む単一状態マシンに変換する変更計画システムにおいて実行される変更計画方法であって、状態マシン内の状態を、状態マシン群に含まれる状態マシン以外の状態マシン内の状態が指定された遷移条件に従って他の状態に遷移させ、単一状態マシン内の状態は、状態マシン群内の全状態マシンの一状態に対応し、単一状態マシン内の状態を、状態マシン内の状態に所定の遷移をさせる時に従う遷移条件を満たしながら、所定の遷移により生じる全状態マシンの他の一状態に対応する他の状態に遷移させることを特徴とする。
【００２８】
本発明による変更計画プログラムを記録した非一時的なコンピュータ読み取り可能な記録媒体は、コンピュータで実行されるときに、１または複数の状態マシンから構成される状態マシン群を、１または複数の状態を含む単一状態マシンに変換し、状態マシン内の状態を、状態マシン群に含まれる状態マシン以外の状態マシン内の状態が指定された遷移条件に従って他の状態に遷移させ、単一状態マシン内の状態は、状態マシン群内の全状態マシンの一状態に対応し、単一状態マシン内の状態を、状態マシン内の状態に所定の遷移をさせる時に従う遷移条件を満たしながら、所定の遷移により生じる全状態マシンの他の一状態に対応する他の状態に遷移させる変更計画プログラムを記憶する。
【発明の効果】
【００２９】
本発明によれば、遷移条件を含む状態マシン群から、効率的な計算アルゴリズムを用いて変更計画を作成できる。
【図面の簡単な説明】
【００３０】
【図１】本発明による変更計画システムの第１の実施形態の構成例を示すブロック図である。
【図２】状態マシン群の概念を示す説明図である。
【図３】状態マシン群のテキストによる定義の一例を示す説明図である。
【図４】OR条件による遷移条件の定義の一例を示す説明図である。
【図５】AND条件による遷移条件の定義の一例を示す説明図である。
【図６】状態マシン群の変換結果の一例を示す説明図である。
【図７】変更計画システム１００による状態マシン群の変換処理の動作を示すフローチャートである。
【図８】変更計画システム１００による状態の生成処理および遷移の生成処理の動作を示すフローチャートである。
【図９】状態と遷移の生成過程の一例を示す説明図である。
【図１０】変更計画システム１００による遷移の除去処理の動作を示すフローチャートである。
【図１１】本発明による変更計画システムの第２の実施形態の構成例を示すブロック図である。
【図１２】並列化可能なタスクを含む状態マシン群の一例を示す説明図である。
【図１３】全順序集合としての遷移順序生成結果の一例を示す説明図である。
【図１４】半順序集合としての遷移順序生成結果の一例を示す説明図である。
【図１５】変更計画システム１００による変更計画処理の動作を示すフローチャートである。
【図１６】遷移順序変換部１０３による遷移順序変換処理の動作を示すフローチャートである。
【図１７】本発明による変更計画システムの第３の実施形態の構成例を示すブロック図である。
【図１８】簡略化可能な状態マシン群の一例を示す説明図である。
【図１９】簡略化可能な状態マシンの一例を示す説明図である。
【図２０】変更計画システム１００による変更計画処理の動作を示すフローチャートである。
【図２１】状態マシン簡略化部１０４による状態マシン群の簡略化処理の動作を示すフローチャートである。
【図２２】状態マシン簡略化部１０４による遷移が誘発される可能性がある状態マシンの判定処理の動作を示すフローチャートである。
【図２３】本発明による変更計画システムの概要を示すブロック図である。
【発明を実施するための形態】
【００３１】
実施形態１．
［構成の説明］
以下、本発明の第１の実施形態を、図面を参照して説明する。図１は、本発明による変更計画システムの第１の実施形態の構成例を示すブロック図である。図１に示す変更計画システム１００は、状態マシン群変換部１０１を含む。
【００３２】
状態マシン群変換部１０１は、１または複数の状態マシンから構成される状態マシン群を、単一の状態マシンに変換する機能を有する。状態マシン群変換部１０１は、変更計画システム１００の外部に存在する入出力部２０１と、通信ネットワークなどを介して通信可能に接続されている。
【００３３】
状態マシン群変換部１０１は、入出力部２０１を介して入力された状態マシン群を受信する。状態マシン群変換部１０１は、受信した状態マシン群を単一の状態マシンに変換する。状態マシン群変換部１０１は、変換した単一の状態マシンを、入出力部２０１に送信する。
【００３４】
本実施形態における状態マシン群は、管理対象になるシステム、および管理対象になるシステムに対する変更要求に対応する。状態マシン群は、１または複数の状態マシンから構成される。状態マシンは、システムを構成する部品を示す。
【００３５】
状態マシンは、複数の状態をとりうる。状態は、同一状態マシン内の他の状態に遷移可能である。状態マシンには、必ず一つの現在状態があり、状態マシンは、任意個（０でもよい。）の要求状態に遷移可能である。すなわち、状態マシンは、複数の状態を含むといえる。
【００３６】
ただし、要求状態が複数指定された場合、要求状態は、指定されたいずれかの状態であればよい。要求状態が指定されない場合、要求状態は、どの状態でもよい。また、遷移の遷移条件は、遷移が含まれる状態マシン以外の状態マシン内の状態によって指定される。
【００３７】
図２は、状態マシン群の概念を示す説明図である。図２において、状態マシンを長方形で表す。また、状態を楕円形で表す。また、遷移を実線の矢印で表す。また、遷移条件を点線の矢印で表す。また、現在状態を破線の楕円形で表す。また、要求状態を黒塗りの楕円形で表す。また、遷移を示す矢印の途中に存在する丸印は、遷移条件の矢印の始点を示す。他の図においても、図２と同じ方法で状態マシンなどが示される。
【００３８】
図２は、"e1"と"e2"の２つの状態マシンから構成される状態マシン群を示す。"e1"と"e2"は、共に"s1"と"s2"の２つの状態を含む。
【００３９】
図２に示すように、"e1"における"s1"は、"s2"への遷移を含む。また、"e2"における"s1"と"s2"は、互いの状態への遷移を含む。また、"e2"の"s1"から"s2"への遷移は、"e1"の状態"s2"を遷移条件にする。また、"e1"は、"s1"を現在状態にする。また、"e2"は、"s1"を現在状態にし、"s2"を要求状態にする。
【００４０】
以下、便宜的に、例えば、状態マシン"e1"の状態"s1"のことを"e1(s1)"と記載する。また、状態マシン"e1"の状態"s1"から状態"s2"への遷移を、"e1(s1,s2)"と記載する。
【００４１】
図３は、状態マシン群のテキストによる定義の一例を示す説明図である。図３は、XML(Extensible Markup Language)形式を用いた表現の一例として、図２に示す状態マシン群の定義例を示す。
【００４２】
図３に示すように、例えば、状態マシンは、"stateMachine"タグによって表される。また、状態マシンのIDは、"stateMachine"の"id"属性によって表される。また、状態マシンが持つ状態は、"stateMachine"タグの子要素としての"state"タグによって表される。また、状態のIDは、"state"の"id"属性によって表される。
【００４３】
また、図３に示すように、状態が持つ遷移は、"state"タグの子要素としての"transition"タグによって表される。また、遷移先の状態を示すIDは、"transition"の"to"属性によって表される。
【００４４】
また、図３に示すように、遷移が持つ遷移条件は、"transition"タグの子要素としての"conditions"タグによって表される。遷移が状態マシン"e1"の状態"s2"を遷移条件にする場合、遷移条件は、"conditions"タグの子要素として"depends"タグを記述し、"depends"の"on"属性に"e1(s2)"を記述することによって表される。一つの遷移が複数の遷移条件を持つ場合、複数の遷移条件を記述するには、"conditions"タグの子要素として複数の"depends"タグを記述すればよい。
【００４５】
また、２つ以上の状態のいずれかに指定される、または、２つ以上の状態全てに同時に指定されるような、より複雑な遷移条件を設けるには、例えば、"or"タグや"and"タグの子要素として、複数の状態に対する遷移条件を記述すればよい。
【００４６】
複数の状態に対する遷移条件を記述した例を図４および図５に示す。図４は、OR条件による遷移条件の定義の一例を示す説明図である。図４は、状態マシン"e1"が状態"s1"、または状態"s2"のいずれかであるときに遷移条件が成り立つことを示す。
【００４７】
図５は、AND条件による遷移条件の定義の一例を示す説明図である。図５は、状態マシン"e1"が状態"s2"であり、かつ状態マシン"e3"が状態"s2"であるときに遷移条件が成り立つことを示す。
【００４８】
本実施形態における状態マシン群に基づくシステムの変更計画の作成は、常に全ての遷移条件を満たしつつ、要求状態が指定された全ての状態マシンの状態を現在状態から要求状態へ遷移させるような遷移順序を発見することによって達成される。図２に示す状態マシン群の例であれば、"(e1(s1,s2), e2(s1,s2))"という遷移順序が、最も単純な唯一の解になる。
【００４９】
このような遷移順序は、システムを構成する状態マシンの数が少ない単純なシステムの場合、容易に発見される。しかし、多くの状態マシンと、状態および遷移する状態と、遷移条件とを含む複雑なシステムの場合、遷移順序の発見は困難である。
【００５０】
そこで、本実施形態の変更計画システムは、複数の状態マシンを単一の状態マシンに変換する。単一の状態マシンに変換することによって、変更計画システムは、遷移順序の発見を容易にすることを目的とする。
【００５１】
図６は、状態マシン群の変換結果の一例を示す説明図である。図６は、図２に示す状態マシン群を単一の状態マシン"eX"に変換した結果を示す。変換後の状態マシンの各状態は、変換前の全ての状態マシンの各状態のあらゆる組合せから構成される。
【００５２】
図２に示すように、変換前の状態マシン群には"e1"と"e2"の２つの状態マシンが含まれている。また、"e1"と"e2"それぞれが、"s1"と"s2"の２つの状態を含んでいる。
【００５３】
図６に示すように、変換後の状態マシン"eX"は、"e1(s1),e2(s1)"と、"e1(s1),e2(s2)"と、"e1(s2),e2(s1)"と、"e1(s2),e2(s2)"の４つの状態を含む。以下、例えば、"e1(s1),e2(s1)"は、"e1"成分が"s1"、"e2"成分が"s1"である状態という。
【００５４】
仮に、変換前の状態マシン群がさらに状態マシン"e3"を含み、"e3"が"s1"と"s2"と"s3"の３つの状態を含む場合であれば、上記の４つの状態それぞれに"e3(s1)"、"e3(s2)"、"e3(s3)"をそれぞれ掛け合せることによって得られる、合計１２個の状態が状態マシン"eX"に含まれる。
【００５５】
また、変換後の状態マシン内の状態は、変換前の状態マシンに含まれる遷移、および遷移条件に従う遷移を含む。図６に示す例では、変換前の状態マシンに含まれる遷移"e1(s1,s2)"に由来する遷移として、"e1(s1),e2(s1)"から"e1(s2),e2(s1)"への遷移と、"e1(s1),e2(s2)"から"e1(s2),e2(s2)"への遷移とが状態マシン"eX"に含まれる。
【００５６】
すなわち、状態マシン群変換部１０１は、変換前の状態マシンに含まれる遷移"e1(s1,s2)"を基に、状態マシン"eX"の状態のうち、"e1"成分が"s1"である全ての状態から、"e1"以外の成分が同一で"e1"成分が"s1"から"s2"に変更されている状態への遷移を生成する。図６に示す上側の吹き出しは、各遷移が、遷移"e1(s1,s2)"に由来することを示す。
【００５７】
同様に、状態マシン群変換部１０１は、変換前の状態マシンに含まれる遷移"e2(s1,s2)"に由来する遷移として、"e1(s1),e2(s1)"から"e1(s1),e2(s2)"への遷移と、"e1(s2),e2(s1)"から"e1(s2),e2(s2)"への遷移を生成しようとする。
【００５８】
同様に、状態マシン群変換部１０１は、変換前の状態マシンに含まれる遷移"e2(s2,s1)"に由来する遷移として、"e1(s1),e2(s2)"から"e1(s1),e2(s1)"への遷移と、"e1(s2),e2(s2)"から"e1(s2),e2(s1)"への遷移を生成しようとする。
【００５９】
すなわち、状態マシン群変換部１０１は、"e1(s1),e2(s1)"と"e1(s1),e2(s2)"の間と、"e1(s2),e2(s1)"と"e1(s2),e2(s2)"の間それぞれに、一方の状態から他方の状態に向かう２つの遷移を生成しようとする。
【００６０】
しかし、結果的に"e1(s1),e2(s1)"から"e1(s1),e2(s2)"への遷移は生成されない。その理由は、変換前の状態マシンに含まれる遷移"e2(s1,s2)"は、状態"e1(s2)"が指定された遷移条件に従う。よって、"e1(s1),e2(s1)"から"e1(s1),e2(s2)"への遷移を生成しようとしても、遷移元である状態"e1(s1),e2(s1)"の"e1"成分が遷移条件を満たさないため、遷移は生成されない。
【００６１】
図６に示す下側の吹き出しは、各遷移が、遷移"e2(s1,s2)"、または遷移"e2(s2,s1)"のいずれかに由来することを示す。なお、上記のように、"e1(s1),e2(s1)"から"e1(s1),e2(s2)"への遷移は生成されないため、対応する矢印には「×」が付されている。
【００６２】
変換後の状態マシン内の現在状態は、変換前の全ての状態マシン内の各現在状態の組合せにより決定される。図２に示す状態マシン群において、状態"e1(s1)"と状態"e2(s1)"がそれぞれ現在状態である。よって、図６に示すように、各現在状態を組合せることによって得られる状態"e1(s1),e2(s1)"が、状態マシン"eX"の現在状態になる。
【００６３】
変換後の状態マシン内の要求状態も、基本的に現在状態と同様の方法で決定される。しかし、要求状態は、変換前の状態マシンにおいて指定されていない場合がある。よって、要求状態として指定された変換前の状態マシン内の状態を成分として含む、指定された要求状態を満たす全ての状態が、変換後の状態マシン内の要求状態になる。その結果、複数の要求状態が生成されることもある。
【００６４】
図２に示す状態マシン群において、"e2(s2)"のみが要求状態として指定されている。よって、図６に示すように、"e2"成分が"s2"である２つの状態"e1(s1),e2(s2)"および"e1(s2),e2(s2)"が、状態マシン"eX"の要求状態になる。
【００６５】
単一の状態マシンにおいて、現在状態から要求状態へ至る遷移順序は、一般に広く知られている最短経路探索アルゴリズムによって発見される。図６に示す例では、"e1(s1),e2(s1)"から"e1(s2),e2(s1)"への遷移と、"e1(s2),e2(s1)"から"e1(s2),e2(s2)"への遷移とで構成される遷移順序が導出される。
【００６６】
導出された遷移順序を構成する遷移それぞれの由来になった変換前の状態マシンに含まれる遷移を参照することによって、"(e1(s1,s2), e2(s1,s2))"という遷移順序が最終的に導出される。遷移順序が導出されることで、変更計画の作成が達成される。
【００６７】
なお、本実施形態の状態マシン群変換部１０１は、例えば、非一時的なコンピュータ読み取り可能な記録媒体に記憶されたプログラムの制御に従って処理を実行するCPU(Central Processing Unit)によって実現される。
【００６８】
［動作の説明］
以下、本実施形態の変更計画システム１００の動作を図７を参照して説明する。図７は、変更計画システム１００による状態マシン群の変換処理の動作を示すフローチャートである。
【００６９】
状態マシン群変換部１０１は、入出力部２０１を介して入力された状態マシン群を受信する。状態マシン群変換部１０１は、受信した状態マシン群を参照して、変換後の状態マシンに含まれる状態と遷移の候補を生成する（ステップＳ１０１）。
【００７０】
ステップＳ１０１において、状態マシン群変換部１０１は、入力された状態マシン群から状態マシンを一つずつ順に取得する。状態マシン群変換部１０１は、暫定結果である単一の状態マシン内の状態と遷移に、取得した状態マシン内の状態と遷移を掛け合せることによって、新たな状態と遷移から構成される新たな暫定結果である単一の状態マシンを生成する。状態マシン群変換部１０１は、状態マシン群に含まれる各状態マシンに基づいて、生成処理を繰り返し行う。
【００７１】
次いで、状態マシン群変換部１０１は、生成された遷移が従う遷移条件を確認する。状態マシン群変換部１０１は、生成された遷移のうち、遷移条件を満たさない遷移を除去する（ステップＳ１０２）。
【００７２】
ステップＳ１０２において、状態マシン群変換部１０１は、ステップＳ１０１で得られた結果から、生成された状態を一つずつ順に取得する。状態マシン群変換部１０１は、取得した状態が保持する各遷移が従う遷移条件を確認する。
【００７３】
状態マシン群変換部１０１は、取得した状態の各成分が、確認した遷移条件を満たしていなければ、遷移条件に従う遷移を除去する。状態マシン群変換部１０１は、取得した状態が保持する各遷移に対して除去処理を繰り返し行う。対象の遷移を除去した後、状態マシン群変換部１０１は、処理を終了する。
【００７４】
次に、図７に示すフローチャートの各ステップにおける処理を具体的に説明する。
【００７５】
ステップＳ１０１における処理を図８を参照して具体的に説明する。図８は、変更計画システム１００による状態の生成処理および遷移の生成処理の動作を示すフローチャートである。
【００７６】
状態マシン群変換部１０１は、状態マシン群から取得した最初の状態マシン内の状態と遷移を、そのまま暫定結果である単一の状態マシンに含める（ステップＳ１１１）。ただし、状態マシン群変換部１０１は、暫定結果である単一の状態マシンの各状態に、取得した状態マシンの成分として、状態マシン内の状態を含める。
【００７７】
例えば、最初に取得した状態マシンが"e1"であり、"e1"が状態"s1"と"s2"を含む場合、暫定結果である単一の状態マシンに生成される状態は、"e1"成分が"s1"である状態"e1(s1)"と、"e1"成分が"s2"である状態"e1(s2)"の２つになる。また、生成された状態には、"e1"における"s1"と"s2"に関連する遷移が含まれる。
【００７８】
次いで、状態マシン群変換部１０１は、入力された状態マシン群内に、未処理の状態マシンがあるか否かを判断する（ステップＳ１１２）。
【００７９】
未処理の状態マシンがない場合（ステップＳ１１２におけるＮｏ）、状態マシン群変換部１０１は、得られた暫定結果を最終結果とし、処理を終了する。
【００８０】
未処理の状態マシンがある場合（ステップＳ１１２におけるＹＥＳ）、状態マシン群変換部１０１は、次に処理する未処理の状態マシンを取得する。次いで、状態マシン群変換部１０１は、暫定結果である単一の状態マシンの各状態に、取得した状態マシンの各状態を成分として追加することによって、新たな状態と遷移を生成する（ステップＳ１１３）。
【００８１】
ステップＳ１１３における、新たな状態と遷移を生成する具体的な処理内容の例を図９に示す。図９は、状態と遷移の生成過程の一例を示す説明図である。
【００８２】
図９に示す例は、図２に示す状態マシン群を対象にする。図９は、"e1"の状態と遷移を暫定結果である単一の状態マシンに含め、暫定結果に"e2"の状態と遷移を掛け合せる様子を示す。
【００８３】
掛け合せ処理において、状態マシン群変換部１０１は、最初に暫定結果である単一の状態マシンの各状態を順に取り出す。そして、状態マシン群変換部１０１は、取り出した状態に関する処理の中で、掛け合せる状態マシンの各状態を順に取り出す。
【００８４】
図９（ａ）に示すように、暫定結果である単一の状態マシンには２つの状態"e1(s1)"と"e1(s2)"がある。また、掛け合せる状態マシンである"e2"には、２つの状態"s1"と"s2"がある。
【００８５】
状態マシン群変換部１０１は、暫定結果である単一の状態マシンから、最初に"e1(s1)"を取り出す。取り出した"e1(s1)"に対して、状態マシン群変換部１０１は、"e2"の状態"s1"と"s2"を順に取り出す。そして、状態マシン群変換部１０１は、暫定結果である単一の状態マシンから取り出した状態に、掛け合せる状態を含む状態マシンの成分を加えた、新たな状態を生成する。
【００８６】
例えば、"e1(s1)"に対して状態マシン"e2"の状態"s1"を取り出した場合、状態マシン群変換部１０１は、新たな状態"e1(s1),e2(s1)"を生成する。また、状態マシン"e2"の状態"s2"を取り出した場合、状態マシン群変換部１０１は、新たな状態"e1(s1),e2(s2)"を生成する。
【００８７】
新たな状態を生成すると、状態マシン群変換部１０１は、掛け合せた状態マシン内の状態ごとに異なるグループのメモリに読み出し可能な状態で、新たな状態を記録する。図９（ｂ）に示すように、例えば、状態マシン群変換部１０１は、"e1(s1),e2(s1)"を"e2(s1)"のグループに記録し、"e1(s1),e2(s2)"を"e2(s2)"のグループに記録する。
【００８８】
以上の処理を、状態マシン群変換部１０１は、掛け合せる状態マシンの各状態に対して繰り返し行う。暫定結果である単一の状態マシンの特定の状態から新たな状態が全て生成されたら、状態マシン群変換部１０１はさらに、生成した各状態に、掛け合せた状態マシンの各状態が持つ遷移と同様の遷移を付与する。
【００８９】
例えば、状態マシン群変換部１０１は、生成された新たな状態"e1(s1),e2(s1)"と"e1(s1),e2(s2)"が、"e2"の"s1"と"s2"の間の遷移関係と同様の遷移関係を持つように、２つの新たな状態に対してそれぞれ遷移を付与する。状態マシン群変換部１０１は、以上の処理を暫定結果である単一の状態マシンの各状態に対して繰り返し行う。
【００９０】
遷移が付与された段階で、掛け合せた状態マシン内の状態ごとに作られた全てのグループに、暫定結果である単一の状態マシンの全ての状態に由来する新たな状態が記録されている。状態マシン群変換部１０１は、各グループから記録された状態を順に取出し、グループ内の状態に暫定結果である単一の状態マシン内の状態が持つ遷移と同様の遷移を付与する。
【００９１】
例えば、状態マシン群変換部１０１は、"e2(s1)"のグループ内の状態である"e1(s1),e2(s1)"と"e1(s2),e2(s1)"が、暫定結果である単一の状態マシン内の状態"e1(s1)"、"e1(s2)"間の遷移と同様の遷移を持つように、"e1(s1),e2(s1)"に対して"e1(s2),e2(s1)"への遷移を付与する。状態マシン群変換部１０１は、以上の処理を各グループに対して繰り返し行う（ステップＳ１１４）。
【００９２】
状態マシン群変換部１０１は、ステップＳ１１４における処理が終了した後に得られる結果を新たな暫定結果にする。新たな暫定結果を生成した後、状態マシン群変換部１０１は、再度ステップＳ１１２における処理を行う。
【００９３】
次に、ステップＳ１０２における処理を図１０を参照して具体的に説明する。図１０は、変更計画システム１００による遷移の除去処理の動作を示すフローチャートである。
【００９４】
状態マシン群変換部１０１は、ステップＳ１０１で作成した結果内に、遷移の除去に関して未処理の状態があるか否かを判断する（ステップＳ１２１）。
【００９５】
未処理の状態がある場合（ステップＳ１２１におけるＹＥＳ）、状態マシン群変換部１０１は、未処理の状態が保持する各遷移が従う遷移条件を確認する。未処理の状態に含まれる各成分が遷移条件を満たしていなければ、状態マシン群変換部１０１は、確認した遷移条件に従う遷移を除去する（ステップＳ１２２）。
【００９６】
例えば、図９（ｂ）に示す"e1(s2),e2(s1)"を未処理の状態として取得する場合、"e1(s2),e2(s1)"は"e1(s2),e2(s2)"への遷移を含む。また、含まれている遷移は、"e1(s2)"が指定された遷移条件に従う。
【００９７】
よって、状態マシン群変換部１０１は、状態の"e1"成分が"s2"であるか否かを確認する。確認した結果、"e1(s2),e2(s1)"の"e1"成分は"s2"であるため、状態マシン群変換部１０１は、"e1(s2)"が指定された遷移条件に従う遷移を維持する。
【００９８】
また、例えば、図９（ｂ）に示す"e1(s1),e2(s1)"を未処理の状態として取得する場合、"e1(s1),e2(s1)"は"e1(s1),e2(s2)"への遷移を含む。また、含まれている遷移は、"e1(s2)"が指定された遷移条件に従う。
【００９９】
よって、状態マシン群変換部１０１は、状態の"e1"成分が"s2"であるか否かを確認する。確認した結果、"e1(s1),e2(s1)"の"e1"成分は"s1"であるため、状態マシン群変換部１０１は、"e1(s2)"が指定された遷移条件に従う遷移を除去する。
【０１００】
遷移の除去に関して未処理の状態がない場合（ステップＳ１２１におけるＮＯ）、状態マシン群変換部１０１は、処理を終了する。以上の処理により変更計画システム１００は、結果として、例えば図６に示す状態マシン"eX"を生成する。
【０１０１】
［効果の説明］
本実施形態における変更計画システムによれば、複数の状態マシンと状態マシン間の遷移条件で表現された部品、依存性、作業に関する定義情報を、単一の状態マシンで表現できる。単一の状態マシンからであれば、作業手順は、一般に広く知られている最短経路探索手法によって導出される。従って、効率の高い計算手順で作業手順が導出される。
【０１０２】
また、本実施形態における変更計画システムは、複数の状態マシンから構成されたシステムを対象にするため、再利用可能性の高い単純なタスク定義を採用できる。また、変更計画システムは、一つの部品が複数の一時状態を経て要求状態に至るような変更計画も作成できる。
【０１０３】
実施形態２．
［構成の説明］
以下、本発明の第２の実施形態を、図面を参照して説明する。図１１は、本発明による変更計画システムの第２の実施形態の構成例を示すブロック図である。図１１において、第１の実施形態と同様の構成要素には同一の符号を付し、説明を省略する。
【０１０４】
図１１に示す変更計画システム１００は、状態マシン群変換部１０１と、経路探索部１０２と、遷移順序変換部１０３とを含む。
【０１０５】
経路探索部１０２は、状態マシンをある状態から他の状態へ移行させる１または複数の遷移群から構成される状態マシン内の遷移の経路を発見する機能を有する。経路探索部１０２は、状態マシン群変換部１０１および遷移順序変換部１０３と、それぞれ通信ネットワークなどを介して通信可能に接続されている。
【０１０６】
遷移順序変換部１０３は、経路を構成する遷移群を、遷移条件によって関連付けられる任意の状態マシンの組に含まれる遷移間のみに順序性が付与されている、遷移の半順序集合に変換する機能を有する。
【０１０７】
半順序集合は、集合の要素に対して、順序性が規定されていない要素の組を含むような順序集合である。半順序集合に対して、全順序集合は、集合の要素に対して、いかなる要素間にも順序性が規定されているような順序集合である。
【０１０８】
本実施形態における状態マシン群変換部１０１は、入出力部２０１から受信した状態マシン群を、単一の状態マシンに変換する。状態マシン群変換部１０１は、変換した単一の状態マシンを経路探索部１０２に入力する。
【０１０９】
経路探索部１０２は、状態マシン群変換部１０１から入力された単一の状態マシンに基づいて、全順序集合としての遷移順序を生成する。
【０１１０】
経路探索部１０２は、例えば、一般に広く知られているDijkstra法による最短経路探索アルゴリズムに基づいて遷移順序を生成する。最短経路探索アルゴリズムに基づく場合、経路探索部１０２は、状態マシンを、状態をノード、遷移をエッジとするグラフと捉える。
【０１１１】
経路探索部１０２は、捉えたグラフに基づいて、現在状態から各状態への最短距離と、最短経路を順次計算する。計算した後、経路探索部１０２は、複数存在する要求状態のうち、最短距離で到達可能な要求状態までの最短経路を検出する。
【０１１２】
経路探索部１０２は、検出した最短経路を構成する遷移を順に並べ、並べた各遷移に一つ前の遷移への依存性を関連付けた情報を遷移順序として出力する。経路探索部１０２は、生成した遷移順序を、遷移順序変換部１０３に入力する。
【０１１３】
遷移順序変換部１０３は、経路探索部１０２から入力された全順序集合としての遷移順序を、半順序集合としての遷移順序に変換する。遷移順序変換部１０３は、変換した半順序集合としての遷移順序を、経路探索部１０２に返す。
【０１１４】
経路探索部１０２は、遷移順序変換部１０３から入力された半順序集合としての遷移順序を、状態マシン群変換部１０１に返す。状態マシン群変換部１０１は、経路探索部１０２から入力された遷移順序を、入出力部２０１に返す。
【０１１５】
図１２は、並列化可能なタスクを含む状態マシン群の一例を示す説明図である。図１２に示す状態マシン群を元に、状態マシン群変換部１０１と経路探索部１０２によって生成された遷移順序の一例を図１３に示す。図１３は、全順序集合としての遷移順序生成結果の一例を示す説明図である。
【０１１６】
図１３において、角丸四角形は遷移を示す。また、遷移間の矢印は、遷移間の依存性を示す。図１３に示す遷移順序に基づいて、各遷移は、正しく実施される。
【０１１７】
しかし、図１３に示す遷移順序に基づいて各遷移が実施される場合、各遷移を実施する処理系が２つ以上存在する時でも、処理系が本来並列に実施できる複数の遷移を、並列に実施できないという問題がある。
【０１１８】
図１２に示す状態マシン"e1"と"e2"の間には、遷移条件が一切指定されていない。すなわち、"e1"内の遷移である"e1(s1,s2)"と、"e2"内の遷移である"e2(s1,s2)"との間に、依存性が指定される必要はない。
【０１１９】
上記に基づいて、図１３に示す全順序集合としての遷移順序が変換された、半順序集合としての遷移順序を図１４に示す。図１４は、半順序集合としての遷移順序生成結果の一例を示す説明図である。
【０１２０】
図１４に示す遷移順序に基づいて各遷移が実施される場合、"e1(s1,s2)"と"e2(s1,s2)"は、並列に実施されてもよい。よって、処理系が２つ以上存在する場合、全順序集合としての遷移順序に基づいて遷移が実施される場合に比べて、より高速に全ての遷移が実施される。
【０１２１】
遷移順序変換部１０３は、全順序集合としての遷移順序から、遷移条件が規定されていない状態マシン間の依存性に相当する依存性を除去し、状態マシン間の正しい依存性に相当する依存性を追加することによって、半順序集合としての遷移順序を生成する。
【０１２２】
なお、本実施形態の経路探索部１０２および遷移順序変換部１０３は、例えば、非一時的なコンピュータ読み取り可能な記録媒体に記憶されたプログラムの制御に従って処理を実行するCPU(Central Processing Unit)によって実現される。
【０１２３】
［動作の説明］
以下、本実施形態の変更計画システム１００の動作を図１５を参照して説明する。図１５は、変更計画システム１００による変更計画処理の動作を示すフローチャートである。
【０１２４】
状態マシン群変換部１０１は、入出力部２０１から状態マシン群の情報を受信する。状態マシン群変換部１０１は、受信した情報が示す状態マシン群を単一の状態マシンに変換する（ステップＳ２０１）。
【０１２５】
状態マシン群変換部１０１は、変換した単一の状態マシンを経路探索部１０２に入力する。経路探索部１０２は、入力された単一の状態マシンから全順序集合としての遷移順序を生成する（ステップＳ２０２）。
【０１２６】
経路探索部１０２は、生成した遷移順序を遷移順序変換部１０３に入力する。遷移順序変換部１０３は、入力された遷移順序を、半順序集合としての遷移順序に変換する。遷移順序変換部１０３は、変換した遷移順序を経路探索部１０２に返す（ステップＳ２０３）。
【０１２７】
経路探索部１０２は、遷移順序変換部１０３から入力された遷移順序を、状態マシン群変換部１０１に返す。さらに、状態マシン群変換部１０１は、入力された遷移順序を入出力部２０１に送信する。送信した後、変更計画システム１００は、全体の変更計画処理を終了する。
【０１２８】
次に、ステップＳ２０３における処理を図１６を参照して具体的に説明する。図１６は、遷移順序変換部１０３による遷移順序変換処理の動作を示すフローチャートである。
【０１２９】
ステップＳ２０３において、遷移順序変換部１０３は、経路探索部１０２から入力された全順序集合としての遷移順序内の遷移を、遷移順序内の順序通りに一つずつ取得する。遷移順序変換部１０３は、取得した遷移を、暫定結果である半順序集合としての遷移順序内に再配置する。遷移順序変換部１０３は、再配置処理を、入力された遷移順序内の各遷移に対して繰り返し行う。なお、初期状態の暫定結果には、何も含まれない。
【０１３０】
遷移順序変換部１０３は、入力された遷移順序内の全ての遷移を変換済みであるか否かを判断する（ステップＳ２３１）。全ての遷移を変換済みである場合（ステップＳ２３１におけるＹＥＳ）、遷移順序変換部１０３は、得られた暫定結果を最終結果として、変換処理を終了する。
【０１３１】
全ての遷移を変換済みでない場合（ステップＳ２３１におけるＮＯ）、遷移順序変換部１０３は、未変換の遷移を一つ取得する。遷移順序変換部１０３は、取得した遷移を、現在の暫定結果である遷移順序内の適切な位置に配置する。
【０１３２】
取得した遷移が配置される、現在の暫定結果である遷移順序内の適切な位置を判断するために、遷移順序変換部１０３は、暫定結果である遷移順序内の遷移の中で、他のどの遷移からも依存されていない最後尾の遷移を全て取得する。遷移順序変換部１０３は、取得した最後尾の遷移と、再配置する遷移との関係を検査する。遷移順序変換部１０３は、取得した最後尾の各遷移に対して、関係の検査処理を繰り返し行う。
【０１３３】
最後尾の遷移を取得する理由は、無駄な順序性を作らないようにするためである。例えば、暫定結果である遷移順序内に"A"と"B"の２つの遷移が存在し、"B"が"A"に依存しているとする。すなわち、"A, B"の順に遷移が誘発される状況であるとする。さらに、次に再配置される遷移として"C"があり、"C"は、"A"と"B"のそれぞれの遷移に依存性を持つとする。
【０１３４】
"A"、"B"、"C"から構成される遷移順序を新たに作成する場合、"C"と"B"との間にのみ依存性が指定されればよい。"C"と"A"との間に依存性を指定することは冗長である。
【０１３５】
その理由は、"B"は必ず"A"の後に誘発されることが保障されている。よって、"C"が"B"の後に誘発されることさえ保障されれば、"C"は必ず"A"の後に誘発されるためである。すなわち、"C"が"B"の後に誘発されることが保障された状態は、"C"と"A"との間に依存性が指定された状態と同じである。
【０１３６】
以上により、上記の例において"C"を再配置する際、遷移順序変換部１０３は、最初に"C"と"B"との関係を検証する。"C"が"B"に対して依存性を持つと判定した場合、遷移順序変換部１０３は、"B"が依存する他の遷移と、"C"との関係を検証しない。
【０１３７】
遷移順序変換部１０３は、取得した最後尾の全ての遷移を検証済みであるか否かを判定する（ステップＳ２３２）。
【０１３８】
取得した最後尾の全ての遷移を検証済みではない場合（ステップＳ２３２におけるＮＯ）、遷移順序変換部１０３は、未検証の最後尾の遷移を一つ取得する。次いで、遷移順序変換部１０３は、取得した最後尾の遷移から続く一連の遷移を一つずつ取得する。遷移順序変換部１０３は、取得した遷移と、再配置対象の遷移との関係を検証する。遷移順序変換部１０３は、取得した各遷移に対して、検証処理を繰り返し行う。
【０１３９】
遷移順序変換部１０３は、最後尾の遷移から続く一連の遷移を、深さ優先探索で順次取得すればよい。再配置対象の遷移が取得した遷移に依存性を持つと判定した場合、遷移順序変換部１０３は、取得した遷移がさらに依存する遷移を探索しない。
【０１４０】
また、同一の再配置対象の遷移に関して同じ遷移との検証を２回以上行わないように、遷移順序変換部１０３は、検証済みの遷移を順次記録する。遷移順序変換部１０３は、検証済みと記録された遷移、および検証済みと記録された遷移が依存する遷移を検証しない。
【０１４１】
以上の処理を行うために、遷移順序変換部１０３は、取得した最後尾の遷移から続く一連の遷移を全て検証済みであるか否かを判断する（ステップＳ２３３）。全て検証済みである場合（ステップＳ２３３におけるＹＥＳ）、遷移順序変換部１０３は、次の最後尾の遷移を処理するために、再度ステップＳ２３２における処理を行う。
【０１４２】
全て検証済みではない場合（ステップＳ２３３におけるＮＯ）、遷移順序変換部１０３は、取得した遷移の次の遷移を取得する。遷移順序変換部１０３は、取得した遷移と再配置対象の遷移との関係を検証する（ステップＳ２３４）。
【０１４３】
２つの遷移が依存関係、または順序関係を持つか否かは、状態マシンに含まれる一方の遷移が従う、他方の遷移が含まれる状態マシン内の状態が指定された遷移条件が存在するか否かによって判定される。遷移条件が存在する場合、依存関係があると判定される。遷移条件が存在しない場合、依存関係がないと判定される。
【０１４４】
図１２および図１３に示す例では、状態マシン"e3"と"e1"の間に遷移条件が存在するため、２つの遷移"e3(s2,s1)"と"e1(s1,s2)"との間に依存関係はあると判定される。また、状態マシン"e1"と"e2"の間に何らの遷移条件も存在しないため、２つの遷移"e1(s1,s2)"と"e2(s1,s2)"との間に依存関係はないと判定される。
【０１４５】
再配置対象の遷移と検証対象の遷移との間に依存関係があると判断した場合（ステップＳ２３４におけるＹＥＳ）、遷移順序変換部１０３は、検証対象の遷移の後ろに再配置対象の遷移を配置する（ステップＳ２３６）。後ろに配置することによって、遷移順序変換部１０３は、再配置対象の遷移に、検証対象の遷移への依存性を設定する。
【０１４６】
再配置対象の遷移を配置した後、遷移順序変換部１０３は、次の最後尾の遷移を処理するために、再度ステップＳ２３２における処理を行う。
【０１４７】
再配置対象の遷移と検証対象の遷移との間に依存関係がないと判断した場合（ステップＳ２３４におけるＮＯ）、遷移順序変換部１０３は、再配置対象の遷移と、検証対象の遷移が依存する次の遷移との関係を検証するために、再度ステップＳ２３３における処理を行う。
【０１４８】
取得した最後尾の全ての遷移を検証した結果（ステップＳ２３２におけるＹＥＳ）、どの遷移との間にも依存関係が見出されなかった場合（ステップＳ２３７におけるＮＯ）、遷移順序変換部１０３は、現在の再配置対象の遷移を、暫定結果である遷移順序内のどの遷移にも依存しない遷移として、遷移順序の先頭に配置する（ステップＳ２３５）。配置した後、遷移順序変換部１０３は、再配置対象の遷移に対する検証を終了し、再度ステップＳ２３１における処理を行う。
【０１４９】
ある遷移との間に依存関係が見出された場合（ステップＳ２３７におけるＹＥＳ）、遷移順序変換部１０３は、再配置対象の遷移に対する検証を終了し、再度ステップＳ２３１における処理を行う。
【０１５０】
例として、図１２に示す状態マシン群に基づいて、図１３に示す全順序集合としての遷移順序を、図１４に示す半順序集合としての遷移順序に変換する場合を考える。
【０１５１】
遷移順序変換部１０３は、遷移順序の先頭の遷移"e3(s2,s1)"を取得する。遷移順序変換部１０３は、暫定結果に比較すべき遷移がないので、"e3(s2,s1)"を先頭に配置する。
【０１５２】
次いで、遷移順序変換部１０３は、"e1(s1,s2)"を取得する。遷移順序変換部１０３は、取得した"e1(s1,s2)"と暫定結果内の"e3(s2,s1)"との関係を検証する。
【０１５３】
検証した結果、"e1"と"e3"との間に遷移条件が存在するため、遷移順序変換部１０３は、"e1(s1,s2)"を暫定結果内の"e3(s2,s1)"の後ろに配置する。
【０１５４】
次いで、遷移順序変換部１０３は、"e2(s1,s2)"を取得する。遷移順序変換部１０３は、取得した"e2(s1,s2)"と暫定結果内の各遷移との関係を検証する。
【０１５５】
遷移順序変換部１０３は、取得した"e2(s1,s2)"と、何の遷移からも依存されていない暫定結果内で唯一の遷移である"e1(s1,s2)"との関係を検証する。検証した結果、"e2"と"e1"との間に遷移条件が存在しないため、遷移順序変換部１０３は、"e2(s1,s2)"を暫定結果内の"e1(s1,s2)"の後ろに配置しない。
【０１５６】
次いで、遷移順序変換部１０３は、取得した"e2(s1,s2)"と、"e1(s1,s2)"が依存する"e3(s2,s1)"との関係を検証する。検証した結果、"e2"と"e3"との間に遷移条件が存在するため、遷移順序変換部１０３は、"e2(s1,s2)"を"e3(s2,s1)"の後ろに配置する。
【０１５７】
次いで、遷移順序変換部１０３は、"e3(s1,s2)"を取得する。遷移順序変換部１０３は、取得した"e3(s1,s2)"と、暫定結果内で何の遷移からも依存されていない遷移"e1(s1,s2)"および"e2(s1,s2)"それぞれとの関係を検証する。
【０１５８】
検証した結果、"e3"と"e1"との間に遷移条件が存在し、"e3"と"e2"との間に遷移条件が存在する。よって、遷移順序変換部１０３は、"e3(s1,s2)"を"e1(s1,s2)"と"e2(s1,s2)"の双方の後ろに配置する。
【０１５９】
［効果の説明］
本実施形態における変更計画システムは、複数の状態マシンと状態マシン間の遷移条件で表現された部品、依存性、作業に関する定義情報から、同時実行的に実施可能な作業手順を作成できる。
【０１６０】
実施形態３．
［構成の説明］
以下、本発明の第３の実施形態を、図面を参照して説明する。図１７は、本発明による変更計画システムの第３の実施形態の構成例を示すブロック図である。図１７において、第２の実施形態と同様の構成要素には同一の符号を付し、説明を省略する。
【０１６１】
図１７に示す変更計画システム１００は、状態マシン群変換部１０１と、経路探索部１０２と、遷移順序変換部１０３と、状態マシン簡略化部１０４とを含む。
【０１６２】
状態マシン簡略化部１０４は、遷移が誘発されない状態マシンを特定し、特定した状態マシンおよび特定した状態マシンに関連する遷移条件を除去する機能を有する。状態マシン簡略化部１０４は、状態マシン群変換部１０１と、通信ネットワークなどを介して通信可能に接続されている。
【０１６３】
本実施形態における状態マシン群変換部１０１は、入出力部２０１から受信した状態マシン群の情報を、一旦状態マシン簡略化部１０４に入力する。
【０１６４】
状態マシン簡略化部１０４は、入力された情報が示す状態マシン群を簡略化する。状態マシン簡略化部１０４は、簡略化した状態マシン群を、状態マシン群変換部１０１に返す。
【０１６５】
さらに、状態マシン群変換部１０１は、状態マシン簡略化部１０４から入力された状態マシン群を、単一の状態マシンに変換する。状態マシン群変換部１０１は、変換した単一の状態マシンを、再度状態マシン簡略化部１０４に入力する。
【０１６６】
状態マシン簡略化部１０４は、入力された単一の状態マシンを簡略化する。状態マシン簡略化部１０４は、簡略化した状態マシンを、再度状態マシン群変換部１０１に返す。
【０１６７】
状態マシン群変換部１０１は、状態マシン簡略化部１０４から入力された状態マシンを経路探索部１０２に入力する。次いで、状態マシン群変換部１０１は、経路探索部１０２から入力された遷移順序を入出力部２０１に返す。
【０１６８】
図１８は、簡略化可能な状態マシン群の一例を示す説明図である。図１８は図２と異なり、状態マシン自体から他の状態マシン内の状態が指定された遷移条件に対応する矢印を示す。矢印は、状態マシン内の全ての遷移が、矢印に対応する遷移条件と同様の遷移条件を持つことを示す。
【０１６９】
本実施形態における簡略化可能な状態マシン群は、状態マシン群変換部１０１や経路探索部１０２に検証されなくても、遷移が誘発されないことが予め判断される状態マシンを含む状態マシン群である。
【０１７０】
状態マシン群変換部１０１により変換された後の状態マシン内の状態の数は、変換前の状態マシンの数が増えると指数関数的に増加する。また、経路探索部１０２による経路計算においても、計算対象の状態の数が増えると計算量が大幅に増加する。
【０１７１】
よって、遷移が誘発されないことが予め分かっている状態マシンは、状態マシン群変換部１０１による状態マシン群の変換処理が行われる前に除去されることが望ましい。
【０１７２】
本実施形態において、遷移は、遷移を含む状態マシンに現在状態と異なる要求状態が設定されている場合に誘発されると判断される。または、遷移は、遷移を含む状態マシンに現在状態と異なる状態が、他の誘発される遷移が従う遷移条件に指定されている場合に誘発されると判断される。
【０１７３】
図１８に示す"e3"は、要求状態を持たない。また、"e3"には遷移条件が指定されていない。よって、"e3"に含まれる遷移は、誘発されない。
【０１７４】
図１８に示す"e4"は、要求状態を持つが、要求状態は現在状態と同一である。また、"e4"には遷移条件が指定されていない。よって、"e4"に含まれる遷移は、誘発されない。
【０１７５】
図１８に示す"e2"は、要求状態を持たない。しかし、"e2"には遷移条件が複数指定されている。指定されている遷移条件のうち、"e1"から指定されている遷移条件は、"e2"の現在状態に関連する。すなわち、"e1"から指定されている遷移条件は、遷移を誘発しない。
【０１７６】
"e3"と"e4"からそれぞれ指定されている遷移条件は、"e2"の現在状態以外の状態に関連する。しかし、上記のように"e3"および"e4"に含まれる遷移は、誘発されないと判断される。すなわち、"e3"と"e4"からそれぞれ指定されている遷移条件も、遷移を誘発しない。
【０１７７】
以上より、図１８に示す例において、"e1"以外の状態マシンは、いずれも状態マシン内の遷移が誘発されない、簡略化可能な状態マシンであると判断される。
【０１７８】
以上のように判断した場合、状態マシン簡略化部１０４は、"e2"と"e2"に関連する遷移条件、"e3"と"e3"に関連する遷移条件、および"e4"と"e4"に関連する遷移条件を全て除去する。除去した後、状態マシン簡略化部１０４は、"e1"のみから構成される状態マシン群を、状態マシン群変換部１０１に返す。
【０１７９】
図１９は、簡略化可能な状態マシンの一例を示す説明図である。本実施形態における簡略化可能な状態マシンは、現在状態から遷移不可能な状態を含む状態マシンである。
【０１８０】
経路探索部１０２による経路探索において一般に広く知られているDijkstra法などが用いられる場合、経路探索には、経路探索の対象になる状態の数の２乗程度の計算時間が求められる。
【０１８１】
よって、現在状態から遷移不可能な状態が短時間で判別される場合、遷移不可能な状態は、予め除去されることが望ましい。遷移不可能な状態を判別するための計算は、一般に広く知られている深さ優先探索などの手法を用いることで、簡単に実施される。
【０１８２】
図１９に示す例において、状態マシン"eY"は、"s1"から"s2"に遷移できない。その理由は、"s1"から遷移できる"s3"と"s4"のいずれからも、"s2"に遷移できないためである。
【０１８３】
図１９に示す状態マシン"eY"が入力された場合、状態マシン簡略化部１０４は、"s2"および"s2"に関連する遷移を全て除去する。状態マシン簡略化部１０４は、"s1"、"s3"および"s4"を含む状態マシン"eY"を、状態マシン群変換部１０１に返す。
【０１８４】
なお、本実施形態の状態マシン簡略化部１０４は、例えば、非一時的なコンピュータ読み取り可能な記録媒体に記憶されたプログラムの制御に従って処理を実行するCPU(Central Processing Unit)によって実現される。
【０１８５】
［動作の説明］
以下、本実施形態の変更計画システム１００の動作を図２０を参照して説明する。図２０は、変更計画システム１００による変更計画処理の動作を示すフローチャートである。
【０１８６】
状態マシン群変換部１０１は、入出力部２０１から状態マシン群の情報を受信する。状態マシン群変換部１０１は、受信した情報を、状態マシン簡略化部１０４に入力する。
【０１８７】
状態マシン簡略化部１０４は、入力された情報が示す状態マシン群を簡略化する。状態マシン簡略化部１０４は、簡略化した状態マシン群を、状態マシン群変換部１０１に返す（ステップＳ３０１）。
【０１８８】
状態マシン群変換部１０１は、状態マシン簡略化部１０４から入力された、簡略化された状態マシン群を単一の状態マシンに変換する（ステップＳ３０２）。ステップＳ３０２における処理は、第２の実施形態のステップＳ２０１における処理と同様である。
【０１８９】
状態マシン群変換部１０１は、変換した単一の状態マシンを、再度状態マシン簡略化部１０４に入力する。状態マシン簡略化部１０４は、入力された単一の状態マシンを簡略化する。状態マシン簡略化部１０４は、簡略化した状態マシンを、状態マシン群変換部１０１に返す（ステップＳ３０３）。
【０１９０】
ステップＳ３０３において、状態マシン簡略化部１０４は、例えば、一般に広く知られている、深さ優先で探索するグラフトラバーサル法を用いて状態マシンを簡略化する。
【０１９１】
グラフトラバーサル法を用いる場合、状態マシン簡略化部１０４は、状態マシンを、状態をノード、遷移をエッジとするグラフと捉える。グラフと捉えた後、状態マシン簡略化部１０４は、対象の状態マシンが現在状態から遷移できる状態を全て検出する。検出した後、状態マシン簡略化部１０４は、遷移できない状態と判定された状態、および判定された状態に関連する遷移を除去する。
【０１９２】
状態マシン群変換部１０１は、状態マシン簡略化部１０４から入力された状態マシンを、経路探索部１０２に入力する。
【０１９３】
経路探索部１０２は、入力された状態マシンから遷移順序を生成する（ステップＳ３０４）。ステップＳ３０４における処理は、第２の実施形態のステップＳ２０２における処理と同様である。
【０１９４】
経路探索部１０２は、生成した遷移順序を、遷移順序変換部１０３に入力する。遷移順序変換部１０３は、入力された遷移順序を、半順序集合としての遷移順序に変換する（ステップＳ３０５）。ステップＳ３０５における処理は、第２の実施形態のステップＳ２０３における処理と同様である。
【０１９５】
遷移順序変換部１０３は、変換した遷移順序を、経路探索部１０２に返す。経路探索部１０２は、遷移順序変換部１０３から入力された遷移順序を、状態マシン群変換部１０１に返す。さらに、状態マシン群変換部１０１は、入力された遷移順序を、入出力部２０１に返す。以上により、変更計画システム１００は、全体の変更計画処理を終了する。
【０１９６】
次に、ステップＳ３０１における処理を図２１を参照して具体的に説明する。図２１は、状態マシン簡略化部１０４による状態マシン群の簡略化処理の動作を示すフローチャートである。
【０１９７】
ステップＳ３０１において、状態マシン簡略化部１０４は、状態マシン群変換部１０１から入力された初期の状態マシン群を、簡略化された状態マシン群の暫定結果にする。
【０１９８】
次いで、状態マシン簡略化部１０４は、暫定結果から遷移が誘発されるか否かが未判定な状態マシンを取得する。状態マシン簡略化部１０４は、取得した状態マシンに対して、状態マシンが含む遷移が誘発される可能性を判定する。状態マシン簡略化部１０４は、未判定な状態マシンそれぞれに対して、判定処理を繰り返し行う。
【０１９９】
状態マシン簡略化部１０４は、暫定結果内の全ての状態マシンを判定済みであるか否かを確認する（ステップＳ３１１）。
【０２００】
全ての状態マシンを判定済みである場合（ステップＳ３１１におけるＹＥＳ）、状態マシン簡略化部１０４は、得られた暫定結果を最終結果として、簡略化処理を終了する。
【０２０１】
全ての状態マシンを判定済みでない場合（ステップＳ３１１におけるＮＯ）、状態マシン簡略化部１０４は、未判定の状態マシンを一つ取得する。状態マシン簡略化部１０４は、取得した状態マシンに含まれる遷移が誘発される可能性を判定する（ステップＳ３１２）。
【０２０２】
ステップＳ３１２における遷移が誘発される可能性を判定するプロセスは、プロセス内で判定する遷移に関連する他の状態マシンに含まれる遷移が誘発される可能性を判定するプロセスを呼び出すという、プロセスの再起呼び出し構造をとる。
【０２０３】
すなわち、プロセスの呼び出しのループが発生する場合、ループにおける再起呼び出しの停止が求められる。呼び出しがループしていることを判断するために、状態マシン簡略化部１０４は、プロセスの呼び出し時に、処理中の状態マシンの連鎖の情報を含むスタック型のデータを渡す。
【０２０４】
最初のステップＳ３１２における処理において、状態マシン簡略化部１０４は、遷移が誘発される可能性を判定するプロセスを最初に呼び出す。すなわち、状態マシン簡略化部１０４は、空のスタック型のデータと共にプロセスを呼び出す。遷移が誘発される可能性を判定した後、状態マシン簡略化部１０４は、再度ステップＳ３１１における処理を行う。
【０２０５】
次に、ステップＳ３１２における処理を図２２を参照して具体的に説明する。図２２は、状態マシン簡略化部１０４による遷移が誘発される可能性がある状態マシンの判定処理の動作を示すフローチャートである。
【０２０６】
状態マシン簡略化部１０４は、判定対象である状態マシン内に、現在状態と異なる要求状態が含まれているか否かを判断する（ステップＳ３２１）。
【０２０７】
状態マシンに現在状態と異なる要求状態が含まれている場合（ステップＳ３２１におけるＹＥＳ）、状態マシン簡略化部１０４は、判定対象である状態マシンに含まれる遷移が誘発される可能性があると判断して、対象の状態マシンに関する処理を終了する。
【０２０８】
状態マシンに現在状態と異なる要求状態が含まれていない場合（ステップＳ３２１におけるＮＯ）、状態マシン簡略化部１０４は、現在状態以外の状態が指定された未確認の遷移条件があるか否かを確認する（ステップＳ３２２）。
【０２０９】
現在状態以外の状態が指定された未確認の遷移条件がない場合（ステップＳ３２２におけるＮＯ）、状態マシン簡略化部１０４は、判定対象である状態マシンに含まれる遷移が誘発される可能性がないと判断して、対象の状態マシンに関する処理を終了する。
【０２１０】
現在状態以外の状態が指定された未確認の遷移条件がある場合（ステップＳ３２２におけるＹＥＳ）、状態マシン簡略化部１０４は、未確認の遷移条件に従う遷移を含む状態マシンを取得する。状態マシン簡略化部１０４は、取得した状態マシンに含まれる遷移が誘発される可能性を判定する。状態マシン簡略化部１０４は、未確認の遷移条件に従う遷移を含む各状態マシンに対して、判定処理を繰り返し行う。
【０２１１】
取得した状態マシンに含まれる遷移が誘発される可能性を判定するために、状態マシン簡略化部１０４は、取得した状態マシンが、再起呼び出しのループを判断するためのスタックに含まれているか否かを判断する（ステップＳ３２３）。取得した状態マシンがスタックに含まれている場合（ステップＳ３２３におけるＹＥＳ）、状態マシンの判定処理はループしている。
【０２１２】
よって、状態マシン簡略化部１０４は、現在判定中の状態マシンに含まれる遷移が誘発される可能性があると判断して、対象の状態マシンに関する処理を終了する。取得した状態マシンがスタックに含まれている場合、スタック内の各状態マシンに含まれる遷移は、全て誘発される可能性があると最終的に判定される。
【０２１３】
取得した状態マシンがスタックに含まれていない場合（ステップＳ３２３におけるＮＯ）、状態マシン簡略化部１０４は、取得した状態マシンをスタックに追加する。追加した上で、状態マシン簡略化部１０４は、取得した状態マシン内の遷移が誘発される可能性を判定するプロセスを再起的に呼び出す（ステップＳ３２４）。
【０２１４】
次いで、状態マシン簡略化部１０４は、再起的に呼び出したプロセスの結果を確認する（ステップＳ３２５）。再起的に呼び出したプロセスに含まれる状態マシン内の遷移が誘発される可能性がある場合（ステップＳ３２５におけるＹＥＳ）、状態マシン簡略化部１０４は、現在判定中の状態マシン内の遷移も誘発される可能性があると判定して、対象の状態マシンに関する処理を終了する。
【０２１５】
再起的に呼び出したプロセスに含まれる状態マシン内の遷移が誘発される可能性がない場合（ステップＳ３２５におけるＮＯ）、状態マシン簡略化部１０４は、再度ステップＳ３２２における処理を行う。
【０２１６】
［効果の説明］
本実施形態の変更計画システムは、複数の状態マシンと状態マシン間の遷移条件で表現された部品、依存性、作業に関する定義情報から、より効率的に作業手順を作成できる。
【０２１７】
次に、本発明の概要を説明する。図２３は、本発明による変更計画システムの概要を示すブロック図である。本発明による変更計画システム１０は、１または複数の状態マシンから構成される状態マシン群を、１または複数の状態を含む単一状態マシンに変換する状態マシン群変換部１１（例えば、状態マシン群変換部１０１）を含み、状態マシン内の状態を、状態マシン群に含まれる状態マシン以外の状態マシン内の状態が指定された遷移条件に従って他の状態に遷移させ、単一状態マシン内の状態は、状態マシン群内の全状態マシンの一状態に対応し、単一状態マシン内の状態を、状態マシン内の状態に所定の遷移をさせる時に従う遷移条件を満たしながら、所定の遷移により生じる全状態マシンの他の一状態に対応する他の状態に遷移させる。
【０２１８】
そのような構成により、変更計画システムは、遷移条件を含む状態マシン群から、効率的な計算アルゴリズムを用いて変更計画を作成できる。
【０２１９】
また、変更計画システム１０は、状態マシン内の状態を、複数の条件が組合せられた遷移条件に従って遷移させてもよい。
【０２２０】
そのような構成により、変更計画システムは、複雑な遷移条件を含む状態マシン群からも変更計画を作成できる。
【０２２１】
また、状態マシン群変換部１１は、単一状態マシン内の状態に、状態マシン群に含まれる各状態マシンの現在状態および要求状態を入力してもよい。
【０２２２】
そのような構成により、変更計画システムは、状態マシン群に含まれる状態マシン内の状態を反映した上で変更計画を作成できる。
【０２２３】
また、変更計画システム１０は、単一状態マシン内の状態が遷移させられる時の順序の基準である、１または複数の所定の遷移から構成される遷移順序を作成する経路探索部（例えば、経路探索部１０２）を含んでもよい。
【０２２４】
そのような構成により、変更計画システムは、複数の遷移間に関係がある状態マシン群からも変更計画を作成できる。
【０２２５】
また、変更計画システム１０は、遷移条件によって関連付けられる複数の状態マシン内の状態それぞれの遷移間のみに順序性を付与することによって、全順序集合としての遷移順序を半順序集合としての遷移順序に変換する遷移順序変換部（例えば、遷移順序変換部１０３）を含んでもよい。
【０２２６】
そのような構成により、変更計画システムは、全体の実施時間がより短縮された変更計画を作成できる。
【０２２７】
また、変更計画システム１０は、状態が遷移させられるように誘発される可能性がない状態マシンを特定し、状態マシン群から状態マシンおよび状態マシンに関連する遷移条件を除去する状態マシン簡略化部（例えば、状態マシン簡略化部１０４）を含んでもよい。
【０２２８】
そのような構成により、変更計画システムは、システムの変更計画作成における計算量を削減できる。
【０２２９】
また、状態マシン簡略化部は、単一状態マシン内の状態の中で、現在状態が遷移不可能な状態を除去してもよい。
【０２３０】
そのような構成により、変更計画システムは、システムの変更計画作成における計算量を削減できる。
【符号の説明】
【０２３１】
１０、１００  変更計画システム
１１、１０１  状態マシン群変換部
１０２  経路探索部
１０３  遷移順序変換部
１０４  状態マシン簡略化部
２０１  入出力部
【図１】
2015215885.tif 000003
【図２】
2015215885.tif 000004
【図３】
2015215885.tif 000005
【図４】
2015215885.tif 000006
【図５】
2015215885.tif 000007
【図６】
2015215885.tif 000008
【図７】
2015215885.tif 000009
【図８】
2015215885.tif 000010
【図９】
2015215885.tif 000011
【図１０】
2015215885.tif 000012
【図１１】
2015215885.tif 000013
【図１２】
2015215885.tif 000014
【図１３】
2015215885.tif 000015
【図１４】
2015215885.tif 000016
【図１５】
2015215885.tif 000017
【図１６】
2015215885.tif 000018
【図１７】
2015215885.tif 000019
【図１８】
2015215885.tif 000020
【図１９】
2015215885.tif 000021
【図２０】
2015215885.tif 000022
【図２１】
2015215885.tif 000023
【図２２】
2015215885.tif 000024
【図２３】
2015215885.tif 000025