未知領域探索のための自律ロボットの効率的な移動経路決定法

全文

(1)情報処理学会第 77 回全国大会. 6A-05. 未知領域探索のための自律ロボットの効率的な移動経路決定法山地秀美†. 辻村泰寛‡. 日本工業大学†. 日本工業大学‡. １．はじめにこれまで複数の自律ロボット環境で協調的にロボットを制御する未知領域探索アルゴリズムを提案してきた (1) 。特に周囲に未知の探索領域がなくなって他の未知領域に移動するとき、及び探索作業がすべて終了し初期位置に戻るときに、現在位置から目的地までの準最短経路を求める手法を提案した。しかし複雑なフィールドでは、提案手法でも計算コストが非常に大きくなることがある。また、遠くに取り残された未知の探索領域に対して、無駄な移動が発生することがある。他方で、できるだけ少ない数のロボットによる効率的な探索が必要な場合も多く存在する。こうしたことから、先ず 1 台のロボットによる被覆作業における無駄な動作の発生を詳細に検討し、これらの問題を回避して移動経路を決定する効率的な方法を提案する。. 障害物の内部にターゲットは存在しないものとする。エージェントがセルのカバーに成功した場合、そのエージェントはマップ上でそのセルの状態を“ターゲット”から“カバー済み”に変更する。それと同時に、そのセルの周辺のセルを調べ、それらの状態をマップ上で記録する。もし、隣接するセルにターゲットが存在しない場合は、エージェントはマップを参照し、シードポイントとして最も近いターゲットを得て、ロボットを移動する。ただし、シードポイントに移動する途中でターゲットを発見した場合は、目的としたシードポイントには行かず、発見したターゲットからカバーを開始する。複数のエージェントが同じシードポイントに向かわないようにするために、エージェントは目的とするシードポイントをシードリストに記録し、エージェント間で共有する。最初にそのシードポイントを獲得したエージェントが優先される。 (2)(3)(4) ２．未知領域探索システムの概要障害物が邪魔で周辺にシードポイントを見つ本システムでは、領域を全てロボットと同じけることができない場合、マップ情報を基にダ大きさの正方形のセルに分割し、セル単位でカイクストラ法に似た探索アルゴリズムを用いてバーする。未知領域は 2 種類のセル、“障害各シードポイントに対する準最短経路を求め、物”と“ターゲット”で構成され、ロボットはその中で最も距離が短い経路を持つシードポイターゲットセル（以下、ターゲットと言う）をントを移動先とする。カバー（探索）する。各ロボットはソフトウェもし、マップ上にターゲットが存在しないとア・エージェント（以下、エージェント）で行き、カバーは完了したとし、エージェントは初動制御され、ターゲットにのみ初期配置される。期位置に戻る。全てのエージェントが初期位置障害物セルを避けながら、エージェントはセンに戻った時点で全ての作業が終了したとする。サでターゲット検出してロボットを動かし、タ３．提案手法ーゲットをカバーする。初期段階では、エージ障害物が複雑に配置されたフィールドの中でェントは領域のマップを持っておらず、ターゲは、分割する矩形の数が大幅に増加するため、ットをカバーしながらマップを構築し、エージ提案手法でも探索が困難となる。特に被覆が終ェント間で共有する。各エージェントは、隣接了し元の位置に戻るときに最も探索に時間がかするセルの特性を認識しながら、単位時間ごとかる。こうした状況も対応するため、たどったに現在のセルから隣接するセルのひとつにロボ経路を記録して利用する手法を提案する。ットを移動させる。セルの状態は、“未知”、“タ初期位置に最初のノードとして位置を記録し、ーゲット”、“障害物”、“カバー済み”の 4 種類で、そのノードが見えなくなる位置まで移動したら An Efficient Method to Obtain Moving Paths of 次のノードの位置を記録する。移動を続けると、 Autonomous Robots for Covering a Field with Unknown 通ってきたノードに近づくことがある。こうし Obstacles †Hidemi Yamachi, Nippon Institute of Technology た場合は、そのノードの次から直前のノードま ‡Yasuhiro Tsujimura, Nippon Institute of Technology. 1-211. Copyright 2015 Information Processing Society of Japan. All Rights Reserved..

