FC2ブログ

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

最短走行

今晩は!
春ですねー。
暖かくなって布団からも脱出しやすくなってきました。

さて、今週からは最短走行について考えていきましょう。
1年目の人はここら辺で試行錯誤してる時が1番楽しい気がします…w
なので、あまり深くには突っ込まないので悪しからず~

ではまず、最短走行とはなんぞやというところから。
前回の記事で、マウスは探索行動によってゴールまでの経路を見つける(未知の区画を減らす)という説明をしました。
無事に探索が成功すると、次の走行からは最短走行と呼ばれる、1区画毎に考えるのではない走り方をします。どういうことかと言うと、探索で得た情報からスタート前にゴールまでの行動をあらかじめ決めて、余計な区画に入らずにゴールまで一気に走り抜ける感じです。
これを、私の周りではパスに従って走ると言います。
パスってのはグラフ理論で出てくる、ある点とある点を結ぶ道のようなものです。

では最短走行を実現するにあたり、私たちはマウスにどのような指示を送ればいいのでしょうか。
ざっくりと説明すると、
1、探索で得た情報から1本の経路を決定
2、その経路のパスを作成
3、パスに従って走行

てな感じの手順になります。

では実際にパスを作ってみましょうか。
03292.jpg

この画像はとあるmice部員のブログから無断でとってきた全国大会の迷路です。
都合が良いことに青線で1本の経路が示されています。

スタートすると、直進→右折→左折→左折→右折→直進→… となっていますね。
パスをどう表現するかは色々あると思いますが、配列で管理してみましょう。path[256]={0}
unsigned char型だとすると、0~255までの数字を使うことができます。

スタート→ループ(配列の値で条件分岐)→ゴール
例えば1区画直進を1、2区画直進を2、・・・、15区画直進を15、右折を20、左折を30としましょうか。
画像の迷路だと、2区画直進→右折→左折→左折→右折→7区画直進→…となっているので、
path[0]=2,path[1]=20,path[2]=30,path[3]=30,path[4]=20,path[5]=7
としておいて、
while(ゴール){
  if(path[i]<=15){
    path[i]の値分直進
  }
  else if(path[i]==20){
    右折
  }
  else if(path[i]==30){
    左折
  }
  i++;
}
大分適当ですがこのようにループします。

このように、(探索成功→)経路決定→パス作る→パス読み込む。
と処理することで、最短走行でのゴールができるようになります。
ソフト的には、経路決定・パス作る・パス読み込む、中ボス3体ですー

初めてだと難しいかもしれませんが、最短走行でゴールできると感動ものですよ!
次週はスラローム走行についてです。

最近は部室開いてる時間多くなってうれしいです\(^o^)/
キャラ強い新入生入ってくれることを期待してますw
スポンサーサイト

重ね探索

今晩は。
暖かくなって参りました。
春と言えば花粉ですが、今年は去年よりも症状が軽いです。なんでだろ。

今日は重ね探索について書きます。
マウス初心者に向けて書いてきたこのシリーズですが、新入生もそろそろだし役に立ってくれたらいいな~(*´ω`)

重ね探索の意味について。
重ね探索とは、保持している壁の情報を使って、再度探索行動をすることです。
これができると次のような利点があります。

1,探索走行中に衝突等でリタイアしても、それまでに得た情報を活かせる
2,ゴール後にスタート地点まで戻るまでが1走行というルールを活かせる

1の利点はとても便利です。
やり方は色々だと思うのですが、例えばセンサ値から衝突を検知して衝突時から5回前の行動(直進右左折)までの壁情報を残すなどすれば、リタイアしても次の走行で得た情報を活かすことができます。
これをうまく作りこむと審査員から高評価です!
(ただし、そもそもリタイアしないとお披露目できないのですが…\(^o^)/)

2は誰もが使う重ね探索です。
簡単なものですとゴール後にスタート地点をゴールとして、同じ探索アルゴリズムで走行する方法などでしょうか。けど帰りの探索中にリタイアして、最短走行できないとかなったら元も子もないので(ハセシュン今もか?)、ゴール後は壁情報を別の変数で保持しておくことをお勧めします。

今週はここまで。
次週はいよいよ最短走行についてです!
就活で時間あんまとれないから小分けになるかも^^;

それではー($・・)/~~~

迷路探索 足立法

こんにちは!
数ある部室開けましたメーリスの中でも、今日の文面おもしろいw

なんだか昼からやる気が出てきたので、今日は足立法について書きます。

先週は、左手法でゴールを認識できることが重要と述べました。
同じ足立法でも色々やり方があると思うのですが、私の場合は次の手順でゴールを目指します。

1,現座標を更新
2,壁情報を更新
3,新たな歩数マップを生成
4,アルゴリズムに基づいて、機体のとるべき動作を決定

1~4を現座標がゴール座標と同じになるまで繰り返します。
この辺自分で書いたのがうまく動くと楽しいので、詳細を書きません。
もし詰まったら、記事の一番下に白文字で大ヒント書いておいたのでドラッグしてみて(*´ω`)

