1 |
1
이동 로봇의 최적 경로 생성 방법에 있어서,격자 지도를 구성하는 각각의 격자점에 할당된 격자 비용에 기초한 제1 경로 생성 방법을 통해 출발 위치로부터 목표 위치까지의 1차 경로가 생성되는 단계와,상기 1차 경로 상의 적어도 일부 경로가 상기 격자 비용에 기초한 제2 경로 생성 방법을 통해 재생성되어 최종 경로가 생성되는 단계를 포함하며, 상기 제2 경로 생성 방법은,(a) 상기 목표 위치 방향으로 상기 제1 경로 상에 순차적으로 위치하는 제1 방향 전환 격자점, 제2 방향 전환 격자점, 제3 방향 전환 격자점을 검출하는 단계와;(b) 상기 제2 방향 전환 격자점과 상기 제3 방향 전환 격자점 사이의 상기 제1 경로 상에서 적어도 하나의 중계점을 설정하는 단계와;(c) 상기 제1 방향 전환 격자점, 상기 각 중계점 및 상기 제3 방향 전환 격자점을 연결하는 각각의 후보 경로에 대한 중계점 경로 비용을 상기 격자 비용에 기초하여 산출하는 단계와;(d) 최소의 중계점 경로 비용을 발생하는 최소 비용 중계점을 추출하는 단계와;(e) 상기 제1 방향 전환 격자점, 상기 최소 비용 중계점 및 상기 제3 방향 전환 격자점을 연결하는 후보 경로가 상기 제1 방향 전환 격자점, 상기 제2 방향 전환 격자점 및 상기 제3 방향 전환 격자점을 연결하는 경로를 대체하여 재생성되는 단계를 포함하고,상기 격자 비용은 그라디언트 방법 상의 고유 비용(Intrinsic cost)과 근접 비용(Adjacent cost)을 포함하며;상기 (c) 단계에서 상기 중계점 경로 비용은 상기 후보 경로가 통과하는 격자 공간을 형성하는 격자점들의 상기 고유 비용에 기초하여 산출되는 공간 고유 비용과, 상기 제1 방향 전환 격자점과 상기 중계점 간의 상기 근접 비용의 합에 의해 산출되는 것을 특징으로 하는 이동 로봇의 최적 경로 생성 방법
|
2 |
2
제1항에 있어서,상기 제1 경로 생성 방법은 그라디언트 방법(Gradient method)이 적용되는 것을 특징으로 하는 이동 로봇의 최적 경로 생성 방법
|
3 |
3
삭제
|
4 |
4
제1항에 있어서,상기 제2 경로 생성 방법은 상기 출발 위치를 첫 번째 상기 제1 방향 전환 격자점으로 하여 상기 1차 경로 상의 방향 전환 격자점들에 대해 상기 (a) 단계 내지 상기 (e) 단계를 수행하여 경로가 재생성되는 것을 특징으로 하는 이동 로봇의 최적 경로 생성 방법
|
5 |
5
제4항에 있어서,상기 제2 경로 생성 방법은,(f) 상기 제1 방향 전환 격자점, 상기 제2 방향 전환 격자점 및 상기 제3 방향 전환 격자점을 연결하는 경우의 경로 비용을 추출하는 단계와,(g) 상기 (f) 단계에서 산출된 경로 비용과 상기 최소 중계점 경로 비용을 비교하는 단계를 더 포함하고;상기 (e) 단계는 상기 최소 중계점 경로 비용이 상기 (f) 단계에서 산출된 경로 비용보다 작은 경우 수행되는 것을 특징으로 하는 이동 로봇의 최적 경로 생성 방법
|
6 |
6
제5항에 있어서,상기 (b) 단계에서는 상기 제3 방향 전환 격자점이 상기 중계점의 하나로 설정되며;상기 (c) 단계에서는 상기 제1 방향 전환 격자점과 상기 제3 방향 전환 격자점을 연결하는 후보 경로에 대한 중계점 경로 비용이 산출되며;상기 (d) 단계에서 상기 최소 비용 중계점으로 상기 제3 방향 전환 격자점이 추출되는 경우, 상기 (e) 단계에서 상기 제1 방향 전환 격자점과 상기 제3 방향 전환 격자점을 연결하는 상기 후보 경로가 상기 제1 방향 전환 격자점, 상기 제2 방향 전환 격자점 및 상기 제3 방향 전환 격자점을 연결하는 경로를 대체하여 재생성되는 것을 특징으로 하는 이동 로봇의 최적 경로 생성 방법
|
7 |
7
삭제
|
8 |
8
제1항에 있어서,상기 (c) 단계는,(c1) 상기 격자 공간을 형성하며 한 방향으로 배열되는 변들과 상기 후보 경로가 교차하는 적어도 하나의 교차점을 추출하는 단계와;(c2) 상기 변을 형성하는 한 쌍의 격자점에 할당된 상기 고유 비용과, 상기 한 쌍의 격자점 각각과 상기 교차점 간의 거리에 기초하여 상기 교차점에 대한 교차점 고유 비용을 산출하는 단계와;(c3) 상기 교차점에 대해 산출된 상기 교차점 고유 비용을 합산하여 상기 공간 고유 비용을 산출하는 단계를 포함하는 것을 특징으로 하는 이동 로봇의 최적 경로 생성 방법
|
9 |
9
제8항에 있어서,상기 교차점 고유 비용은 수학식 ICcp = ICg1×L2 + ICg2×L1 (여기서, ICcp는 상기 교차점 고유 비용이고, ICg1과 ICg2는 상기 한 쌍의 격자점 각각의 상기 고유 비용이고, L1은 상기 고유 비용이 ICg1인 격자점과 상기 교차점 간의 거리이고, L2는 상기 고유 비용이 ICg2인 격자점과 상기 교차점 간의 거리이다)에 의해 산출되는 것을 특징으로 하는 이동 로봇의 최적 경로 생성 방법
|
10 |
10
제1항, 제2항, 제4항 내지 제6항, 제8항 및 제9항 중 어느 한 항에 따른 최적 경로 생성 방법이 적용된 이동 로봇
|