Advanced
Large-Scale Realtime Crowd Simulation Using Image-Based Affordance and Navigation Potential Fields
Large-Scale Realtime Crowd Simulation Using Image-Based Affordance and Navigation Potential Fields
Journal of Korea Multimedia Society. 2014. Aug, 17(9): 1104-1114
Copyright © 2014, Korea Multimedia Society
  • Received : July 01, 2014
  • Accepted : July 25, 2014
  • Published : August 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
수열 옥
Dept. of Game Eng., School of Digital Entertainment, TongMyong University

Abstract
In large-scale crowd simulations, it is very important for the decision-making system of manipulating interactive behaviors to minimize the computational cost for controlling realistic behaviors such as collision avoidance. In this paper, we propose a large-scale realtime crowd simulation method using the affordance and navigation potential fields such as attractive and repulsive forces of electromagnetic fields. In particular, the model that we propose locally handles the realistic interactions between agents, and thus radically reduces the cost of expensive computation on interactions which has been the most problematic in crowd simulation. Our method is widely applicable to the expression and analysis of various crowd behaviors that are needed in behavior control in computer games, crowd scenes in movies, emergent behaviors of evacuation, etc.
Keywords
1. 서 론
대규모 군중행동 시뮬레이션은 영화나 애니메이션 그리고 게임과 같은 영상콘텐츠 [19] 분야뿐만 아니라 긴급 상황(재난)시의 군중행동이나 건축설계, 도시교통 등 다양한 분야에서 연구가 진행되고 있다. 이들 분야에서는 집단행동의 움직임의 대상이 되는 각 개체들의 움직임을 사실적이고 다양한 상황에서의 행동 표현하기 위한 방법으로 크게 멀티 에이전트시스템을 이용한 접근방법과 유체역학 등을 기반으로 하는 파티클 시스템을 이용한 접근방법으로 움직임을 표현하고 있다. 먼저 멀티 에이전트 접근방법은 개체간의 상호 작용적인 움직임에 있어서 특성 및 상태 등을 상세하게 모델링할 수 있기 때문에 다른 방법들보다 사실적이고 다양한 움직임을 표현 할 수 있다. 반면에, 멀티 에이전트의 경우에는 상호작용에 따른 움직임을 생성하는데 있어 많은 계산 비용이 들어가기 때문에 실시간으로 대규모의 군중 행동 시뮬레이션과 같은 거시적 환경에서의 움직임의 현상을 해석하거나 시뮬레이션 하는데 있어서는 어려움이 있다.
한편, 파티클 시스템을 이용한 접근 방법은 개별 개체들의 움직임을 제어하기 보다는 집단전체의 행동특성에 관해서 표현하기 위한 방법으로 대규모의 군집으로 움직이는 군중 행동이나 거시적 환경에 있어서 개체의 움직임을 사실적으로 표현 할 수 있다는 장점이 있다. 단점으로는 멀티 에이전트가 가지고 있는 개별 개체의 다양한 특성 및 속성에 따른 미시적인 움직임을 표현하는데 있어서는 어려움이 있다. 그리고 동종의 특성을 가진 개체들이 정해진 상황에 대해서만 시뮬레이션 할 수 있다는 단점과 개체간의 상호작용을 대한 움직임을 생성하기 위해서 사용되는 수식 및 함수의 표현이 매우 어렵다는 점이 있다.
대규모 군중시뮬레이션을 적용하고자 하는 다양한 분야에서는 멀티에이전트가 가지는 개별 개체의 특성이나 성질에 따른 미시적이고 세밀한 행동 표현 특성과 파티클 시스템이 가지고 있는 거시적인 군중 행동의 현상 해석적인 표현 특성으로 하는 양쪽 모두의 특성을 필요로 하는 경우가 많다. 그럼에도 불구하고 아직까지는 군중행동 시뮬레이션을 접근하는 방법에 있어서 거시적 접근방법 이나 미시적인 접근방법중이 하나를 선택해서 하는 경우가 대부분이다.
이에 본 논문에서는 멀티 에이전트의 의사결정 시스템과 파티클 시스템의 역장(Force Field)개념을 기반으로 하여 대규모 군중시뮬레이션에서 거시적인 행동표현 특성과 미시적인 행동표현 특성의 두 가지 특성을 모두 표현할 수 있고 또한 군중행동 시뮬레이션의 고속화 기법과 이에 따른 다양한 행동 제어방법을 제안하고자 한다.
본 논문에서는 군중의 조종행동에 대한 의사결정 시스템에서 가장 많은 계산 비용을 차지하는 에이전트끼리 상호작용을 자기장과 같은 역장(Force Field) 개념을 이용하여 계산비용을 최소화하는 기법이 핵심요소이다. 이를 위해 에이전트의 상호작용에 대한 영향도를 각 에이전트 특성에 따른 상태, 모양 및 크기를 수식 형태의 포텐셜장으로 표현하는 대신에 이미지 기반의 개별 에이전트의 유도 포텐셜장(Affordance Potential Field:이하 AF)형태로 변환하여 적용한다. 각각 에이전트의 AF는 에이전트의 위치에 맞게 가상공간에 맵핑된다. 에이전트는 항해 계획(Navigation Planning)을 위해 가상공간상에 맵핑된 AF를 바탕으로 항해 포텐셜장(Navigation Potential Field:이하 NF)을 생성하고 자신의 여러 감지센서를 이용하여 생성된 NF 로부터 값을 읽어와 행동에 필요한 조종력을 결정하게 된다. 본 논문에서 제안한 방법은 에이전트의 의사결정 시스템과 파티클 시스템의 역장 개념을 기반으로 하여 대규모 군중시뮬레이션에서 거시적인 행동표현 특성과 미시적인 행동 표현 특성의 두 가지 특성을 모두 표현할 수 있고 또한 군중행동 시뮬레이션의 고속화가 가능하다.
2. 이전 연구
많은 수의 객체들에 대한 군중행동 시뮬레이션은 그래픽스 하드웨어의 발전과 함께 비디오 게임 [1] , 영화 등에서 그 적용 사례가 늘어나고 있다. 이 뿐만 아니라 로봇공학 [2] , 교통공학 [3] , 그리고 사회과학 [4] 등을 포함하여 다양한 분야에 걸쳐 많은 연구가 진행되고 있다. 이러한 군중행동 시뮬레이션 모델은 크게 군중 모델의 접근방법과 특징에 따라서 군중의 규모와 시간 크기에 따라서 분류할 수 있다. 군중 규모에 따른 미지적인 모델은 주로 규칙기반 플로킹 모델 [5] , 사회적인 힘 모델 [6 - 7] , 셀룰라 오토마타 모델 [8] , 속도-장애물 기반 공식화모델 [9] 등 다양한 방법들이 제안되어왔다. 거시적인 모델은 주로 유체모델 [10 - 12] 을 이용하는 경우가 많다.
시간스케일에 따른 군중시뮬레이션 모델은 적용 목적에 따라 장시간에 걸쳐 군중의 물리적인 특정보다는 무형의 사회학적인요소와 심리학적 요소를 포함한 인지모델에 초점을 맞추고 있는 모델과 단시간적으로 섬세한 움직임의 패턴과 같은 군중의 물리적인 특징을 표현하기 위한 모델이 있다. 이들 모델은 주로 자율형 에이전트를 기반으로 하여 자신의 상태를 인지하고 또한 주위의 환경에 대해 동적으로 반응하여 움직임을 생성한다. 몇몇 연구자들은 실제 군중행동의 비디오 정보로 부터 의미있는 흐름 정보를 추출하여 그룹 행동모델을 구축하기 위한 데이터 기반 처리방법 [13 - 14] 을 제안하고 있다.
이들의 접근 방법은 미시적 영역에서의 에이전트 움직임을 제어함으로 사실적인 움직임 표현에 중점을 두었다. 때문에 실시간으로 대규모의 에이전트를 시뮬레이션 하는데 어려움이 많고 가능하더라도 국지적 영역에서 에이전트간의 충돌 및 교착상태에 빠지는 문제점과 전체적인 흐름에서 비사실적인 움직임을 나타나는 경우가 많다. 이를 개선하는 방법으로, Patil [15] 등은 군중의 흐름을 직접적으로 제어하기 위해 사용자의 직접적인 스케치나 비디오데이터에서 추출정보를 벡터장로 표현하여 사용자에게 대역적인 현상 및 그룹의 동적인 움직임을 경로 입력을 기반으로 한 상호작용 모델을 제안하고 있다. 하지만 이 방법은 대규모 에이전트에 가장 큰 연산 시간을 차지하는 충돌처리 부분에 복잡한 수식을 이용하여 처리하기 때문에 실시간 처리에 어려움이 있다.
3. 유도 포텐셜장(AF)과 항해 포텐셜장(NF)
이 장에서는 제안한 가상 역장(Virtual Force Field)개념을 이용한 대규모 군중시뮬레이션 시스템의 흐름도와 AF와 NF에 대한 설명하고자 한다. 제안한 시스템의 전체적인 흐름은 Fig. 1 과 같다. 먼저, 사용자로 부터 에이전트 및 장애물과 같은 가상 환경을 구성하는 오브젝트에 대한 이미지 또는 수식 입력 값을 받아 AF를 생성하고, 생성된 AF는 가상공간상의 오브젝트 위치에 맵핑하여 NF를 생성한다. NF는 에이전트의 상호작용을 위한 가상환경의 전체 포텐셜장 이미지를 나타낸다.
PPT Slide
Lager Image
Flow diagram of crowd simulation based on affordance and navigation potential fields.
AF는 자석이 자신의 주위에 일정크기의 자기장을 만들고 상호간의 자극에 따라서 인력장(Attractive potential field)과 척력장(Repulsive potential field)을 형성하는 것처럼 에이전트나 장애물이 다른 에이전트나 주변의 장애물과 상호작용을 위한 포텐셜장으로 정의한다. 특히, 에이전트의 AF는 자신의 위치에서 장애물을 회피하거나 목표물을 찾기 위한 시계장(Visual Potential Field)으로 간주한다.
이에 에이전트의 AF는 에이전트 상태에 따라 여러 가지 심리적인 포텐셜장으로 표현이 가능하지만, 본 논문에서는 크게 두 가지 상태의 장으로서 표현한다. 하나는 가상 환경에서 에이전트가 다른 에이전트나 장애물에 대한 충돌회피를 위한 척력장, 그리고 다른 하나는 에이전트가 목표물을 찾아가기 위한 인력장이다. Fig. 2 (a)에서는 척력장으로서 포텐셜장의 구배(Gradient)가 밖으로 나가는 형태의 이미지를 나타내고, Fig. 2 (c)는 인력장으로서 포텐셜장의 구배가 안으로 들어오는 형태의 이미지를 나타내고 있는 AF 모양이다.
PPT Slide
Lager Image
AF on agents and scalar potential fields of obstacles.
최근, 이동로봇연구에서 목표경로 결정을 할 때 포텐셜장을 이용한 연구가 많이 진행되고 있다 [16 , 17] . 하지만 이들 연구의 대부분은 장애물 회피나 목표 위치로 유도하기 위해 방정식 형태의 포텐셜장을 적용하는데 이는 상태의 변화에 따 포텐셜장을 실시간으로 변경해야 한다든지 혹은 오브젝트와의 상호작용 범위가 바뀔 때 마나 새로운 방정식 모델을 도입해야하는 문제가 발생한다. 이에 본 연구에서는 AF를 기반으로 해서 설계하였다. AF를 이미지로 사용함으로써의 이점은 다음과 같다.
  • • 에이전트의 상호작용에 대한 복잡한 수식을 사용할 필요가 없다.
  • • 에이전트의 심리적인 특징과 형태에 따라 자유롭게 표현이 가능하고 만들기가 쉽다.
  • • 이미지 처리를 함으로써 보간이 용이하고 GPU 병렬처리를 통해 고속화가 가능하다.
