A fast path-planning algorithm for a mobile robot based on a quadtree representation.

摘要

移動ロボットの実際的な障害物回避経路を高速に生成するアルゴリズムを提案する. このアルゴリズムは, 作業空間を上から撮影した実画像から効率的に作成されるクワッドツリーというモデル上で機能するので, 作業空間の障害物の配置の変化に柔軟に対応できる. また, クワッドツリーは作業空間のすべての領域を位置に関して階層的に管理しているので, 移動ロボットより小さな領域を探索しないようにすることによりロボットと障害物の干渉を調べなくても障害物回避経路が生成できる.膨大な個数のノードを保持するクワッドツリーを直接的に探索して障害物回避経路を選択すると計算時間がかかる. そこで本研究では, クワッドッリー上にノード数を小さくおさえたパスグラフを展開し, それを探索することで間接的に障害物回避経路を選択し, アルゴリズムを高速化する. 最後に, この高速性を従来の経路生成アルゴリズムとの比較で実験的に確認する.