자연어처리

가상으로 구성된 로봇이든 게임 내 NPC 이든 사람들이 살고 있는 세계에서 의미가 있으려면 자연어 처리 기능은 매우 중요하다. 자연어 처리란, 컴퓨터를 통해 자연어 언어를 이해하고 활용할 수 있도록 하는 방법을 말한다. 가령 게임 내에서 자연어를 이해할 수 있다면, 사용자와의 상호 작용이 좀 더 자연스럽게 구성가능하다. 따라서 미리 구성된 문장이 아닌 사용자가 질문한 즉시적인 문장에 대해서도 지능적으로 대응할 수 있게 된다.

현재 기술로 자연어 처리가 물론 완벽하게 구성되지는 않지만, 제한적으로 게임이나 로봇에서도 활용될 수 있는 있다. 이번 글에서는 자연어 처리에 대한 기본적인 이해를 목적으로 정리해 보고자 한다.

용어 이해

  • 품사 : 품사라고 하면 낱말을 문법적인 기능이나 형태, 뜻에 따라 몇 갈래로 나눈 것을 말한다. (위키 백과 발췌) 한국어의 품사는 일반적으로 명사, 대명사, 수사, 동사, 형용사, 관형사, 부사, 감탄사, 조사의 9품사로 구성됨
  • 자모 : 문자 체계의 한 요소로 낱자를 가리킴. 한글의 경우에는 ㅏ, ㄱ, ㅎ, ㅗ 등을 일컫는다.
  • 용언 : 문장에서 주어를 꾸미는 낱말들인 동사, 형용사를 일컫는 문법 용어
  • 어간(語幹, stem) : 용언(동사, 형용사)이 활용할 때, 원칙적으로 모양이 변하지 않는 부분. 활용에서 어미에 선행하는 부분. 때론 어간의 모양도 바뀔 수 있음(예: 긋다, 긋고, 그어서, 그어라).
  • 어미: 용언의 어간 뒤에 붙어서 활용하면서 변하는 부분이며, 여러 문법적 기능을 수행

자연어 처리의 형식적 모델 이해

자연어 처리에 대한 필요성은 분명하기에 예부터 그러한 노력들은 언어에 대한 이해로 시작될 수 있다. 가장 기본적인 이해는 통계학적인 이해이다. 가령 자연어에 사용되는 각 문자들이 어떠한 빈도로 나타나느냐 혹은 인접한 두 문자 이상의 빈도들은 어떻게 되는지를 살펴보는 것이다. 이를 n-gram (단독 문자의 출현빈도만이 아니라 2문자, 3문자가 연접해서 생기는 문자의 관계)이라 한다. 참고로 영어의 경우는 공백을 제외하면 ‘e’ 라는 문자가 9.36% 출현빈도로 나타난다고 한다. (Penn Treebank 통계 발췌) 그리고 한글의 자모 중, 초성의 경우 ‘ㅇㄱㄷㅅㅈㅎㄹㄴㅁㅂㅊ’ 순으로 빈도를 띈다. (한글어 형태소 분석과 정보검색 발췌) 다음은 유한 오토마톤 모델에 대한 이해이다. 통계학적인 이해에 상태 기반 프로세스 개념을 추가해 이해를 하고자 하는 방식이다.

I love you

라는 문장을 가령 통계학적인 이해만을 근거로 you love I 라고 표현하면 안될 것이다.  S(주어), V(동사), O(목적어)라는 기본적인 영어식 문법을 따르지 않았기 때문이다. 이처럼 인접하는 단어끼리는 어떤 문법적 제약이 상주하는 것이다. 비록 모든 언어에 대해 적용되지는 않지만, 그래도 이런 개념을 이용하지 않을 수 없지 않는가? 바로 인접하는 단어끼리의 문법적 제약을 수학적으로 모델링한 것이 유한 오토마톤 모델(Finite Automaton Model)이다.

자연어 처리 과정 이해

자연어 처리를 하기 위해서는 일반적으로 수행되는 단계가 있다. 형태소 분석, 구문분석, 그리고 의미분석이라는 단계이다. 하지만 반드시 거쳐야 되는 과정은 아니면 때로는 형태소 분석만으로 목적하는 자연어 처리가 완료될 수가 있다.

1. 형태소 분석 (Morphological Analysis)

형태소라는 것은 자연어 언어 중 최소의 언어 단위를 말한다. 문장 중 어떤 의미가 있고 형태가 있는 최소 단위이다. 형태소 분석이란 주어진 문을 형태소로 분해하고, 각각의 형태소에 품사 등을 결정(품사 태킹)하는 것이다. 다시 말해 문장을 사전에 등록되어 있는 최소의 단위로 분해한다는 말이다.

형태소 외에 자연 언어가 가지는 계층적 구조를 살펴보면 아래와 같다.

  • 음소(phoneme) : 인간의 의미(의지) 전달에서 음성을 어떻게 사용하는가를 기초로 생각한 음의 단위
  • 형태소(morpheme): 의미를 가진 최소의 언어 단위, 하나 이상의 음소로 된다.
  • 단어(word) : 하나의 의미의 총합을 이루며, 문법상 하나의 기능을 가진 최소의 언어 단위, 하나 이상의 형태소로 구성된다.
  • 문장(sentence) : 전달하고자 하는 내용을 가지며, 완결된 언어 단위, 하나 이상의 단어로 된다.