(2) 情報処理学会第 77 回全国大会. でをカットし、初期位置から現在位置までのより短い経路に更新する。処理が終了して初期位置に戻るときに、こうして求めた経路を利用することで、矩形分割による経路探索が困難な場合に対応する。また次のシードポイントに移動する経路探索が困難な場合も、この経路を利用して移動することで、矩形分割による経路探索が可能な位置を探す。通過経路を利用する場合も、矩形分割による経路探索は行い経路が見つかればそちらを利用する。図 1 に示すように、カバーの過程で小さく孤立したターゲット領域が残ることがある。現在位置や初期位置から遠く離れた孤立ターゲットが多く残ると、長距離の無駄な移動が発生し、処理効率を大幅に低下させる原因となる。特に現在のカバー作業が終了後に、図中の赤丸で囲まれたターゲットに向かうために長い移動が必要となる。こうした孤立ターゲット領域が残る過程を示したのが図 2 である。カバーによりターゲット領域の分割が発生する。スパイラル被覆動作だけに従って一方の領域の被覆を続け、その領域のカバーが、分割された領域から遠く離れた点で終了した場合、残された領域まで無駄な移動が必要になる。また、孤立したターゲット領域の初期配置位置からの距離も問題となる。初期配置位置から近い場合は、戻ってくる過程で被覆できるので無駄な移動が少なくて済むが、遠い場合は無駄な移動が増加する。これを回避するために、ターゲット領域が分割されるとき、それぞれの領域の大きさと孤立状態を調べる。小さい孤立領域が見つかった場合は、初期配置位置からのより遠いものを優先して選択する。初期位置からの遠近は、ロボットの現在位置、経路上のひとつ前のノードの位置、孤立領域の位置から判定する。. 実験結果より、提案する孤立ターゲット領域発生回避法を導入することで、カバー終了までにかかる時間が短縮され、探索効率が向上したことが確認できた。参考文献 (1) E. Gerlein, E. Gonzalez, Multirobot cooperative model applied to coverage of unknown regions, Multi-Robot Systems, Trends and Development, InTech, pp. 109-130, 2011. (2) H. Yamachi, Tsujimura, Y. Kambayashi and T. Iida, Evaluation of multi-agent simulation for coverage algorithm on unknown field, Proceeding of The 16th Asia Pacific Symposium on Intelligent and Evolutionary Systems (IES 2012), pp. 141-146, 2012. (3) H. Yamachi, Y. Tsujimura and Y. Kambayashi and H. Yamamoto, Structural influence of fields on the performance of the unknown field coverage algorithm by means of multi-agent, Proceedings of 16th Asia Pacific Symposium on Intelligent and Evolutionary Systems (IES 2012), CD-ROM, 2012. (4) H. Yamachi, Y. Tsujimura and Y. Kambayashi, Influence of field structure on the multi-agent coverage algorithm on unknown fields, Journal of Advanced Computational Intelligence and Intelligent Informatics, Vol.17 No.6, pp.883-889, 2013.. ４．シミュレーション実験と結果の考察提案手法の効果を明らかにするために、5 種類（Spiral、Block、Cshape、Wall、Bmp）のフィールドを用いてシミュレーションによる実験を行った。実験は、初期位置をフィールドの周囲の辺の上にランダムに設定し、初期位置からカバーを開始して、カバー終了後に元の位置に戻るまでの時間を計測した。それぞれ 10 回ずつ実行し、実行時間の平均、最大、最小、分散を求め、表 1 にまとめた。表中、ターゲット領域が分割される際に小さい孤立ターゲット領域が見つかった場合、“on” は初期配置位置からのより遠いものを優先して選択する操作を行い、 “off”は行わないことを示す。. 1-212. 図1. 孤立したターゲット領域の例. 孤立したターゲット領域. 図2. 孤立したターゲット領域の出現課程. 表1. シミュレーション実験の結果. Copyright 2015 Information Processing Society of Japan. All Rights Reserved..

(3)