로드맵을 이용한 다개체 이동로봇의 충돌회피 알고리즘
A Collision Avoidance Algorithm for Multiple Mobile Robots Using Roadmaps
- 주제(키워드) mobile robot + path planning + collision avoidance
- 발행기관 아주대학교
- 지도교수 홍석교
- 발행년도 2006
- 학위수여년월 2006. 8
- 학위명 박사
- 학과 및 전공 일반대학원 전자공학과
- 본문언어 영어
초록/요약
이동 로봇의 경로계획이란 작업공간에서 로봇이 장애물과의 충돌 없이 출발자세에서 도착자세까지 도달할 수 있는 경로를 생성하는 것을 말한다. 로드맵은 안전한 상태공간의 연결성을 나타내는 1차원 선분으로 이루어진 네트워크로써, 출발상태에서 도착상태까지의 경로를 생성할 수 있게 한다. 골격지도는 이 로드맵의 일종으로 장애물이 존재하는 작업공간에서 자유공간의 중간지점들을 연결한 점들의 집합으로 자유공간의 위상(位相)을 나타낸다. 이 골격지도는 로봇을 충돌로부터 안전하게 하지만, 장애물로부터 필요이상의 거리를 두게 하고 급격한 회전을 하게 하는 단점을 갖는다. 이 논문에서는 첫째로, 위의 골격지도의 단점을 보완한 새로운 로드맵을 생성하는 알고리즘을 제안한다. 둘째로, 같은 작업공간에서 각각 출발점에서 출발하여 도착점으로 경로를 따라 이동하는 두 대의 이동로봇이 만났을 때 충돌을 회피하는 알고리즘을 제안한다. 두 로봇은 위에서 제안한 로드맵을 보완한 로드맵을 이용하여 충돌로부터 안전한 최적의 경로 쌍을 찾아 주행한다. 시뮬레이션 결과로 제안된 로드맵 생성알고리즘과 두 대의 로봇의 충돌회피 알고리즘의 효용성을 검증한다.
more목차
1 Introduction 1
1.1 An Overview of Robot Motion Planning 2
1.2 Motion Planning using Roadmap 3
1.3 Previous Work 4
1.3.1 Roadmaps 4
1.3.2 Collision Avoidance 5
1.3.3 Planning for multiple robots 6
1.4 Outline of the Thesis 7
2 Background 8
2.1 Roadmaps Methods 8
2.2 Skeleton maps 11
2.2.1 Disadvantages of Skeleton map 11
2.2.2 A Wavefront Expansion Method 14
2.3 Motion Planning using Dynamic Programming 15
2.4 Multiple Robot Systems 17
3 A Roadmap Construction Algorithm for Mobile Robot Path Planning Using Skeleton Maps 20
3.1 Introduction 20
3.1.1 Definitions 20
3.1.2 Generation of the skeleton map 21
3.2 A Roadmap Construction Algorithm Using the Skeleton Map 22
3.2.1 Basic idea to improve roadmaps 22
3.2.2 Generation of crossing polygons 25
3.2.3 Crossing polygons of neighboring crossing points 28
3.2.4 Two edges of a pair of nodes 31
3.2.5 Connections of the initial and the goal configurations to roadmaps 33
3.2.6 Flow of the algorithm and computational complexity 35
3.3 Simulations 37
3.4 Conclusions 40
4 A Collision Avoidance Algorithm for Two Mobile Robots with Independent Goals in Roadmap 41
4.1 Introduction 41
4.2 Preliminaries 43
4.2.1 Composite configuration space 43
4.2.2 Various cases where two robots meet each other 45
4.3 Collision Avoidance Algorithm for Two Mobile Robots 45
4.3.1 Roadmap for collision avoidance algorithm 46
4.3.2 Paths for collision avoidance 49
4.3.3 Process for collision avoidance 54
4.4 Simulations 55
4.5 Conclusions 66
5 Conclusions 67
Bibliography 69
Abstract in Korean 74
