(57)【要約】      （修正有）【課題】タイムラインに基づく自動化されたプランニングの方法を提供する。【解決手段】オンラインプランニングシステムおよび方法は、計画が作成される環境における変数をタイムラインの形式で表す。タイムラインは、前記変数のうちの様々な変数がその値を時間と共にどのように変更するのかを捕えることによって、絶えず維持される。前記計画は、影響を受けたタイムラインにトークンを加えることによって、立てられて、維持される一貫した計画であり、各トークンは、このタイムラインによって表される変数に影響を及ぼす様々なタイプのアクションを表す。【選択図】図１
2012150800.tif 000002
【特許請求の範囲】
【請求項１】
オンラインプランニング方法であって、
アクションのシーケンスおよびワールド状態における計画の効果を表す対応するタイムラインの形式で計画が作成される環境における、変数を表すステップと、
前記変数のうちの様々な変数が、その変数の値を時間と共にどのように変更するかを捕えるタイムラインを、絶えず維持するステップと、
影響を受けたタイムラインにトークンを加えることによって、一貫した計画を立てて維持し、各トークンは、このタイムラインによって表される変数に影響を及ぼすアクションの様々なタイプの制約および効果を表すステップと
を含む、オンラインプランニング方法。
【請求項２】
各タイムラインは、少なくとも、前記変数とは異なる変数を表す、請求項１に記載の方法。
【請求項３】
各タイムラインは、タイムラインが表している変数の現在の値と、様々な時間において変数値に関する制約および変更を表すトークンの集合とを含む、請求項１に記載の方法。
【請求項４】
各トークンは、アクションが生じうる最早時点および最遅時点を有する、請求項１に記載の方法。
【請求項５】
前記計画は、目標集合と、変数のいかなる状態にも影響を及ぼす実際の経過時間の後に起こる全ての演算を表す一貫したタイムラインの集合とを入力として用いて形成される、請求項１に記載の方法。
【請求項６】
既知の初期状態から実行されたときに全ての所定の目標を達成するアクションのシーケンスを決定するための、タイムラインに基づく継続的なオンラインプランニングおよびスケジューリング方法であって、
前記方法は、記憶装置を備えたコンピュータ制御システム内に存在するプランナによって実行され、
影響を受けたタイムラインにトークンを加えることによって一貫した有効な計画を立てて維持するステップを含み、
前記計画は、アクションのシーケンスによって規定され、
各タイムラインは、１つの変数を表し、
各変数は、時間と共に変化する１つの値を有し、
各タイムラインは、変数の現在の値と、トークンの集合とを含み、各トークンは、変数に影響を及ぼす１つのアクションの条件または効果を表し、変数の値に影響を及ぼす計画におけるアクションによって、トークンをタイムラインに加える、方法。
【請求項７】
各トークンは、最早時点および最遅時点を有する、請求項６に記載の方法。
【請求項８】
前記プランナは、目標集合と、いかなる状態変数にも影響を及ぼす実際の経過時間の後に起こる全ての演算を表す一貫したタイムラインの集合とを入力として受け取る、請求項６に記載の方法。
【請求項９】
前記計画が有効であるのは、
前記計画が所望の目標または目標集合を達成し、タイムラインの集合によって表される前記計画が、タイムラインの終わりに最後のトークンの終了値が目標と一致する場合に所望の目標を達成する場合と、目標集合における全ての目標に関して、目標変数を表すタイムラインの最後のトークンの終了値が目標を満たすとき、目標集合が達成される場合とであり、
前記計画におけるアクションに起因する全てのトークンが、計画が探索される経過時間後に開始でき、
前記計画に起因する全てのトークンを加えることは、一貫性のなさを何ら引き起こさず、前記計画が一貫しているのは、全ての変数用のタイムラインの集合が、
一貫した値であり、同じタイムラインでの連続のトークンが一貫した変更のシーケンスを作り出す場合にタイムラインが一貫した値であり、所定のトークンの終了値が次のトークンの開始値と一致する場合と、
時間的に一貫している場合とであり、タイムラインが時間的に一貫しているのは、タイムラインに加えられる全てのトークンによって、変数の値が他のタイムラインにおいて同じ変数の値と矛盾しない場合である、請求項６に記載の方法。
【請求項１０】
既知の初期状態から実行されたときに全ての所定の目標を達成するアクションのシーケンスを決定するための、タイムラインに基づく継続的なオンラインプランニングおよびスケジューリング方法を実行するように構成されたデジタル処理装置を含む装置であって、
前記方法は、記憶装置を備えたコンピュータ制御システム内に存在するプランナによって実行され、プランナは、影響を受けたタイムラインにトークンを加えることによって一貫した有効な計画を立てて維持し、
前記計画は、アクションのシーケンスによって規定され、
各タイムラインは、１つの変数を表し、
各変数は、時間と共に変化する１つの状態を有し、
各タイムラインは、変数の現在の値と、トークンの集合とを含み、
１つのトークンは、変数に影響を及ぼすアクションを表し、複数のトークンは、変数の値に影響を及ぼす前記計画におけるアクションによって、タイムラインに加えられ、
各トークンは、前記アクションが生じうる最早時点および最遅時点を有し、
前記プランナは、目標集合と、いかなる状態変数にも影響を及ぼす実際の経過時間の後に起こる全ての演算を表す一貫したタイムラインの集合とを入力として受け取る、装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、概して、タイムラインに基づくプランニングおよびスケジューリングの方法およびシステムに関するものである。より具体的には、本開示は、所定の目標を達成するために、演算およびアクションのオンライン状態での空間プランニングに関するものである。
【背景技術】
【０００２】
プランニングは、既知の初期状態から実行されたときに全ての所定の目標を達成するアクションの順次または並列シーケンスを検出する問題に関する。例えば、通常オフラインである学究的なプランナ、および、関連のプランニングデータが既知である決定論的なプランナ、といった、様々な用途に用いられるプランニングの多くの異なる方法がある。決定論的プランニングシステムへの入力は、変数の集合、アクションの集合、初期状態、および、所望の目標条件からなる。各アクションは、アクションの条件および効果のリストによって表される。条件は、実行されるアクションに関して満たされる必要のある、変数に関する制約である。プランナは、初期状態を目標状態に結びつける論理的に一貫したアクションのシーケンス（計画）を検出する。プランナは、（１）変数がプランナの制御外でアクション（例えば、実行される別の計画からのアクション）の影響を受ける場合、（２）前記計画の検出に必要とされるプランニング時間の間、変数の値がどのように変更されるか、および、（３）実時間で到着する新しい目標、といった問題の説明をしない。これらの問題は、オンラインプランニングに関連しており、前記プランナは、時間の経過の説明をする必要がある。
【０００３】
継続的なオンラインプランニングでは、目標およびシステム（またはワールド）状態が、プランニングプロセスと重複する目標のために従来から計画された計画の実行の説明をするために、時間と共に絶えず更新される。技術的に既知の近年のオンラインプランナは、プランナを誘導するためのドメイン固有誘導技術を用い、新しい用途の適合に時間がかかる。これらの制限によって、計画の探索の誘導のために発見的な、従来のアクションに基づく一般的な目的プランニングを作成することが困難になる。
【発明の概要】
【０００４】
オンラインプランニングシステムおよび方法は、一貫したタイムラインの形式で計画が作成される環境における変数の実時間状態を表す。前記タイムラインは、様々な変数がそれらの値を時間と共にどのように変更するのかを捕えることによって、絶えず維持される。影響を受けたタイムラインにトークンを加えることによって、一貫した計画が立てられ、維持され、各トークンは、このタイムラインによって表される変数に影響を及ぼすアクションの様々な実行条件または効果を表す。
【図面の簡単な説明】
【０００５】
【図１】継続的なオンラインプランナのコンポーネント、入力、および出力の概略図である。
【図２】１つの位置から別の位置にパッケージを移動させるために用いられるステップの概略図である。
【図３】図２に示した例において修正された、いくつかの変数のタイムラインを示す。
【図４】プランナのタイムラインに基づく動作方法を示すフロー図である。
【図５】順方向状態空間プランナの計画決定方法を示すフロー図である。
【図６】有効な計画を探索する順方向状態空間プランナの３つの繰り返しにおける３つの変数を表す３つのタイムラインを示す。
【図７】半順序プランナの計画の決定方法を示すフロー図である。
【図８】有効な計画を決定する半順序プランナの３つの繰り返しにおける３つの変数を表す３つのタイムラインを示す。
【発明を実施するための形態】
【０００６】
図１は、プランナ２２内にコアプランニングコンポーネント２０を備えた継続的なオンラインプランナの全体の枠組みを概説する。コアプランニングコンポーネント２０は、問題定義１４およびオンラインメッセージ１８を入力として受信する。コアプランニングコンポーネント２０に関して、様々なプランニングアルゴリズム４０、４４、探索アルゴリズム４８、および、推論エンジン５０、５４を呼び出し得る、プランニングコンポーネント２４および再プランニングコンポーネント２８という２つの主なコンポーネントがある。コアプランニングコンポーネント２０からの出力は、制御装置６０および／またはビジュアライザ６４に送信される。制御装置が信号を送信することによって、計画が実現される。
【０００７】
プランナ２２は、図示したコンピュータ７０などのデジタル処理装置またはデジタル処理システム内で動作し、適切なソフトウェア、ファームウェア、または他の命令を実行するように、適切に具体化される。前記デジタル処理装置は、例えばオンラインメッセージ１８を受信して、制御装置６０、図示したコンピュータ７０の場合にはビジュアライザ６４、に命令／データを出力するための、適切なユーザインターフェースコンポーネントを含み、視覚出力を提供する（また、「タッチスクリーン」として具体化される場合には、適宜ユーザが入力できる）図示した表示装置７４、図示したキーボード７４、および、図示したマウス７６（または、トラックボール、トラックパッド、または、他のポインティングデバイス）を含む。図示したコンピュータ７０の代わりに、プランナシステムを、ネットワークサーバ、携帯情報端末（ＰＤＡ）、ラップトップまたはノートブックコンピュータ、ｉＰａｄ（アメリカ、カリフォルニア州、クパチーノにあるアップル社から市販されている）などのタブレット端末、といった別のデジタル処理装置によって具体化できる。ポータブルシステムでは、ワイヤレス接続が適切に用いられる。
【０００８】
プランナ２２を、評価システムを実施するためにデジタル処理装置によって実行できる命令を記憶する記憶媒体によって具体化してもよいということも、理解される。一例として、前記記憶媒体は、コンピュータ７０のハードディスク（図示せず）、または、他の磁気記憶媒体、または、光ディスクまたは他の光学的な記憶媒体、または、コンピュータ７０のランダムアクセス記憶装置（ＲＡＭ、図示せず）またはフラッシュメモリまたは他のいくつかの電子記憶媒体などであってもよい。
【０００９】
図２は、様々な考えられる変数と、現在の用途の概念が用いられる変数間の相関とを示すために、例示的なプランニングの概要を図示した環境１００を示している。環境１００では、パッケージ１１０が、Ｂ１１  １１２に位置付けられ、ＬＣ１２  １２２に位置付けられた第１クレーン１２０を用いてＢ２２  １９０に搬送される必要がある。実線の矢印線１０２は、パッケージ１１０の経路を示す。パッケージ１１０を、初めに、第１クレーン１２０を用いて位置ＬＣ１１  １３０に移動し、次に、ベルト２  １３２に移動する。次に、パッケージ１１０を、高架式車両（ＯＨＶ）１５０によってＬ０１  １５４からＬ０２  １５２に運ぶ。次に、パッケージ１１０を、ベルト３  １７０に移動し、ベルト３  １７０から、ＬＣ２１  １８２において位置付けられた第２クレーン１８０によって位置Ｂ２２  １９０に移動する。例えばＬ０２  １５２からＬ０１  １５４にＯＨＶ１５０を移動する、および、ＬＣ２１  １８２からベルト３  １７０に第２クレーンを移動する、といった、パッケージの経路によって表されない最終案に属する、実線１０４によって表されたアクションがあることに留意されたい。残りの点線１０６は、記載した経路の部分ではない利用できるアクションを表している。
【００１０】
図２に示した例において修正された、いくつかの変数用のタイムラインを、図３に示す。表された変数は、（１）パッケージの位置を表す、多値（離散）変数ｖ１＝ＬｏｃａｔｉｏｎＯｆ（Ｐａｃｋａｇｅ）２１０、（２）クレーン１がパッケージを持ち運ぶ場合を表す、２値変数ｖ２＝Ａｖａｉｌａｂｌｅ（Ｃｒａｎｅ１）２２０、（３）ベルト２における利用できるまたは空の空間を表す、連続変数ｖ３＝Ｓｐａｃｅ（Ｂｅｌｔ２）２３０である。２値変数は、離散多値変数（つまり、２つの値のみを有する変数）の特別な場合であることを理解されたい。さらに、３つのタイプの変数のみを記載したが、プランナによって管理されたタイムラインの集合は、他の変数を含んでいてもよい。
【００１１】
変数ｖ用の各タイムラインは、値
【数１】
2012150800.tif 000003
から成り、Ｄ（ｖ）は、ｖの全ての考えられる値を含むｖのバリュードメインである。ｖ用のタイムラインは、実際の経過時間ｔｃにおけるｖの現在の値と、ｖの値に影響を及ぼす今後の事象を表すトークンの集合とから成る。トークンは、前回の目標用に検出された計画におけるアクションによって追加される。ｖ１用のタイムライン＝ＬｏｃａｔｉｏｎＯｆ（Ｐａｃｋａｇｅ）２１０における、図３に示した３つのトークン２１２、２１４、２１６は、以下の順序付けられた事象を表す。（１）ｖ１の値は、現在の値ｖ１＝Ｌ１からｖ１＝Ｌ２  ２１２に変化し、（２）トークンの開始時点および終了時点によって規定された一定の持続期間２１４の値ｖ１＝Ｌ２を維持し、（３）２１６の間ｖ１＝Ｌ２からｖ１＝Ｌ３に値を変更する。ｖ２＝Ａｖａｉｌａｂｌｅ（Ｃｒａｎｅ１）２２０のタイムラインに示した２つのトークン２２２、２２４は、２２２の間に真から偽に変化し、２２４の間に偽から真へと戻って変化する２値変数の値によって表された、変化する可用性クレーン１を表す。
【００１２】
各トークンｔｋは、以下によって表される。
（ｉ）開始時点および終了時点ｓｔａｒｔ（ｔｋ）およびｅｎｄ（ｔｋ）。
（ｉｉ）開始値ｖｓ（または、開始値［ｌｂ；ｕｂ］の範囲、連続変数に関してｌｂ≦ｕｂ）。
（ｉｉｉ）トークンによって満たされる必要のある条件（例えば、＝、≠、＞、＜、≧、≦、ＮＯＮＥ）を指定する、開始条件（例えば、ｖ＝ｖｓ）。
（ｉｖ）変数値がトークン持続期間内でどのように変更されるかを指定する、変更演算（演算子、値）（例えば、ｖ＝ｖ＋５またはｖ←ｘ）。いくつかの変更演算子は、：＝、＋＝、−＝、×＝、／＝、ＣＨＡＮＧＥ、ＵＳＥ、ＭＡＩＮＴＡＩＮである。トークン終了時の変数値は、開始値および変更演算に基づいて計算される。あるいは、開始値および終了値を明瞭に表すことができ、変更演算を開始値および終了値に基づいて計算することができる。
【００１３】
トークンが、アクションに起因する条件および変更を表す場合、（１）同じアクションａの実行条件または効果、または、（２）相互に関連したアクションの条件または効果のいずれか一方を表す、トークン間の時間的関係がありうる。例えば、クレーン１を用いてＬ１からＬ２にパッケージを移動させる前に、まずパッケージを積載する必要がある。したがって、積載アクションに起因するトークンは、トークンが移動アクションによって加えられる前に終了する必要がある。したがって、トークン間には時間的順序付け関係がある。有効な計画では、タイムライン内の全てのトークン間、および、全ての変数用のタイムライン間の時間的関係は、一貫している。
【００１４】
全ての変数用のタイムラインの集合は、各タイムラインが以下の場合、一貫している。
（ｉ）値が一貫している。同じタイムラインでの連続のトークンが一貫した変更のシーケンスを作り出す、つまり、所定のトークンの終了値が、次のトークンの開始値と一致する場合、タイムラインは一貫した値である。「一致している」とは、概して、同じであることを意味する。しかし、［ｌｂ、ｕｂ］間隔によって表される連続変数に関して、一致は、２つの間隔が重複していることを意味する。所定のトークンｔｋの開始値が前回のトークンの終了値と一致しない場合、「ｔｋは支持されていない」と言う。タイムラインにおける全てのトークンが支持されるとき、このタイムラインは一貫している。
（ｉｉ）時間的に一貫している。タイムラインに加えられるトークンは、時間的一貫性のなさを引き起こさないようにする必要がある。時間的一貫性のなさの一例として、２つの時間的順序付けｔ１＜ｔ２およびｔ２＜ｔ１が両方とも同じネットワークから推論できる、ということが挙げられる。
【００１５】
有効な計画が、所望の目標または目標集合を達成する必要がある。所定の目標ｇ＝＜ｖｇ、ｘ＞（つまり、ｖｇ＝ｘ）に関して、タイムラインの終わりに、最後のトークンの終了値がｘと一致する場合、一貫したｖｇ用のタイムラインが、所望の目標を達成する。あるいは、トークンＴの終了値がｘと一致するようなトークンＴが存在する場合、タイムラインはある時点においてｇを達成するといえる。所定の目標集合Ｇに関して、全ての
【数２】
2012150800.tif 000004
に関してｖｇ用の一貫したタイムラインがｇを満たしている場合、全ての変数に関するタイムラインＴＬの集合は、ＧまたはＴＬ｜＝Ｇを満たしているといえる。
【００１６】
図４は、フロー図４００によって、一般的なプランニングアルゴリズムのタイムラインに基づく動作方法を示す。図４および続く図５および図７で用いられるいくつかの表記は、
（ｉ）所定のアクションａに関して、Ｔ（ａ）は、ａに起因するトークンの集合を意味する。
（ｉｉ）アクション集合Ａに関して、Ｔ（Ａ）は、Ａにおけるすべてのアクションに起因するトークンの集合である。
同様に、Ｔ（Ｐ）は、計画Ｐにおけるすべてのアクションに起因するトークンの集合である。
（ｉｉｉ）各時点ｔｐ（例えば、トークンの開始時点／終了時点）に関して、ｅｓｔ（ｔｐ）およびｌｓｔ（ｔｐ）は、ｔｐが生じうる最早および最遅可能時間を表している。
【００１７】
プランナは、入力４１０として一貫したタイムラインの集合ＴＬを受け取る、実際の経過時間から全ての状態変数へと生じる全ての変更、および、目標集合Ｇを表している。プランナは、（１）Ｔ（Ｐ）をＴＬに加えることは、一貫性のなさを何ら引き起こさず、（２）全ての目標を達成し、（３）実行できる（つまり、計画が検出されたときに、この計画に起因する全てのトークンが経過時間後に開始できる必要がある）ように、計画Ｐの検出を試みる（４２４）。このことを達成するために、プランナは、空の計画４１２から開始し、有効な計画が検出されるまで、見直しを絶えず生成する。プランナは、計画状態のキュー（ＳＱ）を維持することによってそのようにし、計画状態は、それぞれ潜在的に不完全な計画Ｐを含み、それに対応したタイムラインは、Ｐにおけるアクションを表すトークンを含む。ＳＱは、プランニング時間４１２において、空の計画および現在のタイムラインによって初期化される。プランナは次に、４１４において、プランニングプロセスの目的機能に従って、キューから最良の状態ｓ＝＜ＴＬｓ、Ｐｓ＞を選ぶ。４１６において、前記状態が一貫した計画Ｐｓを含む場合、計画は実行するために戻される（４２４）。そうではない場合、プランナは、４１８において、部分的計画Ｐｓのゼロ以上の見直しＰ’を生成する。前記プランナは、さらに、４２０において、各新しいＰ’に関してプランナに対応したタイムラインの集合ＴＬ’を生成する。新しく生成された計画Ｐ’とタイムラインＴＬ’とを組み合わせた新しい状態は、４２２において、状態キューＳＱに戻され、プロセスは、４１４に戻って繰り返される。
【００１８】
上述した図４の概念は、以下のアルゴリズム１に関連して展開される。上述したように、プランナは、一貫したタイムラインの集合から開始し、一貫性のなさを何ら引き起こさない計画を検出する必要がある場合、規定された目標を達成し、実行できる。したがって、初期化（ライン１〜７）後、プランナは、空の計画集合から開始し、言及された目的（ライン８〜１１）を達成するまで、計画を見直し続ける。プランナは、生成された状態の集合を維持することによって、（計画Ｐ、および、Ｐに起因するトークンを元のタイムラインに加えることに起因したタイムラインから構成されている）最良の計画を検出しようと試み、各ステップでは、プロセスは、有効な計画であることを検査するために、生成された集合から最良のものを選ぶ。したがって、生成された計画が有効な計画である場合、生成された他の計画よりも良くなければ、前記計画は戻されなくてもよい。最良の計画Ｐが探索されるとき、Ｐは、実行され（ライン１２）、その効果は、絶えず維持されるタイムライン（ライン１３）に組み込まれる。
【００１９】
様々な計画表現用に、および、変数の様々な集合および制約を操作できる様々なプランナ用に、体系的かつ局所的な探索スタイルプランニングを捕えるために、前記アルゴリズムが十分に一般的であることを理解されたい。この点について、Ｐを具体的に見直し、最良の計画であるものを決定し、プランニングプロセス中の計画の表現は、個々の形態に応じて変化でき、かつ、変化するだろう。したがって、一実施形態では、例えば、「最良の」は、他の潜在的な計画よりもより多くの所定の基準（例えば最短実行時間、最も低い全実行コスト）を満たす計画であると理解される。
【表１】
2012150800.tif 000005
【００２０】
タイムラインに関する順方向状態空間（ＦＳＳ）プランナの実現に関して、ＦＳＳプランナは、時間中に前へ移動することによって計画を探索する、ということが理解される。ＦＳＳプランナは、空の計画から開始し、これまでのところ拡大している部分的計画の終わりに、ある一定の経過時間においてアクションを徐々に加える。このプロセスは、アクションの最終シーケンスが規定の目標を満たすまで、繰り返される。したがって、プランニングプロセス中、部分的計画における全てのアクション、および、前記アクションによって取り込まれるトークンは、ある一定の経過時間で生じるように制約される。この制約の集合およびＦＳＳプランナが前へ移動する、したがって所定のタイムスタンプの前に生じるアクションを考慮しない、という事実は、計画状態表現を簡略化し、他のアルゴリズムと比較される分岐因子を低減する。
【００２１】
ＦＳＳプランナによって実行される演算を表すフロー図５００を、図５に示す。図４に記載したプランナと同様に、ＦＳＳプランナは、空の計画５１０から開始し、一貫したタイムラインの集合および目標集合を入力として受け取る。図４のプランナとは違って、ＦＳＳプランナは、探索が実際の経過時間ｔｃから始まるが、計画がその後の経過時間
【数３】
2012150800.tif 000006
において探索されるまで実行されない場合には、計画を検出するためにかかった時間を説明する必要がある。この時間遅延を説明するために、アルゴリズムは、２つの推定を用いる。つまり、全プランニング時間
【数４】
2012150800.tif 000007
の予測される量、および、１つのプランニングステップ
【数５】
2012150800.tif 000008
を行うための予測される時間である。プランニングプロセスを開始するために、プランナは、最終的に探索された計画を実行するためにプランナが開始できる予測される時間
【数６】
2012150800.tif 000009
に移動する（５１２）。プランナはまた、
【数７】
2012150800.tif 000010
の前に、全てのタイムラインにおいて全てのトークンを「フリーズ」し、前記トークンを初期のタイムラインの集合から除去する（５１４）。このステップは、トークンおよびタイムライン表現を簡略化し、さらに、それらの大きさを低減する。図４のプランナと同様に、プランナは、計画状態のキューＳＱを維持することによって最終案を体系的に探索し、計画状態は、それぞれ潜在的に不完全な計画Ｐを含み、それに対応したタイムラインは、Ｐにおけるアクションを表すトークンを含む。ＳＱは、時間ｔｐにおいて空の計画、および、簡略化したタイムラインによって初期化される（５１６）。プランナは次に、５１８において、プランニングプロセスの目的機能に従って、キューから最良の状態ｓ＝＜ＴＬｓ、Ｐｓ、ｔｓ＞を選ぶ。５２０において、前記状態が一貫した計画Ｐｓを含む場合、前記計画は実行するために戻される（５３２）。そうではない場合、プランナは、初期状態からｓへと導く現在の計画ｐｓを拡大するために、候補であるアクションを、以下の手順を用いて検出する。各アクションａのために、ＦＳＳプランナは、ａがｔａにおいて実行する場合に加えられた全ての新しいトークンがタイムラインの一貫性をなくさせない最早時間ｔａ≧ｔｃを検出するまで、現在の状態のタイムスタンプｔｓから時間内に前へ移動する。一貫した実行時間ｔａであるいずれのアクションｔａも、前記アクションは、アクション（または候補）集合に加えられる（５２２）。
【００２２】
次に、プランナは、有望なアクションの部分集合を選択し（５２４）、関連のないアクション（つまり、目標に導かないアクション）を除去する。このステップを実施するいくつかの方法がある。最も簡単な手法は、全ての適用可能なアクションを選択するか、あるいは、発見的機能にしたがって単一の最良のアクションを選択することである。候補集合における各アクションａに関して、トークンが作成され、アクションａの条件および効果を表し、計画用にタイムラインの集合に加えられる（５２６）。アクションは、前回のステップで探索された経過時間ｔａにおいて、計画に加えられ、新しく作成されたタイムラインおよび計画を含む得られた状態は、状態キュー（ＳＱ）に加えられる（５２８）。
【００２３】
次に、１つの付加的な得られた状態を生成するために、タイムスタンプは、前へ移動する（５３０）。これは、目標により近く状態タイムスタンプを前へ移動させるように導く特別のアクションである。タイムスタンプを前へ移動させるとき、この機能は、今後のアクション実行時間に関してより新しい下限を設定する。この下限とは、（１）分岐因子を制限し、（２）新しいタイムスタンプの前に、全てのトークンを除去することによってタイムラインを簡略化し、（３）トークンと今後のアクションとの間の相互作用を低減して、より短い発見的計算時間へと導くものである。次に、プロセスは、５３０から５２０へと戻る。
【００２４】
ＦＳＳアルゴリズムによって戻された計画が、いくつかの一定の経過時間と結びつけられた全てのアクションおよびトークンを有しているならば、ＦＳＳプランニングアルゴリズムは、全てのアクションが最早可能時間において始まる計画を繰り返さなくてもよい。任意のステップとして、「一定の時間」計画から、トークンとアクションとの間の時間的順序付けを有する計画へと変換する（５６２）ことが、可能である。これは、Ｄｏ，Ｍ．，＆Ｋａｍｂｈａｍｐａｔｉ，Ｓ．，「位置的に制約された基準時間計画の時間的柔軟性の改善」（自動化されたプランニングおよびスケジューリングに関する第１３回国際会議（ＩＣＡＰＳ）の議事録、２００３年）において述べられた手法を発展させることによって、達成することができる。
【００２５】
下記のアルゴリズム２において、前記概念は、疑似コードとして詳述される。アルゴリズム２では、ライン８〜２１が、（一定の時間のトークンから時間的制約を有するトークンに変換するオプションを提供するライン２０〜２１を有する）最良の第１探索の枠組みを用いた一般的なアルゴリズム１における、主なステップによく似ている、ということが分かる。図５およびアルゴリズム２の検討に応じて、後続点生成ルーチンが、以下の機能において行われる。
（ｉ）Ａｐｐｌｉｃａｂｌｅ（ライン２５〜３０）：現在の状態ｓに関して、この機能は、初期状態からｓに導く現在の計画Ｐｓを拡大するための候補であるアクションを検出する。各アクションａに関して、ＦＳＳプランナは、ａがｔａで実行する場合に加えられた全ての新しいトークンがタイムラインを一貫性なくさせない最早時間ｔａ≧ｔｃを検出するまで、現在の状態のタイムスタンプｔｓから時間内に前へ移動する。一貫した実行時間ｔａを有する任意のアクションｔａは、候補集合に加えられる。
（ｉｉ）Ａｐｐｌｙ（ライン３３〜３７）：プランナは、通常多くの適用可能だが関連のない（つまり、目標に向かって良い方向に導かない）アクションがあるので、候補アクションの部分集合を選択するだけである（ライン１７）。次に、前記プランナは、アクションの条件および効果に関するトークンを作成することによって、後続点を生成し、それらを現在のトークンに加える。さらに、前回のステップにおいて探索された経過時間ｔａにおけるアクションは、新しい状態に導く全体の計画に加えられる。
（ｉｉｉ）ＡｄｖａｎｃｅＴｉｍｅ（ライン３９〜４４）：状態タイムスタンプを前へ（つまり、目標により近く）移動させるよう導く、特別のアクションである。タイムスタンプを前へ移動させるとき、前記アクションは、基本的には、今後のアクション実行時間においてより新しい下限を設定し、したがって、（１）分岐因子を制限し、（２）タイムラインを簡略化し（つまり、新しいタイムスタンプの前に終了した全てのトークンを除去し）、（３）トークンと今後のアクションとの間の相互作用を低減して、より短い発見的計算時間に導く。
【表２】
2012150800.tif 000011
【００２６】
図２に示した例に戻り、図６は、最終案の決定に導くいくつかのステップを示す。図２における最終案を決定するためにプランナが経るステップを全て示すことは、非常に複雑である。したがって、Ｂ１１からＯＨＶへパッケージを移動させるという、より簡単な目標を仮定する。３つのみの変数用のタイムラインを示し、ｖ１、ｖ２、ｖ３は、パッケージ、クレーン１、および、ＯＨＶのそれぞれの位置を表す。ｖ１６１０、ｖ２６２０、およびｖ３６３０用のタイムラインでは、濃い長方形６４０によって表されたトークンは、前回のオンラインプランニング期間からのトークンである。現在のプランニングプロセス中に作成されたトークンは、前回のプランニング期間からのトークンと重複しないようにする必要がある。まずｔｃ＋ｔｐ６０２と同じ開始時間を設定することで、プランナは、この時刻においてクレーン１  ６１２にパッケージを積載するアクションを加えることによって開始される。このアクションを加えることにより、ｖ１６１０およびｖ２６２０用のタイムラインにおいて、２つの一定時間のトークン６５０、６５２が作成される。次に、ｔ１６０４に到達するためのＡｄｖａｎｃｅＴｉｍｅアクションを数回適用し、ＯＨＶをＬ０１  ６１４に移動させるための第２アクションを適用することで、１つのトークン６５４をｖ３６３０のタイムラインに加える。通常のアクション（例えば、Ｍｏｖｅ（Ｃｒａｎｅ；ＬＣ１１）６１６、Ｕｎｌｏａｄ（Ｐ；Ｂｅｌｔ２）６１８）およびいくつかのＡｄｖａｎｃｅＴｉｍｅアクション６０６を加えるいくつかのステップの後、パッケージをＯＨＶ６２２に積載するアクションを適用する。このとき、全てのタイムラインは、一貫しており、全ての目標が達成されるので、プランニングは終了する。
【００２７】
ここで、本開示に従ったタイムラインで実現される半順序プランナに注目する。本開示においては「半順序プランナ」という用語を用い、このような用語が文献において用いられているが、特に、この半順序プランナがタイムラインに基づいて動作するように設計された場合、著しい違いがあるということに留意されたい。ＦＳＳプランナは、所定のタイムラインの集合が全ての目標を満たすまで、一貫したタイムラインのシーケンスに沿って前へ移動することによって、計画を検出する。一方、半順序プランナは、目標からさかのぼって探索する。半順序プランナは、目標を表す特別のトークンを作成し、初めに特別の目標トークンのみを含む、支持されていないトークンの集合において全てを支持するために、アクションを計画に加えることによって十分なトークンを作成するという目的を有している。したがって、半順序プランナは、一貫性のないタイムラインの集合から開始してもよく、集合が一貫するようになるまで集合を体系的に改良してもよい。ＦＳＳプランナのようにＡｐｐｌｉｃａｂｌｅアクションを検出する代わりに、半順序プランナはＲｅｌｅｖａｎｔアクションを検出する。Ｒｅｌｅｖａｎｔアクションは、これまでのところ支持されていないトークンを支持するトークンを提供できるアクションである。
【００２８】
図７のフロー図７００は、一貫した計画を決定する際に半順序プランナによって実行されるステップを示す。半順序プランナは、一貫したタイムラインおよび目標集合を入力として受け取る。プランナは、空の計画から開始し（７１０）、目標を表す特別のトークンを、タイムラインの終わりに加える（７１４）。図４のプランナと同様に、前記プランナは、計画状態のキューＳＱを維持することによって最終案を体系的に探索し、計画状態は、それぞれ潜在的に不完全な計画Ｐを含み、それに対応したタイムラインは、Ｐにおけるアクションを表すトークンを含む。ＳＱは、時間ｔｐにおける空の計画、および、簡略化したタイムラインによって初期化される（７１６）。プランナは次に、７１８において、プランニングプロセスの目的機能に従って、キューから最良の状態ｓ＝＜ＴＬｓ、Ｐｓ＞を選ぶ。前記状態が一貫した計画Ｐｓを含む場合、前記計画は実行するために戻される。前記状態が一貫している（７２０）場合、前記計画におけるアクション間の時間的順序が設定される（７３２）。前記計画における全てのアクションの実行時間は、全てのアクションが時間的制約によって一貫しているように決定される（７３４）。最後に、前記計画が実行される（７３６）。７２０において、選ばれた状態が一貫した計画を含まない場合、プランナは、これまでのところ支持されていないトークンを支持するトークンを提供する計画において、全ての関連のアクションを識別する（７２２）。これらの関連のアクションからの有望なアクションの部分集合が選択される（７２４）。新しいアクションのそれぞれに関して、そのアクションの条件および効果に対応したトークンが、次に、タイムラインに加えられる（７２６）。新しいアクションは、次に、計画に加えられ、状態集合は、更新され（７２８）、プロセスが７１８から繰り返される。半順序プランナにおける全てのアクションおよびトークンに関して、前記アクションおよびトークンの開始／終了時間が浮動的な時点によって表されているので、所定の開始時間はない。
【００２９】
上記フロー図についてさらに説明すると、記載した半順序プランニング（ＰＯＰ）アルゴリズムに対応するアルゴリズム３の疑似コードを以下に示す。
【００３０】
ＰＯＰアルゴリズムの主要なループは、アルゴリズム１およびアルゴリズム２と同様の計画（ライン６〜１６）を検出するための探索を用いる。しかし、このＰＯＰアルゴリズムとＦＳＳアルゴリズムとの際立った違いがある。
（ｉ）アルゴリズムが（ある経過時間に関する全てのアクションを有する）所定の時間計画を検出しない場合、プランニング時間
【数８】
2012150800.tif 000012
または拡張時間
【数９】
2012150800.tif 000013
を推定する必要はない。
（ｉｉ）プランナは、目標からさかのぼって探索する。それゆえ、前記プランナは、目標を表す特別のトークンを作成し（ライン３〜５）、前記プランナの目的は、アクションを加えることによって十分なトークンを作成し、これらの目標トークン全てが最終的に支持されるようにすることである。
（ｉｉｉ）ＦＳＳアルゴリズムのようにＡｐｐｌｉｃａｂｌｅアクションを検出する代わりに、さかのぼってＲｅｌｅｖａｎｔアクションを検出する。Ｒｅｌｅｖａｎｔアクションを検出する、これまでのところ支持されていないいくつかのトークンを支持できる、いくつかのトークンを提供できる（ライン１４、２２〜２７）。
（ｉｖ）２つのレベルの分岐がある。すなわち、（１）関連があるとみなされるアクションにおいて、および、（２）新しく加えられたアクションによって取り込まれた新しいトークンをそれぞれのタイムラインにおいて加えることができる、トークン順序付けにおいて、である。
（ｖ）全てのアクションおよびトークン用の所定の開始時間はないが、前記アクションおよびトークンの開始／終了時間は、浮動的な時点によって表される。したがって、ＦＳＳアルゴリズムのように、所定の時間からフレキシブルな時間計画に変換するための任意の後処理プロセスは必要ない。
【表３】
2012150800.tif 000014
【００３１】
図８は、図６に示したＦＳＳアルゴリズムと同じアクションの集合を有する計画を検出する場合の、半順序プランナのいくつかのステップ８０２、８０４、８０６を示す。３つの変数用のタイムラインを示し、ｖ１８１０、ｖ２８２０、およびｖ３８３０は、パッケージ、クレーン１、および、ＯＨＶのそれぞれの位置を表している。ｖ１８１０、ｖ２８２０、および、ｖ３８３０のタイムラインでは、濃い長方形８４０によって表されたトークンは、前回のオンラインプランニング期間からのトークンである。プランナは、ｖ１８１０用のタイムラインの終わりに、特別のトークンｖ１＝Ｉｎ（ＯＨＶ）８１２を作成することによって開始する。次に、アクション  Ｌｏａｄ（Ｐ、ＯＨＶ）８５０は今まで支持されなかったｖ１＝Ｉｎ（ＯＨＶ）８１２を支持するトークンを加えるので、計画に加えられる。Ｌｏａｄ（Ｐ、ＯＨＶ）８５０は、２つのトークン８１４、８１６をタイムラインに加える。次のステップ８０６では、２つのトークン８１８、８２２をタイムラインに加えるアクション  Ｕｎｌｏａｄ（Ｐ、Ｂｅｌｔ２）８５２を加える。さらに、適切な時間的順序付けが、関連した時点間に加えられる。半順序プランナは、タイムラインが一貫し、最終案が探索されるまで、支持されないトークンを支持するためにアクションを加え続ける。最終案８０６では、４つの付加的なアクション８２４、８２６、８２８、８３２を生成するステップ８０４以後に、３つの付加的なアクション８５４、８５６、８５８を加えた。
【００３２】
半順序プランナおよびＦＳＳプランナは、様々な属性を含む。所定の時間、および、ＦＳＳプランナのプランニングプロセス中の各探索状態用のタイムスタンプの関連性は、以下のことをもたらす。
（ｉ）より小さい状態表現。（１）タイムスタンプを検討から外すことができる前に、任意のトークンが終了する。（２）様々なトークンが全てのトークンの所定の開始／終了時間によって示されるとき、前記トークン間のいかなる順序も記憶する必要はない。
（ｉｉ）より低い分岐因子。各適用可能なアクションは、１つの後続点を正確に生成し、ＦＳＳプランナが有効な計画を速く検出することを許可する。
【００３３】
ＰＯＰスタイルアルゴリズムの属性は、以下を含む。
（ｉ）予測される全てのプランニング時間および予測される拡張時間の推定を必要としない。
（ｉｉ）いかなる有効な解を除外しない分岐規則を許可する。
【００３４】
以上は、システム変数の値がどのように時間と共に変化するのかを捕えるタイムライン、を維持することによって動作する、タイムラインに基づくプランニング手法について記載した。プランナは、影響を受けたタイムラインにトークンを加えることによって、一貫した計画を立て、維持し、各トークンは、そのタイムラインによって表された変数に影響を及ぼす様々なタイプの演算および／または変更を表している。前記用途は、様々なトークンを介して、多くのタイプの変数およびこれらの変数に関する様々な演算を支持し、それらの全ては、様々な目標用の様々なプランニングエピソード間で共有されることができる。様々なプランニングアルゴリズムが様々な用途に関してより適切であるならば、全体の枠組みは、複数のプランニングアルゴリズムを所定のタスクに用いられるように設計される。また、様々なプランニングアルゴリズムは、プランニングまたは再プランニングタスクを解決するために、様々な探索アルゴリズムおよび制約ソルバ（例えば、時間的推論、不確実性の推論など）を呼び出すことができる。
【００３５】
開示した複数の実施形態は、上述の背景技術における論議およびそこで挙げた技術とにおいて言及した問題に対する改善された解決策の例を提供する。これらの例では、タイムラインに基づく、改善されたオンライン継続的な自動化されたプランニングの枠組みを示す。一実施形態では、既知の初期状態から実行されたときに全ての所定の目標を達成するアクションのシーケンスを決定するための、タイムラインに基づく継続的なオンラインプランニングおよびスケジューリング方法を示す。前記方法は、記憶装置を備えたコンピュータ制御システム内に存在するプランナによって実行される。前記プランナは、影響を受けたタイムラインにトークンを加えることによって、一貫した有効な計画を立てて維持する。前記計画は、アクションのシーケンスによって規定され、各タイムラインは、１つの変数を表す。全ての変数およびそれらの値は、１つの状態を表し、各タイムラインは、変数の現在の値と、時間と共に前記変数の値において制約および変更を表すトークンの集合とを含む。トークンは、変数に影響を及ぼすアクションの条件または効果を表し、トークンは、様々な変数の値に影響を及ぼす計画におけるアクションにより、タイムラインに加えられる。各トークンは、アクションが生じうる、最早時点および最遅時点を有する。前記プランナは、入力として目標集合、および、いかなる状態変数にも影響を及ぼす実際の経過時間の後に起こる全ての演算を表す一貫したタイムラインの集合を受け取る。
【図１】
2012150800.tif 000015
【図２】
2012150800.tif 000016
【図３】
2012150800.tif 000017
【図４】
2012150800.tif 000018
【図５】
2012150800.tif 000019
【図６】
2012150800.tif 000020
【図７】
2012150800.tif 000021
【図８】
2012150800.tif 000022