(57)【要約】【課題】複数のロボットを用いる環境の探察および監視のための技法を提供する。【解決手段】ロボットの各々に対する巡回緩衝域を算定し、ロボットの各々が、他のロボットから実質的に最小限の距離を維持しながら環境内を巡回するのを可能にすることによって、複数のロボットが環境を巡回し、この実質的に最小限の距離は、巡回緩衝域に対応し、巡回緩衝域の各々のサイズは、巡回予定の残りの環境のパーセンテージに基づいて、時間とともに低減される。環境を複数の個別領域に離散化し、幅優先探索を用いて、複数のロボットのうちの一つに対する、例示的環境の中の探査対象の次の未巡回個別領域を決定することによって、ロボットは、環境を巡回することもできる。これら複数の個別領域は、例えば、複数の実際のまたは仮想のタイルとすることができる。【選択図】図２
2015505410.tif 000002
【特許請求の範囲】
【請求項１】
ある環境の中で複数のロボットを巡回させる方法であって、
前記ロボットの各々に対する巡回緩衝域を算定するステップと、
前記複数のロボットの各々が、他のロボットから実質的に最小限の距離を維持しながら、前記環境内を巡回することを可能にするステップと、
を含み、前記実質的に最小限の距離は、前記巡回緩衝域のサイズに相当し、前記巡回緩衝域の各々のサイズは、巡回予定として残っている前記環境のパーセンテージに基づいて時間とともに低減される、
方法。
【請求項２】
前記巡回緩衝域が、巡回予定として残っている前記環境の前記パーセンテージに直接比例して低減される、請求項１に記載の方法。
【請求項３】
前記複数ｋ個の巡回緩衝域が、前記環境内部にｋ個のほぼ均一な巡回緩衝域を適合させるような、開始点巡回緩衝域に初期化される、請求項１に記載の方法。
【請求項４】
前記環境の残りの前記パーセンテージが推量された値である、請求項１に記載の方法。
【請求項５】
前記巡回緩衝域の少なくとも一つの前記サイズが、前記対応するロボットの速度に基づく、請求項１に記載の方法。
【請求項６】
前記巡回緩衝域の各々が、前記対応するロボットの周りの所与の半径の円を含む、請求項１に記載の方法。
【請求項７】
ある環境の中で複数のロボットを巡回させる方法であって、
前記環境を複数の個別領域に離散化するステップと、
幅優先探索を用いて、典型的環境の中で前記複数のロボットの一つが探査することになる次の未巡回個別領域を算定するステップと、
を含む方法。
【請求項８】
前記算定するステップが前記複数のロボットの各々によって行われる、請求項７に記載の方法。
【請求項９】
前記算定するステップが少なくとも一つのプロセッサによって行われ、前記算定するステップの結果が前記複数のロボットの各々に提供される、請求項７に記載の方法。
【請求項１０】
前記複数の個別領域が複数の実際のまたは仮想のタイルを含む、請求項７に記載の方法。
【請求項１１】
前記環境が既知の環境を含む、請求項７に記載の方法。
【請求項１２】
前記算定するステップは、各ロボットが、前記個別領域の一つの中に一度に全ての可能な方向へ仮定的一ステップを進めるステップと、一つのロボットが前記次の未巡回個別領域に達するまで、幅優先探索ツリーの経路を維持するステップとをさらに含む、請求項７に記載の方法。
【請求項１３】
前記算定するステップは、前記一つのロボットが、前記複数のロボットの他のロボットに、前記一つのロボットが前記幅優先探索ツリー中で前記次の未巡回個別領域に到達したことを宣言するステップと、前記複数のロボットの前記他のロボットが、前記一つのロボットとの衝突があるかどうかを判定するステップと、前記一つのロボットが前記幅優先探索ツリーを前記次の未巡回個別領域の単一ポイントに折り畳むステップと、をさらに含む、請求項１２に記載の方法。
【請求項１４】
ある環境の中で複数のロボットを巡回させるための装置であって、前記装置は、
メモリと、
前記メモリに連結された少なくとも一つのハードウェア・デバイスであって、
前記ロボットの各々に対する巡回緩衝域を算定し、
前記複数のロボットの各々が、他のロボットから実質的に最小限の距離を維持しながら、前記環境内を巡回することを可能にする、
よう動作可能な、前記少なくとも一つのハードウェア・デバイスと、
を含み、前記実質的に最小限の距離は、前記巡回緩衝域のサイズに相当し、前記巡回緩衝域の各々のサイズは、巡回予定として残っている前記環境のパーセンテージに基づいて時間とともに低減される、
装置。
【請求項１５】
前記巡回緩衝域が、巡回予定として残っている前記環境の前記パーセンテージに直接比例して低減される、請求項１４に記載の装置。
【請求項１６】
前記ロボットが、一つ以上のセンサを用いて前記環境中で一つ以上の測定を行う、請求項１４に記載の装置。
【請求項１７】
前記複数ｋ個の巡回緩衝域が、前記環境内部にｋ個のほぼ均一な巡回緩衝域を適合させるような、開始点巡回緩衝域に初期化される、請求項１４に記載の装置。
【請求項１８】
前記環境の残りの前記パーセンテージは推定された値である、請求項１４に記載の装置。
【請求項１９】
前記巡回緩衝域の少なくとも一つの前記サイズが、前記対応するロボットの速度に基づく、請求項１４に記載の装置。
【請求項２０】
前記巡回緩衝域の各々が、前記対応するロボットの周りの所与の半径の円を含む、請求項１４に記載の装置。
【請求項２１】
ある環境の中で複数のロボットを巡回させるための装置であって、
メモリと、
前記メモリに連結された少なくとも一つのハードウェア・デバイスであって、
前記環境を複数の個別領域に離散化し、
幅優先探索を用いて、例示の環境の中で前記複数のロボットの一つが探査することになる次の未巡回個別領域を算定する、
よう作動可能な前記少なくとも一つのハードウェア・デバイスと、
を含む、装置。
【請求項２２】
前記算定が前記複数のロボットの各々によって行われる、請求項２１に記載の装置。
【請求項２３】
前記算定が少なくとも一つのプロセッサによって行われ、前記判定の結果が前記複数のロボットの各々に提供される、請求項２１に記載の装置。
【請求項２４】
前記環境が既知の環境を含む、請求項２１に記載の装置。
【請求項２５】
前記算定は、各ロボットが、前記個別領域の一つの中に一度に全ての可能な方向へ仮定的一ステップを進めることと、一つのロボットが前記次の未巡回個別領域に達するまで、幅優先探索ツリーの経路を維持することとをさらに含む、請求項２１に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、所与の環境または領域を探査および監視するための複数の移動ロボットを調整するための自動化技法に関する。
【背景技術】
【０００２】
データ・センタは益々多くのエネルギを消費している。冷却がエネルギ消費の大きな寄与因子であることを認識して、データ・センタの運営担当者は、より高いオペレーション温度を許容し始めている。このやり方はかなりの量のエネルギを節約するが、許容動作温度限界の近くで稼働することは、温度の問題によって設備の故障が生じ、エネルギ節約の経済的利益が帳消しになるというリスクを増大させる。警戒が必要であるので、温度などデータ・センタの環境状態を監視し、厄介なホット・スポットが生じたときには運営担当者に警報を出す、データ・センタのエネルギ管理ソフトウェアを使って警戒が強化されている。
【０００３】
データ・センタ内を自動的に巡回し、マップし、監視する一つ以上のロボットを用いるためのいくつもの技法が提案または提言されてきた。例えば、非特許文献１は、データ・センタを自動的に巡回し、マップし、監視する物理的自律エレメントとして機能するロボットを開示しており、この開示は参照することにより本明細書に組み入れられる。開示されたロボットは、ほとんど人手を借りずに、データ・センタを巡回し、そのレイアウトをマップし、その温度および他の関心のある数値を監視する。さらに２０１０年９月２８日出願、名称「Ｄｅｔｅｃｔｉｎｇ  Ｅｎｅｒｇｙ  ａｎｄ  Ｅｎｖｉｒｏｎｍｅｎｔａｌ  Ｌｅａｋｓ  ｉｎ  Ｉｎｄｏｏｒ  Ｅｎｖｉｒｏｎｍｅｎｔｓ  Ｕｓｉｎｇ  ａ  Ｍｏｂｉｌｅ  Ｒｏｂｏｔ」特許文献１は、一つ以上の移動ロボットを使い、屋内環境中のエネルギおよび環境的な漏出を検出する技法を開示しており、この出願は参照することにより本明細書に組み入れられる。
【０００４】
ロボットの使用は、屋内環境を自動的に監視する能力を大きく向上させたが、これらにはいくつかの欠点があり、それらが克服されれば、屋内環境を監視しているロボットの実用性をさらに拡大し且つ効率をさらに上げることができよう。例えば、複数のロボットを、特に探査の終わり頃に相互に邪魔することなく、屋内環境を効率的に巡回させることは難しい課題である。いくつかの既存の巡回技法は、最初に非特許文献２で単一のロボットに対して記載されており、もっと近年では、複数のロボットを対象として非特許文献３に記載されている、周知のフロンティアベースのＡ＊漸近的ナビゲーション法を用いている。さらに、いくつかの既存の巡回技法は、ロボットが相互に、マニュアルで調整されたある距離を保つよう強制するため、各ロボットが「ポテンシャル場」を持つアイデアも取り入れている。例として、非特許文献４を参照されたい。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国特許出願第１２／８９２，５３２号
【非特許文献】
【０００６】
【非特許文献１】Ｊ．Ｌｅｎｃｈｎｅｒら著、「Ｔｏｗａｒｄｓ  Ｄａｔａ  Ｃｅｎｔｅｒ  Ｓｅｌｆ−Ｄｉａｇｎｏｓｉｓ  Ｕｓｉｎｇ  ａ  Ｍｏｂｉｌｅ  Ｒｏｂｏｔ」、ＡＣＭ  Ｉｎｔ‘ｌ  Ｃｏｎｆ．ｏｎ  Ａｕｔｏｎｏｍｉｃ  Ｃｏｍｐｕｔｉｎｇ  （ＩＣＡＣ  ’１１）（２０１１年）
【非特許文献２】Ｐｅｔｅｒ  Ｈａｒｔら著、「Ａ  Ｆｏｒｍａｌ  Ｂａｓｉｓ  ｆｏｒ  ｔｈｅ  Ｈｅｕｒｉｓｔｉｃ  Ｄｅｔｅｒｍｉｎａｔｉｏｎ  ｏｆ  Ｍｉｎｉｍｕｍ  Ｃｏｓｔ  Ｐａｔｈｓ」、ＳＩＧＡＲＴ  Ｎｅｗｓｌｅｔｔｅｒ、３７：２８〜２９（１９７２年）
【非特許文献３】Ｙａｍａｕｃｈｉ著、「Ｆｒｏｎｔｉｅｒ−Ｂａｓｅｄ  Ｅｘｐｌｏｒａｔｉｏｎ  Ｕｓｉｎｇ  Ｍｕｌｔｉｐｌｅ  Ｒｏｂｏｔｓ」、Ｐｒｏｃ．ｏｆ  ｔｈｅ  Ｉｎｔ‘ｌ  Ｃｏｎｆ．ｏｎ  Ａｕｔｏｎｏｍｏｕｓ  Ａｇｅｎｔｓ（１９９８年）
【非特許文献４】Ｙｏｎｇ  Ｋ．ＨｗａｎｇおよびＮａｒａｎｄｒａ  Ａｈｕｊａ著、「Ａ  Ｐｏｔｅｎｔｉａｌ  Ｆｉｅｌｄ  Ａｐｐｒｏａｃｈ  ｔｏ  Ｐａｔｈ  Ｐｌａｎｎｉｎｇ」、ＩＥＥＥ  Ｔｒａｎｓ．Ｏｎ  Ｒｏｂｏｔｉｃｓ  ａｎｄ  Ａｕｔｏｍａｔｉｏｎ  Ａｃｔｉｏｎｓ、Ｖｏｌ．８、Ｉｓｓｕｅ  １（ＩＥＥＥ、１９９２）
【発明の概要】
【発明が解決しようとする課題】
【０００７】
環境、特にデータ・センタなどの構築がしっかりしている屋内環境を、自動的に巡回し、マップし、監視するロボットのためのさらに効率の良い巡回方法が求められている。
【課題を解決するための手段】
【０００８】
一般に、本発明の諸態様は、複数のロボットを用いる環境の探察および監視を提供する。本発明の一態様によれば、ロボットの各々に対する巡回緩衝域を算定し、ロボットの各々が、他のロボットから実質的に最小限の距離を維持しながら環境内を巡回するのを可能にすることによって、複数のロボットが環境を巡回し、この実質的に最小限の距離は、巡回緩衝域のサイズに対応しており、巡回緩衝域の各々のサイズは、巡回予定の残りの環境のパーセンテージに基づいて、時間とともに低減される。
【０００９】
巡回緩衝域のサイズは、例えば、巡回予定の残りの環境のパーセンテージに直接比例して低減することができる。環境は既知の環境であっても未知の環境であってもよい。巡回緩衝域は、例えば、環境内でｋ個の均一な巡回緩衝域に対し適合させるため、開始点エリアに初期化することが可能である。例えば、巡回緩衝域は、円形、楕円形、正方形、長方形、他の多角形などを含み得る。ロボットが三次元で巡回することが可能な場合、これらの区域を三次元にすることも可能であり、類似のサンプル巡回緩衝域として、球体、楕円体、立方体、または直方体がある。
【００１０】
本発明の別の態様によれば、ある環境を複数の個別領域に離散化し、幅優先探索を用いて、典型的環境の中で複数のロボットのうちの一つが、探査することになる次の未巡回個別領域を算定することによって、複数のロボットが該環境を巡回する。これら複数の個別領域は、例えば、複数の実際のタイルまたは仮想のタイルとすることができる。
【００１１】
以下の詳細な説明および図面を参照することによって、本発明並びに本発明のさらなる特徴および利点がより完全に理解がされよう。
【図面の簡単な説明】
【００１２】
【図１】本発明を用いることができる典型的な屋内環境を示す。
【図２】本発明の態様を組み入れたポテンシャル場半径算定プロセスに対する例示的なフローチャートである。
【図３】本開示の変化するポテンシャル場巡回技法を用いた、図１の典型的な屋内環境を通る例示的なロボットＲ１およびＲ２による巡回を示す。
【図４】本開示の変化するポテンシャル場巡回技法を用いた、図１の典型的な屋内環境を通る例示的なロボットＲ１およびＲ２による巡回を示す。
【図５】本発明の態様を組み入れた幅優先探索経路算定に対する例示的なフローチャートである。
【図６】図５の幅優先探索経路算定プロセスを用いて次の未巡回タイルを算定する、図１の典型的な屋内環境を通る例示的なロボットＲ１およびＲ２による巡回を示す。
【図７】図５の幅優先探索経路算定プロセスを用いて次の未巡回タイルを算定する、図１の典型的な屋内環境を通る例示的なロボットＲ１およびＲ２による巡回を示す。
【図８】図５の幅優先探索経路算定プロセスを用いて次の未巡回タイルを算定する、図１の典型的な屋内環境を通る例示的なロボットＲ１およびＲ２による巡回を示す。
【図９】図５の幅優先探索経路算定プロセスを用いて次の未巡回タイルを算定する、図１の典型的な屋内環境を通る例示的なロボットＲ１およびＲ２による巡回を示す。
【図１０】図５の幅優先探索経路算定プロセスを用いて次の未巡回タイルを算定する、図１の典型的な屋内環境を通る例示的なロボットＲ１およびＲ２による巡回を示す。
【図１１】図５の幅優先探索経路算定プロセスを用いて次の未巡回タイルを算定する、図１の典型的な屋内環境を通る例示的なロボットＲ１およびＲ２による巡回を示す。
【図１２】図５の幅優先探索経路算定プロセスを用いて次の未巡回タイルを算定する、図１の典型的な屋内環境を通る例示的なロボットＲ１およびＲ２による巡回を示す。
【図１３】図５の幅優先探索経路算定プロセスを用いて次の未巡回タイルを算定する、図１の典型的な屋内環境を通る例示的なロボットＲ１およびＲ２による巡回を示す。
【図１４】図５の幅優先探索経路算定プロセスを用いて次の未巡回タイルを算定する、図１の典型的な屋内環境を通る例示的なロボットＲ１およびＲ２による巡回を示す。
【図１５】本発明のプロセスを実装できるロボット巡回システムのブロック図である。
【発明を実施するための形態】
【００１３】
本発明は、これまでに既知の環境、さらにはこれまで未知の環境における、改良されたマルチロボット巡回を提供する。本発明の変化するポテンシャル場の態様によれば、既知および未知の環境でのマルチロボット巡回は、既知環境において探査対象として残っている面積のパーセンテージまたは未知環境において探査対象として残っている面積の推定パーセンテージに基づき、ポテンシャル場の半径を変化させることによって改良される。本明細書では、このポテンシャル場を「巡回緩衝域」とも言う。一般に、典型的なポテンシャル場の半径は、未探査として残っている屋内環境のパーセンテージ（または推定パーセンテージ）が減少するにつれ縮小する。本発明の変化するポテンシャル場の態様は、各ロボットの周りにほぼ均一な半径を有する円形を使って示されているが、当業者には当然のことながら、各ロボットの周りには任意の形状で様々なサイズの巡回緩衝域を設定することが可能である。
【００１４】
本発明の幅優先探索の態様によれば、既知の環境のマルチロボット巡回は、幅優先探索（ＢＦＳ：ｂｒｅａｄｔｈ−ｆｉｒｓｔ  ｓｅａｒｃｈｉｎｇ）を用いて、複数のロボットに対し該既知の環境を通る経路を算定することによって改良される。本開示の幅優先探索技法は、２個以上のロボットが環境の同じ位置を巡回しようとするのを防止する、多項式時間の再帰発見的手法を用いる。一般に、各ロボットは幅優先探索ツリーを漸次的に生成し、これらロボットは環境内の次の未巡回場所を集団で見出そうと試みる。各ロボットは、未巡回場所を最初に見出したロボットに適合させるようそれぞれのＢＦＳツリーを更新する。
【００１５】
一般に、幅優先探索（ＢＦＳ）は、ルート・ノードで開始され隣接する全てのノードを探査する、グラフ探索アルゴリズムである。しかして、これら最近接のノードの各々に対し、このグラフ探索アルゴリズムはそれら未探査の隣接ノードの全てを、所望のノード（すなわち、未巡回タイル）が見付かるまで次々と探査する。
【００１６】
本明細書で用いる用語「ビルディング」は、以下に限らないが、多数の情報技術（ＩＴ：ｉｎｆｏｒｍａｔｉｏｎ  ｔｅｃｈｎｏｌｏｇｙ）設備をホストするデータ・センタ並びに産業事務所スペースおよび住居用ビルディングを含む、さまざまな施設を言及することが意図されている。
【００１７】
図１は、本発明を用いることができる典型的な屋内環境１００を示す。一組のロボット（Ｒ１，・・・，Ｒｋ）が与えられ、この典型的な屋内環境１００内の探査対象スペースが、正方形の「タイル」のセットに離散化されていると仮定しよう。コンピュータ・データ・センタなど一部の実際の環境では、本来の離散化単位は、実際上は物理的なフロアまたは天井のタイルである。他の環境では、この離散化単位を仮想タイルとすることが可能である。図１の典型的な屋内環境１００は、２つの例示的なロボットＲ１およびＲ２によって探査される、６×６のタイルの例示的な配列を含む。典型的な屋内環境１００中のｘでマークされたタイルは未巡回で残されている。斜交平行線で埋められたタイルは、障害物の存在を示す。図２から図４に関連させて以下でさらに説明するように、例示的なロボットＲ１およびＲ２は、本発明の変化するポテンシャル場の態様を使って、典型的な屋内環境１００を通って巡回する。図５〜図１４に関連させて以下でさらに説明するように、例示的なロボットＲ１およびＲ２は、本発明の幅優先探索の態様を使って、典型的な屋内環境１００通って巡回する。
【００１８】
好適な例示的ロボットの詳細な説明については、例えば、特許文献１を参照されたい。この出願は参照することにより本明細書に組み入れられる。本明細書で用いる用語「ロボット」とは、一般に、電子的にまたはコンピュータ・プログラミングで制御可能な移動式電気機械デバイスの任意の形態のものを言う。以下で詳細を述べるように、この基本的な形において、例示的なロボットは、ビルディング１００の指定部分を全体にわたって移動し、温度、空気流もしくは浮遊物質またはこれらの組み合わせの測定値、並びに（該温度、空気流もしくは浮遊物質またはこれらの組み合わせのデータを、特定の時間におけるビルディング１００中の所与の位置に関連付けられるように）時間および位置のデータを採取する。これらロボットは、ビルディング１００において行く必要がある場所を巡回し且つ設備、調度品、壁などの障害物を回避するため、ビルディング１００のフロアに沿って様々な方向に動ける必要がある。
【００１９】
これらロボット（例えば、屋内環境１００のＲ１およびＲ２）は、後で解析ができるように、データ、すなわち温度、空気流もしくは浮遊物質またはこれらの組み合わせの測定値並びに時間／位置データを、収集して格納できる能力を有することが好ましいが、但し、これらデータを制御コンピュータまたはサーバ・コンピュータに流すことも可能である。該コンピュータは前記データを処理もしくは格納またはその両方を行うことができる。
【００２０】
後で説明するように、典型的な屋内環境１００は、既知の環境であっても未知の環境であってもよい。前述したように、本発明の変化するポテンシャル場の態様は、既知のまたは未知の環境を巡回するため使用することができる。同様に、本発明の幅優先探索の態様は、既知の環境を巡回するため使用が可能である。本発明の変化するポテンシャル場および幅優先探索の態様は、既知の環境で、特に、多くのロボットを用い、幅優先探索の計算時間およびスペース・コストが法外になり得る環境の場合に、組み合わせることができる。例えば既知の格子状のスペースでは、例えば５Ｒ格子ポイント（Ｒはロボットの数）が未巡回で残るまでは、変化するポテンシャル場のアプローチを使うことができる。
【００２１】
未探査面積のパーセンテージに基づく巡回緩衝域
図２は、本発明の態様を組み入れた、巡回緩衝域が全て均一な半径の円である、ポテンシャル場半径算定プロセス２００の例示的なフローチャートである。図２に示されるように、ポテンシャル場半径算定プロセス２００は、まず、ステップ２１０で算定される巡回対象の環境の外周を表す多角形Ｐを使って開始される。次に、ポテンシャル場半径算定プロセス２００は、ステップ２２０で、巡回対象の領域の面積Ａを計算し、ｋ個のロボット（Ｒ１，・・・，Ｒｋ）があるという事実に対しプロセス自体を初期化する。
【００２２】
次いで、ポテンシャル場半径算定プロセス２００は、ステップ２３０で、Ｐの中にｋ個の均一な半径の円板を入れ込むため円板の概算最大（開始時の）半径を取得する。この取得は、例えば標準的な格子移動法を使い、ありそうな半径群に対し２分探索法を用いて異なる半径群での円板の入れ込みを試みて各々の入れ込みを達成することによる。格子移動法については、例えば、Ｄ．ＨｏｃｈｂａｕｍおよびＷ．Ｍａａｓ著、「Ａｐｐｒｏｘｉｍａｔｉｏｎ  Ｓｃｈｅｍｅｓ  ｆｏｒ  Ｃｏｖｅｒｉｎｇ  ａｎｄ  Ｐａｃｋｉｎｇ  Ｐｒｏｂｌｅｍｓ  ｉｎ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ  ａｎｄ  ＶＬＳＩ」、３２（１）：１３０〜１３６、１９８５年を参照されたい。次いでステップ２４０で、算定された最大半径は、ロボットが移動する余地を有し、且つ算定された最大半径が推定値以下となることを確実にするため、１０〜２０％など設定可能な分量を低減される。再述するが、当業者には当然のことながら、各ロボットの周りには、任意の形状で様々なサイズの巡回緩衝域を設定することが可能である。
【００２３】
ステップ２５０で、ロボットは、次の未巡回エリアを見付けるよう集団で試み、探査済みの面積のパーセンテージが増大するにつれ、ポテンシャル場の半径は、ステップ２６０で、例えば未探査面積の現在のパーセンテージに線形に比例して、低減される。探査対象領域が前もって分かっていない場合には、当然ながら、どの時点における未探査面積の正確なパーセンテージも、境界多角形の面積と障害物が包含されていることが判明している探査済み面積の割合とを利用して、推定しなければならない。次の未巡回エリアがないとき、言い換えればエリアの探査が完了したとき、ステップ２７０で本プロセスは終了する。
【００２４】
図３および図４は、本発明の変化するポテンシャル場の態様を用いた、典型的な屋内環境１００を通る例示的なロボットＲ１およびＲ２による巡回を示す。図３は、当初の時間ｔ１における例示的なロボットＲ１およびＲ２による巡回を示し、図４は、タイルのある割合が探査された後の時間ｔｎにおける例示的なロボットＲ１およびＲ２による巡回を示す。ｘ２でマークされたタイルはロボットＲ２が探査したタイルを表し、ｘ１でマークされたタイルはロボットＲ１が探査したタイルを表す。なお、典型的な屋内環境１００の未探査として残るパーセンテージが時間とともに低減するので、時間ｔ１における半径ｒｔ１は、時間ｔｎにおける半径ｒｔｎよりも大きい。図３の時間ｔ１において未探査として残るタイルの数は２７タイルであり、一方、図４の時間ｔｎにおいて未探査として残るタイルの数は１５タイルである。個々のロボットに関連付けられたポテンシャル場または巡回緩衝域は、所与の時間においてそれらの周りに関連付けられた円または円板、すなわち、図３の時間ｔ１における半径ｒｔ１の円板および図４の時間ｔｎにおける半径ｒｔｎの円板によって示されている。任意の所与の時間ｔｉにおいて、これらの円板は、ロボット同士を少なくとも２ｒｔｉの距離だけ離しておく働きをする。さらなる変形案において、ポテンシャル場または巡回緩衝域は、ロボット同士を少なくともｒｔｉの距離だけ離しておく機能を果たすことができる（すなわち、所与のロボットは、別のロボット自体がその所与のロボットの巡回区域内にいない限り、移動し続けることができる）。さらに別の変形案では、この半径または形状の面積を各ロボットの速度に比例させることが（同様に、残りの／未巡回のスペースの量に比例させることも）可能である。
【００２５】
幅優先探索の巡回
図５は、本発明の態様を組み入れた幅優先探索経路算定プロセス５００の例示的なフローチャートである。図６〜図１４に関連させて後でさらに説明するように、例示的な各ロボットＲ１およびＲ２は、典型的な屋内環境１００を通る巡回経路中の次の未巡回タイルを決めるために、幅優先探索経路算定プロセス５００を実行する。
【００２６】
図５に示されるように、ステップ５１０で、各ロボットは、その全一式の経路の幅優先探索（ＢＦＳ）ツリーを維持し、全方向への仮定的一ステップを（ソフトウェアで）進める。ＢＦＳツリーは、図７に関連させて後記でさらに説明する。ステップ５２０で、ロボットは各自のＢＦＳツリーを一階層さらなる深度レベルに展開し、未巡回タイルを見出したいずれかのロボットは、その事実を、タイルが見出された経路と共に他のロボットに宣言する。かかる未巡回タイルを見出した任意のロボットのことを「宣言」ロボットと呼ぶものとする。この宣言は、所定の任意の種類の、ロボット−ロボット間、またはロボット−サーバ−ロボット間の通信を用いて行われる。ステップ５３０で、判定／制御点に達する。どのロボットも新しいタイルを見出さなかった場合は、ステップ５１０を繰り返し、全ロボットが自身のＢＦＳツリーをさらなる深度レベルに展開する。他方、一つ以上のロボットが未巡回タイルに遭遇した場合、未巡回タイルを見出さなかったロボットはステップ５４０および５５０を実行し、タイルを見出したロボットはステップ５６０を実行する。
【００２７】
これらのステップのセットは、２組のロボット群によって並行して実行される。２つのロボットが同一のタイルを見出した場合、任意の方法を用いて、どちらのロボットを宣言ロボットとしてステップ５６０に進ませ、どちらのロボットを非宣言ロボットとするかを決めることが可能である。例えば、ポテンシャル場半径算定プロセス２００で先に行ったように、ロボットをＲ１，・・・，Ｒｋなど事前に番号付け（指標付け）し、より低い番号のロボットが「宣言」ロボットになるようにすることができる。ステップ５４０で、非宣言ロボットは、各自のＢＦＳツリーを検討し、宣言ロボットの経路のいずれかと衝突がないかどうかを調べる。どの時点であれ、非宣言ロボットが、宣言ロボットと同時に所与のタイルＴにいれば、それは衝突と見なされ、さらに、非宣言ロボットが、宣言ロボットがタイルＴ’からタイルＴに移動しているのと同時に、タイルＴからタイルＴ’に移動していれば、それも衝突と見なされる。ステップ５４０で衝突に遭遇したどのロボットも、ステップ５５０で、いかなる衝突も回避するように自身のＢＦＳツリーを再生成しなければならない。非宣言ロボットによるこれらの活動に並行して、宣言ロボットの各々は、ステップ５６０で、自分たちが見出したばかりの未巡回タイルに到達するため進む単一の経路に自身のＢＦＳツリーを折り畳む。全ての非宣言ロボットがステップ５４０および５５０を完了し、且つ、全ての宣言ロボットがステップ５６０を完了したならば、制御はステップ５１０に戻り、ロボットは、自身のＢＦＳツリーをさらなる深度レベルに再度展開する。全てのタイルが探査され、それぞれのＢＦＳツリーがこれ以上展開できなくなると、ステップ５８０で本プロセスは終了する。
【００２８】
Ｒ個のロボットと、一定の連結性（長方形のタイルの間を直角に移動するよう制約されたロボットに対しては４の連結性、長方形のタイルを斜めに自由に行き来できるロボットに対しては８の連結性）を有するタイルによるＮ個の合計タイルとに対する、幅優先探索経路算定プロセス５００の実行時間は、Ｏ（ＫＮ２）である。なぜならば、どのロボットに対するどのノードにおけるＢＦＳツリーの生成にもＯ（Ｎ）の時間がかかり、各ノードにおいて、まず、経路衝突に対するチェックの時間Ｎ＋Ｏ（Ｎ）＝Ｏ（Ｎ）があり、次いで所与の深度で開始されるＢＦＳを再生成するからである。Ｎ個の合計ノードとＫ個のロボットとを想定した場合、Ｏ（ＫＮ２）の合計実行時間が予期でき、これはロボット当たりＯ（Ｎ２）時間に完全に並列化することが可能である。予期される実行時間は、２つのロボットは自身のＢＦＳツリーが同じ時間増分に同じタイルを見出した場合にだけ衝突があることになるので、かなり少なくなる可能性がある。
【００２９】
幅優先探索経路算定プロセス５００の合計領域計算量（ｔｏｔａｌ  ｓｐａｃｅｃｏｍｐｌｅｘｉｔｙ）もＯ（ＫＮ２）である。というのは、ロボットは、各々にＯ（Ｎ）タイルまでのサイズＯ（Ｎ）の情報を維持しており、このスペース要件も同様にＯ（Ｎ２）に並列化可能だからである。
【００３０】
幅優先探索経路算定プロセス５００は、随意的に，任意の一つのロボット（またはロボットの全部）によって計算することが可能で、これにより、起動時を除き、ロボット間またはロボットとサーバとの間の通信なしで実行することができる（但し、計算時間および計算領域に関するコストが高くなる）。
【００３１】
図６〜図１４は、４つだけまだ未巡回のタイルがある（未巡回タイルにはｘが表記されている）図６から開始される、幅優先探索経路算定プロセス５００の実行の時間経過を示しており、このプロセスは、正方形のタイルの間を直角に移動するよう制約されたロボットに対し、典型的な屋内環境１００を通る巡回経路中の次の未巡回タイルを算定する。
【００３２】
図６は、ロボットＲ１がそのＢＦＳツリーの拡張を続ける際の該ロボットによる幅優先探索経路算定プロセス５００の２回の反復を示す。図６〜図１４で使用される例示的表記において「ｎ、方向」は、ロボットの運動に関連付けられた反復の回数（ｎ）および出発タイルから所与のタイルに到達するためロボットが必要とする運動の連接方向を示す。例えば「１、Ｕ」は上方向への一回目の移動を示す。同様に、Ｄは下方向への移動を示し、Ｒは右手方向への移動を示し、Ｌは左手方向への移動を示す。しかして、表記「２、ＲＵ」は、ロボットが、右手への運動およびその後の上方への運動による２回の反復によって、指定されたタイルに移動できることを示す。同じように、表記「２、ＤＲ」は、ロボットが、下方への運動およびその後の右手への運動による２回の反復によって、指定されたタイルに移動できることを示す。
【００３３】
図７は、図６に関連して前述したように、ロボットＲ１によって行われたＢＦＳツリー６００の同じ２回の反復を表しているが、従来の「ツリー構造」で仮定的パスのトレースを表現している。なお、例えば、ロボットＲ１は、下方（Ｄ）への運動およびその後の左手（Ｌ）への運動によっても、左手（Ｌ）への運動およびその後の下方（Ｄ）への運動よっても、斜め下のタイルに到達できるであろうことは言うまでもない。これらのいずれを用いるかは任意である。
【００３４】
図８は、ロボットＲ２がそのＢＦＳツリーの拡張を続ける際の該ロボットによる幅優先探索経路算定プロセス５００の二回目の反復を示す。図８に示されるように、ロボットＲ２は、一回目の下方への運動とその後の右手への運動とを使った二回目の反復で未巡回タイル７１０に達する。宣言ロボットＲ２は、未巡回タイル７１０が見付かった事実を、経路（ＤＲ）と共に他のロボットに一斉通信する。ロボットＲ１は未巡回タイル７１０の通知を受信し、ロボットＲ１は、タイル・インジケータを未巡回（ｘ）からＲ２による巡回済み（√Ｒ２）に変更する。
【００３５】
図９は、未巡回タイル７１０の検出後の、ロボットＲ２による幅優先探索経路算定プロセス５００の引き続きの実行を表す。図９に示されるように、ロボットＲ２は、その探索ツリーを未巡回タイル７１０に関連付けられた単一ポイントに折り畳み、次の反復で、ロボットＲ２のＢＦＳをそのポイントで再開始できるようにする。
【００３６】
図１０は、ロボットＲ１が反復幅優先探索経路算定プロセス５００を引き続き４回反復して実行し、ロボットＲ１がそのＢＦＳを拡張して新しい未巡回タイル９１０を見出すのを表している。図１０に示されるように、ロボットＲ１は、右手への運動、その後の上方への運動、その後の右手への２回の連続した運動（ＲＵＲＲ）を用いた４回の反復で未巡回タイル９１０に達する。宣言ロボットＲ１は、未巡回タイル９１０が見付かった事実を、経路（ＲＵＲＲ）と共に他のロボットに一斉通信する。ロボットＲ２は未巡回タイル９１０の通知を受信し、ロボットＲ２は、タイル・インジケータを未巡回（ｘ）からＲ１による巡回済み（√Ｒ１）に変更する。
【００３７】
図１１は、未巡回タイル９１０の検出後の、ロボットＲ１による幅優先探索経路算定プロセス５００の引き続きの実行を表す。図１１に示されるように、ロボットＲ１は、その探索ツリーを未巡回タイル９１０に関連付けられた単一ポイントに折り畳み、次の反復で、ロボットＲ１のＢＦＳをそのポイントで再開始できるようにする。
【００３８】
図１２は、ロボットＲ１が反復幅優先探索経路算定プロセス５００を引き続き５回反復して実行し、ロボットＲ１が、そのＢＦＳを拡張して新しい未巡回タイル１１１０を見出すのを表している。図１２に示されるように、ロボットＲ１は、一連の運動（ＲＵＲＲＲ）を用いた５回の反復で未巡回タイル１１１０に達する。宣言ロボットＲ１は、未巡回タイル１１１０が見付かった事実を、経路（ＲＵＲＲＲ）と共に他のロボットに一斉通信する。ロボットＲ２は未巡回タイル１１１０の通知を受信し、ロボットＲ２は、タイル・インジケータを未巡回（ｘ）からＲ１による巡回済み（√Ｒ１）に変更する。
【００３９】
図１３は、ロボットＲ２による、幅優先探索経路算定プロセス５００を引き続き５回反復して実行することを表す。図１３に示されるように、ロボットＲ２は、未巡回タイル１１１０に対するタイル・インジケータを未巡回（ｘ）からＲ１による巡回済み（√Ｒ１）に変更済みである。
【００４０】
図１４は、今や全部のタイルが巡回済みとマークされ、幅優先探索経路算定プロセス５００が完了した後の、ロボットＲ１およびＲ２の最終的な経路を表す。
【００４１】
また、ある例示的な実施形態によれば、各ロボットは、例えば搭載カメラなどの視覚コンポーネントも有する。データ・センタなどの規則的に格子化（例えばタイル化）された状況では、ロボットの視覚コンポーネントは、タイルの中央に対するロボットの「姿勢」を検出すること、および、ロボットが調査したい次のタイルが見えるのか、またはブロックされている（例えば、タイルが設備に占拠されているかまたは別途に遮られている）のかを判定すること、の役割がある。このロボットの姿勢とは、タイルを中央にして進行方向の「直交」方向に対するロボットの位置および方向である。進行方向の直交方向とは、ロボットの意図した見積もり（一つのタイルの中央から第二の隣接するタイルの中央への）に正確に合わせられた方向であり、すなわち、その方向に沿ってロボットが直進移動したならば、該ロボットは、タイルの境界対し垂直（直角）な経路に沿ってそのタイル間の境界を横断して、自身が到達しようとしているかもしくは（第二タイルが巡回可能かどうかを判定する目的で）検査をしようとしている、第二タイルの中央に達するであろう方向である。これは、この２つの隣接するタイルの中央を結ぶ（理論的な）直線が、２つのタイルの間の境界線と垂直（直角）であると仮定しており、このことはデータ・センタでは一般的である。
【００４２】
データ・センタでの状況において、視覚コンポーネントは、タイルの境界を検出すること、タイルの境界からのロボットの距離（およびこれによりタイルの中央からのロボットの距離）を算定すること、次のタイルの境界と直角をなすラインに対しロボットが現在なす角度を算定すること、および、ロボットが前進する方向の次のタイルが塞がれているのかまたは見ることができるのかどうかを判定すること、に特化される。ある例示的な実施形態よれば、ロボットは、例えば、タイルの境界、およびタイルが見えるかまたは遮られているかどうかを自動的に判定する。このタスクを実施させるためのロボットのプログラミングは、当業者には明らかであろう。従って本明細書ではこれ以上説明しない。方向付けのため、ロボットは、例えばカメラなどの視覚コンポーネントが面する方向から算定された進行方向をとる。また、この進行方向は、ロボットが前進移動を命令されたときの前輪の方向とも一致する（すなわち、ロボットが回転するときは、回転するのは車輪だけでなくアセンブリ全体が回転する）。
【００４３】
タイルで格子化されたレイアウトがある保証のないもっと一般的な施設では、一つの選択肢として、アルファ線またはベータ線を放射する粒子の細かな長方形格子（例えば、６インチ（１５．２４センチメートル）×６インチのセル寸法の格子）を設けてタイルをシミュレートし、続いて（バックトラッキング後）、ロボットに、搭載されたウェブカメラを使うのと類似の方法を使って、アルファ線またはベータ線放射粒子の格子を検出させるやり方がある。ウェブカメラ自体はアルファ線またはベータ線粒子を検出することはできないであろうが、（例えば、薄膜ガイガー・ミュラー・カウンタなどのアルファ線またはベータ線検出器を使って）アルファ線またはベータ線粒子の位置が判明したならば、ウェブカメラがそのアルファ線またはベータ線粒子周り近辺のスナップショットを撮り、ロボットは、該ロボットが次回に再巡回で妥当な仕事ができるように、アルファ線またはベータ線粒子によって決まる正方形および周辺の記録を保持しておくことができよう。
【００４４】
この人為的に設けた格子すなわち仮想タイルは、ロボットがいる場所を示し、必要に応じ、例えば、最良優先Ａ＊探索（特許文献２を参照）、または仮想タイルに対する縦型探索ツリーを追跡し、当該環境の完全な巡回を確実にする役割を果たすことができる。縦型探索ツリーは、グラフによる、計画された完全な探査を追跡するソフトウェア・データ構造体である。これら仮想タイルの場合、グラフのノードは仮想タイルであり、縦型探索ツリーの一つの実装において、タイル・レイアウト中で２つのタイルが隣り合っている場合、言い換えれば、ロボットがタイル１からタイル２へ他のタイルを通過せずに巡回が可能な場合、これらタイルはグラフの縁で繋がれている。
【００４５】
例示的な一実施形態において、ビルディング全体にわたり、自由な動きを備えるため、ロボットはバッテリ電力で走行する。好ましくは、このバッテリは、再充電可能であり、このシステムは一つ以上の充電ステーション（図示せず）をさらに含む。しかして、ロボットが走査中に電力が低下した場合、ロボットは充電ステーションに行き、再充電し、その後、最後に巡回した場所で走査を再開することができる（以下を参照）。再充電のため充電ステーションに戻る移動ロボットを構成する技法は、当業者には既知であり、しかして本明細書ではこれ以上説明しない。
【００４６】
本教示によって、ビルディングの諸方へのロボット（群）の運動を、必要なセンサ測定を同時に行いながら、調整するため用いることが可能な技法を以下に説明する。例えば、あるデータ・センタでは、ロボット（群）の運動の調整は、典型的データ・センタのフロアは全体が業界規格の２フィート（６１センチメートル）×２フィートのタイルから成るという事実によっていくらかやり易くなる。この場合、ロボットの位置特定は、静止画像（当該フロアのロボットによって提供される（前述参照））が正確に解析可能でそれによりタイルの境界が算定可能であれば、映像手段を使って達成することができる。単なる例として、コンピュータまたはその運営担当者は、ロボット（群）が撮った静止画像を解析することができ、所与のタイルの所在場所の外側境界の位置を算定することが可能である。
【００４７】
以下の説明で明らかとなるように、本システムは、業界規格の直線的なタイルの境界の認識を利用して、システムにとって今まで未知だった見取り図を正確に生成することができる。
【００４８】
ある例示的な実施形態よれば、本システムは、同時位置測定およびマップ作成（ＳＬＡＭ：Ｓｉｍｕｌｔａｎｅｏｕｓ  Ｌｏｃａｌｉｚａｔｉｏｎ  ａｎｄ  Ｍａｐｐｉｎｇ）の方法を使用する搭載型のソナー、レーザ、および映像装置の一つ以上を用いる、既存の位置把握技術を利用する。このＳＬＡＭプロセスの要は、ロボットの位置を更新するために環境を使うことである。ロボットの走行距離計測法は、ロボットの位置の推量を得るのに用いることができるが、一般に、時間とともに誤差または「ドリフト」が累積されるので、ロボットの位置を取得するのに単独では依存できない。走行距離計測法に加え、レーザ、ソナー、もしくは映像装置またはこれらの組み合わせを使ってロボットの位置を補正することができる。これは、拡張カルマンフィルタを使い、環境の特徴を抽出し、ロボットが諸方に移動するにつれこれらの特徴を再観測することによって達成される。ＳＬＡＭの論文では、これらの特徴は通常「ランドマーク」と呼ばれる。拡張カルマンフィルタは、ロボットの位置の不確かさ、および環境中で観察したランドマークの不確かさの推量を追跡する。タイル境界によって誘導される、ウェブカメラを使ってデータ・センタ（または他のビルディング／施設）の設備周辺を巡回するロボット巡回のこの事例は、もっと一般的なＳＬＡＭフレームワークの中の単なる特殊な一ケースである。
【００４９】
ある特定の場所で読み取りが採取されたならば、ロボットは、本発明の巡回技法を用いて次の場所に移動する。
【００５０】
本明細書で説明した技法は、これまで本明細書でいかなる詳細も検討してこなかったが実用的な意義のある事項についても当然拡大適用される。すなわち、
（ｉ）ロボット群が変化する速度を有する；
（ｉｉ）ロボットが、相異なる品質ファクタを有する、すなわちロボットＲｉは、一部の一定標準のロボットＲよりも、ｆｉ倍、より効率的な仕事をし、またはその監視においてより徹底している。但し、全ての監視場所が、最小限の合計品質ファクタでカバーされなければならない；
（ｉｉｉ）環境のサブ領域は相異なる優先順位を有する；
も適用される。
【００５１】
図２および５は、例示的なステップのシーケンスを示しているが、これらのシーケンスを変えることが可能な本発明の実施形態もある。本発明の別の実施形態として、アルゴリズムの様々な順列が考えられる。
【００５２】
本発明の例示的諸実施形態を、ソフトウェア・プログラム中の処理ステップに関連させて説明してきたが、当業者には当然のことながら、様々な機能を、ソフトウェア・プログラムの中の、プログラムされた汎用コンピュータによるハードウェア、回路エレメントまたは状態マシンの中の、あるいはソフトウェアおよびハードウェア両方の組み合わせの中の、処理ステップとして、デジタル領域の中に実装することが可能である。かかるソフトウェアは、例えば、デジタル信号プロセッサ、特定用途向け集積回路、マイクロコントローラ、または汎用コンピュータなどのハードウェア・デバイス中で用いることができる。かかるハードウェアおよびソフトウェアは、集積回路内に実装された回路中に具現化することが可能である。
【００５３】
当業者には当然のことながら、本発明の態様は、システム、方法、またはコンピュータ・プログラム製品として具現化することができる。したがって、本発明の態様は、全体がハードウェアの実施形態、全体がソフトウェアの実施形態（ファームウェア、常駐ソフトウェア、マイクロコードなどを含む）、あるいは、ソフトウェア態様およびハードウェア態様を組み合わせた実施形態の形を取ることができ、これらは一般に本明細書では全て「回路」、「モジュール」、または「システム」と称することがある。さらに、本発明の態様は、コンピュータ可読プログラム・コードが中に具現化されている一つ以上のコンピュータ可読媒体中に具体化されたコンピュータ・プログラム製品の形を取ることも可能である。
【００５４】
一つ以上のコンピュータ可読媒体（群）の任意の組み合わせを用いることができる。コンピュータ可読媒体は、コンピュータ可読信号媒体、またはコンピュータ可読ストレージ媒体とすることができる。コンピュータ可読ストレージ媒体は、例えば、以下に限らないが、電子的、磁気的、光学的、電磁気的、赤外的、または半導体の、システム、装置、もしくはデバイス、あるいはこれらの任意の適切な組み合わせであり得る。コンピュータ可読ストレージ媒体のさらに具体的な例（非包括的リスト）には、一つ以上の配線を有する電気接続、携帯型コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ：ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）、読み取り専用メモリ（ＲＯＭ：ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｙ）、消去可能プログラム可能読み取り専用メモリ（ＥＰＲＯＭ：ｅｒａｓａｂｌｅ  ｐｒｏｇｒａｍｍａｂｌｅ  ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｙまたはフラッシュ・メモリ）、光ファイバ、携帯型コンパクト・ディスク読み取り専用メモリ（ＣＤ−ＲＯＭ：ｃｏｍｐａｃｔ  ｄｉｓｃ  ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｙ）、光ストレージ・デバイス、磁気ストレージ・デバイス、または前述の任意の適切な組み合わせが含まれよう。本文書の文脈において、コンピュータ可読ストレージ媒体は、命令実行システム、装置、もしくはデバイスによって、またはこれらに関連させて使用するためのプログラムを、包含または格納できる任意の有形媒体であり得る。
【００５５】
コンピュータ可読信号媒体には、例えばベースバンド中にまたは搬送波の一部として具現化されたコンピュータ可読プログラム・コードを有する、伝播データ信号を含めることができる。かかる伝播信号は、以下に限らないが、電磁気的、光学的、またはこれらの任意の適切な組み合わせを含め、さまざまな形態の任意の形を取ることが可能である。コンピュータ可読信号媒体は、コンピュータ可読ストレージ媒体ではないが、命令実行システム、装置、もしくはデバイスによって、またはこれらに関連させて使用するためのプログラムの通信、伝播、または伝送が可能な任意のコンピュータ可読媒体であり得る。
【００５６】
コンピュータ可読媒体上に具現化されたプログラム・コードは、以下に限らないが、無線、有線、光ファイバ・ケーブル、ＲＦなど、または前述の任意の適した組み合わせを含め、任意の適切な媒体を用いて送信することができる。
【００５７】
本発明の態様のオペレーションを実行するためのコンピュータ・プログラム・コードは、Ｊａｖａ（Ｒ）、Ｓｍａｌｌｔａｌｋ（Ｒ）、Ｃ＋＋などのオブジェクト指向プログラミング言語、あるいは、“Ｃ”プログラミング言語または類似のプログラミング言語などの従来式手続き型プログラミング言語を含め、一つ以上のプログラミング言語の任意の組み合わせで記述することができる。このプログラム・コードは、スタンドアロン・ソフトウェア・パッケージとしてユーザのコンピュータで専ら実行することも、ユーザのコンピュータで部分的に実行することもでき、一部をユーザのコンピュータで一部を遠隔コンピュータで実行することもでき、あるいは遠隔のコンピュータまたはサーバで専ら実行することもできる。後者の場合は、ローカル・エリア・ネットワーク（ＬＡＮ：ｌｏｃａｌ  ａｒｅａ  ｎｅｔｗｏｒｋ）または広域ネットワーク（ＷＡＮ：ｗｉｄｅ  ａｒｅａ  ｎｅｔｗｏｒｋ）を含む任意の種類のネットワークを介して、遠隔コンピュータをユーザのコンピュータに接続することもでき、あるいは（例えばインターネット・サービス・プロバイダを使いインターネットを介し）外部のコンピュータへの接続を行うこともできる。
【００５８】
本発明の実施形態による方法、装置（システム）およびコンピュータ・プログラム製品のフローチャート図もしくはブロック図またはその両方を参照しながら、本発明の態様を上記で説明してきた。当然のことながら、フローチャート図もしくはブロック図またはその両方の各ブロック、および、フローチャート図もしくはブロック図またはその両方中のブロックの組み合わせは、コンピュータ・プログラム命令によって実装することが可能である。これらのコンピュータ・プログラム命令を、汎用コンピュータ、特殊用途コンピュータ、またはマシンを形成する他のプログラム可能データ処理装置のプロセッサに提供し、そのコンピュータまたは他のプログラム可能データ処理装置のプロセッサを介して実行されるこれらの命令が、フローチャートもしくはブロック図またはその両方のブロックまたはブロック群中に特定されている機能群／動作群を実装するための手段を生成するようにすることができる。
【００５９】
また、これらのコンピュータ・プログラム命令を、コンピュータ、他のプログラム可能データ処理装置、または他のデバイスに対し特定の仕方で機能するよう命令することができるコンピュータ可読媒体に格納し、そのコンピュータ可読媒体に格納された命令が、フローチャートもしくはブロック図またはその両方のブロックまたはブロック群中に特定されている機能／動作を実装する命令群を包含する製造品を作り出せるようにすることができる。
【００６０】
さらに、コンピュータ・プログラム命令を、コンピュータ、他のプログラム可能データ処理装置、または他のデバイスにロードし、そのコンピュータ上、他のプログラム可能装置上、または他のデバイス上で一連のオペレーション・ステップを実行させて、コンピュータ実装のプロセスを作り出し、当該コンピュータ上または他のプログラム可能装置上で実行される命令が、フローチャートもしくはブロック図またはその両方のブロックまたはブロック群中に特定されている機能群／動作群を実装するためのプロセスを提供するようにすることも可能である。
【００６１】
図１５は、本発明の諸プロセスを実装できるロボット巡回システム１４００のブロック図である。図１５に示されるように、メモリ１４３０は、本明細書で開示されたロボット巡回の方法、ステップ、および機能（図１５中に集合的に１４８０として示されている）を実装するようにプロセッサ１４２０を設定する。メモリ１４３０は、分散型とすることもまたはローカル型とすることもでき、プロセッサ１４２０は分散型とすることもまたは単独型とすることもできよう。メモリ１４３０は、電気的、磁気的、または光学的メモリ、あるいはこれらの任意の組み合わせ、または他の種類のストレージ・デバイスとして実装することができよう。なお、プロセッサ１４２０を構成する各分散型プロセッサは、通常、それ自体のアドレス可能メモリ空間を包含する。また、コンピュータ・システムの一部または全部を、パーソナル・コンピュータ、ラップトップ・コンピュータ、ハンドヘルド・コンピューティング・デバイス、特定用途向け回路、または汎用集積回路の中に組み込むことが可能である。
【００６２】
図面のフローチャートおよびブロック図は、本発明のさまざまな実施形態による、システム、方法、およびコンピュータ・プログラム製品から可能となる実装のアーキテクチャ、機能、およびオペレーションを示している。この点に関し、フローチャートまたはブロック図中の各ブロックは、特定の論理機能（群）を実装するための一つ以上の実行可能命令を含む、モジュール、セグメント、またはコードの部分を表し得る。また、一部の別の実装においては、ブロック中に記載された機能が、図面に記載された順序を外れて行われ得ることに留意すべきである。例えば、連続して示された２つのブロックが、関与する機能によって、実際にはほぼ同時に実行されることがあり、時にはこれらのブロックが逆の順序で実行されることもあり得る。さらに、ブロック図もしくはフローチャート図またはその両方の各ブロック、およびブロック図もしくはフローチャート図またはその両方中のブロック群の組み合わせは、特定の機能または動作を実施する特殊用途ハードウェア・ベースのシステム、または特殊用途ハードウェアとコンピュータ命令との組み合わせによって実装可能なことにも留意すべきである。
【００６３】
本明細書に示され説明された諸実施形態および変形案は、本発明の原理の単なる例示であり、当業者によって本発明の範囲および趣旨から逸脱することなく様々な修改が実装可能であることを理解すべきである。
【図１】
2015505410.tif 000003
【図２】
2015505410.tif 000004
【図３】
2015505410.tif 000005
【図４】
2015505410.tif 000006
【図５】
2015505410.tif 000007
【図６】
2015505410.tif 000008
【図７】
2015505410.tif 000009
【図８】
2015505410.tif 000010
【図９】
2015505410.tif 000011
【図１０】
2015505410.tif 000012
【図１１】
2015505410.tif 000013
【図１２】
2015505410.tif 000014
【図１３】
2015505410.tif 000015
【図１４】
2015505410.tif 000016
【図１５】
2015505410.tif 000017
【手続補正書】
【提出日】平成26年10月28日(2014.10.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ある環境の中で複数のロボットを巡回させる、コンピュータに実行させる方法であって、
前記コンピュータが、前記ロボットの各々に対する巡回緩衝域を算定するステップと、
前記コンピュータが、前記複数のロボットの各々に、他のロボットから前記巡回緩衝域のサイズを維持しながら、前記環境内を巡回することを可能にさせるステップと、
を含み、
前記巡回緩衝域の各々のサイズは、前記環境の全体に対する、巡回予定として残っている前記環境のパーセンテージに基づいて時間とともに低減される、
方法。
【請求項２】
前記巡回緩衝域が、巡回予定として残っている前記環境の前記パーセンテージに直接比例して低減される、請求項１に記載の方法。
【請求項３】
前記複数ｋ個の巡回緩衝域が、前記環境内部にｋ個のほぼ均一な巡回緩衝域を適合させるような、開始点巡回緩衝域に初期化される、請求項１又は２に記載の方法。
【請求項４】
前記環境の全体に対する、巡回予定として残っている前記環境のパーセンテージが推量された値である、請求項１から３のいずれかに記載の方法。
【請求項５】
前記巡回緩衝域の少なくとも一つの前記サイズが、前記対応するロボットの速度に基づく、請求項１から４のいずれかに記載の方法。
【請求項６】
前記巡回緩衝域の各々が、前記対応するロボットの周りの所与の半径の円である、請求項１から４のいずれかに記載の方法。
【請求項７】
ある環境の中で複数のロボットを巡回させる、コンピュータに実行させる方法であって、
前記コンピュータが、前記環境を複数の個別領域に離散化するステップと、
前記コンピュータが、幅優先探索を用いて、典型的環境の中で前記複数のロボットの一つが探査することになる次の未巡回個別領域を算定するステップと、
を含む方法。
【請求項８】
前記コンピュータは、前記複数のロボットの各々が備える、請求項７に記載の方法。
【請求項９】
前記コンピュータは、前記のロボットの外部のコンピュータであり、前記算定するステップが少なくとも一つのプロセッサによって行われ、前記算定するステップの結果が前記コンピュータから前記複数のロボットの各々に提供される、請求項７に記載の方法。
【請求項１０】
前記複数の個別領域が複数の実際のまたは仮想のタイルを含む、請求項７から９のいずれかに記載の方法。
【請求項１１】
前記環境が既知の環境を含む、請求項７から１０のいずれかに記載の方法。
【請求項１２】
前記算定するステップは、各ロボットが、前記個別領域の一つの中に一度に全ての可能な方向へ仮定的一ステップを進めるステップと、一つのロボットが前記次の未巡回個別領域に達するまで、幅優先探索ツリーの経路を維持するステップとをさらに含む、請求項７から１１のいずれかに記載の方法。
【請求項１３】
前記算定するステップは、前記一つのロボットが、前記複数のロボットの他のロボットに、前記一つのロボットが前記幅優先探索ツリー中で前記次の未巡回個別領域に到達したことを宣言するステップと、前記複数のロボットの前記他のロボットが、前記一つのロボットとの衝突があるかどうかを判定するステップと、前記一つのロボットが前記幅優先探索ツリーを前記次の未巡回個別領域の単一ポイントに折り畳むステップと、をさらに含む、請求項１２に記載の方法。
【請求項１４】
ある環境の中で複数のロボットを巡回させるための装置であって、前記装置は、
メモリと、
前記メモリに連結された少なくとも一つのプロセッサとを備え、
前記プロセッサは、前記ロボットの各々に対する巡回緩衝域を算定し、
前記複数のロボットの各々が、他のロボットから前記巡回緩衝域のサイズを維持しながら、前記環境内を巡回することを可能にさせ、
前記巡回緩衝域の各々のサイズは、前記環境の全体に対する、巡回予定として残っている前記環境のパーセンテージに基づいて時間とともに低減される、
装置。
【請求項１５】
前記ロボットが、一つ以上のセンサを備え、前記センサを用いて前記環境中で一つ以上の測定を行う、請求項１４に記載の装置。
【請求項１６】
ある環境の中で複数のロボットを巡回させるための装置であって、
メモリと、
前記メモリに連結された少なくとも一つのプロセッサとを備え、
前記プロセッサは、前記環境を複数の個別領域に離散化し、
幅優先探索を用いて、例示の環境の中で前記複数のロボットの一つが探査することになる次の未巡回個別領域を算定する、
装置。
【請求項１７】
前記装置は、前記複数のロボットの各々が備える、請求項１６に記載の装置。
【請求項１８】
前記装置は、前記複数のロボットの外部の装置であり、前記算定が少なくとも一つのプロセッサによって行われ、前記判定の結果が前記装置から前記複数のロボットの各々に提供される、請求項１６に記載の装置。
【請求項１９】
コンピュータに請求項１から１３のいずれかに記載の方法を実行させるコンピュータ・プログラム。
【国際調査報告】
2015505410.tif 000018