1 |
1
다중 임무점 방문을 위한 경로 계획 장치에 의해 수행되는 다중 임무점 방문을 위한 경로 계획 방법으로서,임무 시작점으로부터 시작하여 복수의 임무점을 방문하고 임무 종료점으로 귀환하는 무인 이동체의 다중 임무점 경로에 대하여, 도착점이 동일한 구간 경로의 기 연산된 구간 경로 계획 정보를 재사용하여 각각의 구간 경로 비용을 연산 및 제1 경로 계획을 생성하는 단계; 및상기 도착점을 변경한 후, 상기 도착점의 변경 전의 상기 제1 경로 계획을 재사용하여 제2 경로 계획을 생성하는 단계; 및상기 도착점을 이전에 선택하지 않은 도착점들로 변경하면서, 상기 제2 경로 계획을 잔여 도착점들에 대하여 각각 생성하고, 상기 제1 경로 계획과 상기 제2 경로 계획들을 기초로 초기 경로 계획을 생성하는 단계;를 포함하고,상기 제1 경로 계획을 생성하는 단계는상기 복수의 임무점과 상기 임무 종료점을 포함하는 도착점 리스트 중 하나를 도착점으로 설정하고, 상기 도착점 리스트 중 상기 도착점으로 설정하지 않은 임무점들과 상기 임무 시작점을 포함하는 출발점 리스트 중 하나를 출발점으로 설정하여 최초의 구간 경로 계획을 생성하는 단계와,이전 구간의 도착점은 유지한 상태에서, 상기 출발점을 상기 출발점 리스트 중 상기 이전 구간의 구간 경로 계획 생성 단계에서 선택되지 않은 출발점으로 변경한 다음 구간에 대하여 상기 이전 구간의 구간 경로 계획 정보를 재사용하여 다음 구간에 대한 구간 경로 계획을 상기 출발점 리스트의 잔여 출발점에 대하여 각각 수행하는 단계를 포함하는 것인 다중 임무점 방문을 위한 경로 계획 방법
|
2 |
2
삭제
|
3 |
3
제1항에 있어서,상기 제2 경로 계획을 생성하는 단계는,상기 도착점을 제1 도착점에서 제2 도착점으로 변경하는 단계와,상기 도착점의 변경 전의 상기 제1 도착점에서 상기 제2 도착점까지의 경로 비용을 보정값으로하여, 상기 도착점의 변경 후의 상기 제1 도착점 및 상기 제2 도착점 사이의 경로 비용을 보정하는 단계와,상기 보정값에 의한 상기 제1 도착점의 구간 경로 비용의 증가 또는 감소 비용을 기초로 상기 제1 도착점과 상기 제1 도착점에 대응하는 각각의 출발점들 사이의 구간 경로 비용을 보정하는 단계를 포함하는 것인 다중 임무점 방문을 위한 경로 계획 방법
|
4 |
4
제1항에 있어서,상기 구간 경로 계획 정보는,상기 구간 경로 비용에 대한 정보, 임의 셀에 인접한 셀의 상기 구간 경로 비용을 사용하여 상기 도착점부터 상기 임의 셀까지의 최적 경로 비용을 예측하는 값에 대한 정보 및 상기 도착점으로부터 하나씩 확장될 그리드 셀(grid cell)들이 셀 탐색 순서대로 저장된 우선순위 대기열에 대한 정보 중 적어도 하나의 정보를 포함하는 것인 다중 임무점 방문을 위한 경로 계획 방법
|
5 |
5
제4항에 있어서,상기 우선순위 대기열에 대한 정보는,상기 도착점으로부터 상기 임의 셀까지의 최적 경로 비용, 출발점으로부터 임의 셀까지의 어림값에 가중치를 부여한 값 중 적어도 하나를 기초로 연산되는 다중 임무점 방문을 위한 경로 계획 방법
|
6 |
6
제5항에 있어서,상기 복수의 임무점과 상기 임무 종료점을 포함하는 도착점 리스트 중 어느 하나의 도착점에 대하여, 상기 가중치를 단계적으로 감소하고, 상기 가중치의 단계적 감소에 대응하여, 상기 우선순위 대기열을 재정렬하며, 재정렬된 상기 우선순위 대기열을 기초로 상기 제1 경로 계획을 재생성하는 단계; 및상기 도착점을 이전에 선택하지 않은 도착점들로 변경하면서, 상기 제1 경로 계획을 잔여 도착점들에 대하여 각각 생성하고, 생성된 제1 경로 계획들을 기초로 상기 초기 경로 계획을 재계획하는 단계;를 더 포함하는 다중 임무점 방문을 위한 경로 계획 방법
|
7 |
7
다중 임무점 방문을 위한 무인 이동체의 경로를 계획하는 장치로서,임무 시작점, 복수의 임무점 및 임무 종료점을 포함하는 임무점에 대한 정보를 입력 받는 입력부;상기 다중 임무점을 방문하기 위한 경로 계획을 출력하는 출력부;상기 임무점에 대한 정보에 기초하여 상기 경로 계획을 연산한 후, 상기 출력부를 제어하여, 상기 경로 계획을 출력하는 제어부;를 포함하고,상기 제어부는임무 시작점으로부터 시작하여 복수의 임무점을 방문하고 임무 종료점으로 귀환하는 무인 이동체의 다중 임무점 경로에 대하여, 도착점이 동일한 구간 경로의 기 연산된 구간 경로 계획 정보를 재사용하여 각각의 구간 경로 비용을 연산 및 제1 경로 계획을 생성하고,상기 도착점을 변경한 후, 상기 도착점의 변경 전의 상기 제1 경로 계획을 재사용하여 제2 경로 계획을 생성하고,상기 도착점을 이전에 선택하지 않은 도착점들로 변경하면서, 상기 제2 경로 계획을 잔여 도착점들에 대하여 각각 생성하고, 상기 제1 경로 계획과 상기 제2 경로 계획들을 기초로 초기 경로 계획을 생성하고,상기 제어부는상기 제1 경로 계획을 생성하는 경우,상기 복수의 임무점과 상기 임무 종료점을 포함하는 도착점 리스트 중 하나를 도착점으로 설정하고, 상기 도착점 리스트 중 상기 도착점으로 설정하지 않은 임무점들과 상기 임무 시작점을 포함하는 출발점 리스트 중 하나를 출발점으로 설정하여 최초의 구간 경로 계획을 생성하고,이전 구간의 도착점은 유지한 상태에서, 상기 출발점을 상기 출발점 리스트 중 상기 이전 구간의 구간 경로 계획 생성 단계에서 선택되지 않은 출발점으로 변경한 다음 구간에 대하여 상기 이전 구간의 구간 경로 계획 정보를 재사용하여 다음 구간에 대한 구간 경로 계획을 상기 출발점 리스트의 잔여 출발점에 대하여 각각 수행하는 것인 다중 임무점 방문을 위한 경로 계획 장치
|
8 |
8
삭제
|
9 |
9
제7항에 있어서,상기 제어부는상기 제2 경로 계획을 생성하는 경우,상기 도착점을 제1 도착점에서 제2 도착점으로 변경하고,상기 도착점의 변경 전의 상기 제1 도착점에서 상기 제2 도착점까지의 경로 비용을 보정값으로하여, 상기 도착점의 변경 후의 상기 제1 도착점 및 상기 제2 도착점 사이의 경로 비용을 보정하고,상기 보정값에 의한 상기 제1 도착점의 구간 경로 비용의 증가 또는 감소 비용을 기초로 상기 제1 도착점과 상기 제1 도착점에 대응하는 각각의 출발점들 사이의 구간 경로 비용을 보정하는 것인 다중 임무점 방문을 위한 경로 계획 장치
|
10 |
10
제7항에 있어서,상기 구간 경로 계획 정보는,상기 구간 경로 비용에 대한 정보, 임의 셀에 인접한 셀의 상기 구간 경로 비용을 사용하여 상기 임의 셀까지의 최적 경로 비용을 예측하는 값에 대한 정보, 도착점으로부터 하나씩 확장될 그리드 셀(grid cell)들이 셀 탐색 순서대로 저장된 우선순위 대기열에 대한 정보 중 적어도 하나의 정보를 포함하는 것인 다중 임무점 방문을 위한 경로 계획 장치
|
11 |
11
제10항에 있어서,상기 제어부는상기 도착점으로부터 상기 임의 셀까지의 최적 경로 비용, 출발점으로부터 임의 셀까지의 어림값에 가중치를 부여한 값 중 적어도 하나를 기초로 상기 우선순위 대기열에 대한 정보를 연산하는 다중 임무점 방문을 위한 경로 계획 장치
|
12 |
12
제11항에 있어서,상기 제어부는상기 복수의 임무점과 상기 임무 종료점을 포함하는 도착점 리스트 중 어느 하나의 도착점에 대하여, 상기 가중치를 단계적으로 감소하고, 상기 가중치의 단계적 감소에 대응하여, 상기 우선순위 대기열을 재정렬하며, 재정렬된 상기 우선순위 대기열을 기초로 상기 제1 경로 계획을 재생성하고,상기 도착점을 이전에 선택하지 않은 도착점들로 변경하면서, 상기 제1 경로 계획을 잔여 도착점들에 대하여 각각 생성하고, 생성된 제1 경로 계획들을 기초로 상기 초기 경로 계획을 재계획하는 것인 다중 임무점 방문을 위한 경로 계획 장치
|