형태소란 의미를 가진 최소의 언어 단위를 일컫지만, 언어마다의 고유 특성으로 인해 애매한 부분이 있다. 영어의 경우, 형태소는 단어가 어근(radical)과 접사(affix)로 분류되기 때문에, playing는 play(어근) + ing(접사)로 2형태소로 구성되었다고 말할 수 있고, 일본어나 한국어는 활용어의 발달로 형태소의 기준이 애매하지만, 보통 사전에 등록되어 있는 항목으로 보면 가장 근접한 기준이라 할 수 있다.

아래 “나는 너를 사랑한다.” 에 대한 고려대학교 자연어처리에서 분류한 형태소 해석의 예를 보자.

나는 나/VV+아는/EFC, 나/VX+아는/EFC, 낳/VV+아는/EFC, 나/NNCG+는/PX, 나/NPP+는/PX, 나/VV+는/EFD, 나/VX+는/EFD, 날/VV+는/EFD
너를 너/NPP+를/PO, 너르/VJ+ㄹ/EFD
사랑한다. 사랑/NNCV+하/XSVV+ㄴ다/EFF+./SS.

위와 같이 간단한 문장이라도 사전에 등록되어 있는 항목으로 형태소 해석을 하면 경우의 수가 상당히 많다. 이것이 바로 자연어처리의 어려움 중의 하나라고 할 수 있다.

2. 구문 분석

위 형태소 분석으로는 모든 가능한 형태소의 조합을 찾아된다. 이러한 결과를 이용하여 문장에 맞는 태깅을 찾아내기 위해서 구문 분석이라는 단계를 더 활용하기도 한다. 때로는 형태소 분석에서 자연어 처리가 끝나기도 한다. 구문 분석이란, 문법 규칙 및 여러 종류의 규칙에 의해 입력 문장을 해석하고 그 구조를 명백히 하는 것이다. 

예를 들면 “I saw a girl”이란 문장의 구문 분석은 다음과 같다.

nlp_syntactic

그림. 구문 해석의 결과 : I saw a girl.

결국, 구문 분석이라 함은 하나의 탐색(search) 과정이라 할 수 있다. 구문 분석은 Top-down 방식과 Bottom-up 방식으로 가능한데 Top-down 방식을 살펴보면 아래와 같다.

  • Top-Down 알고리즘

Top-Down 알고리즘은 개시기호(S)부터 시작하여 차례로 규칙을 적용해서 전체 문장이 얻어질 때까지 반복하는 방법이다. 가령 문장을 구성하는 문법이 아래와 같이 주어진다고 가정하자. (문맥자유문법, CFG)

[1] S   → NP VP [4] VP → V [7] PP → PREP NP
[2] NP → N [5] VP → V NP
[3] NP → DET N [6] VP → V NP PP

우선 처음에 개시기호 S(전체 문장)를 위의 표에서 규칙 [1]으로 바꿔보자

S ⇒ NP VP

이 시점에서 두 가지 선택이 있다.

(1) 다음에 NP를 바꿀 것인가, VP를 바꿀 것인가?
(2) NP를 바꾼다면 어떤 규칙과 바꿀 것인가?(규칙 [2], [3]) VP의 경우도 그렇다.(규칙 [4], [5], [6])

(1)의 문제는 왼쪽의 기호부터 바꿔 써 간다고 하는 방법( 최좌 도출, Mostleft derivation )을 이용하면 되고, (2)의 문제는 단순히 위의 규칙에 따라 적용해 가는 것으로 한다.

S ⇒ NP VP (∵ 규칙 [1])
⇒ N  VP (∵ 규칙 [2])
⇒ I  VP (∵ 입력 문장의 첫 단어 I의 품사 N과 동일)
⇒ I  V  (∵ 규칙 [4])
⇒ I  saw(∵ 입력 문장의 두 번째 단어 saw의 품사 V과 동일)

입력문과 비교하면 입력문의 후반이 남아 있음에도 불구하고 바뀔 기호열이 더 이상 존재하지 않는다! 실패를 한 것이다. 이와 같은 경우에는, 마치 트리(tree) 탐색와 같이 해를 못 찾을 때, 거슬러 올라가 찾는 것처럼, 다른 규칙의 적용이 가능한 시점까지 되돌아가 다시 바꿔쓰기 규칙을 적용한다. 이와 같은 과정을 백트랙(backtrack)이라 한다.

⇒ I saw
⇒ I V NP
⇒ I V N (∵ 규칙 [2])
⇒ …
⇒ I saw a girl(탐색 완료 시점)

규칙을 적용하여 입력 문장을 찾으면, 경로를 따라가면 쉽게 위와 같은 구조를 알아낼 수가 있는 것이고, 그것으로써 구문 해석은 완료된 것이다.

3. 의미 해석(Semantic Analysis)

컴퓨터가 의미를 해석한다는 의미는 무엇일까? 의미를 해석한다는 의미는 가령 문장 중의 단어 중 ‘다리’라는 단어가 등장할 때 다리가 bridge를 의미하는지 leg를 의미하는지 파악하는 것이다. 여기서 bridge라는 것은 영어라기보다 단어를 의미하는 하나의 심볼(symbol)로 생각하면 된다.

