(57)【要約】本発明は、全平面を複数の部分平面に分割し、各部分平面を各移動ユニットに割り当てる手段に関する。まず全平面を分割して部分平面が定められ、これが１つの移動ユニットに保留付きで割り当てられる。当該の移動ユニットは部分平面の割り当てを示す割り当て情報を送信する。当該の移動ユニットが少なくとも１つの別の移動ユニットから部分平面の割り当て拒否を示す割り当て拒否情報を受信しない場合、保留は解除され、部分平面の割り当てが有効となる。割り当て拒否情報を受信した場合には保留は解除されるが部分平面の割り当ては無効となる。
2005505434.tif 000002
【特許請求の範囲】
【請求項１】
全平面を複数の部分平面に分割し、各部分平面を共同作業用の各移動ユニットに割り当てる
部分平面を移動ユニットに割り当てる方法において、
全平面を分割して部分平面を定め、これを複数の移動ユニットのうちの１つに保留付きで割り当て、
当該の移動ユニットは部分平面の割り当てを示す割り当て情報を送信し、
当該の移動ユニットが少なくとも１つの別の移動ユニットから部分平面の割り当て拒否を示す割り当て拒否情報を受信しない場合、保留を解除して部分平面の割り当てを有効とし、割り当て拒否情報を受信した場合には保留を解除したうえで部分平面の割り当てを無効とする
ことを特徴とする部分平面を移動ユニットに割り当てる方法。
【請求項２】
１つの移動ユニットが所定の部分平面に対して設定された割り当て距離を有するときまたは設定された割り当て距離よりも小さな距離を有するとき、当該の部分平面の決定および／または割り当てを保留付きで行う、請求項１記載の方法。
【請求項３】
１つの移動ユニットが所定の部分平面を要求することにより当該の部分平面の決定および／または割り当てを保留付きで行う、請求項１または２記載の方法。
【請求項４】
複数の移動ユニットが他の部分平面で作業しているあいだに当該の部分平面の決定および／または割り当てを保留付きで行う、請求項１から３までのいずれか１項記載の方法。
【請求項５】
１つの移動ユニットに所定の部分平面を割り当てる際にコネクティビティグラフを使用する、請求項１から４までのいずれか１項記載の方法。
【請求項６】
割り当て情報は割り当てられる部分平面の重要度情報を有しており、該重要度情報は当該の移動ユニットに対する部分平面の割り当てがどれほどの重要性を有するかを示す、請求項１から５までのいずれか１項記載の方法。
【請求項７】
当該の可動ユニットに割り当てられる部分平面と他の複数の可動ユニットに割り当てられる部分平面とを１つの作業区域とする、請求項１から６までのいずれか１項記載の方法。
【請求項８】
作業区域ができるだけコンパクトな領域となるように保留付きで部分平面の割り当てを行う、請求項７記載の方法。
【請求項９】
ルートプランニングプロセスを使用して当該の作業区域に対して作業ルートを求める、請求項７または８記載の方法。
【請求項１０】
少なくともそれぞれの可動ユニットに割り当てられた部分平面の入力された全平面のマップを各移動ユニットに記憶させる、請求項１から９までのいずれか１項記載の方法。
【請求項１１】
少なくとも１つの移動ユニットのマップに割り当てられた部分平面を入力する、請求項１０記載の方法。
【請求項１２】
２つの移動ユニットがそれぞれ設定された通信距離にあるときまたは設定された通信距離よりも小さい距離にあるとき、当該の２つの移動ユニットは（グローバルな通信網の必要なしに）情報を相互に交換する、請求項１から１１までのいずれか１項記載の方法。
【請求項１３】
情報交換中に当該の２つの移動ユニットのマップ間の補償を行う、請求項１２記載の方法。
【請求項１４】
１つの移動ユニットに割り当てられた部分平面が他の移動ユニットにすでに割り当てられている場合、統合プロセスを行う、請求項１から１３までのいずれか１項記載の方法。
【請求項１５】
複数の清掃ロボットによる全平面の清掃に使用し、ここで複数の可動ユニットは複数の清掃ロボットであり、清掃すべき全空間は全平面である、請求項１から１４までのいずれか１項記載の方法。
【請求項１６】
全平面を複数の部分平面に分割し、各部分平面を各移動ユニットに割り当てる
部分平面を移動ユニットに割り当てる装置において、
全平面を分割して部分平面を定め、これを複数の移動ユニットのうちの１つに保留付きで割り当てる割り当てユニットと、
部分平面の割り当てを示す割り当て情報を送信可能な通信ユニットとを有しており、
前記割り当てユニットにより、当該の移動ユニットが少なくとも１つの別の移動ユニットから部分平面の割り当て拒否を示す割り当て拒否情報を受信しない場合、保留を解除して部分平面の割り当てが有効とされ、割り当て拒否情報を受信した場合には保留を解除したうえで部分平面の割り当てが無効とされる
ことを特徴とする部分平面を移動ユニットに割り当てる装置。
【請求項１７】
請求項１記載の部分平面を移動ユニットに割り当てる方法の全ステップを実行するためにコンピュータ上で動作する
ことを特徴とするプログラムコード手段を備えたコンピュータプログラム。
【請求項１８】
コンピュータで読み出し可能なデータ担体に記憶されている、請求項１７記載のコンピュータプログラム。
【請求項１９】
機械で読み出し可能な担体に記憶されたプログラムコード手段を備えている
コンピュータプログラム製品において、
請求項１記載の部分平面を移動ユニットに割り当てる方法の全ステップを実行するためにコンピュータ上で動作する
ことを特徴とするコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は全平面を部分平面に分割してそれぞれの部分平面をそれぞれの移動ユニットに割り当てる手段に関する。
【０００２】
全平面を複数の部分平面に分割し、これを複数の移動ユニットのそれぞれに割り当てることは、複数の移動ユニットの共同作業によって大きな全平面の作業を行う分野、例えば清掃ロボットによるホールの清掃などの際に一般に行われている。これについては引用文献［１］を参照されたい。
【０００３】
全平面を部分平面へ分割し、これを複数のロボットに割り当てる手段として、種々の手法およびアプローチが使用されている。例えばスタティックな手法およびアプローチも使用されているし、ダイナミックな手法およびアプローチも使用されている。
【０００４】
スタティックな手法における分割および割り当てでは、各移動ユニットは複数の移動ユニットによる共同作業の開始前に予め定められた部分平面に固定に割り当てられる。この割り当ては作業中には変更されない。
【０００５】
こうしたスタティックな手法のほとんどは全平面を部分平面へ分割するプロセスにおいて相違しているだけであり、その幾つかは引用文献［２］［３］［４］［５］［６］［７］から知られる。
【０００６】
引用文献［２］［３］からは全平面を同じ大きさのｎ個の部分平面へ分割することが知られる。このときそれぞれの部分平面が所定のポイント、すなわち各部分平面に属するロボットの移動の始点を含んでいなければならない。
【０００７】
引用文献［２］［３］から知られるスタティックな手法は数学的には正確であるが、実際は不要な部分平面またはロボットの不要な作業区域が生じてしまいやすい。
【０００８】
また引用文献［４］から知られるスタティックなアプローチでは、できるだけ鋭角を含まずかつ大きさが同じである部分平面が全平面のなかから探索され求められる。これによりロボットは前述のケースよりも良好に作業することができる。
【０００９】
引用文献［５］［６］［７］から知られるスタティックな手法では、部分平面はできるだけ小さな径、ひいてはできるだけ小さい周を有するように定められる。これによりそれぞれ１つずつの部分平面で作業するロボットが部分平面の縁部へほとんど進行しないよう意図され、衝突の危険が低減される。
【００１０】
ただしこれらの周知のスタティックな手法には、特に部分平面が移動ユニットに固定に割り当てられるという特徴において、重大な欠点が存在する。すなわち、この種の手法はきわめて柔軟性に乏しく、新たな状況にダイナミックに適合させることができない。例えば１つのロボットが故障したとき、この手法では他のロボットが故障したロボットの作業すべき部分平面を引き継ぐことができず、当該の部分平面は作業されずに残ってしまう。
【００１１】
これに対してダイナミックな手法では部分平面の分割および割り当てがダイナミックに行われる。ここでは部分平面は移動ユニットの活動中に分割される。部分平面の割り当ては相互に時間のずらされた複数の段階に分けて行われる。
【００１２】
こうしたダイナミクスから、移動ユニットの活動中に各移動ユニットに割り当てられる部分平面をダイナミックに変更することができる。したがってこの場合には移動ユニットに対して部分平面は予め固定には定義されず、移動ユニットの活動中に周囲条件および／または境界条件にダイナミックに適合するように定められる。
【００１３】
こうしたダイナミックな部分平面の分割および割り当ての欠点は、変更情報を相互に伝達しあうために、移動ユニットが規則的に相互通信のコンタクトを取らなければならないということである。この通信は通常は移動ユニットどうしが相互に通信するグローバルな通信網を介して実現される。
【００１４】
少なくとも部分的にダイナミックな手法の１つが引用文献［８］が知られている。
【００１５】
引用文献［８］から知られるハイブリッドダイナミックプロセスでは、スタティックなアプローチとダイナミックなアプローチとが組み合わされており、全平面は作業の開始前に（ｎ＋１）個の部分平面に分割される。ここでｎ個の部分平面は上述のケースと同じスタティックな手法で各移動ユニットへ分配され、（ｎ＋１）番目の部分平面は作業の終了時にダイナミックに移動ユニット間で分配される。
【００１６】
ただしこのハイブリッドダイナミックプロセスではスタティックな手法の部分が大きいので、やはり上述のスタティックな手法の欠点が存在する。
【００１７】
したがって本発明の課題は、全平面を部分平面に分割してそれぞれの部分平面をそれぞれの移動ユニットに割り当てる手段を提供し、これをフレキシブルに、移動ユニットが全平面を作業しているあいだに変化しうる境界条件に適合可能にすることである。
【００１８】
本発明の課題は、部分平面を移動ユニットに割り当てる本発明の方法および装置、プログラムコード手段を備えたコンピュータプログラム、およびコンピュータプログラム製品によって解決される。
【００１９】
全平面を複数の部分平面に分割し、各部分平面を共同作業用の各移動ユニットに割り当てる本発明の方法では、まず全平面を分割して部分平面が定められ、これが複数の移動ユニットのうちの１つに保留付きで割り当てられる。次に当該の移動ユニットは部分平面の割り当てを示す割り当て情報を送信する。ここで当該の移動ユニットが少なくとも１つの別の移動ユニットから部分平面の割り当て拒否を示す割り当て拒否情報を受信しない場合、保留は解除され、部分平面の割り当てが有効とされる。また割り当て拒否情報を受信した場合には保留が解除されたうえで部分平面の割り当てが無効とされる。
【００２０】
全平面を複数の部分平面に分割し、各部分平面を各共働移動ユニットに割り当てる本発明の装置は、全平面を分割して部分平面を定め、これを複数の移動ユニットのうちの１つに保留付きで割り当てる割り当てユニットを有している。さらに本発明の装置は、部分平面の割り当てを示す割り当て情報を送信可能な通信ユニットとを有している。ここで割り当てユニットは、当該の移動ユニットが少なくとも１つの別の移動ユニットから部分平面の割り当て拒否を示す割り当て拒否情報を受信しない場合、保留を解除して部分平面の割り当てを有効とし、割り当て拒否情報を受信した場合には保留を解除したうえで部分平面の割り当てを無効とするように構成されている。
【００２１】
本発明のプログラムコード手段を備えたコンピュータプログラムは、部分平面を移動ユニットに割り当てる本発明の方法の全ステップを実行するためにコンピュータ上で動作する。
【００２２】
機械で読み出し可能な担体に記憶されたプログラムコード手段を備えている本発明のコンピュータプログラム製品は、部分平面を移動ユニットに割り当てる本発明の方法の全ステップを実行するためにコンピュータ上で動作する。
【００２３】
本発明では、非集中型システム、すなわち多数のシステムに分散されたコンピュータプログラムまたはコンピュータプログラム製品を用いてもよい。つまりこの場合には本発明は多数の個別のコンピュータプログラムまたはコンピュータプログラム製品として実現され、その全体または全体的な共同作用が本発明の方法となる。
【００２４】
本発明の装置、部分平面を移動ユニットに割り当てる本発明の方法の全ステップを実行するためにコンピュータ上で動作する本発明のプログラムコード手段を備えたコンピュータプログラム、および部分平面を移動ユニットに割り当てる本発明の方法の全ステップを実行するためにコンピュータ上で動作する機械で読み出し可能な担体に記憶されたプログラムコード手段を備えている本発明のコンピュータプログラム製品は、特に本発明の方法および以下に説明するその実施形態を実行するのに適している。
【００２５】
本発明の有利な実施形態は従属請求項から得られる。以下に説明する実施形態は本発明の方法にも装置にも関係している。
【００２６】
本発明および以下に説明するその実施形態はソフトウェアとしてもハードウェア（例えば専用電子回路を使用した回路装置）としても実現可能である。また本発明および以下に説明するその実施形態は、これを実行するプログラムコード手段を備えたコンピュータプログラムをコンピュータで読み出し可能な記憶媒体に記憶させることより実現することもできる。さらに本発明および以下に説明するその実施形態は、これを実行するプログラムコード手段を記憶媒体に記憶させたコンピュータプログラム製品により実現することもできる。
【００２７】
本発明の１つの実施形態では、１つの移動ユニットが所定の部分平面に対して設定された割り当て距離または設定された割り当て距離よりも小さな距離を有するとき、当該の部分平面の保留付きの決定および／または割り当てが行われる。
【００２８】
当該の部分平面の保留付きの決定および／または割り当ては１つの移動ユニットが所定の部分平面を要求することにより能動的に行ってもよいし、また第３者が割り当てることによって受動的に行ってもよい。
【００２９】
本発明の別の実施形態では、複数の移動ユニットが他の部分平面で作業しているあいだに当該の部分平面の保留付きの決定および／または割り当てが行われる。これにより部分平面の作業の中断または遅延が回避される。
【００３０】
また割り当て情報は割り当てられる部分平面の重要度情報を有しており、この重要度情報は当該の移動ユニットに対する部分平面の割り当てがどれほどの重要性を有するかを示すものである。
【００３１】
１つの移動ユニットに所定の部分平面を割り当てる際に、引用文献［９］から知られるコネクティビティグラフを使用することもできる。
【００３２】
また作業上、作業区域ができるだけコンパクトな領域となるように保留付きの部分平面の割り当てを決定すると有利である。
【００３３】
このとき当該の可動ユニットに割り当てられる部分平面と他の複数の可動ユニットに割り当てられる各部分平面とを合わせて１つの作業区域とすることができる。
【００３４】
当該の作業区域に対しては、ルートプランニングプロセスを使用して作業ルートを求めることができる。ルートプランニングプロセスについては例えば引用文献［１２］または［１３］から知られている。
【００３５】
また作業上、各移動ユニットに少なくともそれぞれの可動ユニットに割り当てられた部分平面の入力された全平面のマップを記憶させると有利である。マップには割り当てられた部分平面が入力される。
【００３６】
本発明の別の実施形態では、それぞれ２つずつの移動ユニットが通信可能状態にあるとき、これらのユニットが情報を相互に交換することにより、複数のユニットのあいだでの情報通信が行われる。これは特に、メッセージの送受信を行えるように構成された移動ユニットのうちの２つがそれぞれ設定された通信距離または設定された通信距離よりも小さい距離にあるとき、当該の２つの移動ユニットが情報を相互に交換することにより達成される。
【００３７】
このようにすればグローバルな通信網は不要である。情報は各移動ユニットを順次に転送される。
【００３８】
情報交換では当該の２つの移動ユニットのマップ間の補償が行われる。
【００３９】
さらに１つの移動ユニットに割り当てられた部分平面と既に他の移動ユニットに割り当てられた部分平面とが重なっている場合、統合プロセスが行われる。統合プロセスにより当該の部分平面は最終的に２つの移動ユニットの一方に割り当てられる。
【００４０】
本発明の１つの実施形態では、上述の手段は複数の清掃ロボットによる全平面の清掃に使用される。ここで複数の可動ユニットは複数の清掃ロボットであり、また清掃すべき全面が全平面である。
【００４１】
本発明の実施例を図示し、以下に詳細に説明する。
【００４２】
図１には清掃すべき空間１００を本発明の実施例にしたがって複数のポリゴン１０１へ分割する様子が示されている。図２のＡには本発明の実施例にしたがって複数のポリゴン１０１，２０２，２０３へ分割された清掃すべき空間１００の一部２００が示されている。図２のＢには本発明の実施例にしたがって分割された清掃すべき空間の一部のコネクティビティグラフ２１０が示されている。図３には、３つの清掃ロボット３０４によって清掃すべき空間１００に対して、これらのロボットの通信距離３０５、割り当て済かつ清掃済の部分平面３０１、割り当て済であるが清掃の済んでいない部分平面３０２、および割り当ての行われていない部分平面３０３が本発明の実施例にしたがって示されている。図４には２つの別個の部分平面４０１（ポリゴン）が本発明の実施例にしたがって示されている。図５には清掃されるスーパーマーケットの見取図が示されている。図６にはシミュレーション結果の表６００が示されている。図７には部分平面の割り当て方法のステップ７０１〜７０５が本発明の実施例にしたがって示されている。
【００４３】
実施例：複数の清掃ロボットによる所定の空間平面の清掃
以下に説明する実施例は、清掃すべき空間をダイナミックに分割する手法に基づいている。
【００４４】
本発明の手段の基礎
以下に説明する本発明の手段のコンセプトは、清掃すべき空間１００を個々のポリゴンすなわち部分平面１０１へ図１に示されているように分割することに基づいている。個々のロボットはこれらのポリゴン１０１に割り当てられ、これを清掃する。ポリゴン１０１はここでは１つのロボットが１つの所定のポリゴン１０１の清掃を担当し、これを既知とすることを意味する。
【００４５】
従来の他のダイナミックな手法とは異なり、以下に説明する本発明の手段では、個々のロボットがつねに相互に通信可能な位置にあることを前提としない。したがってグローバルな通信網は必要ない。各ロボットはそれぞれ１度、情報交換のために通信するのみで充分である。
【００４６】
本発明の手段
この実施例の手段は清掃すべき空間１００をダイナミックに分割することに基づいている。空間１００はまず複数のポリゴン１０１に分割される。そののち個々のポリゴン１０１がコネクティビティグラフ２１０（図２Ｂを参照）により選択され、ロボットに割り当てられる。１つのロボットが１つまたは複数のポリゴンに割り当てられたのち、このロボットは対応する部分平面の清掃を開始する。
【００４７】
ロボットがポリゴンに割り当てられ清掃が開始されると、このロボットは他のロボットに当該のポリゴンを自身が担当して清掃していることを伝達しなければならない。しかしつねに各ロボットが相互通信可能な位置にあるとはかぎらない。以下では、２つのロボットの通信距離が設定された距離以下であるときにこの２つのロボットが通信可能であるとする。ここで設定された距離とはロボットの通信半径３０５である（図３を参照）。
【００４８】
ロボットの作業は、全てのポリゴンが割り当てられ、割り当てられた全てのポリゴンが清掃されたことをロボットが認識した時点で終了する。
【００４９】
この実施例では最悪の場合、ロボットどうしが邂逅するために衝突が起こりうるので、衝突の回避が重要な意義を有する。衝突回避に対しては引用文献［１４］に記載されているような非集中型の衝突回避プロセスが使用される。
【００５０】
本発明の実施例の拡張手段および代替手段を以下に説明する。
【００５１】
ポリゴンへの分割
分割すべき空間１００には図１のグリッド１０２が重ね合わされ、複数のポリゴン１０１が形成される。これらのポリゴン１０１に基づいて当該の空間はロボットに分配される。この分配は各ロボットに順次に個々のポリゴン１０１を割り当てて清掃させることにより行われる。
【００５２】
コネクティビティグラフの形成（図２Ａ、図２Ｂ）
コネクティビティグラフ２１０は、各ポリゴン１０１に対してノード２０１を設け、共通のエッジを有するポリゴン対２０２，２０３に辺２０５を設けることにより形成される。コネクティビティグラフ２１０は個々のポリゴン１０１がどのように接続されているかを記述している。
【００５３】
コネクティビティグラフ２１０のノード２０１にはポリゴンがすでに割り当てられたか否か、およびポリゴンがすでに清掃されたか否かに関する情報が記憶されている。
【００５４】
コネクティビティグラフ２１０はロボット工学では周知のコンセプトであり、引用文献［９］などから知られる。これは主としてナビゲーションのために用いられる手法である。
【００５５】
割り当てるべきポリゴンの選択
ロボットに割り当てられるポリゴンの選択は２つの方式にしたがって行われる。１つはロボットがつねに作業すべきポリゴンの対をストックしておく方式である。すでに割り当て済みであるが作業は完了していないポリゴンが作業すべきポリゴンとなる。もう１つは有効であると思われる場合に付加的に別のポリゴンを加える方式である。
【００５６】
基本的にそれぞれのロボットがレンジ内に位置するとき、つまりロボットがポリゴンの中心点から設定される割り当て距離よりも近くに位置するときにのみ、ポリゴンが割り当てられることが制限条件である。
【００５７】
通信距離および割り当て距離が適切に選択されれば、同じ時点でポリゴンの割り当てを受けようとする２つのロボットの相互の通信が保証される。ロボットが作業すべきポリゴンを有さず、かつレンジ内にポリゴンが存在していないために新たな割り当てが受けられない場合、当該のロボットは新たな場所へ移動する。
【００５８】
割り当てのストック（図３）
ロボットがつねに一対のポリゴンをストックとして割り当てられている場合、このロボットは作業すべきポリゴン３０２の数が所定の閾値を下回ると新たなポリゴンの割り当てを開始する。
【００５９】
このときの制限条件は、ロボットが作業すべきポリゴンの領域に関連する新たなポリゴンのみを割り当てられるということである。この条件は作業区域が過度にいびつになってしまうのを回避するために必要である。
【００６０】
新たに割り当てられるポリゴンの選択は次の基準にしたがって行われる。
ａ）他のロボットに（または当該のロボット自身に）割り当てられていないポリゴンでなければならない。
ｂ）すでに割り当てられているポリゴンと関連するポリゴンでなければならない。
ｃ）目下作業中のポリゴンとともにできる限り小さい径をなすポリゴンでなければならない。これにより一方では他のロボットとの衝突が回避され（引用文献［５］［６］［７］を参照）、他方では清掃のためのコンパクトな作業区域が得られるので有利である。
【００６１】
特別割り当て（図４）
特別割り当ては主として孤立ポリゴンを回避するために用いられる。割り当てられていない隣接ポリゴンが存在しなくなると、そのポリゴンは孤立ポリゴンとされる。
【００６２】
孤立ポリゴンを特別に処理しないと、孤立ポリゴンに隣接する全てのポリゴン１０１がすでに清掃されたのに、当該の孤立ポリゴンのみが清掃されないままとなってしまう。これは所定のロボットを大きく迂回させて最終的に当該の孤立ポリゴンを作業させなければならなくなるということを意味する。
【００６３】
したがって目下作業中の区域が孤立ポリゴンに接していることをロボットが検出すると、このポリゴンは当該のロボットに割り当てられる。
【００６４】
ポリゴンの割り当て（図３、図７）
ロボットが割り当てを待っているポリゴンを選択した場合（ステップ７０１）、当該のロボットはこのポリゴンの割り当てを受けようとしていた他の全てのロボットと通信しなければならない。この通信は以下に説明する“保留付き割り当てプロセス”ＡＶＶによって実現される。これについては図７の７０１〜７０５を参照されたい。
【００６５】
この場合ロボット相互の通信は、割り当てを待っているポリゴンがレンジ内に存在していなければならないことにより保証される。
【００６６】
ここで選択される割り当てストラテジまたは保留付き割り当てプロセスＡＶＶは引用文献［１０］の選択アルゴリズムおよび引用文献［１１］のコントラクトネットプロトコルの組み合わせに基づいている。
【００６７】
このプロセスは次の各ステップを有する。
ａ）ポリゴンの割り当てを受けようとするロボット（ステップ７０１）は通信可能な他の全てのロボットに割り当て要求メッセージを送信する（ステップ７０２）。このメッセージは割り当てられるべきポリゴンのＩＤと当該の割り当てがこのポリゴンにとってどれほど重要であるかを表す重要度値ＩＶとを有している。
【００６８】
重要度値ＩＶは次のようにして求められる。
【００６９】
【数１】
2005505434.tif 000003
【００７０】
ここでＳＰは形成されたポリゴンの数であり、ｄｉｓｔ（．．．，．．．）は２つのポリゴン中心点のあいだの距離を求める関数であり、ｍｉｎ（．．．）は最小値を求める関数であり、｜．．．｜は絶対値の関数であり、ＭＡＸＤＩＳＴは２つのポリゴン中心点のあいだの最大距離であり、ｐｏｌｙまたはｐはポリゴンのインデクスである。
ｂ）ロボットが割り当て要求メッセージを受け取ったとき
ｂ−１．このロボットがすでに自身で同じポリゴンに対する割り当て要求メッセージを送信していて、その重要度値が受信された割り当て要求メッセージの重要度値よりも大きい場合（重要度ＩＶが同じ値であればロボットのＩＤに関する判別が行われる）、このロボットは割り当て拒否メッセージを送信する（ステップ７０３、７０４）。
ｂ−２．このロボットがすでに自身で同じポリゴンに対する割り当て要求メッセージを送信しているが、その重要度値が受信された割り当て要求メッセージの重要度値よりも小さい場合、このロボットは割り当て受諾メッセージを送信する（ステップ７０３、７０５）。
ｂ−３．このロボットが同じポリゴンに対する割り当て要求メッセージを送信していない場合、このロボットは割り当て受諾メッセージを送信する（ステップ７０３、７０５）。
ｃ）ロボットが割り当て拒否メッセージを受け取ると、このロボットは割り当てを諦めて通信を終了する（ステップ７０４）。
ｄ）ロボットが送信した全ての割り当て要求メッセージに対して割り当て受諾メッセージを受け取ると、割り当てが有効となり完了する。相応のことはこのロボットが割り当て拒否メッセージを受け取らなかった場合にも当てはまる。
ｅ）ロボットに新たなポリゴンが割り当てられたのち、このロボットは他の全てのロボットにその旨を通知する（後述の“情報の再生”の項を参照）。
【００７１】
注意しなければならないのは、割り当てプロセスの進行中に割り当てに関わる複数のロボットの状態が変化しうるということである。例えば新たなロボットが通信距離に入ってきたり、また既知のロボットが遠ざかっていったりすることがある。
【００７２】
これにはもちろん上述の割り当てストラテジまたは保留付き割り当てプロセスにおいても付加的に注意を払わなければならない。したがって新たに参入したロボットに対してさらなる割り当て要求メッセージを送信しなければならない（前記ａ項）こともあるし、また全ての割り当て受諾メッセージを待機できなくなる（前記ｄ項）こともありうる。
【００７３】
情報の再生（図３）
個々のロボットは通信距離３０５の制限によりつねに相互に通信可能であるわけではないので、各ロボットは清掃作業中に割り当て済および清掃済のポリゴンに関して自身のローカルビューを展開する。
【００７４】
例えば第１のロボットが１つのポリゴンを割り当てられ、第２のロボットが同じ時点で通信距離内に位置していないとき、この第２のロボットはもちろん割り当てについて何も知らない。このロボットは別のビューを有していることになる。
【００７５】
こうしたロボットのローカルビューを補償するために、各ロボットは相互に通信可能となるとただちに割り当て済の領域３０２および清掃済の領域３０１に関する情報を交換する。各ロボットはこれによりローカルビューを補償し、共通のビューを展開する。
【００７６】
通信半径３０５が小さくなればなるほどロボットどうしが相互に通信する機会が減り、個々のロボットのローカルビューの偏差が大きくなる。ローカルビューの偏差があまり大きくなると、ポリゴンが多重に割り当てられて多重に清掃されてしまう。
【００７７】
次に本発明の実施例の別の形態および代替手段を説明する。
ａ）ローカルビューの補償のために、ロボットが規則的な間隔で立ち寄る集合場所を導入する。
ｂ）清掃を行わず規則的に他のロボットのあいだを移動して情報の分配を行う特殊ロボットを導入する。
ｃ）他のロボットが自身の作業をすでに完了しており、さらにポリゴンを作業できる場合に割り当て済ポリゴンを開放する。
ｄ）全体できわめて僅かなポリゴンしか割り当てが済んでおらず、ストックされたポリゴンも少ない場合、ポリゴンのストック数をダイナミックに適合化する。この場合ロボットは全てがほぼ同時に割り当てを受け、ほぼ同時に作業を完了する。
【００７８】
シミュレーションおよびシミュレーション結果（図５、図６）
“情報の再生”の項で述べたように、ロボットの通信手段が制限されているため、種々のロボットのローカルビューが生じ、これにより不要な作業が発生するおそれがある。ローカルビューが清掃効率に与える影響の大きさを検出するために、幾つかのシミュレーションを行った。
【００７９】
基礎となるのは大きなスーパーマーケットのＣＡＤプラン５００である（図５を参照）。図５のスーパーマーケットには３つの清掃ロボット５０１が存在している。
【００８０】
さまざまな通信半径およびロボットの数に対して３回ずつシミュレーションを行った。図６の表にはシミュレーションの結果を示してある。ここで表６００の左側の２つの列はそれぞれロボットの通信半径と数とを表している。表６００の第３列と第４列には２重に割り当てられてしまったポリゴンおよび２重に清掃されてしまったポリゴンの割合が示されている。この値は清掃すべき全平面に対するパーセンテージである。右側の２つの列（第５列および第６列）は３回のシミュレーションの平均値が示されている。
【００８１】
図６の表６００によれば、通信半径またはロボットの数が低減されると２重作業の割合が増大することがわかる。通信半径が小さくなればロボット相互の通信の機会が減ってしまう。多くのロボットが使用されれば情報の共有が迅速となる。
【００８２】
前述の方法は完全にダイナミックなプロセスである。空間の分割は全て作業時間中に行われる。
【００８３】
本発明の方法は完全に非集中型のアプローチを基礎としてもよい。中央のコンポーネントもグローバルな座標も必要ない。
【００８４】
本発明の方法はグローバルな通信網を前提としない。ロボットの通信能力が制限されていることにより最悪の場合にはコストが多少高くなるが、それもグローバルな通信網を設ける場合に要するのと同じ程度である。このこともシミュレーション結果に現れている。
【００８５】
本明細書では次の各文献を引用している。
［１］H.Endres, W.Feiten, G.Lawitzky, Field Test of a Navigation System: Autonomous Cleaning in Supermarkets, Int.Conf.on Robotics and Automation (ICRA), 1998 1779頁〜1781頁
［２］S.Hert, V.Lumelsky, Polygon Area Decomposition for Multiple-Robot Workspace Division, Special Issue of International Journal of Computational Geometry and Applications on Applied Computational Geometry, vol.8, no.4, 1998 437頁〜466頁
［３］H.Bast, S.Hert, The Area Partitioning Problem, Proceedings of the 12th Canadian Conference on Computational Geometry, Fredericton, New Brunswick, 2000 163頁〜171頁
［４］M.W. Bern, S.A.Mitchell, J.Ruppert, Linear-size nonobtuse triangulation of polygons, Discrete and Computational Geometry, vol.14, 1995 411頁〜428頁
［５］I.T.Christou, R.R.Meyer, Optimal Equipartition of Rectangular Domains for Parallel Computation, Journal of Global Optimization, vol.8, January 1996 15頁〜34頁
［６］I.T.Christou, Distributed Genetic Algorithms for Partitioning Uniform Grids, University of Wisconsin Madison, Dept.of Computer Sciences Technical Report MP-TR-96-09, Madison, Wisconsin, 1996
［７］J.Yackel, R.R.Meyer, I.T.Christou, Minimum Perimeter Domain Assignment, Mathematical Programming, vol.78, no.2, Aug.1997 283頁〜303頁
［８］S.Hert, B.Richards, Multiple-Robots Motion Planning=Parallel Processing+Geometry, 2001
［９］J.C.Latombe, Robot Motion Planning, Kluwer Academic Publishers, Boston, 1991
［１０］E.Chang, R.Roberts, An Improved Algorithm for Decentralized Extrema-finding in Circular Configrations of Processes, Communications of the ACM, vol.22, 1979 281頁〜283頁
［１１］R.G.Smith, The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver, In IEEE Transactions on Computers, no.12 C-29, 1980 1104頁〜1113頁
［１２］E.M.Arkin et al., Approximation Algorithms for Lawn Mowing and Milling, Angewandte Mathematik und Informatik, Universitaet zu Koeln, Report No.97.255., 1997
［１３］独国出願第１９８０４１９５号明細書
［１４］M.Jaeger et al., Dezentralized Collision Avoidance, Deadlock Detection and Deadlock Resolution for Multiple Mobile Robots, Int.Conf.on Intelligent Robots and Systems (IROS), 2001
【図面の簡単な説明】
【００８６】
【図１】清掃すべき空間を複数のポリゴンへ分割する様子を示した図である。
【図２】複数のポリゴンへ分割された清掃すべき空間の一部とそのコネクティビティグラフとを示す図である。
【図３】３つの清掃ロボットの通信距離、割り当て済かつ清掃済の部分平面、割り当て済であるが清掃の済んでいない部分平面および割り当ての行われていない部分平面を示す図である。
【図４】２つの別個の部分平面を示す図である。
【図５】清掃されるスーパーマーケットの見取図である。
【図６Ａ】シミュレーション結果の表の一部である。
【図６Ｂ】シミュレーション結果の表の残りの部分である。
【図７】部分平面の割り当て方法のフローチャートである。
【図５】
2005505434.tif 000004
【図６Ａ】
2005505434.tif 000005
【図６Ｂ】
2005505434.tif 000006
【図７】
2005505434.tif 000007
【国際公開パンフレット】
2005505434.tif 000008
2005505434.tif 000009
2005505434.tif 000010
2005505434.tif 000011
2005505434.tif 000012
2005505434.tif 000013
2005505434.tif 000014
2005505434.tif 000015
2005505434.tif 000016
2005505434.tif 000017
2005505434.tif 000018
2005505434.tif 000019
2005505434.tif 000020
2005505434.tif 000021
2005505434.tif 000022
2005505434.tif 000023
2005505434.tif 000024
2005505434.tif 000025
2005505434.tif 000026
2005505434.tif 000027
2005505434.tif 000028
2005505434.tif 000029
2005505434.tif 000030
2005505434.tif 000031
2005505434.tif 000032
2005505434.tif 000033
2005505434.tif 000034
2005505434.tif 000035
2005505434.tif 000036
2005505434.tif 000037
2005505434.tif 000038
2005505434.tif 000039
2005505434.tif 000040
【国際公開パンフレット（コレクトバージョン）】
2005505434.tif 000041
2005505434.tif 000042
【国際調査報告】
2005505434.tif 000043
2005505434.tif 000044
2005505434.tif 000045
2005505434.tif 000046
2005505434.tif 000047
2005505434.tif 000048