(-100, -100) (-75, -75)
(-50, -50) (-25, -25)
(0, 0)
- 100 % 0 % 100 %
100 %
<Figure 4.6> Node Expansion in State Space
<Figure 4.6> Node Expansion in State Space
<Figure 4.6> Node Expansion in State Space
<Figure 4.6> Node Expansion in State Space
앞서 설명한 과정을 통해 연산자에 의해서 부모 노드로부터 확장되는 자식 노 드는 8 가지 평가 요소를 위반해서는 안된다.
3.
3.
3.
3. 평가평가평가 함수의평가 함수의함수의함수의 설정설정설정설정
평가 함수는 노드를 평가하는 함수로, 가장 최적인 시퀀스를 이루는데 도움 이 되는 노드들이 선택될 수 있도록, 그러한 노드에 낮은 값을 주어야 한다. 즉, 평가 함수는 지출 함수로서 낮은 값을 가질수록 평가 값이 우수한 것이다.
평가 함수가 지출을 기준으로 정리되는 이유는 연산자에 의한 부모 노드의 파 생 및 확장을 시도할 때, 부모 노드와 자식 노드 사이의 지출을 더해가는 것으 로 평가 값을 계산하는 것이 편리하기 때문이다.
A* 탐색의 평가 함수는 식(4.1)과 같은 구조를 이룬다. 즉 노드 n의 평가값 f(n)은 식(4.1)과 같이 정해진다[19].
) ( ) ( )
( n g n h n
f = + × k (n )
(4.1)) (n
g
은 현재 노드까지의 지출값을 의미한다.h (n )
은 앞으로의 예상 지출로 휴 리스틱 함수이다.k (n )
함수는 휴리스틱 함수를 강화하기 위해 쓰이는 가중 함수 로, 안전성과 관련된 평가 요소들이 한계 값에 가까워진 정도를 의미한다.) (n
f
= 총 입수, 배수 시간)
(n
g
= 현재까지 입수, 배수에 걸린 총 시간)
(n
h
= 앞으로 입수, 배수에 걸릴 예상 시간)
(n
k
= 평가 요소와 관련한 안전성 관련 함수여기서 설정된 평가 함수를 기준으로 탐색은 평가 함수 값이 작은 방향으로 진행하게 되며, 결과적으로 다음의 두 가지 목표를 달성하게 된다.
) (n
g
,h (n )
,k (n )
을 다음 가, 나, 다와 같이 설계한다.가가
가가. . . 과거. 과거과거과거 지출지출지출 함수지출 함수함수함수( ( ( (
g (n )
) ) ) )현재 노드를 n이라 하고, 노드 n의 t번째 대의 조상 노드를
p
t(n )
, 노드와 노 드 사이의 지출 함수(Cost Function)를c ( n
1, n
2)
이라 하면, 현재까지 걸린 총 입수, 배수 시간은 현재의 스텝이 j스텝일 때, 거쳐온 총 지출의 회수는 j-1 번 으로, 총 지출 값은 식(4.2)과 같이 정의된다.g (n )
는 현재 노드 n까지의 지출 의 총합이므로 식(4.2)의 결과와 같으며, 식 (4.3)과 같이 나타낼 수 있다.)) ( ), ( ( ...
)) ( ), ( ( )) ( ,
( n p
1n c p n p
2n c p
2n p
1n
c +
t+ +
j− j− (4.2)) (n
g
=∑
−=
− 1
1
1
( ), ( )) (
j
k
k
k
n p n
p
c
(4.3)) (n
p
t 함수는 밸러스트 시스템에 따른 밸러스트 탱크의 조합과 펌프 용량에 따 른 입수, 배수의 양에 의해 결정된다.나나
나나. . . 미래. 미래미래미래 지출지출지출 함수지출 함수함수함수( ( ( (
h (n )
) ) ) )) (n
h
는 현재 노드 n에서 목표 노드까지의 예상 지출로 정의되어야 하므로, 본 문제에서는 앞으로 남은 밸러스트수 교체 시간으로 설정되어야 한다. A* 탐색의 휴리스틱 함수이므로 허용성(Admissibility)을 지키는 한도 내에서 가장 큰 값을 도출해 낼 수 있는 함수여야 한다.Minimize Ballasting Time
Minimize Ballasting Time Minimize Ballasting Time
Minimize Ballasting Time
Satisfy All Safety Criteria
Satisfy All Safety Criteria
Satisfy All Safety Criteria
Satisfy All Safety Criteria
) (k
t
n 는 현재 노드 n의 k 번째 밸러스트 탱크에 연결 가능한 펌프 중 가장 펌프 용량이 큰 펌프를 연결하였을 때, k 번째 밸러스트 탱크의 남은 물을 모두 입수, 배수(만약 k 번째 밸러스트 탱크가 교체가 전혀 안된 밸러스트 탱크라면 먼저 탱크를 비우기 위해 필요한 양 100%와 탱크를 다시 채우기 위한 양 100%를 더한 200%의 수량)할 경우 걸리는 시간이라 정의한다.총 p 개의 펌프가 존재하고, j 개의 밸러스트 탱크가 있을 때,
h (n )
함수를 식 (4.4)와 같이 설정한다.) (n
h
=∑
= j
k n
k p
1t ( )
1
(4.4)어떠한 경우든 p 개의 탱크가 항상 같이 선택되어 입수, 배수될 때의 남은 시 간이므로, 현재 노드(스텝)에서 어떠한 가장 효율적인 시퀀스로 입수, 배수를 하 더라도 그 시간이
h (n )
시간보다는 짧아질 수 없다. 따라서h
c(n )
는 현재 노드 에서 가장 이상적인 방향으로 알고리즘이 진행했을 때 얻어지는 입수, 배수에 필요한 남은 시간의 최소값이다. 따라서 A* 탐색의 적합성을 보장하기 위한 식 (4.5)와 같은 허용성이 지켜진다.) ( ) ( n h n
h ≤
c (4.5)다다
다다. . . 가중. 가중가중가중 함수함수함수( 함수( ( (
k (n )
))))가중 함수
k (n )
은 안전성과 관련된 평가 요소가 한계 값에 가까워진 정도를 수치화한 것이다. 노드 n에서의 평가 요소가 한계 값에서 멀리 떨어질수록k (n )
은 0에 접근하고, 가까울수록 지수 함수에 적절한 기울기를 부여하는 가중치 a,b,c,~,h에 따라 큰 값을 가지게 된다.k (n )
함수가 평가 요소의 한계값에 가까 워 질 때만 영향력을 발휘하도록 하기 위하여, 특정 값에 가까워질 때 곡선의 기울기가 급속히 증가하는 지수 함수를 사용하였다. 이렇듯k (n )
함수는 노드 n 에서의 안전성이 높을수록 낮은 값을 가지며, 안전성이 낮을수록 높은 값을 가 진다.각 평가 요소의 계산값들이 평가 기준인 한계값에 가까울수록 지수 함수적으 로 큰 값을 가지도록 한다. k함수를 이용함으로써, 알고리즘이 평가 요소의 측면 에서 안전한 쪽으로 흘러가도록 유도한다. 8 가지의 평가 요소 수치들이 각각의 평가 기준 임계치에 근접할 경우 k함수는 이에 대해 벌점을 부여하게 된다.
각 평가 요소에 대해 가중치로 쓰인 a~h는 지수(exponential)함수에 적절한 기울기를 주어, 한계값에 매우 가까워졌을 때에만 k함수가 큰 값을 갖도록 한다.
1. 종강도 관련 가중 함수(