FC2ブログ

スポンサーサイト

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

重ね探索

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

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

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

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

さ、左手法の記事ではなかった気がしますが今週はここまでです!
次週は無駄なくゴールまで探索する優秀なアルゴリズムの足立法について見ていきましょう。
ではでは($・・)/~~~
時計
カテゴリ
最新記事
12月14日開始
RSSリンクの表示
リンク
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。