Delaunay Mesh를 이용한 효율적인 Robot Path 생성방법
- Issued Date
- 2009
- Abstract
- This paper proposes a path generation method for a mobile robot. The path connects a starting position to a goal position with out collision with obstacles in a 2-dimensional plane. There have been many path generation methods. The proposed method generates the path through the procedure of mesh generation, path finding and path straightening. In the mesh generation procedure, the method used Delaunay triangulation. Then a set of neighboring mesh from the starting to goal position forms a path. Among the possible paths, one path can be selected using Dijkstra algorithm The path can still have unnecessary saw tooth segments. So, the path straightening procedure finally straightens the path if possible using Greedy algorithm.
The resulting path is straight as much as possible and avoids obstacles smoothly
- Alternative Title
- An Efficient Robot Path Generation Using Delaunay Mesh
- Alternative Author(s)
- Noh Sung Woo
- Affiliation
- 조선대학교 제어계측공학과
- Department
- 일반대학원 제어계측공학과
- Advisor
- 고낙용
- Awarded Date
- 2010-02
- Table Of Contents
- 제1장 서론 1
제1절 연구 배경 및 목적 1
제2절 연구 범위와 방향 2
제3절 논문의 구성 3
제2장 기초 이론 및 문제 구성 4
제1절 기존의 경로 계획 방법 4
1. 로드법 4
가. 가시성 그래프(Visibility Graph) 4
나. 보르노이 그래프(Voronoi Graph) 5
2. 셀 분할법 7
가. 사다리꼴-분할 방식 7
3. 포텐셜 필드법 8
가. 포텐셜 필드법 8
나. 그레디언트 방법 8
제2절 기존의 대표적인 최단 거리 생성 방법 9
1. Floyd 알고리즘 9
2. A* 알고리즘 10
제3장 제안된 경로계획 방법 11
제 1절 Delaunay Triangulation 정의 11
제 2절 Delaunay Triangulation 생성의 여러 방법들 12
1. Delaunay Triangulation 여러 가지 방법들 12
가. Flipping Algorithm을 이용한 방법 12
나. Divide & Conquer 알고리즘을 이용한 방법 12
다. Plane-Sweep 알고리즘을 이용한 방법 13
2. 제안한 Incremental 알고리즘 방법 14
가. 점짐추가(Incremental Insertion) 14
나. 점진 추가 알고리즘 설명 14
제 3절 Mesh Generator 17
1. Mesh Generator 알고리즘 17
가. 외곽선 생성 17
나. Grid 생성 18
다. 외곽선에서 벗어난점 제거 18
라. Delaunay 삼각형 생성 22
마. Mesh Point 이동 22
제 4절 최단거리 알고리즘 27
1. 인접행렬 생성 27
2. Dijkstra 알고리즘 적용 28
3. Greedy 알고리즘 31
가. 장애물과 직선이 만나는지 구하는 방법 32
제4장 실험 및 고찰 36
제 1절 Node 추가 없이 경로 생성 수행 실험 36
1. 장애물이 없을 때 수행 실험 36
2. 장애물 추가 시 수행 실험 38
3. 임의의 폴리곤에 장애물 추가 시 수행 실험 39
제 2절 Node 추가 시 경로 생성 수행 실험 41
1. 장애물이 없을 때 수행 실험 41
2. 장애물 추가 시 수행 실험 42
3. 임의의 폴리곤에 장애물 추가 시 수행 실험 44
제 3절 Mesh Generator를 이용한 경로 생성 실험 45
1. 장애물이 없을 때 수행 실험 45
2. 장애물 추가 시 수행 실험 47
3. 임의의 폴리곤에 장애물 추가 시 수행 실험 48
제 4절 비교 실험 후 장단점 50
제5장 결론 및 향후 계획 52
참고문헌 53
후 기 56
- Degree
- Master
- Publisher
- 조선대학교
- Citation
- 노성우. (2009). Delaunay Mesh를 이용한 효율적인 Robot Path 생성방법.
- Type
- Dissertation
- URI
- https://oak.chosun.ac.kr/handle/2020.oak/8378
http://chosun.dcollection.net/common/orgView/200000239148
- Appears in Collections:
- General Graduate School > 3. Theses(Master)
- Files in This Item:
-
-
Download
Delaunay Mesh를 이용한 효율적인 Robot Path 생성방법.pdf
기타 데이터 / 4.2 MB / Adobe PDF
-
Items in Repository are protected by copyright, with all rights reserved, unless otherwise indicated.