퍼지 로직 의사 결정(Decision making)

2022.10.03 - [Game AI] - 퍼지 로직(Fuzzy Logic) -2

개요

---

퍼지 로직은 and, or, not을 사용하는 의사결정 시스템이라면 모두 적용이 가능하다.

 

의사 결정을 내릴 때는 항상 0혹은 1로만 표현할 수 있는게 아니다. 예를 들어 자동차의 가속이나 브래이크 패달은  0.5만큼 누를 수도 있어야 한다. 이런 경우에 전통적인 로직으로는 표현의 한계가 있다. 여기에 퍼지 로직을 접목시키면 이와 같은 grey area (0과1사이의 값)를 표현하는데 도움이 된다.

 

---

알고리즘

---

인풋은 실수, 열거형, boolean 등이 될 수 있다. 각각의 인풋은 퍼지 상태(fuzzy state)와 매칭되고 이런 매칭은 소속 함수를 통해 이뤄진다.

 

하나의 인풋이 여러 개의 퍼지 상태로 분리될 수 있다. 이 경우 분리된 상태들의 소속도의 합은 1이다.

 

아웃풋 역시 퍼지 상태이며 캐릭터가 취할 수 있는 각기 다른 행동들을 나타낸다.

 

남은 체력이 '부상' '건강함' 상태로 분리, 소속도의 합이 1이다

 

 

인풋 상태와 아웃풋 상태들을 연결하는 것이 퍼지 규칙(Fuzzy Rules)이다.

 

퍼지 규칙은 다음과 같이 쓸 수 있다.

 

IF input_state_1 & input_state_2 & ... & input_state_n THEN output_state_1

 

 

이 때, 기본적으로 AND만을 써서 규칙을 만든다.

 

위와 같은 규칙은 모든 input_state의 조합을 포함해야 한다. 

 

(체력 적음, 체력 보통, 체력 많음) , (총알 있음, 총알 없음)

 

위와 같은 input_state가 있는 경우 3*2가지의 규칙이 존재하게 된다.

 

 

결과값를 생성하기 위해서, 모든 규칙들을 실행한뒤 각각의 output_state의 소속도를 구한다. output_state가 중복되는 경우에는 가장 높은 값을 취한다.

 

예를 들어 인풋이 다음과 같고

 

(코너 진입, 코너 탈출) (속도 높음, 속도 낮음)

 

퍼지 규칙이 다음과 같다고 하자.

 

IF 코너진입 AND 속도빠름 THEN 브레이크

IF 코너진입 AND 속도느림 THEN 가속

IF 코너탈출 AND 속도빠름 THEN 가속

IF 코너탈출 AND 속도느림 THEN 가속

 

 

각 인풋의 소속도는 다음과 같다.

 

 

코너진입 = 0.1

코너탈출 = 0.9

속도빠름 = 0.4

속도 느림=0.6

 

 

아웃풋은

 

브레이크 = min(0.1,0.4) = 0.1

가속 = min(0.9, 0.4) = 0.4

가속 = min(0.1, 0.6) = 0.1

가속 = min(0.9, 0.6) = 0.6

 

 

따라서 최종적으로 output state는 브레이크가 0.1, 가속이 0.6이 된다.

 

이런 식으로 아웃풋 상태들의 소속도를 구했다면 이것을  역퍼지화하여 무엇을 할지 정한다.

 

 

 

---

 

구현

---

public float[] FuzzyDecisionMaker(object[] inputs, MembershipFunction[][] membershipFns, FuzzyRule[] rules)
{

    //인풋과 아웃풋의 소속도를 저장한다.
    var inputDoms = new float[inputs.Length];
    var outputDoms = new float[inputs.Length];

    for (int i = 0; i < inputs.Length; ++i)
    {
        var input = inputs[i];
        var membershipFnList = membershipFns[i];

        //소속 함수로부터 소속도를 얻어온다.
        foreach (var membershipFn in membershipFnList)
            inputDoms[membershipFn.stateId] = membershipFn.GetMembershipValue(input);
    }

    foreach (var rule in rules)
    {
        var best = outputDoms[rule.conclusionStateId];
        float min = 1;

        foreach (var state in rule.inputStateIds)
        {
            //소속도 (Degree Of Membership)
            var dom = inputDoms[state];

            //최적화 코드 : 계산된 소속도는 낮아지기만 하기 때문에 이미 best보다 낮다면 계산이 불필요하다.
            if (dom < best) break;

            if (dom < min) min = dom;
        }

        outputDoms[rule.conclusionStateId] = min;
    }

    return outputDoms;
}

 

구현시 주의사항

위 알고리즘은  쉽게 병렬연산 처리가 가능하다. 그러나 이를 위해서는 최적화 코드를 제거해야 한다.이런 브랜칭은 병렬 알고리즘에 부적합하다.

 

 

퍼포먼스

$n_i $가 각 인풋의 상태 갯수일때 $i$는 인풋개수라고 하자.

 

룰이 저장되어야 하므로 메모리는 룰의 갯수인 $ (n0*n1*…*ni) $ 만큼 필요하다.

 

퍼포먼스는 $i*(n0*n1*…*ni)$ 이다. 룰의 갯수에 조건의 갯수를 곱한 값이다.

 

 

약점

이러한 알고리즘은 scalability가 매우 떨어진다. 매우 적은 갯수의 인풋 갯수에서만 잘 동작한다.

 

