DATE: 2015/11/24(火)   CATEGORY: 未分類
うむ夫。探索編(1) ~アルゴリズム編~


今回はうむ夫。に実装している探索アルゴリズムについて紹介したいと思います.

足立法
…一般的に知られている探索アルゴリズムです.特に工夫もありません.足立法についての説明は省略します.

未知区間優先アルゴリズム
…部内ではF川法として有名です.部内の先輩に薦められ導入したアルゴリズムです.このアルゴリズムの利点としては,名前の通り未知区間を優先して探索を行うため迷路の概形が掴みやすいです.また,足立法に比べ迷路の多くを探索するためより良い経路を見つけやすいです.今シーズンはとてもお世話になりました.来シーズンも大変お世話になる予定です.現在は2マス以上の袋小路だとわかった場合,未知区間でも探索しないように工夫をして運用しています.この方法も後々紹介したいと思います.今後の改良案としては,2マス以上の袋小路だけでなく一周して戻ってくるような形状も探索しないようにしていきたいです.賢い探索は見ていて気持ちがいいです.

最短経路導出特化型アルゴリズム
…単純に言うと,探索が成功すれば最短経路が確実に見つけられるアルゴリズムです.学生大会のときにアルゴリズムの不手際や壁の読み間違いにより最短経路の導出ができなかったことを反省し考案しました.主に帰りの探索の時に用いています.全日本大会のときもこのアルゴリズムで帰りの探索で用いました.概要としては以下の通りです.

① 現在の迷路情報を参照し,推定最短経路を導出.
② 最短経路導出中に未知区間が現れた場合,その未知区間を仮のゴールとして探索を行う.
③ 仮のゴールに向かう時に,未知区間を探索する場合,①~②を繰り返す.
⓸ ①~③を繰り返し,未知区間が存在しなくなった場合その経路が最短経路である.

この方法の長所は,推定最短経路の求め方にあった経路が必ず求まることです.通常の足立法を用いている人なら経験したことがあると思いますが,足立法による探索ではきちんとした経路が求まらないことが多々あります.この方法ではそれがありません.

一方,短所としては迷路の概形がわっかっていなと探索の時間がかかることです.自分が帰りの探索でしか用いない理由はここにあります.迷路の概形がわからない場合,例えば北に向かおうとするとします.その後北の壁がわかってきた場合,南の壁が無い状態なので,南からの経路を目指そうとします.あとはこのループです.迷路の情報がわかっていない場合,一方向を見て,他方向を見に行くような探索を行ってしまうのです.ですのでこのアルゴリズムは,迷路の概形がわかった上で,残りの可能性のある未知区間をつぶしていくように行うことがいいと考えています.


うむ夫。には以上の探索アルゴリズムが実装されています.今シーズンは迷路探索について力を入れて開発してきました.
次回は,探索中に行っている小技や補正を紹介します.



スポンサーサイト
DATE: 2015/11/22(日)   CATEGORY: 未分類
2015年大会シーズンまとめ


お久しぶりです。
2ヶ月ぶりのブログ更新となりました笑。

今回は我がマウス「うむ夫。」の今シーズンの大会がすべて終わったので今シーズンの振り返りを行いたいと思います。

今シーズンのうむ夫。の参加大会はこちらマイクロマウス競技の大会一覧はこちら。

10/4東日本大会地区大会
10/11東北地区大会フレッシュマンクラス
11/1全日本学生大会
11/全日本マイクロマウス大会フレッシュマンクラス

それぞれの大会結果はこちら
・東日本地区大会
記録:15.154
全体6位
特別賞受賞
補足
自身初の公式大会。一度迷路データを飛ばし、フレッシュマンらしさをアピール()

・東北地区大会フレッシュマンクラス
記録:9.100
準優勝
補足
探索を2回失敗し、探索の安定感の大切さを強く感じた大会。ここから、制御や補正を見直し始める。

・全日本学生大会
記録:15.745
全体8位
特別賞受賞
補足
初めてみたゴール形状に戸惑った大会。ゴール付近の袋小路で壁を1つ読み間違い、最短経路がでなかったことが最大の反省点。直線でのブレが目立っていた。


・全日本マイクロマウス大会フレッシュマンクラス
記録:10.782
全体3位
特別賞受賞
補足
初実装したアルゴリズムでの探索成功。ガバガバ調整の斜め走行に成功。調整の大切さと壁切れの偉大さを一番に感じた大会。

今年の大会を振り返っては、すべての大会で賞をいただけてうれしいです!
マイクロマウスシーズン1年目の自分がここまでやれれば十分ではないかと思います。
各大会を毎に大きな課題を見つけ、それを克服しやってきたシーズンでした。
中でも一番勉強になったのは東北大会での経験だと思います。
あそこで探索を失敗していなかったら今ほどの安定した探索はなかったと思います。

いろいろと技術を教えてくださった先輩・OBの方々に感謝です。
本当にありがとうございました。

まだまだやりたいことが絶えないので、次回作そしてうむ夫。にはもう少し頑張ってほしいです。


次回からは、今シーズンで学んだ技術を紹介していこうと思います。

Copyright © うむ夫の歩み. all rights reserved.