-
- 図1.掃除イメージ
近年、家庭用掃除ロボットのルンバが人気である。ルンバとは、iRobot が製造・販売するロボット掃除機である。ルンバは、個々の部屋や小規模の部屋を掃除する事が可能である。このルンバの動作アルゴリズムは、ルンバ 800 シリーズとルンバ 900 シリーズで異なる。ルンバ 800 シリーズでは、文献[1]の「ルンバの動きと稼働範囲のイメージ」はルンバの動きから部屋全てを清掃する事は出来るが、清掃が終わった個所を何度も掃除している事が分かる。一方、ルンバ 900 シリーズでは、文献[2]の清掃エリアのルンバの動きを見るとルンバ 800 シリーズとは全く異なり、一度しか掃除しない面積が直感的に広く効率的な動作になっている事が理解できる。ルンバ 900 シリーズの方が、[2]にある記述の「清掃できる面積は最大 112 畳(185m²)」となっており、ルンバ 800 シリーズは、[3]のカタログより「最大 25 畳」となっており、ルンバ 900 シリーズは、最大稼働面積が 4 倍以上になっている。この様に、動作が効率的である方がバッテリー稼働可能時間が限られる為、清掃できる面積が増えている。つまり、大規模な部屋において、ルンバの動作が効率的である必要が出てくる。また、文献[4]既存研究ではロボットの動作に注目しており、時間に関して数学的に求められていない。本稿では、清掃ロボットの掃除アルゴリズムを障害物の無い長方形の部屋を対象に用いた時の時間を数学理論を用いて時間効率を述べる。
天井関数として⌈x⌉とし、x 以上の最小の整数とする。なお、広く知られるガウス記号とは次の関係にある。
⌈x⌉ = -|-x|
Coverage Path Planning とは、与えられてた平面領域に対して、単位面積を持つロボットが全ての点をカバーするためのロボットの移動経路を定めることである。ロボットが移動経路を定めるにあたり、様々な制約を考えられる。例えば、未知の領域に対して、ロボットがセンサーを用いて領域を観測しながら、自律的に経路を決定し最終的に自走しながら全ての点をカバーするのと、領域が与えられ、ロボットはセンサーを持たずに受けた指示に従ってすべての点をカバーするように移動するのでは、全く解決法が異なる。
Galceran らは、CPP に関しての論文を 2013 年から過去十年間に達成された成果に焦点を当て、最も成功した CPP 手法のレビューの提示と報告されたフィールドアプリケーションを議論している。彼らの調査した論文で、移動ロボットのカバレッジ操作を実行する為に満たさなければならない要件が定義されている。要件は次のとおりである。
しかし、複雑な環境でこれらの基準をすべて満たす事は必ずしも可能ではない。また、Choset の調査で提案された物で、ロボットはオフラインとオンラインのいずれかに分類する事が出来る。オフラインアルゴリズムは、静止した情報のみに依存しており、環境は事前に分かっているものと想定される。しかし、多くのシナリオでは、環境に関する完全な事前知識が非現実的であると仮定される。オンラインアルゴリズムは、対象となる環境の完全な事前知識を想定せず、リアルタイムにセンサを利用して、ターゲット空間を掃引される。議論されたアプローチで使用される一般的な根本的な考え方を反映し、いくつかの section毎に以下の様に分類して解説されている。
内容は、ロボットの動作や障害物への対応、領域の分解に注目している。本稿では、これらの要件や分類を参考にしている。
Nikitenko らは、複数の清掃ロボットによって、格納庫の様な大きな屋内エリアを清掃する。為のマルチロボット掃除システムを提案している。彼らの手法は、ユーザーが、ユーザーインターフェースをしようして、清掃動作を要求する事によって、開始される。この要求は、サーバーに送信され、全体の清掃領域を責任領域と呼ばれる小さなサブ領域に分ける。各ロボットは、責任領域を割り当てられる。割り当てられた後、ローカライゼーションの目的の為のウェブカメラ、追加のバンパーを割り当てる。その後、ロボットは責任領域に移動し、清掃動作を実行します。清掃が完了したら、次の未割り当ての責任領域をそのロボットに割り当てる。全てのエリアが適切に清掃されるまで、処理が続けられる。本稿では、全体の清掃領域を責任領域に分ける場合に、均等な時間による領域の切り分けをする事により、更なる効率化に役立つと着想を得ている。
荒井らは、家庭用掃除ロボットの開発コンセプトおよび、試作機の設計について報告している。このロボットは、部屋の外壁に沿って 1 周し、走行経路から得た部屋の形状データを用いて所定の走行パターンによって、清掃を行う。本稿では、彼らの動作アルゴリズムを参考にしている。
(m, n)∈R×Rの(mは縦、nは横とする。)長方形領域を掃除ロボットを用いた時の掃除時間の上限と下限を数学的に求める事を目標とする。但し、現状では部分問題しか解けていない。
領域の前提
ロボットの前提
また、オフライン問題、オンライン問題を考える。
オフライン問題
ロボットに、m,n、ロボットを置く位置を予め与える。
オンライン問題
ロボットを領域内、任意の位置に置く。
さらに問題を簡単に考えるため、以下の様な部分問題を考える。
オフラインの場合
一般性を失わず(0,0)∪(m,n)のうち、m≦1とし、図 1-1 の様に初期座標(x,y)初期角度θ。とする。
掃除時間≦2α + n/2 + α + m/2 - 1/2 + 2α + m - 1
= 5α + n/2 + 3m/2 - 3/2・・・➀
となる。
オフラインの場合
オフライン部分問題 1,2 のとき、部屋の四隅を(0,0),(n,0),(0,m),(n,m)と置き、(0,0)から(0,m)の一辺と進行方向を平行にする。
縦の場合
横の場合
縦の場合
横の場合
最初に右に 90°回転する以外は上記と同様に、
➁と➂の差を取って比較すると、
x = ⌈n⌉ - n, y = ⌈m⌉ - mと置くと、
➃が正ならば横、負ならば縦の方が掃除時間が短い。
n,mが整数の場合、x = 0, y = 0となり、➃に代入すると
となり、α ∈ R、n と mが整数なので、2α(n - m - 1/2)は、n と mの差によって正負が決まる。よって、➃の正負が明らかになり、縦と横の掃除時間が短い方が明らかになる。
縦と横の差が無い場合
n,mは実数で、➄はxy 軸上に傾きがm/n切片が2α(⌈n⌉ - ⌈m⌉ - 1/2)/nの右肩上がりの直線で表す事ができる。また、x, yの定義域は、0 ≦ x, y < 1となる。
y < 1のαの条件を求めると、x = 0, y < 1を➄に代入すると
x < 1のαの条件を求めると、x < 1, y = 0を➅に代入すると
α∈Rより、7は(m + 1/2) < n、8はn < (m + 1/2)となる。
まとめると、(m + 1/2) < nのときn/(2(⌈n⌉ - ⌈m⌉ - 1/2)) < α、n < (m + 1/2)のときm/(2(⌈m⌉ - ⌈n⌉ + 1/2)) < αの場合は端数によるはみ出す領域よりも回転の回数が少ない方が早くなる為、(m + 1/2) < nは横、n < (m + 1/2)は縦に掃引する方が時間は短くなる。
オンライン部分問題 1,2,3 のとき、オンライン解法では、ロボットはあらかじめ、m,n を知らない提案解法では、初めに m,n を求める。
また、横に掃引する場合は、
問題 2 のオフラインとオンラインでは、共に同じ式になったが、オンラインの場合は m,n が整数である必要がある。
縦と横のジグザグ走行に関して、数学的に示した。また、mまたはnに小数点以下が存在する時、➁と➂の差の式により縦と横の時間の小さい方が明らかにできる。また、αの値によっては、mとnの大小のみで縦と横の小さい方が明らかに出来る。
αが非常に小さい値の場合、⌈n⌉mと⌈m⌉nの比較によって、縦と横の小さい方が明らかになるが、ガウス記号が入った大小比較は、図 3 のグラフを見ると、複雑なグラフになっており、そのままmとnの大小比較にならず、⌈n⌉mと⌈m⌉nの式に代入して計算した後の値を比較する事で明らかに出来る。
複雑な形の部屋や文献[5]の様な大きな領域を一定の領域毎に分ける時に、領域を掃除時間で分ける事が有用だと考えられる。関連研究[4]や[6]と異なり、障害物の無い長方形の部屋のみを想定しており、長方形以外の部屋の形、例えば台形や円形にそのまま用いる事ができない。複雑な形の部屋に用いるには、新たな動作や部屋を長方形の形に分解する工夫が必要である。
この論文では、領域とロボットの前提を決め、オンライン問題とオフライン問題に大きく分け、更に問題を簡単に考えるために部分問題に分けて、いくつかの動作を数学的な理論により掃除時間を示した。
特に、ジグザグ走行に関して議論した。
結論として、障害物の無い長方形の一定の動作に関しての掃除時間を数学的に明らかにした。
長方形以外の部屋の形や障害物がある場合の動作は示せていない。
特定の部屋の掃除時間が一定以下になる事が不可能な事は示せていない。
問題 1 のオンライン問題に関しては示せていない。
問題 2 の別解として、付録の図 3,4 の様な動作を考案したが数学的に示せていない。
また、m,n が整数の場合は、ジグザグ走行が最適と考えられるが GOAL の位置や m,nが整数以外の場合は示せていない。
