Rule-Based System (3) - Rete

2023.01.07 - [Game AI] - Rule-Based System (2)

Rule-Based System (2)

 

 

Unification

---

다음과 같이 와일드카드를 이용한 패턴이 있다고 해보자.

(?person (hp 0-15))
AND
(라디오 (held-by ?person))

 

그리고 데이터 베이스는 다음과 같다.

데이비드 (hp 30)
레베카 (hp 15)
루시 (hp 25)
라디오 (held-by 루시)

 

첫번째 person 와일드 카드는 레베카를, 두번째 라디오를 들고 있는 와일드카드는 루시가 매칭될 것이다.

 

그런데 만약 hp가 0-15이면서 라디오를 들고 있는 사람을 선택하고 싶었다면 어떻게 해야할까? 혹은 hp가 0-15인 사람과 라디오를 든 사람이 달라야 한다는 조건을 주고 싶다면 또 어떻게 해야할까?

 

이를 위해서 와일드카드에 id를 부여할 수 있다.

(?person-1 (hp 0-15))
AND
(라디오 (held-by ?person-1))

위와 같이 쓰면 hp가 0-15이면서 라디오를 들고 있는 인원을 매치시킬 수 있다.

 

 

 

퍼포먼스

 

그럼 퍼포먼스를 생각해보자. 

 

앞선 예에서 인원(데이터)이 n명이 있다고 가정해보자.

 

(?person-1 (hp 0-15))
AND
(라디오 (held-by ?person-2))

그리고 위와 같이 hp가 0-15인 인원이 있고, 라디오를 들고 있는 인원이 따로 있는 매칭을 생각해보자.

 

위와 같은 매칭은 최악의 경우 $O(n^2)$의 퍼포먼스를 보인다. 만약 조건이 2개가 아니라 m개라고 한다면 $O(n^m)$이라는 말도 안 되는 속도를 가지게 된다.

 

물론 이를 크게 개선해서 $O(nm)$의 퍼포먼스를 보이는 통합 알고리즘도 있긴 하지만 훨씬 복잡해진다.

 

다행히 간단하면서 속도도 빠른 방법이 존재하는데 다음에 설명할 Rete다.

 

 

---

 

Rete

---

 

그림1

 

레테는 위와 같은 모양의 directed acyclic graph이다.

 

동그라미(패턴 노드)는 조건을 , 네모(join 노드)는 AND를, 그리고 맨 아래 흰 노드는 실행할 규칙을 나타낸다.

 

 

위 그림의 Rete는 다음과 같은 규칙을 표현한다.

통신장비 교환 :
    IF
        (?person-1 (hp < 15))
        AND
        (라디오 (held-by ?person-1))
        AND
        (?person-2 (hp > 45))
    THEN
        remove(라디오 (held-by ?person-1))
        add(라디오 (held-by ?person-2))

지원 변경 : 
    IF
        (?person-1 (hp < 15))
        AND
        (?person-2 (hp > 45))
        AND
        (?person-2 (지원 ?person-1))
    THEN
        remove(?person-2 (지원 ?person-1))
        add(?person-1 (지원 ?person-2))

 

 

 

 

매칭 방법

Rete에서 노드와 DB는 위에서부터 아래로 매칭되기 시작한다.

 

만약 다음과 같은 조건이

(?person (hp < 15))

 

아래 DB와 매칭된다면,

(데이비드 (hp 12))

 

아래와 같이 변수를 바인딩 한 뒤에 아래 노드로 넘겨준다.

?person = 데이비드

 

 

이 때 매칭되는 DB가 2개 이상이라면 다음과 같이 아래 노드로 넘겨준다.

?person = 데이비드
OR
?person = 레베카

 

Join 노드 (네모난 노드)에서는 넘겨 받은 바인딩된 변수들의 교집합을 처리하여 아래로 넘겨준다. 만약 교집합이 없다면 아무것도 넘겨주지 않는다.

 

 

이렇게 바인딩된 변수를 위에서 아래로 넘겨주다가, 바인딩된 변수를 넘겨받은 규칙 노드가 존재한다면, 해당 규칙 노드를 리스트에 다 저장한다. 규칙 노드가 넘겨 받은 바인딩된 변수들도 저장해준다.

 

자이제 그림1과 같은 Rete에 다음과 같은 DB가 넘겨졌다고 해보자.

(레베카 (hp 50) (지원 : 데이비드))
(데이비드 (hp 30))
(루시 (hp 40))
(팔코 (hp 10) (지원 : 루시))
(라디오 (held-by 팔코))

 

 

그러면 Rete는 다음과 같은 상태가 된다.

 

 

'통신장비 교환'에는 인풋이 들어갔기 때문에 실행된다. 반면 '지원 변경'은 실행되지 않는다.

 

 

 

Fact의 추가 제거

어떤 Fact를 추가하거나 제거하려면 우선 이런 추가/제거 사실을 모든 패턴 노드에게 전달한다. 각 노드는 알아서 이런 Fact들을 처리하고, 아래에 있는 노드로 변경 사항을 전파한다.

 

만약 노드가 업데이트 되지 않았다면 아래 노드로 전파할 필요가 없다.

 

 

 

업데이트 관리

Fact의 추가/제거가 수행되는 매 iteration마다 추가/제거 요청을 패턴 노드들한테 해준다. 이 과정중에 실행되는 규칙이 있다고 해도 그냥 실행되도록 내버려둔다.

 

일반적으로, 모든 제거를 수행한 다음 추가를 수행하는 것이 더 효율적이다.

 

업데이트가 끝나고 나면 실행 가능한 규칙 리스트가 변경될 것이고, 실행이 가능해진다.

 

 

 

업데이트의 예

아래와 같이 추가/제거로 DB업데이트를 표현할 수 있다.

remove (팔코 (hp 10))
add (팔코 (hp 70))
remove (루시 (hp 40))
add (루시 (hp 5))

앞서 remove를 먼저 수행하는 게 효율적이라고 했으므로 remove를 먼저 해주고, 그다음 add를 수행한다.

 

이 과정에서 바인딩이 제거되기도, 추가되기도 하며 최종적으로 실행 가능한 규칙과 그 인풋이 변경될 것이다.

 

 

퍼포먼스

$O(nmp)$ 의 속도를 지닌다. n은 규칙의 갯수, m은 규칙당 조건의 갯수, p는 DB에 있는 Fact의 갯수.

$O(nmq)$ 의 메모리를 사용한다. q는 패턴당 매칭되는 와일드 카드의 갯수이다.

 

 

 

기타

만약 Rule Sets이 너무 방대해진 경우 Rete를 써도 퍼포먼스가 낮아질 수 있다. 이런 경우에는 절대 같이 실행되지 않는 애들을 서로 나눈 뒤 상황에 따라 on/off 하며 불필요한 연산을 줄일 수 있다.

 

DB 변경에 대한 로그를 저장하는 것이 도움 될 수 있다. 물론 인게임에서 매 프레임 이런 로그를 저장할 수는 없겠지만 테스트 환경에서라면 가능하다. 

 

룰베이스 시스템은 학습이 없는 의사결정 시스템중에 굉장히 복잡한 편에 속한다. 룰 베이스 시스템은 굉장히 정교한 AI를 설계할 수 있지만 구현이 어렵고 GUI 에디터를 제공하는 데에 한계가 있어 표현력이 굉장히 좋음에도 FSM이나 행동 트리만큼 잘 쓰이지 않는다.

 

---

참고 : Ian Millington, AI for GAMES 3rd edition, CRC press, [Chapter 5.8]