1 |
1
OHT 시스템의 동적 라우팅 방법에 있어서,차량이 서로 인접한 두 노드 사이의 엣지를 통하여 다른 하나의 노드까지 이동하는 데 걸리는 시간인 Q 값을 기록한 Q 테이블을 생성하는 과정;목적지 노드를 배정받은 차량이 현재 노드와 다음 노드 사이의 통과 엣지를 통과할 때, 상기 차량의 통과 시간을 측정하는 과정;복수의 엣지들 중 상기 통과 시간에 의해 갱신될 타겟 엣지들을 추출하는 과정; 및상기 차량이 상기 목적지 노드까지 이동하는 데 걸리는 시간값으로서, 상기 통과 시간에 부분적으로 기초하여 상기 통과 엣지와의 거리에 따라 상기 타겟 엣지들에 대한 Q 값을 차등적으로 갱신하는 과정을 포함하는 동적 라우팅 방법
|
2 |
2
제1항에 있어서,상기 타겟 엣지들을 추출하는 과정은,상기 복수의 엣지들 중에서 상기 다음 노드에서 상기 목적지 노드로 이동하는 데 이용될 수 있는 엣지들과 상기 통과 엣지 모두를 제외한 엣지들을 상기 타겟 엣지들로 추출하는 과정을 포함하는 동적 라우팅 방법
|
3 |
3
제1항에 있어서,상기 타겟 엣지들에 대한 Q 값을 차등적으로 갱신하는 과정은,상기 통과 시간에 부분적으로 기초하되, 상기 통과 엣지와 가까운 타겟 엣지에 대한 Q 값의 변화량을 상기 통과 엣지와 먼 타겟 엣지에 대한 Q 값의 변화량보다 크도록 Q 값을 조정하는 과정을 포함하는 동적 라우팅 방법
|
4 |
4
제1항에 있어서,상기 타겟 엣지들에 대한 Q 값을 차등적으로 갱신하는 과정은,상기 목적지 노드와 상기 현재 노드 사이의 제1 포텐셜, 및 상기 목적지 노드와 상기 다음 노드 사이의 제2 포텐셜을 계산하는 과정;상기 제1 포텐셜과 상기 제2 포텐셜 간 차이를 계산하는 과정; 상기 통과 시간을 상기 차이만큼 조정함으로써 보상을 결정하는 과정;상기 타겟 엣지들과 상기 통과 엣지 간 거리를 계산하는 과정; 및상기 보상 및 상기 거리에 부분적으로 기초하여 상기 타겟 엣지들에 대한 Q 값을 갱신하는 과정을 포함하는 동적 라우팅 방법
|
5 |
5
제4항에 있어서, 상기 타겟 엣지들에 대한 Q 값을 차등적으로 갱신하는 과정은,상기 통과 엣지와의 거리가 멀수록 상기 보상을 상기 Q 값에 적게 반영하는 과정을 더 포함하는 동적 라우팅 방법
|
6 |
6
제4항에 있어서, 상기 타겟 엣지들에 대한 Q 값을 차등적으로 갱신하는 과정은,상기 Q 테이블에 기초하여 상기 다음 노드와 상기 목적지 노드 간 이동 시간을 계산하는 과정;상기 보상, 상기 이동 시간 및 상기 통과 엣지에 대한 Q 값에 기초하여 시간차 에러를 계산하는 과정; 및상기 통과 엣지와의 거리가 멀수록 상기 시간차 에러를 상기 Q 값에 적게 반영하는 과정을 더 포함하는 동적 라우팅 방법
|
7 |
7
제1항에 있어서,상기 Q 테이블을 생성하는 과정은,상기 Q 테이블에 포함된 상기 Q 값을 모두 0으로 설정하는 과정;제1 목적지 노드를 배정받은 제1 차량이 현재 노드와 다음 노드 사이의 제1 엣지를 통과할 때, 상기 제1 차량의 제1 통과 시간을 측정하는 과정;상기 Q 테이블에 기초하여 상기 제1 차량이 상기 다음 노드에서 상기 제1 목적지 노드까지 이동하는 데 걸리는 최단 시간을 계산하는 과정; 및상기 제1 통과 시간과 상기 최단 시간에 기초하여, 상기 제1 엣지를 통하여 상기 제1 목적지 노드까지 이동하는 데 걸리는 시간인 제1 Q 값을 설정하는 과정을 포함하는 동적 라우팅 방법
|
8 |
8
제1항에 있어서,차량 요청 노드로부터 차량 할당을 요청 받는 과정;갱신된 Q 테이블에 기초하여 복수의 차량 중 최적 차량을 선택하는 과정; 및볼츠만 소프트맥스 정책(boltzmann softmax policy)에 따라 상기 최적 차량을 상기 차량 요청 노드까지 이동시키는 과정;을 포함하는 동적 라우팅 방법
|
9 |
9
제8항에 있어서,상기 볼츠만 소프트맥스 정책은,상기 차량이 위치한 노드에 연결된 복수의 라우팅 엣지들이 존재하는 경우, 상기 복수의 라우팅 엣지들에 대한 Q 값의 비율에 따른 확률에 기초하여 상기 최적 차량을 상기 복수의 라우팅 엣지들 중 하나의 라우팅 엣지를 통해 이동시키는 것을 특징으로 하는 동적 라우팅 방법
|
10 |
10
제8항에 있어서,상기 최적 차량을 선택하는 과정은,상기 갱신된 Q 테이블에 기초하여 상기 복수의 차량이 상기 차량 요청 노드로 이동하는 데 걸리는 예상 시간들을 각각 계산하는 과정; 및상기 복수의 차량 중 예상 시간이 가장 짧은 차량을 상기 최적 차량으로 선택하는 과정을 포함하는 동적 라우팅 방법
|
11 |
11
OHT 시스템의 동적 라우팅 장치에 있어서,차량이 서로 인접한 두 노드 사이의 엣지를 통하여 다른 하나의 노드까지 이동하는 데 걸리는 시간인 Q 값을 기록한 Q 테이블을 생성하는 Q 테이블 생성부;목적지 노드를 배정받은 차량이 현재 노드와 다음 노드 사이의 통과 엣지를 통과할 때, 상기 차량의 통과 시간을 측정하는 측정부;복수의 엣지들 중 상기 통과 시간에 의해 갱신될 타겟 엣지들을 추출하는 타겟 엣지 추출부; 및상기 차량이 상기 목적지 노드까지 이동하는 데 걸리는 시간값으로서, 상기 통과 시간에 부분적으로 기초하여 상기 통과 엣지와의 거리에 따라 상기 타겟 엣지들에 대한 Q 값을 차등적으로 갱신하는 Q 테이블 관리부을 포함하는 동적 라우팅 장치
|
12 |
12
제11항에 있어서,상기 타겟 엣지 추출부는,상기 복수의 엣지들 중에서 상기 다음 노드에서 상기 목적지 노드로 이동하는 데 이용될 수 있는 엣지들과 상기 통과 엣지 모두를 제외한 엣지들을 상기 타겟 엣지들로 추출하는 것을 특징으로 하는 동적 라우팅 장치
|
13 |
13
제11항에 있어서,상기 Q 테이블 관리부는,상기 통과 시간에 부분적으로 기초하되, 상기 통과 엣지와 가까운 타겟 엣지에 대한 Q 값의 변화량을 상기 통과 엣지와 먼 타겟 엣지에 대한 Q 값의 변화량보다 크도록 Q 값을 조정하는 것을 특징으로 하는 동적 라우팅 장치
|
14 |
14
제11항에 있어서,상기 Q 테이블 관리부는,상기 목적지 노드와 상기 현재 노드 사이의 제1 포텐셜, 및 상기 목적지 노드와 상기 다음 노드 사이의 제2 포텐셜을 계산하고, 상기 제1 포텐셜과 상기 제2 포텐셜 간 차이를 계산하고, 상기 통과 시간을 상기 차이만큼 조정함으로써 보상을 결정하고, 상기 타겟 엣지들과 상기 통과 엣지 간 거리를 계산하고, 상기 보상 및 상기 거리에 부분적으로 기초하여 상기 타겟 엣지들에 대한 Q 값을 갱신하는 것을 특징으로 하는 동적 라우팅 장치
|
15 |
15
제14항에 있어서,상기 Q 테이블 관리부는,상기 통과 엣지와의 거리가 멀수록 상기 보상을 상기 Q 값에 적게 반영하는 것을 특징으로 하는 동적 라우팅 장치
|
16 |
16
제14항에 있어서,상기 Q 테이블 관리부는,상기 Q 테이블에 기초하여 상기 다음 노드와 상기 목적지 노드 간 이동 시간을 계산하고, 상기 보상, 상기 이동 시간 및 상기 통과 엣지에 대한 Q 값에 기초하여 시간차 에러를 계산하고, 상기 통과 엣지와의 거리가 멀수록 상기 시간차 에러를 상기 Q 값에 적게 반영하는 것을 특징으로 하는 동적 라우팅 장치
|
17 |
17
제11항에 있어서,상기 측정부는,제1 목적지 노드를 배정받은 제1 차량이 현재 노드와 다음 노드 사이의 제1 엣지를 통과할 때, 상기 제1 차량의 제1 통과 시간을 측정하고,상기 Q 테이블 생성부는,상기 Q 테이블에 포함된 상기 Q 값을 모두 0으로 설정하고, 상기 Q 테이블에 기초하여 상기 제1 차량이 상기 다음 노드에서 상기 제1 목적지 노드까지 이동하는 데 걸리는 최단 시간을 계산하고, 상기 제1 통과 시간과 상기 최단 시간에 기초하여, 상기 제1 엣지를 통하여 상기 제1 목적지 노드까지 이동하는 데 걸리는 시간인 제1 Q 값을 설정하는 것을 특징으로 하는 동적 라우팅 장치
|
18 |
18
제11항에 있어서,차량 요청 노드로부터 차량 할당을 요청받는 수신부;갱신된 Q 테이블에 기초하여 복수의 차량 중 최적 차량을 선택하는 차량 선택부; 및볼츠만 소프트맥스 정책(boltzmann softmax policy)에 따라 상기 최적 차량을 상기 차량 요청 노드까지 이동시키는 차량 제어부를 더 포함하는 동적 라우팅 장치
|
19 |
19
제18항에 있어서,상기 볼츠만 소프트맥스 정책은,상기 차량이 위치한 노드에 연결된 복수의 라우팅 엣지들이 존재하는 경우, 상기 복수의 라우팅 엣지들에 대한 Q 값의 비율에 따른 확률에 기초하여 상기 최적 차량을 상기 복수의 라우팅 엣지들 중 하나의 라우팅 엣지를 통해 이동시키는 것을 특징으로 하는 동적 라우팅 장치
|
20 |
20
제18항에 있어서,상기 차량 선택부는,상기 갱신된 Q 테이블에 기초하여 상기 복수의 차량이 상기 차량 요청 노드로 이동하는 데 걸리는 예상 시간들을 각각 계산하고, 상기 복수의 차량 중 예상 시간이 가장 짧은 차량을 상기 최적 차량으로 선택하는 것을 특징으로 하는 동적 라우팅 장치
|