井土です。
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最短経路を計算する
- 斜め走行できるところは経路を斜め走行に変更する
- 計算した経路のコスト(予想走行時間)を計算する
- コストの最も小さい経路を選ぶ
最後に
来年は個人でロボットを一つ作ってマイクロマウスの大会にでます。
