自律型迷路探索ロボット「マイクロマウス」製 作 記
京都情報大学院大学 応用情報技術研究科 京都コンピュータ学院 制御通信部（CINCS） 倉田 実功◆

1. はじめに◆

４．探索アルゴリズム

な制約の要素がある。
迷路の探索アルゴリズムは左手法（右手法），拡張左手法（拡また，制約の要素だけではなく，ハードウェア上で実現する張右手法），求心法，足立法などがある。制作したマイクロマ

処理とソフトウェア上で行う処理にもメリット・デメリットがウスでは，足立法を実装したため，足立法について説明する。

存在するなど特性がある。ハードウェアを最大限に活かすソフ

足立法とは，以下のステップで最短経路を求めるアルゴリズム

トウェアがあり，ソフトウェアを最大限に活かすハードウェアである。ただし，スタート地点を S 地点，ゴール地点を G 地が存在する。

点と表現する。
マイクロマウスとは，1977 年に IEEE（米国電気電子通信学
i. 初期値として現在地点を S 地点に設定し，目的地点を Gして，マイクロマウスの競技会はマイクロプロセッサで動くロ地点に設定する。

ボットの実証実験のイベントとして行われた最も歴史のあるロ最後に，大会出場記録である写真（図５，６，７）を掲載する。
図５ 2010 年関西支部
復活記念大会
マイクロマウスクラシック競技
競技中写真

在地点から目的地点までの最短経路を求める。
iii. i で計算した最短経路に沿って移動し，走行中に新しく発

図 2 ハーフサイズ競技の迷路写真

また，日本では 1980 年から「全日本マイクロマウス大会」

見された壁によって最短経路を通れない場合 ii に戻る。目◆３．製作したマイクロマウス

的地点に到達した場合は iv に飛ぶ。

部（CINCS）として 2008 年より自律型迷路探索ロボット「マイクロマウス」の製作に取り組んでおり，その中での経験につ発が行えるのである。

ii. 現在の地点と現在保持している迷路の壁情報を用いて，現ボット競技会であり，自律制御で未知の迷路を探索してゴールが毎年開催されている。私は，京都コンピュータ学院制御通信

ハードウェアやソフトウェアを開発する際には，それぞれの要素を多角的に考えることが重要であり，それによって良い開会）によって提唱された自律型知能ロボットのことである。そに到達するまでの時間が競われる。

ゴリズムとハードウェア制約の一例を取り上げたが他にも様々

iv. 最短経路で未探索地点がある場合，目的地点を S 地点な
マイクロマウスの製作にあたって，最低限必要な機能要件はいて，特に迷路探索を中心に記述した。

大きく分けて３つに分けられる。走行・旋回制御と迷路探索機

２．マイクロマウス競技の概要（機構・電子回路）とソフトウェアで実現し，より良くするたら G 地点に，G 地点なら S 地点に変更して ii に戻る。未探索地点がない場合探索終了する。

能と最短経路の導出機能である。それらの機能をハードウェア◆めに創意工夫を凝らせて製作していくのである。

このステップによって最短経路を求めることができる。この
図６ 2010 年関西支部
復活記念大会
マイクロマウスクラシック競技
ゴール到達写真

足立法の主に優れた点は，最短経路と考えられる地点を移動し現在のマイクロマウス競技は，従来からあるクラシック競技制作したマイクロマウス（図３，図４）では，ステッピング続けるために，迷路をすべて探索せずとも最短経路を求められと 2009 年の全日本マイクロマウス大会から正式競技として追モータやそのモータを駆動させるためのドライブ回路や，壁やるところである。マイクロマウス競技では，制限時間が限られ加されたハーフマウス競技の２つの種別がある。

機体の状態を取得するための光センサや駆動制御や探索等の計ており探索の効率性が求められるため競技に適したアルゴリズ

マイクロマウス（クラシック）競技は，ロボットが 18cm算を行うマイコンや，電池やデバッグ・操作画面用の LCD なムといえる。

× 18cm を 1 マスとする 16 × 16 マスからなる迷路（図１）を，どそれらを搭載してタイヤに動力を伝え動作する機体の機構を定められた制限時間と走行回数の中で，スタート地点からゴー作った。

◆５．探索アルリゴリズムとハードウェア制約

