Dynamic visibility graph for path planning

Abstract

In this paper, we propose a fast dynamic visibility graph (DVG) for constructing a reduced roadmap among convex polygonal obstacles. DVG is extracted from the global environment with the simple geometric method and rules. Moreover, the data preprocessing is based on the concept of V-circle. Through V-circle, the process is speeded up greatly. Finally, DVG is extended to deal with multi-target problems that traditionally require a lot of time for reconstructing configuration space (C-space).