| 1 |
1
이동체(mobile body)를 위한 경로 계획 방법에 있어서,상기 이동체의 시작점과 목표점 및 장애물들의 위치 정보를 포함하는 형태 공간을 입력받는 단계;상기 형태 공간 내에 존재하는 장애물들의 탐색 순서를 결정하는 단계;상기 결정된 순서에 따라 반복적으로 하나의 장애물의 꼭지점으로부터 다른 장애물의 꼭지점을 연결하여 셀을 분할하는 단계;상기 연결이 생성되지 않은 꼭지점들로부터 상기 꼭지점들의 반각을 양분하는 방향으로 연장선을 생성하여 셀을 분할하는 단계; 및상기 생성된 연결선들을 양분하는 정점을 생성하여 상기 이동체의 이동 경로상의 후보 노드로 설정하는 단계;를 포함하는 방법
|
| 2 |
2
제 1 항에 있어서,상기 꼭지점을 연결하여 셀을 분할하는 단계는,상기 위치 정보를 이용하여 제 1 장애물의 꼭지점으로부터 최단 거리에 위치한 제 2 장애물의 꼭지점이 상기 제 1 장애물의 꼭지점의 반각 내에 존재할 경우 상기 제 1 장애물의 꼭지점과 상기 제 2 장애물의 꼭지점을 연결하는 단계; 및상기 연결이 생성되지 않은 꼭지점들에 대해 상기 위치 정보를 이용하여 제 3 장애물의 꼭지점으로부터 상기 제 3 장애물의 꼭지점의 반각 내에 존재하는 최단 거리의 제 4 장애물의 꼭지점을 연결하는 단계를 포함하는 방법
|
| 3 |
3
제 2 항에 있어서,상기 제 1 장애물의 꼭지점과 상기 제 2 장애물의 꼭지점을 연결하는 단계는,상기 위치 정보를 이용하여 상기 제 1 장애물의 꼭지점으로부터 최단 거리에 위치한 제 2 장애물의 꼭지점을 탐색하는 단계;상기 위치 정보를 이용하여 상기 제 1 장애물의 꼭지점의 반각 내에 상기 제 2 장애물의 꼭지점이 존재하지는 여부를 검사하는 단계; 및상기 검사 결과에 따라 상기 제 1 장애물의 꼭지점으로부터 상기 제 2 장애물의 꼭지점을 선택적으로 연결하는 단계를 포함하는 방법
|
| 4 |
4
제 2 항에서 있어서,상기 제 3 장애물의 꼭지점과 상기 제 4 장애물의 꼭지점을 연결하는 단계는,상기 위치 정보를 이용하여 상기 꼭지점 간의 연결이 생성되지 않은 꼭지점들에 포함되는 제 3 장애물의 꼭지점의 반각 내에 존재하는 모든 꼭지점들을 탐색하는 단계;상기 탐색된 꼭지점들에 대해 상기 제 3 장애물의 꼭지점과의 거리를 산출하는 단계; 및상기 산출된 거리 정보에 기초하여 상기 제 3 장애물의 꼭지점으로부터 최단 거리에 위치한 상기 제 4 장애물의 꼭지점을 연결하는 단계를 포함하는 방법
|
| 5 |
5
제 2 항에 있어서,상기 위치 정보에 기초하여 상기 꼭지점 간에 생성된 연결이 각각 양 꼭지점의 반각 내에 존재한다고 판단된 경우, 상기 양 꼭지점을 추가적인 연결 생성의 대상으로부터 삭제하는 것을 특징으로 하는 방법
|
| 6 |
6
제 2 항에 있어서,상기 위치 정보에 기초하여 연결 생성의 대상 꼭지점에 이미 2개의 연결이 생성되었고 상기 2개의 연결선과 상기 대상 꼭지점이 형성하는 내각이 각각 180도 이내인 것으로 판단된 경우, 상기 꼭지점을 연결 생성의 대상으로부터 삭제하는 것을 특징으로 하는 방법
|
| 7 |
7
제 1 항에 있어서,상기 꼭지점들의 반각을 양분하는 연장선을 생성하여 셀을 분할하는 단계는,상기 연결이 생성되지 않은 꼭지점들로부터 상기 꼭지점들의 반각을 양분하는 단계; 및상기 위치 정보를 이용하여 상기 양분된 반각으로부터 상기 반각을 양분하는 방향으로 최단 거리에 위치한 셀 분할선, 장애물 또는 상기 형태 공간의 외곽선 중 어느 하나까지 연장선을 생성하는 단계를 포함하는 방법
|
| 8 |
8
제 7 항에 있어서,상기 연장선은 상기 반각을 이등분하는 것을 특징으로 하는 방법
|
| 9 |
9
제 1 항에 있어서,상기 셀 분할을 위한 꼭지점은 예각이고,상기 꼭지점 간의 연결은 반각 내에 존재하는 꼭지점을 대상으로 생성됨으로써 분할된 셀이 볼록 다각형이 되는 것을 특징으로 하는 방법
|
| 10 |
10
제 1 항에 있어서,상기 꼭지점들을 연결하는 셀 분할은 그 분할 각도 및 방향에 제한이 없는 것을 특징으로 하는 방법
|
| 11 |
11
삭제
|
| 12 |
12
제 1 항 내지 제 10 항 중에 어느 한 항의 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체
|
| 13 |
13
이동체를 위한 경로 계획 장치에 있어서,상기 이동체의 시작점과 목표점 및 장애물들의 위치 정보를 포함하는 형태 공간을 입력받아 저장하는 저장부; 및상기 저장된 형태 공간에 기초하여 상기 이동체를 위한 탐색 경로를 계획하는 처리부를 포함하고,상기 처리부는,상기 형태 공간 내에 존재하는 장애물들의 탐색 순서를 결정하는 탐색 순서 결정부;상기 결정된 순서에 따라 반복적으로 하나의 장애물의 꼭지점으로부터 다른 장애물의 꼭지점을 연결하여 셀을 분할하고, 상기 연결이 생성되지 않은 꼭지점들로부터 상기 꼭지점들의 반각을 양분하는 방향으로 연장선을 생성하여 셀을 분할하는 셀 분할부를 포함하며,상기 셀 분할부에 의해 생성된 연결선들을 양분하는 정점을 생성하여 상기 이동체의 이동 경로상의 후보 노드로 설정하는 것을 특징으로 하는 장치
|
| 14 |
14
제 13 항에 있어서,상기 셀 분할부는,상기 위치 정보를 이용하여 제 1 장애물의 꼭지점으로부터 최단 거리에 위치한 제 2 장애물의 꼭지점이 상기 제 1 장애물의 꼭지점의 반각 내에 존재할 경우 상기 제 1 장애물의 꼭지점과 상기 제 2 장애물의 꼭지점을 연결하고,상기 연결이 생성되지 않은 꼭지점들에 대해 상기 위치 정보를 이용하여 제 3 장애물의 꼭지점으로부터 상기 제 3 장애물의 꼭지점의 반각 내에 존재하는 최단 거리의 제 4 장애물의 꼭지점을 연결함으로써 셀을 분할하는 것을 특징으로 하는 장치
|
| 15 |
15
제 14 항에 있어서,상기 셀 분할부는,상기 위치 정보를 이용하여 상기 제 1 장애물의 꼭지점으로부터 최단 거리에 위치한 제 2 장애물의 꼭지점을 탐색하고,상기 위치 정보를 이용하여 상기 제 1 장애물의 꼭지점의 반각 내에 상기 제 2 장애물의 꼭지점이 존재하지는 여부를 검사하고,상기 검사 결과에 따라 상기 제 1 장애물의 꼭지점으로부터 상기 제 2 장애물의 꼭지점을 선택적으로 연결함으로써,상기 제 1 장애물의 꼭지점과 상기 제 2 장애물의 꼭지점을 연결하는 것을 특징으로 하는 장치
|
| 16 |
16
제 14 항에서 있어서,상기 셀 분할부는,상기 위치 정보를 이용하여 상기 꼭지점 간의 연결이 생성되지 않은 꼭지점들에 포함되는 제 3 장애물의 꼭지점의 반각 내에 존재하는 모든 꼭지점들을 탐색하고,상기 탐색된 꼭지점들에 대해 상기 제 3 장애물의 꼭지점과의 거리를 산출하고,상기 산출된 거리 정보에 기초하여 상기 제 3 장애물의 꼭지점으로부터 최단 거리에 위치한 상기 제 4 장애물의 꼭지점을 연결함으로써,상기 제 3 장애물의 꼭지점과 상기 제 4 장애물의 꼭지점을 연결하는 것을 특징으로 하는 장치
|
| 17 |
17
제 13 항에 있어서,상기 셀 분할부는,상기 연결이 생성되지 않은 꼭지점들로부터 상기 꼭지점들의 반각을 양분하고,상기 위치 정보를 이용하여 상기 양분된 반각으로부터 상기 반각을 양분하는 방향으로 최단 거리에 위치한 셀 분할선, 장애물 또는 상기 형태 공간의 외곽선 중 어느 하나까지 연장선을 생성함으로써 셀을 분할하는 것을 특징으로 하는 장치
|
| 18 |
18
제 13 항에 있어서,상기 꼭지점들을 연결하는 셀 분할은 그 분할 각도 및 방향에 제한이 없고,상기 셀 분할을 위한 꼭지점은 예각이며,상기 꼭지점 간의 연결은 반각 내에 존재하는 꼭지점을 대상으로 생성됨으로써 분할된 셀이 볼록 다각형이 되는 것을 특징으로 하는 장치
|
