マイクロマウス
11月26
12月21
rogy Advent Calendar 2015，20日目は ざくろくんの Dynamorphism 〜 Haskellでも動的計画法がしたい！ 〜 でした．
DPなのに再帰的な手法によって計算されるって，よくあるメモ化再帰の計算オーダ改善としてDPが出てくる話の流れに馴染みがある私からすれば「あれ，話が逆なんじゃないかな」と最初思ったのですが，後で詳しく読んでみます(間違ってたらごめんなさい)．
どうもご無沙汰しております．11年度入学のところです．もう老害ですね．
今回は毛色が変わってロボットの制御に関する話です．
最近こちらのブログを触らずに自分のブログの方でいろいろ書いております．
式やコードの入力がそちらのほうが圧倒的に楽にできるように構築してしまいましたので，勝手ながら自分のブログの方に記事の本体を投稿させていただきました．
👉 [rogy Advent Calendar 2015] マイクロマウスと制御理論 (1)壁トレース制御 | Tokoro's Tech-Note
分量が多くなりそうなので2部作になっていて，今日の記事はその前半パートです．
(1) 壁トレース制御 (今回書いたやつ)
(2) 絶対・相対運動の制御と非ホロノミック拘束 (12/26公開予定)
ところでマイクロマウスって何？という方は，井土くんの記事や下の動画を見てもらえると良いと思います．
マイクロマウスでは壁で区切られた区画の中を走っていくのですが，その際に壁にぶつかってしまわないようになるべく真ん中を走ろうということをします．
真ん中を走るのなんて簡単じゃないかと思われるかもしれませんが，マイクロマウスによく使われる車両ロボットの構造は，実はそういった走行がしづらい面倒な性質を持ったものなんです(そんなに難しいわけでもないです)．
結構ニッチな話でもありますので，もし興味を持っていただけたらでいいのでご覧ください．
ついでに宣伝ですが，今年のマイクロマウス大会への参加レポートも書きましたので，そちらもぜひご覧ください．
👉 第36回全日本マイクロマウス大会に参加してきた | Tokoro's Tech-Note
rogy Advent Calendar 2015，明日 22日目 は NHKロボコンチーム Maquinista の "Chai-Yo活動記録" です．
DPなのに再帰的な手法によって計算されるって，よくあるメモ化再帰の計算オーダ改善としてDPが出てくる話の流れに馴染みがある私からすれば「あれ，話が逆なんじゃないかな」と最初思ったのですが，後で詳しく読んでみます(間違ってたらごめんなさい)．
どうもご無沙汰しております．11年度入学のところです．もう老害ですね．
今回は毛色が変わってロボットの制御に関する話です．
最近こちらのブログを触らずに自分のブログの方でいろいろ書いております．
式やコードの入力がそちらのほうが圧倒的に楽にできるように構築してしまいましたので，勝手ながら自分のブログの方に記事の本体を投稿させていただきました．
👉 [rogy Advent Calendar 2015] マイクロマウスと制御理論 (1)壁トレース制御 | Tokoro's Tech-Note
分量が多くなりそうなので2部作になっていて，今日の記事はその前半パートです．
(1) 壁トレース制御 (今回書いたやつ)
(2) 絶対・相対運動の制御と非ホロノミック拘束 (12/26公開予定)
ところでマイクロマウスって何？という方は，井土くんの記事や下の動画を見てもらえると良いと思います．
マイクロマウスでは壁で区切られた区画の中を走っていくのですが，その際に壁にぶつかってしまわないようになるべく真ん中を走ろうということをします．
真ん中を走るのなんて簡単じゃないかと思われるかもしれませんが，マイクロマウスによく使われる車両ロボットの構造は，実はそういった走行がしづらい面倒な性質を持ったものなんです(そんなに難しいわけでもないです)．
結構ニッチな話でもありますので，もし興味を持っていただけたらでいいのでご覧ください．
ついでに宣伝ですが，今年のマイクロマウス大会への参加レポートも書きましたので，そちらもぜひご覧ください．
👉 第36回全日本マイクロマウス大会に参加してきた | Tokoro's Tech-Note
rogy Advent Calendar 2015，明日 22日目 は NHKロボコンチーム Maquinista の "Chai-Yo活動記録" です．
12月5
井土です。
rogyAdventCalendar2015 5日目です。
先日行われた第36回全日本マイクロマウス大会に友人のもりゅう氏が参加しました。
このロボットの製作には一応私も協力をしており、迷路の探索アルゴリズムを担当しました。
今回は製作した探索アルゴリズムの概要を紹介したいと思います。
まずは同時に製作した探索シミュレータの動画を見てください。
マイクロマウスとは、迷路のスタートからゴールまでをいかに速く走れるかを競う競技です。迷路は競技直前まで知ることができず、迷路情報をロボットにプログラムすることも禁止です。ただ、迷路のサイズとスタート・ゴールの位置だけは事前情報として知っておくことができます。
競技には制限時間と走行できる回数に制限があります。スタートからゴールまでの時間は各走行ごとに測られ、一番タイムの短い走行のタイムがその人の記録になります。大抵の場合は1回目の走行で迷路をゆっくりと走って探索をし、壁がどこにあるかを記憶していきます。2回目以降の走行で1回目の走行で得た情報を元に最短経路を全力で走っていきます。
私が製作した迷路を探索し、最終的な経路を決定するアルゴリズムについて
迷路の探索
探索にかかる時間を抑えたかったので、なるべく無駄の無い探索ができないかと考えました。
具体的には最短経路になり得そうな部分のみを探索して無駄を省こうとしました。
そこで次のようなアルゴリズムを考えました。
未探索の壁が無いものとして暫定のk最短経路を計算したとき、その経路上の未探索壁というのは
「もし壁がなくて通れたらこれが最短なんだけどなぁ」
という壁になっています。したがって今から壁があるかどうかを調べに行くべきです。実際に壁を見に行って未探索壁が一つ減ると、また状況が変化します。そこでもう一度暫定のk最短経路を計算し、また未探索壁を見に行きます。
見に行くべき未探索壁がなくなった時はk最短経路が確定したことになるので、そこで探索終了です。
最終的に走る経路の決定
マイクロマウスは走行タイムを競う競技です。探索時に最短経路を求めてはいるのですが、それはあくまで距離(市街地距離)における最短経路であって走行した場合に時間が最短になる経路ではありません。そこでなんとかして走行時間が最短となる(なりそうな)経路を探す方法を考えました。
まず、
距離が短いほど走行時間が短いだろう
という仮定を立てました。ただ、距離最短≠時間最短であるので
距離におけるk最短経路を時間における最短経路の候補としました。
k本の時間最短候補が求まったので、このk個の中から真の時間最短経路を選択します。
どうやって1本を選ぶかなのですが、k本それぞれについて実際にロボットがその経路を走行したとしたら何秒かかるかを計算します。直線の台形加速やカーブにかかる時間をロボットの実測値などに基づいて走行時間を計算します。また、ここではロボットが斜め走行できる場合は斜め走行をするとして考えていきます。k本すべての予想走行時間が計算できたらその予想走行時間が最短であるものを1本選びます。それを最終的に走行する経路として決定します。
以上のことをまとめると次のようになります。
最後に
来年は個人でロボットを一つ作ってマイクロマウスの大会にでます。
rogyAdventCalendar2015 5日目です。
先日行われた第36回全日本マイクロマウス大会に友人のもりゅう氏が参加しました。
このロボットの製作には一応私も協力をしており、迷路の探索アルゴリズムを担当しました。
今回は製作した探索アルゴリズムの概要を紹介したいと思います。
まずは同時に製作した探索シミュレータの動画を見てください。
マイクロマウスとは、迷路のスタートからゴールまでをいかに速く走れるかを競う競技です。迷路は競技直前まで知ることができず、迷路情報をロボットにプログラムすることも禁止です。ただ、迷路のサイズとスタート・ゴールの位置だけは事前情報として知っておくことができます。
競技には制限時間と走行できる回数に制限があります。スタートからゴールまでの時間は各走行ごとに測られ、一番タイムの短い走行のタイムがその人の記録になります。大抵の場合は1回目の走行で迷路をゆっくりと走って探索をし、壁がどこにあるかを記憶していきます。2回目以降の走行で1回目の走行で得た情報を元に最短経路を全力で走っていきます。
私が製作した迷路を探索し、最終的な経路を決定するアルゴリズムについて
- どのようにして未知の迷路を探索していくか
- どのようにして最終的に走行する経路を選択するか
迷路の探索
探索にかかる時間を抑えたかったので、なるべく無駄の無い探索ができないかと考えました。
具体的には最短経路になり得そうな部分のみを探索して無駄を省こうとしました。
そこで次のようなアルゴリズムを考えました。
- 足立法でゴールに向かう
- 未探索の壁を通れるとして暫定のk最短経路を計算する
- k最短経路上の未探索壁を列挙
- 列挙した壁を調べに行く
- k最短経路上の未探索壁がなくなるまで2~4を繰り返す
＊ここでいう最短経路とは迷路上の市街地距離のことです
足立法とはマイクロマウスにおいて迷路を探索する際によく使われるアルゴリズムです。絶対にゴールにたどり着けます。とりあえずゴールに一回は到達しておくことでタイムを残しつつ、1つの経路を確保します。
最短経路と言えば最も短い1本の経路のとこを指しますが、k最短経路とは短いものk本の経路のことです。(k=20とかでやっていました)ここでk本の最短経路を計算している理由は後ほどの最終的に走行する経路の決定についてのところで出てきます。
k最短経路を計算するアルゴリズムですが、Yen's algorithmというものを使いました。このアルゴリズムは来た道を戻って経路を稼ぐ経路を答えに含めないので今回の目的に適しています。Yen's algorithm中では2点間の最短経路を何度も計算するのですが、その最短経路の計算アルゴリズムは何でもいいです。なのでその最短経路は歩数マップをスタートからゴールまでたどることで求めました。
市街地距離であれば歩数マップから考えれば十分であり、実装も楽で計算も早いのでこうしました。
足立法とはマイクロマウスにおいて迷路を探索する際によく使われるアルゴリズムです。絶対にゴールにたどり着けます。とりあえずゴールに一回は到達しておくことでタイムを残しつつ、1つの経路を確保します。
最短経路と言えば最も短い1本の経路のとこを指しますが、k最短経路とは短いものk本の経路のことです。(k=20とかでやっていました)ここでk本の最短経路を計算している理由は後ほどの最終的に走行する経路の決定についてのところで出てきます。
k最短経路を計算するアルゴリズムですが、Yen's algorithmというものを使いました。このアルゴリズムは来た道を戻って経路を稼ぐ経路を答えに含めないので今回の目的に適しています。Yen's algorithm中では2点間の最短経路を何度も計算するのですが、その最短経路の計算アルゴリズムは何でもいいです。なのでその最短経路は歩数マップをスタートからゴールまでたどることで求めました。
市街地距離であれば歩数マップから考えれば十分であり、実装も楽で計算も早いのでこうしました。
未探索の壁が無いものとして暫定のk最短経路を計算したとき、その経路上の未探索壁というのは
「もし壁がなくて通れたらこれが最短なんだけどなぁ」
という壁になっています。したがって今から壁があるかどうかを調べに行くべきです。実際に壁を見に行って未探索壁が一つ減ると、また状況が変化します。そこでもう一度暫定のk最短経路を計算し、また未探索壁を見に行きます。
見に行くべき未探索壁がなくなった時はk最短経路が確定したことになるので、そこで探索終了です。
最終的に走る経路の決定
マイクロマウスは走行タイムを競う競技です。探索時に最短経路を求めてはいるのですが、それはあくまで距離(市街地距離)における最短経路であって走行した場合に時間が最短になる経路ではありません。そこでなんとかして走行時間が最短となる(なりそうな)経路を探す方法を考えました。
まず、
距離が短いほど走行時間が短いだろう
という仮定を立てました。ただ、距離最短≠時間最短であるので
距離におけるk最短経路を時間における最短経路の候補としました。
k本の時間最短候補が求まったので、このk個の中から真の時間最短経路を選択します。
どうやって1本を選ぶかなのですが、k本それぞれについて実際にロボットがその経路を走行したとしたら何秒かかるかを計算します。直線の台形加速やカーブにかかる時間をロボットの実測値などに基づいて走行時間を計算します。また、ここではロボットが斜め走行できる場合は斜め走行をするとして考えていきます。k本すべての予想走行時間が計算できたらその予想走行時間が最短であるものを1本選びます。それを最終的に走行する経路として決定します。
以上のことをまとめると次のようになります。
- 距離に関するk最短経路を計算する
- 斜め走行できるところは経路を斜め走行に変更する
- 計算した経路のコスト(予想走行時間)を計算する
- コストの最も小さい経路を選ぶ
最後に
来年は個人でロボットを一つ作ってマイクロマウスの大会にでます。
こんにちは，11年度入学のところです．
今回は先日参加してきた第29回全日本学生マイクロマウス大会のレポートを書こうと思います．
マイクロマウス競技は，小さな自律ロボットが広大な迷路の中を探索し，スタートから指定された場所にあるゴールまでの最短走行時間を競う競技です．
といってもイメージが掴みづらいと思いますので，今回参加してきた動画をご覧ください：
このように，まず1回めは真ん中にあるゴールをとりあえず目指して走っていきます．
最初は迷路の中の壁がどうなっているか情報を持っていないので，走行中に壁のあるなしを自分で判断して，頭(マイコン)の中に迷路を作っていき，その情報を使いながらゴールまでの最短経路を探します．
ゴールにたどり着いた後は，追加の探索をしながらスタート地点に帰ってきます．
そして…
それまでに探した迷路の情報を使って，最速と思われる経路を高速で駆け抜けます．
これを何度も繰り返し，最速タイムを目指します．
今回参加した学生大会は公式の大会で，無事完走した参加者にはこのような認定証が交付されます．
私の機体は今回09秒942，第6位でした．
個人や社会人の競技者も参加する全日本大会は，今月末の11月22〜23日に，東京工芸大学 厚木キャンパスで開催されます．
大会公式Webサイト： http://www.ntf.or.jp/mouse/micromouse2014/index.html
ロ技研からも3台(?)が出走予定です！
是非皆さん見にいらしてください！
今回は先日参加してきた第29回全日本学生マイクロマウス大会のレポートを書こうと思います．
マイクロマウス競技は，小さな自律ロボットが広大な迷路の中を探索し，スタートから指定された場所にあるゴールまでの最短走行時間を競う競技です．
といってもイメージが掴みづらいと思いますので，今回参加してきた動画をご覧ください：
このように，まず1回めは真ん中にあるゴールをとりあえず目指して走っていきます．
最初は迷路の中の壁がどうなっているか情報を持っていないので，走行中に壁のあるなしを自分で判断して，頭(マイコン)の中に迷路を作っていき，その情報を使いながらゴールまでの最短経路を探します．
ゴールにたどり着いた後は，追加の探索をしながらスタート地点に帰ってきます．
そして…
それまでに探した迷路の情報を使って，最速と思われる経路を高速で駆け抜けます．
これを何度も繰り返し，最速タイムを目指します．
今回参加した学生大会は公式の大会で，無事完走した参加者にはこのような認定証が交付されます．
私の機体は今回09秒942，第6位でした．
個人や社会人の競技者も参加する全日本大会は，今月末の11月22〜23日に，東京工芸大学 厚木キャンパスで開催されます．
大会公式Webサイト： http://www.ntf.or.jp/mouse/micromouse2014/index.html
ロ技研からも3台(?)が出走予定です！
是非皆さん見にいらしてください！
東京工業大学ロボット技術研究会で研究室「10g」で活動しております，11年度入学のところ(@tokoro10g,@tokorogy,@gelidium,@taskstacks,@cation_bot)です．
今回は，簡単に私の研究室の紹介と，現在私が取り組んでいるマイクロマウス競技大会に向けたロボット製作の一環である，迷路探索シミュレータについて現況を報告しようと思います．
・10gについて
10g(Laboratory of Graphics, 読み:ログ)は，画像処理技術を用いて賢くロボットを制御することを目標として設立された研究室です．
現在はロボットの製作・制御を主な活動としており，Graphicsの名を持つ割には画像処理は行なっていません．
過去の制作物の一部としては，次のようなものがあります．
・画像処理技術を使用して音ゲーコントローラをVR的に実現した，「VR jubeatコントローラ」
詳細(ブログ記事) Augenblick: 家庭用jubeat制作
・3輪オムニホイール全方向移動車
・クモ型8脚ロボット「VORAS」
・マイクロマウス「カブトガニ野郎」
現在は，VORASの回路周りの改善，新しいマイクロマウス2台の設計製作，最近流行りのクアッドコプターの小型機の製作などを行っています．
・
・迷路探索シミュレータ
新しいマイクロマウスでのアルゴリズムの改善のために，迷路探索シミュレータの新バージョンを作成しています．
詳細 (Wiki記事) 迷路探索シミュレータの製作 - マイクロマウス
従来のアルゴリズムよりも今回採用したアルゴリズムの方が探索にかかる時間が短く，かつ使用するメモリも少ないという一粒で二度おいしいやつです．
ちなみに従来のアルゴリズムは斜め走行には対応しておらず，前後左右のみの動作をシミュレーションするものでした．
従来のシミュレータの動画
今回作成したシミュレータでは斜め走行にも対応しているため，次の大会ではこれを活かして好タイムを狙いたいと考えています．
私個人の技術系情報Wikiでは，ロボット製作や電子工作に関わる情報を垂れ流していますので，興味が有る方はそちらもご覧ください．
Tokoro's Tech-Note
今後も進捗等このブログにアップしていこうと考えておりますので，応援のほどよろしくおねがいします！
今回は，簡単に私の研究室の紹介と，現在私が取り組んでいるマイクロマウス競技大会に向けたロボット製作の一環である，迷路探索シミュレータについて現況を報告しようと思います．
・10gについて
10g(Laboratory of Graphics, 読み:ログ)は，画像処理技術を用いて賢くロボットを制御することを目標として設立された研究室です．
現在はロボットの製作・制御を主な活動としており，Graphicsの名を持つ割には画像処理は行なっていません．
過去の制作物の一部としては，次のようなものがあります．
・画像処理技術を使用して音ゲーコントローラをVR的に実現した，「VR jubeatコントローラ」
詳細(ブログ記事) Augenblick: 家庭用jubeat制作
・3輪オムニホイール全方向移動車
・クモ型8脚ロボット「VORAS」
・マイクロマウス「カブトガニ野郎」
現在は，VORASの回路周りの改善，新しいマイクロマウス2台の設計製作，最近流行りのクアッドコプターの小型機の製作などを行っています．
・
・迷路探索シミュレータ
新しいマイクロマウスでのアルゴリズムの改善のために，迷路探索シミュレータの新バージョンを作成しています．
詳細 (Wiki記事) 迷路探索シミュレータの製作 - マイクロマウス
従来のアルゴリズムよりも今回採用したアルゴリズムの方が探索にかかる時間が短く，かつ使用するメモリも少ないという一粒で二度おいしいやつです．
ちなみに従来のアルゴリズムは斜め走行には対応しておらず，前後左右のみの動作をシミュレーションするものでした．
従来のシミュレータの動画
今回作成したシミュレータでは斜め走行にも対応しているため，次の大会ではこれを活かして好タイムを狙いたいと考えています．
私個人の技術系情報Wikiでは，ロボット製作や電子工作に関わる情報を垂れ流していますので，興味が有る方はそちらもご覧ください．
Tokoro's Tech-Note
今後も進捗等このブログにアップしていこうと考えておりますので，応援のほどよろしくおねがいします！
カテゴリー