初めての場合、3と4が特に難しいと思います。
3の歩数マップに関してはまだ説明していないのですが、RTさんの迷路探索アルゴリズムの記事でとても分かりやすく説明されています。
つまり、1,2で更新された壁情報からすべての座標に対してゴールまで何歩なのかを求め、現座標からは前後左右どこに移動するのが良いかを決めるということです。
これがたぶん純粋な足立法。面白いのは、この探索を繰り返したとしても、最短タイムでゴールできる経路が見つかるとは限らないところです。例えば極端な例ですが、スタートからゴールまでの経路が、下の図のように2経路あり、それぞれの歩数が書き込んだ状態であったとします。

03152.png

歩数マップ上では、赤の経路のほうが歩数が短いですが、機体が斜め走行ができないならば、紫の経路のほうが早くゴールできることが分かると思います。

このように、単に歩数マップからだけでは真の最短経路を導けないため、各製作者は全体の区画が分かるまで探索する全面探索や、未知区画を積極的に探索するといった工夫をほどこしています。

そして最短走行時に、それらの情報から経路を選択します。
簡単なものでは、曲がる動作と直進動作の評価を変えるというものです。これは、仮にこの機体は斜め走行ができず、直進優先にしたいので曲がる動作では評価2、1区画直進では評価1であるとすると、複数の経路がある中で評価の合計が一番少ない経路を選ぶことで曲がる動作が少ない経路を選ぼうということです。

上位陣の経路選択はさらにすごいです。
直進時の加速度と最高速、斜め走行時の加速度と最高速、ターン時の速度などからスタートからゴールまでの時間を見積もり、各経路の中で最も早くゴールできる経路を選択します。時間換算なので理に適ってますよね(憧)。

さらに昨年の全日本大会では、ハーフの決勝で探索のアルゴリズムがとても重要になりました。
既知区間加速をしたとしても、全面探索をすると時間が足りなくなるという(;・∀・)

アルゴリズムのうまさが今後も問われることになると思います。
なので、まずは足立法をマスターして、その後自分なりの工夫を発見してどんどんトライしていきましょう!

それでは今週はここまで。
次週は探索でこけても次の走行に活かす、重ね探索についてです。
ではでは($・・)/~~~

1,現座標を機体が向いている方角の向きに1歩進める
2,前・左・右壁を判定して現座標の壁情報を更新
3,全壁情報を使って新たな歩数マップを生成
4,歩数が1減る座標へ前後進左右折の行動をとる(ついでに機体が向いている方角変える)

迷路探索 左手法

こんにちは!

今週から迷路探索について書いていきます。
いよいよこのシリーズにも終わりが見えてきました。

さて、マイクロマウスの迷路探索では必要不可欠な要素がいくつかあります。
迷路を解くアルゴリズム、そして「スタート」と「ゴール」の認識です。

初めてマイクロマウスに挑戦する人はどうやってスタートとゴールを認識しているか、ということも分からないと思うのでそこから話を始めます。

クラシック競技では18cm×18cmを1区画として、縦16横16区画の計256区画があるということが既知の情報です。
これを上から眺めたとき、各区画は2次元の座標で表すことができます。

つまり、横軸をx、縦軸をyとすれば、角に当たる座標は、(x,y)=(0,0)、(0,15)、(15,0)、(15,15)というように表すことができます。

この時、例えば機体が南向きに進んでいるとします。
①(3,8)座標から前進した→進む先の座標は(3,7)
②(3,8)座標から右折した→進む先の座標は(2,8)

このように、現在の座標向いている方角、そして前進・右折・左折・反転のどの動作をしたかによって、座標を更新することがゴール認識への第一歩です。

プログラムもここの記述が最も苦戦するでしょう。
分かりやすいのは下線を引いた3つの条件から座標を更新するように記述していくことだと思いますが、工夫できることは多々あり、例えば向いている方角をビットシフトで処理するとif文が1/4になります。(私もバグが怖くてまだできていない…)

