3 0 0 0 OA マイクロマウスにおける迷路探索の効率化に関する研究
マイクロマウスは、迷路の探索を行う小型の自律移動ロボットである。IEEEによって提唱され、日本では1980年より毎年、競技会が開催されている。ロボットは16×16区画からなる迷路を自律的に走行し、スタートからゴールまでに要した時間を競う。競技時間の制限のもと、効率的に迷路を探索し最適な経路を見つけ、素早く走行することが求められる。このようなマイクロマウスにおいて本研究では、迷路の最短経路を見つける探索(最短経路探索)を扱い、これを効率的に行う方法を明らかにする。本研究ではまず、最短経路探索の検証に備えて迷路の生成を行った。マイクロマウスの迷路は独自の特徴を多く持ち、それらは探索の検証結果に影響を及ぼすことが考えられた。実際の競技会で用いられた迷路には限りがあったため、類似性のある迷路を生成する方法を提案し、数を補うようにした。なお、実際の迷路との類似性を評価する指標を導入し、これによって生成した迷路に類似性があることを確認した。効率的な最短経路探索を実現するために、本研究では、2つの提案を行った。1つは、見つけようとする迷路の最短経路とはならないような、探索の必要がない区画を判別し探索から除外(枝刈り)するというものである。もう1つは、探索が必要な区画を順に辿る際にその巡回路を最適化するというものである。これは、計画的に巡回することによって、探索が必要な区画の見過ごしを抑えることを目的としたものである。10,000種類の迷路を用いた検証の結果、探索の効率化として、枝刈りによる効果は確認できたが、巡回路の最適化による効果はわずかであった。上記2つの提案に関連して、通常は探索の必要がある区画を見過ごすと再探索のために余計にコストが掛かることになるが、枝刈りを行うようにしておくと見過ごした区画が枝刈りされ、結果的に探索しなくても良くなる場合がある。つまり、枝刈りを行うことと見過ごさないことは、二律背反の関係にあると考えられた。そのため、どの程度の見過ごしによって探索を最も効率的に行えるか検証したところ、見過ごしは極力行ったほうが良いという結果を得られた。ただし、枝刈りを多数発生させる必要があり、この検証ではその方法も見出すことができた。以上のように、最短経路探索を効率的に行う方法をいくつか明らかにすることができた。