의미해석이 무엇인가를 생각하게 하는 실마리로 필모어(C. Fillmore)의 격문법을 들 수 있다. 격문법(case grammar)은 어와 어 사이의 의미관계를 동사 중심으로 다룬 것이다. 이때 격이란 주격 목적격 등의 통사적 격이 아니라 동사의 의미적 수행에 필요한 ‘의미역’과 같은 개념이다. 즉, 심층격(deep case)이라는 것에 근거하여 문장의 의미를 표현한 것이다.

동작주격(A) 어떤 동작을 일으키는 사람의 역할
경험자격(E) 어떤 심리사상을 체험하는 사람의 역할
도구격(I) 어떤 사건의 직접적인 원인이 되기도 하고, 어떤 심리사상과 관계하여 반응을 일으키게 하는 자극이 되는 역할
대상격(O) 이동하는 대상물이나 변화하는 대상물, 혹은 판단, 상상과 같은 심리사상의 내용을 나타내는 역할
원천격(S) 대상물의 이동에 있어서의 기점 및 상태 변화와 형상 변화에 있어서의 최초의 상태나 형상을 나타내는 역할
목표격(G) 대상물의 이동에 있어서의 종점 및 상태 변화와 형상 변화에 있어서의 최종적인 상태, 결과를 나타내는 역할
장소격(L) 어떤 사건이 일어나는 장소 및 위치를 나타내는 역할
시간격(T) 어떤 사건이 일어나는 시간을 나타내는 역할

표. 필모어의 심층격(C. J. Fillmore : 격문법의 원리 삼성담)

예를 들어, 동사 break에 대한 심층격 표현은

break-O(I)(A)

라고 표현된다.
여기서 여기서 O는 대상물의 역할을 하는 대상격으로 동사 break의 의무적 요소역할을 하며, (A), (I)는 각각 동작주격, 도구격으로 임의의 요소 역할임을 나타낸다. 의무적 요소를 필수격(obligatory case), 임의적 요소를 임의격(optional case)라 부른다. 이와 같이, 동사에 대한 심층격으로의 표현을 격프레임이라 한다.

한국어 문장의 경우는, 아래 문장을 살펴보자.

나는 오늘 컴퓨터 책을 샀다.

‘나는’ ‘오늘’ ‘책을’ 이 모두 ‘샀다’ 에 걸리고, ‘컴퓨터’ 가 ‘책을’ 에 걸린다.한국어가 영문과 다른 또 한 가지는 어순이 비교적 자유롭다는 것이다. 예를 들어, 앞의 문장은 다음과 같이 바꿔써도 뜻이 완전히 같다.

오늘 컴퓨터 책을 나는 샀다.

이러한 특징을 가진 한국어의 의미해석에는, 동사를 중심으로 하는 격문법이 가장 바람직하다. 영문의 격을 결정하는 데에는 어순이 큰 영향을 미치지만, 한국어 문장의 격은 조사가 결정적인 역할을 한다 . (AIStudy.com 발췌, 최기선 1992)

참고로 격문법 외에 의미 분석을 하는 방법으로는 의미망, 몬테규문법, 개념의존 등의 방법들이 더 있다. 

참고 문헌

Flocking

Flocking은 게임에서 새떼나 물고기 무리들의 움직임을 프로그램으로 시뮬레이션하기 위한 주제이다. 이는 1987년 SIGGRAPH에 제출된 논문에서 처음 등장한 기법으로, 레이놀즈(Craig Reynolds)는 이러한 움직임을 발생시키는 요인을 아래와 같이 제시하였다.

  • 응집력 (cohesion) :무리를 한데 모이게 하는 힘. 개개인의 움직임은 자유롭지만 무리를 벗어나지 않으려는 욕구로 인하여 발생함
  • 정렬 (alignment) : 무리의 평균 움직임 방향과 일치시키려는 욕구
  • 거리 유지(separation) : 무리와 충돌하지 않으려는 욕구

위 3가지 외 외부 객체와 충돌 (Object avoidance)하지 않으려는 욕구가 더 있을 수 있다. 이러한 기본적인 기법도 중요하지만, 무리의 자연스러운 움직임을 만들어내는 데 있어서는 “배회(wander)하는 움직임 자체”를 만들어 내는 방법도 역시 중요하다. 무작위로 움직이는 듯 하지만 배회하는 나름대로의 규칙도 정교해야지만 새 떼나 물고기 떼의 움직임을 흉내낼 수 있게 된다. 

Image

위 과정에서 생겨나는 행동들이 미리 규정된 것이 아니라는 점에서 창발적인 행동들이라 할 수 있다. 전체는 부분들의 복잡한 상호작용의 결과이며 이 결과가 역으로 부분들에 작용하면서 애니메이션의 선형적 행동과는 다른 비선형적인 복잡한 행동을 만들어낸다. 이것이 바로 “상향식(bottom-up) 구조”이며 새들의 미묘한 움직임은 여기서 나오는 것이다. 

 

위치, 속도, 가속도 그리고 힘

개체의 자율적 행위를 구성하기 위해서는 물리적인 이해가 필요하다.  가장 간단하면서도 익히 들어온 위치, 속도, 가속도 그리고 힘에 대한 내용을 2D 화면에서 어떻게 표현되는지 정리해보고자 한다. 3D에서도 비슷하게 확장 가능하리라 본다. 

phy_pos_n_force

