| 1 |
1
다중 임무점 방문을 위한 경로 계획 장치에 의해 수행되는 다중 임무점 방문을 위한 경로 계획 방법으로서,임무시작점으로부터 시작하여 복수의 임무점을 방문하고 임무종료점으로 귀환하여야 하는 무인 이동체의 다중 임무점 경로에 대하여, 도착점이 동일한 구간 경로의 기 계산된 경로 계획 정보를 재사용하여 각각의 구간 경로 비용을 계산 및 구간 경로 계획을 수행하는 단계와,상기 각각의 구간 경로 비용에 기초하여 상기 복수의 임무점에 대한 임무점 방문 순서를 결정하는 단계와,상기 결정된 임무점 방문 순서 및 상기 구간 경로 계획에 기초하여 상기 복수의 임무점을 방문하는 사전 경로 계획을 수행하는 단계를 포함하고,상기 각각의 구간 경로 비용을 계산 및 구간 경로 계획을 수행하는 단계는, 우선순위 큐에 저장된 키 값에 대응하는 순서로 인컨시스턴트 셀을 탐색하되, 상기 키 값을 바뀐 상기 임무시작점에 따라 다시 계산하여 상기 우선순위 큐를 재정렬하는다중 임무점 방문을 위한 경로 계획 방법
|
| 2 |
2
제 1 항에 있어서,상기 구간 경로 계획을 수행하는 단계는,상기 복수의 임무점과 상기 임무종료점으로 구성된 도착점리스트의 멤버 중 하나를 도착점으로 설정하고, 상기 도착점리스트의 멤버 중 상기 도착점으로 설정하지 않은 임무점들과 상기 임무시작점으로 구성된 출발점리스트의 멤버 중 하나를 출발점으로 설정하여 최초의 구간 경로 계획을 수행하는 단계와,이전 구간의 도착점은 유지한 채, 출발점을 상기 출발점리스트의 멤버 중 이전에 선택되지 않은 멤버로 변경한 다음 구간에 대하여, 상기 이전 구간의 상기 경로 계획 정보를 재사용하여 수행하는 상기 다음 구간에 대한 구간 경로 계획을 상기 출발점리스트의 잔여 멤버에 대하여 각각 수행하는 단계와,상기 도착점리스트의 멤버 중 이전에 선택되지 않은 멤버를 도착점으로 변경하고, 출발점을 상기 출발점리스트의 각각의 멤버로 변경하면서 각각 구간 경로 계획을 수행하는 단계를 포함하는다중 임무점 방문을 위한 경로 계획 방법
|
| 3 |
3
제 1 항에 있어서,상기 경로 계획 정보는, 상기 구간 경로 비용에 대한 정보, 임의 셀에 인접한 셀의 상기 구간 경로 비용을 사용하여 상기 임의 셀까지의 경로 비용을 예측하는 값에 대한 정보, 도착점으로부터 하나씩 확장된 그리드 셀(grid cell)들이 셀 탐색 순서대로 저장된 우선순위 대기열에 대한 정보 중 하나 이상의 정보를 포함하는다중 임무점 방문을 위한 경로 계획 방법
|
| 4 |
4
제 1 항에 있어서,상기 사전 경로 계획에 따라 상기 무인 이동체가 이동하던 중 이전에 식별되지 않은 장애물을 발견할 경우에 경로 재계획을 수행하는 단계를 더 포함하고,상기 경로 재계획을 수행하는 단계는, 도착점은 같지만 출발점은 다른 모든 구간 경로에 대하여 통합된 경로 계획 정보를 사용하는다중 임무점 방문을 위한 경로 계획 방법
|
| 5 |
5
제 4 항에 있어서,상기 통합된 경로 계획 정보는, 상기 구간 경로 비용에 대한 정보, 임의 셀에 인접한 셀의 상기 구간 경로 비용을 사용하여 상기 임의 셀까지의 경로 비용을 예측하는 값에 대한 정보 중 하나 이상의 정보를 포함하는다중 임무점 방문을 위한 경로 계획 방법
|
| 6 |
6
제 5 항에 있어서,상기 경로 재계획을 수행하는 단계는, 상기 무인 이동체의 경로를 따른 이동에 대응하는 보정값()을 사용하여, 도착점으로부터 하나씩 확장된 그리드 셀(grid cell)들이 셀 탐색 순서대로 저장된 우선순위 대기열을 갱신하는다중 임무점 방문을 위한 경로 계획 방법
|
| 7 |
7
제 6 항에 있어서,상기 경로 재계획을 수행하는 단계는, 상기 장애물이 발견되면 현재의 위치를 새로운 구간 출발점으로 설정하고 상기 보정값을 갱신하는 단계와,구간 도착점에 대응되는 상기 구간 경로 비용에 대한 정보, 상기 임의 셀까지의 경로 비용을 예측하는 값 및 상기 갱신된 보정값에 기초하여 상기 장애물로 인해 변화가 생긴 셀 간의 이동 비용을 갱신한 후 현재 구간 출발점과 구간 도착점으로 이루어지는 구간에 대해 실시하는 경로 탐색을 방문해야 할 잔여 임무점들에 대해 반복하는 단계와,상기 장애물을 회피하도록 임무점 방문 순서를 갱신하여 갱신된 임무점 방문 순서에 기초하여 상기 잔여 임무점들을 방문하는 재계획 경로를 결정하는 단계를 포함하는다중 임무점 방문을 위한 경로 계획 방법
|
| 8 |
8
임무시작점으로부터 시작하여 복수의 임무점을 방문하고 임무종료점으로 귀환하여야 하는 무인 이동체의 다중 임무점 경로에 대하여, 도착점이 동일한 구간 경로의 기 계산된 경로 계획 정보를 재사용하여 각각의 구간 경로 비용을 계산 및 구간 경로 계획을 수행하는 단계와,상기 각각의 구간 경로 비용에 기초하여 상기 복수의 임무점에 대한 임무점 방문 순서를 결정하는 단계와,상기 결정된 임무점 방문 순서 및 상기 구간 경로 계획에 기초하여 상기 복수의 임무점을 방문하는 사전 경로 계획을 수행하는 단계를 포함하고, 상기 각각의 구간 경로 비용을 계산 및 구간 경로 계획을 수행하는 단계는, 우선순위 큐에 저장된 키 값에 대응하는 순서로 인컨시스턴트 셀을 탐색하되, 상기 키 값을 바뀐 상기 임무시작점에 따라 다시 계산하여 상기 우선순위 큐를 재정렬하는 다중 임무점 방문을 위한 경로 계획 방법을 프로세서가 수행하도록 하는컴퓨터 프로그램이 저장된 컴퓨터 판독 가능한 기록매체
|
| 9 |
9
다중 임무점 방문을 위한 무인 이동체의 경로를 계획하는 장치로서,임무시작점, 복수의 임무점 및 임무종료점을 포함하는 임무점에 대한 정보를 입력받는 정보 입력부와,상기 다중 임무점을 방문하기 위한 경로 계획을 출력하는 출력부와,상기 임무점에 대한 정보에 기초하여 상기 경로 계획을 결정한 후 상기 출력을 제어하는 제어부를 포함하고,상기 제어부는,상기 임무시작점으로부터 시작하여 상기 복수의 임무점을 방문하고 상기 임무종료점으로 귀환하여야 하는 상기 무인 이동체의 다중 임무점 경로에 대하여, 도착점이 동일한 구간 경로의 기 계산된 경로 계획 정보를 재사용하여 각각의 구간 경로 비용을 계산 및 구간 경로 계획을 수행하며,상기 각각의 구간 경로 비용에 기초하여 상기 복수의 임무점에 대한 임무점 방문 순서를 결정하고,상기 결정된 임무점 방문 순서 및 상기 구간 경로 계획에 기초하여 상기 복수의 임무점을 방문하는 사전 경로 계획을 수행하며,상기 각각의 구간 경로 비용을 계산 및 구간 경로 계획을 수행할 때에, 우선순위 큐에 저장된 키 값에 대응하는 순서로 인컨시스턴트 셀을 탐색하되, 상기 키 값을 바뀐 상기 임무시작점에 따라 다시 계산하여 상기 우선순위 큐를 재정렬하는다중 임무점 방문을 위한 경로 계획 장치
|
| 10 |
10
제 9 항에 있어서,상기 제어부는,상기 구간 경로 계획을 수행할 때에, 상기 임무점들과 상기 임무종료점으로 구성된 도착점리스트의 멤버 중 하나를 도착점으로 설정하고, 상기 도착점리스트의 멤버 중 상기 도착점으로 설정하지 않은 임무점들과 상기 임무시작점으로 구성된 출발점리스트의 멤버 중 하나를 출발점으로 설정하여 최초의 구간 경로 계획을 수행하며,이전 구간의 도착점은 유지한 채, 출발점을 상기 출발점리스트의 멤버 중 이전에 선택되지 않은 멤버로 변경한 다음 구간에 대하여, 상기 이전 구간의 상기 경로 계획 정보를 재사용하여 수행하는 상기 다음 구간에 대한 구간 경로 계획을 상기 출발점리스트의 잔여 멤버에 대하여 각각 수행하고,상기 도착점리스트의 멤버 중 이전에 선택되지 않은 멤버를 도착점으로 변경하며, 출발점을 상기 출발점리스트의 각각의 멤버로 변경하면서 각각 구간 경로 계획을 수행하는다중 임무점 방문을 위한 경로 계획 장치
|
| 11 |
11
제 9 항에 있어서,상기 경로 계획 정보는, 상기 구간 경로 비용에 대한 정보, 임의 셀에 인접한 셀의 상기 구간 경로 비용을 사용하여 상기 임의 셀까지의 경로 비용을 예측하는 값에 대한 정보, 도착점으로부터 하나씩 확장된 그리드 셀(grid cell)들이 셀 탐색 순서대로 저장된 우선순위 대기열에 대한 정보 중 하나 이상의 정보를 포함하는다중 임무점 방문을 위한 경로 계획 장치
|
| 12 |
12
제 9 항에 있어서,상기 제어부는,상기 사전 경로 계획에 따라 상기 무인 이동체가 이동하던 중 이전에 식별되지 않은 장애물을 발견할 경우에 경로 재계획을 수행하되, 상기 경로 재계획을 수행할 때에, 도착점은 같지만 출발점은 다른 모든 구간 경로에 대하여 통합된 경로 계획 정보를 사용하는다중 임무점 방문을 위한 경로 계획 장치
|
| 13 |
13
제 12 항에 있어서,상기 통합된 경로 계획 정보는, 상기 구간 경로 비용에 대한 정보, 임의 셀에 인접한 셀의 상기 구간 경로 비용을 사용하여 상기 임의 셀까지의 경로 비용을 예측하는 값에 대한 정보 중 하나 이상의 정보를 포함하는다중 임무점 방문을 위한 경로 계획 장치
|
| 14 |
14
제 13 항에 있어서,상기 제어부는, 상기 경로 재계획을 수행할 때에, 상기 무인 이동체의 경로를 따른 이동에 대응하는 보정값()을 사용하여, 도착점으로부터 하나씩 확장된 그리드 셀(grid cell)들이 셀 탐색 순서대로 저장된 우선순위 대기열을 갱신하는다중 임무점 방문을 위한 경로 계획 장치
|
| 15 |
15
제 14 항에 있어서,상기 제어부는, 상기 경로 재계획을 수행할 때에, 상기 장애물이 발견되면 현재의 위치를 새로운 구간 출발점으로 설정하고 상기 보정값을 갱신하고,구간 도착점에 대응되는 상기 구간 경로 비용에 대한 정보, 상기 임의 셀까지의 경로 비용을 예측하는 값 및 상기 갱신된 보정값에 기초하여 상기 장애물로 인해 변화가 생긴 셀 간의 이동 비용을 갱신한 후 현재 구간 출발점과 구간 도착점으로 이루어지는 구간에 대해 실시하는 경로 탐색을 방문해야 할 잔여 임무점들에 대해 반복하며,상기 장애물을 회피하도록 임무점 방문 순서를 갱신하여 갱신된 임무점 방문 순서에 기초하여 상기 잔여 임무점들을 방문하는 재계획 경로를 결정하는다중 임무점 방문을 위한 경로 계획 장치
|
