(57)【要約】【課題】人間形ロボットのような自律機械が屋内タスクを遂行するシステムと方法を提供する。【解決手段】人間が、知識データベースに対してプランを入力する。知識データベース内の情報は、タスクステップを識別し、タスクステップを動作と客体のペアとして特徴付けるために事前処理される。この知識データベースからプランデータベースが創作される。区別的手法は、このプランデータベースから１つの既存プランを選択するために、階層的集積クラスタリングを用いる。生成的手法は、第一順番のマルコフ連鎖を用いることによりプランデータベースから新たなプランを公式化する、また操作環境についての情報を考慮することができる。人間による実験と評価が両手法の効果を確認している。【選択図】図２
2009500746.tif 000002
【特許請求の範囲】
【請求項１】
自律機械が制約された環境下においてタスクを遂行するステップを識別する識別方法であって、
前記識別方法は、
分散キャプチャ技術により収集された、前記タスクを遂行するための１つ又は複数のプランを含むデータを受け取り、
前記タスクを遂行するためのタスクステップのシーケンスを前記データから抽出することを含むこと
を特徴とする識別方法。
【請求項２】
前記自律機械は人間形ロボットであることを特徴とする請求項１に記載の識別方法。
【請求項３】
前記データを受け取る手順は、複数のユーザ又は複数の場所からのデータを受け取ることをさらに含むこと
を特徴とする請求項１に記載の識別方法。
【請求項４】
前記分散キャプチャ技術は、タスクを特定する検索に対する回答としてプランを提供することを人間に対して促すことを含むこと
を特徴とする請求項１に記載の識別方法。
【請求項５】
前記タスクステップのシーケンスから動作と客体のペアを抽出する手順をさらに含み、
前記動作と客体のペアは、前記タスクステップのシーケンスのタスクステップに対応していること
を特徴とする請求項１に記載の識別方法。
【請求項６】
前記識別方法は、
前記動作と客体のペアの客体が存在する場合に前記動作と客体のペアの動作が発生する確率を特定し、環境の制約を処理する条件付確率分布を、前記動作と客体のペア毎に、決定することをさらに含むこと
を特徴とする請求項５に記載の識別方法。
【請求項７】
前記条件付確率分布は、前記動作と客体のペア毎に、（式１）によって決定され
【数１】
2009500746.tif 000013
2009500746.tif 000014
【請求項８】
前記識別方法は、
前記動作と客体のペア毎に、前記タスクを含むプランモデルと、前記動作と客体のペアと、前記条件付確率分布を取得し、
前記プランモデルを複数取得し、
前記プランモデルのペア毎の関連性の度合いを示す１組の類似度を決定し、
前記プランモデルのペアのうち、その類似度が最初のプランの類似度を超過するものをプランのペア同士グルーピングし、
それぞれの階層的なプランクラスタ内のプランのペアの平均類似度が、最初のプランのペアの平均類似度を超過するように、前記プランのペアを階層的なプランクラスタに分類し、
プランモデルの最大数に対応する前記階層的なプランクラスタの１つからプランモデルをランダム選択することをさらに含むこと
を特徴とする請求項６に記載の識別方法。
【請求項９】
前記類似度は、（式２）によって決定され
【数２】
2009500746.tif 000015
2009500746.tif 000016
【請求項１０】
前記識別方法は、
前記タスクステップのシーケンスから、それぞれの動作と客体のペアが前記タスクステップのシーケンスのタスクステップに対応している複数の動作と客体のペアを抽出し、
前記複数の動作と客体のペアから、
１つの開始ノード、動作と客体のペアに対応する１つ又は複数のタスクステップ、及び１つの終了ノードを含む複数のノードと、
ノード同士を連結する複数のリンクを有する前記タスクモデルを合成することをさらに含むこと、
を特徴とする請求項５に記載の識別方法。
【請求項１１】
前記タスクモデルは、
先行して発生した１つのタスクステップに関連して次の各タスクステップの発生の起こりやすさを示す複数の遷移確率をさらに有すること
を特徴とする請求項１０に記載の識別方法。
【請求項１２】
前記識別方法は、
１つのタスクステップのノードに対応するタスクステップのシーケンスを有するプランを生成する手順をさらに含み、
前記シーケンスは、（式３）によって決定され、
【数３】
2009500746.tif 000017
2009500746.tif 000018
【請求項１３】
前記遷移確率は、タスクステップに対応する客体の屋内環境における存在に基づいて修正されること
を特徴とする請求項１１に記載の識別方法。
【請求項１４】
前記識別方法は、
１つのタスクステップのノードに対応するタスクステップのシーケンスを有するプランを生成する手順をさらに含み、
前記シーケンスは、（式４）によって決定され、
【数４】
2009500746.tif 000019
2009500746.tif 000020
【請求項１５】
タスクステップ候補のうち最良の選択肢が複数ある場合には、ランダムにプランの選択を行う手順をさらに含むこと
を特徴とする請求項１４に記載の識別方法。
【請求項１６】
タスクステップ候補のうち最良の選択肢が複数ある場合には、長さが最短のプランを選択する手順をさらに含むこと
を特徴とする請求項１４に記載の識別方法。
【請求項１７】
自律機械が制約された環境下においてタスクを遂行するステップを識別する識別装置であって、
分散キャプチャ技術によって収集され、前記タスクを遂行するための１つ又は複数のプランを含むデータを受け付けるように作成された入力部と、
前記タスクを遂行するためのタスクステップのシーケンスを、前記データから自動的に抽出するように作成された制御部を有すること
を特徴とする識別装置。
【請求項１８】
自律機械が制約された環境下においてタスクを遂行するステップを識別する識別装置であって、
分散キャプチャ技術によって収集され、前記タスクを遂行するための１つ又は複数のプランを含むデータを受け付ける手段と、
前記タスクを遂行するためのタスクステップのシーケンスを、前記データから自動的に抽出する手段を有すること
を特徴とする識別装置。
【請求項１９】
自律機械が制約された環境下においてタスクを遂行する方法をコンピュータの処理部に実装させるコンピュータ用のプログラムを保持したコンピュータに読取可能な媒体を含むコンピュータプログラム製品であって、
前記方法は、
分散キャプチャ技術によって収集され、前記タスクを遂行するための１つ又は複数のプランを含むデータを受け付け、
前記タスクを遂行するためのタスクステップのシーケンスを、前記データから自動的に抽出する手段を有すること
を特徴とするコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、２００５年７月８日に出願された“Building Plans for Household Tasks from Distributed Knowledge”と題する米国特許仮出願第６０／６９７，８４３号、及び２００５年１２月６日に出願された“Building Plans for Household Tasks from Distributed Knowledge”と題する米国特許出願第１１／２９６，０２０号を基礎とする優先権を米国特許法第１１９条（ｅ）に基づき主張し、これらの出願はその全体がここに引用される。
【０００２】
本出願は、２００６年３月１６日に出願された“Commonsense Reasoning About Task Instructions”と題する米国特許出願第１１／３７８，０６３号と関連しており、当該出願はその全体がここに引用される。
【０００３】
本出願は、２００５年１月２８日に出願された“Responding to Situations Using Knowledge Representation and Inference”と題する米国特許出願第１１／０４６，３４３号と関連しており、当該出願はその全体がここに引用される。
【０００４】
本発明は、自律機械の分野に関し、特に、可動性ロボットが制約環境下においてタスクを遂行することを可能にすることに関する。
【背景技術】
【０００５】
例えば人間の特徴を有するロボットのような人間形ロボットは、自律機械技術を適用して家庭やオフィスの人間を支援するうえで重要なステップを踏んできた。子供の世話をする、質問や電話に応答する等の無数の日常的活動に対して潜在的な適用可能性がある。屋内用人間形ロボットは、コーヒーを作る、衣服を洗濯する、こぼした汚れを掃除する等の一般的な家庭内の雑事を遂行するものと考えられている。
更なる適用例として、年配者や障害者の支援も含み得る。人間形ロボットは、ロボットのユーザの知覚された要望を満足させるようなタスクを遂行することになると考えられている。視聴覚認識技術を通じて、ロボットはそのユーザを名前で認識し、挨拶をすることができる。さらに、ロボットは、人間との相互作用や他の方法を通じて学習することもできる。これらの必要を満たすために、このようなロボットは必要な知識を有さなければならない。
【０００６】
特に、屋内のタスクを遂行するために、人間形ロボットのような自律システムは、複数のステップを有するプランを必要とする。ロボットはこのようなプランを動的に引き出す、すなわちタスクがこれから遂行されるときに屋内環境の現状を考慮に入れることができることが望ましい。常識的な知識に基づいたプランを引き出すことも望ましい。例えば、家庭やオフィスでの通常のタスクを遂行するためのステップは、分散キャプチャ技術を用いて非熟練のボランティアから収集し得る。
【０００７】
人間活動は、様々なレベルで分析されてきている。最も基本的なレベルでは、動作の遂行は、知覚モータマッピングのモータ反応スキームによって紹介されている。この詳細は、非特許文献１に記載されており、ここにその全体を引用する。
最も抽象的なレベルでは、手書き文字や記憶組織パケット（ＭＰＯ）の考えが、レストランへ行く又は手術を受けに医者を訪れる等のよく学習された活動の組織化を説明するために提案されてきている。この詳細は、非特許文献２及び非特許文献３に記載されており、ここにその全体を引用する。ＭＯＰが作用するとき、一般的にはステップは１つずつ実行されるが、時には、複数のステップが他の活動と組み合わされることもあり得る。例えば、医者の待合室で待ちながら読書することもできる。
【０００８】
このような両極端の間に、朝食を作る、歯を磨く、服を着る、のような実地のよく学習された活動の幅が存在する。この中間レベルにおいて、クーパーとシャーリスは、動作図式の階層的ネットワーク組織内での競合作用に基づくルーチンのためのステップ選択の計量モデルを紹介している。彼らのシーケンシャルなステップ選択のための活性化モデルは、ノーマンとシャーリスの競合スケジュール理論に基づいている。この詳細は、非特許文献４及び非特許文献５に記載されており、ここにその全体を引用する。
クーパーとシャーリスのモデルは、コーヒーを準備するルーチンについて実証された。通常の機能のもとでは、このモデルは、一杯のコーヒーが飲めるようになるまでの単純行動のシーケンス（スプーンを取り、砂糖入れにスプーンを浸す、等）を発生させる。
【０００９】
対照的に、人工知能の働きは、合目的的探索行動の分類に属する。別々のプランの知識を用いて目的点に到達する試みがなされ、成功したシーケンスが選択される。この詳細は、非特許文献６に記載されており、ここにその全体を引用する。
【００１０】
ある従来型アプローチは、専門的システムを使用して、タスクをアルゴリズム的に遂行するためにステップを符号化している。キー成分となるのは、骨の折れる手作業プロセスを使用することによる専門的人間知識のキャプチャであった。この詳細は、非特許文献７に記載されており、ここにその全体を引用する。このアプローチの短所は、人間が学習するもの全てが専門家によって教えられるわけではない、ということである。靴紐を結ぶというような最も日常的な活動は、非専門家を観測することによって、また、非専門家と相互に関係することによって学習される。
【００１１】
ラスマッセンらによれば、このようなルーチンにおける人間の行動は合目的的であり、１揃いの証明済の規則によって制御されるものである。タスクステップのシーケンスは、典型的には経験に基づいて引き出され、他人のノウハウ又は“クックブック”シーケンスから伝達される。この詳細は、非特許文献８に記載されている。
【００１２】
常識的知識の１つの源として、ワールドワイドなウェブ（Ｗｅｂ）がある。例えば、ｅＨｏｗ.ｃｏｍのようなウェブサイトは、活動を遂行するステップを列挙している。インテル社は、行動モデルを構築するために確率行動ツールキット（ＰＲＯＡＣＴ）と呼ばれるシステムを開発した。これらのモデルは、行動の対象となる客体を観測することによって行動を自動的に特定した。これらのモデルはまた、所与の活動に対する様々な語の関連性を、ウェブから発見した。例えば、“コップ”という語は、“お茶を作る”という行動に密接に関連している。なぜならば、ウェブページでは、“コップ”は、お茶を作る際に頻繁に現れるからである。この詳細は、非特許文献９及び非特許文献１０に記載されており、ここにそれらの全体を引用する。
【００１３】
タスクのためのプランを構築するための公開情報としてウェブを使用することは非常に興味を引く。しかし、抽出された知識は高度の相違や“ノイズ”、例えば、無関係又は誤った情報を提示し、文書は非常に大きいことがある。代替物として、オープンマインドインドア常識（ＯＭＩＣＳ）データベースのような分散情報がある。このデータベースをコンパイルしていると、ボランティアは、家庭のタスクに魅力を感じ、家庭のタスクを遂行するためのステップを作成してほしいと依頼される。この詳細は、非特許文献１１に記載されている。しかし、このアプローチを以ってさえ、意味的な情報は、提供された情報から抽出されなければならない。
【非特許文献１】R.A.Schmidt,A Schema Theory of Discrete Motor Skill Learning,Psychological Review,82(4):225-260,1975
【非特許文献２】R.C.Schank and R.Abelson,Scripts,Plans,Goals and Understanding,Lawrence Erlbaum Associates Ltd.,Hove,UK,1977
【非特許文献３】R.C.Schank,Dynamic Memory:A Theory of Reminding and Learning in Computers and People,Cambridge University Press,Cambridge,1982
【非特許文献４】Richard Cooper and Tim Shallice,Contention Scheduling and the Control of Routine Activities,Cognitive NeuroPsychology,17(4):297-338,2000
【非特許文献５】D.Norman and T.Shallice,Attention to Action:Willed and Automatic Control of Behavior,pages 1-18,Plenum Press,New York,1980
【非特許文献６】Daniel S.Weld,Recent Advances in AI Planning,AI Magazine,20(2):93-123,Summer 1999
【非特許文献７】D.A.Waterman,A Guide to Expert Systems,Addison Weseley,1986
【非特許文献８】Jens Rasmussen,Skills,Rules and Knowledge:Signals,Signs, and Symbols, and Other Distinctions in Human Performance Models,IEEE Transactions on Systems,Man and Cybernetics,SMC-13(3):257-266,May/June 1983
【非特許文献９】Matthai Philipose,Kenneth P.Fishkin,Mike Perkowitz,Donald Patterson,and Dirk Haehnel,The Probabilistic Activity Toolkit:Towards Enabling Activity-Aware Computer Interfaces,Technical Report IRS-TR-03-013,Intrel Research Laboratories,November 2003
【非特許文献１０】Mike Perkowitz, Matthai Philipose, Kenneth Fishkin,and Donald J.Patterson,Mining Modeks of Human Activities from the Web,Proceedings of the 13th Conference on World Wide Web,pages 573-582,ACM Press,2004
【非特許文献１１】R.Gupta and M.Kochenderfer,Common Sense Data Acquisition for Indoor Mobile Robots,Nineteenth National Conference on Artificial Intelligence(AAAI-04),July25-29 2004
【非特許文献１２】Eric Brill,A Simple Rule-based Part-of-speech Tagger,Proceedings of ANLP-92,3rdConference on Applied Natural Language Processing,pages152-155,Trento,IT,1992
【非特許文献１３】Gelad Salton,ed.,Automatic Text Processing: The Transformation, Analysis,and Retrieval of Information by Computer,Addison Wesley,1989
【発明の開示】
【発明が解決しようとする課題】
【００１４】
前記から、人間形ロボットのような自律機械が屋内環境のような制約された環境でタスクを遂行できるようにするための、分散知識からプランを構築する実用的なシステム及び方法が必要であることがわかる。
【課題を解決するための手段】
【００１５】
屋内環境のような制約のある環境でタスクを遂行するためのプランを、人間形ロボットのような自律機械に備えるための方法と装置を提供することによって、本発明はこれらの要求を満たす。本発明の一面によれば、このようなタスクを遂行するプランは、知識データベースから自動的に抽出され又は生成される。このデータベース内の知識は、分散知識キャプチャ技術を使用して、人間によって作成される。
ワールドワイドなウェブは、分散知識キャプチャ及び移転媒体として選択的に使用され、非常に多くの人々からの収集が実際に可能である。メリットとして、知識データベースは、“常識”すなわちそれを作成する主体のコンセンサスを具現化している。
【００１６】
知識データベースは１つ又は複数のタスクを有し、各タスクは、１つ又は複数のプランを有し、各プランは、複数の命令からなる１つのシーケンスを有する。ある実施形態によれば、本発明は、過半数のコンセンサスを示すプランとして、知識データベースのなかの複数のプランから“最善”のプランを選択する。この実施形態では、階層集積的なクラスタリングが類似のプランを集めて更に大きなグループとする。これを区別的アプローチという。
【００１７】
他の実施形態によれば、本発明は、知識データベースの複数のプランから１つの新たなプランを生成する、すなわち引き出す。これを生成アプローチという。それぞれのプランは、第一順序のマルコフ連鎖としてモデル化されており、そこでは、各ステップが直前のステップに依存し、隠れた状態はない。本発明のある実施形態によれば、コーヒーメーカのような特別な器具が屋内環境に存在するか否かのような環境制約を、生成されたプランは考慮に入れる。このことにより、人間形ロボットは、ロボットの知覚又はこのような制約情報に基づいた最適のタスクプランをリアルタイムで生成できる。
【００１８】
タスクステップを公式化するために、動作と客体のペアが、知識データベースから抽出される。例えば、“衣服を洗濯する”というタスクについて、１つのタスクステップに対応する動作と客体のペアは、「収集する、衣服」であり得る。それに続くステップは「に向かう、洗濯機」であり得る。さらに、所与のタスクの動作と客体の間の関係は知識データベースから引き出される。例えば、衣服が存在することを条件とする、衣服を収集するという条件付確率が引き出される。１つの特定のタスクが、多くの、潜在的には数百のプランを有し、さらに各プランが複数のステップからなる１つのシーケンスを有し得る。１つのプランが有するステップの数は任意であるが、望ましくは５から７である。
【００１９】
ある実施形態によれば、１つの特定のタスクに対応するプラン候補のステップ候補はグラフで表示することができる。そのグラフには、ノードとリンクが含まれる。ノードは、動作と客体のペア、すなわちステップを示し、リンクは、ステップ間の遷移を示す。ある所与のノード／ステップが、複数のプランに共有されていてもよい。グラフは、共通の“開始”ノードで始まり、この“開始”ノードから、タスクの最初のステップ候補全てに対してリンクが接続している。知識データベースから決定されるように、対応する遷移の相対的な起こりやすさ、すなわち確率が、各リンクに対応している。連続するノードとリンク毎に、このトポロジーは繰り返される。
【発明の効果】
【００２０】
この図示方法の効果は、１つのタスクに対応する全てのプラン候補を引き出す、又は生成するための効果的な根拠を提供することである。プランの更新が可能になれば、この図示モデルは適宜修正され得る。部分的最適化又は全体的最適化のような、多様な戦略に基づくグラフから、プランは決定され得る。ある実施形態によれば、２つのプラン候補間の接続の際には、最短シーケンスを有するプランが選択される。他の実施形態によれば、環境制約が考慮される。例えば、現状の環境内で洗濯機が利用可能である場合、ドライクリーニングを使用するプランよりは、洗濯機を使用するプランが好まれることとなる。
【００２１】
本明細書に記載された特徴や効果は限定的なものではなく、別途記載する図面、明細書及び特許請求の範囲に接した当業者には、追加的な特徴や効果が明らかになる。さらに、本明細書に使用される用語は、主として読み易さ及び教育目的のために選択されており、本発明の主旨を限定するために選択されているのではない。
【００２２】
後記する本発明の詳細な説明、別添の特許請求の範囲を、添付の図面と参照することによって、本発明が他の効果や特徴を有していることがより容易に明らかになる。
【発明を実施するための最良の形態】
【００２３】
以降、別添の図に例示される本発明のいくつかの実施形態の詳細を説明する。類似の参照番号が複数の図面で使用される場合は類似の機能を示している。各図は、単に例示目的で本発明の実施形態を描写している。当業者であれば、本発明の原理から逸脱することなく以降に例示する構成や方法の代替的実施形態を実施することが可能であることを後記する明細書の記載から容易に知り得るであろう。
【００２４】
図１は、本発明のある実施形態に係るシステムである。
コンピュータシステム１１０は、入力装置１１２、主記憶装置１１４、補助記憶装置１１８、中央制御装置１２２、及び出力装置１２４を備える。代替的な実施形態においては、画像処理装置１２０が、中央制御装置１２２の一部分として存在してもよいし、状況を所定のデジタルフォーマットに変換されたデジタル画像として知覚する独立装置として存在してもよい。
同様に、主記憶装置１１４は、スタンドアローンの記憶デバイス（例えば、ＲＡＭチップ等）であってもよいし、中央制御装置１２２に付属するメモリーチップ（例えば、キャッシュメモリー）であってもよい。補助記憶装置１１８は、ハードディスク、ＤＶＤ−Ｒ／ＲＷ、ＣＤ−Ｒ／ＲＷ又はＲＡＭのような任意の大容量ストレージである。同様にコンピュータシステム１１０は、サーバ、パーソナルコンピュータのようなスタンドアローンのシステムであってよい。代替例として、コンピュータシステム１１０は、例えば、視覚システムを備えるロボットのようなより大きなシステムの一部であってもよい。
【００２５】
当該実施形態によれば、コンピュータシステム１１０は、データベース１４０から常識データのような必要情報を受け付ける入力装置１１２を有する。入力装置１１２は、デジタルカメラ１３０ｂ（例えば、ロボットの目）、ビデオシステム１３０ａ（例えば、閉回路テレビジョン）、画像センサのような画像装置１３０から、直接デジタル画像を受け付けてもかまわない。代替的に、入力装置１１２は、データベース、他の視覚システム、インターネットサーバのようなネットワークシステムから情報を受け付けるインタフェースであってもよい。
このインタフェースは、ＵＳＢ、ＲＳ−２３２シリアルポート、イーサネットカードのような有線インタフェースであってもよいし、ブルートウース、ＷｉＦｉ、ＩＥＥＥ８０２.１１のような無線プロトコルを使用した無線通信デバイスのような無線インタフェースモジュールであってもよい。画像処理装置１２０は、中央処理装置１２２が処理可能なフォーマットにデジタル画像を変換するために、入力装置１１２を介して受け付けたデジタルイメージの事前処理用に使用されてもよい。
【００２６】
必要な情報は、主記憶装置１１４にロードされ、中央制御装置１２２による処理を受ける。中央処理装置１１２は、本発明に係る１つ又は複数の方法（例えば、タスクを遂行するためのプランを生成する等）を遂行する一連の命令を読み込み実行する。主記憶装置１１４は、タスクを遂行するためのプランを生成する命令モジュール１１６を含んでもよい。
【００２７】
主記憶装置１２２は、ネットワーク１５０ａ、表示装置１５０ｂ、データベース１５０ｃのような外部装置１５０に対して、出力装置１２４を介して情報を出力する。入力装置１１２と同様に、出力装置１２４は、有線であってもよいし、無線であってもよい。出力装置１２４は、ストレージドライブインタフェース（例えば磁気又は光学ドライバ）、ネットワークインターフェース装置（例えば、イーサネットインタフェースカード、無線インタフェースカード）、ディスプレイドライバ（例えばグラフィックカード）あるいは情報又は決定された応答を出力する任意の装置であってもよい。
【００２８】
図２には、本発明のある実施形態に係る、プランデータベースの創作方法２００が示されている。方法２００は、例えば、前記の命令モジュール１１６を実行する中央制御装置１２２によって実装される。知識データベース２０６は、まずオフラインで集められ、前記のデータベース１４０に対応する。定義された各タスクについて、人手によってデータベース２０６に常識プランが集められる。それぞれの常識プランは、ステップのシーケンスを有している。知識データベース２０６は、コーヒーを作る、床を掃除する、衣服を洗濯するなどの数百に及ぶタスク毎にプランを有する。知識データベース２０６から得たプランの一例を以下に示す。
タスク：
衣服を洗濯する
ステップ：
衣服を集める
洗濯機へ向かう
洗濯機に衣服を入れる
洗剤を衣服に加える
洗濯機の蓋を閉める
洗濯機を動かす
【００２９】
本発明のある実施形態は、知識データベース２０６のなかの所与のタスクごとに１組のプランを使用し、プランデータベース２２６を構築する。プランデータベース２２６は、例えば前記補助記憶装置１１８又はデータベース１５０ｃの中に存在してもよい。後記するように、ある特定のプランがプランデータベース２２６から後ほど抽出され又は生成される。
２１２において、興味のあるタスクが選択される。
２１６において、知識データベース２０６内の情報から当該選択されたタスクに対応する１組の動作と客体のペアが抽出される。ある実施形態においては、タスクステップは、初めに、ブリルのパートオブスピーチ（ＰＯＳ）タグによって解析される。この詳細は、非特許文献１２に記載されている。この方法は、最初の動詞を動作として識別する。動詞の後に前置詞が続く場合は、前置詞は動詞と一緒にして扱われる。最終的に、最初の名詞句が動作の客体として識別される。前記プラン例の解析結果を以下に示す。
タスク：
衣服を洗濯する
ステップのための動作と客体のペア：
集める、衣服
へ向かう、洗濯機
置く、衣服
加える、洗剤
閉める、蓋
動かす、洗濯機
【００３０】
ある実施形態によれば、２２０において、所与のタスクの、各客体及び対応する動作と客体のペアについて、以下に記す条件付確率分布を決定する。
【００３１】
【数５】
2009500746.tif 000003
【００３２】
2009500746.tif 000004
一旦前記決定がなされると、タスクに関連付けて、動作と客体のペア及びその条件付確率が、２２４においてプランデータベース２２６に記憶される。
【００３３】
単純化されたプランの決定方法は、プランデータベース２２６内のプランの組からランダムな選択をする。このアプローチは、後記する更に複雑なアプローチとの比較における基本型であり、以降、第１の手法と呼ぶ。
【００３４】
（区別的アプローチ）
本発明のある実施形態によれば、貢献者のコンセンサスとなっているプランが、プランデータベース２２６から選択される。これを区別的アプローチ、すなわち第２の手法と呼ぶ。この手法は、図３に示される階層集積的クラスタリング方法に基づいている。この手法は、プランデータベース２２６に存在する類似のプランをグルーピングして、さらに類似のグループをより上位のクラスタに分類することを含む。この詳細は、非特許文献１３に記載されており、ここにその全体を引用する。
この実施形態によれば、プランデータベース２２６は、前記のように、補助記憶装置１１８の中に存在してもよいし、データベース１４０に対応してもよい。方法３００は、例えば、命令モジュール１１６を実行する中央制御装置１１４により実装され、クラスタリング方法３００の結果は、出力装置１２４を介してネットワーク１５０に渡されて、適宜、蓄積又は転送される。
【００３５】
2009500746.tif 000005
【００３６】
【数６】
2009500746.tif 000006
【００３７】
2009500746.tif 000007
３１２において、（式２）に従い最小の類似度が特定され、その特定によって、３１６において、プランの組み合わせがグループ化される。３２０において、このようなグループは、特定されたクラス数を得るために使用される平均グループ類似度に基づいて階層的に分類される。言い換えれば、階層化されたクラスタの所望の数を得るために、２つのレベルのクラスタスクリングが実行される。
【００３８】
このようなクラスタは、タスクを遂行するための、区別されるべき手法やカテゴリに対応していることが経験的に知られている。例えば、コーヒーを作るタスクの場合、さまざまなクラスタが、コーヒーメーカ、インスタントコーヒー及びエスプレッソマシーンの使用に対応する。過半数のボランティアは、コーヒーメーカを使用してコーヒーを作るプランに貢献したので、このカテゴリは最大のクラスタになっていた。
屋内タスクのプランは、通常は５種類以下のカテゴリに属する。従って、平均グループ類似度は、各タスクの５種類以下の階層的クラスタ、すなわちプランのカテゴリを得るように設定されるのが好ましい。階層的クラスタ形成の後、３２４において、貢献されたプランの最大数に相当する階層的クラスタから、特定のプランがランダムに選択される。
【００３９】
（生成的アプローチ）
本発明の他の実施形態によれば、プランデータベース２２６から新たなプランが生成され得る。第一に、第一順番のマルコフ連鎖を使用してタスク毎にタスクモデルが構築される。
マルコフ連鎖は、ランダムな複数の変数のシーケンスである。マルコフ連鎖の適用は、プランを構成するステップがもともと連続的な性質を有するので有効である。ある実施形態によれば、各プランは第一順番のマルコフ連鎖としてモデル化されており、そこでは、各ステップは、直前のステップに依存しており、隠れた状態は存在しない。
図４に、“衣服を洗濯する”タスクの典型的タスクモデル４００が示されている。タスクモデル４００の図においては、状態又はステップとも呼ばれるノードがタスクステップを示している。図中のリンクは、連続するステップ間の遷移を示している。タスクのプランは、全てが共通の開始ステップ４１０で開始し、共通の終了ステップ４９０で終了する。１つのプランは、ステップとリンクが交互に連続する特定のシーケンスによって示される。衣服を洗濯するプランの例が、破線の境界４１２の内側に示されている。方法４００は、例えば、前記の命令モジュール１１６を実行する中央制御装置１２２によって実装される。生成されたプランは、出力装置１２４を介してネットワーク１５０に渡され、適宜蓄積又は転送される。
【００４０】
複数のステップ４２０は、ステップ４１０に続き、グラフ４００から引き出され得る全てのプランの最初のステップ候補を含む。例えば、ステップ４２０ｂは、例示されるプランの、（開始ステップの直後の）最初のステップである。各リンクは、遷移確率、すなわち直前ステップが発生した場合に発生し得る次のステップ候補の相関確率に対応している。例えば、タスクモデル４００に示されるプランの数が１００であり、“衣服を集める”がそのうちの３０のプランの最初のステップである場合、ステップ４２０ｂの確率は、０．３となる。モデル４００における他のリンクの確率も同様に定義される。
【００４１】
完全なタスクモデルは、所与のタスクに対する全てのステップ候補を、このように簡潔に示している。さらに、後記するように、タスクモデルは、新たなプランを生成する基礎となる。タスクモデルは、ステップとリンクを追加する又は変更することによって容易に拡張され又は更新され得る。そしてタスク毎に新たなプランの確率を調節することも可能になっている。
【００４２】
（部分的最適化に基づく生成的プラン）
本発明のある実施形態によれば、確率が最大である次のステップを選択することにより、対応するタスクモデルからタスクに対する新たなプランが生成され得る。例えば、タスクモデル４００では、状態４２０ｂは、複数の状態４２０の中から選択される。
時点ｔにおける状態は（式３）によって決定される。
【００４３】
【数７】
2009500746.tif 000008
【００４４】
2009500746.tif 000009
このような生成的プランは、局所的最適を有していると言われる。以降、このアプローチを第３の手法と呼ぶ。
【００４５】
一旦ステップ候補が選択されると、タスクモデル中のそのステップに到達するリンクのうち、直前の状態からのリンク以外のリンクは廃棄される。これは、望まれない循環、すなわち図中のループが形成されるのを回避するためである。
１つのプランのなかで、同一のステップが２度以上発生することも一般的にあり得ることに留意すべきである。例えば、“衣服を洗濯する”タスクにおいて、“蓋を開ける”ステップは、洗濯機に衣服を入れる前にも発生し得るし、選択が終了した後にも発生し得る。以下に、この実施形態に係る“衣服を洗濯する”タスクの生成的プランの一例を示す。各ステップが、ステップ→遷移確率→ステップのフォーマットによって表現されている。
開始              →  ０．３６      →  探す、衣服
探す、衣服        →  ０．３３３    →  設置する、機械
設置する、機械    →  ０．４２８５  →  へ向かう、機械
へ向かう、機械    →  ０．２７２７  →  持ってくる、衣服
持ってくる、衣服  →  ０．５        →  開ける、機械
開ける、機械      →  ０．８        →  入れる、衣服
入れる、衣服      →  ０．５２９４  →  加える、洗剤
加える、洗剤      →  ０．５        →  閉める、機械
閉める、機械      →  ０．２８５７  →  動かす、機械
動かす、機械      →  ０．６６６６  →  終了
【００４６】
（全体的最適化に基づく生成的プラン）
本発明の他の実施形態によれば、単に直前のステップだけではなく、経由した全てのステップを考慮に入れて各ステップを選択することにより、タスクモデルからプランが生成される。この実施形態では、時点ｔにおけるステップは（式４）によって決定される。
【００４７】
【数８】
2009500746.tif 000010
【００４８】
ここでｔは現ステップの時点である。
2009500746.tif 000011
複数の候補が同じ最大確率を提供する場合、すなわち同点状態がある場合には、ランダムに選択がなされることとしてもよい。このアプローチを第４の手法と呼ぶ。
【００４９】
本発明の他の実施形態によれば、第４の手法が適用されるのは、同点状態でステップ数が最小のプランが選択される場合以外である。この後者のアプローチを第５の手法と呼ぶ。
【００５０】
（環境制約つき生成的プラン）
第１〜５の手法はアプリオリに、すなわち自律機械が動作する現実の屋内環境を考慮することなく実装される。しかし、現実の屋内環境の知られた面が、プランの生成に考慮され得る。このことは、プランが実際的になることを約束する。このような環境情報は、例えば、ロボットのユーザによって提供され得る。代替的に、ロボット自身が、デジタルカメラ１３０ａ、ビデオシステム１３０ｂ又は他の手段を用いて環境情報を決定してもよい。生成されるプランを、知られた利用可能な客体の使用を推奨するように限定する又はそのようにバイアスを与えるとより有利である。このアプローチを第６の手法と呼ぶ。
【００５１】
本発明のある実施形態によれば、タスクモデルは動作と客体のペアで構成されているので、最もありそうな動作とはその客体が存在することがわかっている場合に最も発生する頻度が高い動作であると仮定することによって、（式１）によって決定された確率が使用され得る。さらに明確にいえば、そのような客体と結びつくべき最も確率の高い動作は、（式５）によって発見される。
【００５２】
【数９】
2009500746.tif 000012
【００５３】
観測された客体が最もありそうな動作と結びついているからといって、そのような動作がプランの中で要求されるわけではない。例えば、プラン生成プロセスは、他の選択されたステップとの整合性を保つために、そのようなステップを無視し得る。
【００５４】
水、衣服及び洗濯機が使用されるという制約付の“衣服を洗濯する”タスクのための生成的プランの一例として、以下があげられる。
発見された制約：“注ぐ、水”確率０．２
発見された制約：“入れる、衣服”確率０．３２
発見された制約：“動かす、洗濯機”確率０．１５
プラン：
開始            →  ０．３６  →  探す、衣服
探す、衣服      →  １        →  入れる、衣服
入れる、衣服    →  １        →  注ぐ、水
注ぐ、水        →  １        →  注ぐ、洗剤
注ぐ、洗剤      →  １        →  設定する、タイミング
設定する、タイミング  →  １  →  動かす、洗濯機
動かす、洗濯機  →  ０．６６６６  →  終了
前記方法に制約を満たすステップを選択させるために、対応する遷移確率は１．０に設定される。結果として、このプランは、前記のように制約なしで引き出されたプランとは異なる。
【００５５】
実験においては、１０５個の家事タスクについてのタスクプランが、前記のように第１〜５の手法にしたがって決定されかつ評価された。第６の手法は、後記する理由により評価されなかった。タスク毎に、少なくとも２５個のプランが知識データベースに存在していた。全ての決定されたタスクが同じ知識と処理手順を使用した。５つの手法に対する評価は、要すれば以下の通りである。
第１の手法（ランダムアプローチ）：プランがランダムに、プランデータベースから選択された。
第２の手法（区別的アプローチ）：プランが、最大のクラスタから選択された。
第３の手法（生成的アプローチ、局部的最適化）：プランが対応するタスクモデルから生成され、各ステップは独立的に考慮された。
第４の手法（生成的アプローチ、全体的最適化、同点ランダム解決）：ステップのシーケンス全体の確率を評価することによって、タスクモデルからプランが生成された。同点状態の場合は、最良候補の中からのランダム選択が行われた。
第５の手法（生成的アプローチ、全体的最適化、同点厳密解決）：ステップのシーケンス全体の確率を評価することによって、タスクモデルからプランが生成された。同点状態の場合は、最短のプランが選択された。
【００５６】
結果の評価及び比較に用いた判断基準は以下の通りである。
１．完全性：タスクに対するプランは、ステップの完全な組を含むべきである。例えば、床を掃除するプランが水及び石鹸を使用したが、その後に床をモップ掛けしなかった場合は、不完全とされる。
２．シーケンスの正確性：ステップのシーケンスは、ステップ自身と整合しているべきである。例えば、コーヒーメーカに水を注ぐ前に、水差しからコップにコーヒーを注ぐプランは、評価が低い。
３．有意性：プラン全体が意味をなすべきである。例えば、コーヒーを作るプランがコーヒーメーカとインスタントコーヒーを同時に使用していれば、評価は低い。
４．簡潔性：所与の客体数に対して、より簡潔な説明を有するプランが好ましい。例えば、コーヒーを作るタスクについて、“フィルターを加える”単独のステップは、“フィルターを発見し”次に“フィルターを１枚取り”最後に“フィルターを加える”というシーケンスよりも好ましい。
【００５７】
プランの“よさ”はそもそも客観的に評価され得ないことから、人間が結果を評価した。１０５個のタスクのそれぞれについて決定されたプランを１０人が評価した。第６の手法はこの方法では評価されなかった。なぜならば、環境制約の使用は、評価するのが困難であるからである。しかしながら、第６の手法は、第３の手法の特別な場合であるから、第３の手法の効果を引き継いでいる。あるプランに対して、最悪のスコアとして５を、最良のスコアとして１を割り振った。プラン毎に１０人によるスコアの平均値が計算された。それぞれの手法毎に１０５個の平均スコアがその際加えられた。結果は図５の通りであるが、そこからは以下の観測がなされ得る。
第１の手法は、最悪のパフォーマンスに留まった。１人だけの知識、又は１つだけの情報源に頼る結果は、劣ったプランにしかならない。
第２の手法は、第１の手法よりは上位にある。したがって、コンセンサスの取れたクラスタからランダムに選択されたプランは、完全にランダムに選択されたプランよりは優れている。
第３の手法は、最良のパフォーマンスを発揮した。この手法は他の理由からも魅力的といえる。第一に、この手法は、（第１、２の手法のように）先在するプランの各局面というよりはむしろ別々の構成要素としてステップを捉えている。従って、結果として生じるプランは、（第１、２の手法のように）先行するプランに限定されない。第二に、この手法は、例えばスペルミス、勘違い等の“ノイズ”や、学習を介したが故の偽りのデータを取り除く。第三に、この手法は、タスクステップとそのシーケンシングのレベルでコンセンサスを得る。
第４と第５の手法は、第３の手法ほどのパフォーマンスを発揮しない。これは、長いステップシーケンスの推論を有効に実行するために使用されるプランの数が不足していることによる。
【００５８】
テーブル１のランキングの信頼度を評価するために、両側ｔ分布検定が実行された。このテストは、１組のテストの相関する結果の信頼レベルを、２つのテスト結果が同一の確率分布に起因しているか否かを判定することにより評価する。起因する場合は、結果は統計的に有意である、すなわち２つの手法の評価された相関するパフォーマンスには高度の信頼度があることになる。
第１の手法に対する第２〜５の手法のｐ値（有意確率）が図６に示されている。ｐ値が０．０５未満であれば、相関するパフォーマンスの信頼度は少なくとも９５％である。図６に示されるように、第３、４の手法のｐ値は０．０５未満である。従って、第３、４の手法のパフォーマンスが第１の手法よりもよいということが、少なくとも９５％の信頼度に基づいていえる。前記したように、これらのテストは、それぞれ、第１位、第２位にランクされる。
【００５９】
人間形ロボットのような自律機械が屋内タスクを遂行するプランを提供するシステム及び方法を備えることが本発明の効果である。プランは常識、すなわち非熟練ボランティアのコンセンサスに基づいている。このことは、家事ルーチンや他の屋内タスクには適当な基準である。プランは、アプリオリに、すなわち現状の操作環境に対する知識なしで決定され得る。代替的に、現状の操作環境中の客体の利用確率を考慮に入れるためにプランが最適化されることもあり得る。新たなバリエーションが利用可能になれば、プランは容易に修正される。
【００６０】
自律機械が屋内タスクを遂行するプランを提供するためのシステム及び方法についての追加的な代替デザインを、当業者であれば評価できるであろう。従って、本発明はここに開示した具体的構成に限定されず、また、前記特許請求の範囲に記載した本発明の主旨や範囲から逸脱することなく、ここに開示される本発明の方法や装置について、当業者にとって明らかな修正や設計変更を加えることが可能であると理解される。
【図面の簡単な説明】
【００６１】
【図１】本発明の一実施形態によるシステムを示す図である。
【図２】本発明の一実施形態によるタスク知識データベースの創作方法を示す図である。
【図３】本発明の一実施形態によるタスクを遂行するためのプランの構築手法を示す図である。
【図４】本発明の一実施形態によるタスクモデルの一部分を示す図である。
【図５】本発明の実験結果を示す図である。
【図６】本発明の実験結果に対応するｐ値（有意確率）を示す図である。
【図１】
2009500746.tif 000021
【図２】
2009500746.tif 000022
【図３】
2009500746.tif 000023
【図４】
2009500746.tif 000024
【図５】
2009500746.tif 000025
【図６】
2009500746.tif 000026
【国際調査報告】
2009500746.tif 000027