(57)【要約】【課題】内部に共通の部分状態機械を含まない有限状態機械の状態数を削減する。【解決手段】有限状態機械の中の遷移条件について、同一の遷移条件が複数あり、その遷移条件がある変数の値または値の変化を条件とする場合に、その変数を状態とする新たな有限状態機械を作成し、元の有限状態機械ではその遷移の前後の状態を統合することで状態数を削減する。【選択図】  図２
2020135253.tif 000002
【特許請求の範囲】
【請求項１】
第一の変数の値または値の変化を条件とする第一の遷移条件を複数備える第一の有限状態機械の状態数を削減する方法において、
第一の遷移条件を抽出するステップと、
第一の変数を抽出するステップと、
第一の変数を状態とする第二の有限状態機械を作成するステップと、
第一の有限状態機械からその遷移の前後の状態を統合するステップと、
を有することを特徴とする、有限状態機械の状態数削減方法。
【請求項２】
請求項１における有限状態機械の状態数削減方法において、
前記統合するステップにおいて、統合する遷移のアクションが異なる場合は、遷移元の状態を判定するガード条件を加えることを特徴とする、有限状態機械の状態数削減方法。
【請求項３】
第一の変数の値または値の変化を条件とする第一の遷移条件を複数備える第一の有限状態機械の状態数を削減する状態削減装置において、
第一の遷移条件を抽出する第一の処理部と、
第一の変数を抽出する第二の処理部と、
第一の変数を状態とする第二の有限状態機械を作成する第三の処理部と、
第一の有限状態機械からその遷移の前後の状態を統合する第四の処理部と、
を有することを特徴とする、有限状態機械の状態削減装置。
【請求項４】
請求項３における有限状態機械の状態削減装置において、
前記第四の処理部において、統合する遷移のアクションが異なる場合は、遷移元の状態を判定するガード条件を加えることを特徴とする、有限状態機械の状態削減装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は自動運転を行うための車載コンピュータ（ＥＣＵ）の安全機構などに用いる、有限状態機械の状態数を削減するソフトウェアの技術に関する。
【背景技術】
【０００２】
有限状態機械の状態数を削減する方法としては、たとえば下記特許文献１の方法がある。特許文献１では、有限状態機械の中の部分的な状態遷移に注目し、その部分的な状態遷移が有限状態機械の中で複数回あらわれる場合に、その部分的な状態遷移を切り出し、小さい有限状態機械の組合せで表現することで、全体の状態数を削減する。例えば図９に示すように、状態３００１、３００２、３００３、３００４からなる状態遷移と、状態３００７、３００８、３００５、３００６からなる状態遷移とは共通であるので、ｓｕｂ１として切り出す。これにより全体の状態数を１２から１１に削減する。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００２−２９７６８１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
特許文献１の方法では、複数の同一の部分的な状態遷移を含む場合でしか状態数を削減できない。そのため、切り出したい部分的な状態遷移について、異なる遷移条件を含む場合には切り出すことができず、状態数を削減できない。例えば、図３は図９と異なり、状態３００１、３００２、３００３、３００４からなる状態遷移と、状態３００７、３００８、３００５、３００６からなる状態遷移とは遷移３１１２と３１１５、３１１１と３１１６、３１１４と３１１７，３１１３と３１１８とがそれぞれ異なるため、特許文献１の方法で切り出すことができない。
【課題を解決するための手段】
【０００５】
有限状態機械の中の遷移条件について、同一の遷移条件が複数あり、その遷移条件がある変数の値の変化を条件とする場合に、その変数を状態とする新たな有限状態機械を作成し、元の有限状態機械ではその遷移の前後の状態を統合することで状態数を削減する。
【発明の効果】
【０００６】
有限状態機械の中で、同一の状態遷移を含まない場合においても、状態数を削減することができる。
【図面の簡単な説明】
【０００７】
【図１】実施例１の全体構成図
【図２】状態削減プログラムのフローチャート
【図３】状態削減前の有限状態機械
【図４】状態削減中の有限状態機械
【図５】状態削減後の有限状態機械
【図６】図３の状態遷移とアクション、状態と状態の意味の対応表
【図７】図４の状態遷移とアクション、状態と状態の意味の対応表
【図８】図５の状態遷移とアクション、状態と状態の意味の対応表
【図９】特許文献１の方法を適用可能な有限状態機械
【発明を実施するための形態】
【０００８】
以下、本発明の実施例を、図面を用いて説明する。
【実施例１】
【０００９】
図１は実施例１の全体構成図である。
【００１０】
図１に示す通り、実施例１の全体構成はＰＣ１とコンソール１９からなる。さらに、ＰＣ１はＣＰＵ１２、メモリ１１、ＨＤＤ１３を含み、内部バスやアダプタで介して互いに接続している。またコンソール１９とＣＰＵ１２も、アダプタや内部バスを介して互いに接続している。
【００１１】
メモリ１１は作業中の有限状態機械１１１、状態削減プログラム１１２を含む。ＨＤＤ１３は削減前の有限状態機械１３１、削減後の有限状態機械１３２を含む。
【００１２】
ＣＰＵ１２はメモリ１１に格納したプログラムを実行する。なお、以降の説明では、プログラムを主語として説明することもあるが、実行主体はあくまでＣＰＵである。またメモリ１１内に格納したプログラムの機能は、次の図２を用いて説明する。
【００１３】
コンソール１９はオペレーターが、削減前の有限状態機械１３１の編集や保存・読み出し(作業中の有限状態機械１１１へのコピー)の指示をしたり、状態削減プログラム１１２の起動を指示したり、削減後の有限状態機械１３２を表示したり保存(作業中の有限状態機械１１１からのコピー)を指示するために用いる。
【００１４】
図２は、状態削減プログラム１１２の処理内容を示す、フローチャートである。状態削減プログラム１１２は、削減前の有限状態機械１３１が作業中の有限状態機械１１１として保存された後、オペレーターが指示することにより起動する。
【００１５】
状態削減プログラム１１２は、作業中の有限状態機械１１１の中から、同一の遷移条件を抽出し（ステップＳ１０１）、同一の遷移条件が見つからなかった場合は処理を終了する（ステップＳ１０２Ｎ）。同一の遷移条件が見つかった場合（ステップＳ１０２Ｙ）、状態削減プログラム１１２は、見つかった遷移条件が参照している変数（その変数の値の変化を条件となっている変数）を抽出する（ステップＳ１０３）。変数が見つからなかった場合（ステップＳ１０４Ｎ）ステップＳ１０１から繰り返す。変数が見つかった場合（ステップＳ１０４Ｙ）、状態削減プログラム１１２はステップＳ１０３で見つかった変数を状態とする、新たな有限状態機械を作成する（ステップＳ１０５）。ステップＳ１０５において状態削減プログラム１１２は、ステップＳ１０２Ｙにおいて見つかった状態遷移を、作成した有限状態機械にコピーする。その際、コピーする状態遷移が、条件は同じでもアクションが異なる場合、どのアクションを起動すべきかは、元の有限状態機械の状態によって決まるため、元の有限状態機械の遷移元の状態をコピー先の状態遷移のガード条件として追加する。また、コピーする状態遷移の前後の状態の状態変数の値が異なる場合、状態削減プログラム１１２は、その状態変数の値の差分を、作成した状態遷移のそれぞれの状態にマッピングし、元の有限状態機械の状態から削除する。
【００１６】
さらに状態削減プログラム１１２は、作業中の有限状態機械１１１において、ステップＳ１０３で抽出した遷移の前後の状態を統合する（ステップＳ１０６）。ステップＳ１０５において、元の有限状態機械の遷移元の状態を、状態遷移のガード条件として追加した場合は、状態削減プログラム１１２は、ガード条件として追加した状態を統合後の状態に書き換える。さらにステップＳ１０６において、統合する状態の間で状態変数の値の差分が残っている場合、状態削減プログラム１１２は、ステップＳ１０５で作成した有限状態機械の変数を参照するよう、統合後の状態の状態変数の参照式を変更する。
【００１７】
次に、図３から図５を用いて、状態削減プログラム１１２の処理例を示す。図３が状態削減前の有限状態機械である。状態削減プログラム１１２はステップＳ１０１において、状態削減前の有限状態機械から同一の遷移条件を抽出する。図３においては、同一の遷移条件として、遷移３１０１と３１０３、３１０５、３１０７、および、遷移３１０２と３１０４、３１０６、３１０８とを抽出する。さらに状態削減プログラム１１２はステップＳ１０３において抽出した遷移条件から、その遷移条件が参照している変数を抽出する。ここでは状態削減プログラム１１２はｖ１を抽出する。抽出した状態遷移のアクションの違いがある場合についての動作例は、後程まとめて説明することとし、ここでは違いがないとして説明する。
【００１８】
さらに状態削減プログラム１１２はステップＳ１０５において、ステップＳ１０３で見つかった変数を状態とする、新たな有限状態機械を作成する。この例では図４の有限状態機械３２００を作成する。ここで、状態３２０１は変数ｖ１がａ、状態３２０２は変数ｖ１がｂの状態である。有限状態機械３２００により、遷移３１０１と３１０３、３１０５、３１０７、および、遷移３１０２と３１０４、３１０６、３１０８の前後の状態の差分が表現できるようになったので、状態３００１と３００２、状態３００３と３００４、状態３００５と３００６、状態３００７と３００８が統合可能である。そこで状態削減プログラム１１２はステップＳ１０６において、遷移の前後の状態を統合する。統合後の有限状態機械が図４の有限状態機械３４００である。なお、ステップＳ１０６における統合前後の状態の状態変数の値の差分が有限状態機械３４００に残る場合についての動作例は、後程まとめて説明することとし、ここでは違いがないとして説明する。
【００１９】
同様に状態削減プログラム１１２はステップＳ１０１において、有限状態機械３４００から、遷移３４１１と３４１５、および、遷移３４１２と３４１６とを抽出、ステップＳ１０３において、変数ｖ２を抽出し、ステップＳ１０５において、図５の有限状態機械３３００を作成する。ここで、状態３３０１は変数ｖ２がｃ、状態３３０２は変数ｖ２がｄの状態である。さらに状態削減プログラム１１２はステップＳ１０６において、遷移の前後の状態を統合する。統合後の状態遷移が図５の有限状態機械３５００である。有限状態機械３５００には同一の遷移条件を含まないため、状態削減プログラム１１２はステップＳ１０２Ｎに分岐して処理を終了する。
【００２０】
このように、状態削減プログラム１１２はステップＳ１０５において部分的な有限状態機械を切り出し、ステップＳ１０６において切り出し後の有限状態機械の状態を統合し、切り出した状態機械との組み合わせによってもとの状態を表すことで、全体の状態数を削減する。図３から図５の例では、状態数が８から６に削減できている。
【００２１】
次に、図６から図８を用いて、ステップＳ１０３でのアクションの違い、ステップＳ１０６での統合前後の状態の状態変数の値の差分が有限状態機械３４００に残る場合についての動作例を示す。
【００２２】
図６は図３に示す有限状態機械の状態と状態変数の値との対応表、および状態遷移とアクションとの対応表を示す。表４０１は状態に付与した符号とその状態の状態変数の値との対応を示す表である。表４０２は、図３の有限状態機械の状態遷移に付与した符号と状態遷移との対応を示す。
【００２３】
表４０２は状態遷移として、遷移の条件およびアクションを条件／アクションの書式で示している。例えば、符号３１０１の状態遷移は、変数ｖ１がａからｂに変化することが遷移の条件であり、Ａ−１がその時に実行すべきアクションである。
【００２４】
図６の内容は、図７の説明で引用される。
【００２５】
図７は図４に示す有限状態機械の状態と状態変数の値との対応表、および状態遷移とアクション、新しい状態変数の値との元の状態変数の値との対応表、を示している。表４１１は有限状態機械３４００の状態に付与した符号と、その状態での状態変数の値との対応を示す。表４１２a、表４１２ｂは図４の有限状態機械の状態遷移に付与した符号と状態遷移との対応を示す。表４１２aは状態削減プログラム１１２のステップＳ１０６における状態統合の前の遷移の条件を示し、表４１２ｂはステップＳ１０６における状態統合の後の遷移の条件を示している。  
表４１２a、表４１２ｂは状態遷移として、遷移の条件およびアクションを条件／アクションの書式で示しており、条件は［ガード条件］，イベントの書式であらわしている。例えば、符号３４１１の状態遷移は、変数ｖ２がｃからｄに変化するときに、ガード条件に従って、変数ｖ１がａならアクションＡ−１１が、変数ｖ１がｂならアクションＡ−１３がその時に実行すべきアクションであることを示す。また、符号３２４１の遷移は、ガード条件として表４１１に示す状態変数の値を参照しており、値がＳ−１−１の時、すなわち符号３４０１の状態であるときは、Ａ−０１がその時に実行すべきアクションであることを示している。
【００２６】
状態削減プログラム１１２のステップＳ１０５において有限状態機械３２００を作成する際、遷移３１０１と３１０３、３１０５、３１０７を統合して遷移３２４１を、遷移３１０２と３１０４、３１０６、３１０８を統合して遷移３２４２を生成する。ここで、統合する遷移のアクションが異なる場合は、遷移元の状態によって、すなわち遷移前の状態変数の値によって、どの遷移かを区別する必要がある。そこで、ガード条件として、遷移前の状態変数の値の判定を追加する。遷移前の状態変数の値の判定を追加した表が表４１２aである。
【００２７】
状態削減プログラム１１２のステップＳ１０６において状態を統合する際、遷移条件を統合後の状態変数の値の判定に置き換える必要がある。表４１２aにおいては遷移３２４１および遷移３２４２が、統合前の状態変数を参照しているので、統合後の状態変数ｖ’を参照するように更新する。また、統合に伴い、遷移３１１１と遷移３１１３、遷移３１１５と遷移３１１７、遷移３１１２と遷移３１１４、遷移３１１６と遷移３１１８、遷移３１２１と遷移３１２３、遷移３１２２と遷移３１２４もそれぞれ統合され、統合前後は変数ｖ１で区別が可能なため、それぞれの遷移に変数ｖ１を判定するガード条件を追加する。ガード条件を更新・追加した表が表４１２ｂである。
【００２８】
表４１３は、有限状態機械３４００の状態変数の値および有限状態機械３２００の状態変数の値と、図３の有限状態機械の状態変数の値との対応を示す。図３の有限状態機械の状態は、新規に切り出した有限状態機械３２００の状態と、統合後の有限状態機械３５００の状態との組合せで表現できる。例えば、図３での状態３００１は状態３４０１に統合されており、同じく状態３４０１に統合された状態３００２とは有限状態機械３２００の状態が異なり、状態３００１は状態３２０１すなわちｖ＝＝ａ、状態３００２は状態３２０２すなわちｖ＝＝ｂで表される。このようにして作成した表が表４１３であり、この表を参照することで統合後の有限状態機械から元の有限状態機械の状態を参照することができる。
【００２９】
図８は図５に示す有限状態機械の状態と状態変数の値との対応表、および状態遷移とアクション、新しい状態変数の値との元の状態変数の値との対応表、を示している。表４２１は有限状態機械３４００の状態に付与した符号と、その状態での状態変数の値との対応を示す。表４２２a、表４２２ｂは図４の有限状態機械の状態遷移に付与した符号と状態遷移との対応を示す。表４２２aは状態削減プログラム１１２のステップＳ１０６における状態統合の前の遷移の条件を示し、表４２２ｂはステップＳ１０６における状態統合の後の遷移の条件を示している。表４２２a、表４２２ｂの書式は表４１２a、表４１２ｂと同様である。
【００３０】
状態削減プログラム１１２のステップＳ１０５において有限状態機械３３００を作成する際、統合する遷移について変数ｖ２を用いで判定するガード条件を追加した表が表４２２aである。作成の方法は表４１２aと同様なので、説明を省略する。
【００３１】
状態削減プログラム１１２のステップＳ１０６において状態を統合する際、遷移条件を統合後の状態変数の値の判定に置き換える必要があり、ガード条件を更新・追加した表が表４２２ｂである。表４２２ｂの作成方法は表４１２ｂの作成方法と同様であるため、説明を省略する。
【００３２】
表４２３は、有限状態機械３５００の状態変数の値および有限状態機械３２００の状態変数の値、有限状態機械３３００の状態変数の値と、図３の有限状態機械の状態変数の値との対応を示す。表４２３の作成方法は表４１３の作成方法と同様であるため、説明を省略する。
【００３３】
このようにして、統合する遷移のアクションや統合する状態の状態変数の値に差分がある場合でも、新たに定義した有限状態機械の状態と組み合わせることにより、区別ができるため、本発明の方法によれば、元の有限状態機械との等価性を保ちながら、状態数を削減することができる。
【符号の説明】
【００３４】
１：ＰＣ
１１：メモリ
１２：ＣＰＵ
１３：ＨＤＤ
１９：コンソール
１１２：状態削減プログラム
Ｓ１０１、Ｓ１０３：切り出す状態機械の状態を抽出する処理
Ｓ１０５：状態機械を切り出す処理
Ｓ１０６：切り出し後の有限状態機械の状態を統合する処理
【図１】
2020135253.tif 000003
【図２】
2020135253.tif 000004
【図３】
2020135253.tif 000005
【図４】
2020135253.tif 000006
【図５】
2020135253.tif 000007
【図６】
2020135253.tif 000008
【図７】
2020135253.tif 000009
【図８】
2020135253.tif 000010
【図９】
2020135253.tif 000011