NF는 에이전트끼리 또는 에이전트와 장애물과 같은 오브젝트간의 상호작용을 처리하기 위해 사용된다. NF는 에이전트의 AF와 장애물AF 그리고 목적지로 유도하기 위한 목적장(Target Force Field)의 AF 등을 가상 환경의 맵상에 텍스쳐로 맵핑한 전역적인 포텐셜장의 이미지이다. NF는 에이전트의 목적지이동과 에이전트간의 충돌회피처리 및 장애물회피 등의 상호작용을 이미지로 처리함으로서 기존의 수식기반에 비해 획기적으로 계산비용을 줄일 수 있다. 또한 에이전트는 다양한 상태 특성을 나타내는 AF를 다중 레이어 NF에 나누어 적용함으로써 다양한 심리상태의 조종행동을 표현할 수 있다.
- 3.1 유도 포텐셜장(AF) 생성과 항해 포텐셜장(NF) 생성
유도 포텐셜장(AF)와 항해 포텐셜장(NF)는 가상군중환경에서 에이전트 및 가상 오브젝트와의 다양한 상호작용적 특성을 GPU상의 컬러 버퍼 메모리에 컬러 코드화된 포텐셜장 이미지(Color Coded Image of Potential Field)이다.
AF생성방법은 크게 2가지로 나눌 수 있다. 하나는 포텐셜장 방정식을 이용한 AF생성방법과 다른 하나는 이미지편집 툴을 활용한 AF생성방법이다. 먼저, 포텐셜장 방정식을 이용한 AF생성방법은 AF를 생성할 정점 정보와 식 (1)과 같은 가우시안 포텐셜 함수를 이용하여 생성한다. 각 정점의 위치는 Fig. 3 (a)와 같이 정방형으로 배치한다. 그리고 각 정점은 가우시안 포텐셜 함수의 결과값을 색상 값으로 하고 정점 색상 보간을 통해 Fig. 3 (b)와 같은 이미지를 생성한다. 이를 모든 정점들에 적용하면 Fig. 3 (c)와 같은 하나의 AF를 생성할 수 있다.
PPT Slide
Lager Image
PPT Slide
Lager Image
Generation of AF images based on the simple potential equation.
이 방법은 사전에 간단한 포텐셜장 방정식을 이용하여 AF생성이 가능하다는 점과 특별한 이미지 편집도구를 사용하지 않고도 생성이 가능하다는 장점이 있다. 두 번째 생성 방법은 이미지 편집 툴을 사용한 AF생성방법이다. 이 방법은 AF를 이미지편집 툴을 사용하여 직접 다루기 때문에 방정식을 이용한 AF를 생성방법보다 빠르게 AF생성이 가능하다. 또한, 방정식으로 표현하기 어렵고 복잡한 AF를 생성할 수 있는 장점이 있다.
NF생성은 목적지까지의 이동을 위한 목적장과 가상환경에서의 장애물장, 에이전트의 유도장 등을 가상환경의 맵상에 텍스쳐로 맵핑한 전역적인 포텐셜장의 이미지이다. NF는 가상환경에서 에이전트 및 장애물과 같은 오브젝트들의 현재 위치에 AF를 NF의 그리드상에 맵핑하여 생성한다. AF는 NF에 맵핑 할 때에 에이전트를 포함한 각 객체들이 가지고 있는 AF의 영향도 범위를 조정하여 맵핑한다. Fig. 4 는 에이전트의 목적장을 NF에 맵핑한 포텐셜장 이미지 Fig. 4 (a)와 에이전트의 충돌처리 척력장을 NF에 맵핑한 포텐셜장 이미지 Fig. 4 (b)를 나타내고 있다.
PPT Slide
Lager Image
Mapping of Agent AF onto NF.
그리고 AF는 Fig. 5 와 같이 NF에 맵핑할 때에 에이전트나 오브젝트의 다양한 상태 및 특성에 따라 스케일뿐만 아니라 다양한 형상으로 모양을 조정하여 NF에 맵핑된다. 그리고 NF는 Fig. 6 과 같이 AF의 특성이나 종류에 따라 다중 레이어로 NF생성하여 에이전트의 상태나 특성에 맞게 NF의 포텐셜장 값을 조합하여 다양한 움직임을 표현하는데 사용된다.
PPT Slide
Lager Image
Mapping onto NF depending on AF properties by controling AF shape vertices.
PPT Slide
Lager Image
AF mapping onto multi-layered NF.
- 3.2 에이전트의 센서 설계
본 연구에서는 복잡한 대규모 군중 시뮬레이션 환경에서 적응적으로 상호작용하면서 행동하도록 에이전트의 센서를 시야센서(Visual Sensor)로 간주하여 에이전트의 속도 및 상태에 따라 위치나 감지 범위가 적응적으로 변동 가능하도록 용장성있게 설계하였다. Fig. 7 (a)과 같이 에이전트의 주변 8방향(S1∼S8) 센서는 근접 상황에서 충돌회피와 같은 상황을 효과적으로 대응하도록 주변을 둘러싸는 형태로 설계하였다. 그리고 전방(VS1∼VS3) 센서는 사람의 이동속도에 따른 시야범위 조절과 같이 에이전트의 속도에 증감에 따른 센서의 위치조절과 함께 전방에 대한 사전감지를 통해 충돌회피 방향 전환과 감속처리가 가능하도록 설계하였다. 전방 센서의 위치조절은 진행 속도에 따라 에이전트의 중심에서 방사형으로 뻗어나가는 형태가 아닌 Fig. 7 (b)와 같이 에이전트의 진행 방향으로 속도에 비례해서 직선 방향으로 위치하도록 하였다. 이는 인간의 시야가 속도에 따라 전방주시점이 멀어지고 시야범위가 좁아지는 것과 같이 에이전트의 속도증가에 따라 센서 범위를 전방으로 좁히고 속도에 비례해서 사전 충돌 처리를 하기 위해서이다.
PPT Slide
Lager Image
Sensor design of agents.
4. 에이전트의 조종력 계산
에이전트의 조종력은 상호작용을 필요로 하지 않는 도착하기, 회피하기, 배회하기 등의 기본 행동 조종력과 에이전트간이나 장애물과의 상호작용에 따른 조종력으로 크게 두 가지로 나눌 수 있다. 먼저, 에이전트의 기본 행동 조종력은 Reynolds [5] 가 제안한 모델을 적용하였다. 그리고 상호작용에 따른 조종력은 본 논문에서 제안한 NF에 의한 조종력이다. 에이전트는 이 두 가지 조종력을 자신의 상태에 따라 적절하게 선형 결합하여 다양한 조종행동 표현이 가능하다.
- 4.1 척력과 인력 계산
척력장은 에이전트간 혹은 벽과 같은 장애물을 피해야하는 상황을 표현하기 적합한 장 (potential field) 으로 Fig. 8 (a)와 같이 장의 중심에서 바깥쪽으로 에이전트를 밀어내는 힘을 발생시킨다. 포텐셜장의 힘을 계산할 때에는 구배법을 사용하여 스칼라값이 높은 곳에서 낮은 곳으로 흘러가는 형식이다. 이를 간단한 정수 값으로 표현하면 Fig. 8 (b)와 같다. 이 형태를 본 논문에서 사용되는 AF로 변환을 하게 되면 Fig. 8 (c)와 같은 표현된다. 척력장의 AF의 바깥 끝 부분은 AF가 맵핑되기 전 NF의 컬러코드 초기값과 동일하도록 설정하였다.
PPT Slide
Lager Image
Representations of repulsive force.
아래의 식 (2)은 에이전트의 센서를 통해서 NF에 매핑된 척력장의 이미지로부터 척력을 계산하는 식이다.
PPT Slide
Lager Image
여기서, N은 에이전트의 센서 개수이고, SensorPos는 센서의 현재 위치를 나타내다. AgentPos는 에이전트의 현재 중심위치이다. 그리고 SensorValue와 AgentValue는 각 센서 위치와 에이전트의 중심 위치에서 읽어낸 척력장의 크기 값을 나타낸다. 식 (2)는 각 센서에서 힘의 방향과 크기를 구하여 하나로 합친 척력이다.
인력장은 에이전트 자신의 중심으로 다른 에이전트를 끌어 들이는 힘을 계산할 때 사용한다. 인력장의 힘은 척력장의 힘 계산과 동일하지만 힘의 방향이 역으로 향하도록 SensorValue와 AgentValue의 위치를 바꾸어 반대가 되도록 하였다. 아래의 식 (3)은 NF에 매핑된 인력장의 AF로부터 힘을 계산하는 식이다.
PPT Slide
Lager Image
에이전트는 기본 행동 조종력과 NF에 의한 조종력을 합산하여 조종 행동 제어에 필요한 최종 조종력을 계산한다. 에이전트의 조종행동은 상황에서 따라 하나의 힘만으로 처리할 수 없는 경우가 많이 있다. 예로, 충돌처리를 하면서 목적지까지 도착하는 것이 대표적인 경우이다. 어떤 조건을 보다 우선시 하는가 혹은 더 많은 영향을 받는가에 따라서 에이전트 간 충돌이 일어나고 목적지까지 도달하지 못하는 경우도 발생한다. 이는 조종력을 어떻게 조합하느냐에 따라 에이전트가 목적을 달성 할 수도 있고 그렇지 않을 수도 있다. 따라서 에이전트의 조종행동을 결정하는 최종 조종력 Ffinal 은 식 (4)에서와 같이 에이전트의 기본 행동 조종력(B), 인력장의 조종력(A),척력장의 조종력(R), 충돌회피 조종력(C)을 선형결합해서 구한다. 각 α, β, λ, δ 는 에이전트의 상태에 따른 각각의 조종력을 조절하기 위한 가중치이다. 이 가중치는 어떤 조종력을 우선시 할 것인지에 따라 에이전트의 다양한 움직임을 표현할 수 있다. 그리고 필요한 따라서는 다양한 조종력을 추가할 수 있다.
PPT Slide
Lager Image
- 4.2 충돌회피
본 논문에서는 충돌회피를 위해 AF, NF와 같은 역장(Force Field)형식의 컬러코드화된 이미지를 이용함으로써 기존 O( N 2 )수준의 에이전트간 상호작용 계산량을 O(N)수준의 실시간처리 방법을 제안한다. AF를 이용한 충돌회피방법은 에이전트 자신이 척력장과 같은 충돌회피를 위한 AF를 가지는 것이다. 이는 에이전트를 움직이는 자성체로 간주하고 같은 극을 가진 에이전트들이 상호 회피하려는 동작을 하도록 설계하였다.
제안한 충돌회피는 사전충돌영역 감지단계와 이를 기반으로 한 상호충돌회피 단계로 진행된다. 먼저, 사전충돌영역 감지단계는 Fig. 9 (a)와 같이 동일한 역장의 세기를 갖는 에이전트의 유도장 (AF)이미지를 사용한다. Fig. 9 (b)와 같이 사전충돌영역 감지용 AF를 사전충돌 NF에 맵핑하면 충돌에 의해서 만들어진 중첩 영역이 다른 영역보다 색상 농도가 높아진 영역이 나타난다. 이 영역이 사전 충돌감지영역이다. 에이전트는 이 사전 충돌영역의 역장 값으로 사전 충돌 영역을 감지할 수 있다. 사전 충돌영역의 역장으로는 충돌회피를 처리할 수 없다. 왜냐하면, Fig. 9 (a)와 같이 에이전트간 거리가 멀거나 가깝더라도 동일한 컬러코드 값을 읽어오기 때문에 충돌회피 움직임이 표현되지 않는다. 그래서 다음 단계인 상호충돌회피 단계에서 충돌회피를 처리한다. 상호충돌회피 단계는 Fig. 9 (c)와 같이 상호충돌회피를 위한 에이전트의 척력장 AF를 이용해 상호충돌회피 NF에 맵핑 후 Fig. 9 (d)와 같이 센서를 통해 읽어드린 척력장의 값으로 충돌회피 조종력 계산하여 에이전트의 최종조종력에 선형결합형태로 적용된다.
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
Collision avoidance by way of AF-based repulsive field.
충돌회피 조종력은 위의 식 (5)과 같이 계산된다. 여기서, N 은 에이전트의 전방 센서의 개수를 나타내다. AgentValue는 에이전트 중심위치에서 척력장 값을 나타내고, SensorValue(N)은 전방센서 위치에서의 척력장 값을 나타낸다. ωC 는 충돌회피 조종력의 가중치 계수이다. 충돌회피 조종력계산은 식 (6)와 같이 에이전트의 센서 위치에서의 척력장 값과 에이전트의 중심위치에서의 척력장 값의 차를 지수함수로 취하여 합하여 구한다. 여기서 지수함수를 취한 이유는 에이전트 중심에서 척력이 가장 강하고 거리에 따라 지수 함수적으로 감소하도록 하기 위함이다.
5. 시뮬레이션 실험
본 시뮬레이션에서는 에이전트기반의 대규모 군중행동 시뮬레이션에서 많이 사용되는 횡단보도와 같은 교차환경을 대상으로 실험하였다. 먼저, A,B 두개의 에이전트 그룹으로 나누고 각각의 에이전트그룹이 목적지로 하는 목적장의 NF를 Fig. 10 와 같이 생성하였다. 목적장 NF는 에이전트들을 목표위치로 이동시키기 위한 인력장의 역할을 한다. Fig. 10 의 화살표 모양은 스칼라장의 구배방향을 표현한 것이다. Fig. 10 (a)는 에이전트 그룹A의 목적장 NF로 왼쪽에서 오른쪽으로 이동하는 형태의 포텐셜장 이미지이다. 반대로 Fig. 10 (b)는 에이전트 그룹B가 목적장 NF로 오른쪽에서 왼쪽으로 이동하는 형태의 포텐셜장 이미지이다.
PPT Slide
Lager Image
Environment setting for cross simulation.
본 교차 시뮬레이션에서는 에이전트 그룹 A와 B의 목적장 NF( Fig. 11 (a)(b))와 사전충돌영역 감지 NF( Fig. 11 (c)) 그리고 충돌회피처리를 위한 척력장 NF( Fig. 11 (d))로 총 4개의 NF를 사용하였다. 각 그룹의 에이전트들은 자신들의 센서를 통해 해당되는 NF에서 포텐셜장 값만 읽어 들이기 때문에 충돌회피처리에 대한 계산량을 O(N)수준으로 줄이 수 있다.
PPT Slide
Lager Image
Four NF images used for cross simulation.
Fig. 12 (e)는 교차 시뮬레이션 5초 후에 나타난 결과로 왼쪽에서 오른쪽으로 이동하는 에이전트 그룹 A(황색)가 조밀하게 모여 있는 에이전트 그룹B를 피하기 위해 외각으로 이동하려는 모습을 볼 수 있다. Fig. 12 (f)는 시뮬레이션 20초 후에 나타난 결과로 상호 에이전트끼리 교차상태 심화 되는 것을 알 수 있다. Fig. 12 (g)는 시뮬레이션 40초 후에 나타난 결과로 중심 부분에서는 교착상태가 아직 이루어지고 있지만 상대적으로 외각 쪽의 일부 에이전트 교착이 해소되어 빨리 이동하고 있는 모습을 알 수 있다. 또한 에이전트끼리 상호 뚫고 들어가는 형상은 전혀 보이지 않고 충돌회피를 잘 하면서 목적지로 이동하고 있는 것을 알 수 있다. 그리고 기존의 제안 방법 [18] 에서는 200명 정도의 군중 시뮬레이션을 실시간 처리하지 못하는 반면에 본 연구에서는 Fig. 12 (h)에서 보는 것과 같이 20000명 정도의 대규모 군중 교차 시뮬레이션에 있어서도 실시간으로 상호 충돌 없이 잘 회피하고 있음을 알 수 있었다.
PPT Slide
Lager Image
Experimental results of cross avoidance simulation.
6. 결 론
본 논문에서는 대규모 군중행동 시뮬레이션에서 복잡한 연산 시간을 필요로 하는 에이전트 간 상호작용을 AF과 NF이라는 이미지기반의 포텐셜 역장을 이용하여 실시간 시뮬레이션이 가능한 방법을 제안하였다.
제안 방법은 군중의 세밀한 행동 제어뿐만 아니라 상호작용을 포텔셜장의 집합 연산을 통해 충돌체크 및 회피에 대한 계산량을 O( N 2 )에서 수준에서 O( N )으로 최소화하여 고 밀집 군중 시뮬레이션이 실시간으로 가능한 새로운 방법이다. 특히, 제안한 유도장과 항해장 모델은 기존의 복잡한 수식 및 함수를 사용하지 않고 에이전트 간 사실적인 상호작용을 국소적으로 처리할 수 있어 군중 시뮬레이션에서 가장 문제가 되는 상호작용 연산 비용을 획기적으로 줄일 수 있다. 또한 제안 방법은 대규모 군중시뮬레이션에서 중요한 두 가지 필수 요소인 거시적인 군중의 흐름제어와 미시적인 에이전트 간 상호작용을 동시에 실시간으로 표현할 수 특징이 있다. 단, 본 연구에서는 평면상에서 시뮬레이션 결과로 다양한 임의지형상에서 적용가능성에 대해서 검토할 필요가 있고 또한 향후, 제안한 방법을 토대로 사실적인 데이터를 기반으로 한 교통시뮬레이션 및 재난 시뮬레이션에 적용하여 그 타당성을 보다 심도 있게 검토하고자 한다.
BIO
옥 수 열
1994년 2월 동아대학교 산업공학과 공학사
1998년 3월 일본 Tsukuba대학교 이공학연구과 공학석사
2001년 8월 일본 Tsukuba대학교 공학연구과 공학박사
2001년 8월~2004년 1월 일본 통신종합연구소(CRL) 연구원
2004년 3월~현재 동명대학교 게임공학과 부교수
관심분야 : 게임 인터페이스, 게임 인공지능, 컴퓨터 그래픽스, 가상현실, GPU병렬처리
References
McDonnell R. , Dobbyn S. , O’Sullivan C. 2006 “Crowd Creation Pipeline for Games” Proceeding of International Conference on Computer Games 183 - 190
Snape J. , Berg J.V. , Guy S.J. , Manocha D. 2009 “Independent Navigation of Multiple Mobile Robots with Hybrid Reciprocal Velocity Obstacles” Proceeding of IEEE/RSJ International Conference on Intelligent Robots and Systems 5917 - 5922
Lin M.C. , Manocha D. 2010 “Virtual Cityscapes: Recent Advances in Crowd Modeling and Traffic Simulation” Frontiers of Computer Science in China 4 (3) 405 - 416    DOI : 10.1007/s11704-010-0119-y
Paris S. , Donikian S. 2009 “Activity-Driven Populace: A Cognitive Approach to Crowd Simulation” IEEE Computer Graphics and Applications 29 (4) 34 - 43    DOI : 10.1109/MCG.2009.58
Reynolds C.W. 1987 “Flocks, Herds and Schools: A Distributed Behavioral Model” Proceeding of the 14th Annual Conference on Computer Graphics and Interactive Techniques Vol. 21, No. 4 25 - 34
Helbing D. , Molnar P. 1995 “A Social Force Model for Pedestrian Dynamics” Physical Review E 51 (5) 4284 - 4286    DOI : 10.1103/PhysRevE.51.4282
Helbing D. , Farkas I. , Viscek T. 2000 “Simulating Dynamical Features of Escape Panic” Nature 407 (6803) 487 - 490    DOI : 10.1038/35035023
Yamamoto K. , Kokubo S. , Yamashita H. , Nishinari K. 2008 “Simulation of Fire Evacuation by Real-Coded Cellular Automata(rca)” Proceeding of the 8th international conference on Cellular Automata for Research and Industry 447 - 454
Berg J.P. , Lin M.C. , Manocha D. 2008 “Reciprocal Velocity Obstacles for Real-Time Multi-Agent Navigation” Proceeding of IEEE International Conference on Robotics and Automation 1928 - 1935
Henderson L.F. 1974 “On the Fluid Mechanics of Human Crowd Motion” Transportation Research 8 (6) 509 - 515    DOI : 10.1016/0041-1647(74)90027-6
Helbing D. 1992 “A Fluid-Dynamic Model for the Movement of Pedestrians” Complex Systems 6 (5) 391 - 415
Helbing D. 2001 “Traffic and Related Self-driven Many Particle Systems” Reviews of Modern Physics 73 (4) 1067 - 1141    DOI : 10.1103/RevModPhys.73.1067
Ondřej J. , Pettré J. , Olivier A. , Donikian S. 2010 “A Synthetic-Vision Based Steering Approach for Crowd Simulation” ACM Transactions on Graphics Article No. 123 29 (4) 1 - 9    DOI : 10.1145/1778765.1778860
Kratz L. , Nishino K. 2012 “Going with the Flow: Pedestrian Efficiency in Crowded Scenes” Proceeding of the 12th European conference on Computer Vision 4 558 - 572
Patil S. , Berg J. , Curtis S. , Lin M.C. , Manocha D. 2011 “Directing Crowd Simulations using Navigation Fields” IEEE Transactions on Visualization and Computer Graphics 17 (2) 244 - 254    DOI : 10.1109/TVCG.2010.33
Shimoda S. , Kuroda Y. , Iagnemma K. 2007 “High-Speed Navigation of Unmanned Ground Vehicles on Uneven Terrain using Potential Fields” Robotica 25 (4) 409 - 424    DOI : 10.1017/S0263574706003171
PêTrèS C. , Romero-Ramirez M.A. , Plumet F. 2012 “A Potential Field Approach for Reactive Navigation of Autonomous Sailboats” Robotics and Autonomous Systems 60 (12) 1520 - 1527    DOI : 10.1016/j.robot.2012.08.004
Golas A. , Naraina R. , Lin M.C. 2013 “Hybrid Long-Range Collision Avoidance for Crowd Simulation” Proceeding of ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games 29 - 36
Sung M.K. 2012 “3D Character Motion Synthesis and Control Method for Navigating Virtual Environment using Depth Sensor” Journal of Korea Multimedia Society 15 (6) 827 - 836    DOI : 10.9717/kmms.2012.15.6.827