먼저 2D 화면에서의 위치 개념은 쉽다. 좌표가 즉 위치이다.  위 그림에서 가령 A의 x, y 좌표값 (100, 250)이 바로 위치이다.  B의 위치는 (400, 200)이다. 그렇다면 A에서 B까지의 속도는 얼마일까? 위치가 바뀐것이라 볼 수 있으니 방향과 크기가 주어진 벡터로 표현가능하며 B에서 A 위치값을 뺀 값이 속도가 된다.

속도 AB = 위치B – 위치 A = (300, -50)

이 때 만약 A위치에 있던 개체가 C 위치로 이동하고 있었다고 가정해보자. 즉 A가 AC의 속도로 이동하고 있다고 가정해보자는 것이다.

그렇다면 CB는 무엇이 될까? 속도와 속도와 변화량이기에 가속도가 된다. 주어진 가속도에  A의 개체가 질량까지 고려된다면 CB는 B 위치로 가기 위한 힘으로 표현이 된다.

F = ma 

힘은 가속도와 질량의 곱으로 표현이 가능하기에, 가속도(a)를 질량(m)으로 나누면 요구되는 힘(F)이 된다.

예를 하나 들어보자.  위 그림처럼 포인트 A에 행위 조절이 되어야 하는 자율 (automous)적 개체가 있다고 가정하자. 게임에서 NPC라 생각하면 된다. 그 개체가 어떤 이유에서든 B 위치로 가고자 한다. 그런데 A는 이미 C 방향 일정 속도로 이동 중이었다고 한다면, B위치로 가고자 한다면, CB 방향으로 가속도 내지는 힘이 필요한 것으로 설명되는 것이다. 질량이 1kg이면 가속도 수치값이 곧 힘값이 된다. 물론 단위는 다르다.

셀(cell)

셀(cell)은 3D 메쉬(mesh)를 구성하는 기본 단위이다. 네비게이션을 위한 메쉬는 특히 3각형으로 구성된 셀로 구성된다.

게임에서 자율적 행위 개체를 구성하기 위해서는 지형적인 정보까지도 파악하고 있어야 하는데 가장 근본적인 처리 중 하나가 특정 포인트가 셀 안에 있는지를 확인하는 과정이다. 셀은 삼각형으로 구성되기에 3개의 좌표가 주어진다. 특정 포인트가 셀 안에 있는지를 파악하기 위한 코드는 아래와 같다. (Copyright (C) Greg Snook, 2000. 발췌)

int InteriorCount = 0;
for (int i=0;i<3;i++)
{
    Line2D::POINT_CLASSIFICATION SideResult = m_Side[i].ClassifyPoint(TestPoint);
   if (SideResult != Line2D::LEFT_SIDE)
   {
      InteriorCount++;
   }
}

return (InteriorCount == 3);

알고리즘을 설명하면 셀을 구성하는 각 라인에 대하여 포인트가 왼편에 있는지 또는 오른편에 있는지를 확인하고 나서, 모든 라인에 대하여 오른편에 있다고 한다면 포인트는 셀 안에 위치한 것이다.

위 알고리즘 사용 예

  • 자율적 행위 개체가 어느 셀에 위치한지를 파악할 때 사용 가능함. 
  • 특정 포인트가 어느 셀과 가장 가까운지를 파악하고자 할 때 사용 가능함

행위 기반 로보틱스

I. 개요

로봇을 지능적으로 만들려는 방법은 아마도 누군가는 지금도 고민하고 있을 것이다. 환경을 인식하고 목표로 주어진 태스크(task) 임무를 처리하는 데 있어 로봇의 처리 능력은 앞으로 더더욱 중요한 요소이기 때문이다. 행위 기반의 제어 방법도 역시 로봇을 더 바람직하게 만들기 위한 방법론 중 하나이며, 대표적으로 청소 로봇인 룸바(roomba)에 적용되어 많은 이슈가 되었다. 지금부터 behavior-based robotics에 대한 내용을 정리해보고자 한다.

기존의 방식(non behavior-based?)

로봇의 제어 방법론 중 보편적으로 생각할 수 있는 것은 에이전트(agent)의 제어 방식과 유사하다. 외부 환경에 대하여 인식(sensing)하고 생각(think)하고 그리고 행동하는 것이다. 보통 생각하는 과정이 생략되면 반응적(reactive)라고 하며, 생각하는 과정이 포함되면 사고적인(d*?)이라고 하기도 한다. 생각하는 과정에 있어서는 규칙 기반의 엔진이나 스크립트 또는 신경망 등 여러 가지 알고리즘을 사용하곤 했다.

위와 같은 방식에 있어서 엔지니어들은 문제가 있다는 것을 알기 시작했다. 생각하는 방식에 있어 외부 환경에 대하여 기술하고 규칙화하고 플래닝(planning) 하기가 너무나 어렵다는 것이다. 특히 모바일 로봇에 있어서는 주위 환경이 동적 환경(dynamic environment)이기에 지능적인 처리를 하기가 너무나도 어렵다는 것이다.

II. 행위 기반의 로보틱스(behavior-based robotics)

행위(behavior)란 무엇인가?

행위 기반의 로보틱스인데 행위를 먼저 알아보자. 행위란 무엇일까? 액션(action)보다는 조금 더 큰 개념으로 보기도 한다. 특정 목적을 기반으로 진행되는 액션들의 묶음이라고 생각한다. 행위에 있어 정확한 경계선(boundary)은 없다. 다만 프로그래밍 언어에도 모듈(module)이라는 개념이 있듯이 어쩌면 편의에 따라, 또는 사용 목적에 따라 구분되어 진 것이라 생각한다. 프로그램 언어에서의 모듈이 바로 로봇에서는 행위라 생각하면 얼추 맞다.

