東京工業大学 ロボット技術研究会

東京工業大学の公認サークル「ロボット技術研究会」のブログです。 当サークルの日々の活動の様子を皆さんにお伝えしていきます。たくさんの人に気軽に読んでもらえると嬉しいです。
新歓特設ページ        ロボット技術研究会 HP        ロボット技術研究会 twitter公式アカウント

アルゴリズム

「ロボット技術研究会」通称「ロ技研」は、その名前の通りロボットの制作や研究はもとより、電子工作や機械工作、プログラミングなどの幅広い分野にわたるものつくり活動を行っています。

カテゴリ一覧: loading

プログラミングコンテスト

こんにちは!14年度入学の@yosupotです.

突然ですがプログラミングコンテストというものを知っていますか?
与えられた課題を解くプログラムを短時間で素早く書くというものです.(実は長時間のもありますが…)

具体的には、
"二次元平面上に沢山点が与えられるから、その中で最も近い2点間の距離はどのくらいか?"
のような問題が5問/2時間ぐらいで出されます.
多少プログラミングをかじった人なら、すぐにO(N^2)(N:点の数)のアルゴリズムは思いつくでしょう.
勿論これではあんまり難しくないです.
ですがこれをO(NlogN)やO(N)で解こうとすると難しいです.
O(N^2)とO(NlogN)というのはめっちゃ違います. 普通のフーリエ変換はO(N^2)で高速フーリエ変換はO(NlogN)です.
こういうのを解くアルゴリズムをウンウン考えたりネットで調べたりするのがプログラミングコンテストですね.

日本ではAtCoderというサイトが有名です.
今週末もコンテストをやるようです、よかったら参加してみてはいかがでしょうか?


それでここからが本題で、
実は僕もコンテストを開催します!!
KCSという、kagamiz(rogyではない)さんが作ったコンテストサイトを借りて、問題を出題します!
3月8日の夜に行う予定です!!
今バリバリ準備をしてますよ〜〜〜〜、ぜひ参加してくださいね!

ではノシ

シミュレータ作って迷路探索してみた


迷路探索のアルゴリズム

・はじめに

はじめまして、14のみやびです。
大学に入学してからいまのところ現在までは主にソフト面をやってきています。
(ソフトって気軽に触れるからついつい偏っちゃいますよね)
rogyではマイクロマウスの大会に向けて活動しています。
迷路シミュレータを作っています。
前期研究報告会では迷路の生成法について発表したので、ここでは迷路の探索方法についてお話ししたいと思います。

探索改良
こんな感じです。

大まかな流れ
探索アルゴリズムの流れを簡単に記述すると、
①探索結果を保存する入れ物を作っておく
(マス目の間の壁全てに対して用意し、初期状態は壁がないとしておく)
②ゴール座標からの歩数マップ(そのマスに行くための最短歩数が入ったマス)を作る
③歩数マップともろもろのデータからスコアを算出したうえで、最も低いスコアの方向に進む
(自分の向いている方向でない部分に進む選択になったら、進みたい方向に向きを変える)
④現在の座標と方向から視野内の壁を認識する
⑤②-④を繰り返してゴール座標に到達する
⑥(0,0)座標を目指して同じように探索する
以上の流れで一往復探索します。

・詳細
上記だけでは大まかすぎるので、以下に詳細を書きます。

①探索結果を保存する入れ物
私の場合は、横の壁の集合rと縦の壁の集合cを用意しています。
マス目の座標に対して、上下左右のマスがどの壁になるのかよく確認する必要があります。
初期状態は壁がない状態にしてあり、進みながら壁を追加します。

②歩数マップ作成
研究発表会でも話しましたが、歩数マップの作成方法についてお話しします。
・任意の座標に0を入れて確定マスとする。
・確定マスに隣接する、未確定かつ踏破可能なマスをピックアップする。
・ピックアップしたマスに、隣接する確定マスの最小値+1を代入する。
・数値の入ったマスを確定マスにする。
これを繰り返すことで、ある座標からの歩数が入ったマスが出来ます。
ゴール座標からこの歩数マップを作ることによって、数値が大きいほどゴールから遠いマスということになります。

③スコア算出
自分の周りの四方のマスに対して、
Score=(歩数マップの値)+(踏破済みマスかどうか)+(最近に踏破したマスかどうか)
というようなスコアを算出しています。
・歩数マップの値…②で言った通りのゴールからの歩数を加えます。
・踏破済みマスかどうか…踏破済みならk1,未踏破なら0を加えます。
・最近踏破したマスかどうか…現在から10個前までのマスをログとして保存し、
i個前のログに存在するマスだった場合、(10-i)*k2を加えます。
ただし、四方で踏破不可能なマス(壁に阻まれたマス)がある場合は、
その方向はスコアを10000などの高すぎるものにし選ばれないようにします。

このようにスコアを算出した後、このスコアが最も低い方向へ進みます。
移動した先のマスを踏破済みマスにし、ログに座標を収納しておきます。

④迷路の壁認識
このプレイヤはマウスの特性上、自分の両隣の壁と、一つ前のマスの両隣の壁を見れる設定にしてあります。
ただし、目の前が壁だった場合は一つ前のマスの両隣の壁は見えないようになっています。

⑤ゴール座標に到達してから、踏破済みマスでの最短経路を考える
ゴール座標についたタイミングで、とりあえず認識した範囲での最短経路を知りたいですね。
しかし、踏破済マスだけだとうねうね曲がっているので経路を考えるのが難しいです。
そこで、踏破済マスと未踏破マスの間にわざと壁があるとして歩数マップを作ることによって、踏破済マスの中でのゴールまでの経路を作っています。
壁で囲まれた範囲なら歩数マップを使って歩数を割り出すことが出来、かつ歩数が壁の外に出ないので未踏破マスを通ることがありません。
ゴール座標から、隣接する差が1のマスをたどることによって経路を出すことが出来ます。

⑥スタート地点に戻る
今度はスタート地点からの歩数マップを作り、同じようにスコアを算出して動きます。
踏破済みマスのスコアが高くなるように設定されてるので、帰るときは行ったことのないマスに向かうようになっています。


これらのような方法で探索しています。
現在ではスコアの部分をいじって、探索の効率を上げている段階です。
スコア方式を用いているので、新しい項を追加するのも簡単かなぁと思っている次第です。


・終わりに
なにか不明な点や知りたい点、迷路の生成方法やシミュレータの仕様など気になることがあれば、
ついったーでリプください。
miyabi3180
それでは、失礼しました。
ギャラリー
  • 自作キーボードを作ろうver1.0
  • 自作キーボードを作ろうver1.0
  • 自作キーボードを作ろうver1.0
  • 自作キーボードを作ろうver1.0
  • 第14回ROBO-ONE Light 結果報告
  • ロボット技術研究会紹介
  • ロボット技術研究会紹介
  • rogy2016冬合宿 in 戸狩
  • rogyサバゲ:†革命†をもっと
記事検索
最新コメント