Computation of Configuration Space and Voronoi Structure for Planar Moving Object with 3DOF

Abstract

We present efficient algorithms for computing configuration space obstacles and Voronoi structures for a planar moving object bounded by arc-splines. This approach is based on simple geometric properties of circular arcs. Moving objects and obstacles represented with Bezier curves or B-splines curves can be converted to arc-spline models using biarc approximation. For the computation of configuration space obstacle, we can derive the exact equation and the parameter domain of contact surfaces from the boundary of configuration space obstacle. For the computation of Voronoi structure, we first compute the Voronoi diagrams for some fixed rotations and then stack them up to form a network of surface patches. Using the constructed network of surfaces, we generate a maximum clearance path by following the path on the Voronoi surface. The path can be further optimized based on various different criteria depending on specific applications.

이 논문에서는 평면 위에서 움직이는 arc-spline으로 표현된 물체의 Configuration 공간 장애물과 Voronoi 구조의 효율적인 계산 방법을 제시한다. 이를 위해, 원호가 가지는 단순한 기하학적 성질들이 활용된다. Bezier 또는 B-spline 곡선으로 표현된 움직이는 물체의 경우에는, biarc approximation을 통해 arc-spline으로 표현이 가능해진다. Configuration 공간 장애물의 경계면 계산은 대수적인 방법을 통해 그 정확한 식과 정의역을 구할 수 있다. 3차원 Voronoi 구조를 이루는 곡면은 θ가 고정된 2차원 Voronoi Diagram을 쌓는 방식을 사용하여 만들어진다. 마지막으로, 만들어진 곡면 위에서 움직이는 최대 clearance 경로를 생성한다.