始めに
この記事はMicro Mouse Advent Calendar 2019 - Adventarの12日目の記事です。昨日はまんぼー君のロボット製作のスケジューリング - まんぼーの技術記でした。非常にためになる内容でした。ありがとうございました。あとは彼自身の体調管理まで考慮したロボット製作のスケジューリングを組めるようになれば彼は完璧ですね🖤
はじめまして。WMMCのsophiaと申します。
さて、始めさせていただきます。
摘要
ステッパマウスに埃取り器を装着して迷路を掃除させてみた。
目次
開発経緯
クラシックマウス用迷路をロボットに掃除させる考えは弊サークル内に昔からあった。時々そのことについて皆で話していたが、当時は筆者を含め誰もが冗談半分であった。いつしかこの考えは忘れ去られてしまっていた。
ところがある日突然筆者はその考えを思い出し、実現したくなってしまった。ムラムラとやる気が出て来たのである。
クラシックマウス用迷路をロボットに掃除させるという発想自体は陳腐である。しかし弊サークルには迷路を掃除するロボットが無い。その上、迷路を掃除するロボットは役に立つ可能性がある。ゆえに試作してみる価値があると判断した。
背景
迷路掃除の現状と問題点
- どの区画を掃除していて、どの区画はまだ掃除していないかが分からなくなってしまう。これは特に複数人で掃除しているときに連携がうまくとれないと発生する問題である。
- 迷路の中央付近は手が届きにくく掃除しづらい。この問題は特に16×16のクラシックマウス用迷路を掃除するときに発生する問題である。
目的
- 人による掃除より早く掃除が完了する。もしくは掃除のために時間を用意する必要がない。
- コロコロと同等かそれ以上に埃を除去できる。
- 掃除し忘れがない。
- 導入にかかる金銭的・時間的費用と手間が少ない。
- 従来の迷路掃除と同等かそれ以上の丁寧さ。
以上の条件を全て満たすために、「既存のステッパマウスに埃取り器を装着し、迷路を全探索させながら掃除もさせる」ことを提案する。既存の物を使用すれば開発及び作成にかかる時間的費用を抑えられる。ステッパマウスはタイヤの回転角を直接制御しているため、余計な物を後付けして重量等が変わっても走行に影響が出ない。埃取り器に関しては選定次第であるが金銭的費用を抑えられる。既存のステッパマウスに埃取り器を装着するだけなので手間がかからない。迷路を全探索すれば掃除し忘れが無くなる。埃取り器を取り付けたステッパマウスを速く走らせれば人より早く掃除が完了する。マウス調整しながら掃除できるため、そもそも迷路掃除のために時間を用意する必要が無くなる。丁寧さは埃取り器の形状やステッパマウスの走行軌道・速度によって変わるので工夫次第である。
提案手法
全体の流れ
ステッパマウス
全探索アルゴリズム
トレモー・アルゴリズム
あらゆる迷路を解くことが出来る解法として「トレモー・アルゴリズム」が知られている。この解法は19世紀のフランスの数学者エドゥアール・リュカによって紹介された。この方法は本質的には「全パターンの経路をしらみ潰し的に試す」というものであるが、チョークで地面に自分が通った跡を残す事で、しらみ潰しを効率的にできる点に特徴がある。この方法では、迷路上の各々の通路は最大2回しか通らない(試しに進んでみる場合と、諦めて戻る場合の2回)。よって最悪でも通路の長さの合計値の2倍歩けば、ゴールにたどり着く。
アルゴリズムの詳細は以下の通り。以下のアルゴリズムで、迷路を歩くときは常にチョークで地面に「→→→→」と描き続ける。また、まだチョーク跡のつけられていない通路を歩くのを「通路を進む」と言い、すでにチョーク跡「→→→→」がつけられた通路を「←←←←」の方向へと進むのを「通路を戻る」と呼ぶ。
簡単のため、スタート地点が迷路中の分岐点の一つにあると仮定して話を進める。
任意に選んだ通路を進む。
そのうち分岐点か行き止まりかゴールにたどり着く。
まだ通っていない(=チョークの跡がない)分岐点に辿り着いたら、通ってきた通路以外の任意の通路を選び、そこを進む。→2
すでに通った(=チョークの跡がある)分岐点に辿り着いたら、進んできた通路を戻る。→2
通路を戻っているときに分岐点に辿り着いた場合(注:戻っているときなので、この分岐点は必ず過去に通っている)
まだ通っていない(=チョークの跡がない)通路が残っていたら、その通路へと進む。→1
全ての通路にチョークの跡があったら、各通路を眺める。ほとんどの通路は、通路へと伸びて行くチョーク跡「→→→→」および通路から引き返して来るチョーク跡「←←←←」があるが、一つだけ「←←←←」の無い通路(=この分岐点に最初に来たときに通った通路)がある。その通路を引返す。→2
ただし今いる分岐点がスタート地点だった場合は、全ての通路に「→→→→」と「←←←←」の両方が書いてある事もありうる。この場合ゴールに到達する方法が無いので、諦めて終了。
行き止まりに辿り着いたら、来た道を戻る。→2
ゴールにたどり着いたら終了。
スタート地点が迷路中の分岐点の一つに無い場合も、スタート地点が分岐点だとみなして上述のアルゴリズムが使うことが出来る。つまり、スタート地点が通路の中央にある場合は、スタート地点は2方向に分岐する分岐点だとみなす。スタート地点が迷路の行き止まりにあるときは、スタート地点は一方向にだけ分岐する分岐点だと考える。
掃除道具選定
概要
迷路に堆積する埃の種類
埃除去方法
商品選定
本ブログでは試作品を作成するだけであるため商品選定については追求しないものとする。
今回は近くのスーパーに売っていたのでクイックルハンディ取り替え用を使用した。
埃取り器
概要
市販の掃除道具を加工して埃取り器を作成する。
加工
静電気掃除グッズをステッパマウスに装着するために必要な加工をする。
今回使用したクイックルハンディ取り替え用には元から穴が開いており、その穴にひもを通してステッパマウスに装着するため加工は不要であった。
装着
静電気掃除グッズをステッパマウスに装着する。
今回はクイックルハンディ取り替え用の穴にタコ糸を通してステッパマウスに結び付けた。取り付けやすさのために、ステッパマウス後部に静電気掃除グッズを装着した。
実験
本来ならば実験では再現性を重視し実験環境を現実環境にできるだけ似せる必要がある。しかし今回の実験ではそこまで気にしないことにする。
見やすさのために迷路に多めに綿埃を配置して埃取り器付ステッパマウスを走らせた。綿埃は掃除機の中から入手した。
掃除後の埃取り器付ステッパマウスの裏面を次図に示す。埃取り器で綿埃を掃除できていると分かる。しかし、埃取り器をステッパマウス後部に装着したせいで綿埃がステッパマウスのタイヤや底板にくっついてしまっている。
埃取り器装着方法をもっと工夫する必要がある。
今後の課題
今回の取り組みでは定量的な評価を一切行わなかった。よって、迷路掃除が迷路走行時間最小化にどれほど貢献するのか、一番除去すべき埃は綿埃で合っているのか、綿埃を除去するために最適な掃除道具は静電気掃除グッズで合っているのか、静電気掃除グッズで迷路掃除するとどれくらい埃が取れるのかについて不明なままである。定量的に評価するならば、迷路掃除前後でタイヤの滑りやすさを測ったり、迷路掃除で除去できる埃の重量を量ったりする必要がある。加えて、今回立てた推測や予想や仮説に関して一切検証しなかった。よって、今回試作した物が妥当かどうかは非常に怪しい。妥当性を示すためにも推測や予想や仮説を検証する必要がある。また、今回試作した物が仕様である「コロコロと同等かそれ以上に埃を取れる」と「従来の迷路掃除と同等かそれ以上の丁寧さ」を満たしているかどうか不明なままである。比較して検証する必要がある。
感想
今回は迷路掃除をロボットにやらせてみた。しかし、迷路掃除くらい人がやれと筆者は言いたい。
終わりに
日頃からクソ真面目に阿呆なことがしたいな~、専門性の無駄遣いをしてほくそ笑みたいな~、とんでもない物を作って周囲を唖然とさせたいな~、へんてこな物を作れば誰かが笑ってくれるかな~、と思っているので自分でもよく分からない方向に突き進んでしまうんですよね。しかし理想に反してほぼ全員が笑ってくれない上にそもそも無視されると気付いてしまいました。みんな無関心なんですよ。でも笑ってくれる人が少しだけいることにも気付きました。このブログを読んで誰か1人でも笑ってくれると筆者は嬉しいです。
明日はらっちさんの記事です。