1. 행위의 유형(type) – Servo and ballistic behaviors 단순한 구성을 원칙적으로 유지하려는(primitive) 행위 그 자체에 대한 이해를 돕기 위해 행위를 유형에 따라 분류해 보자. 구성 방식의 특성에 따라 2가지 정도로 나뉠 수 있다. 첫째가 서보(servo) 기반의 행위이며, 둘째가 시나리오 기반(ballistic) 기반의 행위가 있다.

  • 서보 기반의 행위 : 피드백 기구(closed loop) 기반의 센서와 장치 출력 및 피드백의 연속적 제어 방식으로 구성 가능한 행위를 말한다. 가령 Wandering 이나 빛의 강도에 따라 전진과 후진이 제어되는 행위임
  • 시나리오 기반 행위 : 행위에 대한 제어 방식이 외부 이벤트에 따른 시나리오 혹은 FSM 와 같은 제어 방식이 포함되어 있는 행위임

행위의 유형을 위와 같이 설명을 길게? 작성한 이유가 있는데 행위 기반의 로보틱스에서 바람직한 행위 제어 방식은 서보 기반의 행위이며 시나리오 기반의 행위는 가급적 사용을 지양해야 한다. 시나리오 기반의 행위들을 몇 개의 서보 기반 행위들로 세분화될 수 있는지 고민을 해야 한다는 의미이기도 하다. 그러한 이유는 시나리오는 다이나믹한 외부 환경에 대해서 서보 기반의 행위보다는 적응력이 약하기 때문이다.

2. 행위의 기본 구성 행위에는 트리거(Trigger)와 제어를 위한 컨트롤(Control)이 포함되어 있다. 트리거는 행위가 동작되는 조건과 같다.

행위 기반에서의 방식에서 행위 내 트리거가 포함되어 있다는 사실을 유심히 살펴볼 필요가 있다. 보통 기존 방식에서는 행위를 중앙 집중적인 외부 모듈에서 행위에 대한 시작과 중지를 한다.

행위 기반(behavior-based)라는 의미는 무엇일까?

기존의 방식은 로봇이 제어되기까지 인식, 판단, 액션이라는 전체 흐름을 형성하면서 진행되는 데 반해 행위 기반은 (인식, 액션)이라는 모듈을 N개 구성하고 조율하는 식으로 제어를 진행한다고 생각하면 된다. (이후 그림 추가) 판단이라는 과정에서 발생할 수 있는 오묘한 복잡성을 어쩌면 역발상적인 접근으로 기본적으로 행위는 간단하게 하되, 다만 행위간 조합으로 그 오묘함을 실현하고자 하는 것이다.

Arbiter

행위 기반(behavior-based)에서는 Arbiter라는 기능이 필요하다. 우리말 사전에 의하면 조정자라는 뜻이다. 행위가 한 개가 아닌 여러 개 구성될 수 있으며, 따라서 동시간에 같은 리소스 (가령 바퀴 등)을 사용하는 경우가 불가피하게 생긴다 이럴 경우 행위 중 하나를 선택해야 한다. 이 과정(선택)에서 필요한 기능이 Arbiter이다. arbiter는 보통 행위간 우선 순위(priority)를 할당하고 조정이 필요할 시 우선 순위가 높은 행위를 선택하도록 한다.

Subsumption architecture

행위 기반의 로보틱스를 언급할 때 빠질 수 없는 분야가 바로 Subsumption architecture라는 방법론이다. Subsumption은 포섭이라는 의미인데 아마도 행위간 계층 구조로부터 생긴 단어인 듯 한다. Subsumption architecture는 1896년에 인공지능 분야에 있어 대가라고 할 수 있는 Rodney Brooks에 의해 제안되어 더욱 유명해 졌다. Subsumption architecture이 바로 결국 지금까지 언급된 행위 기반의 로보틱스의 분류 중 가장 정립된 방법론 중 하나이다. 그렇다면 Subsumption architecture의 장점을 살펴 보자 (wiki 참조) – 장점 (advantages)

  • 모듈식으로 구성
  • 계층적으로 구성되어 iterative development가 가능함

아래 그림은 Subsumption architecture을 사용한 예이다. 그림에서 보면 여러 개의 행위를 계층적으로 구성하고 계층간 행위가 서클 모양으로 조정되는 것을 확인할 수 있다.

Subsumption architecture에는 두 가지 유형의 Arbiter가 있다.

  • S (suppressor) : 우선 순위가 높은 상위 행위가 하위 행위를 억압(suppress) 할 수 있지만 상위 행위가 종료되면 다시 하위 행위가 동작하는 식의 조정
  • I (inhibitor) : 우선 순위가 높은 상위 행위가 하위 행위를 억제(inhibit)하면 상위 행위가 종료되더라도 하위 행위가 동작하지 못하는 식의 조정

참고

그래프

자율적 행위를 구성하기 위해서는 공간에 대한 인식이 필요하다. 특히 게임 같은 경우 2D/3D 공간을  네비게이션(navigation)할 필요가 종종 발생한다. 이와 같은 경우 공간 바닥에서 활용되는 데이터 구조가 그래프(graph)이다.

