(57)【要約】エランドエンジン１３０を提供するための方法及び装置を開示する。エランドエンジン１３０は、エランドを構成する一組のタスクを受け取るエランド受信ロジック２１０と、一組の有効な開始状態を記述する特徴関数を生成する開始状態識別ロジック２６０と、エランドを遂行するためのツアーを生成する解決ロジック２８０、２８５とを備える。
2006520976.tif 000002
【特許請求の範囲】
【請求項１】
エランドを構成する一組のタスクを受け取るエランド受信ロジック２１０と、
一組の有効な開始状態を記述する特徴関数を生成する開始状態識別ロジック２６０と、
エランドを遂行するためのツアーを生成する解決ロジック２８０、２８５とを備えるエランドエンジン１３０。
【請求項２】
上記有効な開始状態の集合に基づいて、到達不能な状態をマスキングする枝刈りロジック２７０を更に備える請求項１記載のエランドエンジン１３０。
【請求項３】
上記ツアーを終了する最後の場所を定義する待ち合わせ設定ロジック３３０を更に備える請求項１記載のエランドエンジン１３０。
【請求項４】
ストアからリソースを得るコストを計算するコスト計算ロジック２３０を更に備える請求項１記載のエランドエンジン１３０。
【請求項５】
上記コストは、実費及びトランザクションコストを含むことを特徴とする請求項４記載のエランドエンジン１３０。
【請求項６】
収束ループから抜けるためのループブレークロジック２９０を更に備える請求項１記載のエランドエンジン１３０。
【請求項７】
上記ループブレークロジック２９０は、最大制限値を指定することによって、反復数を制限するように構成されることを特徴とする請求項６記載のエランドエンジン１３０。
【請求項８】
上記ループブレークロジック２９０は、当該エランドエンジン１３０がループに割り込みをかけることができるように構成されることを特徴とする請求項６記載のエランドエンジン１３０。
【請求項９】
多段階エランドを独立したタスクに分割するエランド分割ロジック２５０を更に備える請求項１記載のエランドエンジン１３０。
【請求項１０】
ツアーを計画するツアー計画方法において、
エランドを含む一組のタスクを受け取るステップ４１０と、
一組の有効な開始状態を記述する特徴関数を生成するステップ４４５と、
報酬を最大化する、上記タスクの少なくともサブセットを遂行するためのツアーを生成するステップ４７０、４７５とを有するツアー計画方法。
【請求項１１】
上記有効な開始状態の集合に基づいて、到達不能な状態をマスキングするステップ４６０を更に有する請求項１０記載のツアー計画方法。
【請求項１２】
上記ツアーを終了する最後の場所となる１つ以上の待ち合わせ場所に関する情報を受け取るステップ４５０、４５５を更に有する請求項１０記載のツアー計画方法。
【請求項１３】
ストアからリソースを入手するコストを計算するステップ４１５、４２０を更に有する請求項１０記載のツアー計画方法。
【請求項１４】
上記コストは、実費及びトランザクションコストを含むことを特徴とする請求項１３記載のツアー計画方法。
【請求項１５】
収束ループを特定するステップ４８０と、
収束ループから抜けるステップ４８５とを更に備える請求項１０記載のツアー計画方法。
【請求項１６】
上記収束ループから抜けるステップ４８５は、
上記収束ループの反復数が最大制限値を超えているか否かを判定するステップ４７５、４８０、４８５と、
上記収束ループの反復数が最大制限値を超えている場合、該収束ループから抜けるステップ４８５とを有することを特徴とする請求項１５記載のツアー計画方法。
【請求項１７】
上記収束ループから抜けるステップ４８５は、該収束ループに割り込みをかけるステップを有することを特徴とする請求項１５記載のツアー計画方法。
【請求項１８】
ユーザと対話し、遂行するべき一組のタスクを特定するユーザシステム１１０と、
一組の有効な開始状態を記述する特徴関数を生成する開始状態識別ロジック２６０と、エランドを遂行するためのツアーを生成する解決ロジック２８０、２８５とを含むエランドエンジン１３０とを備えるエランドシステム。
【請求項１９】
上記エランドエンジン１３０は、有効な開始状態の集合に基づいて、到達不能な状態をマスキングする枝刈りロジック２７０を備えることを特徴とする請求項１８記載のエランドシステム。
【請求項２０】
上記エランドエンジン１３０は、上記ツアーを終了する最後の場所を定義する待ち合わせ設定ロジック３３０を備えることを特徴とする請求項１８記載のエランドシステム。
【請求項２１】
上記ユーザシステム１１０は、ウェブインタフェースをサーバに提供するシステムを備えることを特徴とする請求項１８記載のエランドシステム。
【請求項２２】
エランドを構成する複数のタスクと、該タスクに関連する遂行報酬とに関する情報を受け取るエランド受信ロジック２１０と、
上記複数のタスクを複数の状態及び状態遷移に符号化するゴール符号化器２４０と
到達不能な状態及び状態遷移をマスキングする枝刈りロジック２７０と、
ツアーを生成する解決ロジック２８０、２８５とを備えるエランドエンジン１３０。
【請求項２３】
上記ツアーは、複数のタスクのサブセットを遂行することを特徴とする請求項２２記載のエランドエンジン１３０。
【請求項２４】
上記ツアーを終了する最後の場所を定義する待ち合わせ設定ロジック３３０を更に備える請求項２２記載のエランドエンジン１３０。
【請求項２５】
コスト計算ロジック２３０は、リソースの価値からリソースを入手するコストを減算して遂行報酬を算出することを特徴とする請求項２２記載のエランドエンジン１３０。
【請求項２６】
上記コストは、実費及びトランザクションコストを含むことを特徴とする請求項２５記載のエランドエンジン１３０。
【請求項２７】
エランドを受け取るエランド受信手段２１０と、
到達不能な状態を除外する第１の手段２７０と、
上記第１の手段によってマスキングされていない到達可能な状態に基づいてツアーを生成する第２の手段２８０、２８５とを備えるエランドエンジン１３０。
【請求項２８】
上記第１の手段は、複数の状態にゴールを符号化する符号化手段と、到達不能な複数の状態のサブセットをマスキングするマスキング手段とを備えることを特徴とする請求項２７記載のエランドエンジン１３０。
【請求項２９】
獲得すべき複数のリソースに関する情報を受け取るステップ４１０と、
上記複数のリソースのそれぞれを入手できる可能性があるそれぞれの場所を特定するステップ４１５と、
上記場所へのツアーを計算するステップ４６５〜４８５と、
ユーザによって定義された待ち合わせ場所でツアーを終了するステップとを有するエランド実行方法。
【請求項３０】
複数の待ち合わせ場所に関する情報を受け取るステップを更に有する請求項２９記載のエランド実行方法。
【請求項３１】
上記ツアーは、リソースのサブセットを獲得できる場所のサブセットのみを含むことを特徴とする請求項２９記載のエランド実行方法。
【請求項３２】
コンピュータシステムによって実行されて、コンピュータシステムがエランドを実行するためのツアーを構築するツアー構築処理を実行する命令のシーケンスを表すデータを保存するマシンにより読取可能な媒体において、該ツアー構築処理は、
様々な場所で入手可能な、エランドに含まれるリソースのリストを受け取る手順４１０と、
一組の有効な開始状態を記述する特徴関数を生成する手順４４５と、
報酬を最大化するように設計された、上記タスクの少なくともサブセットを遂行するツアーを生成する手順４６５〜４８５とを有するマシンにより読取可能な媒体。
【請求項３３】
上記ツアー構築処理は、有効な開始状態のセットに基づいて、到達不能な状態をマスキングする手順４６０を含むことを特徴とする請求項３２記載のマシンにより読取可能な媒体。
【請求項３４】
上記ツアー構築処理は、実費及びトランザクションコストを含む、ストアからリソースを入手するコストを計算するステップ４２０を含むことを特徴とする請求項３２記載のマシンにより読取可能な媒体。
【請求項３５】
上記ツアー構築処理は、収束ループを識別する手順４８０と、該収束ループを抜ける手順４８５とを含むことを特徴とする請求項３２記載のマシンにより読取可能な媒体。
【発明の詳細な説明】
【関連出願】
【０００１】
本発明は、２００３年３月１７日に出願された米国仮出願第６０／４５６，０３５号に対する優先順位を主張し、この特許文献は、引用により本願に援用される。
【技術分野】
【０００２】
本発明は、経路決定に関し、詳しくは、複数の場所への経路決定の最適化に関する。
【背景技術】
【０００３】
現在利用可能なエランドエンジン（errands engine）は、通常、所定の場所の組（deterministic set of points）によってポイントツーポイントの経路決定を提供する。ユーザがエランドを実行しようとする場合、従来の技術では、ユーザは、開始位置を入力し、これに続いて各場所を順に入力する必要があった。従来の計画では、エランドの順序が予め定められていると仮定している。更に、従来の手法は、ルートの失敗を処理するための事故処理計画（contingency planning）を提供しない。
【０００４】
プランニング及びスケジューリングコミュニティ（planning and scheduling community）は、アプリケーションシナリオ及びアプリケーションシナリオが存在する更に大きなクラスの問題を長期に亘って検討してきた。但し、従来の解決策は、技術を利用する所定のオペレータを必要とし（すなわち、確率的なオペレータを扱うことができない）、又は実数の効用関数（real-valued utility functions）を扱うことができず、又は最適解を提供しない。
【発明の開示】
【課題を解決するための手段】
【０００５】
エランドエンジンを提供するための方法及び装置を開示する。エランドエンジンは、エランドを構成する一組のタスクを受け取るエランド受信ロジックと、一組の有効な開始状態を記述する特徴関数を生成する開始状態識別ロジックと、エランドを遂行するためのツアーを生成する解決ロジックとを備える。
【発明を実施するための最良の形態】
【０００６】
以下、エランドエンジンのための方法及び装置について説明する。エランドエンジンは、コスト、所望のリソースを入手できる確率及びリソース入手の報酬を考慮して、一組のエランドを満足させるために、客観的な基準関数に基づき、一組の場所について最適な訪問のシーケンシングを行うように設計される。一実施形態においては、このシーケンシングは、記号−発見的探索法（Symbolic-Heuristic approach）（記号−発見的探索に組み合わされた決定理論的な記号モデル検査）を用いて実行される。
【０００７】
このエランドエンジン解決法を適用できる一般的な問題空間は、一組の場所に亘って一組のリソースの場所を特定するための最適経路を生成するタスクに関係する。ここに開示するエランドエンジンの一実施形態では、その演算において、所定のリソースが特定の場所で利用可能となる生来的な不確実性を含むとともに、場所を訪問するコスト、場所からリソースを取得するコスト及び場所からリソースを取得したときの報酬に関する性能を最適化する。エランドエンジンは、例えば、買物リストに従って一連のストアで買物を行う等の場所検知タスク（location-aware task）、例えば、ネットワーク上の一組のリソースの訪問を最適にシーケンシングする等の仮想（サイバースペース）のアプリケーション、ワークフロータスクを作成するために有用なシーケンシングの自動化、ゲームキャラクタ及びロボットの玩具のプログラミング、及びこの他の多段階タスクに好適に用いられる。
【０００８】
本発明は、所望のリソースが入手できる「リソースストア」又は場所（ここでは、単に「ストア」又は「場所」という）を取り扱い、ストア又は場所は、所望のリソースを保有していてもしていなくてもよい。トリガメカニズム（ここでは、単に「ユーザ」と呼ぶ）は、個人、機器、アプリケーションプログラム又はエランドエンジンをトリガすることができる他の如何なるエンティティであってもよい。作成されるポリシは、ユーザに対して、最も期待されるユーティリティによって、次の場所を特定するように指示する。なお、ユーティリティとは、コスト及び報酬の組合せである。コストは、移動時間又は費用に基づいて算出される。報酬は、主観的価値と、リソースの獲得を試みる金銭的コストに基づいて算出される。
【０００９】
一実施形態においては、タスクは、マルコフ決定過程（Markov decision processes：ＭＤＰ）として実現（posed）される。ＭＤＰは、タプル（Ｓ，Ａ，Ｐ，Ｒ）である。Ｓは、状態の集合である。Ａは、アクションの集合である。Ｐは、遷移確率Ｐａ：Ｓ×Ｓ→［０，１］を特定する１アクションあたり１つの遷移モデルの集合である。Ｒは、報酬Ｒａ：Ｓ→Ｒである。ここで、Ｒは、実数の集合である。目的は、Ｄ∈［０，１］を割引因子として、Ｈ∈０，１・・・∞の範囲内で、予想される割り引かれた報酬を最大にする、ポリシπ：Ｓ→Ａを発見することである。
【００１０】
Ｍ個の「リソース」の集合ＲＭ＝｛ｒ１・・・ｒＭ｝（「アイテム」とも呼ぶ）及びＬ個の「場所」（それぞれ、「ストア」とも呼ぶ）ＸＬ＝｛ｘ１・・・ｘＬ｝について検討する。推理エージェントは、宣言された場所（stated locations）のあるサブセットを連続して訪問することによって、Ｍ個のリソースを獲得しようとする。Ｓ＝ＳＬ×ＳＤ×ＳＭ×Ｓφ。「ヌル」の状態Ｓは、反則となる又はこの他の「悪い」移動を明示的にトラップするために用いられる吸収状態である。ＳＤ＝２｛ＸＬ｝は、先にエージェントが訪れた場所を追跡し、ここで２｛Ｚ｝は、ある集合Ｚの全てのサブセットを取ることによって得られたベキ集合である（すなわち、Ｚの要素の全ての組み合わせ及び空集合を含む）。ＳＭ＝２｛ＲＭ｝は、Ｍ個の所望のリソースのうち、どのリソースがエージェントによって取得されたかを追跡する。問題の定式化において、ＳＬは、現在の位置を述べる。
【００１１】
一実施形態においては、ＳＬ＝ＸＬである。したがって、この実施形態では、＃ＳＬ＝Ｌ、＃ＳＤ＝２Ｄ、＃ＳＭ＝２Ｍ、＃Ｓφ＝２である。この実施形態では、場所を表すための符号化を行う状態変数は、少なくともｌｏｇ２（Ｌ）ビット（２を底とする対数は、次の最も近い整数値に丸める必要がある。）を用いて、二値符号化を行う。所定のＭ及びＬについて、この状態空間のサイズは、Ｌ−２Ｌ＋Ｍ＋１である。
【００１２】
他の実施形態においては、Ｓを他のサブ状態ベクトルと互いに排他的にすることによって、状態空間のサイズを更に縮小する。この場合、Ｓ＝｛ＳＬ×ＳＤ×ＳＭ｝∪Ｓφである。所定のＭ及びＬについて、この状態空間のサイズは、Ｌ２Ｌ＋Ｍ＋１である。
【００１３】
他の実施形態においては、ＳＬ＝２｛ＸＬ｝とし、ｓ∈ＳＬを選択した場合、エランドエンジンは、唯一のｘｉ＝１，１≦ｉ≦Ｌを設定し、残りをゼロに設定する。これにより、ＭＤＰ符号を生成し、及びポリシを抽出するタスクが簡略化されるが、状態空間のサイズが大きくなり、この場合、＃ＳＬ＝２Ｌとなる。所定のＭ及びＬについて、この状態空間のサイズは、２２Ｌ＋Ｍ＋１である。一実施形態においては、このインプリメンテーションは、例えば、ｓＬＡＯ＊等、到達不能な状態を考慮から除外する到達可能性ステップ（reachability step）を用いる技術を含む、探索空間のサイズによる影響が少ない空間及び時間複雑性を有するＭＤＰ解決法（MDP solver）を利用する。
【００１４】
アクションＡ＝｛ｇｘ，ｙ，ｘ≠ｙ，ｘ∈ＸＬ，ｙ∈ＸＬ｝∪ｇ０と定義する。ここで、ｇｘ，ｙは、「ｘからｙまで行く」ことを表し、ｇ０は、「滞在」を表す。したがって、＃Ａ＝Ｌ（Ｌ−１）＋１となる。この表現は、リソースを入手するアクションを明示的には提供せず、エージェントが場所を訪問して、（恐らく）利用可能なリソースを獲得することを暗黙的に仮定し、この結果、タスクを表現するために必要なアクションの数が大幅に減少する。一実施形態においては、推理エージェントには、それまで有していないアイテムを獲得する毎に報酬を与える。
【００１５】
また、幾つかの場所は、待ち合わせ場所（rendezvous location）として指定される。エージェントが所望のリソースを獲得した後、待ち合わせ場所でツアーを完了すると、エージェントには、更に報酬を与える。一実施形態においては、１つ以上の所望のリソースを獲得する毎に、エージェントに報酬を与える。他の実施形態においては、エージェントが所望のリソースの全てを獲得した場合、更なる報酬をエージェントに与える。一実施形態においては、エランドエンジンは、状態変数ＳＤを介して訪問された状態を追跡する符号化を用いて、不必要な場所に再訪問した場合（すなわち、エージェントが現在必要としているリソースを有さない場所を訪問した場合）、エージェントに罰を科す。なお、エージェントのアクティブな買物リストに含まれる少なくとも１つのアイテムがそのストアにある場合、又はアクティブな買物リストが空であり、その場所が待ち合わせ場所である場合には、この罰は科されない。
【００１６】
報酬をより正確に定めるために、一実施形態においては、状態の即値（immediate value）からアクションコストを減算することによって報酬を決定する。Ｒａ（ｓ）＝Ｒｒ（ｓ）−Ｒｃ（ａ），ｓ∈＃Ｓ及びａ∈＃Ａ。ここで、Ｒｒ：Ｓ→Ｒ及びＲｃ：Ａ→Ｒ＋であり、Ｒ＋＝｛ｘ∈Ｒ，ｘ≧０｝である。一実施形態においては、場所ｘ及びｙについて、Ｒｃ（ｇｘ，ｙ）は、ｘからｙに移動するために必要な時間を表す。他の実施形態においては、Ｒｃ（ｇｘ，ｙ）は、ｘからｙへの移動に含まれる距離を表す。任意の２つの場所間の移動時間（又は距離）は、非対称であり、すなわち、ｘからｙまでの時間（又は距離）は、逆方向の時間（又は距離）より長いことも短いこともあり、包括的には、Ｒｃ（ｇｘ，ｙ）≠Ｒｃ（ｇｙ，ｘ）と表すことができる。
【００１７】
許容できる遷移をより正しく指定するために、一実施形態では、既にＳＤにおいて指定されている全ての場所への訪問を禁じるように状態遷移を変更することによって、全体的に再訪問を禁止する。他の実施形態においては、不要な再訪問を禁じ、以下の２つのケースのいずれかが成立する場合、ＳＤにおいて指定されている全ての場所への訪問を許可するように状態遷移を変更することによって、有用な再訪問を許可する。（ａ）その場所は、在庫として、利用可能性の確率が０より大きい少なくとも１つのリソースを有し、このリソースがＳＭにおいて、まだ指定されていない（すなわち、場所は、エージェントが必要とするものを所有している）。又は（ｂ）全てのアイテムが取得されており（すなわち、ＳＭは、全て「１」であり）、その場所が待ち合わせ場所である。他の実施形態として、追跡状態変数ＳＤを使用せず、如何なる場所への再訪問も無制限に許可してもよい。この実施形態は、ポリシが場所への再訪問を勧めた際、オンザフライで再計算される非定常のポリシを用いる。この実施形態は、状態空間のサイズを大幅に減少させ、この結果、ポリシを得るために必要な時間を減少させることができるが、不要な又は望ましくない再訪問を避けるために、実行時に、再計画が必要である。
【００１８】
一実施形態においては、エランドエンジンは、ゴール間の依存性を表すために、追加的データ構造を用いる。ＧをアイテムＲＭ＝｛ｒ１・・・ｒＭ｝に亘る非循環の有向グラフとする。Ｇ内の２つのノードｒｉ及びｒｊについて、ｒｉからｒｊまでのエッジは、依存性を表し、ｒｊを獲得する前に、ｒｉを獲得しなくてはならない（すなわち、ゴールｒｉは、ゴールｒｊの必須条件である）。グラフは、切断することができる。（接続されたグラフには、グラフ内のいずれのポイントからも、他の全てのポイントへのパスがある。この条件を満たさない、接続されていないグラフを切断されたグラフと呼ぶ。）切断されているアイテム（それぞれ「所望のリソース」）を表すノードは、他の如何なるゴールに対しても依存性を有していない。Ｇ内のノードｒｊは、複数の依存性を有することができ、これは、複数の他のノードからのエッジによって表される。一実施形態においては、これらの依存性は、遷移図における必須条件によって、ＭＤＰにより符号化される。この符号化は、ゴールが何らかの必須条件を有する場合、それらの必須条件は、ゴールに到達する前に満たさなければならないことを規定する。
【００１９】
一実施形態では、同様のデータ構造及び符号化を用いて、アクションの必須条件を指定することができ、すなわち、あるアクションをイネーブルにする前に他の所定のアクションが既に「実行」されていなければならないことを定めることができる。他の実施形態では、より一般的な符号化を用いて、各アクションについて、アクションをイネーブルにするために、１つ以上が成立しなければならない状態の集合を指定する。他の実施形態では、各ゴールについて、ゴールに達する前に１つ以上が成立しなければならない状態の集合を指定する符号化を用いる。この状態の集合は、決定グラフ、意志決定の木、ルックアップテーブル又は符号化ＭＤＰにおいて用いられている他の標準的な状態の表現法のいずれかによって表すことができる。
【００２０】
エランドエンジンは、特に、物理的な空間及び時間内に存在する（地理的に、位置する）場所ベースのアクティビティ又は、例えば、仮想世界（例えば、コンピュータゲーム）又は自動移動ロボットの行動の制御等、それに類似するアクティビティ又はシミュレーションに好適に用いることができる。ここまでの説明では、エランドエンジンは、場所ベースのアクティビティに適用されるが、エランドエンジンは、サイバースペース内での意志決定プロセスの実行に容易に適応化することができる。ここで、「サイバースペース」という用語は、例えば、ワールドワイドウェブ内にあるウェブサービスからの複合サービスの動的な構成等、ネットワーク化された環境を意味する。この応用例では、場所Ｌは、ウェブサービスＬを指す。この適応化は、アクションＡをアクションＡＷＷＷ＝｛ｇｙ，ｙ∈ＸＬ｝∪ｇ０に置き換えることによって実現される。ここで、ｇｙは、「ｙに行く」ことを表し、ｇ０は、「滞在」を表す。したがって、＃Ａｗｗｗ＝Ｌ＋１である。直観的に理解されるように、各場所ｙは、単一のウェブサービスを表す。なお、ウェブサービスにアクセスするコストは、「現在の場所」に依存せず、特に、システムがアクセスした直前のウェブサービスに依存しない。
【００２１】
一実施形態においては、エランドエンジンは、例えば、値反復法、ポリシ反復法、修正ポリシ反復法又は線形プログラミング法等、既知のＭＤＰ（マルコフ決定過程）解決法（この分野では、「フラットな」又は「古典的」手法とも呼ばれる。）を用いる。他の実施形態においては、エランドエンジンは、記号−発見的探索ストラテジ（ｓＬＡＯ＊）に組み合わされた記号モデル検査を用いてＭＤＰを解決する、決定理論的な回帰に基づくアルゴリズムを利用する。記号モデル検査は、問題内の構造を自動的に利用することによって値反復法に動的プログラミングを適用する効率的な手法である。また、これは、専門用語では、「構造的」手法又は「因数分解」表現を用いる手法と呼ばれる。記号ＬＡＯ＊は、これも問題内の構造を自動的に利用する発見的探索法である。これらの２つの手法を組み合わせることにより、動的計画法が発見的探索に組み合わされる。本明細書では、この手法を、「記号−発見的」探索と呼ぶ。
【００２２】
記号−発見的探索法は、エランドエンジンに以下の特徴を与えるアルゴリズムを提供する。
（ａ）表現能力、−ＭＤＰとして定式化された確率論的立案タスクを解決できる。
（ｂ）最適性−所定のＭＤＰタスクについて最適値関数を生成することができる。
（ｃ）空間的複雑性−効率的なデータ構造を介して問題構造を利用できる。
（ｄ）時間的複雑性−到達不能な状態に関する演算の無駄を回避することができる。
【００２３】
図２は、エランドエンジン１３０の一実施形態のブロック図を示している。エランド受信ロジック２１０は、ユーザからエランド定義を受け取る。一実施形態においては、ユーザは、単に、達成すべきタスクの集合のリストを渡す。他の実施形態においては、ユーザは、タスクの何らかの依存性も定義する。例えば、タスクは、ＡＴＭに行き、プレゼントを購入し、飲み物を得るといったタスクであってもよい。プレゼント及び飲み物の購入は、第１に、ＡＴＭでお金を引き出すタスクに依存している場合がある。一実施形態においては、ユーザは、これらの依存性を定義する。他の実施形態においては、後述するように、エランドエンジン１３０がこのような依存性を特定する。
【００２４】
場所フェッチロジック２２０は、要求されたリソースが入手可能なストアの場所の集合を得る。上述の具体例では、場所フェッチロジック２２０は、ＡＴＭの場所と、飲料を販売するストアの場所と、プレゼントを販売するストアの場所とに関する情報を入手する。一実施形態においては、ユーザは、プレゼントの種類に関する嗜好を定義し、すなわち、ユーザは、ユーザが腕時計を購入したいことを指示し、場所フェッチロジック２２０は、腕時計を販売するストアをフェッチする。一実施形態においては、場所フェッチロジック２２０は、場所の集合をフェッチし、例えば、１０箇所の場所をフェッチする。
【００２５】
コスト計算ロジック２３０は、各場所でリソースを獲得するコストを計算する。このコストには、アイテムの物理的なコスト（すなわち、ＡＴＭの手数料、飲み物の代金等）と、トランザクションコスト（すなわち、移動時間）が含まれる。
【００２６】
報酬計算エンジン２３５は、各タスクを達成するための主観的価値（subjective value）について計算する。これにより、一実施形態においては、エランドエンジン１３０は、制約された状況内で最も高い報酬を有するタスクのサブセットのみを実行することができる。制約条件は、時間、移動距離又はユーザによって設定される他の如何なる制約条件であってもよい。一実施形態においては、ユーザは、「必要な」タスクを特定できる。例えば、上述の具体例では、ユーザは、ＡＴＭに行くタスク及びプレゼントを購入するタスクを「必要な」タスクとし、飲み物を得るタスクを任意のタスクとすることができる。一実施形態として、システムは、初期状態で、全てのタスクが任意であると仮定してもよい。他の実施形態として、システムは、初期状態で、全てのタスクが必要であると仮定してもよい。一実施形態においては、ユーザは、自らの嗜好を初期の仮定として設定してもよい。
【００２７】
ゴール符号化器２４０は、ユーザがセットしたゴール（すなわち、タスク）を演算のために符号化する。一実施形態においては、記号−発見的探索法の利点を利用できるようにタスクを定式化する。使用される符号化は、状態変数の数を最小化し、記号モデル検査法（初期の発見を得るために用いられる）及び記号−発見的探索法（ポリシを計算するために用いられる）の両方の有益な特徴を利用する。一実施形態においては、この符号化は、非常に柔軟で広範囲のクラスに亘るタスクに適用可能な結果を提供する。なお、一実施形態では、エランドエンジンによって検討される探索空間を小さくするために、ある種の判定を外部の処理にオフロードする。
【００２８】
エランド分割ロジック２５０は、一実施形態において、エランドを２つの段階に分割する。エランド分割ロジック２５０は、それぞれが所定の長さの時間によって分離された２つの明確に区分された段階によって得られるリソースをサポートする。
【００２９】
例えば、１時間でフィルムの現像を行うサービスを提供する写真店に写真のフィルムのロールを預ける場合、ユーザは、まず写真店を訪問し、フィルムを預けた後、フィルムを受け取るまでに少なくとも１時間待たなければならない。一実施形態においては、エランドエンジンは、特定のアクティビティについて、所望の時間の単位（この具体例では、フィルムを預けた時刻から１時間）の経過を追跡する他の状態変数を用い、そして、フィルムが返却されたとき、エランドエンジンに「報酬を与える」。報酬は、（１）ユーザが写真店を訪問し、（２）１時間が経過し、（３）ユーザが写真店を再び訪問するといった、イベントの集合に対して与えられる。エランドエンジンは、ストアを出て、割り当てられた時間内に他のタスクを試みるより、そこで待つ方がよいと判断してもよい。例えば、ユーザがサービスステーションに自動車を預け、１５分程度かかると予想されるオイル交換を依頼するとする。エランドエンジン１３０は、リスト内の他のエランドを遂行するコストを計算し、そのための正味コスト（報酬から移動コストを減算した値）が１５分待つためのコストを超えないと判断することもある。
【００３０】
一実施形態においては、このような各２段階タスクについて、基底にあるＭＤＰには、１つの更なる多変量状態変数Ｔτ∈｛ｔ１・・・ｔτ｝が補われる。ここで、Ｔτは、２段階タスクの第１の段階が開始されてから経過した時間的段階の数のブール表現であり、Ｔτ∈｛（０，０・・・０，０），（０，０・・・０，１），（０，０・・・  １，０），（０，０・・・１，１），（１，１・・・１，０），（１，１・・・  １，１）である。
【００３１】
この実施形態では、Ｔτ＝｛１，１・・・１｝（すなわち、全てが１である）場合、２段階タスクの第２の段階が実行される。この実施形態では、この「ストップウォッチ」変数の各「チック」（すなわち、時間的ステップ）は、例えば１５分等の時間の単位に対応している。この実施形態では、特定のアクションが費やした時間に基づいて、あらゆるアクションがこのストップウォッチ変数を更新し、インクリメントすることができる。Ｔτが全て１に設定されると、この設定は、２段階タスクの第２の段階が完了するまで維持される。この実施形態では、ストップウォッチ変数は、２τ−１個の時間的ステップを表すことができる。他の実施形態においては、以下のように、ストップウォッチ変数に単項符号化（unary encoding）を用いる。Ｔτ∈｛（０，０・・・０，０），（０，０・・・０，１），（０，０・・・１，１），（０，１・・・１，１），（１，１・・・１，１）この実施形態では、ストップウォッチ変数は、最大τ個の時間的ステップを表すことができる。他の実施形態においては、何らかの整数Ｋ及びτ＝Ｋについて、Ｔτ∈｛（０，０・・・０，０），（０，０・・・０，１），（０，０・・・１，０），（０，１・・・０，０），（１，０・・・０，０）｝のように、「ｏｎｅ−ｏｆ−Ｋ」符号化を用いる。この実施形態では、ストップウォッチ変数は、最大τ個の時間的ステップを表すことができる。これらの更なる実施形態のそれぞれにおいては、２段階タスクの第２の段階は、最上位ビット（すなわち、ここに記した順序で一番左のビット）が１に設定されたときに実行される。一旦、ストップウォッチ変数が最も高い値に達すると、この値は、２段階タスクの第２の段階が完了するまで維持される。
【００３２】
一実施形態においては、アクションセットに更に「待機」アクションを追加し、この「待機」アクションでは、エージェントは、同じ場所に残り、ストップウォッチ変数を１チック分インクリメントする（すなわち、時間の一単位を費やす。）のみである。
【００３３】
開始状態識別ロジック２６０は、記号−発見的探索法において用いられる「初期状態」を定義する。一実施形態では、開始状態識別ロジック２６０は、タスク記述符号化における規則性を利用して、有効な開始状態の全てを特定し、そして、有効な開始状態の集合を記述する特徴関数によって特定される複合的な「初期状態」を生成する。これによりＭＤＰ解決法は、到達可能性構造（例えば、ｓＬＡＯ＊）を利用して、単一の開始状態ではなく、全ての有効な開始状態に有効なポリシを算出することができる。他の実施形態においては、開始状態識別ロジック２６０は、単一の有効な開始状態を特定する。これによりＭＤＰ解決法は、（ｓＬＡＯ＊等の）到達可能性構造を利用して、所定の開始状態から到達可能な状態のみの値及びポリシを算出することができる。
【００３４】
待ち合わせロジック２６５は、エランドエンジン１３０によって設計されたツアーが終了する場所を特定する。一実施形態においては、ツアーは、如何なる場所でも終了することができる。一実施形態においては、エランドエンジン１３０は、ストアのサブセットを「待ち合わせ場所」として指定する。待ち合わせ場所は、エランドエンジン１３０がツアーを終わらせることができる場所である。待ち合わせ場所は、リソースを有している必要はない。
【００３５】
例えば、２人の人が一緒に買物に行き、そして、それぞれが個々のエランドのために、しばらく別れることを決めたとする。そして、彼らは、彼らが自分達の個々のタスクを終えた後に、再び会うことを決めたとする。彼らは、公園（彼らの各買物リストのいずれに関するリソースも含まない。）又は喫茶店（いずれかの買物リストに登録されているリソースを含んでいる場合がある。）等を待ち合わせ場所として指定する。また、一実施形態においては、エランドエンジン１３０は、２つ以上の待ち合わせ場所を指定してもよい。これにより、一方の人がそのタスクを完了し、彼らが選択した待ち合わせ場所で待ち、そして、他方の人に、自分がどこで待っているかを電話で知らせることができる。このように、待ち合わせ場所が定義されている場合、ツアーは、待ち合わせ場所で終わる必要がある。ツアーを実際に待ち合わせで終わらせるか否かは、そうすることによる報酬と、待ち合わせ場所に移動するためのコストとに基づいて決めてもよい。待ち合わせ場所に移動するための最大のコストより、報酬を大きく設定することによって、ツアーを必ず待ち合わせで終わらせることができる。
【００３６】
枝刈りロジック２７０は、全ての到達不能な状態を除外する。ＭＰＤ解決法では、状態遷移図（アクションを実行することによって、他の状態からある状態にどのように到達できるかを規定する）が、通常の動作では、ある状態への到達を禁止する場合があり、この場合、この状態には到達し得ない。換言すればこのような状態は、特定の開始状態の集合からは、「到達不能」である。開始状態識別ロジック２６０によって特定される開始状態及び待ち合わせロジック２６５によって特定される終了状態に基づく「到達不能な状態」は、マスクされる。これは、エランドエンジン１３０がこれらの到達不能な状態に関する演算を行わないことを意味する。これにより、値図（value diagram）及びポリシ図（policy diagram）の複雑性を大幅に低減することができる。数十万個のノードを有するマスキングされていない値図面について、数万個のノードをマスキングすることにより、複雑性を約９０％も低減できることが知られている。この低減の度合いは、もちろん、問題及び問題の到達可能性構造による。
【００３７】
図５Ａ及び図５Ｂは、枝刈りされた（マスキングされた）ポリシ図とマスキングされていないポリシ図の違いを示している。これらの図からわかるように、枝刈りされたポリシ図は、到達不能な状態のポリシを含まないので、マスキングされていないポリシ図に比べて複雑性が低い。
【００３８】
（記号ＬＡＯ＊等の）到達可能性を利用するＭＤＰ解決法の１つの副次的な利点は、これにより得られる評価関数が、不要な状態の言及を除外し、これにより得られるポリシが、全ての到達不能な状態について「ヌル」アクションを生成するという点である。図５Ａ及び図５Ｂは、ＳＰＵＤＤの網羅的なブラインド探索法と、（この場合、ＬＡＯ＊によって生成される）「マスキングされた」ポリシとの間の違いを示している。
【００３９】
図５Ａは、４つの場所ＳＶ（ａｔ０，ａｔ１，ａｔ２，ａｔ３）及び単一のリソースＳＶ（駐車：parked）を用いて、エランドタスクの単純化されたバージョンに関するマスキングされていないポリシを示している。（ポリシが場所を再訪問することを避けることができるＳＶの追跡は、図面を明瞭にするために省略している）。内部の（すなわち、終端ではない）ノードは、ＳＶを表す。ＳＶが真である場合、実線を辿り、この他の場合、破線を辿る。一実施形態においては、タスクは、マルコフ決定過程（Markov decision processes：ＭＤＰ）として実現（posed）される。リーフ（すなわち、終端）ノードは、アクションを表す。例えば、ｐａｒｋｅｄ  ＡＮＤ  ａｔ０のアクションは（他の全てのＳＶが偽であるとすると）、滞在（stay）である。ａｔ３のアクションは（他の全てのＳＶが偽であるとすると）、ｇｏ＿３ｔｏ０である。２つ以上の場所変数が真に設定された全てのノードは、到達不能であり、すなわち、これらのノードは、アクセスされることはない。例えば、ａｔ０  ＡＮＤ  ａｔ１のアクションは（他の全てのＳＶが偽であるとすると）、ｇｏ＿１ｔｏ２である。これは、（マスキングされてない）値反復アルゴリズムによって生成されたポリシは、到達不能な状態についてのポリシを含むことを示している。
【００４０】
図５Ｂは、図５Ａと同様のタスクについて、マスキングされたポリシを示している。マスキングされたポリシでは、到達不能な状態をマスキングしている。図５Ｂに示すように、一実施形態では、全ての到達不能な状態は、「ｎｏｎｅ」のラベルが付された単一の終端ノードにトラップされる。
【００４１】
例えば、１１個の場所と、６個のリソースと、全部で２９個の状態変数とがある状況では、一実施形態において符号化される状態の総数は、５３６，８７０，９１２個を超える。しかしながら、到達可能な状態の数は、２，８８３，５８４個にすぎない。これは、エランドエンジンが如何なる時刻においても唯一の場所にしか存在できず、この符号化の下では、唯一の場所状態変数のみしか１に設定されず、１１の場所があるための、場所状態変数における過疎性に起因する。したがって、状態の０．５４％だけが到達可能である。網羅的（ブラインド）検索を用いた周知の値反復法では、実際の使用時には決して到達する筈がない９９．４６％の状態の評価にサイクルを費やす。
【００４２】
図２に示すように、一実施形態では、システムは、最適解だけではなく、近似解を提供する。一実施形態においては、エランドエンジン１３０は、最適解ロジック２８５と、近似解ロジック２８０とを備える。
【００４３】
近似解ロジック２８０は、「終端対（pair terminal）」ＡＤＤのデータ構造をｓＬＡＯ＊メソッドに統合する。これにより、正確な値を繰り返す値反復法を近似値反復法に置換するオプションが提供される。これにより、近似解を用いるいことが適切であるシナリオにおいて、処理が高速化され、この結果、近似値反復法の利点と、記号−発見的探索法及び関連する到達不能な状態のマスキングの利点とを同時に享受することができる。他の実施形態においては、近似的な線形プログラミング法を用いて、近似解を得る。
【００４４】
最適解ロジック２８５は、反復的最適解を計算する。一実施形態においては、ループブレークロジック２９０を設ける。応用領域における記号−発見的探索法をプロファイリングすることにより、収束ループに過度の時間が費やされていたことが見出された。ループブレークロジック２９０は、最適解ロジック２８５が以下の２つの手法で、ループに費やされる時間を短縮することができるようにするためのタスクに依存するパラメータである。（ａ）最大制限値を指定することによって、反復数を制限する。及び／又は（ｂ）ループブレークロジック２９０がループに割り込みをかけられるようにする。最適解ロジック２８５は、必要に応じて、演算を再開できる。一実施形態においては、最適解ロジック２８５は、ポリシのランタイムが経過した後、初期状態を、ポリシを実行している間に遭遇した直近の状態に設定することによって演算を再開できる。
【００４５】
図２に示すエランドエンジン１３０は、「ストア」（リソースのレポジトリ）及び「リソース」（ストアで内に見出される）及び買物リスト（また、エランドリストとも呼ばれる）を利用する。エランドエンジン１３０は、買物リストが空になるまで、ストアを訪問してリソースを収集することによって「ツアー」を作成する。このツアーは、ユーザに提示される。
【００４６】
図３は、ユーザシステム１１０の一実施形態のブロック図である。エランド送信ロジックは、エランドエンジン１３０にエランドを送る。一実施形態においては、ユーザは、一組のゴールを定義する。一実施形態においては、ユーザは、ゴールの間の相対的優先順位又は依存性を定義してもよい。例えば、ユーザは、以下のような項目を入力できる。
１．ＡＴＭでお金を引き出す。
２．フォンデュ・フレッズ（Fondue Fred's）で昼食をとる。
２．息子のためのプレゼントを購入する。先にＡＴＭでお金を引き出す必要あり。
３．サンフランシスコを観光する。
【００４７】
上のリストは、優先順位（順序）並びに依存性を示している。一実施形態では、依存性計算ロジック３２０は、ユーザに対し、何らかの依存性を特定するように入力を促してもよい。例えば、システムは、上のリストを受け取り、昼食をとる前にＡＴＭに行く必要があるか否かをユーザに問い合わせてもよい。
【００４８】
待ち合わせ設定ロジック３３０により、ユーザは、１つ以上の目的地を待ち合わせ場所として指定できる。一実施形態においては、特定された場所のみが待ち合わせ場所として指定される。したがって、上述の具体例では、ＡＴＭ、プレゼントの購入場所及び観光する場所は、明確に特定されていないので、待ち合わせ場所に指定できるのは、フォンデュ・フレッズだけである。他の実施形態として、いずれの場所も待ち合わせ場所として指定できるようにしてもよい。
【００４９】
一実施形態においては、ウェブインタフェースを用いる。この場合、一実施形態では、インタフェースは、図３Ｂに示すような情報を表示する。図３Ｂに示すように、各エランド３５０の隣には、依存性３６０のリストが表示されている。一実施形態においては、依存性３６０は、プルダウンメニュー３７０として表示される。一実施形態においては、可能な全ての組合せが表示される。他の実施形態においては、優先順位が高いもの（リストの上位にある）のみが示される。エランドが待ち合わせ３８０であるか否かに関する指定も選択される。このように、ユーザは、単に、ツアーの作成に十分なデータをシステムに提供する。
【００５０】
他の実施形態においては、知識に基づくシステムは、所定のユーザプロファイル及び領域知識に基づいて、ユーザ及び所定の状況に適切な典型的な依存性を決定する。一実施形態においては、ユーザがユーザプロファイルを提供する。他の実施形態においては、ユーザを経時的に観察することによってユーザプロファイルを作成する。他の実施形態においては、同様のユーザの母集団を観察することによって、ユーザプロファイルを得る。一実施形態においては、領域知識は、専門の設計者によって提供される。他の実施形態においては、Ｃｙｃ等の常識の知識ベースによって領域知識を提供する。他の実施形態においては、領域知識は、領域及びその領域に関する演繹的な規則について記述するオントロジによって提供される。他の実施形態においては、領域知識は、同様のユーザの母集団を観察することによって提供される。
【００５１】
図３Ａに示すように、ユーザのシステムは、エランドエンジン１３０によって算出されたツアーを受け取るツアー受信ロジック３４０を備える。
【００５２】
図４は、エランドエンジン１３０を用いる処理の一実施形態のフローチャートである。この処理は、ステップ４０５から開始される。ステップ４１０においては、エランドのリストを受け取る。一実施形態では、エランドのリストは、異なるストアから入手される少なくとも２つのリソースを含んでいる。
【００５３】
ステップ４１５では、各ストアの場所を特定する。一実施形態では、ストアの場所は、公共のソースから得られる。例えば、ストアがモール内の物理的なストアである場合、モールマップ（インターネットで一般に公開されている）を用いて各ストアの場所を特定することができる。他の実施形態においては、ストアの場所は、例えば、モール所有者又はモール所有者を代表するマーケティング代理店等、プライベートなソースとの契約に基づいて入手される。他の実施形態においては、サードパーティのデータベンダからストアの場所を入手してもよい。
【００５４】
ステップ４２０では、各ストアのリソースコストを特定する。上述のように、リソースコストは、アイテム自体の実費と共に、トランザクションコスト（移動時間、駐車コスト等）を含む。一実施形態においては、アイテムの実費は、未知であってもよい。このような場合、トランザクションコストだけを評価する。一実施形態においては、例えば、インターネット（例えば、広告）等の公共のソースから、ストアの在庫に関する情報を得る。他の実施形態においては、サードパーティのデータベンダからストアの在庫に関する情報を得る。他の実施形態においては、協力するユーザの共同体からストアの在庫に関する情報を得る。
【００５５】
ステップ４２５において、処理は、エランドのリスト内に幾つかの２段階タスクがあるか否かを判定する。２段階タスクは、通常、時間又は場所が離れた２つの個別の段階を必要とする。ステップ４３０において、２段階タスクがあると判定された場合、それらを独立したタスクに分解する。なお、この機能及びゴール間の必要条件への依存性を規定する能力により、３つ以上のステップを有する多段階タスクを実行することができる。
【００５６】
ステップ４３５において、各タスク／アイテムについて報酬を特定する。一実施形態においては、ユーザは、１つ以上のエランドについて、優先順位／報酬レベルを指定できる。最も簡単な具体例では、ユーザは、「必ず実行する」エランドを指定でき、他のエランドを「実行が望ましい」又は「時間があれば、実行してもよい」といった優先順位に置くことができる。一実施形態においては、数値によって優先順位付けを行ってもよい。標準のタスクプランニングと同様に、ユーザは、各エランドに優先順位を割り当てることができる。優先順位が高い程、タスクの遂行の報酬も高くなる。
【００５７】
ステップ４４５では、開始状態を特定する。一実施形態においては、全ての可能な開始状態を指定し、全ての開始状態を特定する単一の式を生成する。そして、エランドエンジンは、この単一の式を用いて、全ての可能な開始状態についてのツアーを算出することができる。他の実施形態においては、全ての「有効な」開始状態を指定する。ここで「有効」とは、空のショッピングカートから開始し、まだ、如何なる場所も訪問していないことを意味することができる。そして、全ての有効な開始状態を特定する単一の式を生成する。他の実施形態においては、単一の開始状態を指定し、その開始状態を特定する単一の式を生成する。
【００５８】
処理は、ステップ４５０において、ユーザが待ち合わせ場所を指定しているか否かを判定する。待ち合わせ場所は、ツアーを終了できるポイントである。ユーザが待ち合わせ場所を指定している場合、ステップ４５５において、ツアーの可能な終了点を判定する。この他の場合、一実施形態では、処理は、ツアーを如何なるポイントで終了してもよいと仮定する。なお、待ち合わせ場所は、「ストア」ではなく、「リソース」を有していないポイントであってもよい。例えば、買物ツアーの場合、待ち合わせ場所は、自宅であってもよい。
【００５９】
ステップ４６０において、エランドリストに基づいて生成された報酬図の枝刈りを行う。生成された「標準的」報酬図は、全ての可能なパスをプロットすることを試み、すなわち、網羅的である。ここで、既知の開始状態からは到達できない多くの状態がある。例えば、ユーザが同時に複数の場所に存在する状態がある。これは、明らかに不可能である。そこで、枝刈りによって、到達不能なパスを演算から除外する。一実施形態においては、この枝刈り又はマスキングは、これらのパスの値を計算しないことを意味する。これにより、評価フェーズにおける処理時間を大幅に短縮することができる。
【００６０】
処理は、ステップ４６５において、近似解が許容可能であるか否かを判定する。システムは、最適解を提供できる。但し、近似解を算出する方が時間を消費しないで済む。近似解が許容可能な場合、処理は、ステップ４７０に進む。そして、ステップ４７０において、近似解を算出する。上述したように、一実施形態では、近似解は、ｓＬＡＯ＊メソッドと共に「終端対（pair terminal）」ＡＤＤを用いる。他の実施形態においては、線形近似プログラミングを用いて近似解を得る。
【００６１】
そして、処理は、ステップ４９０に進みツアー情報をユーザに送る。一実施形態においては、ツアーは、ユーザの携帯装置からリモートのコンピュータシステムによって算出される。この具体例では、ユーザは、ツアーに関する情報を携帯装置にダウンロードして利用する。他の実施形態においては、このステップをスキップしてもよい。そして、処理は、ステップ４９５で終了する。
【００６２】
ステップ４６５において、近似解を許容できないと判定された場合、処理は、ステップ４７５に進む。ステップ４７５では、反復的な最適解を算出する。一実施形態においては、ｓＬＡＯ＊メソッドを用いて最適解を算出する。他の実施形態においては、従来の値反復法を用いて最適解を算出する。他の実施形態においては、従来のポリシ反復法を用いて最適解を算出する。他の実施形態においては、修正ポリシ反復法を用いて最適解を算出する。他の実施形態においては、ＳＰＵＤＤ等の構造化された値反復法を用いて最適解を算出する。他の実施形態においては、到達可能性マスキング法に組み合わせて、ＳＰＵＤＤ等の構造化された値反復法を用いて、最初に初期状態から到達可能性解析を実行し、次に到達可能な状態の集合のみに構造化された値反復法を適用することによって最適解を算出する。他の実施形態においては、到達可能性マスキング法に組み合わせて、従来の値反復法を用いて、最初に初期状態から到達可能性解析を実行し、次に到達可能な状態の集合のみに値反復法を適用することによって最適解を算出する。
【００６３】
処理は、ステップ４８０において、収束ループロックがあるか否かを判定する。一実施形態においては、検査により、収束ループに過度の時間が費やされていたことが見出された。そこで、収束ループが検出された場合、処理は、ステップ４８５に進む。ステップ４８５では、推理エージェントが以下の２つの手法で、ループに費やす時間を短縮できるようにするためのタスクに依存するパラメータを用いる。（ａ）最大制限値を指定することによって、反復数を制限する。及び（ｂ）推理エージェントがループに割り込みをかけられるようにする。推理エージェントは、必要であれば、演算を再開できる。そして、処理は、ステップ４７５に戻る。他の実施形態においては、最適解ロジック２８５は、ポリシのランタイムが経過した後、初期状態を、ポリシを実行している間に遭遇した直近の状態に設定することによって演算を再開できる。これにより、ＭＤＰ解決法は、現在の現実世界の状態に対応する状態から到達可能な状態の探検のみに演算リソースを集中させることができる。収束ループが存在せず、最適解の算出に成功した場合、処理は、ステップ４９０に進む。
【００６４】
図６は、本発明を適用できるコンピュータシステムの一構成例を示している。なお、他の代替的なシステムとして、様々なシステムアーキテクチャを用いてもよいことは当業者にとって明らかである。
【００６５】
図６に示すデータ処理システムは、情報を通信するためのバス又は他の内部の通信手段６１５と、このバス６１５に接続された、情報を処理するためのプロセッサ６１０とを備える。更に、システムは、バス６１５に接続され、プロセッサ６１０によって実行される命令及び情報を保存するランダムアクセスメモリ（ＲＡＭ）又は他の揮発性記憶装置（メモリと呼ばれる）６５０を備える。プロセッサ６１０による命令の実行の間、メインメモリ６５０に一時的な変数又は他の中間的情報を保存してもよい。更に、このシステムは、バス６１５に接続され、静的情報及びプロセッサ６１０の命令を保存する読取専用メモリ（ＲＯＭ）及び／又は読取専用メモリ６２０と、例えば、磁気ディスク又は光ディスク及び対応するディスクドライブ等のデータ蓄積装置６２５とを備える。データ蓄積装置６２５は、バス６１５に接続され、情報及び命令を保存する。
【００６６】
更に、このシステムには、バス６６５を介してバス６１５に接続され、コンピュータユーザに情報を表示するための、例えば、陰極線管（ＣＲＴ）又は液晶ディスプレイ（ＬＣＤ）等の表示装置６７０を接続してもよい。また、プロセッサ６１０に情報及びコマンド選択結果を供給するために、英数字及び他のキーを含む英数字入力装置６７５をバス６６５を介して、バス６１５に接続してもよい。バス６６５を介してバス６１５に接続される更なるユーザ入力装置としては、マウス、トラックボール、スタイラス、カーソル方向キー等のカーソル制御デバイス６８０があり、これにより、プロセッサ６１０に方向情報及びコマンド選択を供給し、表示装置６７０に表示されているカーソルの動きを制御してもよい。
【００６７】
コンピュータシステム６００に任意に接続することができる他の装置としては、ネットワークを介して分散システムの他のノードにアクセスするための通信装置６９０がある。通信装置６９０は、例えば、イーサネット（登録商標）、トークンリング、インターネット又はワイドエリアネットワークに接続するために用いられる多くの市販のネットワーク周辺機器のいずれであってもよい。通信装置６９０は、更にヌルモデム接続、無線接続メカニズム又はコンピュータシステム６００と外の世界とを接続する他の如何なるメカニズムであってもよい。なお、図６に示すこのシステムの要素及び関連するハードウェアいずれか又は全ては、本発明の様々な実施形態で用いることができる。
【００６８】
なお、特定のインプリメンテーションに基づく様々な目的のために、如何なる構成のシステムを用いてもよいことは当業者にとって明らかである。本発明を実現する制御ロジック又はソフトウェアは、メインメモリ６５０、データ蓄積装置６２５、又はプロセッサ６１０にローカルに又はリモートからアクセス可能な他のストレージメディアのいずれに保存してもよい。
【００６９】
本明細書に開示したシステム、方法及び処理は、メインメモリ６５０又は読出専用メモリ６２０に保存され、プロセッサ６１０によって実行されるソフトウェアとして実現できることは当業者には明らかである。また、制御ロジック又はソフトウェアは、データ蓄積装置６２５に読み込み可能であり、本明細書に示す方法及び開示に基づいてプロセッサ６１０を動作させるコンピュータにより読取可能なプログラムコードを有するコンピュータにより読取可能な媒体を含む製品内に格納してもよい。
【００７０】
また、上述したコンピュータ構成機器のサブセットを含むハンドヘルド型又は携帯型機器によって本発明を実現してもよい。例えば、ハンドヘルド型機器は、バス６１５、プロセッサ６１０、メインメモリ６５０及び／又はデータ蓄積装置６２５のみから構成してもよい。また、本発明は、上述したコンピュータ構成機器のサブセットを含む専用機器として実現してもよい。例えば、この専用機器は、プロセッサ６１０、データ蓄積装置６２５、バス６１５、メインメモリ６５０、及び例えば、小型のタッチスクリーン等、ユーザが機器と簡易に通信するための初歩的な通信メカニズムのみから構成してもよい。一般に機器は、専用性が高い程、その機器を動作させるための要素は少なくて済む。幾つかの機器では、ユーザとの通信は、タッチセンサ式の画面又は同様のメカニズムを介して行ってもよい。
【００７１】
様々な目的のために、特定のインプリメンテーションに基づき、如何なる構成のシステムを用いてもよいことは当業者には明らかである。本発明を実現する制御ロジック又はソフトウェアは、プロセッサ６１０がローカルで又はリモートからアクセス可能な如何なるマシンにより読取可能な媒体に保存してもよい。マシンによって読取可能な媒体は、マシン（例えば、コンピュータ）によって読取可能な形式で情報を保存又は送信する如何なるメカニズムであってもよい。マシンにより読取可能な媒体は、例えば、読取専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、磁気ディスク記録媒体、光記録媒体、フラッシュメモリ装置、電気的、光学的、音響的又は他の形式で伝播する信号（例えば、搬送波、赤外線信号、デジタル信号等）のいずれであってもよい。
【００７２】
本発明のエランドエンジンは、様々な用途に応用できる。本発明のエランドエンジンを適用できる幾つかの具体例を以下に示す。
（ａ）ウェブサービス構成：一組のサービスから複合サービスを自動的に作成する。
（ｂ）旅行計画：観光地の様々な場所を訪れる旅行者のために、興味レベル及び旅行の嗜好（歩き、公共交通機関、ドライブ）等に基づき、個人用の旅程を作成する。
（ｃ）買物エージェント：ショッピングモールを訪れる買物客のために、その買物リスト及び他の嗜好、例えば、店舗の嗜好及び希望の価格帯に基づき旅程を作成する。
（ｄ）博物館巡回計画：訪問者の嗜好及び移動特性（行動的な単一の歩行者、ゆっくり散歩するカップル、車椅子利用者等）に基づき、博物館内の展示を回るためのポリシを提案する。
（ｅ）デバイス調整：マスタデバイスによって使用される近接ネットワーク内の所定の一組のサーバントデバイスについて、あるタスクを実行する目的のために、サーバントデバイスを最適に訪れ、デバイスを配列するためのポリシをマスタデバイスに提供する。例えば、ユーザは、デジタルカメラによってスナップショットを撮影し、デジタルカメラは、画像データをＰＤＡに渡し、ＰＤＡは、画像処理によってピクチャをクロッピングし、画像内の人物の赤目を修正し、後に回収するために、近くの商用プリンタに１つのハードコピーを送信し、携帯電話を介して１つのコピーをユーザの配偶者に送り、そして、ハードコピーを回収するために、ＧＰＳ装置に対し、先の商業プリンタにユーザを案内するように指示する。
（ｆ）個人情報アシスタント：広域ネットワーク（例えば、インターネット又はワールドワイドウェブ等）に存在する一組のリソースへの訪問を最適に配列する。
（ｇ）ワークフロータスク：アルゴリズムは、例えば、ドキュメントワークフローの作成又は必要なレビュー、承認及び署名を得るためにドキュメントを送る必要がある共同プロジェクトにおける連携に有用な自動シーケンス処理を行う。
（ｈ）ゲームキャラクタのプログラミング
（ｉ）ロボット玩具のプログラミング
以上、特定の例示的な実施形態に基づいて本発明を説明した。但し、添付の請求の範囲に定義されている本発明のより広い精神及び範囲から逸脱することなく、上述の実施形態を様々に修正及び変更できることは明らかである。したがって、ここに示した実施形態及び図面は、例示的なものであり、本発明を制限するものではない。
【図面の簡単な説明】
【００７３】
【図１】エランドエンジンを用いることができるネットワークの一実施形態のブロック図である。
【図２】本発明に基づくエランドエンジンの一実施形態のブロック図である。
【図３Ａ】本発明に基づくエランドエンジンのためのユーザシステムの一実施形態のブロック図である。
【図３Ｂ】一組のエランドを定義するための例示的なユーザインタフェースを示す図である。
【図４】エランドエンジンを用いてルートを生成する一実施形態のフローチャートである。
【図５Ａ】枝刈りされていないポリシ図である。
【図５Ｂ】本発明に基づいて枝刈りされたポリシ図である。
【図６】本発明を実現できるコンピュータシステムのブロック図である。
【図１】
2006520976.tif 000003
【図２】
2006520976.tif 000004
【図３Ａ】
2006520976.tif 000005
【図３Ｂ】
2006520976.tif 000006
【図４】
2006520976.tif 000007
【図５Ａ】
2006520976.tif 000008
【図５Ｂ】
2006520976.tif 000009
【図６】
2006520976.tif 000010