ル地点の間を走行して，ゴール地点に到達するまでの時間を競う競技である。迷路について，スタート地点は四隅のいずれかマイクロマウスでは，ハードウェア（機構・電子回路）とソであり，ゴール地点は中央の 4 マスと定められているが，迷フトウェアで創意工夫が必要である。その一例として，探索ア路全体の内容は事前には知らされていない。競技中は，外部かルゴリズムの足立法を実現するソフトウェアと関係するハードらの無線操作や迷路情報の入力は禁止されており，ロボットはウェア制約について述べる。

自律的に壁を検出して迷路の探索や最短経路走行を行わなけれ足立法の探索アルゴリズムは，４章で述べた通り探索しながばならない。

ら走行し最短経路を求める。

マイクロマウスの（ハーフサイズ）競技では，クラシック競

スムーズに走行しながら探索を行うためには，常にマスを移技の１マスを 2 分の 1 に縮小した 9cm × 9cm を１マスとす動し始める前に次に移動すべきマスが計算し終わっていなけれる 32 × 32 マスからなる迷路（図２）で，クラシック競技同様にゴール地点に到達するまでの時間を競う競技である。ただ

図 7 過去の大会記録

図３ 製作したマイクロマウス（真上）し，ゴール位置は可変で大会前に告知されるという変更はある。

ばならない。つまり，１マスの最大移動時間は次に移動すべきマスの計算にかかる最大計算時間を超えないことを保証できればよい。この点で，マイコンが可能な最大計算速度のハードウェア制約が存在している。
今回の制作経験では，探索の移動速度の向上を行うのであれば安定走行制御アルゴリズムに加え，探索アルゴリズムの高速化も求められた点が非常に面白い点であった。

【参考文献・資料】
公益財団法人ニューテクノロジー振興財団 マイクロマウス公式ホーム
ページ「h t t p : / / w w w. n t f . o r. j p / m o u s e/」
キーワード：マイクロマウス 迷路探索 ロボット 自律型◆

図１ クラシック競技の迷路写真

20

６．まとめ

知能

探索アルゴリズム

今回の制作経験を通じて，ハードウェアとソフトウェアは相図４ 制作したマイクロマウス（横）互依存関係であることがよくわかる。今回，第５章で探索アル21

自律型迷路探索ロボット「マイクロマウス」製 作 記
京都情報大学院大学 応用情報技術研究科 京都コンピュータ学院 制御通信部（CINCS） 倉田 実功◆

1. はじめに◆４．探索アルゴリズム

な制約の要素がある。
迷路の探索アルゴリズムは左手法（右手法），拡張左手法（拡また，制約の要素だけではなく，ハードウェア上で実現する張右手法），求心法，足立法などがある。制作したマイクロマ処理とソフトウェア上で行う処理にもメリット・デメリットがウスでは，足立法を実装したため，足立法について説明する。

存在するなど特性がある。ハードウェアを最大限に活かすソフ

足立法とは，以下のステップで最短経路を求めるアルゴリズム

トウェアがあり，ソフトウェアを最大限に活かすハードウェアである。ただし，スタート地点を S 地点，ゴール地点を G 地が存在する。

点と表現する。
マイクロマウスとは，1977 年に IEEE（米国電気電子通信学
i. 初期値として現在地点を S 地点に設定し，目的地点を Gして，マイクロマウスの競技会はマイクロプロセッサで動くロ地点に設定する。

ボットの実証実験のイベントとして行われた最も歴史のあるロ最後に，大会出場記録である写真（図５，６，７）を掲載する。
図５ 2010 年関西支部
復活記念大会
マイクロマウスクラシック競技
競技中写真

在地点から目的地点までの最短経路を求める。
iii. i で計算した最短経路に沿って移動し，走行中に新しく発

図 2 ハーフサイズ競技の迷路写真

また，日本では 1980 年から「全日本マイクロマウス大会」

見された壁によって最短経路を通れない場合 ii に戻る。目◆３．製作したマイクロマウス

的地点に到達した場合は iv に飛ぶ。

部（CINCS）として 2008 年より自律型迷路探索ロボット「マイクロマウス」の製作に取り組んでおり，その中での経験につ発が行えるのである。

ii. 現在の地点と現在保持している迷路の壁情報を用いて，現ボット競技会であり，自律制御で未知の迷路を探索してゴールが毎年開催されている。私は，京都コンピュータ学院制御通信