그래프 구성

그래프는 노드(node)와 에지(edge)로 구성된다. 노드와 노드의 연결이 에지인 셈이다. 노드에는 적어도 1개 이상의 에지와 연결되어야 한다. 그리고 에지가 방향성이 있을 수 있다. 일반적으로 사용되는 그래프 중 하나는 DAG (Directed Acyclic Graph)로 방향성 그래프를 가리킨다.

그래프 활용

그래프가 사용되는 곳은 네비게이션 외에도 의존성을 표기하거나 상태 기계를 표기하기도 한다. 의존성 표기는 무기 체계나 행위 체계를 표현하며 노드들이 무기나 행위등이 되며 노드들을 연결하는 에지는 의존 관계를 표현하는 것이다.

그래프 구현

노드와 에지를 구성하는 그래프를 프로그램으로 구현할 경우는 행렬이나 리스트(list) 데이터 구조를 사용한다. 주어진 노드에 연결되어 있는 모든 노드들을 가지고 있는 식으로 리스트가 구성된다.

그래프 탐색

그래프를 구성하는 노드들을 탐색하여 출발노드에서 목적노드까지의 경로 구성이 필요할 경우 그래프 탐색을 한다. 길찾기에서 그리드 (grid) 방식이 아니면 보통 그래프 탐색을 하는 것이라 볼 수 있다. 그래프 탐색도 깊이 우선 방식과 너비 우선 방식 그리고 A* 등으로 나뉠 수 있다. 깊이 우선 방식은 스택 (stack) 구조를 활용하며 너비 우선 방식은 큐(queue)를 활용한다.

astar

A*  알고리즘은 출발지 노드에서 목적지 노드까지의 최단 거리를 찾아주는 그래프 탐색 알고리즘이다.  일종의 탐색 알고리즘이다. 탐색 알고리즘으로는 깊이우선 탐색이나 너비우선 탐색 등 여러 가지가 있지만 A*의 장점은 휴리스틱(heuristic)정보를 사용한다는 점이다. 쉽게 말해, 깊이 우선 탐색이나 너비우선 탐색은 목적지 노드가 어디에 있는지를 전혀 모르는 상태에서 무작정 탐색 공간들을 찾아 해맨다. 하지만 A* 알고리즘은 다르다.

목적지 노드가 어디쯤 있는지를 휴리스틱 정보를 통해 알고 있다. A*의 휴리스틱 정보는 탐색 노드에 대한 평가 함수 f(n)를 통해 알 수 있으며 다음과 같이 정의된다.

f(n) = g(n) + h(n)

  • g(n) : 출발지 노드로부터 노드 n까지의 경로비용
  • h(n) : 노드 n으로부터 목표 노드까지의 휴리스틱 (heuristic) 정보

보통 h(n)에 대한 정보는 목적지 노드와의 거리값으로 추정된다.

노드 구성

A* 알고리즘을 운영하기 위해서는 노드(node)라는 것을 데이터 구조를 활용한다. 노드는 네모난 그리드(grid) 형태의 격자 모양에서 노드를 취할 수도 있으며 또는 비정형 삼각형인 메시(mesh) 기반에서 노드를 구성할 수도 있다. 노드를 작게 하면 탐색 공간이 넓어져 계산량이 많아질 수 있어 응용 환경에 맞게 최소화하는 것이 바람직하겠다.

길찾기 이슈

  • partitioning (공간분할) : convex polygons, quadtree, uniform, …
  • smoothing : 각진 path를 부드럽게 구성해야 함. 보통 A*를 통해서 구성된 패스는 각이 진 패스 (Catmull-Rom spline can be applied)
  • straight : 접힌 path를 펴도록 이동 (구불구블 이동하지 않도록 함) 보통 LineOfSight를 기준으로 곡선을 핌. straight와 smoothing을 적절히 사용해야 패스의 결과가 좋아짐
  • hierarchical path : path finds from larger scale to smaller scale
  • maximizing responsibility :player가 move 명령을 보내고 나서 즉각적으로 움직이도록 하기 위한 방법

응용 분야

게임뿐 아니라 로봇의 길찾기에서도 활용된다. 로봇에서의 길찾기를 하기 위해서는 SLAM이라는 방법으로 로봇이 위치한 맵(map)을 우선 구성하게 된다. 맵에서 로봇이 다닐 지점을 노드로 구성하고 A* 를 적용한다.

퍼지 제어

퍼지(Fuzzy) 논리는 자연 언어 등의 애매함을 정량적으로 표현하기 위하여 1965년 미국 버클리대학교의 L. A. 자데(Zadeh) 교수에 의해 도입된 퍼지 집합의 사고방식을 기초한다. 퍼지 집합은 일반집합 A에서 위치가 애매한 원소 a가 A의 부분집합 P에 속한다는 말의 애매한 정도를 나타냄으로써 a와 A의 관계를 수학적으로 표현한다. 이를 표현하기 위해 멤버함수(membership function)가 사용된다.

기원

1920년대 30년대 논리학자들이 하이젠베르크의 불확정성 원리를 다루기 위해 다치적 논리를 처음 개발하였다. 그 원리는 기존의 2치 논리를 나타내는 옳음, 틀림 외에 결정할 수 없음을 표현한 것이다. 2개 이상의 명제치를 다루기에 다치논리(multi-valued logic)라 한다.

