(57)【特許請求の範囲】
【請求項１】
複数のアクチュエータを備えた設備によって意図した結果を実現するアクチュエータの動作順を探索し、探索された複数の動作順の中から準最短動作順を探索する方法であり、
（１）ハミング距離と状態コストと遷移コストを評価関数としてＲＴＡ＊探索方法を実行して結果を実現する一つの動作順を探索する工程、
（２）ハミング距離と状態コストと遷移コストを評価関数としてＲＴＡ＊探索方法を実行して結果を実現するもう一つの動作順を探索する工程、
（３）探索された二つの動作順を比較し、少ない動作数で結果を実現する準最短動作順の候補を選択する工程、
（４）選択された準最短動作順の候補と選択されなかった動作順を比較して、準最短動作順の候補の中に存在する前後関係の制約がない複数の動作を特定する工程、
（５）ハミング距離と状態コストと遷移コストを評価関数としてＲＴＡ＊探索方法を実行して結果を実現するさらにもう一つの動作順を探索する工程、
（６）前記（３）で選択された準最短動作順の候補と、前記（５）で探索された動作順を比較して、少ない動作回数で結果を実現する準最短動作順の候補を再度選択する工程、
（７）前記（６）で選択された準最短動作順の候補と、選択されなかった動作順を比較して、準最短動作順の候補の中に存在する前後関係の制約がない複数の動作を特定する工程
（８）前記（６）の実行時には前回の（６）の工程で選択された準最短動作順の候補を比較の対象にしながら、前記（５）から（７）の工程を繰り返し実行する工程
を有する準最短動作順探索方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、複数のアクチュエータを備えた設備によって意図した結果を実現するアクチュエータの動作順を探索し、複数回探索することによって複数個探索される動作順の中から数少ない動作回数で結果を実現する準最短動作順を探索する技術に関する。ここで準最短動作順とは、数学的に最小動作回数であることが保証されてはいないものの、最小動作回数または最小動作回数に近い動作回数で結果を実現すると評価できる動作順をいう。
【０００２】
【従来の技術】
例えば、二つのベルトコンベアと一つのクレーンを備えた設備を考える。第１のベルトコンベアは地点Ａから地点Ｂに物を移送する。第２のベルトコンベアは地点Ｃから地点Ｄに物を移送する。クレーンは、初期地点Ｅから地点Ｂ又は地点Ｄに移動し、そこで物を吊り上げ、地点Ｅに移動し、そこで物を降ろすことができるものとする。
ここで、地点Ａにある物Ｘを地点Ｅに移送し、その上に物Ｙを積み重ねるというタスクが与えられたものとする。
与えらたタスクを実行して意図した結果を実現する為には、ベルトコンベアやクレーンを動作させるアクチュエータ類を順序良く動作させなければならない。
このとき、様々な制約が加えられることが多い。例えば二つのベルトコンベアを同時には作動させられないといった制約が加えられることがある。するとおのずと明らかに、前記の場合には、最初に第１ベルトコンベアで物Ｘを地点Ａから地点Ｂに移送し、ついで、クレーンで物Ｘを地点Ｂから地点Ｅに移送すると同時に第２ベルトコンベアで物Ｙを地点Ｃから地点Ｄに移送する順でアクチュエータを駆動すると、意図した結果が最短時間で達成されることがわかる。
【０００３】
上記の動作順を決定するには、「ある動作はある動作に先立って実行されなければならない」、「ある動作とある動作には先後の制約がない」、「ある動作とある動作は同時に実行しても問題がない」といった情報を必要とする。
【０００４】
事象が簡単な場合、人は意図した結果を実現する動作回数が少なくてすむ合理的な動作順を容易に決定することができる。しかしながら、事象が複雑になってくると合理的な動作順を探索する好適な技術がなく、現時点では、ベテラン作業者が試行錯誤を繰返して意図した結果を数少ない動作回数で実現する動作順を得ている。
【０００５】
意図した結果を実現する動作順を探索する手法が開発され、R.E.Korf,”Real-Time Heuristic Search”, Artificial Intelligence Vol. 42, pp 189-211, 1990に報告されている。
この技術では、動作状態を状態ベクトルであらわす。実現する結果に対応する目標状態ベクトルと現時点での状態ベクトルの仮想距離（ハミング距離）を評価関数としながら、その仮想距離を小さくしていく状態ベクトルの変遷の順を探索していく。この技術をこの明細書ではＲＴＡ＊アルゴリズムないしＲＴＡ＊探索方法という。
このＲＴＡ＊探索方法によると、一定の手順に従って処理することで、結果を実現する動作順が探索される。極めて有用な探索技術ということができる。現時点では、専らロボットが迷路を走行しながら目標地点（ゴール）に至るルートを探索する問題に応用され、ＲＴＡ＊探索方法が開発されたことによってロボットが確実にゴールできるようになっている。
【０００６】
【発明が解決しようとする課題】
ＲＴＡ＊探索方法では、ハミング距離を評価関数に用いながら動作順を探索していく。このために、結果を実現する動作順が探索されるだけでなく、少ない動作数で結果を実現する動作順が得られるように探索される。動作後のハミング距離が等しい２以上の動作が選択可能な場合、ＲＴＡ＊探索方法では一定の確率でいずれか一つの動作を採用する。この場合、ハミング距離が変化しない動作群の中で動作選択が繰返され、なかなかハミング距離が減少しないことが起こる。即ち、ＲＴＡ＊探索方法をアクチュエータの動作順探索問題に用いると、探索速度が非常に遅いという問題をもたらす。
本発明の一つの課題は、アクチュエータの動作順の探索に要する時間を短縮化することにある。
ＲＴＡ＊探索方法では、結果を実現する動作順を探索することはできるが、探索された動作順に含まれる動作と動作の関係、即ち、一方の動作は他方の動作よりも先だって実行しなければならないのか、あるいは順不動で同時並行的に実行させることが可能な関係にあるのか否かはわからない。ＲＴＡ＊探索方法は専ら迷路の探索問題に用いられ、一つのロボットが２つのルートを同時並行的に進行することができないから、ＲＴＡ＊探索方法の前記した問題が現時点では認識されていない。しかしながら、アクチュエータの動作順探索問題では、並列処理できる動作については並列処理する動作順が探索できなければ、実用的な動作順が得られることにはならない。ＲＴＡ＊探索方法では、もともと並列処理を想定していないので、この問題に対処することができない。
本発明の他の一つの課題は、並列処理できる動作には並列処理を指示する動作順が探索されるようにすることにある。
例えば、第１動作から第９動作までで結果が実現される場合、動作数は９個である。ここで第１から第３動作は同時に実行することが可能であり、第４から第６動作は同時に実行することが可能であり、第７から第９動作は同時に実行することが可能であるとすると、時間軸に沿って考えたときには３回の動作回数で結果を実現することができる。本明細書では、動作数と動作回数の意味を上記にように使い分ける。
ＲＴＡ＊探索方法では、結果を実現する動作順が探索されるものの、探索された動作順が必ずしも最短動作回数で結果を実現できるものであることは保証されていない。もっと少ない動作回数で結果を実現することができる動作順がありながら、それ以外の動作順が探索されることが多い。
本発明のさらに他の一つの課題は、一つの動作順を探索するだけでなく、複数回に亘って探索する結果として複数個の動作順が探索される中から、少ない動作回数で結果を実現する準最短動作順を検索できるようにすることにある。
【０００７】
【課題を解決するための手段、作用及び効果】
本発明では、複数のアクチュエータを備えた設備によって意図した結果を実現するアクチュエータの動作順を探索し、探索された複数の動作順の中から準最短動作順を探索する。この方法では
（１）ハミング距離と状態コストと遷移コストを評価関数としてＲＴＡ＊探索方法を実行して結果を実現する一つの動作順を探索する工程、
（２）ハミング距離と状態コストと遷移コストを評価関数としてＲＴＡ＊探索方法を実行して結果を実現するもう一つの動作順を探索する工程、
（３）探索された二つの動作順を比較し、少ない動作数で結果を実現する準最短動作順の候補を選択する工程、
（４）選択された準最短動作順の候補と選択されなかった動作順を比較して、準最短動作順の候補の中に存在する前後関係の制約がない複数の動作を特定する工程、
（５）ハミング距離と状態コストと遷移コストを評価関数としてＲＴＡ＊探索方法を実行して結果を実現するさらにもう一つの動作順を探索する工程、
（６）前記（３）で選択された準最短動作順の候補と、前記（５）で探索された動作順を比較して、少ない動作回数で結果を実現する準最短動作順の候補を再度選択する工程、
（７）前記（６）で選択された準最短動作順の候補と、選択されなかった動作順を比較して、準最短動作順の候補の中に存在する前後関係の制約がない複数の動作を特定する工程
（８）前記（６）の実行時には前回の（６）の工程で選択された準最短動作順の候補を比較の対象にしながら、前記（５）から（７）の工程を繰り返し実行する工程を実行する。
工程（１）と（２）と（５）で用いられる状態コストは、物理的位置についての結果位置と現在位置との間の距離に関する値をいい、遷移コストとは前記距離が実質的に変化しない動作についての結果実現に貢献する程度をいう。
【０００８】
前記方法において、工程（１）と（２）と（５）のそれぞれは、ＲＴＡ＊探索方法を実行して結果を実現する一つの動作順を探索するものであり、基本的にはR.E.Korf,”Real-Time Heuristic Search”, Artificial Intelligence Vol. 42, pp 189-211, 1990に報告されている処理を実行する。ここで、本発明では、ハミング距離のほかに、状態コストと遷移コストを考慮した評価関数を用いて探索することから、少ない動作数で結果を実現する動作順が優先的に探査される。ハミング距離が同じ動作の中で探索が実質的に停滞することがなく、結果を実現する動作順がスムースに探索され、しかも、少ない動作数で結果を実現する動作順が優先的に探査される。
【０００９】
この方法では、（４）と（７）の工程で二つの動作順を比較し、動作順に含まれる複数の動作で、前後関係の制約のないものを特定する。例えば、探索された一つの動作順が、「・・・Ａ動作・・・Ｂ動作・・・」の順で動作群を含み、探索されたもう一つの動作順が、「・・・Ｂ動作・・・Ａ動作・・・」の順で動作群を含む場合、Ａ動作とＢ動作は、どちらを先に実施しても良く、前後関係の制約がない事がわかる。従って、同時に処理することができることがわかる。それに対して、探索された動作順のすべてで「Ａ動作、Ｂ動作」の順であり、「Ｂ動作、Ａ動作」の順が探索されないうちは、「Ｂ動作、Ａ動作」の順で実行することが許されるのか否かいまだ不明であることがわかる。
この方法では、複数個の動作順を探索し、探索された動作順を用いて前後関係の制約がない複数の動作を特定していくことから（例えば前記した前者の例ではＡ動作とＢ動作）、探索が進むにつれて、同時に実行可能な動作と動作の関係が累積的に明らかにされていく。
【００１０】
この方法で、探索された動作順から、同時に実行可能な動作と動作の関係が累積的に明らかにされていくことから、探索された動作順の動作回数をカウントすることができ、探索された動作順の中から動作回数の少ないものを選択することができる。
【００１１】
前記（６）の工程で比較の対象とする準最短動作順の候補については、（４）または前回の（７）の工程で、前後関係の制約がない動作が特定されていることから、動作数の他に動作回数が算出可能となっている。従って（６）では、準最短動作順の候補の動作回数と、（５）で検索された動作順の動作数を比較する。
これに代えて、（５）で検索された動作順についても、それまでに判明している前後関係の制約がない動作の情報を活用して動作回数を求め、求められた動作回数を準最短動作準の候補の動作回数と比較してもよい。あるいは、極単純に、動作数同士を比較の対象にしてもよい。この場合、動作回数に近似するものとして動作数が活用される。
（５）と（６）と（７）の工程では、一つの動作順を探索し、それまでに選択された準最短動作順の候補の動作回数と新たに探索された動作順の動作回数（近似的には動作数）を比較して少ない動作回数で結果を実現する準最短動作順の候補を再度選択し、選択された準最短動作順の候補と選択されなかった動作順を比較して、選択された準最短動作順の候補の中に存在する前後関係の制約がない複数の動作を特定するために、動作回数が少ない動作順が優先的に選択され、しかも、新たに選択された準最短動作順の中に存在する前後関係の制約がない複数の動作が明らかにされて準最短動作順の候補の動作回数がさらに減らされる。
【００１２】
以上の処理が（８）によって繰り返し実行される結果、動作回数が少なくてすむ準最短動作順が効率的に探索される。
この場合、ＲＴＡ＊探索方法で探索される動作順がすでに準最短動作順であるということもできる。しかしながら、この発明では、ＲＴＡ＊探索方法で複数個探索される（準最短）動作順の中からさらに最小の動作回数ですむ動作順を選択するものであり、ここではこの様にして選択された動作順を準最短動作順という。ＲＴＡ＊探索方法で探索される動作順は通常の意味ではすでに準最短動作順であるけれども、ここでは、単に一つの動作順にすぎないとして扱う。
【００１３】
本発明の方法によると、複雑な事象を伴う為に一つの結果実現動作順すら見出せないような場合に、合理的な（すなわち動作回数が少なくてすむ）動作順を機械的に探索することができ、設備のシーケンスコントロールプログラムを非ベテラン作業者が短時間で作成することが可能となる。
【００１４】
【発明の実施の形態】
最初に、本発明の方法で動作順を探索する設備の一例を図１を参照して説明する。
図１に示された搬送設備Ｓは、第１ベルトコンベアＸ１、第２ベルトコンベアＸ２、第３ベルトコンベアＹ１、第４ベルトコンベアＹ２、第１クレーンＣ１、第２クレーンＣ２、ワーク置き場Ｐを備える。この搬送設備Ｓは、第１ベルトコンベアＸ１のワーク投入端すなわち始端（図左上端）または第２ベルトコンベアＸ２の始端（図左上端）に投入されたワークＷをワーク置き場Ｐに搬送する。この搬送設備Ｓは、図示されない制御コンピュータと、プログラマブルロジックコントローラ（ＰＬＣ）を備える。
制御用コンピュータは、意図した搬送結果が得られるように搬送するために必要なアクチュエータの動作順を予め演算ないし探索する。また制御用コンピュータは、予め演算ないし探索された結果に基づいて、プログラマブルロジックコントルーラＰＬＣを介して、各アクチュエータの動作を制御する。制御用コンピュータは、この制御動作中に、各アクチュエータの動作状態やワーク位置を検出し、検出値を参照しながら各アクチュエータが意図した動作状態となるように制御する。
プログラマブルロジックコントルーラは、制御用コンピュータとアクチュエータ間のインターフェースの役割を担うものである。制御用コンピュータからの指令に基づき各アクチュエータを直接駆動させるドライバーであり、またコントローラである。さらに、各アクチュエータの動作状態やワーク位置を検出する検出装置からの検出信号を制御用コンピュータに送信するとともに、搬送設備Ｓの動作状態を記録するデータロガーでもある。
【００１５】
第１ベルトコンベアＸ１は始端に投入されたワークＷを終端に移送することができる。第１ベルトコンベアＸ１の始端と中間位置と終端にワークの有無を検出する検出装置Ｘ１１、Ｘ１２、Ｘ１３が設けられている。同様に、第２ベルトコンベアＸ２は始端に投入されたワークＷを終端に移送することができる。第２ベルトコンベアＸ２の始端と中間位置と終端にワークの有無を検出する検出装置Ｘ２１、Ｘ２２、Ｘ２３が設けられている。
第１クレーンＣ１はアームＡ１を備え、そのアームＡ１はクレーンの長さ方向すなわち、ベルトコンベア群Ｘ１、Ｘ２、Ｙ１、Ｙ２のワーク移送方向に直角な水平方向に移動可能である。また、アームＡ１は上下動可能である。アームＡ１の下端には吸着口が形成されており、その吸着口は可撓性ホースによって図示されない小型コンプレッサに接続されている。小型コンプレッサの吸気管に発生する負圧が吸着口に伝えられたときにアームＡ１の下端にワークＷが吸着され、小型コンプレッサの排気管に発生する正圧が吸着口に伝えられたときにアームＡ１の下端からワークＷが開放される。
第１クレーンＣ１は、第１・第２ベルトコンベアＸ１とＸ２の終端でワークを吸着し、上方に持ち上げ、第３・第４ベルトコンベアＹ１とＹ２の始端上に移動し、ワークを降ろし、第３・第４ベルトコンベアＹ１とＹ２の始端にワークを置くことができる。
第１クレーンＣ１は、アームＡ１の水平方向の位置を検出する５つの検出装置Ｃ１１〜Ｃ１５を備えている。検出装置Ｃ１１〜Ｃ１５は、図１に良く示されるように、クレーンの長さ方向に設けられている。検出装置Ｃ１１は第１ベルトコンベアＸ１の終端にあるワークをアームＡ１が吸着できる位置に対応する。検出装置Ｃ１５は第２ベルトコンベアＸ２の終端にあるワークをアームＡ１が吸着できる位置に対応する。検出装置Ｃ１２はアームＡ１で吸着したワークを第３ベルトコンベアＹ１の始端に置ける位置に対応する。検出装置Ｃ１４はアームＡ１で吸着したワークを第４ベルトコンベアＹ２の始端に置ける位置に対応する。また、アームＡ１には、アームＡ１が上動しているのか下動しているのかを検出する検出装置Ｃ１６と、アームＡ１下端にワークＷが吸着されているかいないかを検出する検出装置Ｆ１１が設けられている。
【００１６】
第３ベルトコンベアＹ１は始端に投入されたワークＷを終端に移送することができる。第３ベルトコンベアＹ１の始端と中間位置と終端にワークの有無を検出る検出装置Ｙ１１、Ｙ１２、Ｙ１３が設けられている。同様に、第４ベルトコンベアＹ２は始端に投入されたワークＷを終端に移送することができる。第４ベルトコンベアＹ２の始端と中間位置と終端にワークの有無を検出する検出装置Ｙ２１、Ｙ２２、Ｙ２３が設けられている。
第２クレーンＣ２はアームＡ２を備え、そのアームＡ２はクレーンの長さ方向すなわち、ベルトコンベア群Ｘ１、Ｘ２、Ｙ１、Ｙ２のワーク移送方向に直角な水平方向に移動可能である。またアームＡ２は上下動可能である。アームＡ２の下端には吸着口が形成されており、その吸着口は可撓性ホースによって図示されていない小型コンプレッサに接続されている。小型コンプレッサの吸気管に発生する負圧が吸着口に伝えられたときにアームＡ２の下端にワークＷが吸着され、小型コンプレッサの排気管に発生する正圧が吸着口に伝えられたときにアームＡ２の下端からワークＷが解放される。
第２クレーンＣ１は、第３・第４ベルトコンベアＹ１とＹ２の終端でワークを吸着し、上方に持ち上げ、ワーク置き場Ｐ上に移動し、ワークを降ろし、ワーク置き場Ｐにワークを置くことができる。
第２クレーンＣ２は、アームＡ２の水平方向の位置を検出する５つの検出装置Ｃ２１〜Ｃ２５を備えている。検出装置Ｃ２１〜Ｃ２５は、図１に良く示されるように、クレーンの長さ方向に設けられている。検出装置Ｃ２２は第３ベルトコンベアＹ１の終端にあるワークをアームＡ２が吸着できる位置に対応する。検出装置Ｃ２４は第４ベルトコンベアＹ２の終端にあるワークをアームＡ２が吸着できる位置に対応する。検出装置Ｃ２３はアームＡ２で吸着したワークをワーク置き場Ｐに置ける位置に対応する。また、アームＡ２には、アームＡ２が上動しているのか下動しているのかを検出する検出装置Ｃ２６と、アームＡ２下端にワークＷが吸着されているかいないかを検出する検出装置Ｆ２１が設けられている。
ワーク置き場Ｐは、第３・第４ベルトコンベアＹ１とＹ２の終端間に設けられている。ワーク置き場Ｐにも、ワークＷの有無を検出する検出装置Ｐ０が設けられている。
【００１７】
上記各検出装置の出力信号は（０，１）の２値であり、検出した場合は「１」、検出しない場合は「０」である。
【００１８】
この搬送設備Ｓの動作状態は、各検出装置の検出値で記述できる。例えば、第１ベルトコンベアＸ１の場合、ワークが始端に投入された状態では、Ｘ１１が「１」で、Ｘ１２とＸ１３は「０」である。中間位置に移送された状態では、Ｘ１２が「１」で、Ｘ１１とＸ１３は「０」である。終端に移送された状態では、Ｘ１３が「１」で、Ｘ１１とＸ１２は「０」である。第１クレーンＣ１で第１ベルトコンベアＸ１の終端からワークが吊り上げられると、Ｘ１１とＸ１２とＸ１３の全部が「０」となる。
第１ベルトコンベアＸ１を動作させるアクチュエータは、検出装置の検出値の組合せ状態が変化する動作を単位として制御される。例えば、ワークが始端にある「１，０，０」の状態から、ワークが中間位置に送られて「０，１，０」となる動作が一つの単位であり、ワークが中間位置にある「０，１，０」の状態からワークが終端に送られて「０，０，１」となる動作が一つの単位である。ここで、「１，０，０」等は、Ｘ１１,Ｘ１２,Ｘ１３の検出値の組合せをいう。動作の単位は、すべてのアクチュエータについて共通的に前記のようにされており、制御用コンピュータが一つの動作を指示すると、対応するアクチュエータは隣接する検出装置または自身の検出装置の検出値が反転するまで動作を続け、そこで動作を停止する。
【００１９】
次に搬送設備Ｓの動作順探索手順について説明する。図示されない制御用コンピュータが、アクチュエータの動作順を探索する。例えば、ベルトコンベアＸ１について見ると、最初にワークが始端にある「１，０，０」の状態から中間位置に送られて「０，１，０」となる動作を選択し、ついでワークが中間位置にある「０，１，０」の状態から終端に送られて「０，０，１」となる動作を選択するといった動作順を探索する。
本実施形態では、ＲＴＡ＊探索方法（以下ＲＴＡ*と略す）を実行して動作順を探索する。ＲＴＡ*探索方法は、実時間解探索アルゴリズムであり、最適ではないけれども準最適な解を短時間で探索することができるアルゴリズムである。
ここで準最適な解は１つではなく、複数存在し、探索のたびに新たな準最適解が探索される。
前記したように、搬送設備Ｓは、合計２７の検出装置をもつために、２７ビットの２進数で状態を記述できる。図２は、この内、第１クレーンＣ１のアームＡ１の水平位置を記述する部分（Ｃ１１からＣ１５の５ビット）と、アームＡ１が上動しているか下動しているかを記述する部分（Ｃ１６の１ビットで、１は上動しており、０は下動していることを示す）と、アームＡ１がワークＷを吸着しているか否かを記述する部分（Ｆ１１の１ビットで、１は吸着しており、０は吸着していないことを示す）を示したものであり、例えば、左コラムの最上段に示す状態BＸ１は、アームＡ１がＣ１２に位置して上動してワークを吸着しないでいる状態であることを記述している。図２では、Ａ〜ＥがアームＡ１の水平方向位置を示し、Ｘはアームが上動しており、Ｙはアームが下動しており、１はワークを保持しておらず、２はワークを保持している状態を示す。
【００２０】
図２は、可能な動作（中間コラム）と、動作前の状態（左コラム）と、動作後の状態（右コラム）の一覧表を示している。例えば、前記したBＸ１の状態から動作番号１の左進動作と、動作番号６の右進動作と、アームの下動動作が可能で、左進すれば状態ＡＸ１に変化し、右進すれば状態ＣＸ１に変化し、アームＡ１が下動すれば状態ＢＹ１に変化することを示す。
動作番号が９と１０の動作は、状態Ａ〜Ｅと状態１〜２のいずれからも実行可能な動作である。
図２は、搬送設備Ｓの２７ビットで示される状態のうちの第１クレーンＣ１に関する部分を抜き出したものであって、実際にはさらに多くの状態数が存在し、さらに多くの動作種類が存在する。搬送設備Ｓが取り得る状態は、その状態から取り得る動作種類と、その動作後の状態と組になって、制御用コンピュータの記憶装置に記憶されている。
【００２１】
ＲＴＡ＊探索方法は、出発状態と最終状態が与えられたときに、その間の動作順を探索する方法である。あるいは状態の遷移順を探索する方法である。例えば、出発状態がＡＸ１で最終状態がＢＹ１であるとき、図２から明らかに、順１、順２、順３・・に例示する様々な動作の連鎖が抽出可能である。ＲＴＡ＊探索方法は、可能な動作の連鎖の中から、最終状態に至る連鎖ないし動作順を探査する方法である。例えば、ＲＴＡ＊探索方法を実行する途中段階で、状態ＢＸ１に至る動作順までが探索されたとする。次に選択可能な動作は動作番号が１、６、９のいずれかである。この場合、各動作の実行後の状態で記述される状態ベクトルの先端と最終状態を記述する状態ベクトルの先端との間のベクトル空間内での距離（ハミング距離）を計算し、そのハミング距離を小さくする動作を選択する。
このロジックを次々に実行すると、最終状態に至る動作順が探索される。なおハミング距離が同じ動作が複数存在する場合には、確率に従っていずれか一つの動作を選択して探索ステップを進める。このとき、確率を利用して動作を選択する為に、探索の都度、異なる動作順が探索される。
なお、ＲＴＡ＊探索方法の詳細は、R.E.Korf,”Real-Time Heuristic Search”, Artificial Intelligence Vol. 42, pp 189-211, 1990に報告されている。ＲＴＡ＊探索方法を一度実行すると、出発状態から最終状態に至る一つの動作順が探索される。この場合、ハミング距離を短くするような動作順が探索されることから、この動作順は最小の動作数で出発状態から最終状態に至らせる順であろうと推定される。但し、ハミング距離が等しい複数の動作が存在することから、ＲＴＡ＊探索方法を実行するたびに別の動作順が探索される。ＲＴＡ*探索方法では複数の動作順が探索され、そのままでは本発明でいう準最短動作順（ＲＴＡ*探索方法で探索される複数の動作順のなかで動作回数が最短のもの）は決らない。
【００２２】
ＲＴＡ＊探索方法の実行中に次の動作を探索する際に、ハミング距離だけを評価関数として次の動作を探索すると、ハミング距離が等しい動作が複数ある場合に、無駄な動作を繰返す動作順が探索されることが多くおこり、探索処理に期間がかかるのみならず、無駄な動作を含む動作順が探索されやすい。そこで、この実施の形態では、評価関数として、ハミング距離のほかに、状態コストと遷移コストを用いる。
【００２３】
状態コストは、ワークＷを速やかにワーク置き場Ｐへ搬送させるために、探索空間に対しゴール方向への圧力をかける効果がある。この状態コストを図３に示す。第１・第２ベルトコンベアＸ１、Ｘ２の始端側で最も大きな値を持ち、ワーク置き場Ｐに物理的に近づくにつれて小さな値に変化する。即ち、ワークＷがワーク置き場Ｐに物理的に近づくほど、状態コストは小さくなる。クレーンＣ１、Ｃ２の水平方向位置のように、ゴールまでの物理的距離が同一の状態については同一の値を持つ。
【００２４】
遷移コストは、動作自体に要するコストの指標であり、本搬送設備Ｓの場合には以下のように設定する。
▲１▼コンベアＸ１、Ｘ２、Ｙ１、Ｙ２の終端にワークＷが存在し、かつ、クレーンＣ１、Ｃ２がワークＷを把持していない場合、ワークＷに近づくようにアームＡ１、Ａ２を動かす場合の遷移コストは「１」、何もしない場合は「２」、離れる場合は「３」とする。
▲２▼クレーンＣ１、Ｃ２がワークＷを把持している場合、コンベアＹ１、Ｙ２の始端又はワーク置き場Ｐに近づくようにアームＡ１、Ａ２を動かす場合の遷移コストは「１」、何もしない場合は「２」、離れる場合は「３」とする。
▲３▼その他の場合、クレーンＣ１、Ｃ２の遷移コストは「２」、動かない場合は「１」とする。
▲４▼コンベアＸ１、Ｘ２、Ｙ１、Ｙ２の遷移コストは全て「１」とする。
【００２５】
ハミング距離は、遷移先状態ベクトル（一つの動作後の状態ベクトル）と目標状態ベクトルの仮想距離を示す。
【００２６】
状態遷移候補（すなわち動作候補に対応する）に対し、前述した状態コストと遷移コストとハミング距離の３つの和を計算する。検討している状態から実行可能な動作群について、動作後の状態について計算した評価値が一番小さい状態へ遷移する動作を選択する。一番小さい評価値を持つ遷移先の状態が複数ある場合、すなわち複数の動作が存在する場合は、そのうちの一つの動作を確率的に選択する。
前述したように、「遷移先の状態候補（動作に対応する）を創発し、それぞれの動作の実行後の状態の評価値を計算し、その評価値がもっとも低くなる動作を選択する」という処理を繰返しながら、出発状態から最終状態に至る動作順を探索する。
このように、評価関数にハミング距離の他に状態コストと遷移コストを導入した為に、動作の選択に際して目的実現側に圧力がかけられることになり、ＲＴＡ＊探索方法によって動作順が短時間で探索されるようになった。
【００２７】
ＲＴＡ＊探索方法によって探索される動作順は、動作の一次元の連鎖である。
すなわち、動作１、動作２、動作３・・・といった並びが探索される。この場合、例えば、動作２の実行前に動作１が実行されていなければならないのに対し、動作２と動作３の間には前後関係の制約がなく、同時に実行してもよいことがある。ＲＴＡ*探索方法で探索される動作順からは、上記の前後関係の制約の有無まではわからない。
しかしながら、「動作２の実行前に動作１が実行されていなければならない」という前後関係の制約が存在すれば、ＲＴＡ*探索方法を繰り返し実行したときに「動作１が先で動作２が後」の動作順しか探索されないのに、「動作２と動作３との間には前後の制約がない」のならば、ＲＴＡ*探索方法を繰り返し実行したときに「動作２が先で動作３が後」の動作順が探索されたり、あるいは、「動作３が先で動作２が後」の動作順が探索される。すなわち、探索された複数の動作順を分析することで、内在している前後関係の制約を顕在化することができる。
【００２８】
図４に示すフローチャートは、ＲＴＡ*探索方法で探索された２つの動作順から、前後関係の制約がない二つの動作の組合せを見出すための処理を示している。
最初にＲＴＡ*探索方法を実行して一つの動作順を探索する（ステップＳ４）。ここでは最初に検索された動作順に従って各動作の動作番号を１、２、・・と命名する。動作番号を上記のように命名すると、最初に探索される動作順は、１、２、３、・・となる。ここでは、動作１から動作８までの８動作によって結果が得られることがわかったとする。
ステップＳ８では、探索された動作順を図５の行列に展開する。この行列では、列に沿って動作順をならべ、行についてはその動作順に含まれる動作を順不動に配置する。この行列では、列に示される動作と行に示される動作の前後の関係を示し、列に示される動作に対して行に示される動作が先行する場合には「１」を割り当て、そうでない動作には「０」を割り当てる。行方向にも探索された順に従って動作を配列すると、上三角要素が「０」、下三角要素が「１」となる。
図５に示すこの行列を以下メイン行列Ｍ１という。なお、この行列は、動作の前後関係を示すものであり、最初の動作１同士を比較することが無意味であるので、列から最初の動作を外す。同様に、最後の動作８同士を比較することも無意味であるので、行から最後の動作を外す。この様に最初の動作と最後の動作を外しても、前後関係の情報が行列に盛り込まれる。
【００２９】
次に、図4のステップＳ８で、再度ＲＴＡ*探索方法を実行して、二つ目の動作順を探索する。ここでは、仮に、図６の列方向に示す動作順が探索されたとする。すなわち、２回目には、１，２，６，３，４，５，７，８の動作順が探索されたとする。
図４のステップＳ１０では、２回目に探索された動作順に対してステップＳ８と同じ処理をする。この結果、図６に示す行列が得られる。この行列の例えば動作６の行を見ると、動作１と２は動作６よりも先行し、動作３，４，５，７，８は動作６よりも先行しないことを記述している。当然のことながら、この行列は２度目の動作順の前後関係の情報を反映している。図６に示す行列を以下サブ行列Ｓ１という。
【００３０】
図４のステップＳ１２は、探索された動作順に含まれる動作数ないし動作回数を比較する処理であり、同じであれば意味を持たない。ここでは同じである場合を先に説明する。
ステップＳ１４では、図５に示されるサブ行列Ｓ１の配列をメイン行列Ｍ１の配列に並び替える。この並び替えれたサブ行列Ｓ２が図７に示される。
ステップＳ１６では、メイン行列Ｍ１と並び替えられたサブ行列Ｓ２の要素ごとに論理積を計算して新たなメイン行列Ｍ２を求める。
新たに求められたメイン行列Ｍ２は、最初に探索された動作順でも、２度目に探索された動作順でも、ともに前後の関係にある２つの動作に対して「１」が割当てられ、一方の動作順と他方の動作順の前後の関係が逆転している２つの動作に対して「０」が割当てられている。最初のメイン行列Ｍ１の列６では、動作６に対して動作３、４が先行しているのに対し、２度目のメイン行列Ｍ２の列６では、動作６に対して動作３、４が後行しても良いのに対応して「０」に変わっている。
【００３１】
以後、３度、４度・・とＲＴＡ＊探索方法を繰り返し（ステップＳ８）、新たに探索される動作順によってサブ行列を生成し（ステップＳ１０）、そのサブ行列の配列順をメイン行列の配列順に置き換え（ステップＳ１４）、メイン行列Ｍと並び替えられたサブ行列Ｓの要素ごとに論理積を計算して新たなメイン行列Ｍを求める処理を繰返す。
この処理を多数回繰返したときのメイン行列Ｍは、多数個探索された動作順のすべてで前後の関係にある２つの動作に対して「１」が割当てられ、一つの動作順と他の動作順で前後の関係が逆転している２つの動作に対して「０」が割当てられている。すなわち、多数回繰返したときのメイン行列Ｍは、それまでにわかっている結果実現動作順のいずれでも前後の関係が固定的であり、前後関係を逆転したときに結果を実現できるか否かがわからない２つの動作に対して「１」が割当てられ、前後の関係が制約されない２つの動作に対して「０」が割当てられている。
この結果、多数回繰返したときのメイン行列を分析することによって、前後の関係を逆転しても結果を実現できる２つの動作と、前後の関係を逆転したときには結果を実現できることが保証されていない２つの動作の関係を知ることができる。
【００３２】
次に、多数回繰返したときのメイン行列から、同時に実行可能な動作であることを視覚的に示すグラフ（木構造）に転換する為の処理を示す。
いま、図７のＭ２が多数回繰返したときのメイン行列であるとする。グラフ表示に転換するときには、このメイン行列Ｍ２を、一行中に含まれる「１」の数が少ない順に列を並べ替える。ついで、その並べ替えられた列の順に従って行を並べ替える。この結果が図８のＭ３に示される。この行列Ｍ３から、下記のルールによってグラフ化する。
ルール１：「１」の数が増加する順で動作を配置する。
ルール２：「１」の数が同じ動作は並列に配置する。
ルール３：グラフ中の直前の階層に含まれ、しかもマトリクスで「１」の動作から矢印を引く。
図９は、図８の行列を先のルールに従ってグラフ化したものであり、ルール１に従って、１，２，３，４，５，７，８が配置され、ルール２に従って３と６が並列に配置され、ルールに３によって矢印が加えられている。例えば、動作５についてみると、グラフ中の直前の階層に４と６の動作が含まれるところ、図８のメイン行列中、動作４に対しては「１」であり、動作６に対しては「０」である為に、動作５に対しては動作４からのみ矢印が引かれる（ルール３）。動作７についてみると、グラフ中の直前の階層に５と６の動作が含まれるところ、図８のメイン行列中、動作５と６のいづれに対しても「１」であり、動作７に対して動作５と６の双方から矢印が引かれる（ルール３）。
図９のグラフは、図８の行列の意味するところを視覚的に認識しやすく表現したものである。同時に実行可能な動作に対しては、並列分岐処理の矢印が示される。このために、図７の過程を並列分岐処理の抽出過程といい、そのようにして得られた行列Ｍ２からＭ３を介して図９のグラフを得る過程を木構造化処理ということにする。
図９の木構造は、ＲＴＡ*探索方法を何度実行しても、「１，２，３，４，５，７，８、」の順しか探索されないのに対し、動作６は、動作３，４，５に対して先行したり後行したりする動作順が探索された結果を反映している。
図８の最終メイン行列から、結果を実現する動作順は１から８の８個の動作数を必要とするところ、動作６は動作３，４，５のいずれかと同時に実行することができるために、動作回数は７回であることがわかる。
【００３３】
上記の例では、探索される動作順に含まれる動作数が等しく、かつ、同じ動作が含まれる場合を説明した。
実際には、探索された動作順の一方に含まれる動作数が他方に含まれる動作数よりも小さいことがある。当然に、一方の動作順に含まれる動作が他方の動作順に含まれないことがある。手順によって結果実現までの動作数が異なったり、あるいは、ある手順に従うと他の手順では必要とされない動作を実行しなければならなくなることは日常生活でよく経験するところであるが、ＲＴＡ*探索方法では、確率を用いながら動作順を探索していくことから、上記の現象が得られるのである。
【００３４】
次に、ＲＴＡ*探索方法で、それまでに探索された動作回数とは違う動作数の動作順が探索された場合の処理を説明する。
このときにも、図４のフローチャートによって、探索された動作順の中で、前後関係が必要とされる動作と、必要とされないために同時に実行可能な動作が判明する。
このときには、図４のステップＳ１２が意味を持つ。ステップＳ１２では、それまでに得られているメイン行列の動作回数と、新たに探索された動作順の動作数を比較する。ここで動作回数は図９を参照して説明したものであり、図９の場合は７回である。新たに探索された動作順からは同時に実行可能な動作かあるいは経時的に実行することを要する動作なのかの分析が終了していないために、動作回数がわからない。そこで、この段階では、動作回数に代って動作数を用いる。
【００３５】
図１０に示す新たな動作順、すなわち、１，４，２，５，９，８の動作順が探索されたものとする。この場合、図９に示される、それまでに探索された動作順から並列処理可能な動作を抽出して動作回数を低減した動作回数（この場合７回）と、新たに探索された動作順の動作数（この場合６動作）を比較すると、後者の方が数が少ないので、新たに探索された動作順の行列をメイン行列とし、それまでのメイン行列をサブ行列とする。
新たに探索された動作順に対して、それまでに判明している並列処理可能な動作の関係を適用して動作回数を算出し、算出された動作回数（動作数でない）をステップＳ１２の比較処理に用いることも可能である。この方法によると、動作回数が少ない動作順を中心にして探索された動作順が選択されていく為に、動作回数の少ない動作順が効率的に選択され、その動作回数が少ない動作順の中でさらに並列処理可能な動作の抽出が実行されて一層に動作回数が少なくなる。
図１１のＭは、置き換えられたメイン行列であり、図１０のものである。図１１のＳは、置き換えられたサブ行列であり、図７のＭ２または図８のＭ３の行列から得られる。図１１のＳの行列は、図７のＭ２の行列を図１１のメイン行列Ｍの配列に一致させて配列しなおしたものである。ここで、Ｍのメイン行列に登場しない動作は無視する。Ｍのメイン行列にあってＳのサブ行列に存在しない動作については、対応する要素を空白にする。Ｍのメイン行列にあってＳのサブ行列に存在しない動作は、新たに探索された動作順ではじめて探索された動作であり、前後の関係がまだ未検討な動作に相当する。
以上の処理の終了後に、図４のステップＳ１６を実施する。この場合、一方の要素が空白の部分については論理和を取る。
【００３６】
以上の処理の様子が図１１に示され、処理後のメイン行列Ｍには、それまでの処理によって並列処理可能なことが判明した動作の情報が盛り込まれている。このようにして得られたメイン行列から、先に説明したグラフ化処理をした結果が図１２に示され、新たに探索された１，４，５，２，９，８の動作順が、実際には、１，４，５，９，８の動作順と１，２，９，８の動作順が複合したものであって、動作２は、動作４と５に対して並列処理可能であり、動作回数が５回であることがわかる。
【００３７】
以上の処理をＲＴＡ*探索方法を実行するごとに繰返すと、動作回数が少ない動作順が選択され、しかも、その動作順のなかに存在する並列処理可能な動作と経時的に処理することが必要な動作の関係が抽出され、結局は、与えられた出発状態から目的とする最終状態に至らせる各アクチュエータの動作順（並列処置できる動作にはその情報を盛り込んだ動作順であって、探索された中では最小の動作回数ですむ動作順）が得られる。
この様にして得られる動作順は、ＲＴＡ*探索方法で探索された動作順から並列処理可能な動作を抽出して動作回数を求め、その動作回数が最小のものである。従って実際には、最短動作回数の動作順と評価することができる。但し、数学的には最短動作回数であることが保証はされてはいない。そこで、本発明では、この様にして選択された動作順を準最短動作順という。
【００３８】
ＲＴＡ*探索方法による探索処理と、並列処理できる動作を抽出して動作回数を計算して動作回数が少なくてすむ動作順を選択していく処理は別に実施することが可能であり、図１３に示すように、予め複数の結果実現動作順を探索しておき、その後にステップＳ１０以降の処理を繰返してもよい。
【００３９】
搬送設備Ｓに対して、ＲＴＡ*探索方法を１０回実施し、２つのワークＷが第１・第２ベルトコンベアＸ１，Ｘ２の始端にある初期状態から、２つのワークＷがともにワーク置き場Ｐにある最終状態にまで至らせる動作順を１０個探索した。図１４は、探索された動作順に必要とされた動作数を示す。図１４のＷ１は１つ目のワークＷがワーク置き場Ｐまで到達するのに要した動作数であり、Ｗ２は２つ目のワークＷがワーク置き場Ｐまで到達するのに要した全動作数である。図１４に良く示されるように、ＲＴＡ*探索方法を１０回実行することで探索された１０個の動作順（Ｎｏ．１〜１０）のなかで、最小動作順は４５動作数（Ｎｏ．７）であり、最大動作順は５８動作（Ｎｏ．１０）であった。人間が直感的に考える最小動作数は４１であり、ＲＴＡ*探索方法でほぼ最短動作順を探索できるものの、なお、余分な動作を行っていることになる。
図１５に、検索された動作順のうち、１番と５番と７番の動作順を例示する。
図中に示す記号はアクチュエータの動作の名称である。
ある動作順では存在する動作で他の動作順では存在しない動作が存在する。これらの動作は選択分岐の動作である。一方に、全部の動作列に存在するもののその出現順序が異なっている動作が存在する。それらの動作は並列分岐の動作である。
【００４０】
前述した１０個の動作順（Ｎｏ．１〜１０）に対し、並列分岐抽出アルゴリズムを適用した結果を図１６と図１７に示す。
図１６中のTrial 1 （以下Ｔｒ．１と略す）は、最初に探索された動作順自身であり、図１５のＮｏ．１に等しい。この動作順には並列分岐抽出処理が実行されていない。
Ｔｒ．２は、Ｎｏ．１とＮｏ．２の動作順に対し並列分岐抽出アルゴリズムを実施した結果である。Ｎｏ．１が５６動作であり、Ｎｏ．２が４８動作であるために、Ｎｏ．２の動作順をメイン行列にし、Ｎｏ．１の動作順をサブ行列にし、図４のステップＳ１６とステップＳ２０の処理を行なった。Ｔｒ．２に示されるように、４ヶ所（動作順位の１、１１、２６、２７番）で並列分岐が抽出されていることが判る。この結果、Ｎｏ．２の動作順は、４８の動作数で、４４の動作回数であることがわかる。
【００４１】
以下同様に、Ｔｒ．３は、それまでのメイン行列とＮｏ．３の行列から並列分岐を抽出したものであり、Ｔｒ．１０はそれまでのメイン行列とＮｏ．１０の行列から並列分岐を抽出したのである。
この処理の過程で、Ｎｏ．７の動作順が４５動作であり、そのときのメイン行列の動作回数が４０であり、そのときまでに判明している前後関係の制約のない動作の情報を用いて計算したＮｏ．７の動作順の動作回数が３９であった為に、Ｔｒ．７以降を計算する際には、Ｎｏ．７の動作順がメイン行列とされた。
最終的に得られた結果であるＴｒ．１０では、６ヶ所（動作順位１、２、２４、２５、２８、３５）で並列分岐が抽出されている。そのＴｒ．１０の動作回数は３９回である。Ｔｒ．１０の動作回数（３９回）はＴｒ．１の動作回数（５６回）に比べて１７回も短くなっている。本アルゴリズムの有効性を示す結果となっている。
【００４２】
本実施形態のアルゴリズムでは、評価関数として状態コストと遷移コストとハミング距離を用いているが、それぞれの評価値の設定や評価方法は、前述した値に限らずに適用することができる。
また、本実施形態では、最短動作順の探索の過程で並列分岐処理の抽出手法を用いたが、２つの動作順から並列分岐処理可能な動作を抽出すること自体で有用性を持つものであり、繰り返し実行してはじめて有用なものでない。
また、本実施形態では、最短動作順を探索してから木構造に変換する処理をしているが、２つの動作順から並列分岐処理可能な動作を抽出した段階で木構造に変換すること自体で有用性を持つものであり、最後に一度実行する使い方に限られない。
本実施の形態では、制御用コンピュータが予め準最短動作順を探索する。これに代えて、制御用コンピュータがアクチュエータを動作させながら同時に準最短動作順を探査する方式も可能である。
【図面の簡単な説明】
【図１】本実施形態の搬送設備を示した図である。
【図２】本実施形態の動作前状態と動作後状態の例を示す。
【図３】本実施形態のワークによる状態コストを示した図である。
【図４】ＲＴＡ*探索方法で探索された２つの動作順から、前後関係の制約がない二つの動作の組合せを見出すためのアルゴリズムを示したフローチャートである。
【図５】探索された動作順を示した行列である。
【図６】探索された動作順を示した行列である。
【図７】行列Ｍ１と、行列Ｓ１の配列を行列Ｍ１の配列に並び替えられた行列Ｓ２と、論理演算後の行列Ｍ２を示す。
【図８】行列Ｍ２を、一行中に含まれる「１」の数が少ない順に列を並べ替えた行列Ｍ３を示す。
【図９】行列Ｍ３の木構造化処理の結果を示す。
【図１０】探索された動作順を示した行列である。
【図１１】図１０の行列Ｍと、図７のＭ２行列から置き換えられたサブ行列と、論理演算後の行列Ｍを示す。
【図１２】行列Ｍの木構造化処理の結果を示す。
【図１３】予め複数の結果実現動作順を探索する場合のアルゴリズムを示したフローチャートである。
【図１４】出発状態から最終状態までの動作数を示す。
【図１５】検索された動作順を例示する。
【図１６】並列分岐抽出アルゴリズムを適用した結果を示す。
【図１７】並列分岐抽出アルゴリズムを適用した結果を示す。
【符号の説明】
Ｓ・・搬送設備
Ｘ１・・第１ベルトコンベア
Ｘ２・・第２ベルトコンベア
Ｙ１・・第３ベルトコンベア
Ｙ２・・第４ベルトコンベア
Ｃ１・・第１クレーン
Ｃ２・・第２クレーン
Ｐ・・ワーク置き場
【図１】
0004560591.tif 000002
【図２】
0004560591.tif 000003
【図３】
0004560591.tif 000004
【図４】
0004560591.tif 000005
【図５】
0004560591.tif 000006
【図６】
0004560591.tif 000007
【図７】
0004560591.tif 000008
【図８】
0004560591.tif 000009
【図９】
0004560591.tif 000010
【図１０】
0004560591.tif 000011
【図１１】
0004560591.tif 000012
【図１２】
0004560591.tif 000013
【図１３】
0004560591.tif 000014
【図１４】
0004560591.tif 000015
【図１５】
0004560591.tif 000016
【図１６】
0004560591.tif 000017
【図１７】
0004560591.tif 000018