ハードウェアやソフトウェアを開発する際には，それぞれの要素を多角的に考えることが重要であり，それによって良い開会）によって提唱された自律型知能ロボットのことである。そに到達するまでの時間が競われる。

ゴリズムとハードウェア制約の一例を取り上げたが他にも様々

iv. 最短経路で未探索地点がある場合，目的地点を S 地点な
マイクロマウスの製作にあたって，最低限必要な機能要件はいて，特に迷路探索を中心に記述した。

大きく分けて３つに分けられる。走行・旋回制御と迷路探索機

２．マイクロマウス競技の概要（機構・電子回路）とソフトウェアで実現し，より良くするたら G 地点に，G 地点なら S 地点に変更して ii に戻る。未探索地点がない場合探索終了する。

能と最短経路の導出機能である。それらの機能をハードウェア◆めに創意工夫を凝らせて製作していくのである。

このステップによって最短経路を求めることができる。この
図６ 2010 年関西支部
復活記念大会
マイクロマウスクラシック競技
ゴール到達写真

足立法の主に優れた点は，最短経路と考えられる地点を移動し現在のマイクロマウス競技は，従来からあるクラシック競技制作したマイクロマウス（図３，図４）では，ステッピング続けるために，迷路をすべて探索せずとも最短経路を求められと 2009 年の全日本マイクロマウス大会から正式競技として追モータやそのモータを駆動させるためのドライブ回路や，壁やるところである。マイクロマウス競技では，制限時間が限られ加されたハーフマウス競技の２つの種別がある。

機体の状態を取得するための光センサや駆動制御や探索等の計ており探索の効率性が求められるため競技に適したアルゴリズ

マイクロマウス（クラシック）競技は，ロボットが 18cm算を行うマイコンや，電池やデバッグ・操作画面用の LCD なムといえる。

× 18cm を 1 マスとする 16 × 16 マスからなる迷路（図１）を，どそれらを搭載してタイヤに動力を伝え動作する機体の機構を定められた制限時間と走行回数の中で，スタート地点からゴー作った。

◆５．探索アルリゴリズムとハードウェア制約

ル地点の間を走行して，ゴール地点に到達するまでの時間を競う競技である。迷路について，スタート地点は四隅のいずれか

マイクロマウスでは，ハードウェア（機構・電子回路）とソであり，ゴール地点は中央の 4 マスと定められているが，迷フトウェアで創意工夫が必要である。その一例として，探索ア路全体の内容は事前には知らされていない。競技中は，外部かルゴリズムの足立法を実現するソフトウェアと関係するハードらの無線操作や迷路情報の入力は禁止されており，ロボットはウェア制約について述べる。

自律的に壁を検出して迷路の探索や最短経路走行を行わなけれ足立法の探索アルゴリズムは，４章で述べた通り探索しながばならない。

ら走行し最短経路を求める。

マイクロマウスの（ハーフサイズ）競技では，クラシック競

スムーズに走行しながら探索を行うためには，常にマスを移技の１マスを 2 分の 1 に縮小した 9cm × 9cm を１マスとす動し始める前に次に移動すべきマスが計算し終わっていなけれる 32 × 32 マスからなる迷路（図２）で，クラシック競技同様にゴール地点に到達するまでの時間を競う競技である。ただ

図 7 過去の大会記録

図３ 製作したマイクロマウス（真上）し，ゴール位置は可変で大会前に告知されるという変更はある。

ばならない。つまり，１マスの最大移動時間は次に移動すべきマスの計算にかかる最大計算時間を超えないことを保証できればよい。この点で，マイコンが可能な最大計算速度のハードウェア制約が存在している。
今回の制作経験では，探索の移動速度の向上を行うのであれば安定走行制御アルゴリズムに加え，探索アルゴリズムの高速化も求められた点が非常に面白い点であった。

【参考文献・資料】
公益財団法人ニューテクノロジー振興財団 マイクロマウス公式ホーム
ページ「h t t p : / / w w w. n t f . o r. j p / m o u s e/」
キーワード：マイクロマウス 迷路探索 ロボット 自律型◆

図１ クラシック競技の迷路写真

20

６．まとめ

知能

探索アルゴリズム

今回の制作経験を通じて，ハードウェアとソフトウェアは相図４ 制作したマイクロマウス（横）互依存関係であることがよくわかる。今回，第５章で探索アル21