퍼지 상태 머신 (Fuzzy State Machine)

개요

---

퍼지 상태 머신의 종류는 여러 가지가 있을 수 있다. 전통적인 상태 머신에 퍼지 요소를 조금 섞으면 퍼지 상태 머신이라고 부르기도 한다. 상태끼리의 Transition이 퍼지 로직을 사용할 수도 있고, 아니면 상태 자체가 퍼지 상태일 수 있으며 둘 다일 수도 있다. 

 

 

---

 

 

알고리즘

---

퍼지 상태에 전통적인 전이(Transition)를 사용하는 퍼지 상태 머신을 구현한다고 하자.

 

전통적인 상태 머신에서는 현재 상태만을 저장하는 것과 달리 모든 상태의 소속도를 저장한다. 어떤 상태가 활성화 됐는지 알아보려면 그냥 모든 상태의 소속도를 보면 된다. 그러나 실사용에서는 몇몇의 상태만이 한 번에 활성화 되어 있는 경우가 많으므로 활성화된 상태를 저장하는 리스트를 따로 마련하는 것이 좋다.

 

아무튼 이렇게 활성화된 상태들은 동시에 전이할 수 있다. 그러나 병렬 연산의 한계가 있으므로 이런 전이들은 보통 순차적으로 진행하게 된다. 따라서 이런 전이의 결과물을 모두 캐싱해둔 다음에 그것들을 종합해서 사용하면 된다. 간단한 방법 중 하나는 소속도가 높은 상태부터 전이를 발생시키는 것이다. 

 

전이가 발생하면, 한 상태는 동시에 여러 개의 새로운 상태로 전이할 수 있다. 그리고 전이 그 자체도 전이도(degree of transition)를 가지게 된다. 새로운 상태의 소속도는 기존 상태의 소속도와 전이의 소속도를 AND연산 한 결과가 된다.

 

예를 들어, 소속도가 0.4인 A상태가 있다. 그리고 새로운 상태B에 도달하는 전이도가 0.6인 전이 T가 있다. 새로운 상태 B의 소속도가 현재 0이라고 가정한다면 새로운 상태B의 전이도는 다음과 같다.

 

$$M_B=M_{(A\ AND\ T)} = min(0.4,0.6) = 0.4$$

 

$M_x$상태 x의 전이도이다.

 

만약 상태B의 소속도가 0이 아니었다면 기존 값과 새로운 값을 OR연산한다. B의 소속도가 0.3이었다면 새로운 B의 소속도는 다음과 같다. 

 

$$M'_B=M_{(B\ OR\ (A\ AND\ T))} = min(0.3,0.4) = 0.4$$

 

동시에 기존 상태A의 소속도는 기존 소속도와 NOT T를 AND연산 하여 계산한다. 

 

$$M'_A=M_{(A\ AND\ NOT\ T)} = min(0.4,1-0.6) = 0.4$$

 

 

한 상태가 두개 이상의 상태로 전이할 때 기존 상태의 소속도는 더 낮은 값을 선택하도록 할 수 있다. 예를 들어 소속도가 0.5인 어떤 상태A가 각각 0.2, 0.7의 전이도로 상태B, C로 전이한다고 하자.

 

그러면 A의 소속도는 다음과 같다.

 

$$M'_A= min(0.5,1-max(0.2,0.7)) = 0.3$$

 

 

전통적인 상태 머신과 다르게 퍼지 상태 머신은 상태가 직접 무엇을 할지를 정하지 않는다. 무엇을 할지를 상태머신과 분리한 뒤에 각 상태들의 소속도를 역퍼지화 하여 어떤 행동을 할지 결정한다.

 

 

---

 

 

구현

---

public class FuzzyStateMachine
{
    //DOM(degree of membership) = 소속도
    public struct StateAndDOM
    {
        public int state;
        public float dom;
    }

    //현재 활성화된 상태를 넣어준다.
    private StateAndDOM[] _curActiveStates;

    void Update()
    {
        //내림차순으로 현재 상태를 정렬한 copy를 얻어옴
        var statesInOrder = _curActiveStates.GetCopySortByDecreasingDOM();

        foreach (var state in statesInOrder)
        {
            for(var transition in state.GetTransitions())
            {
                if (transition.IsTriggered())
                {
                    //dot = degree of transition, 전이도
                    var dot = transition.GetDot();

                    foreach (var endState in transition.GetTargetStates())
                    {
                        //소속도를 업데이트한다.
                        StateAndDOM end = _curActiveStates.GetStateAndDOM(endState);
                        end.dom = max(end.dom, min(state.dom, dot));

                        //새로 활성화된 상태라면 추가해준다.
                        if (end.dom > 0 && false == _curActiveStates.Contains(end))
                            _curActiveStates.Add(end);
                    }

                    state.dom = min(state.dom, 1 - dot);

                    //기존 상태가 비활성화되었다면 제거해준다.
                    if (state.dom <= 0.0f)
                        _curActiveStates.Remove(state);

                    //이 상태에 대해서 더 이상 전이를 확인하지 않는다.
                    break;
                }
            }
        }
    }
}

transition들이 trigger되었는지를 구하기 위해 IsTriggered 메서드에서는 내부적으로 퍼지 로직을 사용할 수 있다. 예를 들어 어떤 전이가 0.5정도로 조건을 만족했다면 메서드는 true를 리턴하고 dot값은 0.5가 될 것이다.

 

---

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