목 차
1. 머리말
2. 상태 공간을 줄이기 위한 연구 3. 가상환경에 적합한 상태 공간 관리 방법 4. 사례를 통한 상태 공간의 크기 비교 5. 결론
의사결정의 정확성을 고려한 Q-학습의 상태 공간을 줄이는 방법
－ 3D환경에 적용한 사례 중심으로
성연식*ㆍ조경은**ㆍ엄기현**
1)
1. 머리말
가상현실은 물리적인 객체를 가상환경에서 실세계와 같이 이동시키 는 기술이다.1) 가상현실에 관한 연구 범위가 커지면서 가상현실과 인공 지능을 통합하는 연구가 발생했다.2) 인공지능은 가상현실에서 다음과
* 동국대 게임공학과 박사과정.
** 동국대 게임멀티미디어공학과 교수.
1) N. Magnenat-Thalmann, D. Thalmann. ｢Virtual Reality software and technology｣, Encyclopedia of Computer Science and Technology, Marcel Dekker, vol. 41, pp. 331-361, 1999.
2) Ruth Aylett, Michael Luck, ｢Applying Artificial Intelligence to Virtual Reality: Intelligent
같은 역할을 한다. 첫 번째, 사용자의 행동을 모의 실험할 수 있는 환경 을 제공한다. 실세계에서 실험하기 어려운 문제를 가상현실에 구현해서 다양한 사용자의 행동을 모의 실험한다. 가상 사용자의 의사결정을 인 공지능으로 구현함으로써 모의실험의 현실성을 높인다. 두 번째, 지능적 인 가상환경을 제공한다. 가상환경은 정적인 환경이 아니라 동적인 환 경이다. 동적인 환경에는 가상의 사람, 동물 등이 존재한다. 인공지능을 사용해서 가상의 사람과 동물의 행동을 제어함으로써 실세계와 비슷한 환경을 제공한다.
가상의 사람과 동물의 의사결정을 하기 위해서는 각각 에이전트로 정의하고 다음과 같은 방법을 사용한다. 첫 번째, FSM을 사용한다.3) FSM은 에이전트의 가능한 상태를 유한개 정의하고 각각의 상태에서 전 이가 가능한 상태를 연결한다. FSM을 사용할 때 각각의 에이전트마다 의사결정 모델을 정의하기 때문에 에이전트의 종류가 많아지거나 복잡 해지면 정의하기 어렵다. 그리고 유한개의 상태로 의사결정 모델을 정 의하기 때문에 행동이 동일한 행동이 반복적으로 수행되는 단점이 있다.
두 번째, 학습을 사용한다.4) 가상환경은 복잡하기 때문에 에이전트가 자 율적으로 행동하기 위해서는 학습이 필요하다. Q-학습은 대표적인 강화 학습으로 환경 모델의 정의 없이 학습하고 행동하기 때문에 가상환경에 적합하다.5) 에이전트를 학습시키기 위해서는 환경에서 발생 가능한 모
Virtual Environments｣, Applied Artificial Intelligence, vol. 14, pp. 3-32, 2004.
3) James Cremer, Joseph Kearney, Yiannis Papelis, ｢HCSM: A Framework for Behavior and Scenario Control in Virtual Environments｣, ACM Transactions on Modeling and Computer Simulation, vol. 5, pp. 242-267, 1995.
4) Toni Conde, William Tambellini, and Daniel Thalmann, ｢Behavioral Animation of Autonomous Virtual Agents Helped by Reinforcement Learning｣, In Lecture Notes in Computer Science, pp. 175-180, 2003.
든 상태를 저장하기 위한 공간을 미리 정의한다. 학습 동안에는 정의한 상태가 발생할 때 행동을 수행하고 얻은 결과 값을 정의한 상태 공간에 저장한다. 그래서 학습을 종료하면 각 상태 공간에 저장한 결과 값으로 행동을 결정한다. 하지만 Q-학습은 환경의 상태가 많아지면 학습에 필 요한 상태 공간이 커지는 문제가 발생한다. 가상현실에서 Q-학습을 사 용할 때 상태 공간 문제를 해결할 수 있다면 자율적인 에이전트 구현이 가능하다.
상태 공간 문제를 해결하기 위한 연구들은 상태 공간을 줄이고 줄인 상태는 근접한 Q-값을 찾거나 중간 Q-값을 계산하는 방법을 사용한다.
5)6)7) 하지만 학습에 사용하는 상태를 줄이면 에이전트가 의사결정을 할 때 불확실성이 높아진다. 그래서 불확실성을 낮추면서 상태 공간을 줄일 수 있는 연구가 필요하다.
이 논문에서는 상태 공간을 줄이고 줄인 상태는 계획으로 보완하는 방법과 가상환경을 분리해서 상태 공간을 줄이는 방법을 제안한다. 제 안한 방법을 사용한다면 의사결정의 정확도를 떨어뜨리지 않으면서 상 태 공간을 줄일 수 있다.
2. 상태 공간을 줄이기 위한 연구
모든 상태를 고려해서 상태 공간을 정의하는 것은 많은 메모리를 요 구하기 때문에 상태 공간을 줄이기 위한 방법이 필요하다. 상태 공간을 줄이기 위해서는 일반적으로 에이전트의 의사결정에 영향을 덜 미치는
5) Watkins, C. J. C. H. and Dayan, P., ｢Technical Note : Q-learning｣ Machine Learning, vol. 8, pp. 279-292, 1992.
상태를 줄인다. 하지만 줄인 상태의 의사결정은 부정확해진다.
Q-학습에서 상태 공간 문제를 해결하기 위한 연구는 두 가지로 구분 한다. 첫 번째, 국소 최소 자승법(Locally Weighted Regression)을 사용해서 근접한 상태를 찾는 방법6)과 중간 Q-값을 계산 방법7)이 있다. 근접한 상태를 찾는 방법에서 정의하지 않는 상태의 Q-값은 근접한 상태를 선 택하고 선택한 상태의 Q-값을 사용한다. 근접한 상태는 거리를 측정하 는 커널(Kernel) 함수와 각각 상태의 가중치를 사용해서 거리를 구하고 가장 작은 값을 가지는 상태로 결정한다. 하지만 선택한 상태의 Q-값과 실제 Q-값 사이에는 오차가 발생한다. 상태의 중간 Q-값을 계산 방법은 두 이산 상태의 Q-값과 가치 함수를 사용해서 중간 Q-값을 계산한다.
Q-학습에서는 연속적인 값을 가지는 상태를 이산 상태로 변경해서 학습 하기 때문에 Q-값도 연속적인 값이 아닌 이산 값을 가진다. 그래서 가치 함수를 사용해서 이산 상태의 Q-값을 보정하고 해당 상태의 Q-값에 유 사한 값을 계산한다. 하지만 가치 함수가 모든 Q-값에 동일하게 사용하 기 때문에 정확성에는 문제가 있다. 두 번째, 온라인 퍼지 클러스터링을 기반으로 한 근사 함수를 사용한다.8) 이 방법에서 정의하지 않은 상태 나 학습이 부족한 상태는 각 군집에 속하는 소속도를 계산한다. 그리고 각 군집에서 가장 Q-값이 큰 행동을 찾아 최적의 행동을 예측한다.
근접한 상태를 찾거나 중간 Q-값을 계산하는 방법은 정확한 Q-값을 구하는 방법이 아니기 때문에 의사결정의 정확성을 떨어뜨린다. 정확성
6) Chris Atkeson, Andrew Moore and Stefan Schaal, ｢Locally Weighted Learning｣, Articial Intelligence Review, vol. 11, pp. 11-73, 1997.
7) H. Aljibury, ｢Using Locally Weighted Regression to Enhance Q-learning｣, University of Florida, 2002.
8) 이영아, 정태충, ｢강화학습의 Q-learning을 위한 함수근사 방법｣, 퍼지 및 지능 시스 템학회 논문지, 제13권, 제6호, pp.635-642, 2003.
을 유지하면서 상태 공간을 줄이기 위해서는 필요없는 상태 공간을 줄 이거나 정확성을 높이기 위한 보정 작업이 필요하다. 이 논문에서 정확 성의 문제를 해결할 수 있는 방법을 제안한다.
3. 가상환경에 적합한 상태 공간 관리 방법
Q-학습에서 에이전트는 다음과 같이 학습한다. 첫 번째, 가상환경에 서 에이전트가 의사결정을 하기 위한 상태를 정의한다. 에이전트는 각 상태에서 최적의 행동을 선택하고 수행한다. 그래서 학습을 하기 위해 서는 가장 먼저 행동을 수행할 상태를 정의한다. 상태 표현은 에이전트 가 학습하는 도메인에 따라 정의하는 방법이 달라진다. 두 번째, 각 상 태에 수행한 행동의 결과를 저장하기 위한 Q-테이블을 정의한다. 하나 의 상태는 하나의 Q-값에 Q-함수를 사용해서 계산한 값을 저장한다. Q- 테이블은 모든 Q-값을 포함하는 집합이다. 세 번째, 에이전트는 Q-테이 블에서 최대 Q-값을 가지는 행동을 선택하고 수행한다. 그리고 수행한 행동의 보상 값은 Q-함수를 사용해서 Q-값을 갱신한다. 에이전트는 세 번째 단계를 반복적으로 수행하면서 각 상태에서 수행할 최적의 행동을 학습한다. Q-학습은 모든 상태에 해당하는 Q-값을 정의하기 때문에 상 태의 개수가 증가 할수록 Q-값으로 구성한 Q-테이블의 크기가 커진다.
Q-학습에서 연속적인 상태를 표현하기 위해서는 상태를 양자화 한 다.9) Q-테이블 크기는 상태 개수와 동일하기 때문에 양자화 한 상태의
9) Yasutake Takahashi and Masanori Takeda and Minoru Asada, ｢Improvement Continuous Valued Q-learning and Its Application to Vision Guided Behavior Acquisition｣, In Lecture Notes in Computer Science, vol. 2019, pp. 385-390, 2001
개수가 많아질수록 Q-테이블의 크기도 같이 증가한다. 하지만 양자화 한 상태 개수를 줄일수록 표현하지 못하는 상태가 증가하기 때문에 에 이전트가 정확한 의사결정을 할 수 없다. 상태 공간을 줄이면서 정확한 의사결정을 하기 위해서는 Q-학습에서 에이전트가 의사결정에 사용하 지 않는 상태에 대한 보완이 필요하다.
이 장에서는 상태 공간을 가능한 범위에서 정의하는 방법을 소개하 고 상태 공간을 줄일 때 떨어지는 의사결정 정확도를 보완할 수 있는 두 가지 방법을 제안한다.
1) 허용범위에서 상태 공간을 정의하는 일반적인 방법
가상환경에서 상태를 가장 쉽게 정의하는 방법은 메모리가 가능한 범위에서 Q-테이블을 가장 크게 잡고 Q-테이블의 크기에 맞추어 상태의 개수를 조절하는 방법이다. 가능한 Q-테이블의 크기가 상태 공간보다 크면 Q-테이블의 크기를 상태 공간에 맞추어 정의한다. 하지만 상태 공 간이 Q-테이블의 크기보다 크면 상태를 양자화 할 때 상태 공간이 Q-테 이블의 크기보다 적게 나오도록 조절한다. 예를 들어, <그림 1>에서 상 태를 정의할 수 있는 범위가 R1부터 R2까지 일 때 양자화 하면 <그림 1>의 (d)와 같이 범위가 R1부터 R2사이의 상태를 n개 정의해서 전체 n+2개의 상태 값으로 표현할 수 있다. 범위 안에 있는 상태를 표현하는 방법은 에이전트가 학습하는 환경에 따라 다르게 정의하지만 개수가 많 아질수록 Q-테이블이 커진다.
(a) 값의 범위
(b) 3종류의 상태 값
(c) 4종류의 상태 값
(d) n종류의 상태 값
<그림 1> 상태의 양자화
양자화 할 때 상태를 표현하는 값의 개수가 적을수록 두 개의 상태 값의 중간 값을 표현할 수가 없는 경우가 자주 발생한다. 예를 들어,
<그림 2>와 같이 상태 M1부터 상태 M3까지의 상태를 상태 M1, 상태 M2,그리고 상태 M3로 정의할 때 상태 M1과 상태 M2 사이에서 에이전 트가 의사결정을 할 때 상태 M1과 상태 M2상태 중간에 있는 상태 W1 은 상태 W1에 더 가까운 상태의 행동을 수행한다.
<그림 2> 두 개의 상태 값 사이 표현
이 방법은 양자화를 통해서 상태 공간의 크기를 조절할 수 있기 때 문에 상태 공간의 문제는 해결할 수 있지만 에이전트가 의사결정을 할 때 정확하지 못한 문제가 발생한다. 그래서 상태 공간을 줄이면서 의사 결정의 정확도는 높일 수 있는 방법이 필요하다.
2) Q-학습과 계획을 통합하는 방법
Q-학습에서는 상태 공간 문제 때문에 가상환경에서 발생 가능한 모 든 상태를 고려해서 의사결정을 하지 않는다. 그래서 상태는 에이전트 가 Q-학습에 적용하는 상태와 적용하지 않는 상태로 구분한다. 적용한 상태는 상태 공간을 정의하기 위해서 사용한다. 적용한 상태가 많아지 면 상태 공간이 커지고 적용하지 않는 상태가 많아지면 상태 공간이 작 아진다. 학습 중에 적용하지 않는 상태는 바뀌어도 적용하는 상태가 동 일하면 에이전트는 동일한 상태로 판단한다. 그래서 정확한 의사결정을 하기 위해서는 Q-학습에서는 사용하지 않지만 남은 상태도 고려해서 의 사결정을 하는 방법이 필요하다.
이 논문에서는 적용하지 않는 상태를 사용해서 정확한 의사결정을 하기 위한 방법으로 계획을 학습과 통합하는 방법을 제안한다. 계획은 에이전트가 학습 과정을 거치지 않고 동적으로 의사결정하기 때문에 의 사결정을 위한 저장 공간이 필요가 없다. 그래서 상태 공간 문제가 있는 Q-학습과 통합해서 사용하기에 적합하다.
sn : n번째 상태 an : n번째 상태의 행동 (a) Q-학습에서 상태와 행동
sn : n번째 상태 gn : n번째 상태의 목표
(b) Q-학습과 계획의 통합 방법에서 상태와 행동
<그림 3> 상태와 행동의 관계
Q-학습에서는 <그림 3>의 (a)와 같이 각각의 상태에서 에이전트가 수행할 행동을 학습한다. 제안한 방법은 <그림 3>의 (b)와 같이 에이전 트가 각각의 상태에서 최적의 행동을 선택하기 위해서 학습하지 않고 계획이 수행할 목표를 선택하기 위해서 학습한다. 그래서 Q-학습에서 선택한 목표는 계획을 사용해서 달성한다. Q-학습에서는 전체 상태 중 에서 목표를 선택하기 위한 상태만 적용하기 때문에 상태 공간을 줄일 수 있다. 그리고 계획은 학습에서 적용하지 못한 상태를 사용해서 목표 를 달성하기 때문에 정확한 의사결정을 할 수 있다.
3) 상태 공간을 분리하는 방법
이 절에서는 전체 상태 공간을 두 개 이상의 지역으로 나누어 학습 하는 방법을 제안한다. Q-학습에 사용하는 상태 공간은 다음과 같은 원 인으로 에이전트가 도달하지 못하는 상태를 포함한다. 첫 번째, 상태를 양자화 하면서 발생하지 않는 상태를 포함한다. 예를 들어, <그림 4>와 같이 에이전트가 행동을 수행하면서 발생하는 상태를 이산 값으로 표현
(a) 전체 상태 공간
(b) 상태 공간 분리
<그림 4> 상태 공간
하다가 보면 발생하지 않는 상태도 상태 공간에 포함한다. 발생하지 않 는 상태는 학습에 필요한 상태 공간의 크기를 줄인다. 그래서 발생하지 않는 상태 공간을 줄이면 학습에 필요한 상태 공간을 늘릴 수 있다. 두 번째, 에이전트가 환경의 영향을 받아서 특정 상태에 진입하지 못하는 경우이다. 에이전트가 상태에 진입하지 못하면 학습도 진행하지 못하지 만 실제 발생하지도 않는다. 그래서 에이전트가 진입하지 않는 상태는 줄여도 의사결정에 영향을 주지 않는다.
상태 공간을 줄이기 위해서는 양자화 할 때 발생하지 않는 상태 공 간을 줄일 수 있도록 정의한다. 정의하는 방법은 도메인에 따라서 달라 진다. 예를 들어, <그림 4>의 (b)에서는 상태 공간을 3개의 공간으로 나 눈다. 상태 공간 1과 상태 공간 3에서 정의한 상태는 발생이 가능하지만 상태 공간 2는 발생하지 않는다. 발생하지 않는 상태 공간 2는 학습이 필요 없기 때문에 상태 공간을 정의할 필요가 없다. 그래서 학습을 위해 서는 상태 공간 1과 상태 공간 3만 정의한다. 에이전트가 행동을 선택할 때에는 현재 상태가 상태 공간 1이지 상태 공간 3적용 구분하고 각각의 상태 공간에서 행동을 선택하며 학습결과를 각각의 Q-테이블에 반영한 다.
상태 공간을 분리해서 학습하는 방법은 상태 공간을 잘게 나눌수록 발생하는 상태 공간의 크기가 작아지지만 현재 상태가 속한 지역을 찾 는 과정이 복잡해진다.
4. 사례를 통한 상태 공간의 크기 비교
이 장에서는 각각의 방법을 3D환경에 적용한 사례를 통해서 상태 공 간의 변화를 알아본다. 상태 공간 크기에 맞추어 상태를 정의할 때 에이 전트가 판단하는 상태를 알아보고 정확한 의사결정을 위해서 보안하는 두 가지 방법과 비교한다.
가상환경은 상태 공간을 정의하기 위해서 3D 지형을 X-Y축으로 잘 라 <그림 5>의 (a)와 같이 정의한다. 가상환경에는 두 개의 에이전트를 배치하고 에이전트의 상태는 좌표 x와 y로 기술한다. 에이전트는 <그림 5>의 (b)와 같이 에이전트는 x축으로 14칸, y축으로 10칸의 격자 환경에
(a) 가상환경
(b) 에이전트 위치 상태의 양자화
<그림 5> 가상환경 단면도
서 이동한다. 가상환경의 현재 상태는 두 개 에이전트의 위치 x와 위치 y로 표현한다. 예를 들어, 에이전트의 위치는 (1, 1)부터 (14, 10)까지 중 에 하나로 표현한다.
0 50,000 100,000 150,000 200,000 250,000
1 2 3 4 5 6 7 8 9 10
전체 상태 개수
<그림 6> 추가 상태 개수와 상태 공간 크기
1) 상태 개수를 줄이기
에이전트는 에이전트의 위치 x와 위치 y로 상태를 기술하기 때문에 하나의 에이전트 상태를 표현하기 위해서는 140가지의 위치 상태가 필 요하다. 그리고 두 개의 에이전트를 동시에 표현하기 위해서는 140의 제 곱인 19,600가지의 상태가 필요하다. 만약에 가상환경에서 에이전트의 상태를 표현하기 위해서 위치 상태뿐만 아니라 다른 상태도 적용한다면
<그림 6>과 같이 다른 상태의 개수가 증가하면서 상태 공간의 크기도 선형적으로 증가한다.
상태 공간의 크기는 각각의 상태 개수를 곱한 값으로 결정한다. 그래 서 상태를 표현하기 위한 개수를 줄인다면 상태 공간을 줄일 수 있다.
예를 들어, <그림 7>과 같이 에이전트 위치를 x축으로 7개, y축으로 5 개로 표현하면 35가지로 하나의 에이전트 상태를 줄여서 표현할 수 있 다. 상태 공간은 두 개의 에이전트의 상태로 표현하기 때문에 35의 곱으
<그림 7> 7 X 5 크기의 가상환경
<그림 8> 에이전트의 상태 판단
로 1,225개 상태로 표현할 수 있다. 예를 들어, 에이전트의 위치는 (1, 1) 부터 (7, 5)까지 중에 하나로 표현한다. 에이전트의 위치 상태를 표현할 때 x축과 y축을 각각 반씩 줄임으로써 상태 공간을 약 6%로 줄일 수 있 다.
이 방법은 위치 표현을 반씩 줄이기 때문에 <그림 8>과 같이 에이 전트가 있는 4개의 상태를 1개의 상태로 판단한다. 두 개의 에이전트 위 치는 16개의 상태를 1개의 상태로 판단한다. 그래서 서로 다른 상태에 있어도 같은 상태로 판단하는 경우가 발생한다. 잘못된 판단은 의사결 정의 정확도를 떨어뜨린다.
<그림 9> 에이전트의 위치 정보 보 정을 위한 계 획 사용
2) Q-학습과 계획 통합을 사용한 Q-테이블 크기 축소
학습과 계획을 통합해서 사용할 때 상태 공간의 크기는 에이전트가 학습에 적용하는 상태 크기에 비례한다. 학습에 적용하는 상태와 계획 에서 사용하는 상태는 가상환경의 특성을 고려해서 정의한다. 학습기는 계획기가 수행할 목표를 선택하기 위해서 학습한다. 계획기는 학습기가 선택한 목표를 수행하기 위해 계획한다.
두 개의 에이전트가 서로 다른 위치에 있지만 상태 공간의 크기를 줄 이다보면 학습기는 같은 상태로 판단한다. 예를 들어, <그림 9>과 같이 두 개의 에이전트는 모두 위치 (2, 2)에 있다고 학습기는 판단한다. 그래 서 학습기가 판단한 이 상태는 동일하지만 계획기에서는 학습에서 사용 하지 않는 정보를 사용해서 세부적으로 구분한다. <그림 9>와 같은 경 우에는 인접한 에이전트 간의 거리, 인접한 에이전트 정보 그리고 인접 한 환경 정보를 계획기가 받는다. 그래서 계획기는 인접한 에이전트 간 의 거리로 두 에이전트가 동일한 위치에 있는 지 아니면 서로 다른 위치 에 있는 지 판단하고 이에 맞는 행동을 결정한다. 결국, 학습기는 상태
를 크게 나누어 각 상태에 적합한 계획기의 목표를 선택하고 계획기는 선택한 목표를 인지한 정보로 에이전트가 수행할 행동을 결정한다. 인 접한 정보를 학습기가 사용안함으로써 상태 공간을 줄일 수 있고 계획 기가 사용함으로써 학습기가 고려하지 못한 사항을 고려한 행동 결정이 가능하다.
3) 가상환경을 분리해서 Q-테이블을 정의
상태 공간에는 에이전트가 학습하면서 발생하는 상태와 발생하지 않 는 공간이 있다. 예를 들어, 에이전트가 학습하기 위해서 에이전트의 상 태를 위치 상태로 표현하면 이동하지 못하는 공간은 Q-값을 정의하지만
<그림 10>의 (a)와 같이 사용하지 않는 경우가 발생한다. 이 공간은 에 이전트가 이동하지 못하는 공간이지만 Q-테이블에 정의한 공간이다. 일 반적으로 가상환경에서 에이전트가 이동하지 못하는 곳이 다수 존재한 다. Q-테이블을 정의할 때 이런 공간에 상태 공간을 할당하지 않는다면 많은 공간을 줄일 수 있다.
위치 x와 위치 y로 두 개의 에이전트의 상태를 기술할 때 에이전트 의 위치는 (1, 1)부터 (14,10)까지 중에 하나의 값으로 표현한다. 이 상태 공간은 다음과 같이 줄일 수 있다. 제안한 방법과 같이 에이전트가 이동 하지 못하는 공간을 <그림 10>의 (a)와 같이 제외하고 상태 공간을 다 시 정의하면 <그림 10>의 (b)와 같다. <그림 10>의 (b)의 상태 공간은 두 개의 상태 공간 크기를 합하면 전체 75개의 상태 공간으로 이루어진 다. 줄인 상태는 두 그룹으로 나누어 위치를 표현한다. 첫 번째, 에이전 트의 위치를 (1, 1)부터 (7, 7)까지로 표현한다. 두 번째, (1, 1)부터 (13, 2) 까지로 표현한다. 처음에 에이전트가 이동하지 못한 공간까지 포함한
(a) 에이전트가 이동하지 못하는 공간
(b) 가상환경의 상태 공간 분리
<그림 10> 가상환경과 상태 공간
<그림 10>의 (a) 상태 공간에 비해서 약 53%로 상태 공간을 줄일 수 있다.
5. 결론
이 논문에서는 Q-학습을 가상환경에 사용할 때 발생하는 상태 공간
의 문제에 대해서 알아보았다. Q-학습에서 상태 공간을 줄이는 방법은 상태 공간의 크기를 조절할 수 있지만 에이전트의 이사 결정이 정확하 지 못한 문제가 발생한다. 그래서 상태 공간 문제를 해결하기 위해서 2 가지 방법을 제시하고 각각의 방법을 사용할 때 상태 공간의 크기 변화 를 알아보았다. 첫 번째, Q-학습과 계획을 통합해서 사용하는 방법을 소 개했다. 이 방법은 학습에서 고려하지 못한 상태를 계획에서 사용함으 로써 정확한 의사결정을 기대할 수 있었다. 두 번째, 상태 공간을 나누 어 학습하는 방법을 제안했다. 이 방법은 상태 공간을 나누는 방법에 따 라서 상태 공간의 크기에 차이가 발생한다. 사용하지 않는 상태를 줄이 기 때문에 상태 공간을 줄이면서 의사결정에는 영향을 주지 않는 방법 이었다.
사례를 통한 비교에서는 3차원 가상환경을 X-Y축으로 잘라서 2차원 환경으로 만들고 에이전트의 상태를 표현했다. Q-학습에서 상태 공간을 줄이는 방법은 약 6%정도로 상태 공간을 줄일 수 있었지만 의사결정의 정확도가 많이 떨어졌다. 그래서 제안한 학습과 계획을 통합하는 방법 은 상태 공간의 크기를 자유롭게 정의할 수 있었고 Q-학습에 적용하는 않는 상태는 계획에서 고려하기 때문에 의사결정의 정확도도 유지할 수 있었다. 마지막으로 상태 공간을 나누는 방법은 의사결정에 영향을 주 지 않고 사용안하는 상태 공간을 제거함으로써 상태 공간을 반으로 줄 일 수 있었다.
Q-학습은 환경 모델을 정의하지 않고 학습하기 때문에 가상 환경처 럼 복잡한 환경에 적합하지만 적용하기 위해서는 상태 공간 문제뿐만 아니라 학습 시간과 같은 다양한 문제를 해결하기 위한 연구를 더 진행 해야 할 것이다.
￭ 참고문헌
N. Magnenat-Thalmann, D. Thalmann. ｢Virtual Reality software and technology｣, Encyclopedia of Computer Science and Technology, Marcel Dekker, vol. 41, pp. 331-361, 1999.
Ruth Aylett, Michael Luck, ｢Applying Artificial Intelligence to Virtual Reality: Intelligent Virtual Environments｣, Applied Artificial Intelligence, vol. 14, pp. 3-32, 2004.
James Cremer, Joseph Kearney, Yiannis Papelis, ｢HCSM: A Framework for Behavior and Scenario Control in Virtual Environments｣, ACM Transactions on Modeling and Computer Simulation, vol. 5, pp.
242-267, 1995.
Toni Conde, William Tambellini, and Daniel Thalmann, ｢Behavioral Animation of Autonomous Virtual Agents Helped by Reinforcement Learning｣, In Lecture Notes in Computer Science, pp. 175-180, 2003.
Watkins, C. J. C. H. and Dayan, P., ｢Technical Note : Q-learning｣
Machine Learning, vol. 8, pp. 279-292, 1992.
Chris Atkeson, Andrew Moore and Stefan Schaal, ｢Locally Weighted Learning｣, Articial Intelligence Review, vol. 11, pp. 11-73, 1997.
H. Aljibury, ｢Using Locally Weighted Regression to Enhance Q-learning｣, University of Florida, 2002.
이영아, 정태충, ｢강화학습의 Q-learning을 위한 함수근사 방법｣, 퍼지 및 지능 시 스템학회 논문지, 제13권, 제6호, pp.635-642, 2003.
Yasutake Takahashi and Masanori Takeda and Minoru Asada, ｢ Improvement Continuous Valued Q-learning and Its Application to Vision Guided Behavior Acquisition｣, In Lecture Notes in Computer Science, vol. 2019, pp. 385-390, 2001.
￭ 국문초록
가상환경에서 사용자와 상호 작용하는 가상현실 분야는 점점 넓어지면서 인공지능 기술을 사용한다. 가상현실에서 사람이나 동물의 움직임을 제어할 때 FSM과 같은 전통적인 인공지능을 사용하면 동일한 행동이 반복적으로 수 행되거나 행동 모델이 복잡한 경우에는 정의하기가 어려운 단점이 있다. Q-학 습은 환경 모델을 정의하지 않고 학습하기 때문에 가상환경에 적합하다. 하지 만 환경이 복잡해지면 학습한 결과를 저장하는 상태 공간이 커지는 문제가 발 생한다. 상태 공간 문제를 해결하기 위한 연구들은 학습에 적용하는 상태를 줄여서 상태 공간을 줄인다. 그리고 발생한 오차는 계산하거나 추정하는 방법 을 사용한다. 하지만 정확한 의사결정을 하기 위해서는 모든 상태를 고려하면 서 학습하는 방법이 필요하다. 이 논문에서는 Q-학습의 상태 공간을 줄이면서 의사결정의 정확성이 떨어지는 것을 보완할 수 있는 두 가지 방법을 제안한 다. 첫 번째, 학습과 계획을 통합한 방법에서는 상태 공간을 줄일 때 발생하는 의사결정의 정확성 문제를 계획기를 사용해서 보완하는 방법을 제안한다. 두 번째, 가상환경의 공간을 분리해서 다수의 작은 상태공간으로 학습에 사용하 는 상태공간을 정의하는 방법을 소개한다. 이 방법은 사례에서 공간을 두 개 로 나누어 상태공간을 정의함으로써 학습 결과를 저장하는 상태공간을 약 53%로 줄였다.
주제어: 가상현실, Q-학습, 상태 공간 문제
￭ Abstract
A Technique to Solve the Q-learning's Curse of Dimensionality
Considering Decision-Making's Accuracy
－ Focused on the Case Study in 3D Environment
Sung, Yun-sick, Cho Kyung-eun, Um, Ky-hyun
As Virtual reality which interacts with user extends its research fields, it started to integrate with artificial intelligence. If virtual human and animal is controlled using traditional artificial intelligence like FSM in Virtual reality, their actions are usually executed recursively or it's sometime vary difficult to define their actions when action's model is complex. Q-learning suits virtual environment, because agent could learn without the definition of environment model. But it needs to solve the curse of dimensionality, because state space is defined bigger as environment is more complex. The research which solves this problem reduces state space and calculates the Q-value which state is not defined. But it needs learning algorithm considering all states to decide an action accurately. In this paper, we propose two methods which can preserve decision's accuracy. First, we propose the method which preserves decision's accuracy using planner when Q-learning's state
space is reduced. Second, we introduce the way how to divide virtual environment and define state space of learning using numbers of small state spaces. In this way, we divided the space into two regions which could cut down the state space where learning results store by 53%.
Keywords: Virtual reality, Q-learning, Curse of dimensionality
논문투고일 : 2009년 2월 23일 심사완료일 : 2009년 3월 20일 게재확정일 : 2009년 4월 20일