多角形および曲線障害物間の移動ロボットのための接線グラフを用いた経路計画

本稿では、一般的な境界を持つ障害物の間で移動ロボットの経路計画のための接線グラフを提案します。接線グラフは、局所的に最短の経路に基づいて定義されます。このグラフは可視性グラフと同じデータ構造を持ちますが、ノードは障害物の境界上の共通接線点を表し、エッジは接線点間の境界と凸境界セグメントの間の衝突のない共通接線に対応しています。接線グラフは、O(K²)のメモリを必要とし、ここでKは障害物の境界の凸セグメントの総数を示します。この接線グラフはすべての局所的に最短の経路を含み、多角形障害物だけでなく曲線障害物の間でも経路計画に対応できます。