私の場合ここでバグが大量に発生しました。
2次元配列を用意して(map[16][16]とでもしましょうか)、向いている方角と行う動作で条件分岐させたのですが、配列のアンダーフロー・オーバーフローを除く処理を書いてなくて大変な目にあいました^^;
比較の時に、map[x-1][y]などを使うときは、その前にif(x!=0)などを入れましょう


とりあえず、ここまでで座標の認識ができるようになったとしましょう。
プログラムは大変ですが機体を走らせてモチベーションを維持しつつ頑張るのです。

座標の認識ができるようになったら、if(現在座標がゴール座標)のようにゴール処理をすればゴールできるようになります。
そして、ここで登場するのが左手法です。
左手法を使う目的は座標の認識がうまくいっているということを知るためです。このアルゴリズムは「なるべく左に行く」という簡単なものなので、座標の認識ができればゴール処理にたどり着けるでしょう。いきなり上位のアルゴリズムを動かそうとすると、アルゴリズムのバグなのか座標認識ができていないのか…と迷走することになるので、左手法でうごかしてアルゴリズムが正しければゴールできるという前提を獲得しておきましょう。

さ、左手法の記事ではなかった気がしますが今週はここまでです!
次週は無駄なくゴールまで探索する優秀なアルゴリズムの足立法について見ていきましょう。
ではでは($・・)/~~~

モーターの軸を切るよ

本日2回目の投稿( ・`д・´)
そして、タイトルが不気味でしょう。

何をしようかというと、先日両軸で使おうと買ったモーターを、やっぱり片軸で使おうということになり、片軸を切り落としたというお話です。

検索するとモーターの軸をルーターで落としている人を発見。
よし、これにしようとamazonさんでルーター購入。部室のバンドソーや穴開け機と同じプロクソンというメーカーでした。そう言えば、この前バンドソー使ってたら刃が切れちゃって、替え刃買ったので近々治しに行きます。

切断以外にもバリ取りや穴あけに使えそう。
03011.png

で、意外だったのが、金属の切断は切る側も硬い金属でキイイイィィィィンってやるもんだと思ってたのですが、実際は切断砥石なるものを使って、ジジジジジって感じでした。とても地味でした。

そんなこんなでこんなからこんなへ。
03012.png03013.png

あ、もちろん作業は外に出てやってますよ^^;
ちなみにモーターはこちらのIMONコアレスモータ1616S2
このモーターはトルクもさることながら、シャフト長7.6mmが素晴らしい!
シャフト長がどう生きるかは、マウスが完成してからのお楽しみです(*´ω`)


続いてキット話ですが今こんな姿です。
03014.png

書き込みできました~(*´ω`*)
(一度ショートしました~)

モーターにもトルク入ったので良かったです。
バンドソー治しに部室行ったら走らせてみよう。

加減速をする

今晩は!
2月はあっという間でしたね。今日から3月です。

今日の記事は加減速についてです。
内容薄いです。

例によってMONOistさんの記事
http://monoist.atmarkit.co.jp/mn/articles/1305/07/news005.html

私が加減速をちらっと説明している記事

MONOistさんの記事では、180mm進むときに、あらかじめ何回パルスを送ればよいかを計算しています(ステップ数ベース)。
今まで私が説明してきたやり方は、機体の速さが理想速度になるように1ms毎のパルス数を決定するというもので、1ms毎に理想速度を更新し、理想速度を積分した時の距離と実際に進む距離が同じになるというものでした(物理量ベース)。

物理量ベースで、加減速はとても簡単です。
加速度というパラメーターを用意して、理想速度の更新時に±するだけで、他に処理は要りません。

MONOistさんの記事で言う、「急激に速度を上げたために脱調」は、設定した加速度が高すぎるときにおこります。また、「速度を上げ過ぎた(過負荷)ことによる脱調」は、設定した最高速が高すぎる時におこります。

一度、どのくらいの加速度・最高速なら脱調しないのか、実験してみるのが良いでしょう。

今週はここまで\(^o^)/
次週からは、ついに迷路探索アルゴリズム編です。

現段階で、
・任意の距離を進める
・壁の有無が分かる
・姿勢制御できる
・超信地旋回できる

なんて前提があることにして、話進めるんだけどOKかな?
迷路探索アルゴリズムの予習をしたい人はRTさんのブログへ!
ではでは。
時計
カテゴリ
最新記事
12月14日開始
RSSリンクの表示
リンク
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。