(An) Efficient Algorithm for Uniform Coverage Path Planning on Surfaces

다국어 초록 (Multilingual Abstract)

Coverage path planning (CPP) is widely used in numerous robotic applications. With progressively complex and extensive applications of CPP, automating the planning process has become increasingly important. This thesis proposes an efficient CPP algorithm based on a random sampling scheme for spray painting applications. We have improved on the conventional CPP algorithm by alternately iterating the path generation and node sampling steps. This method can reduce the computational time by reducing the number of sampled nodes. We also suggest a new distance metric called “upstream distance” to generate reasonable path following given vector field. This induces the path to be aligned with a desired direction. Additionally, one of the machine learning techniques, support vector regression (SVR) is utilized to identify the paint distribution model. This method accurately predict the paint distribution model as a function of the painting parameters. We demonstrate our algorithm on several types of analytic surfaces and compare the results with those of conventional methods. Experiments are conducted to assess the performance of our approach compared to the traditional method.

국문 초록 (Abstract)

본 논문에서는 2차원 표면의 균일 커버리지 경로 계획을 설명하고 이를 효율적으로 푸는 알고리즘을 제시한다. 우리는 경로 계획 문제를 두 개의 하위 문제로 분리하여 각각 푸는 기존의 방식을 보완하여 두 개의 하위문제를 한 번에 풀면서 계산시간을 줄이는 방법을 제시하였다. 또한 경우에 따라 주어진 벡터 필드와 나란한 방향으로 경로가 생성될 필요가 있는데 이를 위해 거스름 거리(upstream distance)의 개념을 제시하였으며 여행 외판원 문제(Traveling Salesman Problem)를 풀 때 이를 적용하였다. 우리는 차량 도장 응용분야에 균일 커버리지 경로 계획법을 적용하였으며 도장 시스템을 고려하여 균일한 페인트 두께를 보장하는 방법을 같이 제시하였다. 네 가지 타입의 2차원 곡면에 대해 시뮬레이션을 진행하였으며 기존의 방법에 비해 더 적은 계산시간을 요구하면서도 합리적인 수준의 페인트 균일도를 달성함을 검증하였다.

목차 (Table of Contents)

• 1 Introduction 1
• 1.1 Related Work 3
• 1.2 Contribution of Our Work 7
• 1.3 Organization of This Thesis 8
• 2 Preliminary Background 9
• 2.1 Elementary Differential Geometry of Surfaces in R3 10
• 2.1.1 Representation of Surfaces 10
• 2.1.2 Normal Curvature 10
• 2.1.3 Shape Operator 12
• 2.2 Traveling Salesman Problem 15
• 2.2.1 Definition 15
• 2.2.2 Variations of the TSP 17
• 2.2.3 Approximation Algorithm for TSP 19
• 2.3 Path Planning on Vector Fields 20
• 2.3.1 Randomized Path Planning 20
• 2.3.2 Upstream Criterion 20
• 2.4 Support Vector Regression 21
• 2.4.1 Single-Output SVR 21
• 2.4.2 Dual Problem of SVR 23
• 2.4.3 Kernel for Nonlinear System 25
• 2.4.4 Multi-Output SVR 26
• 3 Methods 29
• 3.1 Efficient Coverage Path Planning on Vector Fields 29
• 3.1.1 Efficient Node Sampling 31
• 3.1.2 Divide and Conquer Strategy 32
• 3.1.3 Upstream Distance 34
• 3.2 Uniform Coverage Path Planning in Spray Painting Applications 35
• 3.2.1 Minimum Curvature Direction 35
• 3.2.2 Learning Paint Deposition Model 36
• 4 Results 38
• 4.1 Experimental Setup 38
• 4.2 Simulation Result 41
• 4.3 Discussion 41
• 5 Conclusion 45
• Bibliography 47
• 국문초록 52