다치논리학(多値論理學)은 보통의 논리학이 명제(판단)가 참이냐 거짓이냐 하는 어느 하나의 명제치(命題値)를 지니는 ‘2치(二値)논리학’인 데 반해, 이 2치 외에 진위(眞僞)를 결정지을 수 없는 명제가 있다고 주장하는 것이다. 최초의 주장자는 우카시에비치로서 현재에 와서는 이 사고방식이 확률론이나 양자역학(量子力學)에 응용되고 있다.  (Daum 백과사전 발췌)

퍼지 논리의 연산

2치 명제 논리에는 AND, OR 연산이 있고 논리 연산 방식들은 이미 익숙할 것이다. (진리표) 퍼지논리의 경우는 멤버 함수로 표현되기에, 기존의 AND, OR 연산을 활용할 수 없다. 따라서 퍼지 논리에 맞는 AND, OR 연산 방법이 필요하다. 아래는 기존 2치 명제에서의 연산 방식과 퍼지 논리에서의 연산 방식에 대한 비교 예이다.

기존의 논리 연산
  • false AND false = false
  • true OR false = true
퍼지 논리 연산
  • 0.3 AND 0.4 = 0.3
  • 0.6 OR 0.4 = 0.6

퍼지 논리의 연산은 AND는 더 작은 값을 가진 소속도로 연산이 되며, OR는 더 큰값을 가진 소속도로 연산이 된다.

퍼지 제어

퍼지 논리를 활용한 사례는 퍼지 제어를 들 수 있다. 애매한 퍼지 규칙으로 구성된 제어를 의미한다. 가령 예전에 한창 유행했던 세탁기에 응용된 퍼지 제어를 예로 들어보자. 실제 세탁기는 더 복잡하게 퍼지 제어가 되겠지만 여기서는 설명을 위해 간단히 제시하고자 한다.

세탁기 퍼지 제어 예

빨래량이 많으면 좀 더 긴 시간 동안 세탁하라  — (1)

퍼지 제어 활용 예

먼저 빨래량이 많다는 것에 대한 멤버함수를 정해야 한다. 아래 그림처럼 구할 수 있다. 빨래량이 50보다 작을 경우는 많다는 멥버함수에서는 0을 의미하고, 50에서 80까지는 0에서 1.0까지의 애매한 값을 가지도록 설정해보자.  빨래량을 확인할 수 있는 센서 등 전자부품 장치는 있다고 가정한다.

fuzzy_laundry_membership

다음은 긴시간 동안 세탁한다고 하는 규칙의 액션 부분에서 긴 시간이라는 기준을 수치화해야 한다. 가령 3시간이라고 하자. 이제 퍼지 제어를 위한 기본적인 준비는 하였다. 규칙에 대한 조건에 대한 멤버 함수를 설정하고 액션 부분에서의 수치값을 결정하면 된다.

이제 실제로 퍼지 제어로 세탁기를 제어해보자.

어느날 이제 투입된 빨래량이 60으로 감지되었다고 하자. 그러면 위 퍼지 규칙에 의해  계산된 시간동안 세탁이 되는 것이다.

60인 빨래량에 대하여 빨래량이 많은 정도는 위 그림에서 0.3 정도에 해당되는 것을 알 수 있고,  따라서 위 (1)번 규칙에 부합되는 정도도 0.3에 해당된다. 3 * 0.3 = 0.9 (1시간 30분) 정도 동안 세탁하는 것이다. 조건문이 빨래량이 많다는 조건 외 다른 조건이 있다면 AND, OR의 조건문들에 따라서 그리고 추가되는 조건문에 따라서 규칙의 부합 정도가 다르게 나타날 것이다. 본 예에서는 하나의 조건문에 하나의 규칙을 활용하였다.

퍼지 제어의 원리

퍼지 제어에 개념을 설명하면 결국 수치가 측정(빨래량)되면 측정된 빨래량에 대한 조건문 (빨래량이 많음)이 있을 것이고 조건에 대한 멤버함수로 수치에 해당하는 조건의 부합 정도를 애매하게 확인가능할 것이다. 조건의 부합 정도에 따라 AND, OR 연산으로 퍼지 규칙의 부합 정보를 알 수 있을 것이다. 위 예에서는 하나의 퍼지 규칙이지만 실제 예에서는 꽤 많은 퍼지 규칙들이 구성되어 있을 것이다. 그런 퍼지 규칙별로 위 계산 방법과 같이 부합정도를 계산할 수 있으면 가장 많이 부합되는 규칙을 선정하고, 규칙에 해당하는 액션에 규칙이 부합되는 정도를 반영하여 처리하는 방식이 퍼지 제어의 원리이다.

참고

Situation Calculus

