| 1 |
1
맵의 벽을 따라 이동하면서 랜드마크를 탐지하여 랜드마크의 정보를 수집하는 단계;수집된 랜드마크의 정보를 이용하여 탐지된 랜드마크가 볼록 랜드마크인지 오목 랜드마크인지를 판단하는 단계;탐지된 랜드마크 중 볼록 랜드마크의 유무에 따라 맵 축소 및 맵 분해 중 하나의 동작을 수행하는 단계; 및수행된 동작에 따라 분해된 맵에 대하여 BSA(backtracking spiral algorithm)를 이용하여 경로를 생성하는 단계를 포함하며, 상기 동작을 수행하는 단계는,탐지된 랜드마크 중 볼록 랜드마크가 없다고 판단된 경우, 오목 랜드마크를 통해 계산된 축소점 랜드마크를 이용하여 맵에 대하여 축소작업을 수행하는 단계; 및탐지된 랜드마크 중 볼록 랜드마크가 있다고 판단된 경우, 맵에 대하여 맵 분해를 수행하는 단계를 포함하고,상기 맵에 대하여 맵 분해를 수행하는 단계는,탐지된 볼록 랜드마크로부터 각각의 엣지까지 수직선으로 연결한 수직선 엣지를 생성하는 단계;생성된 수직선 엣지 중에서 맵 분해 조건을 만족하는 수직선 엣지를 선택하는 단계;선택된 수직선 엣지로 구성되는 분해 엣지 집합을 생성하는 단계; 및생성된 분해 엣지 집합 및 맵의 엣지 집합에 A* 기법을 적용하여 맵을 분해하는 단계를 포함하는 것을 특징으로 하는 확장된 BSA 커버리지 경로계획 방법
|
| 2 |
2
제1항에 있어서, 상기 볼록 랜드마크인지 오목 랜드마크인지를 판단하는 단계는,경로 탐사 장치가 맵의 벽을 따라 시계방향으로 이동할 경우, 좌측에 있는 장애물은 벽으로 판단하고, 전방에 장애물이 있는 경우 오목 랜드마크로 판단하며, 좌측의 장애물이 계속되다 장애물이 사라지는 경우 볼록 랜드마크로 판단하는 것을 특징으로 하는 확장된 BSA 커버리지 경로계획 방법
|
| 3 |
3
제2항에 있어서, 상기 볼록 랜드마크인지 오목 랜드마크인지를 판단하는 단계는,볼록 랜드마크의 값을 음의 무한대 값(-∞)으로 설정하며, 랜드마크의 값의 총합계가 0보다 큰 경우 볼록 랜드마크가 없는 것으로 판단하고, 랜드마크의 값의 총합계가 0보다 작은 경우 볼록 랜드마크가 있는 것으로 판단하는 것을 특징으로 하는 확장된 BSA 커버리지 경로계획 방법
|
| 4 |
4
삭제
|
| 5 |
5
제1항에 있어서, 상기 맵에 대하여 축소작업을 수행하는 단계는,맵의 벽을 따라가면서 탐지된 각각의 오목 랜드마크를 서로 연결하거나, 탐지된 오목 랜드마크와 경로 탐사 장치의 현재 위치를 연결한 엣지를 생성하는 단계;생성된 복수 개의 엣지로 구성되는 엣지 집합을 생성하는 단계;생성된 엣지 집합으로 구획되는 맵 구역을 생성하는 단계;탐지된 각각의 오목 랜드마크 또는 경로 탐사 장치의 현재 위치를 중심으로 상, 하, 좌, 우 및 각각의 대각선 방향에 위치하는 8개의 격자 중 맵 구역의 내부에 위치하는 격자를 축소점 랜드마크로 선택하는 단계; 및선택된 축소점 랜드마크를 서로 연결하여 축소점 랜드마크로 구성된 새로운 엣지의 집합으로 맵을 축소하는 단계를 포함하는 것을 특징으로 하는 확장된 BSA 커버리지 경로계획 방법
|
| 6 |
6
제5항에 있어서, 상기 엣지를 생성하는 단계는,탐지된 랜드마크의 집합에서 두 개의 인접한 랜드마크를 연결하여 맵의 윤곽을 구성하는 엣지를 생성하는 것을 특징으로 하는 확장된 BSA 커버리지 경로계획 방법
|
| 7 |
7
제5항에 있어서, 상기 축소점 랜드마크로 선택하는 단계는,경로 탐사 장치의 현재 위치를 중심으로 한 8개의 격자 중 맵 구역의 내부에 위치하는 격자가 두 개 이상일 경우, 맵 구역의 내부에 위치하는 격자 중 임의로 선택된 하나의 격자를 축소점 랜드마크로 선택하는 것을 특징으로 하는 확장된 BSA 커버리지 경로계획 방법
|
| 8 |
8
제5항에 있어서, 상기 새로운 엣지의 집합으로 맵을 축소하는 단계는,축소점 랜드마크를 따라서 이동하는 도중에 장애물을 만날 경우, 경로 탐사 장치가 장애물을 따라 이동하는 도중 새로운 볼록 랜드마크가 탐지되는 경우 맵 분해를 수행하는 것을 특징으로 하는 확장된 BSA 커버리지 경로계획 방법
|
| 9 |
9
제5항에 있어서, 상기 맵에 대하여 축소작업을 수행하는 단계는,축소점 랜드마크가 존재하지 않을 때까지 맵의 축소작업을 계속하는 것을 특징으로 하는 확장된 BSA 커버리지 경로계획 방법
|
| 10 |
10
삭제
|
| 11 |
11
제1항에 있어서, 상기 맵 분해 조건은,수직선과 엣지의 교차점은 랜드마크 집합에 속하지 않으며, 수직선 엣지는 장애물을 지나가지 않으며, 볼록 랜드마크와 생성된 수직선 엣지의 유클리드 거리(Euclidean distance)를 계산하여 수직선 엣지 중에서 가장 짧은 거리의 수직선 엣지를 선택하며, 생성된 수직선 엣지는 기 생성된 엣지 집합과 결합하지 않고 별도의 수직선 엣지 집합에 속하는 것을 특징으로 하는 확장된 BSA 커버리지 경로계획 방법
|
| 12 |
12
제1항에 있어서, 상기 A* 기법을 적용하여 맵을 분해하는 단계는,분해된 복수 개의 맵 중 하나의 맵을 구성하는 엣지 집합 중에서 임의의 한 개의 엣지를 선택하는 단계;선택된 엣지를 구성하는 두 개의 랜드마크 중 하나의 랜드마크를 시작점으로 설정하고, 다른 하나의 랜드마크를 목표점으로 설정하는 단계; 및전체 맵 중에서 시작점으로부터 목표점까지 연결되는 엣지로 구성되는 분해 맵을 생성하는 단계를 포함하는 것을 특징으로 하는 확장된 BSA 커버리지 경로계획 방법
|
| 13 |
13
제12항에 있어서, 상기 분해 맵을 생성하는 단계는,엣지의 시작이 되는 랜드마크와 연결될 랜드마크가 두 개가 탐지되는 경우, 목표점으로 설정된 랜드마크와 가까운 랜드마크를 엣지를 구성할 랜드마크로 선택하는 것을 특징으로 하는 확장된 BSA 커버리지 경로계획 방법
|
| 14 |
14
제1항 내지 제3항, 제5항 내지 제9항 및 제11항 내지 제13항 중 어느 하나의 항에 따른 확장된 BSA 커버리지 경로계획 방법을 수행하기 위한, 컴퓨터 프로그램이 기록된 컴퓨터로 판독 가능한 기록 매체
|
| 15 |
15
맵의 벽을 따라 이동하면서 랜드마크를 탐지하여 랜드마크의 정보를 수집하는 정보 수집부;상기 정보 수집부에 의해 수집된 랜드마크의 정보를 이용하여 탐지된 랜드마크가 볼록 랜드마크인지 오목 랜드마크인지를 판단하는 랜드마크 판단부;상기 랜드마크 판단부의 판단에 따른 볼록 랜드마크의 유무에 따라 맵 축소 및 맵 분해 중 하나의 동작을 수행하는 동작 수행부; 및상기 동작 수행부에서 수행된 동작에 따라 분해된 맵에 대하여 BSA(backtracking spiral algorithm)를 이용하여 경로를 생성하는 경로 생성부를 포함하며,상기 동작 수행부는,상기 랜드마크 판단부가 볼록 랜드마크가 없다고 판단한 경우, 오목 랜드마크를 통해 계산된 축소점 랜드마크를 이용하여 맵에 대하여 축소작업을 수행하는 맵 축소부; 및상기 랜드마크 판단부가 볼록 랜드마크가 있다고 판단한 경우, 맵에 대하여 맵 분해를 수행하는 맵 분해부를 포함하고,상기 맵 분해부는,볼록 랜드마크로부터 각각의 엣지까지 수직선으로 연결한 수직선 엣지를 생성하는 수직선 엣지 생성부;생성된 수직선 엣지 중에서 맵 분해 조건을 만족하는 수직선 엣지를 선택하는 수직선 엣지 선택부;선택된 수직선 엣지로 구성되는 분해 엣지 집합을 생성하는 분해 엣지 집합 생성부; 및분해 엣지 집합 및 맵의 엣지 집합에 A* 기법을 적용하여 맵을 분해하는 분해부를 포함하는 것을 특징으로 하는 확장된 BSA 커버리지 경로계획 장치
|
| 16 |
16
삭제
|
| 17 |
17
제15항에 있어서, 상기 맵 축소부는,각각의 오목 랜드마크를 서로 연결하거나, 오목 랜드마크와 경로 탐사 장치의 현재 위치를 연결한 엣지를 생성하는 엣지 생성부;생성된 복수 개의 엣지로 구성되는 엣지 집합을 생성하는 엣지 집합 생성부;생성된 엣지 집합으로 구획되는 맵 구역을 생성하는 맵 구역 생성부;각각의 오목 랜드마크 또는 경로 탐사 장치의 현재 위치를 중심으로 상, 하, 좌, 우 및 각각의 대각선 방향에 위치하는 8개의 격자 중 맵 구역의 내부에 위치하는 격자를 축소점 랜드마크로 선택하는 축소점 랜드마크 선택부; 및선택된 축소점 랜드마크를 서로 연결하여 축소점 랜드마크로 구성된 새로운 엣지의 집합으로 맵을 축소하는 축소부를 포함하는 것을 특징으로 하는 확장된 BSA 커버리지 경로계획 장치
|
| 18 |
18
삭제
|
