(57)【要約】【課題】装置自らが実数値条件を変更可能とし、現実的な環境下で装置が現実的な時間内に最適な制御プログラムを自律的に求め得る制御システムおよび制御方法を提供する。【解決手段】制御システム１は、装置の内部状態と実数値条件とを対応付け、内部状態に関連付けられたノードとパスとで構成されるプログラムを一定数生成させる初期個体生成手段２と、実数値条件下でシミュレーションを行って適応度を計算する適応度計算手段３と、目標適応度Ｑに達したプログラムの有無を判断する判断手段４と、エリート保存して親選択を行う親選択手段５と、プログラム中の内部状態の追加または削除を行う状態数増減手段６と、各プログラムを交叉させる交叉手段７と、各プログラムに突然変異を生じさせる突然変異手段８と、を備え、前記各手段における処理を繰り返し行って、判断手段４で目標適応度に達したと判断されたプログラム出力するように構成されている。【選択図】  図１
2005228141.tif 000002
【特許請求の範囲】
【請求項１】
装置を自律的に動作させるための制御システムであって、
前記装置の遷移可能な内部状態と実数値で規定される制御条件とを対応付け、前記内部状態に関連付けられた非終端記号と終端記号とよりなるノードと前記ノードを連結させるパスとで構成されるプログラムを一定数生成させる初期個体生成手段と、
前記各プログラムについて、それぞれプログラムの実行中の前記内部状態の遷移に伴って変化し得る前記制御条件の下でシミュレーションを行い、所定の評価式に基づいて前記各プログラムについてそれぞれ適応度を計算する適応度計算手段と、
前記適応度が所定の目標適応度に達したプログラムの有無を判断する判断手段と、
前記判断手段において前記目標適応度に達したプログラムがないと判断された場合に、前記適応度が最大のプログラムを隔離し、前記適応度が最大のプログラム以外の前記各プログラムまたは前記適応度が最大のプログラム以外の前記各プログラムと前記適応度が最大のプログラムのコピープログラムについて選択を行う親選択手段と、
前記親選択手段で選択された前記各プログラムについて、所定の規則に基づいて、それぞれプログラム中の前記内部状態の追加または削除を行う状態数増減手段と、
前記状態数増減手段で生成された各プログラムを一定の割合で交叉させる交叉手段と、
前記交叉手段で生成された各プログラムに一定の割合で突然変異を生じさせる突然変異手段と、
を備え、
前記突然変異手段で生成された各プログラムを前記適応度計算手段に移して前記各手段による処理を繰り返して行い、
前記判断手段においては、前記各プログラムに、前記隔離された適応度が最大のプログラムを含めて判断し、
前記判断手段において前記目標適応度に達したプログラムがあると判断された場合には、そのプログラムを解として前記各手段による処理を終了し、前記解であるプログラムを前記装置に出力するように構成されていることを特徴とする制御システム。
【請求項２】
前記初期個体生成手段は、１つの前記内部状態に対して１つの前記実数値で規定される制御条件が対応付けられ、かつ、１つの前記内部状態に対して前記ノードと前記パスとで構成される１つの木構造プログラムが関連付けられた状態の単数または複数の前記内部状態からプログラムを一定数生成するように構成されており、前記生成されたプログラムには、前記内部状態の数、前記内部状態に対応付けられた前記制御条件の内容、または前記内部状態に関連付けられた前記木構造プログラムの構造が互いに異なるプログラムが含まれることを特徴とする請求項１に記載の制御システム。
【請求項３】
前記初期個体生成手段は、１つの前記内部状態に対して１つの前記実数値で規定される制御条件が対応付けられ、かつ、前記内部状態に関連付けられた不変数の非終端記号と終端記号とよりなるノードと前記ノードを連結させる前記内部状態に関連付けられたパスとで構成されるプログラムを一定数生成するように構成されており、前記生成されたプログラムには、前記内部状態に対応付けられた前記制御条件の内容、前記ノードを連結させる前記パスの数、または前記パスの連結の仕方が互いに異なるプログラムが含まれることを特徴とする請求項１に記載の制御システム。
【請求項４】
前記非終端記号には、実数値を引数とする論理式が含まれるように構成されていることを特徴とする請求項１乃至請求項３のいずれか一項に記載の制御システム。
【請求項５】
前記非終端記号である論理式に閾値として与えられる引数の値を、遺伝的アルゴリズムにより決定するように構成されていることを特徴とする請求項４に記載の制御システム。
【請求項６】
装置を自律的に動作させるための制御方法であって、
前記装置の遷移可能な内部状態と実数値で規定される制御条件とを対応付け、前記内部状態に関連付けられた非終端記号と終端記号とよりなるノードと前記ノードを連結させるパスとで構成されるプログラムを一定数生成させる初期個体生成処理と、
前記各プログラムについて、それぞれプログラムの実行中の前記内部状態の遷移に伴って変化し得る前記制御条件の下でシミュレーションを行い、所定の評価式に基づいて前記各プログラムについてそれぞれ適応度を計算する適応度計算処理と、
前記適応度が所定の目標適応度に達したプログラムの有無を判断する判断処理と、
前記判断処理において前記目標適応度に達したプログラムがないと判断された場合に、前記適応度が最大のプログラムを隔離し、前記適応度が最大のプログラム以外の前記各プログラムまたは前記適応度が最大のプログラム以外の前記各プログラムと前記適応度が最大のプログラムのコピープログラムについて選択を行う親選択処理と、
前記親選択処理で選択された前記各プログラムについて、所定の規則に基づいて、それぞれプログラム中の前記内部状態の追加または削除を行う状態数増減処理と、
前記状態数増減処理で生成された各プログラムを一定の割合で交叉させる交叉処理と、
前記交叉処理で生成された各プログラムに一定の割合で突然変異を生じさせる突然変異処理と、
を行い、
前記突然変異処理で生成された各プログラムを前記適応度計算処理に移して前記各処理を繰り返して行い、
前記判断処理においては、前記各プログラムに、前記隔離された適応度が最大のプログラムを含めて判断し、
前記判断処理において前記目標適応度に達したプログラムがあると判断された場合には、そのプログラムを解として前記各処理を終了し、前記解であるプログラムを前記装置に出力することを特徴とする制御方法。
【請求項７】
前記初期個体生成処理では、１つの前記内部状態に対して１つの前記実数値で規定される制御条件が対応付けられ、かつ、１つの前記内部状態に対して前記ノードと前記パスとで構成される１つの木構造プログラムが関連付けられた状態の単数または複数の前記内部状態からプログラムを一定数生成し、前記生成されたプログラムには、前記内部状態の数、前記内部状態に対応付けられた前記制御条件の内容、または前記内部状態に関連付けられた前記木構造プログラムの構造が互いに異なるプログラムが含まれることを特徴とする請求項６に記載の制御方法。
【請求項８】
前記初期個体生成処理では、１つの前記内部状態に対して１つの前記実数値で規定される制御条件が対応付けられ、かつ、前記内部状態に関連付けられた不変数の非終端記号と終端記号とよりなるノードと前記ノードを連結させる前記内部状態に関連付けられたパスとで構成されるプログラムを一定数生成し、前記生成されたプログラムには、前記内部状態の数、前記内部状態に対応付けられた前記制御条件の内容、または前記ノードを連結させる前記パスの数または連結の仕方が互いに異なるプログラムが含まれることを特徴とする請求項６に記載の制御方法。
【請求項９】
前記非終端記号には、実数値を引数とする論理式が含まれることを特徴とする請求項６乃至請求項８のいずれか一項に記載の制御方法。
【請求項１０】
前記非終端記号である論理式に閾値として与えられる引数の値を、遺伝的アルゴリズムにより決定することを特徴とする請求項９に記載の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、遺伝的手法を用いた制御システムおよび制御方法に係り、特に、適応型ＧＰ−オートマトンや遺伝的オートマトンの手法を実数値で規定される制御条件においても適用可能である制御システムおよび制御方法に関する。
【背景技術】
【０００２】
近年、ロボット等の装置が自らの動作を自律的に制御するための制御方法や制御システムの研究が盛んに行われている。特に、センサ等の感覚入力手段を備えた装置が、与えられた環境（外部情報）の中で、求められる結果を得るために自らの動作を最適化する制御プログラムを自動生成させ、それに基づいて自律的に最適な行動をとるようにする装置の制御方法や制御システムは、工業的に応用範囲が広く、鋭意開発が進められている。
【０００３】
このような最適化されたプログラムを自動生成させる手法としては、従来から、遺伝的プログラミング（Genetic Programming。ＧＰと略される。）がよく知られている。遺伝的プログラミングは、生物界の遺伝法則や進化論を工学的に取り入れて、与えられた条件に対する適応度の高いプログラムを自動生成させること等を目的とする遺伝的手法である。つまり、遺伝的プログラミングでは、複数の初期プログラムを交叉させ、突然変異させて新たなプログラムを生成し、前記所与の条件に対する適応度が低いプログラムを淘汰し、適応度が高いプログラムを増殖させ、目標の適応度に達するまで淘汰や交叉、突然変異等を繰り返すことで、より適応度が高いプログラムを見出していくという進化過程を採る。
【０００４】
この遺伝的プログラミングにより得られる解プログラムは木構造として表現されることが多く、図１９に示すように、通常、葉の部分である終端記号（図ではＮｏｄｅ４やＮｏｄｅ５等）とその他の部分である非終端部分（図ではＮｏｄｅ１やＮｏｄｅ２等）がパスにより有向連結された状態に表現される。プログラムに一定の入力があると、プログラムの根である非終端記号（図ではＮｏｄｅ１）の論理式に基づいて論理演算が行われ、演算結果に応じてパスをたどることにより、次々と非終端記号の論理式で論理演算が行われて、最終的に１つの終端記号に対応する一定の出力、すなわち、プログラムが制御プログラムの場合は一定の動作（行動）が出力される。
【０００５】
しかし、このような一般的な遺伝的プログラミングでは、例えば、図２０に示すような簡単な迷路でスタート地点Ｓから出発してゴール地点Ｇに最短路で到達するという課題を満足する解プログラムすら得られない。この迷路では、装置は、東西南北の方向（図２０参照）の壁の有無をそれぞれ検知する４つセンサを備え、センサで壁の有無を検知しながらその入力に応じていずれか１方向に１マスずつ移動して行く。
【０００６】
つまり、この迷路のａ点およびｂ点において、装置には、ともに南北方向に壁があり東西方向に壁がないという同一の入力が与えられる。装置は、ａ点では東方向に移動し、ｂ点では西方向に移動しなければゴールできない。しかし、前述したように、遺伝的プログラミングでは同一の入力に対して１つの最適な動作を出力する解プログラムが与えられるから、仮にａ点で東方向に１コマ移動させる解プログラムが得られれば、この解プログラムはｂ点においても同様に装置を東方向に１コマ移動させる。したがって、装置はゴール地点Ｇに到達することができず、結局、遺伝的プログラミングではこの迷路探索問題を解くことは不可能ということになる。
【０００７】
このような一般的な遺伝的プログラミングの問題を解決するため、遺伝的プログラミングと有限オートマトンとを組み合わせたＧＰ−オートマトン（GP-Automata）という手法が提案されている。この手法では、前記のように同一の入力に対して装置に異なる出力をさせるために、装置の内部状態という概念を導入する。ＧＰ−オートマトンでは、あらかじめ有限の内部状態の状態数が設定され、図２１に示すように、各内部状態には状態番号が付され、各内部状態ごとに木構造プログラム（制御木とも言われる。）が関連付けられて、全体として１つのプログラムが構成される。
【０００８】
このプログラムでは、ある状態番号の内部状態の装置に入力があると、その内部状態に関連付けられた木構造プログラムの演算処理により、一定の動作と次に遷移すべき状態番号との組が出力される。装置は、その出力に基づいて一定の動作を行うと同時に、その内部状態を次の状態番号に対応する内部状態に遷移させる。そして、新たに入力があると、その入力は遷移した後の内部状態に関連付けられた木構造プログラムにより演算処理されるというようにして動作と状態遷移とが繰り返される。この手法を用いれば、図２０に示した迷路のａ点とｂ点とで装置の内部状態を変えることで、装置をａ点では東方向に、ｂ点では西方向に移動させることができる。このＧＰ−オートマトンにおいても、最適な解プログラムを得るために、複数のプログラムに対して淘汰や交叉、突然変異等を繰り返して所与の条件に対する最適な解プログラムを求めていくという進化過程が採られる。
【０００９】
しかし、このＧＰ−オートマトンでは、あらかじめ設定される内部状態の状態数が適切であれば問題を解くことができるが、状態数が足りないと問題の解は得られず、状態数が多すぎると進化過程でプログラム中に非終端記号や終端記号からなるノードの数が増大して冗長な部分が増えて探索領域が膨大になり、必ずしも最適化が容易には行えなくなるという問題があった。
【００１０】
ＧＰ−オートマトンの性能があらかじめ設定された状態数に左右されるという問題点を克服するために、最適解を得るための進化過程で内部状態の状態数を増減させる適応型ＧＰ−オートマトン（Adaptive GP-Automata。以下、ＡＧＰＡという。）が提案されている（非特許文献１参照）。また、ＧＰ−オートマトンの進化過程で生じるプログラム中の冗長なノード数の増加を抑えるために、プログラム中のノードを固定し、非終端記号に状態を設定し、状態番号の違いによりたどるパスを変えるようにして、同一の入力に対して異なる出力を得る遺伝的オートマトン（Genetic Automata Generation。以下、ＧＡＵＧＥという。）の手法も提案されている（非特許文献２）。
【非特許文献１】片岡  寛明、外２名、「適応型ＧＰ−オートマトンによるエージェントの行動制御」、情報処理学会論文誌、平成１５年９月、第４４巻、第９号、ｐ．２３９０−２４００
【非特許文献２】片岡  寛明、外２名、「遺伝的オートマトンＧＡＵＧＥ」、情報処理学会論文誌、平成１４年７月、第４３巻、第７号、ｐ．１２３４−１２４３
【発明の開示】
【発明が解決しようとする課題】
【００１１】
しかしながら、前記ＡＧＰＡやＧＡＵＧＥの手法は、図２０のような簡単な迷路やさらに複雑になった迷路等の問題ではその性能が証明されているが、これらの手法では、装置への入力として、図２０に示した迷路の場合のように壁がある（１）、ない（０）の２値化された信号しか扱うことができない。ＡＧＰＡやＧＡＵＧＥにおける装置のモデルは、壁の有無のみを判断できるセンサを備えていればよく、センサの分解能等はまったく考慮する必要がない。
【００１２】
しかし、実際のロボット等の装置においては、例えば、装置に搭載されるセンサを適正に作動させるためには、少なくとも分解能の設定が必要であり、その値としては１／１、１／２、１／４、…、１／５１２、１／１０２４等のように実数値を取る。そのため、ＡＧＰＡやＧＡＵＧＥを実際の装置に応用する場合には、実数値を取るセンサの分解能や種々の閾値は、通常、所与のものとして設計者があらかじめ装置に設定することにより対処する。しかし、従来のＡＧＰＡやＧＡＵＧＥで設計者があらかじめ実数値を設定しても、例えば、図２２に示すような障害物がある領域でスタート位置からゴールを探索するような簡単な問題を解くことは、事実上、困難である。
【００１３】
図２２に示す探索問題は、円柱側面に８つのセンサを有する装置Ｘがスタート位置Ｓから障壁Ｙの開孔Ｚを通り抜けてゴールエリアＧの内側に入るまでの動作を最短時間で行うための最適化されたプログラムを求めるという問題である。この場合、例えば、設計者がセンサの分解能を１／１０２４に設定してＡＧＰＡやＧＡＵＧＥで最適解を求めようとしても、装置Ｘはいわば慎重になり過ぎてしまい、障壁Ｙのスタート位置Ｓ側の領域Ｒ１を右往左往するだけで障壁Ｙの開孔Ｚの領域Ｒ２を通過しない。また、設計者がセンサの分解能を１／１６に設定すると、装置Ｘはいわば大胆に行動するが、障壁Ｙや開孔Ｚの内面等に衝突してしまい、結局、障壁Ｙの開孔Ｚを通過してゴールエリアＧ側の領域Ｒ３に進入できないという結果になる。
【００１４】
このように、実数値を扱う現実問題にＡＧＰＡやＧＡＵＧＥの手法を応用する際に、センサの分解能のような実数値で規定される制御条件（以下、実数値条件という。）をあらかじめ固定された値として設定しても、問題は解決できない。また、たとえ最適解が得られるとしても、最適な制御条件を設計者が試行錯誤を繰り返しながら見出していくには膨大な時間が掛かり、現実的ではない。
【００１５】
図２２のような探索問題では、スペースが広い領域Ｒ１や領域Ｒ３では装置のセンサの分解能は粗くてもよく、また障壁Ｙの開孔Ｚの内部である領域Ｒ２のようなスペースが狭い領域では分解能は細かくする方がよい。つまり、センサの分解能等の実数値条件を何らかの方法で状況に応じて変更できるようにすべきであり、そのようにしないと図２２の探索問題に例示されるような現実的な問題をＡＧＰＡやＧＡＵＧＥの手法で解くことは困難である。
【００１６】
そこで、本発明の目的は、装置自らが実数値条件を的確に変更することを可能とし、現実的な環境下で装置が現実的な時間内に最適化された制御プログラムを自律的に求めることが可能な制御システムおよび制御方法を提供することである。
【課題を解決するための手段】
【００１７】
前記の問題を解決するために、請求項１に記載の制御システムは、
装置を自律的に動作させるための制御システムであって、
前記装置の遷移可能な内部状態と実数値で規定される制御条件とを対応付け、前記内部状態に関連付けられた非終端記号と終端記号とよりなるノードと前記ノードを連結させるパスとで構成されるプログラムを一定数生成させる初期個体生成手段と、
前記各プログラムについて、それぞれプログラムの実行中の前記内部状態の遷移に伴って変化し得る前記制御条件の下でシミュレーションを行い、所定の評価式に基づいて前記各プログラムについてそれぞれ適応度を計算する適応度計算手段と、
前記適応度が所定の目標適応度に達したプログラムの有無を判断する判断手段と、
前記判断手段において前記目標適応度に達したプログラムがないと判断された場合に、前記適応度が最大のプログラムを隔離し、前記適応度が最大のプログラム以外の前記各プログラムまたは前記適応度が最大のプログラム以外の前記各プログラムと前記適応度が最大のプログラムのコピープログラムについて選択を行う親選択手段と、
前記親選択手段で選択された前記各プログラムについて、所定の規則に基づいて、それぞれプログラム中の前記内部状態の追加または削除を行う状態数増減手段と、
前記状態数増減手段で生成された各プログラムを一定の割合で交叉させる交叉手段と、
前記交叉手段で生成された各プログラムに一定の割合で突然変異を生じさせる突然変異手段と、
を備え、
前記突然変異手段で生成された各プログラムを前記適応度計算手段に移して前記各手段による処理を繰り返して行い、
前記判断手段においては、前記各プログラムに、前記隔離された適応度が最大のプログラムを含めて判断し、
前記判断手段において前記目標適応度に達したプログラムがあると判断された場合には、そのプログラムを解として前記各手段による処理を終了し、前記解であるプログラムを前記装置に出力するように構成されていることを特徴とする。
【００１８】
請求項１に記載の発明によれば、装置が自らの行動を制御するためのプログラムの中に、現実的な問題の解決に不可欠なセンサの分解能等の実数値で規定される制御条件を取り込んだ状態の最適な解プログラムを見出すことができるようになる。
【００１９】
請求項２に記載の発明は、請求項１に記載の制御システムにおいて、前記初期個体生成手段は、１つの前記内部状態に対して１つの前記実数値で規定される制御条件が対応付けられ、かつ、１つの前記内部状態に対して前記ノードと前記パスとで構成される１つの木構造プログラムが関連付けられた状態の単数または複数の前記内部状態からプログラムを一定数生成するように構成されており、前記生成されたプログラムには、前記内部状態の数、前記内部状態に対応付けられた前記制御条件の内容、または前記内部状態に関連付けられた前記木構造プログラムの構造が互いに異なるプログラムが含まれることを特徴とする。
【００２０】
請求項２に記載の発明によれば、初期プログラムをＡＧＰＡ型のプログラムとするため、ＡＧＰＡの手法に準ずる進化過程により解プログラムを求めることができる。
【００２１】
請求項３に記載の発明は、請求項１に記載の制御システムにおいて、前記初期個体生成手段は、１つの前記内部状態に対して１つの前記実数値で規定される制御条件が対応付けられ、かつ、前記内部状態に関連付けられた不変数の非終端記号と終端記号とよりなるノードと前記ノードを連結させる前記内部状態に関連付けられたパスとで構成されるプログラムを一定数生成するように構成されており、前記生成されたプログラムには、前記内部状態に対応付けられた前記制御条件の内容、前記ノードを連結させる前記パスの数、または前記パスの連結の仕方が互いに異なるプログラムが含まれることを特徴とする。
【００２２】
請求項３に記載の発明によれば、初期プログラムをＧＡＵＧＥ型のプログラムとするため、ＧＡＵＧＥの手法に準ずる進化過程により解プログラムを求めることができる。
【００２３】
請求項４に記載の発明は、請求項１乃至請求項３のいずれか一項に記載の制御システムにおいて、前記非終端記号には、実数値を引数とする論理式が含まれるように構成されていることを特徴とする。
【００２４】
請求項４に記載の発明によれば、プログラム中の非終端記号に１、０しか引数としない論理式のみならず、実数値を引数とする論理式を含ませることにより、実際的なセンサの入力値のような実数値をそのままプログラムに取り込むことが可能となる。
【００２５】
請求項５に記載の発明は、請求項４に記載の制御システムにおいて、前記非終端記号である論理式に閾値として与えられる引数の値を、遺伝的アルゴリズムにより決定するように構成されていることを特徴とする。
【００２６】
請求項５に記載の発明によれば、進化過程にある各プログラムのそれぞれが、そのプログラムの論理構造においてとり得る最大値に近い適応度を持つように加工された状態で淘汰や増殖作用を受けることになる。
【００２７】
請求項６に記載の発明は、
装置を自律的に動作させるための制御方法であって、
前記装置の遷移可能な内部状態と実数値で規定される制御条件とを対応付け、前記内部状態に関連付けられた非終端記号と終端記号とよりなるノードと前記ノードを連結させるパスとで構成されるプログラムを一定数生成させる初期個体生成処理と、
前記各プログラムについて、それぞれプログラムの実行中の前記内部状態の遷移に伴って変化し得る前記制御条件の下でシミュレーションを行い、所定の評価式に基づいて前記各プログラムについてそれぞれ適応度を計算する適応度計算処理と、
前記適応度が所定の目標適応度に達したプログラムの有無を判断する判断処理と、
前記判断処理において前記目標適応度に達したプログラムがないと判断された場合に、前記適応度が最大のプログラムを隔離し、前記適応度が最大のプログラム以外の前記各プログラムまたは前記適応度が最大のプログラム以外の前記各プログラムと前記適応度が最大のプログラムのコピープログラムについて選択を行う親選択処理と、
前記親選択処理で選択された前記各プログラムについて、所定の規則に基づいて、それぞれプログラム中の前記内部状態の追加または削除を行う状態数増減処理と、
前記状態数増減処理で生成された各プログラムを一定の割合で交叉させる交叉処理と、
前記交叉処理で生成された各プログラムに一定の割合で突然変異を生じさせる突然変異処理と、
を行い、
前記突然変異処理で生成された各プログラムを前記適応度計算処理に移して前記各処理を繰り返して行い、
前記判断処理においては、前記各プログラムに、前記隔離された適応度が最大のプログラムを含めて判断し、
前記判断処理において前記目標適応度に達したプログラムがあると判断された場合には、そのプログラムを解として前記各処理を終了し、前記解であるプログラムを前記装置に出力することを特徴とする。
【００２８】
請求項６に記載の発明によれば、装置が自らの行動を制御するためのプログラムの中に、現実的な問題の解決に不可欠なセンサの分解能等の実数値で規定される制御条件を取り込んだ状態の最適な解プログラムを見出すことができるようになる。
【００２９】
請求項７に記載の発明は、請求項６に記載の制御方法において、前記初期個体生成処理では、１つの前記内部状態に対して１つの前記実数値で規定される制御条件が対応付けられ、かつ、１つの前記内部状態に対して前記ノードと前記パスとで構成される１つの木構造プログラムが関連付けられた状態の単数または複数の前記内部状態からプログラムを一定数生成し、前記生成されたプログラムには、前記内部状態の数、前記内部状態に対応付けられた前記制御条件の内容、または前記内部状態に関連付けられた前記木構造プログラムの構造が互いに異なるプログラムが含まれることを特徴とする。
【００３０】
請求項７に記載の発明によれば、初期プログラムをＡＧＰＡ型のプログラムとするため、ＡＧＰＡの手法に準ずる進化過程により解プログラムを求めることができる。
【００３１】
請求項８に記載の発明は、請求項６に記載の制御方法において、前記初期個体生成処理では、１つの前記内部状態に対して１つの前記実数値で規定される制御条件が対応付けられ、かつ、前記内部状態に関連付けられた不変数の非終端記号と終端記号とよりなるノードと前記ノードを連結させる前記内部状態に関連付けられたパスとで構成されるプログラムを一定数生成し、前記生成されたプログラムには、前記内部状態の数、前記内部状態に対応付けられた前記制御条件の内容、または前記ノードを連結させる前記パスの数または連結の仕方が互いに異なるプログラムが含まれることを特徴とする。
【００３２】
請求項８に記載の発明によれば、初期プログラムをＧＡＵＧＥ型のプログラムとするため、ＧＡＵＧＥの手法に準ずる進化過程により解プログラムを求めることができる。
【００３３】
請求項９に記載の発明は、請求項６乃至請求項８のいずれか一項に記載の制御方法において、前記非終端記号には、実数値を引数とする論理式が含まれることを特徴とする。
【００３４】
請求項９に記載の発明によれば、プログラム中の非終端記号に１、０しか引数としない論理式のみならず、実数値を引数とする論理式を含ませることにより、実際的なセンサの入力値のような実数値をそのままプログラムに取り込むことが可能となる。
【００３５】
請求項１０に記載の発明は、請求項９に記載の制御方法において、前記非終端記号である論理式に閾値として与えられる引数の値を、遺伝的アルゴリズムにより決定することを特徴とする。
【００３６】
請求項１０に記載の発明によれば、進化過程にある各プログラムのそれぞれが、そのプログラムの論理構造においてとり得る最大値に近い適応度を持つように加工された状態で淘汰や増殖作用を受けることになる。
【発明の効果】
【００３７】
請求項１に記載の発明によれば、制御システムを、初期個体生成手段により装置の内部状態と実数値条件とを対応付ける構造のプログラムを一定数生成させ、そのプログラムに対して適応度計算手段、判断手段、親選択手段、状態数増減手段、交叉手段、および突然変異手段を経て、適応度が目標適応度に達したプログラムを解プログラムとして出力するように構成したので、装置が自らの行動を制御するためのプログラムの中に、現実的な問題の解決に不可欠なセンサの分解能等の実数値で規定される制御条件を取り込んだ状態の最適な解プログラムを見出すことができるようになり、装置が自ら適切なタイミングでセンサの分解能等の実数値条件を的確に切り替えることができる解プログラムを求めることが可能となる。そのため、従来のＡＧＰＡやＧＡＵＧＥの手法を用いた場合と比較して、種々の問題に対して制御適応性を顕著に向上させることができる。
【００３８】
また、実数値条件を定義することによって実数値を扱う問題における解探索空間を狭めることができるため、解プログラムが見出されるまでの時間を短縮することができ、現実的な時間内に最適化された制御プログラムを自律的に求めることが可能となる。さらに、装置が単独である場合に限らず、複数の装置が領域の中で最適な行動をとるための制御プログラムをそれぞれの装置について同時に求めることもでき、また、複雑に変化する環境下での単独または複数のロボット等の自律移動可能な装置の行動を制御することも可能となる。
【００３９】
請求項２に記載の発明によれば、初期個体生成手段で生成されるプログラムを、内部状態に実数値条件が対応付けられ、木構造プログラムが関連付けられた状態のＡＧＰＡ型のプログラムとして構成するようにしたので、ＡＧＰＡの手法に準ずる進化過程により解プログラムを求めることができる。そのため、前記請求項１に記載の発明の効果に加えて、設計者が試行錯誤により装置の内部状態の状態数を決める必要がなく、かつ、進化過程の中で状態数を適宜増減させることによりプログラム中の状態数が膨大になることを防止できるというＡＧＰＡの特性を有効に活用できるという効果が得られる。
【００４０】
請求項３に記載の発明によれば、初期個体生成手段で生成されるプログラムを、装置の内部状態に対して１つの実数値条件が対応付けられ、かつ、内部状態に関連付けられた不変数の非終端記号と終端記号とよりなるノードとノードを連結させる内部状態に関連付けられたパスとで構成されるＧＡＵＧＥ型のプログラムとして構成するようにしたので、ＧＡＵＧＥの手法に準ずる進化過程により解プログラムを求めることができる。そのため、前記請求項１に記載の発明の効果に加えて、非終端記号を固定することにより、遺伝的プログラミングにおける木構造の肥大化による探索効率の低下を防止することができるというＧＡＵＧＥの特性を有効に活用できるという効果が得られる。
【００４１】
請求項４に記載の発明によれば、プログラム中の非終端記号には、実数値を引数とする論理式が含まれるようにしたので、実際的なセンサの入力値のような実数値をそのままプログラムに取り込むことが可能となる。そのため、前記各請求項に記載の発明の効果に加えて、装置は実数値で規定される環境からの入力により的確に対応することが可能となり、現実的な問題に対してより顕著に制御適応性を向上させることができるという効果が得られる。
【００４２】
請求項５に記載の発明によれば、非終端記号である論理式に閾値として与えられる引数の値を遺伝的アルゴリズムにより決定するようにしたので、進化過程にある各プログラムのそれぞれが、そのプログラムの論理構造においてとり得る最大値に近い適応度を持つように加工された状態で淘汰や増殖作用を受けることになる。そのため、前記各請求項に記載の発明の効果に加えて、より的確に環境に対応し得るプログラムが得られる確率が高くなると同時に、設計者が閾値を１つ１つ定める必要がなくなるという効果が得られる。
【００４３】
請求項６に記載の発明によれば、制御方法を、初期個体生成処理により装置の内部状態と実数値条件とを対応付ける構造のプログラムを一定数生成させ、そのプログラムに対して適応度計算処理、判断処理、親選択処理、状態数増減処理、交叉処理、および突然変異処理を行い、適応度が目標適応度に達したプログラムを解プログラムとして出力するように構成したので、装置が自らの行動を制御するためのプログラムの中に、現実的な問題の解決に不可欠なセンサの分解能等の実数値で規定される制御条件を取り込んだ状態の最適な解プログラムを見出すことができるようになり、装置が自ら適切なタイミングでセンサの分解能等の実数値条件を的確に切り替えることができる解プログラムを求めることが可能となる。そのため、従来のＡＧＰＡやＧＡＵＧＥの手法を用いた場合と比較して、種々の問題に対して制御適応性を顕著に向上させることができる。
【００４４】
また、実数値条件を定義することによって実数値を扱う問題における解探索空間を狭めることができるため、解プログラムが見出されるまでの時間を短縮することができ、現実的な時間内に最適化された制御プログラムを自律的に求めることが可能となる。さらに、装置が単独である場合に限らず、複数の装置が領域の中で最適な行動をとるための制御プログラムをそれぞれの装置について同時に求めることもでき、また、複雑に変化する環境下での単独または複数のロボット等の自律移動可能な装置の行動を制御することも可能となる。
【００４５】
請求項７に記載の発明によれば、初期個体生成処理工程で生成されるプログラムを、内部状態に実数値条件が対応付けられ、木構造プログラムが関連付けられた状態のＡＧＰＡ型のプログラムとして構成するようにしたので、ＡＧＰＡの手法に準ずる進化過程により解プログラムを求めることができる。そのため、前記請求項６に記載の発明の効果に加えて、設計者が試行錯誤により装置の内部状態の状態数を決める必要がなく、かつ、進化過程の中で状態数を適宜増減させることによりプログラム中の状態数が膨大になることを防止できるというＡＧＰＡの特性を有効に活用できるという効果が得られる。
【００４６】
請求項８に記載の発明によれば、初期個体生成処理工程で生成されるプログラムを、装置の内部状態に対して１つの実数値条件が対応付けられ、かつ、内部状態に関連付けられた不変数の非終端記号と終端記号とよりなるノードとノードを連結させる内部状態に関連付けられたパスとで構成されるＧＡＵＧＥ型のプログラムとして構成するようにしたので、ＧＡＵＧＥの手法に準ずる進化過程により解プログラムを求めることができる。そのため、前記請求項６に記載の発明の効果に加えて、非終端記号を固定することにより、遺伝的プログラミングにおける木構造の肥大化による探索効率の低下を防止することができるというＧＡＵＧＥの特性を有効に活用できるという効果が得られる。
【００４７】
請求項９に記載の発明によれば、プログラム中の非終端記号には、実数値を引数とする論理式が含まれるようにしたので、実際的なセンサの入力値のような実数値をそのままプログラムに取り込むことが可能となる。そのため、前記各請求項に記載の発明の効果に加えて、装置は実数値で規定される環境からの入力により的確に対応することが可能となり、現実的な問題に対してより顕著に制御適応性を向上させることができるという効果が得られる。
【００４８】
請求項１０に記載の発明によれば、非終端記号である論理式に閾値として与えられる引数の値を遺伝的アルゴリズムにより決定するようにしたので、進化過程にある各プログラムのそれぞれが、そのプログラムの論理構造においてとり得る最大値に近い適応度を持つように加工された状態で淘汰や増殖作用を受けることになる。そのため、前記各請求項に記載の発明の効果に加えて、より的確に環境に対応し得るプログラムが得られる確率が高くなると同時に、設計者が閾値を１つ１つ定める必要がなくなるという効果が得られる。
【発明を実施するための最良の形態】
【００４９】
以下、本発明の制御システムおよび制御方法に係る実施の形態について、図面を参照して説明する。
【００５０】
図１は、本実施形態に係る制御システムを示すブロック図であり、制御システム１としては、ＣＰＵやＲＡＭ、ＲＯＭ、入出力インターフェース等がＢＵＳにより接続されて構成されたコンピュータを用いることができる。制御システム１は、初期個体生成手段２と、適応度計算手段３と、判断手段４と、親選択手段５と、状態数増減手段６と、交叉手段７と、突然変異手段８とを備えている。
【００５１】
初期個体生成手段２は、図示しない装置本体の制御部からのプログラム生成指示に応じて、状態番号が付された内部状態と、センサの分解能のような実数値で規定される制御条件（すなわち実数値条件）とを対応付け、図２に例示するような非終端記号と終端記号とよりなるノードとノードを連結させるパスとで構成される木構造プログラム（以下、制御木という。）を前記各内部状態にそれぞれ関連付けて構成されるプログラムを一定数生成させるように構成されている。
【００５２】
本実施形態では、初期個体生成手段２は、図３に示すように、状態番号が０およびデフォルトの内部状態に対してそれぞれ０、デフォルトの番号を付した任意の実数値条件を対応付け、任意に発生させた２つの制御木にそれぞれ０、デフォルトの番号を付して状態番号０、デフォルトの内部状態にそれぞれ関連付けて１つのＡＧＰＡ型のプログラムを生成し、このようなプログラムをランダムに一定数生成するように構成されている。
【００５３】
このように、プログラムをランダムに生成させることにより、プログラムの中に、状態番号に対応する実数値条件が互いに異なるものや、制御木におけるノードの種類やパスの張り方等が互いに異なるものを含ませることが可能となる。また、本実施形態では、図３に示したように、状態番号が０またはデフォルトの２つの内部状態からなるプログラムを生成させるが、生成されたプログラムの中に内部状態の数が互いに異なるプログラム（図４参照）が含まれるように構成することも可能である。
【００５４】
初期個体生成手段２には、適応度計算手段３が接続されており、初期個体生成手段２で生成された各プログラムが適応度計算手段３に送られるようになっている。適応度計算手段３には、装置本体の制御部から、例えば、装置が行動可能なエリアの形状、障害物の位置や大きさ、形状、ゴールの位置や範囲、前記エリアにおける装置の現在位置（すなわちスタート位置）等の情報が入力されるように構成されており、適応度計算手段３は、そのような条件下で各プログラムについてそれぞれシミュレーションを行い、所定の評価式に基づいて各プログラムについてそれぞれ適応度を計算するように構成されている。
【００５５】
適応度計算手段３におけるシミュレーションについてより詳しく説明すると、例えば、図２に示したように、プログラム中の制御木を構成する終端記号には、装置の動作を規定する終端記号（ＭＦ［ｓｅｔ＊］等）と次に遷移すべき状態番号を規定する終端記号（Ｉｎｃ等）とがあり、各制御木からは一定の動作と次に遷移すべき状態番号が出力されるようになっている。また、本実施形態では、図２に例示したように、終端記号としてセンサからの入力値を０〜１０２４までの実数値として扱うことができるようになっており、非終端記号の論理式には、そのような実数値を引数とするものが含まれるように構成されている。
【００５６】
そして、シミュレーションにおいては、初期状態である状態番号０の内部状態にある装置は、その状態に対応する実数値条件（例えば、センサの分解能）の下で周囲の環境から得た情報を入力し、その実数値である入力値を制御木０に基づいて演算処理して一定の動作と次に遷移すべき状態番号を得る。そして、装置は、その一定の行動をした後、状態遷移した後の状態に対応する実数値条件の下で再度環境からの情報を入力し、その入力値を状態遷移した後の状態に関連付けられた制御木に基づいて演算処理して更に次の行動と次に遷移すべき状態番号を得るという作業を繰り返すようになっている。その際、状態遷移した後の状態番号が付された内部状態がない場合には、状態番号がデフォルトの内部状態が参照され、番号がデフォルトの実数値条件下で番号がデフォルトの制御木に基づいて演算処理がなされるようになっている。
【００５７】
適応度計算手段３は、このようなシミュレーションを各プログラムごとに行うが、プログラム自体が実行不能なものであったり、装置に前進後退を繰り返させるようなものである場合もあるので、装置がゴールに到達する等の所定の目的を一定時間内に達成しない場合には、その一定時間が経過した時点でシミュレーションを打ち切るように構成されている。
【００５８】
また、適応度計算手段３は、プログラムに則って装置がとった行動のシミュレーション結果に対して、各プログラムごとに、最短距離でゴールに到達する等の装置に課せられた課題に応じて与えられる前記評価式に基づいて適応度を計算するように構成されている。評価式は、例えば、課題が最短距離でゴールに到達するというものであれば、シミュレーションにおいて装置の各動作で移動した距離の総和に関連付けられてもよいし、装置内のクロックのパルス数に基づいて適応度を計算するようにされてもよい。
【００５９】
適応度計算手段３には、判断手段４が接続されている。判断手段４は、適応度が計算された各プログラムの中に、適応度が所定の目標適応度Ｑに達したプログラムがあるかどうかを判断し、目標適応度Ｑに達したプログラムがあれば、そのプログラムを解プログラムとして装置本体の制御部に出力し、制御システム１の各手段による処理を終了させるように構成されている。適応度計算手段３は、所定の目標適応度Ｑに達したプログラムがないと判断すると、次の親選択手段５に各プログラムを送るようになっている。なお、目標適応度Ｑは、課題に応じて設計者により装置に所与の値としてあらかじめ入力される。
【００６０】
判断手段４には、親選択手段５が接続されている。親選択手段５は、各プログラムの中から適応度が最大のプログラムのみをＲＡＭ９に格納して隔離（エリート保存）すると同時に、適応度が最大のプログラムのコピープログラムを生成し、そのコピープログラムと前記適応度が最大のプログラム以外の各プログラムについてルーレット選択や期待値選択、ランキング選択、トーナメント選択等の方法で次世代に残すべきプログラムの選択およびそれらのプログラムの増殖を行うように構成されている。本実施形態では、親選択手段５は、エリート保存とトーナメント選択とを組み合わせて処理するように構成されている。なお、適応度が最大のプログラムのコピーを行わず、適応度が最大のプログラム以外の各プログラムのみで選択を行うように構成することも可能である。
【００６１】
親選択手段５には、状態数増減手段６が接続されており、親選択手段５で選択された次世代の各プログラムが状態数増減手段６に送られるようになっている。状態数増減手段６は、各プログラムについて、所定の規則に基づいて、それぞれプログラム中の内部状態の追加または削除を行うように構成されている。
【００６２】
本実施形態では、状態数増減手段６は、前記適応度計算手段３におけるあるプログラムのシミュレーションにおいて、状態遷移した後の状態番号が付された内部状態がなく（例えば、図５（Ａ）に示すプログラムで図６に示すように状態番号１、２、３の内部状態が使用されたがそれらの状態番号が付された内部状態がなく）、状態番号がデフォルトの内部状態が参照された場合には、必要とされた状態番号（前記例では状態番号１、２、３）の中からランダムに１つの状態番号が選択され、その選択された状態番号が付された内部状態にランダムに選択された実数値条件を対応付け、番号がデフォルトの制御木をコピーしてその選択された状態番号が付された内部状態に関連付けて、そのプログラムに追加してプログラムの状態数を増加させるように構成されている［図５（Ｂ）参照］。その際、追加される制御木は、すでに状態番号が付された内部状態に関連付けられている制御木をコピーしたものとしてもよく、デフォルトの制御木やすでに状態番号が付された内部状態に関連付けられている制御木の終端記号を変えたものとしてもよい。
【００６３】
また、状態数増減手段６は、適応度計算手段３におけるあるプログラムのシミュレーションにおいて、１度も使われなかった内部状態がある場合には（例えば、図７（Ａ）に示すプログラムで図８に示すように状態番号１、４の内部状態が使われなかった場合には）、使われなかった内部状態の状態番号（前記例では状態番号１、４）の中からランダムに１つの状態番号が選択され、その選択された状態番号が付された内部状態と、その内部状態に対応付けられ関連付けられた実数値条件と制御木とがそのプログラム中から削除され、プログラムの状態数を減少させるように構成されている［図７（Ｂ）参照］。
【００６４】
状態数増減手段６は、以上のような状態数の増加および減少をすべてのプログラムについて行うようになっている。
【００６５】
状態数増減手段６には、交叉手段７が接続されており、状態数増減手段６で処理された各プログラムが交叉手段７に送られるようになっている。交叉手段７は、各プログラムを図９に示すような遺伝子型にしたうえでプログラムを２個体ずつ対にして、それぞれの個体対ごとにランダムに選ばれた遺伝子上の交叉点で一定の割合（例えば、７０％の割合）で互いに交叉させるように構成されている。その際、交叉の結果、状態番号（内部状態）の後に状態番号が連結されたり、１つの状態番号に対する実数値条件が２つになったり、非終端記号であるノードの後に状態番号が連結されたりすると、そのプログラムは実行不能となるので、交叉後のプログラムが実行可能なものとなるように、交叉を行わせる遺伝子上の交叉点などには制限が加えられる。また、本実施形態では、交叉は１点交叉の方法で行われるが、この他にも多点交叉や一様交叉等の方法で交叉させるように構成することも可能である。
【００６６】
交叉手段７には、突然変異手段８が接続されており、交叉手段７で処理された各プログラムが突然変異手段８に送られるようになっている。突然変異手段８は、各プログラムごとに、プログラムを構成する制御木のノードに対して一定の割合（例えば、１％の割合）で突然変異を生じさせるように構成されている。その際、交叉手段７における場合と同様に、プログラムが実行可能なものとなるようにされており、例えば、終端記号を非終端記号に突然変異させる等の突然変異は禁止される。本実施形態では、状態番号や実数値条件については突然変異を生じさせないようにしているが、それらについても突然変異させるように構成することも可能である。
【００６７】
突然変異手段８には、前記適応度計算手段３が接続されており、突然変異手段８で処理された各プログラムは、適応度計算手段３に送られて再びシミュレーションが行われ、適応度が計算されるようになっている。
【００６８】
また、適応度計算手段３において適応度が計算された各プログラムは、前記判断手段４に送られるが、その際、前記親選択手段５によりＲＡＭ９に格納されて隔離されていた１世代前の前記適応度が最大のプログラムが読み出されて判断手段４に送られて、次世代の前記各プログラムとともに目標適応度Ｑに達したかどうかを判断されるようになっている。
【００６９】
次に、前述した制御システムを用いた本発明に係る制御方法の実施形態について説明する。本実施形態の制御方法は、図１０に示すようなフローチャートとして表すことができる。制御方法における各処理についての詳細は前記制御システム１の対応する各手段で説明したとおりであるが、ここで図１０に基づいて簡単に処理の手順について述べる。
【００７０】
まず、装置本体からプログラム生成指示があると、初期個体生成処理（ステップＳ１）で、装置の内部状態と実数値条件とを対応付け、内部状態に制御木を関連付けたプログラムを一定数生成し、各プログラムについて、内部状態の遷移に伴って実数値条件が変化するという制御条件の下でシミュレーションを行い、所定の評価式に基づいて各プログラムについてそれぞれ適応度を計算する（ステップＳ２）。適応度が所定の目標適応度Ｑに達したプログラムがあるかどうかを判断し（ステップＳ３）、目標適応度Ｑに達したプログラムがあれば処理を終了し、解プログラムを装置に出力する。
【００７１】
目標適応度Ｑに達したプログラムがないと判断された場合には、適応度が最大のプログラムを隔離し、前記適応度が最大のプログラム以外の各プログラムと前記適応度が最大のプログラムのコピープログラムについて親選択を行い（ステップＳ４）、選択された各プログラムについてそれぞれプログラム中の前記内部状態の追加または削除を行う（ステップＳ５）。そして、各プログラムについて交叉を行い（ステップＳ６）、突然変異を生じさせて（ステップＳ７）、再び適応度計算処理（ステップＳ２）に移される。
【００７２】
このようにして、目標適応度Ｑに達したプログラムが現れるまで、この処理のサイクルを繰り返し行う。なお、親選択処理（ステップＳ４）において隔離した適応度が最大であった親世代のプログラムは、次世代の各プログラムを判断処理する際（ステップＳ３）に、その次世代の各プログラムとともに判断処理を行う。
【００７３】
また、本実施形態の制御方法および制御システムにおいて、非終端記号である論理式（図２参照）に閾値として与えられる引数（例えば、同図のＩＦＬＴＥ（Ａ、Ｂ、Ｃ、Ｄ）のＡやＢなど）の値を、遺伝的アルゴリズムにより決定するように構成することも可能である。具体的には、前記親選択処理（ステップＳ４）において適応度が最大のプログラムを隔離した後、親選択が行われる前に、１つのプログラムについて、プログラム中の閾値の値をランダムに変えた一定数の初期プログラムを生成させて、そのすべてについて前記シミュレーションを行い、親選択や交叉、突然変異等を生じさせてプログラムの適応度がより高くなるようにプログラム中の閾値を決める。その作業をすべてのプログラムについて行い、各プログラムの新たな適応度に基づいて親選択を行う。このようにすることで、より適応度が高くより的確なプログラムが得られこととなり、好ましい。
【００７４】
一方、前述した本発明の制御システムおよび制御方法における初期個体生成で、図３に示したような状態番号、実数値条件および制御木の組で構成されるＡＧＰＡ型のプログラムではなく、図１１に示すように、１つの内部状態（正確には後述する非終端記号Ｒｏｏｔ［ＳＲ］の状態番号ＳＲ）に対して１つの実数値条件が対応付けられ、内部状態に関連付けられた数が増減しないノードとノードを連結させるパスとで構成されるＧＡＵＧＥ型のプログラムを一定数生成するように構成してもよい。
【００７５】
図１１に例示したプログラムでは、非終端記号のノードは楕円状に示され、終端記号のノードは矩形状に示されている。非終端記号には状態番号ＳＲが設定されており、非終端記号の状態番号ＳＲの違いによりたどるパスが変わるようになっている。また、各パスは状態番号を操作する関数（図１２参照）を持つことができ、関数を持つパスをたどるときは、パスをたどった時点でその関数を実行し、関数により指定された非終端記号の状態番号を変更する。
【００７６】
図１１に示されたプログラムを例にとって説明すれば、まず、非終端記号の状態番号ＳＲはすべて０であるとする。その場合、演算は、非終端記号Ｒｏｏｔ［ＳＲ］からスタートし、Ｒｏｏｔ［ＳＲ］の状態番号ＳＲは０であるから０のラベルを持つパスを非終端記号Ａ［ＳＲ］にたどる。そして、非終端記号Ａ［ＳＲ］の論理演算の結果がｎ（Ｎｏ）であれば、終端記号Ｙに向かうパス０−ｎをたどり、このプログラムからは一定の行動Ｙが出力される。装置は行動Ｙを実行し（またはそのような行動をとるシミュレーションをし）、状態番号０に対応付けられた実数値条件０の下で周囲の環境から得た情報を入力し、再び非終端記号Ｒｏｏｔ［ＳＲ］からスタートするという演算を繰り返す。
【００７７】
もし先の非終端記号Ａ［ＳＲ］における論理演算の結果がｙ（Ｙｅｓ）であれば、０−ｙのラベルが付されたパスをたどるが、このパス０−ｙは関数（Ｒｏｏｔ， Ｓｅｔ１）を持つので、非終端記号Ｒｏｏｔ［ＳＲ］の状態番号ＳＲが１に設定される。そして非終端記号Ｂ［ＳＲ］の論理演算の結果がｙであれば、パス０−ｙをたどり行動Ｘを出力する。非終端記号Ｒｏｏｔ［ＳＲ］の状態番号は１になっているから、この場合、装置は、行動Ｘを実行し、非終端記号Ｒｏｏｔ［ＳＲ］の状態番号１に対応付けられた実数値条件１の下で周囲の環境から得た情報を入力し、今度は非終端記号Ｒｏｏｔ［ＳＲ］からスタートして１のラベルを持つパスをたどるという操作を繰り返す。
【００７８】
本実施形態では、初期個体生成において、初期状態が０のプログラム、すなわち、各非終端記号の状態番号が０とされ、Ｒｏｏｔ［ＳＲ］の状態番号に任意の実数値条件０が対応付けられ、各非終端記号には状態番号０のパスだけが設定されたプログラムがランダムに一定数生成される。そのため、一定数のプログラムの中には、パスの数やパスの連結の仕方、内部状態（Ｒｏｏｔ［ＳＲ］の状態番号０）に対応付けられた実数値条件０の内容が互いに異なるプログラムが含まれる。なお、図１１に例示されたプログラムでは、終端記号がＸとＹの２個しか記載されていないが、例えば、図２に例示したような終端記号を用いてプログラムが生成される場合には、終端記号は、図２中の装置の動作を規定する終端記号であるＭＦ［ｓｅｔ＊］、ＭＢ［ｓｅｔ＊］、ＴＲ［ｓｅｔ＊］、ＴＬ［ｓｅｔ＊］の４個となる。
【００７９】
このようにして生成された各プログラムは、図１に示した制御システム１で図１０に示した制御方法のフローチャートに従って適応度が計算される。
【００８０】
適応度計算におけるシミュレーションでは、プログラム中に、非終端記号の状態番号ＳＲをラベルに持つパスがまだ設定されていない場合がある。その場合は、その状態番号以下で最大の状態番号をラベルに持つパスをたどるようにする。また、一定回数パスをたどっても終端記号にたどり着かない場合は、終端記号の中からランダムに選択する。
【００８１】
また、適応度計算のシミュレーションにおいて、プログラム中の非終端記号Ｒｏｏｔ[ＳＲ]の状態番号ＳＲが未設定の状態になる場合がある。その場合には、状態数増減処理において、状態数を増加させる。具体的には、プログラムのシミュレーション中にＲｏｏｔ[ＳＲ]がとった最大の状態番号までの範囲で未設定の状態番号の中から１つの状態番号ＳＲがランダムに選択され、その状態番号ＳＲをラベルに持つパスがＲｏｏｔ[ＳＲ]に追加される。それと同時に、Ｒｏｏｔ[ＳＲ]の状態番号ＳＲにランダムに選択された実数値条件ＳＲが対応付けられる。また、状態数増減処理では、適応度計算のシミュレーションで使われなかったＲｏｏｔ[ＳＲ]の状態番号がある場合には、使われなかった状態番号の中から１つがランダムに選択され、非終端記号Ｒｏｏｔ[ＳＲ]から出るその状態番号ＳＲをラベルに持つパスが削除され、状態数を減少させる。それと同時に、Ｒｏｏｔ[ＳＲ]の選択された状態番号ＳＲに対応付けられた実数値条件ＳＲも削除される。
【００８２】
交叉においては、各プログラムの非終端記号を図１３に示すような遺伝子型に並べたうえでプログラムを２個体ずつ対にして、それぞれの個体対ごとにランダムに選ばれた遺伝子上の交叉点で一定の割合で互いに１点交叉させる。その際、交叉点以下の非終端記号から出るパスごと交叉される。例えば、図１４（Ａ）に示す２個体のプログラムの対において、図１３の遺伝子構造のＡとＢの間が交叉点として選択された場合には、図１４（Ａ）の太線で示されたパスが非終端記号Ｂ[ＳＲ]とともに他の個体と交換される[図１４（Ｂ）参照]。
【００８３】
以上のようにして図１０に示したフローチャートに従って適応度計算、判断、親選択、状態数の増減、交叉、突然変異が繰り返され、最適化されたプログラムが見出され、解プログラムとして装置に出力される。
【００８４】
次に、障害物がある領域で、装置Ｘがスタート位置Ｓから出発し、ゴールエリアＧに最短距離で到達するプログラムを探索するという問題を例にとって、本実施形態の制御システムおよび制御方法の作用について説明する。
【００８５】
装置Ｘは、図１５に模式的に示すように、直径６０ｍｍの円筒状の装置本体１０の両側面に図示しない駆動モータにより独立に回転駆動される２つの車輪１１、１１が取り付けられて構成されている。装置Ｘの進行方法前方側には、３０ｍｍ以内の障害物との距離を１／１〜１／１０２４の範囲の分解能で検知可能な赤外線センサ１２が６個配設されており、６個の赤外線センサ１２は、それぞれの検知エリア１３に存在する障害物を検知するようになっている。また、装置Ｘの進行方向後方側には、同様の赤外線センサ１２が２個配設されており、２個の赤外線センサ１２が装置後方の障害物を検知するようにされている。装置Ｘには、図示しない制御部と図１に示した制御システム１が組み込まれており、制御部は制御システム１から解プログラムの出力があると、その解プログラムに従って駆動モータを駆動させ、車輪１１、１１を回転させて装置Ｘを移動させるように構成されている。
【００８６】
探索領域は、図１６に示すように、南北方向９００ｍｍ、東西方向９００ｍｍの正方形状の領域であり、領域の中央には障壁Ｙが設けられている。障壁Ｙには、１辺１２０ｍｍの正方形をジグザグに組み合わせたような開孔Ｚが穿孔されている。スタート地点Ｓは、探索領域の南西側縁端であり、装置Ｘは、スタート地点Ｓと装置の円筒の中心が一致するように東方向を向くように置かれる。ゴールエリアＧは、探索領域の北東側縁端の１辺１２０ｍｍの正方形のエリアであり、装置全体がゴールエリア内に入るとゴールとなる。
【００８７】
制御システム１は、制御部からプログラム生成の指示を受けると、図１０のフローチャートに従って解プログラムを見出すべく作動する。初期個体生成手段２で図２に示された非終端記号および終端記号から図３に示されたＡＧＰＡ型のプログラムを１００個体ランダムに生成させる。その際、実数値条件としてのセンサの分解能は１／２、１／２2、…、１／２10の１０通りの分解能の中からランダムに選択される。
【００８８】
適応度計算手段３には、前記探索領域の情報が制御部から入力され、その条件下で各プログラムについてシミュレーションを行う。この場合、装置Ｘが障壁Ｙや開孔Ｚの内面に当たると、装置Ｘはその時点で行動を停止し、そのプログラムのシミュレーションは終了される。また、シミュレーションにおけるプログラムのステップ数Ｃと装置Ｘとゴールとの距離Ｌとの和Ｃ＋Ｌを評価式として、各プログラムについてそれぞれ適応度を計算する。この場合、シミュレーションにおいて装置ＸがゴールエリアＧに到達すればＬは０であり、ステップ数も小さい方がより適応していると言えるため、Ｃ＋Ｌがより小さい方が適応度が高いと判断される。
【００８９】
そのため、判断手段４は、各プログラムの中にＣ＋Ｌ≦１００を満たすプログラムがあれば、そのプログラムを解プログラムとして制御部に出力し、制御システム１の各手段による処理を終了させる。そして、装置Ｘはその解プログラムに従って行動し、ゴールエリアＧに到達する。各プログラムの中にＣ＋Ｌ≦１００を満たすプログラムがなければ、判断手段４は、各プログラムを親選択手段５に送る。
【００９０】
親選択手段５では、適応度が最大のプログラムはＲＡＭ９に格納され隔離される。そして、同時に、適応度が最大のプログラムのコピープログラムを生成し、そのコピープログラムとそれ以外の各プログラムについて、トーナメント選択を行いプログラムの選択を行う。トーナメント選択では、１００個体のプログラムの中から１０個体をランダムに選択し、その中で最も適応度の高いプログラムを残す。これを１００回繰り返し、次世代に残す１００個体のプログラムを選択する。この処理により、適応度が高いプログラムが高い確率で次世代に残され、その個体数も増える（増殖）。また、適応度が低いプログラムは高い確率でプログラム中から除かれる（淘汰）。
【００９１】
状態数増減手段６では、このようにして選択された各プログラムについて、前述したような規則に基づいて、それぞれプログラム中の内部状態の追加または削除が行われる。この場合は、追加される制御木は、デフォルトの制御木がコピーされる。交叉手段７では、プログラムの個体対ごとにランダムに選ばれた交叉点で１００％の確率で１点交叉が行われる。突然変異手段８では、各プログラムごとに、プログラムを構成する制御木のノードに対して１％の割合で突然変異を生じさせる。
【００９２】
以上のように処理された次世代の１００個体のプログラムが前記適応度計算手段３に送られ、再びシミュレーションが行われて適応度が計算される。なお、判断手段４では、前世代で適応度が最大であったプログラムがＲＡＭ９から読み出され、次世代の１００個体のプログラムとともに適応度が目標適応度Ｑに達したプログラムがあるかどうかを判断される。以上の処理が、目標適応度Ｑに達したプログラムが現れるまで繰り返し行われる。
【００９３】
このような処理で得られた解プログラムに従って装置Ｘがスタート地点ＳからゴールエリアＧに至るまでの軌跡を図１７に示す。また、この処理で得られた解プログラムを図１８に示す。図１８の解プログラムは、図３のようなＡＧＰＡ型のプログラムを１本の制御木にまとめた形で表現されており、装置の動作を規定する終端記号であるＭＦ［ｓｅｔ＊］等のｓｅｔ＊の部分で、次に遷移すべき内部状態が状態番号＊の内部状態であることが示されている。
【００９４】
この解プログラムには、各内部状態（この場合は状態番号が０から３までの４つの内部状態）に対応する実数値条件は示されていないが、結果として、状態番号が０と１の内部状態ではセンサの分解能は１／１２８、状態番号が２と３の内部状態では分解能は１／１０２４となっている。図１７に示した探索領域の領域Ｒ１および領域Ｒ３ではセンサの分解能が比較的粗い条件（分解能１／１２８）に基づいて行動し、障壁Ｙの開孔Ｚ付近では分解能が細かい条件下（分解能１／１０２４）で行動することによりゴールエリアＧに到達することができるという結果が得られた。なお、この解プログラムが得られるまでの世代交代は約５０００世代であり、解プログラムが得られるまでにかかった時間は約３時間であった。
【００９５】
図１６に示した領域に対する探索問題は、図１１に示したようなＧＡＵＧＥ型のプログラムを用いても同様にして解プログラムが得られる。
【００９６】
以上のように、本発明の制御システムおよび制御方法によれば、装置の内部状態に実数値条件を対応付けてＡＧＰＡやＧＡＵＧＥに準ずる手法で解プログラムを求めることにより、装置が自ら適切なタイミングでセンサの分解能等の実数値条件を的確に切り替えることができる解プログラムを見出していくことが可能となる。そのため、従来のＡＧＰＡやＧＡＵＧＥの手法を用いた場合と比較して、種々の問題に対して制御適応性を顕著に向上させることができる。
【００９７】
また、実数値条件を定義することによって実数値を扱う問題における解探索空間を狭めることができるため、解プログラムが見出されるまでの時間を短縮することができ、現実的な時間内に最適化された制御プログラムを自律的に求めることが可能となる。
【００９８】
さらに、本発明の制御システムおよび制御方法によれば、複数のロボット等の装置が、ある領域の中で最適な行動をとるための制御プログラムをそれぞれの装置について同時に求めることもでき、また、複雑に変化する環境下での単独または複数のロボット等の自律移動可能な装置の行動を制御することも可能となる。例えば、エンジンの回転数や車速を自動車が自律的にコントロールする場合など、装置自らが実数値で規定される制御条件を的確に変更するような最適化された制御プログラムを、現実的な時間内に自律的に求めることが可能となる。
【図面の簡単な説明】
【００９９】
【図１】本実施形態に係る制御システムを示すブロック図である。
【図２】制御木のノードに用いられる非終端記号と終端記号の例である。
【図３】ＡＧＰＡ型のプログラムの例である。
【図４】図２に示すプログラムとは内部状態の数が異なるプログラムの例である。
【図５】状態数の増加を説明する図であり、（Ａ）は状態数が増加する前のプログラム、（Ｂ）は増加した後のプログラムを示す。
【図６】シミュレーション中に使用された状態番号と使用回数の例を示す図である。
【図７】状態数の減少を説明する図であり、（Ａ）は状態数が減少する前のプログラム、（Ｂ）は減少した後のプログラムを示す。
【図８】シミュレーション中に使用された状態番号と使用回数の例を示す図である。
【図９】遺伝子型にしたプログラムを示す図である。
【図１０】本発明の制御方法を示すフローチャートである。
【図１１】ＧＡＵＧＥ型のプログラムの例である。
【図１２】ＧＡＵＧＥ型のプログラムのパスが持つことができる関数の例である。
【図１３】遺伝子型にしたプログラムを示す図である。
【図１４】ＧＡＵＧＥ型のプログラムの交叉を説明する図であり、（Ａ）は交叉する前の２個体のプログラム、（Ｂ）は交叉した後の２個体のプログラムを示す。
【図１５】装置の模式図である。
【図１６】図１５の装置を用いた探索問題の探索領域を示す図である。
【図１７】図１６の探索領域において解プログラムに従って行動した装置の軌跡を示す図である。
【図１８】図１６の探索問題について得られた解プログラムである。
【図１９】遺伝的プログラミングで用いられる木構造プログラムを説明する図である。
【図２０】迷路を説明する図である。
【図２１】従来のＧＰ−オートマトンで用いられるプログラムを説明する図である。
【図２２】障害物がある探索領域を説明する図である。
【符号の説明】
【０１００】
１    制御システム
２    初期個体生成手段
３    適応度計算手段
４    判断手段
５    親選択手段
６    状態数増減手段
７    交叉手段
８    突然変異手段
Ｑ    目標適応度
【図１】
2005228141.tif 000003
【図２】
2005228141.tif 000004
【図３】
2005228141.tif 000005
【図４】
2005228141.tif 000006
【図５】
2005228141.tif 000007
【図６】
2005228141.tif 000008
【図７】
2005228141.tif 000009
【図８】
2005228141.tif 000010
【図９】
2005228141.tif 000011
【図１０】
2005228141.tif 000012
【図１１】
2005228141.tif 000013
【図１２】
2005228141.tif 000014
【図１３】
2005228141.tif 000015
【図１４】
2005228141.tif 000016
【図１５】
2005228141.tif 000017
【図１６】
2005228141.tif 000018
【図１７】
2005228141.tif 000019
【図１８】
2005228141.tif 000020
【図１９】
2005228141.tif 000021
【図２０】
2005228141.tif 000022
【図２１】
2005228141.tif 000023
【図２２】
2005228141.tif 000024