예를 들어 인풋이 10개고 각각 5개 스테이트가 있다? 그렇다면 $5^{10}$개의 룰이 존재하게 된다. 이러한 약점을 보완하기 위하여 아래의 Comb Method를 쓴다.

 

 

 

 

---

 

Comb Method

---

Comb Method에서는 Logical Entailment라는 논리 연산자를 사용한다. 대충 한국어로는 수반한다는 뜻인 듯.

 

어떻게 쓰냐면 

 

$A\ ⊨\ B$ 혹은 $A\ Entails\ B$

 

이렇게 쓴다.

 

IF A THEN B

이렇게도 쓴다.

 

뜻은 A가 B를 수반한다는 것인데, "A가 참일 때 B가 거짓이라는 것은 있을 수 없는 일이다." 라는 뜻이다.

 

좀 더 명확하게 하자면 "A가 참인 세계의 집합은 B가 참인 세계의 집합의 부분집합이다." 라고 할 수 있다. 이 논리 연산자는 다음과 같은 연산 결과를 지닌다

 

A	B	A=>B
True	True	True
True	False	False
False	True	True
False	False	True

(책에서는 False/False가 False라고 나와있는데 오타인듯...)

 

아무튼 A가 True일 때는 직관적으로 이해가 된다.

 

 

IF "내가 바다에 빠졌으면" THEN "나는 젖었다" 

라는 문장은 유효하다. (참)

 

IF "내가 바다에 빠졌으면" THEN "나는 젖지 않았다"

 

 라는 문장은 당연히 유효하지 않다.(거짓)

 

근데 A가 False때는 직관적으로 이해가 안되는데, 다음의 문장을 보자.

 

IF "1+1 = 3 이면" THEN "나는 대통령이다."

 

위 문장은 실제로 내가 대통령이든 아니든 유효하다.(참) 전제가 틀렸기 때문이다. 

 

 

 

$(a\ and\ b)\ ⊨\ c$

 

는 다음과 같이 쓸 수 있다.

 

$(a ⊨ c)\ or\ (b ⊨ c)$

 

 

a	b	c	a&b => c	a => c	b => c	a=>c or b=>c
t	t	t	T	T	T	T
t	t	f	F	F	F	F
t	f	t	T	T	T	T
t	f	f	T	F	T	T
f	t	t	T	T	T	T
f	t	f	T	T	F	T
f	f	t	T	T	T	T
f	f	f	T	T	T	T

 

 

아무튼 이걸 왜 얘기하냐면...

 

퍼지 규칙도 형식이 Entailment랑 동일하기 때문이다.

 

IF input_A & input_B THEN output_A

 

 

따라서 위와 같은 퍼지 규칙은 다음과 같이 쓸 수 있다.

 

(IF input_A THEN output_A) OR (IF input_B THEN output_B)

 

 

이건 다시 다음과 같이 쓸 수 있다.

 

IF input_A THEN output_A

IF input_B THEN output_B

 

예를 들어,

 

IF 코너진입 AND 속도빠름 THEN 브레이크

IF 코너탈출 AND 속도빠름 THEN 가속

 

위와 같은 규칙이 있다고 한다면 아래와 같이 쓸 수 있다.

 

IF 코너진입 THEN 브레이크

IF 속도빠름 THEN 브레이크

IF 코너탈출 THEN 가속

IF 속도빠름 THEN 가속

 

그런데 이 경우 속도가 빠를 때 브레이크를 밟아야 하는건지 가속을 해야하는 건지 알 수 없다.

 

이런 문제는 어쩔수가 없다.

 

그래서 그냥 애초에 규칙을 단순하게 (혹은 Comb format으로 변환 가능하게) 짜는 수 밖에 없다. 이렇게 되면 당연히 규칙을 만드는데 한계가 존재하지만 규칙을 생성하는게 쉬워지기 때문에 규칙을 잘 비틀어서 만들 수 있다. 

 

 

아무튼 원래 포맷에서는

 

IF 코너진입 AND 속도빠름 THEN 브레이크

IF 코너진입 AND 속도느림 THEN 가속

IF 코너탈출 AND 속도빠름 THEN 가속

IF 코너탈출 AND 속도느림 THEN 가속

 

 

여기서 각 소속도가 다음과 같다면

 

코너진입 = 0.1

코너탈출 = 0.9

속도빠름 = 0.4

속도 느림=0.6

 

 

 

다음과 같은 계산을 통해

 

브레이크 = min(0.1,0.4) = 0.1

가속 = min(0.9, 0.4) = 0.4

가속 = min(0.1, 0.6) = 0.1

가속 = min(0.9, 0.6) = 0.6

 

 

 

최종 결과값이

 

브레이크 = 0.1

가속 = 0.6

 

이었다.

 

 

 

 

위의 규칙을 Comb Format으로 다시 다음과 같이 재정의 할 수 있다.

 

IF 코너진입 THEN 브레이크

IF 코너탈출 THEN 가속

IF 속도빠름 THEN 브레이크

IF 속도느림 THEN 가속

 

이 경우 다음과 같은 결과가 나온다.

 

브레이크 = 0.4

가속 = 0.9

 

어쨋든 동일한 인풋에 대하여 수치는 다르지만 그럴듯한 값이 나옴을 볼 수 있다. 

 

 

 

 

이런 Comb methods는 퍼지 로직을 짤때 굉장히 실용적이다. 클래식한 로직에서 사용된다면 노답이지만 퍼지 로직에서는 그럴듯하게 작동한다.

 

 

---

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