Situation Calculus는 동적인 환경(dynamic domains)에서 사용하도록 고안된 논리 형식 (logic formalism)이다. 1차 함수 (First-order logic)은 논리적인 특성으로 동적보다는 정적인 환경에서 사용될 수 있음에 반해 Situation Calculus는 동적인 환경에서 사용가능하다. 일반적인 논리 구성과는 다르게 액션(actions)과 Fluents 그리고 상황(situation) 이라는 개념을 포함한 논리 형식이다. 동적인 환경이라는 것을 예를 들면, 가령 로봇이 어느 곳에서 물건을 집어 또 다른 곳으로 이동한 후 집은 물건을 다시 내려놓은 상황을 의미한다. 이와 같은 환경에서 표현과 추론이 가능한 논리를 구성하기 위해서는 액션들의 조합으로 구성된 시나리오(scenario)가 필요하며 상황 전개에 대한 이해가 필요하다. 이와 같은 환경에서의 논리의 표현(representation)과 추론(reasoning)을 위해 사용될 수 있는 논리 형식이 Situation Calculus 이다. 존 매카시(John McCarthy)에 의해 1963년에 처음으로 소개되었다.

Situation Calculus의 요소

  • 액션(action) : 주어진 환경에서의 액션들을 의미함
  • Fluents : 동적인 환경에서의 여러가지 조건이나 기타 정보들을 의미함.  Fluents 정보들은 시나리오가 흘러감에 따라 계속 변화됨.
  • 상황(situation) : 정적인 상태(state)와는 구별되며, 상태의 이력(history)까지 포함된 복합적인 상황들을 의미함. 상태에 도달하게 된 정보까지도 포함하는 것임. 따라서 같은 상태일지라도 그 상태에 도달하는 액션이 다들 수 있는 상황은 다를 수 있음. 가령 do(pickup(Ball, S0)라면, S0 상황에서의 Ball을 pickup하는 액션을 취한 상황을 표기함. 단순한 상태 정보가 아닌, 복합적인 상황 정보를 의미 (It is not a state, but a situation)

Situation Calculus의 구성식(formulae)

Situation Calculus를 사용하는 데 있어 몇 가지 패턴이 사용된다. 패턴이라 하면 마치 공식(formulae)과 같은 것이다.

Action precondition

액션을 실행하기 위해 필요한 사전 조건 (precondition)을 구성하기 위한 논리 공식이다. 여기에서 Poss (a, s)라고 불리는 술어 논리를 종종 사용하는데, Poss(a, s) 는 액션이 행할 수 있는지를 점검(check)하기 위해 사용된다. 가령

Poss(drop(o), s) <-> is_carrying(o, s) 라고 하면

오브젝트 o를 drop 이라는 액션을 취하기 위한 조건은, 오브젝트를 나르고 있어야 한다는 선제 조건이 있어야 한다는 의미이다.

Action effects

액션을 행한 후의 변화를 기술하기 위한 논리 구성 방식이다. 가령

Poss(pickup(o), s) -> is_carrying (o, do (pickup(o), s)) 라고 하면

오브젝트 o를 pickup하고 나면 is_carrying Fluents 가 참이 된다는 의미이다.

Successor states axiom

Situation Calculus에서 핵심적인 개념으로 행동이 발생한 이후 Fluents에 대한 내용을 명세화하는 것에 대한 의미이다.  이 논리는 Frame Problem과도 연관되며, Situation Calculus에서 Frame Problem을 해결하기 위한 방법이 바로 Successor states axiom이다. 가령

Poss(a, s) -> [broken(o, do(a s)) <-> a = drop(o) ^ fragile(o) V broken(o, s) ^ a != repair(o)] 라고 하면

위 논리는 broken에 대한 Successor state를 기술하는 방법이다.

참고

스택 기반 FSM

스택 기반 FSM은 게임 아키텍처에서 자주 볼 수 있는 기법이면서 설계 패턴으로, 상태가 스택 메모리에 팝(pop)되거나 푸시(push)될 수 있는 구조이다. 이는 현 상태에서 인터럽트 걸려 새로운 상태로 전이되어 액션이 되는 진행되며 완료되면 다시 이전 상태로 팝되어 복귀하는 구조이다. 마치 프로그램에서 서브 함수를 호출하는 식의 스택 사용과 동일하여 붙여진 이름일 것이다. 가령 게임에서 건물을 짓는 있는 유닛이 공격을 받을 경우 유닛은 공격행동으로 전이한다. 만약 적이 없어졌다면 그 유닛은 다시 원래의 행동으로 돌아갈 것이다.

보통의 상태기계는 현재 상태만이 중요하고 상태에 따른 행동을 한다. 하지만 스택 기반의 FSM은 상태 도중 인터럽트가 걸리면 해당하는 스택을 푸시하고 인터럽트 처리가 완료되면 푸시를 했던 상태를 다시 팝하여 운영되는 구조이다. 따라서 스택 기반의 FSM에서는 이전 상태 혹은 푸시를 했던 상태를 기억해야 하는 번거로움은 있다.

스택 기반 FSM을 잘 활용하면 기본 FSM보다 상대적으로 간단한 상태머신으로 구성 가능하다. 일반적인 FSM은 동일 평면 내 상태들간 연결 구성이 2^n으로 증가하지만 스택 구조로는 함수 개념처럼 상태를 모듈화하여 관리하면 상태 수가 대폭 줄어들 것이기 때문이다. 상태 기계가 명백히 분리가능할 경우에 사용하면 바람직하다. 그러나 이전 상태로 항상 복귀가 가능하지는 않을 수 있음을 유의해야 한다.

추상적인 상태 개념으로 사용하여 전체 상태간 연결 관계를 유지하면서 재사용성을 높이려면 HFSM (Hierarchical FSM)을 사용하고 일부를 모듈화하여 재사용성을 높이려면 스택 기반 FSM을 사용하는 것이 적당하다.

stackFSM